Note (12/7): this assignment is worth twice as much as a typical assignment, and you have two "academic weeks" to complete it. The final submission is due 1/10. However, you are required to turn in code for Part 2 through extended precision addition on 12/13. We encourage you to do more if possible, since this isn't quite the halfway point. Also, that way, we'll have a chance to give you feedback on your progress.

We've changed the input/output for ASCII text to (hopefully) make things easier. You can put Part 1 off until after vacation if you like, at which point we'll have more detailed instructions on the checklist.

There was a typo in the "repeated squaring" algorithm for the RSA function. Be sure to use the (now corrected) online version of the assignment when you do Part 3.


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) to produce a serious encryption / decryption tool.

    • Checking Your Work and Hints

  • Some hints on getting started are available here.

  • Check your work continuously as you go along. Test each function thoroghly before continuing on with the next task. 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
    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 two command-line arguments. The first is either the string "-e" or "-d", and the second is the name of the file containing the encryption key. The message should be read from standard input. You should be able to use your program as follows: 
    % a.out -e alice.pub < message.txt
% a.out -d alice.pri < message.encrypted

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

    • Submission and readme
  • Use the following submit command: 
    submit126 10 readme xp.c XP.h rsa.c

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

  • Name, precept number, high level description of code, any problems encountered, and whatever help (if any) your 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 movel 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.

    • 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