post-gu

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

1. Choose two prime numbers:

   $$p=3,q=11$$

   Then:

   $$n=p\cdot q=3\cdot 11=33$$

   $$\varphi (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) ).

2. Choose a public key ( e ):

   $$1<e<\varphi (n),,\text{and},gcd(e,\varphi (n))=1$$

   For example:

   $$e=7$$

3. Compute the private key ( d ):

   $$d\cdot e\equiv 1,(\text{mod},\varphi (n))$$

   Solving:

   $$d=3$$

4. 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},\varphi (n))$$

Thus, we have:

$$e\cdot d=1+k\cdot \varphi (n)$$

1. From the encryption formula:

   $$c=m^e,(\text{mod},n)$$

2. Using the decryption formula:

   $$m=c^d,(\text{mod},n)$$

3. Substituting ( c ) from the encryption equation:

   $$m=(m^e{)}^d,(\text{mod},n)$$

4. Consolidating the exponent:

   $$m=m^{e\cdot d},(\text{mod},n)$$

5. Since ( e \cdot d = 1 + k \cdot \phi(n) ):

   $$m=m^{1+k\cdot \varphi (n)},(\text{mod},n)$$

6. Applying Euler’s theorem:

   $$m^{\varphi (n)}\equiv 1,(\text{mod},n)$$

7. Simplifying:

   $$m^{1+k\cdot \varphi (n)}\equiv m^1\cdot (m^{\varphi (n)}{)}^k,(\text{mod},n)$$

8. Since ( m^{\phi(n)} \equiv 1 ):

   $$m^{1+k\cdot \varphi (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
$$

1. ( \mathbb{Z} = \mathbb{Z}/q \mathbb{Z} ) represents a finite ring modulo ( q ).
2. ( \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 ).