Lecture Notes on RSA Cryptosystem and Chinese Remainder Theorem

Assignment Updates

• Assignment 3 grades are posted with comments available for review.
• Assignment 4 is due today.
• Assignment 5, focusing on the RSA cryptosystem's programming aspect, will be released today and will have undergraduate and graduate versions.

RSA Cryptosystem Recap

• Lectures covered:
  • Introduction to public-key cryptosystems.
  • Mathematical preliminaries.
  • RSA cryptosystem description and correctness proof.
• The correctness proof had a minor issue that needs correction.

RSA Implementation Guidelines

• Use integer arithmetic exclusively. Avoid floating-point or real number arithmetic.
• Implement algorithms taught in the course yourself without using library functions.

RSA Key Generation Algorithm

• Bob selects two large prime numbers, $p$ and $q$.
• Bob computes $n = p \times q$.
• Bob computes $\phi(n) = (p-1)(q-1)$.
• Bob picks an integer $b$ in $Z<em>{\phi(n)}$ such that $gcd(b, \phi(n)) = 1$. This means $b$ has an inverse in $Z</em>{\phi(n)}$.
• Bob computes the inverse of $b$ mod $\phi(n)$.
• Public Key: $(n, b)$
• Private Key: Factorization of $n$ into $(p, q)$ and the decryption exponent $a$.

Encryption and Decryption Functions

• Encryption: $E(x) = x^b \mod n$, where $x$ is the plaintext.
• Decryption: $D(y) = y^a \mod n$, where $y$ is the ciphertext.
• Both encryption and decryption involve modular exponentiation.

Toy Example of RSA

• $p = 7$, $q = 11$
• $n = 7 \times 11 = 77$
• $\phi(n) = (7-1)(11-1) = 6 \times 10 = 60$
• Pick $b = 13$ in $Z_{60}$
• Check if 13 has an inverse in $Z_{60}$ by computing $gcd(13, 60)$.
  • $gcd(13, 60) = 1$
• Compute $a$, the inverse of $b$ (13) mod 60, using the extended Euclidean algorithm. $a = 37$

Public and Private Keys (Toy Example)

• Public Key: $(77, 13)$
• Private Key: $(7, 11, 37)$

Plaintext and Ciphertext Space

• $Z_{77}$

Encryption Example with Small Numbers

• Plaintext $x = 15$
• Encryption: $15^{13} \mod 77$

Modular Exponentiation Problem

• Direct computation of $x^{13}$ requires 12 multiplications, which is inefficient.

Square and Multiply Algorithm (Russian Peasant Algorithm)

• Efficient method for modular exponentiation.
• Write the exponent in binary.

Example: Computing $15^{13} \mod 77$

• Binary representation of 13: 1101 (i.e., $13 = 8 + 4 + 1$)
• Compute $x^2, x^4, x^8$ through repeated squaring.
• $x = 15$
• $x^2 = 15^2 = 225 \equiv 71 \mod 77$
• $x^4 = 71^2 = 5041 \equiv 36 \mod 77$
• $x^8 = 36^2 = 1296 \equiv 64 \mod 77$
• $x^{13} = x^8 \times x^4 \times x^1 = 64 \times 36 \times 15 \equiv 64 \mod 77$

Decryption Example

• Ciphertext $y = 64$
• Compute $64^{37} \mod 77$.
• Binary representation of 37: 100101 (i.e., $37 = 32 + 4 + 1$)
• Compute successive powers of $y$.
• $y = 64$
• $y^2 = 64^2 \equiv 15 \mod 77$
• $y^4 = 15^2 \equiv 71 \mod 77$
• $y^8 = 71^2 \equiv 36 \mod 77$
• $y^{16} = 36^2 \equiv 64 \mod 77$
• $y^{32} = 64^2 \equiv 15 \mod 77$
• $y^{37} = y^{32} \times y^4 \times y^1 = 15 \times 71 \times 64 \equiv 15 \mod 77$

Formal Description of Square and Multiply Algorithm

• Goal: Compute $x^b \mod n$
• Write $b$ in binary as $b = b<em>{l-1}b</em>{l-2}…b_0$ (L bits).
• Initialize accumulator $z = 1$.
• For $i = l-1$ down to 0:
  • $z = z^2 \mod n$
  • If $b_i = 1$, then $z = z \times x \mod n$
• Output $z$.

Complexity Analysis

• Naive method requires $b-1$ modular multiplications.
• Square and multiply requires $O(l)$ multiplications.
• Significant improvement as $l$ is proportional to $\log_2(b)$.

Bit-Level Complexity

• Let $k = \lfloor \log n \rfloor + 1$ be the number of bits needed to represent any number in $Z_n$.
• Addition/Subtraction: $O(k)$
• Multiplication: $O(k^2)$
• Exponentiation: $O(k^3)$
• RSA encryption and decryption can be performed in cubic time.

Practical Considerations

• RSA is slower than private key cryptosystems like DES.
• RSA may be 1,700 times slower than DES.
• Hybrid encryption is used in practice.

Hybrid Encryption

• Use both public key and private key cryptosystems.
• Alice wants to send message X to Bob.
  • Bob's public key: $k_{Bob}$
  • Bob's private key: $k'_{Bob}$
• Alice encrypts X using DES with key K: $Y = DES_K(X)$.
• Alice encrypts DES key K using Bob's public key: $Z = E<em>{k</em>{Bob}}(K_{DES})$.
• Alice sends Y and Z to Bob.
• Bob decrypts Z using his private key to obtain DES key K: $K<em>{DES} = D</em>{k'_{Bob}}(Z)$.
• Bob decrypts Y using DES with key K to obtain X: $X = DES_K^{-1}(Y)$.

Correctness of RSA Cryptosystem and Chinese Remainder Theorem (CRT)

• Need to show that encryption followed by decryption yields the original message.
• RSA's plaintext space is $Z<em>n$, not just $Z</em>n^*$.
• Chinese Remainder Theorem is used to prove the correctness of RSA.

Chinese Remainder Theorem (CRT)

• Let $m<em>1, m</em>2, …, m_r$ be pairwise relatively prime numbers.
• Let $M = m<em>1 \times m</em>2 \times … \times m_r$.
• CRT states that there is a unique solution to the following system of congruences modulo M:
  • $x \equiv a<em>1 \mod m</em>1$
  • $x \equiv a<em>2 \mod m</em>2$
  • $\vdots$
  • $x \equiv a<em>r \mod m</em>r$

Proof of Chinese Remainder Theorem (by Construction)

• Define $M<em>i = M / m</em>i$ (product of all $m$'s except $m_i$).
• $gcd(M<em>i, m</em>i) = 1$.
• Therefore, $M<em>i$ has an inverse $y</em>i$ in $Z<em>{m</em>i}$.
• $x = \sum<em>{i=1}^{r} a</em>i M<em>i y</em>i$ is a solution to the system of congruences.
• To show this, consider the equation modulo $m_j$:
  • All terms except $a<em>j M</em>j y<em>j$ vanish because they have $m</em>j$ as a factor.
  • Since $M<em>j y</em>j \equiv 1 \mod m<em>j$, we have $x \equiv a</em>j \mod m_j$.

Uniqueness of Solution

• Suppose X and Y are both solutions.
• Then $x \equiv a<em>i \mod m</em>i$ and $y \equiv a<em>i \mod m</em>i$ for all i.
• Therefore, $x \equiv y \mod m_i$ for all i.
• This implies $x - y \equiv 0 \mod m_i$ for all i.
• Thus, $m_i$ divides $x - y$ for all i.
• Since the $m<em>i$ are pairwise relatively prime, $M = m</em>1 \times m<em>2 \times … \times m</em>r$ divides $x - y$.
• This means $x \equiv y \mod M$, so the solution is unique up to modulo M.