Discrete Logarithms and RSA Cryptosystem

Discrete Logarithms

Discrete Logarithm is defined as: Given a prime number $p$, a generator $g$, and a value $y$, find $x$ such that $g^x \mod p = y$.

• It is the inverse of modular exponentiation
• Computing discrete logarithms is computationally hard, which forms the basis of many asymmetric cryptosystems (like Diffie-Hellman, ElGamal)
• Example: If $3^x \mod 7 = 6$, then the discrete logarithm $x = 3$

---

RSA Key Generation, Encryption and Decryption

A. Key Generation

• Step a: Choose two large prime numbers $p$ and $q$
• Step b: Compute $n = p \times q$
• Step c: Compute Euler's totient function $\phi(n) = (p-1)(q-1)$
• Step d: Choose public exponent $e$ such that $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$
• Step e: Compute private exponent $d$ such that $e \cdot d \equiv 1 \mod \phi(n)$
• Public Key = $(e, n)$
• Private Key = $(d, n)$

B. Encryption

Ciphertext: $C = M^e \mod n$

C. Decryption

Plaintext: $M = C^d \mod n$

---

Numerical Solution: p = 13, q = 7, M = 'hi'

Step a: Compute n

$$n = p \times q = 13 \times 7 = 91$$

Step b: Compute $\phi(n)$

$$\phi(n) = (p-1)(q-1) = 12 \times 6 = 72$$

Step c: Choose e

Choose $e$ such that $\gcd(e, 72) = 1$ and $1 < e < 72$

Let $e = 5$ (since $\gcd(5, 72) = 1$)

Step d: Compute d

Find $d$ such that $e \cdot d \equiv 1 \mod 72$

$$5 \cdot d \equiv 1 \mod 72$$

$$d = 29 \quad (\text{since } 5 \times 29 = 145 = 2 \times 72 + 1 \equiv 1 \mod 72)$$

Keys:

• Public Key = $(e, n)$ = $(5, 91)$
• Private Key = $(d, n)$ = $(29, 91)$

---

Step e: Convert plaintext M = 'hi' to numbers (a=0, b=1, ..., z=25)

• h = 7
• i = 8

---

Step f: Encryption $(C = M^e \mod n)$

For h (M = 7):

$$C_1 = 7^5 \mod 91$$

$7^2 = 49$ $7^4 = 49^2 = 2401 \mod 91 = 2401 - 26 \times 91 = 2401 - 2366 = 35$ $7^5 = 7^4 \times 7 = 35 \times 7 = 245 \mod 91 = 245 - 2 \times 91 = 63$

$$C_1 = 63$$

For i (M = 8):

$$C_2 = 8^5 \mod 91$$

$8^2 = 64$ $8^4 = 64^2 = 4096 \mod 91 = 4096 - 45 \times 91 = 4096 - 4095 = 1$ $8^5 = 8^4 \times 8 = 1 \times 8 = 8$

$$C_2 = 8$$

Ciphertext = (63, 8)

---

Step g: Decryption $(M = C^d \mod n)$

For $C_1 = 63$:

$$M_1 = 63^{29} \mod 91$$

$63 \mod 91 = 63$ $63^2 = 3969 \mod 91 = 3969 - 43 \times 91 = 3969 - 3913 = 56$ $63^4 = 56^2 = 3136 \mod 91 = 3136 - 34 \times 91 = 3136 - 3094 = 42$ $63^8 = 42^2 = 1764 \mod 91 = 1764 - 19 \times 91 = 1764 - 1729 = 35$ $63^{16} = 35^2 = 1225 \mod 91 = 1225 - 13 \times 91 = 1225 - 1183 = 42$

$63^{29} = 63^{16} \times 63^8 \times 63^4 \times 63^1 = 42 \times 35 \times 42 \times 63 \mod 91$

$42 \times 35 = 1470 \mod 91 = 1470 - 16 \times 91 = 1470 - 1456 = 14$ $14 \times 42 = 588 \mod 91 = 588 - 6 \times 91 = 588 - 546 = 42$ $42 \times 63 = 2646 \mod 91 = 2646 - 29 \times 91 = 2646 - 2639 = 7$

$$M_1 = 7 = \textbf{h}$$

For $C_2 = 8$:

$$M_2 = 8^{29} \mod 91$$

$8^4 \mod 91 = 1$ (calculated above) $8^{29} = 8^{28} \times 8^1 = (8^4)^7 \times 8 = 1^7 \times 8 = 8$

$$M_2 = 8 = \textbf{i}$$

---

Conclusion

Decrypted message = 'hi', which matches the original plaintext, confirming that RSA encryption and decryption work correctly with the generated keys.