Cryptography / spring 2012

Exercise 4, week 6

1. If checking a 128-bit key takes a microsecond, how long time is needed to check

all possible 128-bit keys ?

2. A person whose name is AN signs his message by encoding letters of his name (A = 65, N = 78) by his secret RSA key. Sign and check the signature, when the public key is n = 253, e = 3 and secret key n = 253, d = 147.

3. Let in Diffie-Hellman public key encryption p = 11 and g = 2 be its primitive

root (show!).

a) Let J_A = 9 be A’s public key. Determine A’s secret key S_A ?

b) Let J_B = 3 be B’s public key. Determine A’s and B’s common secret key ?

4. Choose p = 11, g = 7, S_A = 5 and S_B = 6 in El Gamal schema. Show first that g is a primitive root of p. What is the result when B encrypts the message m = 9? How A decrypts the encrypted message?

5. If n is nonprime, it has factor £ Ön. How long time does it take to find the factors of a 100 (decimal) digits integer, if million divisions can be completed in a second?