Lab7: RSA Cracking
Motivation
In this lab you will learn about the PKE systems, specifically the RSA encryption algorithm, as well as key length selection.
Public Key Encryption (PKE) Systems
So what is a PKE system? PKE is based on a certain type of mathematical algorithm that provides one-way encryption/decryption. That is, a public key algorithm allows you to encrypt a message with a special key that has some very special properties.
· Encrypted messages can only be unencrypted with a single private key (distinct from the public key).
· It would be beyond the realm of probability to break the secret key through possession of the public key, the encryption algorithm, and the encoded message.
You distribute your public key to anyone who wants it with full confidence that messages sent to you that have been encrypted with your public key will only be readable to you. Any sender can encrypt their message with your public key and that message will only be able to be unencrypted with your private key.
RSA
In 1977 Ronald Rivest, Adi Shamir and Leonard Adleman came up with the now famous RSA encryption algorithm (based on the work of mathematical greats like Euler and Fermat). This algorithm is one of the cornerstones of public key encryption (PKE). In fact, this algorithm is so important that recently (2002) the authors were awarded the highest honor one can receive in the field of Computer Science: the Turing Award. I would encourage you (on your own time – not officially part of the lab) to go to http://www.acm.org/awards/turing_citations/rivest-shamir-adleman.html and watch their acceptance speeches. They are only about 15 minutes in length each and give you some sense of the history of computing.
RSA Math Theory Overview
The underlying principle of RSA is that a one-way computation is performed. That is, something that is easy to do in one direction, but impossible (or very, very difficult) to reverse without the proper key. The computation used is the multiplication of prime numbers. For example, take the two prime numbers P=13 and Q=23. PQ=13*23=299. This is a simple calculation to perform. A computer can do it with ease and a human could even do it with nothing more than paper and pencil. However, the reverse operation of finding the P and Q given only PQ is very difficult, even for a computer. This is called finding a prime factorization of PQ. Try it: given a PQ of 203 what were the P and Q? Give up? How about P=7 and Q=29. How did I know this – because I picked P and Q in the first place and cheated! OK, so a human has a hard time finding P and Q from PQ. But a computer can do it easily, right? Well, a computer can do it but it takes a lot of time. And the time it takes is proportional to the length (in bits) of PQ. So a computer could crack the example given above because P and Q are small numbers. But if PQ was picked so that it contained 1024 bits or more (e.g. a 1024bit number can have a range of [0..2^1024) or up to 309 decimal digits!), it would take a computer longer than the estimated age of the universe to crack the code. This is one of the things we will be examining later in the lab.
In addition to finding primes P and Q, as well as PQ, the RSA algorithm also has 2 other values it needs to compute: E and D. Our public key will be the pair (E, PQ) and the private key will be the pair (D, PQ). P and Q are used to generate all 3 of these numbers, but are then thrown away after PQ, E and D are found. E and PQ are public and anyone can use them to encrypt a message. D is private and is used along with PQ to decrypt a message encrypted with E and PQ. So you never want to give out D. And the only way the code can be cracked is if someone can recreate the factors P and Q from their product, PQ. The details of computing E and D are given in the comments in the included jar file.
RSA Implementation
You are given two implementations of the RSA algorithm in the rsa jar file (RSA and BigIntegerRSA). Both are simply prototypes of the algorithm in a single main method. The RSA version is a version coded with primitives (longs) and is limited in the key bit length it can produce (because the resulting cipher must fit back into a long). This version also has to perform all of the computations by hand. But this version does have more informative comments. The BigInteger version contains an implementation of this same code, but written using BigIntegers instead of longs. Thus, it can handle much larger key bit lengths. In addition, it provides many methods that help you automatically compute some of the functions required for RSA. Look through these pieces of code and run them a few times until you understand what they are doing.
RSA Cracker
Your job for this lab is to write an RSA cracker program. That is, given a public key (PQ, E) you need to find the corresponding private key, (PQ, D). Note that the PQ is the same for both keys, so your job comes down to simply finding D. However, you can’t just directly find D from PQ and E. Instead you first need to factor PQ into the two primes P and Q that originally formed it. There is no fast way to do this – part of what makes encryption work so well – but there are ways to do this that are faster than others. Try to come up with a technique that is not too inefficient. Once you have found the proper P and Q you can use them to derive the value of D. Then when D is combined with PQ, you can form the private key that goes with the public key. With the private key you can decrypt any message encrypted with that public key. Note that when you are doing this I want to make your code work with BigIntegers. Not only will this allow you to attempt to crack keys with larger bit lengths, but it also gets you working with BigIntegers.
To prove that your cracker works, I'm providing an encrypted message for you to attempt to crack -- one that employs a 40 bit key (i.e. PQ is 40 bits long). Here is the public key:
PQ: 587920946759
E: 7
And the encrypted message (as an array of BigInteger values):
112987317794
486806796327
211922900563
34359738368
174657704360
253114772130
261720111807
419919002336
211922900563
360476756129
261720111807
Note that you will probably want to rewrite the BigInteger version of the given RSA code slightly so that is broken into methods that can produce keys and methods that can encrypt (taking the public key info and message – array of BigIntegers) and decrypt (taking the private key info and message). That way, you can simply reuse that code to do the decrypting of the hard-coded message above after you have cracked the key.
Timing the Cracker
Your last job is to time your cracker. You do not want to time the encryption/decryption of actual messages, but just the part that goes from (PQ, E) to the discovery of D. Specifically, you are to produce a graph of how long it takes to crack various bit length keys. Start with a key length of 14 and work your way upward. You should stop when it takes more than a min or two to run the crack. Use the BigIntegerRSA code to produce the original values to be cracked. As suggested above, if you rewrite that code slightly you can easily have a method that produces keys with given key lengths. If you completed the above step then your cracker should be working already, but you can always make sure my checking that you get back the proper P, Q and D values from (PQ, E).
Remember that you can get the current time in milliseconds (from 1970) with the System.currentTimeInMillis() method – just do this twice and subtract to get the execution time. Then you should record the key length and the time it took to execute so you can plot these values on a graph. But instead of simply printing out the times and cut-and-pasting them to Excel, you should instead have your program automatically produce a file of data that Excel can read. You are going to want a file of tab-separated data points with an extension of .xls. This of course means you will need to run all your tests in a loop so they can easily be placed into the same file.
Once you open the data up in Excel you need to create a chart. A Scatter Chart is often the best choice for this type of data. When it plots it will only show the collected data points so you will want to add a trend-line that connects the points together (right-click on the grid points to add a trend-line). Note that Excel is picky about its exponential fitting algorithm. If your data has zeros and perhaps other duplicate values it won't offer you exponential as a choice. If this happens, then the problem is most likely your data at the start of your run. So simply make the chart without this starting data so you can fit an exponential curve to the remaining data. Once you have the trend-line you can estimate how long it would take to crack a key of any length (the forecast option of trend-lines). I want you to give me an estimate for how line it would take to crack a 1024 bit key. I want this estimate in both milliseconds and in centuries.
Keep in mind that what you are really plotting is the relative time it takes to do each crack – that is, as my bit length goes up, my cracking time goes up by some percentage. Because of this, you must run all your timing tests on the same computer system. They will be meaningless if you run half of them in the lab and half on your laptop. It doesn’t matter what machine they are run on, it just needs to be the same machine for all the tests.
Demo
You will be expected to show/demo your code next week. Also tell me the cracked message and show me your graph of timing information including your estimate of cracking a 1024 bit key.