Questions tagged [cryptography]
Questions on the mathematics behind cryptography, cryptanalysis, encryption and decryption, and the making and breaking of codes and ciphers.
1,922
questions
1
vote
1
answer
32
views
AES S-box as simple algebraic transformation
The next matrix represents the Rijndael S-box according to wikipedia and other sources
$$\begin{bmatrix}s_0\\s_1\\s_2\\s_3\\s_4\\s_5\\s_6\\s_7\end{bmatrix} =
\begin{bmatrix}
1 & 0 & 0 &...
1
vote
2
answers
41
views
Fermat's last Theorem and elliptic curve cryptography
AFAIR, elliptic curve cryptography became popular soon after Fermat's last Theorem had been proven. Is it just a coincidence, or some important cryptographic properties of elliptic curves follow from ...
0
votes
0
answers
38
views
Fully homomorphic encryption textbook suggestion
I am looking for mathematics textbooks which include a rigorous introduction to fully homomorphic encryption and especially CKKS / TFHE algorithms at the level of Boneh and Shoup's A Graduate Course ...
1
vote
0
answers
45
views
Conway Polynomial for p=2, n=3?
Im doing an exercise on Conway polynomials. As far as im concerned, for p=2, n=3 both
$f(x)=x^3 + x^2 + 1$
and
$g(x)=x^3 + x + 1$
satisfy every condition. According to every source i found, the latter ...
0
votes
0
answers
31
views
How can I be certain of the existence of elliptic curves of certain order when the parameter a is fixed?
My question came up while researching an attack on Elliptic Curve Cryptography (described in Computer Security - ESORICS 2015.
I'm given an elliptic curve $E$ defined by $y^2=x^3+ax+b$ over the finite ...
0
votes
1
answer
37
views
Determine Whether a Pseudorandom Generator Is Secure
Let $G: \{0, 1\}^s \to \{ 0, 1\}^n$ be a secure pseudorandom number generator (with $s$ seed bits and $n$ output bits).
I have attached a problem below that I am confused about; Which generator $G'$ ...
0
votes
0
answers
32
views
Problems about Probability Analysis of the Success Rate
I am currently reading a paper on linear cryptanalysis and I am a bit confused by the probability analysis of its success rate. I wonder if I can seek advice here?
Let $N$ be the number of given ...
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
1
vote
0
answers
29
views
Proof of Golomb's three randomness postulates for binary sequences [closed]
I want to prove that the binary sequence generated by a max-length linear feedback shift register (LFSR) satisfies Golomb's balance, run and autocorrelation postulates:
The numbers of zeros and ones ...
0
votes
0
answers
16
views
$\epsilon$-secure encryption system
Suppose the message space of a symmetric key encryption system is infinite (countable) with a probability distribution on it such that { $m \in M: Pr(m) \neq 0$ } is infinite. For a real number $\...
0
votes
1
answer
43
views
Confusion on the procedure of public-key and private-key cryptography
Procedure: $1):$ choose two distinct primes $p$ and $q$.
$2):$ calculate $n=pq.$
$3):$ compute $\phi(n)=T$.
$4):$ get $E$ from $gcd(E,T)=1.$
$5):$ get $D$ from $ED \equiv 1 \pmod{T}$
To encrypt the ...
4
votes
0
answers
128
views
Shortest vector problem as hidden subgroup problem
I posted this question on the cryptography stack exchange with a bounty, but I haven’t gotten much attention. I think part of the reason might be that I’m really interested in the use of group theory ...
1
vote
0
answers
20
views
Root finding of multivariate polynomials over the integers
TL;DR: is there any library for multivariate polynomial root finding over the integers?
I'm trying to implement an attack on RSA with known bits of p by using Coppersmith, such as shown in this paper. ...
-1
votes
2
answers
71
views
How do I solve a discrete log using pen paper for exam without bruteforcing it? [closed]
I have my Network Security finals. In elgamal cryptosystem, I am often encountering these equations like this
3 = (10^XA) mod 19
now everywhere I am finding only ...
0
votes
0
answers
15
views
Analyze the probability distribution of a specific sequence $S(x)$ with compensation mechanism
I'm developing a theoretical model for a sequence $S(x)$ equally spaced in the time dimension where each element is randomly preselected from set $\{1,2,...,L\}$, but the real selection(when it's turn)...
2
votes
1
answer
81
views
Embedding degree of an elliptic curve
I've been reading about the embedding degree of elliptic curves in Costello's "Pairings for Beginners". The following equivalent conditions are given for the embedding degree (p51):
where $...
2
votes
1
answer
145
views
Can we do any better bijective mapping of a permutation series which is only bijective for a probabilistic subset of its input domain?
So we want to bijectively map one path to another. But depending on start and target node we can only choose from a subset of all transitions. It would look like this:
We also do not know where one ...
1
vote
1
answer
81
views
RSA finding D key
Given the RSA public key find the decryption key d and decrypt the ciphertext c=5.
Known information:
n=221, p=17, q=13, e=11
$\phi(n) = (p-1)(q-1) = 16\times 12=192$
Equation for finding d:
$$ed\...
0
votes
2
answers
72
views
generating a polynomial algorithm from the given one-way function
I am trying to solve the following problem:
Suppose that $f : \mathbb{N} \rightarrow \mathbb{N} $ is a one-way function
and that for some function $l: \mathbb{N} \rightarrow \mathbb{N}$, the following ...
1
vote
0
answers
33
views
Confusion about Kraft-McMillan inequality for infinite alphabet
I was wondering if the Kraft-McMillan inequality continues to hold for codes with infinite alphabets. The reason I'm confused about this is because I was thinking about a code from $\{0,1\}^*$ to $\{0,...
1
vote
1
answer
84
views
Min and max value of index of coincidence
I am pretty new to cryptography and trying to understand some mathematical aspects. Studying different types of cipher, I came across the definition of index of coincidence which is as follows:
Index ...
2
votes
1
answer
67
views
Why do we get a connected 2-regular graph?
In reading "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES" by Rostovtsev and Stolbunov, they claim on page 8 that the set $U=\{E_i(\mathbb{F}_p)\}$ of elliptic curves with a specific prime $l$ ...
0
votes
0
answers
38
views
Why do 3 collinear points on an elliptic curve sum to $O$?
I'm working on a problem,
Let $\mathcal{E}:y^2=x^3-2x+1$ be an elliptic curve over the field $\mathbb{F}_5$, and let $P=(0,1)$ be among the points on $\mathcal{E}$. Find the equation of the line on ...
0
votes
0
answers
117
views
Confusion over the use of the term "module" in mathematics and post-quantum cryptography.
In post-quantum cryptography, there's a suite of algorithms based on "modular lattice". These schemes are defined in terms of vectors and matrices whose elements are polynomials of a fixed ...
0
votes
1
answer
49
views
Wouldn't it be easy to find private keys with the Diffie Hellman exchange? [closed]
I recently watched this video by Computerphile, where Mike explains the mathematics of the Diffie Hellman exchange. I've been wondering, since as explained $g$, $g^a$ and $g^b$ is public, can't you ...
0
votes
0
answers
74
views
the difference between a set and an ensemble
I am reading a paper in cryptography, there is something that I cannot understand well! here is the paragraph:
An inherently unobfuscatable function ensemble is an ensemble
$\{H_k\}_{k∈N}$ of ...
0
votes
0
answers
14
views
Notation for weighted norm of polynomial in lattice reduction
Where does this definition for the weighted norm of a polynomial $h(x,y)$ come from?
I do not understand the notation for the weighted norm of a polynomial because I am used to summation notation with ...
0
votes
0
answers
64
views
question about a derivation of an inequality [ related to wieners attack in cryptography ]
I had a question
regarding a formula derivation from a cryptography class
I am taking. Not really a crypto question.. Just more wondering how
does one go from LHS to RHS in above equality ?
$d<=(N^...
0
votes
1
answer
90
views
inverse problem about scalar multiplication on koblitz curves (or more exactly the secp256k1)
My problem is given $Q=nP$ to find point $P$ given 257 bits long integer $n$ and point $Q$.
It’s something possible on other curves but Koblitz curves have extra characteristic and can’t be converted ...
0
votes
1
answer
107
views
Find all pairs of keys $(a, b)$ for affine ciphers.
The question is as follows:
Find all pairs of integer keys $(a, b)$ for affine ciphers for which
the encryption function $c = (ap + b) \bmod 26$ is the same as the
corresponding decryption function.
...