COS 126 RSA Cryptosystem Assignment Checklist

Assignment Goals

Learn about cryptography.

Learn about designing algorithms.

Learn about estimating the running time of algorithms.

Combine many of the skills you've developed this semester (client-interface-implementation, recursion, structs, arrays, strings, analysis of algorithms, theory of hard problems) to produce a sophisticated encryption tool.

Checking Your Work and Hints

Some hints on getting started are available here.

The directory ftp.cs.princeton.edu/pub/cs126/rsa contains a number of key files that you can use to test out your program.

You may compare your results to our reference solutions by running the program rsa40, rsa80, and rsa160 for 40, 80, and 160 decimal digit cryptography. The programs rsa40-base256, rsa80-base256, and rsa160-base256 are identical except that they are faster because they use base 256 in the underlying data structure.

Here is the beginning of a sample debugging client. Modify as needed.

Check your work continuously as you go along. Test each function thoroughly before continuing on with the next task or you will regret it. Be sure to test your function with extreme cases (near 0 or near the overflow tolerance). It is a good idea to check the input to each function, and make sure, for example, that you don't attempt to multiply two 2N-digit integers since this would overflow the data type.

Maple is a useful tool to check your arithmetic (or calculus and linear algebra assignments). It is already installed on arizona. To run, type maple. Now type arithmetic expressions, followed by a semicolon.

> 2003 ^ 7;
                                                129350063142700422208187

> 2003 &^ 7 mod 3713;
                                                          746

> iquo(108, 5);
                                                          21

The ampersand tells Maple to do exponentiation by repeated squaring, instead of using the naive method. It is crucial if the exponent is large.

If you don't have Maple on your system, you can run the Unix tool bc instead. Type "man bc;" for help.

The program should take one command-line argument - the name of the file containing the encryption key. The message should be read from standard input. You may assume that the message is smaller than the modulus of the encryption key. You should be able to use your program as follows:

% a.out bob.pub < message.txt > message.encrypted
% a.out bob.pri < message.encrypted

The following command should return the original message:

% a.out bob.pub < message.txt | a.out bob.pri

Note: you only need to handle nonnegative integers.

When you use your program with a particular public/private key, be sure to modify the constant N that represents the maximum number of digits that your extended precision data type can handle. You should also modify N and recompile when testing the complexity of your various arithmetic functions.

You may need to increase the stack size (space available for local variables and function parameters) to run your program on large values of N. Alternatively, you can reduce the amount of stack space that your program uses by unrecursifying XPmod() and XPrsa(), or by using pointers to avoid excessive copying of integers.

For Windows and lcc, compile with

lcc126 rsa.c xp.c -stack-commit 100000

and adjust the last number as needed, e.g., by adding 0's.

For Unix or OS X, the command unlimit will turn off any previously imposed limit on the stack size.

Submission and readme

Submit the following files via the course submission system:

readme.txt         (both submit)
xp.c, rsa.c, XP.h  (1 partner submits all three files)

Do not use different file names. Be sure to submit XP.h, and set the number of decimal digits to 40. You will lose significant points if your source files includes xp.h instead of XP.h.

The readme.txt file should contain the following information. Here is a template readme file.

Name, precept number, name of partner, precept number of partner, high level description of code, any problems encountered, and whatever help (if any) you received.

State the asymptotic running times (as a function of the number of digits N) for the following routines: addition, multiplication, division, RSA encryption, and RSA decryption. Justify your answer with empirical and analytic support.

Enrichment Links

Here the RSA Security home page. As of September 2000, the US patent for the RSA cryptosystem was released into the public domain.

Here are demos for grade school addition and subtraction. Enjoy!

Instead of implementing our recursive division algorithm, feel free to implement grade school long division.

There are many novel algorithms to perform fast multiplication on large integers. The following link describes Karatsuba and FFT based multiplication. Speeding up division requires a bit more work.

There are a number of professional tools that provide strong encryption and digital signatures for email. PGP (Pretty Good Privacy) is a freeware product that uses the RSA cryptosystem (along with a few other strategies). It is available for many platforms, and is already installed on arizona - use the Unix command pgp. Microsoft Outlook users can achieve a similar effect (for an annual fee): choose the menu option Tools -> Options -> Security.

Here's a song about Ed Felten and the SDMI (Secure Digital Music Initiative).

Extra credit

There are three main challenges. First you need to find large "random" primes. This is the hardest step. Second, you need to choose an integer e that is relatively prime with φ. Finally, you need to find an integer d such that ed = 1 mod φ.

Step 1. There are efficient randomized algorithms that test whether a given integer is prime. (Surprisingly, the factoring problem appears much harder.) The most famous of these tests is the Miller-Rabin test. It's extremely unlikely that you'd come up such an algorithm on your own, so do a Web search and you'll find lots of information.

Step 2. This is equivalent to checking whether gcd(e, φ) = 1. Use Euclid's gcd algorithm.

Step 3. Redesign Euclid's gcd algorithm so that if it determines gcd(e, φ) = 1, it also finds the inverse d. This will require some careful thought.

Kevin Wayne