In the problems below, “textbook” refers to Wade Trapp and Lawrence C. Washington, Introduction to Cryptography with Coding Theory, Second Edition, Prentice-Hall, 2006.

Problem 1: Divides and mod

Textbook, exercise 3-7.

Solution: Let (n) be the multi-set that includes all prime factors of n. For example, (8) = {2,2,2} and (12) = {2,2,3}.

1. ab ≡ 0 (mod p) implies that p∣ab. Because p is prime, we have either p (a) or p (b) (or both). In the first case, p∣a and thus a ≡ 0 (mod p). In the second case, p∣b and thus b ≡ 0 (mod p).
2. n∣ab implies that (n) ⊆ (ab). gcd(a,n) = 1 implies that (n) ⁄⊂ (a). Therefore, it follows that (n) ⊆(b), and thus n∣b.

Problem 2: Chinese Remainder theorem

Textbook, exercise 3-10.

Solution: Assume the smallest number is x. Then we set up the following formulas according to the available information.

Let y be the next smallest number. We know that y = 58 + 60 = 118, because x ≡ y mod 60.

Problem 3: Euler theorem

Textbook, exercise 3-12.

Solution: Because 101 is prime, we have ϕ(101) = 100. Since 2 is relatively prime to 101, 2 Z₁₀₁^*. By Euler’s theorem,

Let x be the remainder of dividing 2¹⁰²⁰³ by 101. Then

Thus, x = 8.

Problem 4: Order

Textbook, exercise 3-20.

Solution:

1. gcd(a,n) = 1 implies that a Z_n^*. By Euler’s theorem, a^ϕ(n) ≡ 1 (mod n). Thus r ≤ ϕ(n), because r is the smallest positive integer such that a^r ≡ 1 (mod n).
2. a^m ≡ a^rk ≡ (a^r)^k ≡ 1^k ≡ 1 (mod n).
3. a^t ≡ a^qr+s ≡ (a^r)^q × a^s = a^s (mod n). Because a^t ≡ 1 (mod n), we have a^s ≡ 1 (mod n).
4. By definition, r is the smallest positive integer such that a^r ≡ 1 (mod n). It follows that s = 0 because a^s ≡ 1 (mod n) and 0 ≤ s < r. Therefore, t = qr and thus r∣t.
5. Combining parts (b) and (c) gives that a^t ≡ 1 (mod n) iff ord_n(a)∣t. It follows that ord_n(a)∣ϕ(n) because a^ϕ(n) ≡ 1 (mod n).

Problem 5: Rabin cryptosystem

Textbook, exercise 3-27.

Solution:

1. • Assume n ∤ m. Then m Z_n^* and thus x has 4 square roots module n. Thus, each time the machine has a probability of 1∕4 returning the meaningful message m. The expected number of trials is thus 4.
   • Assume p∣m and q ∤ m. Then x has 2 square roots module n. Thus, each time the machine has a probability of 1∕2 returning the meaningful message m. The expected number of trials is thus 2.
   • Assume q∣m and p ∤ m. The analysis is similar to the previous case and thus the expected number of trails is 2.
   • Assume n∣m. Then x = 0. This is a special case and thus should be easily decrypted.
2. A good message m is in Z_n^*. It is hard for Oscar to determine m, because it is believed that there is no feasible algorithm to compute the square root of a number in Z_n^* without knowing the factorization of n.
3. Eve chooses m = 1 and computes x = m² mod n = 1. Then Eve repeatedly feeds the machine with x until 2 different numbers a,-a are obtained, such that a and -a are not equal to 1 or -1 module n. This is possible because x Z_n^* and thus has 4 different square roots module n. Therefore, a + 1 and a - 1 are both non-zero. Since

   we have either p∣(a + 1) or q∣(a + 1). Without loss of generality, assume p∣(a + 1). Then Eve computes p = gcd(a + 1,n) and q = n∕p.

Problem 6: Adaptive chosen ciphertext attack against RSA

Textbook, exercise 6-7.

Solution: We know that 2 is relatively prime to n because n is a product of two odd primes. Therefore, 2 Z_n^*. By Euler’s theorem, 2^ϕ(n) ≡ 1 (mod n). By the definition of RSA algorithm, ed ≡ 1 (mod ϕ(n)). Thus, we have

Let x = D_d(2^ec mod n), where D is the decryption function used by Nelson. After obtaining x from Nelson, Eve computes the inverse of 2 module n by the extended Euclidean algorithm. Then Eve computes m = (2^-1x) mod n.

Problem 7: Same modulus attack on RSA

Textbook, exercise 6-16.

Solution: Since e_A and e_B are relatively prime, gcd(e_A,e_B) = 1 and thus xe_A + ye_B = 1 for some integers x and y. Using extended Euclidean algorithm to solve this linear Diophantine equation, Eve gets a working pair (x,y). Then we have

Thus, after intercepting c_A and c_B, Eve computes m = [(c_A)^x(c_B)^y] mod n.

Problem 8: RSA puzzle

Textbook, exercise 6-23.

Solution: Since gcd(e,12345) = 1, ex + 12345y = 1 for some integers x and y. Using extended Euclidean algorithm to solve this linear Diophantine equation, we get a working pair (x,y). Since m¹²³⁴⁵ ≡ 1 (mod n), we have

Thus, we decrypt m by computing c^x mod n.