CSC 290: Cryptology: RSA-AES Hybrid

Diagram of the AES Algorithm

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

Win Valuable Prizes!

The project judged most impressive overall (above a certain minimal standard of course) will win its author a handsome, hard-bound edition of Bruce Schneir's Practical Cryptography .

Hybrid System

You are going to write a hybrid system that generates a random session key, uses RSA public-key encryption to send the encrypted session key to another user (Bob, of course) , and then uses AES to encrypt a message using the key. You (in your Bob role) will also implement the reverse process of receiving and decrypting the RSA-encrypted session key and using the result to decrypt the resulting symmetric session key to decrypt the message.

You will send your encrypted messages to Bob, and you (as Bob) will receive encrypted messages via a peer-to-peer client-server protocol and decrypt them.

Generating Session Key

Schneier's book Applied Cryptography (on reserve) has some ideas here in section 17.14 (we'll go over them in class). Basically the idea is to use natural and computer-based phenomena (the time, disk access counts, process IDs, etc.) along with user input (keystrokes and their timing, mouse movements and times, etc) to generate a 192-bit random number for use as a session key.

Of course you'll document your algorithm clearly in your writeup. It would be amusing to test how random you keys are: you can do a little research to find appropriate tests (Schneier mentions some I think). At least you could do the "obvious" ones (Nth order statistics, say).

Asymmetric Crypto: RSA

AES can deal with 128, 192, or 256 long (symmetric) keys. We'll use 192. Thus for the RSA portion, the maximum message length needed is 24 bytes. Your n (product of p and q) must therefore be longer than 192 bits (48 hex digits).

Write routines to encrypt and decrypt these long bitstrings (for short messages and signatures, the bitstrings can represent 24 Ascii characters.) That is, Look up the RSA encryption algorithm in the text (hint: p. 162) and implement it.

Since you don't have to write infinite-precision modular arithmetic (see below), you have time to demonstrate your understanding of number-theory algorithms by writing all your own number-theoretical utilities. Don't use a library package or native calls for any of them. In particular, we want to see your versions of fast modular exponentiation, the generalized euclidean algorithm, and (Rabin-Miller) primality testing; Individual test demonstrations that these basic utilities work would be a good thing to see in your writeup (in an appendix presumably) : they could give you confidence during debugging and give the reader confidence you did the work.

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 message (192 bits). 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 long numbers using your keys.

For your public key registration on WebCT, the format should be:

# your_login_name your_n your_e #

...where your_n and your_e are each a single string of decimal digits. The # characters appear in the first and last lines, and lines are delimited as usual by CRLF.

Symmetric Crypto: AES

Here is the state-of-the-art Advanced Encryption Standard (AES) Algorithm in C. You can find AES descriptions on the web of course: there are some nice diagrams at one of the Pictures and Animations links off the Rijndael web site . The animation only works on PC's (pfui!). Main site has lots of links of all types.

One way to use this code is to modify the test program to take a key you provide (say in a file) and a message (ditto) and to spit out the result (ditto).

More elegantly, you can call C from Java, using JNI. In fact your stalwart TA has written this code so we know it's possible (and not hard). Following are pointers to instructions that for putting the AES C-code into a shared library and using it with a Java or C/C++ client/server architecture. There is a simple java class skeleton that can be fleshed out in order to have a bare-bones encryption and decryption implementation.

As it turns out, and unsurprisingly when you think about it, Java has AES support (Thanks Greg!). For 192-bit keys, you'll need to go to Java's main site and download their domestic security upgrade thingie, which is a couple of .jar files that you put in some /security directory. This is another possible route to AES.

Communications

Part of the fun here is the P2P client-server architecture that will let you communicate directly with a partner through sockets. This is a basic part of your CS education, so if it's not familiar it's even more important. Your TA was able to create the client-server application in a couple of days, so again it's possible and not hard. To use the comms software (pointers below), we need a protocol so messages can be parsed. We should all use the same one so the TA can check your work too.

Message Package Protocol:
SKL: length-of-session-key-in-bytes [length: 4 bytes] (for us, SKL = 24 (192 bits))) SK: RSA-encrypted-session-key [length: SKL bytes] ML: length-of-message-in-bytes [length: 4 bytes] M: AES-encrypted-message [length: ML bytes] ST: Signature type [length:4 bytes] (ST = 1, 2 or 3) N: Plaintext Name [length: 24 bytes] (N field exists if ST = 2 or 3) NE: Encrypted Name [length: 24 bytes] (N field exists if ST = 2 or 3) HE: Encrypted Hash [length: 24 bytes (192 bits)] (H field exists if ST = 3)

Signatures are an optional but easy extension. Read more below in "Extras" section. So ST=1 if message unsigned (N and H fields unused and presumably empty). ST=2 if you're only signing your name. ST=3 if you're signing your name and a hashed version of your message.

The simplest way to distribute encrypted messages is through files. You can just mail files to one another, or point each other to files on disk. This could be good for debugging but isn't good for full credit.

Gotcha! Motorola and Intel hardware differ in how they represent numbers in some applications. It's "big-endian" (Motorola) versus "little-endian" (Intel). C and C++ will use the host hardware's byte order unless you use the following conversion instructions explicitly. The "host to network long" (and vice versa) commands convert 4-byte integers for you. If you're in C or C++, use net_length = htonl(length); to generate the lengths to embed in outgoing message packages. Contrariwise, to get the lengths from incoming message packages into usable C or C++ form, use host_length = ntohl(net_length);.

Project Outline

As always, your heroic TA stands ready to assist and your kindly professor stands ready to issue confusing hints and Delphic utterances. In fact, the following prose outline and linked pages are just lightly edited versions of Phil Michalak's tutorial prose with pointers to his tutorial files (Thanks, Phil!). Now, onward!

Write an effective session-key generating program.
Implement and test all the number-theoretic utilities you need for RSA encryption, and implement and test RSA en- and de-cryption (for 192-bit and shorter messages).
Ensure that the aes.h header file and the aes.o C library file has been compiled from the AES.c source.
Incorporate the AES encryption-decryption code into a simple program to verify that it is working correctly. For those using Java, this can easily be done using JNI to access the native C code. For those using C or C++, link with the aes.o library and include the aes.h header file. Here is a special-purpose JNI Tutorial . It points to an example template AES Java Wrapper .
Create your main application: the whole pipeline of key-generation, RSA, AES, and communications for your hybrid systems. The server and client pair winds up being the main application program. Here is a description of the general approach to creating a Client-Server application.
Exchange encrypted messages in both directions with at least two other students. Document everything, especially creative things, in the usual high-quality writeup.

Extras

If you have extra energy, good for you; we got extra points. You can implement signatures and send signed messages. Your recipient has to do about the same amount of work to verify your signatures, so if you can't find another signature-capable student you may have to play Alice and Bob both. For a signature you can just use your private key to encrypt your name if you like -- this is pretty minimal but kind of fun to make sure the two layers of encryption (and decryption) are organized right.

In real systems you sign with a hash of the document along with your name, so this extra involves implementing a hash function (Some source code seems to be out there, but all I see is Windows-based so I didn't pay serious attention). The entire MD5 algorithm (and other hash functions) seem to be in Schneier (on reserve, remember...), in and around Section 18.5. OR if the commercial hash functions are hard to work with or hard to get, just implement something on your own (checksum is simplest, or you might have other cool ideas for hashing) and use that. Remember two of you have to do it so that lowers the bar a bit: you can of course collaborate with your partner(s) on deciding on and producing a hash function.

There may be some issues of registration with your signature, but I doubt it. That is, if your name is less than 24 characters things should still work out OK (as long as your integer is right-justified in the field --- ASCII characters have some leading zeros.) If in doubt you can pad with blanks.

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.

And, there's Even More: Write a cracking program that exploits some weakness in RSA 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.)

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.

Ground rules

Please work on this assignment individually. Use your favorite infinite-precision arithmetic package (Lisp and Java have them, and there are libraries I can give to you if need be: see section below).

Demonstrate that you can successfully create session keys, send and receive them via RSA, and send and receive AES-encrypted messages that use the session key. Demonstrate successful P2P communication through your client-server code.

Demonstrate any extra capabilities you come up with.

Post your public key information on the WebCT discussion group and trade messages with at least two other students.

What to Hand In

Submit to WebCT the usual in the way of code, writeup, documentation of successful communication with other students, etc. Also anything new or cute you did, like clever session key generation. You know the drill by now. We want to be surprised and delighted, is all....

This page is maintained by CB.

Last update: 9.16.04.