YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer SecurityHandout #13
Xueyuan Su   April 4, 2010



 

Solutions to Problem Set 4

Due on Wednesday, March 24, 2010.

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 P(n) be the multi-set that includes all prime factors of n. For example, P(8) = {2,2,2} and P(12) = {2,2,3}.

  1. ab 0 (mod p) implies that pab. Because p is prime, we have either p ∈P(a) or p ∈P(b) (or both). In the first case, pa and thus a 0 (mod p). In the second case, pb and thus b 0 (mod p).
  2. nab implies that P(n) P(ab). gcd(a,n) = 1 implies that P(n) ⁄⊂ P(a). Therefore, it follows that P(n) P(b), and thus nb.

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.

x ≡ 1  (mod  3)

x ≡ 2  (mod  4)
x ≡ 3  (mod  5)
Let n = 3 × 4 × 5 = 60. The above system has the same form as in Chinese remainder theorem and thus has a unique solution in Zn. Let Ni = n∕ni and Mi = Ni-1 mod ni, for 1 i 3. Using extended Euclidean algorithm to compute Mi, we have
N  = 20,M  =  2
 1        1
N2 = 15,M2 =  3
N3 = 12,M3 =  3
Then x = ( ∑3          )
    i=1 aiMiNi mod n = 58.

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 ∈ Z101*. By Euler’s theorem,

2100 mod 101 = 1

Let x be the remainder of dividing 210203 by 101. Then

x ≡ 210203 ≡ (2100)102 × 23 ≡ 8 (mod 101)

Thus, x = 8.

Problem 4: Order

Textbook, exercise 3-20.

Solution:

  1. gcd(a,n) = 1 implies that a ∈ Zn*. By Euler’s theorem, aϕ(n) 1 (mod n). Thus r ϕ(n), because r is the smallest positive integer such that ar 1 (mod n).
  2. am ark (ar)k 1k 1 (mod n).
  3. at aqr+s (ar)q × as = as (mod n). Because at 1 (mod n), we have as 1 (mod n).
  4. By definition, r is the smallest positive integer such that ar 1 (mod n). It follows that s = 0 because as 1 (mod n) and 0 s < r. Therefore, t = qr and thus rt.
  5. Combining parts (b) and (c) gives that at 1 (mod n) iff ordn(a)t. It follows that ordn(a)ϕ(n) because aϕ(n) 1 (mod n).

Problem 5: Rabin cryptosystem

Textbook, exercise 3-27.

Solution:

  1. A good message m is in Zn*. 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 Zn* without knowing the factorization of n.
  2. Eve chooses m = 1 and computes x = m2 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 ∈ Zn* and thus has 4 different square roots module n. Therefore, a + 1 and a - 1 are both non-zero. Since
    0 ≡ a2 - 1 ≡ (a + 1)(a- 1) (mod pq),

    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 ∈ Zn*. By Euler’s theorem, 2ϕ(n) 1 (mod n). By the definition of RSA algorithm, ed 1 (mod ϕ(n)). Thus, we have

  e d     e e d    ed ed
(2 c)  ≡ (2 m )  ≡ 2  m   ≡ 2m  (mod n)

Let x = Dd(2ec 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 eA and eB are relatively prime, gcd(eA,eB) = 1 and thus xeA + yeB = 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

    x    y     e  x   e y     xe +ye
(cA) (cB) ≡ (m  A) (m B ) ≡ m   A   B ≡ m  (mod  n)

Thus, after intercepting cA and cB, Eve computes m = [(cA)x(cB)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 m12345 1 (mod n), we have

 x     e x     e x   12345 y    ex+12345y
c ≡  (m  ) ≡  (m ) (m     ) ≡ m          ≡ m  (mod n)

Thus, we decrypt m by computing cx mod n.