CSC 290: Cryptology 2001: RSA and ShAkespeaRe

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

Groundrules

Please work on this assignment individually. Please write all your own numerical utilties, such as modular exponentiation, generalized euclidean algorithm, primality testing, digital signature, whatever. There should be no external libraries necessary nor used for this assignment. Hand in the usual in the way of code, writeup, documentation of successful communication with other students, etc. Hand in hardcopy and send the writeup to webCT as well.

This assignment is Due ???.

Hybrid Simplicity

Traditionally, a class assignment for RSA encryption involves lots of messing around with converting blocks of ASCII text to binary numbers of a certain size, encoding the blocks, and then to decode there is the reverse exercise of turning numbers to ASCII again. Also, traditionally one uses a built-in or imported library to handle and perform mathematical operations on integers of enormous size (hundreds of digits, say).

I'd like to concentrate on the numerical meat of the problem instead of the text-munging fiddly details, which simplifies matters and will also make it easier to be platform independent I think. Also, although it would be good for you to make you use special functions for dealing with huge integers, that isn't really necessary either.

The idea is that we shall encode and decode small integers. Thus our encryption input and output actually will be numbers. In fact they are an ordered code . Here is the codebook . Here are some examples of what you can write with this vocabulary.

It would be just as easy to produce an unordered code, and just as easy to en- and decode, using PERL (or Java) random number functions and built-in hashtables, but again I'm striving for simplicity and portability here.

I'm thinking we can extend the codebook with codes for names so we can do signatures...remind me to do this.

A consequence of having small numbers as inputs means we can use small numbers (32 bits) for our numerical operations, obviating any need for special libraries or language features.

What to Do

Write encoding and decoding routines to take text to numbers and vice versa. You can try to pick your text from the codebook or just take your chances and substitute something cute when your encoder doesn't find the word it needs in the codebook. For example, here is a charming little quatrain:

shall i compare thee to a summers day
thou art more lovely and more temperate
a womans nature is blunt and rough
despite her beemer which is sweet enough

Which encodes to (actually my encoder loses the carriage returns):
2382 1359 488 2723 2801 1 2635 612
2759 143 1730 1614 107 1730 2700
1 3142 1769 1435 307 107 2270
697 1294 2900 3081 1435 2663 861

You can already spot a weakness with ordered codes,no? Anyway, this then decodes to (again my decoder loses the CRs...):
shall i compare thee to a summers day thou art more lovely and more temperate a womans nature is blunt and rough despite her unknown which is sweet enough

Now our code groups are integers less than 3300, so there is no reason to get involved with multiple-precision arithmetic (this takes a bit of the fun out of the exercise, but you can just use LIP or Java function calls or some other package (see below) if you want to generalize your code.

Look up the RSA encryption algorithm in the text (hint: p. 162) and implement it. First you should write a generator for your public and private keys. To do this you should specify some maximum size for n = pq , the product of your two primes (each congruent to 3 modulo 4), and for d, one of your exponents. n must be larger than the biggest code, or say 3400, and to keep your arithmetic within single-precision limits should be smaller than 15 bits, or 32768 in decimal. d and n will determine e, the multiplicative inverse of d (mod phi(n) ).

Test your en- and de-cryption by en- and de-crypting a message using your keys.

Register your public key (n,e) in some public place to be announced, probably a WebCT discussion topic or at worst a web page the prof will maintain. The format should be:

#
your_login_name
your_n
your_e
#

Where each line is a single string of decimal digits.

Using information in this public key repository, encrypt messages to several (say three) classmates. The best way to distribute encrypted messages is through simple text files. You can just mail text to one another.

When you get messages, decrypt them. Keep copies of the messages sent to you and your decryptions and include them in your report.

Now implement signatures. Send some signed messages. We'll need to put your names into the code book, so remind the prof about that and he'll do it. You'll need to stick your (encrypted) signature on the end of your message. Demonstrate that you can correctly decrypt your correspondent's signature and that he has correctly decrypted yours -- document some message exchanges in each of your final reports.

Now for the fun. Write a cracking program that exploits some weakness in key choice. With ns this small I expect it should be easy to read someone else's mail. You are Mallory and Alice. As Alice, encode a message to Bob using his public key. As Mallory, try then to decrypt it, using any weakness you like. You may even choose to be Carl, someone who makes a sub-optimal choice of keys, breaks some rule or other, has a weakness in short, and show how Mallory can break Carl's encryption. For instance, if p and q are too close to one another, this is a weakness. As Mallory you get to pick the weakness and as Carl you implement it. The basic thing to do is factor n. To do this you should implement one of the factoring algorithms (trial division is dumbest, you'd get lots of Brownie Pointes for implementing quadratic sieve (handout). Mollin (on reserve) has three doable algorithms in chapter 5 plus a treatment of the number field sieve, currently the top contender.)

FYI: Multiprecision Packages

Obviously to do real (unbreakable) encryption you need massively huge numbers (hundreds of bits), 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 (multiprecision) software package that is not for the faint of heart. As of now it is not installed on our Solaris system, I believe. You can find out more at this link to the Gnu MP 3.1.1 Manual . It scares me, though we did have it working at one point in 1995, and 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, include 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 these Solaris machines. It is another possibility. If you want to use LIP, let me know and I'll make it available.

Last, Java of course has a multiprecision library.

Other Code

Of course there is a ton of PK and RSA code out there. It would be total overkill for this project, of course. There is cryptological source code written by other students at other universities in various languages out on the net. In fact I have imported a lot of it, and if you want to take a look it is in this source code directory . In "real life", that is, to get solutions for big problems, it is often useful to get code from elsewhere, and in fact you'd be crazy not to try it. HOWEVER these are not big problems, the fun and pedagogical point here is in developing the algorithms, not using them for research or to make a profit. Thus I expect you to write your own code. It's a lot more fun than trying to understand someone else's, and you learn more. Furthermore, plagiarism is lame, pitiful, shameful, dishonest, easy to detect, and bad for your academic record. However if you want to incorporate or build on some foreign source code, talk to me about it first and we'll see what makes sense. These algorithms are so trivial that it's hard to see what would be worth building on, but I could be convinced.

---

This page is maintained by CB.

Last update: 29.07.01.