The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic... The dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and celebrated.
K.F Gauss (1777 - 1855)
The following numbers are all prime...
31; 331; 3,331; 33,331; 333,331; 3,333,331; and 33,333,331.
However, 333,333,331 = 17 * 19,607,843. Darn...
Things to implement (lots of choices) and associated points for
You'll need an unlimited-precision arithmetic package (see section below).
First as Bob, create some flawed (n,e) pairs of public keys and send them to Alice; in parallel write your RSA encryption and decryption code.
Then, as Alice, send messages to Bob, using each of his public keys at least once. You'll have to tell him which you used, since he's got several corresponding private keys. Also send him some "short plaintext" messsages.
As Bob, acknowledge receipt of Alice's message (unencrypted..just send Alice what you decrypted) so you two can get together and debug your algorithms if they don't do what's expected. If it works, you're both doing it right.
As Eve, you implement the cracking algorithms and "discover" secrets and message contents "independently".
n: choose n between 30 and 40 decimal digits.
m: let your messages be integers less than n, made up of all 1's, all 2's, etc. The idea is that Bob should know when he's successfully decrypted a message.
As Bob, you are going to make some mistakes in constructing your RSA system. You'll leave yourself open to one of the attacks in the book (section 6.2 or 6.21).
m/4 attack on p, q: As Bob, start your search for primes p and q at N*10^18 , for some random N < 100. As Eve, take advantage.
m/4 attack on d: As Bob, "leak" the last m/4 digits of d to yourself (as Eve). As Eve, take advantage.
Low exponent attack: As Bob, choose d as in the theorem on p. 170. As Eve, take advantage.
Short plaintext: chose m < 10^10. As Alice, send such a message to Bob. Bob as Bob can decrypt: as Eve, he will try to read it without using Bob's secrets.
Factoring: see how big an n you can factor: maybe see if you can factor another student's n, but note that n may have to be constructed to have particular structure: use the assumptions and algorithms in section 6.4.
You'll need to deal with massively huge numbers (well, 200-bit ones anyway). So multiple-precision arithmetic packages are needed. Depending on the course, we could write our own (data structures), or learn to use someone else's (more like the real world), or even take advantage of modern language's built-in capabilities.
There is a Gnu MP (multi-precision) software package that is not for the faint of heart. I don't know if it is currently installed on the CSUG Linux system. You can find out more at this link to the Gnu MP 3.1.1 Manual . Ee did have it working at one point in 1995, and successfully used it for this problem.
I wrote a PK system in LISP, since lisp has built-in infinite precision arithmetic. Thus I know this is a possible and pretty elegant approach. The whole thing is 337 commented lines long, but it was for the messy problem of reading text and breaking it up into blocks, etc,. which we don't need here. My code, like yours, includes all necessary number-theoretic functions like Euclid's algorithm, etc. etc.
A pretty common utility is LIP, which I have compiled here. Here is the Lip Documentation . This is C code, and it is supposed to run well under Windows as well as on Linux machines. It is another possibility. If you want to use LIP, let us know and we shall make it available.
It's a bit schizophrenic being both Bob and Eve, but the fun should be in seeing if you can apply these cracking methods as if you were Eve and not Bob. You should write your report to demonstrate clearly what you accomplished as Alice, Bob, and Eve. Let us know who you sent messages to and got messages from, and demonstrate your successful en- and decryptions. Sample output and transcripts are good. Convince us you, as Eve, could in fact credibly attack flawed systems (when you're NOT Bob as well!) Submit to WebCT the usual in the way of code and project writeup. You know the drill by now. We want to be surprised and delighted, is all....
This page is maintained by CB.
Last update: 10.17.06.