Notes on RSA and Diffie-Hellman
1. Mathematical Background of RSA and Diffie-Hellman
RSA
- Prime Factorization: The problem of integer factorization.
- Diffie-Hellman: The discrete logarithm problem.
Let:
$$
s \in \mathbb{Z}_n^2, a_i \in \mathbb{Z}_2^n, e_i \in \mathbb{Z}^n
$$
Define:
$$
a_i \cdot s + e_i
$$
as a certain encryption form.
For example:
$$
\mathbb{Z}_n^2 = {7, 11, 13, 15, 17, 19, 23, 27, 31}
$$
2. RSA Algorithm Steps
Choose two prime numbers:
$$
p = 3, q = 11
$$Then:
$$
n = p \cdot q = 3 \cdot 11 = 33
$$$$
\phi(n) = (p-1)(q-1) = 2 \cdot 10 = 20
$$(Computing the number of integers coprime to ( n ))
- Since ( p, q ) are primes, for all ( a \in \mathbb{Z}^+ ), if ( a < p ), then ( \gcd(a, p) = 1 ), where ( p ) is a prime.
- There are ( (p-1) ) and ( (q-1) ) numbers coprime to ( pq ).
- The total count of numbers up to ( n ) is ( n = p \cdot q ), and ( n ) is divisible by ( q ) and ( p ).
- The total count of numbers not coprime to ( n ) is ( p + q - 1 ).
- Therefore, ( \phi(n) = n - (q + p - 1) = pq - q - p + 1 = (p-1)(q-1) ).
Choose a public key ( e ):
$$
1 < e < \phi(n), , \text{and} , \gcd(e, \phi(n)) = 1
$$For example:
$$
e = 7
$$Compute the private key ( d ):
$$
d \cdot e \equiv 1 , (\text{mod} , \phi(n))
$$Solving:
$$
d = 3
$$Public-private key pair:
- Public key: ( (e, n) = (7, 33) )
- Private key: ( (d, n) = (3, 33) )
3. Encryption and Decryption Process
Suppose the plaintext is ( m = 4 ), the ciphertext ( c ) is:
$$
c = m^e , \text{mod} , n
$$Calculation:
$$
c = 4^7 , \text{mod} , 33 = 16
$$Decrypting to retrieve ( m ):
$$
m = c^d , \text{mod} , n
$$Calculation:
$$
m = 16^3 , \text{mod} , 33 = 4
$$
4. Proof of Correctness of Decryption
The encryption and decryption rely on the following equation:
$$
e \cdot d \equiv 1 ,(\text{mod}, \phi(n))
$$
Thus, we have:
$$
e \cdot d = 1 + k \cdot \phi(n)
$$
From the encryption formula:
$$
c = m^e ,(\text{mod}, n)
$$Using the decryption formula:
$$
m = c^d ,(\text{mod}, n)
$$Substituting ( c ) from the encryption equation:
$$
m = (m^e)^d ,(\text{mod}, n)
$$Consolidating the exponent:
$$
m = m^{e \cdot d} ,(\text{mod}, n)
$$Since ( e \cdot d = 1 + k \cdot \phi(n) ):
$$
m = m^{1 + k \cdot \phi(n)} ,(\text{mod}, n)
$$Applying Euler’s theorem:
$$
m^{\phi(n)} \equiv 1 ,(\text{mod}, n)
$$Simplifying:
$$
m^{1 + k \cdot \phi(n)} \equiv m^1 \cdot (m^{\phi(n)})^k ,(\text{mod}, n)
$$Since ( m^{\phi(n)} \equiv 1 ):
$$
m^{1 + k \cdot \phi(n)} \equiv m ,(\text{mod}, n)
$$
Thus, decryption is correct.
LWD:
$$
\left{ \left(a_i, \langle a_i, s \rangle + e_i \right) : s \gets \mathbb{Z}_q^n, a_i \gets \mathbb{Z}q^n, e_i \gets \chi \right}{i=1}^m
$$
- ( \mathbb{Z} = \mathbb{Z}/q \mathbb{Z} ) represents a finite ring modulo ( q ).
- ( \chi ) is a probability distribution over ( \mathbb{Z} ), used to generate “small numbers” (noise).
- Uniform Distribution: ( \chi ) randomly generates integer values from the range [−B, B] (e.g., [−5,5]), where ( B \ll q/2 ).
The assumption ( B \ll q/2 ) ensures that the noise ( e_i ) does not obscure the modulated result during decryption. - Discrete Gaussian Distribution: Another common distribution, denoted as ( D_{\mathbb{Z}, \sigma} ), with standard deviation ( \sigma ), used to generate near-zero random noise values.
( a \gets D ): a is randomly sampled (or generated) from probability distribution D.
( a \gets S ): When S is a finite set, a is randomly and uniformly selected from S.
( a_i \in \mathbb{Z}_q^n ): This denotes an ( n )-dimensional vector space modulo ( q ), where each component belongs to ( \mathbb{Z}_q ).