Reminder: Look at <file:/home/jake/CSC/index.html> for updates or corrections!
Goal: This optional exercise will give you a feel for the performance aspects of RSA encryption.
RSA encryption relies on the fact that it’s very difficult to factor a large number. A number with k digits that is the product of two primes will require O(10k) operations to find it’s factors.
The encryption operation is done using a key N, the data to be encoded, plus an auxiliary number e. The decryption operation uses the two factors of N, called p and q, plus the data to be decoded, and an auxiliary number d. The e and d numbers are determined as part of setting up the mechanism, and will discuss below how to do that; they’re not secret information. As far as we know today, there is no way of decrypting information without finding the p and q factors that correspond to the N used for encryption. Since that’s very time-consuming to do, at least for large enough N, it’s considered safe to publish N and e so that people can encrypt messages to you.
We added some functions to JEP that are useful in RSA cryptographic calculations. (See previous exercise for an introduction to JEP; use the directory you created there for access to this exercise’s code) We’ve put the basic parts into Encode.java and Decode.java files in the directory with your Sine.java file. There is also a TestDecode.java that tests both of them in series. These are somewhat complicated to write, because they have to deal with very large numbers. As far as we know they work so long as the key that’s passed is less than 16 decimal digits long (this is a limitation of the 64-bit “double” size that’s passed around internally)
Here’s an example of how they are used: If the key is made from primes p=31543 and q=31547, you could have N=31543*31547 and e=5. Then to encode the message “23” you would do:
JEP > encode(31543*31547, 5, 23)
encode w N=9.95087021E8 e=5.0 M=23.0
6436343.0
(The middle line is just some confirmation output). The result is a cyphertext of 6436343. To decode that, you provide the original p, q and e values along with the ciphertext:
JEP > decode(31543, 31547, 5, 6436343)
decode w N=995087021 d=398009573 C=6436343
23.0
and get back the original message of “23”.
In addition to the “p” and “q” prime numbers that make up part of the key via N=p*q, you have to find two additional numbers “e” and “d”. “e” has to be chosen so that it’s relatively prime to (p-1)*(q-1), i.e. so that ((p-1)*(q-1))%e != 0. If you pick p and q values that have a least-significant digit of 3, 7 or 9 you can always use 5 for e. (And you’ll never pick p or q with least-significant digits of 0, 2, 4, 6 or 8, as those will not be prime numbers)
“d” is harder to find, because it has to be chosen so that (( p-1)*(q-1)) % d == 1. A simple algorithm to do this using brute force is in Decode.java if you’d like to look at it.
Using some small primes for p and q, encode and decode some small messages to check whether you understand how this works. You might want to try doing a calculation by hand to see what we mean about “using large numbers”.
To “break” the RSA encoding by finding the original message from a ciphertext, you take the N value from a public key, and find the two p and q values. In BreakKey.java you’ll find a class that does just that using a brute force approach. TestBreakKey provides some test cases with various size keys.
You can find how long it takes to break a key using:
time java BreakKey 995087021
Make an informal plot of how long it takes to break a key as a function of the key length using the keys from the tests in TestBreakKey.
Can you think of a better way to do this?