Textbook, Exercise 11.5
Textbook, Exercise 11.17
Extending the previous problem: Show how, if the encryption scheme from Exercise 11.17 is used and you have captured a ciphertext \(c\) that you know encrypts a message \(m\), you can replace \(c\) so that it decrypts to any message of your choice of the same length. (Note that this is stronger than breaking CCA security. Breaking CCA security just means you can tamper with the ciphertext to make a predictable change in the plaintext. Here we’re saying you can replace the message with a message of your choosing.)
One way to pick a large random \(\lambda\)-bit prime is to pick a random odd \(\lambda\)-bit number \(x\), loop to test numbers \(x\), \(x+2\), \(x+4\), \(x+6\) and so on for primality using a function ISPRIME until a prime number is found. Eventually (and generally before very long) one will be prime.
Here’s a mistake someone made in implementing RSA one time: This method was followed to find the prime \(p\), and then they just continued counting to test \(p+2\), \(p+4\), \(p+6\) and so on until a second prime was found, which is \(q\). Now the modulus is \(N=p\cdot q\). Show how you can very quickly factor any number \(N\) generated in such a manner.
In this class, everyone’s first name is less than 10 letters long. You’ll be doing computations with large numbers in this problem, and I would recommend using Python (there are other ways, including writing using the “BigInteger” class in Java, but Python is much easier). Note that in Python, pow(a,b,n) efficiently computes \(a^b\ \%\ n\). For all the parts below, show your work, describing how you did the computations.
Write out your name using ASCII character codes in hexadecimal, and then convert that to decimal (you can do this by hand, but you can also just type the hexadecimal digits into Python preceded by “0x”).
The decimal number 2349310626352960893120133 is an “RSA modulus” that is larger than \(2^{80}\), so should be larger than the value you computed in part a. Using RSA values e=17 and d=1520142169991108573141333, compute the “Textbook RSA” signature of your name. You may give this value either in decimal or hexadecimal.
My public key has RSA modulus 2551255183750716043759591 and e=3. You don’t know my secret signing key \(d\), but since this modulus is so short you can figure it out. Forge a signature on your name (the value from part a) for my key. (Hint: WolframAlpha is pretty good at factoring….)
In the previous question, the public exponents (\(e\)) in both cases were small values. There’s a reason for this!
Trace through the ModExp algorithm from page 235 and count how many squarings and multiplications are required for \(e=3\) (don’t worry about the cost of the mod operation – just count squarings and multiplications).
If \(e\) were a random 80-bit value, approximately half of the bits would be zero and half would be one. Approximate how many squarings and multiplications are required, on average, for such a value.
The most common public exponent \(e\) used in practice is 65,537. What is this number in hexadecimal, and why does this make an efficient exponent?