2. Alice wants to send Bob the signed and enciphered message M = 49. If Bob’s public key is
eB = 41, nB = 4747, and Alice’s private key and modulus are dA = 11, nA = 6667, what value should Alice send?
3. Suppose you work at a company where everyone is given a different RSA key pair, but they all share the modulus n = 143. Your public/private key pair is eM = 13 and dM = 37. Alice’s public key is eA = 47. Use Attack #13 to find a private key that will allow you to impersonate Alice. Like other exercises, the numbers here are kept unrealistically small. This greatly eases the calculations involved and allows you to check your result by factoring n and calculating (n), to see what values will serve as inverses for eA modulo (n). Attack #13 will work for larger moduli, where factoring isn’t feasible.
4. a) What would you send to convey the message M = 95 using an Elgamal signature if
p = 2687, g = 22, a = 17, s = 54, and the random enciphering key for the message is e = 73. b) Now pretend you are the intended recipient and check the validity of the signature. Note that the recipient wouldn’t know s, but v = gs = 678 would be made public by the sender.
5. Suppose the message M = 39 arrives with the Elgamal signature S1 = 1283, S2 = 165. Use
p = 2687, g = 22, and v = 678 to determine if the signature is valid.
You should solve this problem by first calculating the multiplicative inverse of
216 (mod 1019 – 1).
7. Key generation for DSA was done in this chapter by picking a prime q and then testing 2q + 1 for primality. If q must be 100 digits long, how many different prime values would we have to test, on average, to find one such that 2q + 1 is also prime? You may estimate this value by using the prime number theorem from chapter 15. Don’t concern yourself about whether or not a number of the form 2q +1 is more or less likely to be prime, if we know q is prime. Simply find what percentage of numbers of this size are prime and use this fact (in conjunction with the observation that 2q + 1 is always odd) to get your answer.
8. For DSA, the two primes q and p are often taken at 160 and 512 bits, respectively. If q is generated first and we test numbers of the form kq + 1 for primality to find p, how large should k be? Remember, a one bit increase in length doubles the size of the number.
9. A method for finding the two primes, p and q, required by DSA was given by Alexander W. Dent and Chris J. Mitchell in User’s Guide to Cryptography and Standards. It follows below.
“Randomly generate a large prime number p, known as the modulus. The modulus p should be at least 512 bits long…. Randomly generate a large prime q such that q divides into p – 1. The prime q is known as the order and should be at least 160 bits long.”9 Explain why this technique would be more time consuming than the method I suggested. Of course, it is more important to generate the primes securely (i.e., as randomly as possible) than quickly.
10. Verify the claim made in the DSA example that the message cannot be changed from D to C without detection.
11. a) Use DSA to generate a signature for the message M=21 using q = 97, p = 971, g = 169,
s = 35, v = 141, and k = 8. Let the hash function simply take M to M, since M is small.
b) Verify that the signature is valid.
12. Suppose the message M = 75 arrives with the DSA signature S1 = 58, S2 = 79. Use
q = 97, p = 971, g = 169, and v = 141 to determine if the signature is valid.