CSC 290: Cryptology: Breaking RSA

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...

Request

This is the first draft of this assignment; it's in alpha-testing if you like, so please get in touch if it's unclear, wrong, unreasonable, etc.
Thanks -- CB

The Idea

You get to play three parts: As Bob, you will create and share some public keys, only you will make simple mistakes outlined in T&W 6.2. As Alice, you will use all Bob's public keys and send him encrypted messages; you too may make some simple mistakes. As Bob, you will receive messages and decrypt them. As Eve, you will receive the same messages Bob receives, but pretend you don't know Bob's secret p,q, or d numbers; Your goal is to use RSA cracking techniques to discover the message and if possible Bob's secret numbers. Thus the idea here is to implement the RSA algorithm and several methods for cracking it, assuming some elementary mistakes have been made. All you need to know is in Trappe and Washington 6.1 -- 6.4. Assume you're Alice and each of you pick another student (or more than one) who will be your Bob-Eve.

Coding

Things to implement (lots of choices) and associated points for demonstrated functionality.

Pseudo-prime finder(s): Fermat: 3 points; Miller- Rabin: 6 points; Solovay-Strassen, 9 points.

RSA algorithm (3 points)

Factoring: 3 (mod 4) square root attack (p. 88): 5 points; Fermat: 3 points; p-1: 6 points; Quadratic Seive: 9 points.

RSA Attack(s): m/4 digits method (p. 169) 5 points: Low-exponent: 5 points; Short plaintext: 5 points. Timing (10 points). In your researches (next section) you may find other attacks too. Please feel free to substitute other attacks for any listed here: be sure to explain how they work and relate their complexity and effort to the ones suggested so we can assign credit fairly.

Modular exponentiation, Exended Euler algorithm, Jacobi symbol evaluation, continued fraction evaluation, whatever other utilities are necessary. (3 points each).

You'll need an unlimited-precision arithmetic package (see section below).

How to Proceed

You will probably want to do some library research. For example, the first two attacks mentioned in section 6.2 reference Boneh, Boneh et al., and Coppersmith. I recommend the Web of Science database (available off the main Library webpage,) which often leads to full-text downloadable copies of papers. Carlson might have some of these journals on the shelves. Diane Cass, the CS reference librarian in Carlson, is a fine resource. Interlibrary loans has a friendly web interface and they can often get books or even faxes of individual articles really quick. Then there's Google (titles, authors), Google Scholar, etc.

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".

All Attacks but Timing

Do as many attacks as you want!

Parameters:
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.

Timing Attack

Here I'd just like to see if this can be made to work, so you can be Alice, Bob, and Eve all three. See if you can make the scheme in section 6.2.3 work. Issues are how to do the timing (depends on your application and/or your OS: matlab has a timer but I don't know if it's adequate.) Then there's an issue of how many messages you need to time to get good statistics. Given the data, the algorithm seems pretty straightforward.

Multi-precision Packages

Everybody uses Java library routines nowadays so the following is a bit dated.

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.

What to Hand In

Please work on this assignment individually.

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.