In the problems below, “textbook” refers to Douglas R. Stinson, Cryptography: Theory and Practice, Third Edition, Chapman & Hall/CRC, 2006.

Problem 1: Homomorpohic Mapping χ

Textbook, problem 5.5.

 
Solution:

According to Chinese remainder theorem, define the function χ^-1 : Z₃ × Z₅ × Z₇ → Z₁₀₅ as follows:

(1)

where {n_i} = {3,5,7}, N_i = 105∕n_i and M_i = N_i^-1 mod n_i. Therefore, we compute χ^-1(a₁,a₂,a₃) as follows:

(2)

Thus we can compute χ^-1(2,2,3) = (70 × 2 + 21 × 2 + 15 × 3) mod 105 = 17.

Problem 2: Chinese Remainder Theorem

Textbook, problem 5.6.

 
Solution:

According to Chinese remainder theorem, define x as follows:

(3)

Therefore, we compute χ^-1(a₁,a₂,a₃) as follows:

n₁ = 25, N₁ = 702, M₁ = 702^-1 mod 25 = (-12) mod 25 = 13.

n₂ = 26, N₂ = 675, M₂ = 675^-1 mod 26 = (-1) mod 26 = 25.

n₃ = 27, N₃ = 650, M₃ = 650^-1 mod 27 = (-13) mod 27 = 14.

Problem 3: Primitive Root

Textbook, problem 5.9.

 
Solution:

Lucas test says, g is a primitive root of p if and only if g^(p-1)∕q ⁄≡ 1 (mod p) for all q > 1 such that q∣(p - 1). Now because p and q are odd primes such that p = 2q + 1, there are only two integers that we need to test with, 2 and q. We know that α ⁄≡±1 (mod p). Then α² ⁄≡ 1 (mod p) since if it were, α would be a square root of 1 (mod p), and the only square roots of 1 modulo a prime are ±1.

Now let us look at α^q. Since p is a prime and α Z*_p, then ϕ(p) = p- 1 = 2q, so by Euler’s theorem, α^2q ≡ 1 (mod p). Then α^q is a square root of 1 (mod p), so

(4)

According to Lucas test, α is a primitive root of p if and only if α^q ⁄≡ 1 (mod p). Combining this with (4), we conclude that α is a primitive root of p if and only if α^q ≡-1 (mod p).

Problem 4: RSA Speedup

Textbook, problem 5.13.

 
Solution:

1. We have the following equations:
   
   Combining (5) and (7) gives

   (10)

   Since p is prime, ϕ(p) = p - 1. According to Euler’s theorem, if gcd(a,p) = 1, then a^p-1 ≡ 1 (mod p), which implies

   (11)

   Combining (10) and (11) gives

   (12)

   Similarly, from (6) and (8) we can derive

   (13)

   Therefore, according to Chinese reminder theorem, there is a unique solution for y^d mod p, which is calculated exactly the same as (9) does. Thus we conclude that the value x returned by this algorithm is in fact y^d mod p.

2. 
3. 

Problem 5: RSA Insecure Against Chosen Ciphertext Attack

Textbook, problem 5.14

 
Solution:

Let yŷ ≡ 1 (mod n). Then the multiplicative property implies

(14)

Applying decryption function D_K^′(⋅) to both sides of (14) and noting D_K^′(1) = 1, we have

(15)

Given , we can easily compute x using extended Euclidean algorithm.

Problem 6: RSA Common Modulus Failure

Textbook, problem 5.16.

 
Solution:

1. We have the following equations:
   
   Plugging (17-19) into (20) gives
   
2. Applying (18-20) gives