CS458-658 Network Security

HomeWork 2

From Stallings (do not use computer for any of these problems):

• 8.4
• 8.5
• Extra credit (required for grads): 8.10, 8.11;
• Extra credit for all: 8.12

1. (CRT) 
   • Find an integer x, such that x mod 37 = 27 and x mod 43 = 1
   • Find an integer y, such that y mod 37 = 27 and y mod 43 = -1
   • Find gcd(x-y, 1591) and gcd(x+y, 1591)
   • Do you see any "coincidents" above? Explain.
2. (QR)
   • Indicate which of the integers below are quadratic residues modulo 2537=43*59 and which are not. For each of those that are quadratic residues, find all the square roots (modulo 2537):
         1,-1, 2, -2, 60,-60, 2000,-2000, 2535, -2535, 41, 42, -42, 57, -57, 58,-58
     (hint: use all the simplifications you can to make your computations easier, or even unnecessary)
3. (Factoring)
   • Given n=10403 is a product of two primes p, q, and f(n)=10200, 
     find p,q. (hint: write and solve quadratic equation)
   • Given n=12091, and that 220² mod n = 36, 
     find factors of n. (hint: you might need two square roots)
   • Given n=11639, and x=93, x'=402, be the results of two square root computations for the same number (does it matter which?) such that during the second (that of x') a mistake was made computing the root modulo one of the factors of n.
     Factor n. What would change if the mistake was made during the first computation (of x)?
4. [DH] Let p=11 be the modulus.
   1. What (sub)groups of Z^*_p are generated by the following elements: 1, 2, 3, 4, 5, 8, 9, 10?
   2. Suppose that Alice and Bob run DH protocol and g=2 is selected. If Alice makes her secret a=4 and Bob makes his secret b=7, what will be
      • Alice's message to Bob?
      • Bob's msg to Alice?
      • How will Bob compute the shared secret from Alice's msg?
      • How will Alice compute the shared secret from Bob's msg?
      • Is the result the same?
   3. Now suppose that g=3, and do the previous item again.
   4. Would any of the above change if b=2? Is this a coincidence? Explain.
5. [RSA] Let n=15.
   1. What are the elements of the group mod 15 (Z^*₁₅) ?
   2. What (sub)goups are generated by 1, 2, 3, 4, 7, 12, 13, 14?
6. Now, suppose n=33.
   1. What are the elements of the group mod 33 (Z^*₃₃) ?
   2. What (sub)goups are generated by 1, 2, 3, 4, 5, 10, 30, 31, 32?
   3. Give examples of e,d pairs such that m^e mod 33 would "encrypt" the msg m and c^d mod 33 would decrypt the ciphertext c? Illustrate it for msgs 2,4, 5, 7, 29.
   4. Can you find such e,d for n=35?