Note: this assignment is worth twice as much as a typical assignment, and you have two "academic weeks" to complete it. You are encouraged to work with a partner on this assignment. Your partner need not have the same preceptor. You and your partner will submit one program and you will receive the same grade. However, EACH of you must submit a readme file. The warmup section is due 5/1 and is worth 10 points. The final submission is due 5/10 and is worth 30 points.


Warmup Requirements

The following functions should be implemented in XP.c:

The following functions are optional for the warmup (they will not be graded):


Checking Your Work and Hints

  • Some hints on getting started are available here.

  • The directory ftp.cs.princeton.edu/pub/cs126/rsa-warmup contains files that will be useful for the warmup portion of this assignment.

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

  • Note: you only need to handle nonnegative integers.

  • 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 as assignment 9 via courseinfo.cs.princeton.edu: 
    readme.txt (both submit)
     
xp.c (1 partner submits)
     
XP.h (1 partner submits)
    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 include xp.h instead of XP.h.

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

  • Name, precept number, partner's name and precept number.

    • 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 algorithm 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).


    • Kevin Wayne