Question

Suppose that RSA is used to send a message \(m\) to three recipients, who have relatively prime encryption moduli \(n_{1}, n_{2}\), and \(n_{3} .\) All three recipients use the same encryption exponent \(e=3\), a once-popular choice as it makes encryption very fast. Show that someone who intercepts all three encrypted messages \(c_{1}=m^{3}\) \(\bmod n_{1}, c_{2}=m^{3} \bmod n_{2}\), and \(c_{3}=m^{3} \bmod n_{1}\) can efficiently decipher \(m .\) Hint: The Chinese remainder theorem implies that you can efficiently find a \(c\) such that \(c=c_{1} \bmod n_{1}, c=c_{2} \bmod n_{2}\), and \(c=c_{3} \bmod n_{3} .\) Assume this, and show that it implies \(c=m^{3} \bmod n_{1} n_{2} n_{3} .\) Then note \(m^{3}

Short answer

Use CRT to solve \(c = m^3 \mod (n_1 \cdot n_2 \cdot n_3)\) and find \(m\) by taking the cube root of \(c\).

Step-by-step solution

Information Setup

Identify the given information. Encryption exponent is given as \(e=3\). We have three encryption moduli \(n_1, n_2, n_3\), all of which are relatively prime. The intercepted encrypted messages are \(c_1=m^3 \mod n_1\), \(c_2=m^3 \mod n_2\), and \(c_3=m^3 \mod n_3\).

Use Chinese Remainder Theorem (CRT)

According to the hint, use the Chinese Remainder Theorem to find \(c\) such that it satisfies: \(c \equiv c_1 \mod n_1\), \(c \equiv c_2 \mod n_2\), and \(c \equiv c_3 \mod n_3\). This theorem allows us to efficiently combine the congruences because the moduli \(n_1, n_2, n_3\) are relatively prime.

Combine Congruences

Using CRT, determine \(c\) such that: the value of \(c\) will satisfy: \[ c \equiv c_1 \mod n_1,\]\[ c \equiv c_2 \mod n_2,\]\[ c \equiv c_3 \mod n_3\]This combination can be found efficiently and uniquely modulo \(n_1 \cdot n_2 \cdot n_3\). Hence, we get \(c = m^3 \mod (n_1 \cdot n_2 \cdot n_3)\).

Inequality Condition

Note that since \(m^3 < n_1 \cdot n_2 \cdot n_3\), it implies that \(m^3\) is a positive integer that is less than the product of the three moduli.

Cube Root to Find Original Message

Since \(m^3 < n_1 \cdot n_2 \cdot n_3\), solving for \(m\) can be done by taking the integer cube root of \(c\) to retrieve the original message, i.e., \(m = \sqrt[3]{c}\). This step involves efficient computation since \(c\) is already known from the previous steps.

Key concepts

Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a powerful tool in number theory. It helps to solve system of simultaneous congruences with different moduli. To understand CRT better, consider three numbers: n1, n2, and n3, which are pairwise relatively prime - meaning each pair of numbers share no common divisor other than 1. In RSA cryptography, instead of working modulo one large number, you can split the work across these smaller moduli using CRT for efficiency.
For our problem, we have three moduli n1, n2, and n3 and corresponding ciphertexts:

• c1 = m^3 mod n1
• c2 = m^3 mod n2
• c3 = m^3 mod n3

By applying CRT, you can find a unique integer 'c' such that:
c ≡ c1 (mod n1)
c ≡ c2 (mod n2)
c ≡ c3 (mod n3)
This 'c' helps to combine the modular equations into a single expression efficiently. We end up with c = m^3 mod (n1 * n2 * n3). CRT is critical in simplifying problems involving multiple moduli.

Encryption Moduli

In RSA cryptography, the encryption modulus is a crucial part. An encryption modulus 'n' is typically a product of two large prime numbers, p and q. Each RSA user has their own 'n', which must be kept secret. In this exercise, we deal with multiple recipients having their individual encryption moduli: n1, n2, and n3.
Key aspects of working with encryption moduli include:

• They must be large enough to secure the encryption.
• Each pair of moduli in our problem is relatively prime, ensuring CRT's effectiveness.
• The exponent used (e=3 in this case) also factors into the encryption process.

These moduli determine the group in which operations are conducted. In our case, instead of one large number, the product of three individual moduli is taken, making decryption feasible using CRT.
Encryption moduli ensure that the encryption process is computationally hard to break unless the decryption key is known or special properties, like in this exercise, are leveraged.

Cubing and Cube Roots

In RSA encryption, the message 'm' is usually raised to the power of an encryption exponent 'e'. Here, e=3, meaning m^3. This cubing process makes encryption quick, thanks to its low exponent. However, decryption generally requires knowledge of the private key.
In this exercise, since the intercepted messages are already in cubed form modulo different primes, we use CRT to combine them efficiently. Then we have:
c = m^3 mod (n1 * n2 * n3)
Given the condition that m^3 is less than the product of these moduli (n1 * n2 * n3), finding 'm' is straightforward. We calculate the cube root of 'c'.
The steps can be summarized as:

• Intercept messages c1, c2, and c3.
• Use CRT to combine into c = m^3 mod (n1 * n2 * n3).
• Confirm m^3 < n1 * n2 * n3.
• Compute the cube root to get 'm'.

Cube roots bring back the original message 'm' from its encrypted form efficiently, rounding off the decryption process.