Question

Prove that the RSA decryption algorithm recovers the original message; that is, \(m^{e d} \equiv m \bmod p q .\) Hint: You may assume that, because \(p\) and \(q\) are relatively prime, it suffices to prove the congruence \(\bmod p\) and \(\bmod q\).

Short answer

The RSA decryption algorithm recovers the original message as \(m^{ed} \equiv m \bmod pq\). This is proven using the Chinese Remainder Theorem and Euler's theorem for \(\bmod p\) and \(\bmod q\).

Step-by-step solution

- State the problem clearly

We need to prove that the RSA decryption algorithm recovers the original message, which means proving that \(m^{e d} \equiv m \bmod pq\). Given that \(p\) and \(q\) are relatively prime, it suffices to prove the congruence \(\bmod p\) and \(\bmod q\).

- Understand RSA key structure

In RSA, \(e\) and \(d\) are the public and private exponents, respectively, and they satisfy the relationship \(e d \equiv 1 \bmod (p-1)(q-1)\). This means there exists an integer \(k\) such that \(e d = 1 + k (p-1)(q-1)\).

- Prove congruence modulo p

Consider \(m^{ed} \bmod p\). By Euler's theorem, since \(m \ot\equiv 0 \bmod p\) and \(\phi(p) = p-1\), it follows that \(m^{p-1} \equiv 1 \bmod p\). Thus, \(m^{ed} = m^{1 + k(p-1)} = m \cdot (m^{p-1})^k \equiv m \cdot 1^k \equiv m \bmod p\).

- Prove congruence modulo q

Similarly, consider \(m^{ed} \bmod q\). Again, by Euler's theorem, since \(m \ot\equiv 0 \bmod q\) and \(\phi(q) = q-1\), it follows that \(m^{q-1} \equiv 1 \bmod q\). Therefore, \(m^{ed} = m^{1 + k(q-1)} = m \cdot (m^{q-1})^k \equiv m \cdot 1^k \equiv m \bmod q\).

- Combine results using the Chinese Remainder Theorem (CRT)

Given that \(m^{ed} \equiv m \bmod p\) and \(m^{ed} \equiv m \bmod q\), and since \(p\) and \(q\) are relatively prime, by the Chinese Remainder Theorem, these congruences imply \(m^{ed} \equiv m \bmod pq\).

Conclusion

After following these steps, it is evident that the RSA decryption algorithm correctly recovers the original message, since \(m^{ed} \equiv m \bmod pq\).

Key concepts

RSA algorithm

The RSA algorithm is a cryptographic system used for secure data transmission. It works on the principles of public-key cryptography, where two keys are used: a public key for encryption and a private key for decryption. The process involves three key steps: key generation, encryption, and decryption. The key generation involves selecting two large prime numbers, typically denoted as \(p\) and \(q\), then computing their product \(n = pq\). The Euler's totient function \(\phi(n)\) is calculated as \((p-1)(q-1)\). A public exponent \(e\) is chosen such that \(1 < e < \phi(n)\) and \(e\) is coprime to \(\phi(n)\). The private exponent \(d\) is then determined such that \(ed \equiv 1 \bmod \phi(n)\). Encryption converts a message \(m\) into a ciphertext \(c\) using the formula \(c = m^e \bmod n\). Decryption reverts the ciphertext \(c\) back to the original message \(m\) using \(m = c^d \bmod n\).

Number theory

Number theory is a branch of pure mathematics dealing primarily with integers and integer-valued functions. It involves properties and relationships of numbers, especially the more complex aspects like divisibility, primes, and the solutions of equations in integers. Within the context of the RSA algorithm, number theory provides foundational principles such as prime factorization and the properties of modular arithmetic. Understanding number theory helps in comprehending why certain encryption methods work and establishes the security of algorithms like RSA, which rely on the difficulty of factoring the product of two large primes.

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a result from number theory that provides a way to solve systems of simultaneous congruences with different moduli. It essentially states that if one knows the remainders of the division of an integer by several pairwise coprime integers, then one can uniquely determine the remainder of the division of that integer by the product of these integers. In the context of RSA decryption, CRT is used to combine congruences. Since we prove the congruence separately mod \(p\) and mod \(q\), CRT allows us to conclude that the results hold mod \(pq\). This theorem is crucial for simplifying and speeding up the RSA decryption process.

Euler's theorem

Euler's theorem is a key result in number theory that states: if \(a\) and \(n\) are coprime, then \(a^{\phi(n)} \equiv 1 \bmod n\). Euler's totient function \(\phi(n)\), counts the number of integers up to \(n\) that are relatively prime to \(n\). In RSA, Euler's theorem plays a crucial role as it guarantees the existence of a multiplicative inverse needed for key generation. When we raise the message \(m\) to the power of \(ed\), Euler's theorem helps us show that \(m^{ed} \equiv m \bmod p\) and \(m^{ed} \equiv m \bmod q\). Essentially, Euler's theorem ensures the consistency and correctness of the RSA decryption process.

Modular arithmetic

Modular arithmetic is a system of arithmetic for integers, where numbers wrap around after reaching a certain value, known as the modulus. In RSA encryption and decryption, modular arithmetic is used to ensure that integers do not exceed the bounds set by the modulus, typically \(n = pq\). It involves operations like modular addition, subtraction, multiplication, and exponentiation. To decrypt the message in RSA, we rely on properties of modular exponentiation: computing powers of numbers modulo \(n\). Hence, modular arithmetic is foundational to the functioning of the RSA algorithm, helping in keeping calculations manageable even with large numbers.