Internet Infrastructure Security

[anthonyhk7]

urgent 《Internet Infrastructure Security》

1. (Affine Cipher) Recall that the encryption function for the Affine Cipher is EK(m) = (a ×
m + b) mod 26. Moreover, not all values in {0, 1, · · · , 25} can be used for a. To illustrate
it, consider a = b = c = 10. Explain why a = 10 cannot be used. (Note: do not use
multiplicative inverse for the explanation).

2. (The Chinese Remainder Theorem, CRT) The CRT is very useful for reducing the computational complexity of RSA by decomposing a number from a large modulus into several
numbers coming from smaller moduli (a plural of modulus). For example, given a number
3000 from Z5797 (5797 = 11 × 17 × 31), decompose it into numbers from smaller moduli.

3. (RSA) Consider RSA with p = 7 and q = 11. Are 5 and 7 legitimate values for e and why?
If any of the two values is legitimate, find the corresponding d.

thanks for help!
i need the steps for my revision! Really Thanks all!

 

[statdad]

OK, what have you tried?

 

[anthonyhk7]

i have try my best to read the notes and google,
but until some steps don't know how to process the following parts
such as step 4...

1. Select primes p=11, q=3.
2. n = pq = 11.3 = 33
phi = (p-1)(q-1) = 10.2 = 20
3. Choose e=3
Check gcd(e, p-1) = gcd(3, 10) = 1 (i.e. 3 and 10 have no common factors except 1),
and check gcd(e, q-1) = gcd(3, 2) = 1
therefore gcd(e, phi) = gcd(e, (p-1)(q-1)) = gcd(3, 20) = 1
4. Compute d such that ed ≡ 1 (mod phi)
i.e. compute d = e-1 mod phi = 3-1 mod 20
i.e. find a value for d such that phi divides (ed-1)
i.e. find d such that 20 divides 3d-1.
Simple testing (d = 1, 2, ...) gives d = 7
Check: ed-1 = 3.7 - 1 = 20, which is divisible by phi.
5. Public key = (n, e) = (33, 3)
Private key = (n, d) = (33, 7).