COS 126

RSA Public-Key Cryptosystem Warmup 		Programming Assignment 9

Due: Wednesday, 11:59pm

Overview.  Write a program to implement the RSA public-key cryptosystem. The RSA (Rivest-Shamir-Adleman) cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and the Windows operating system. It works by manipulating large integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate large integers (hundreds of digits). The built-in C type int is only capable of dealing with 16 or 32 bit integers, providing little or no security. You will design, implement, and analyze an extended precision arithmetic data type that is capable of manipulating much larger integers. You will use this data type to write a client program that encrypts and decrypts messages using RSA.

Note: the training wheels are off on this assignment - you're starting with a blank screen, not our code. This means that you must pay particular attention to the process of building up your program from scratch. Consider carefully how your program should be structured and how you are going to implement the various functions before plunging in. Remember to thoroughly test and debug each function as you write it.

The RSA cryptosystem.  As discussed in Lecture S1, the RSA public key cryptosystem involves three integers d, e, and n that satisfy certain mathematical properties. The private key (d, n) is known only by Bob, while the public key (e, n) is published on the Internet. If Alice wants to send Bob a message (e.g., her credit card number) she encodes her message as an integer M that is between 0 and n-1. Then she computes:

E(M) = Me mod n
and sends the integer E(M) to Bob. As an example, if M = 2003, e = 7, d = 2563, n = 3713, then Alice computes
E(M) = 20037 mod 3713 = 129,350,063,142,700,422,208,187 mod 3713 = 746.
When Bob receives the encrypted communication E(M), he decrypts it by computing:
M = E(M)d mod n.
Continuing with the example above, Bob recovers the original message by computing:
M = 7462563 mod 3713 = 2003.
To check your arithmetic, you may use bc, maple, or xmaple.

Part 1 (extended precision arithmetic).  The RSA cryptosystem is easily broken if the private key d or the modulus n are too small (e.g., 32 bit integers). The built-in C types int and long int can typically handle only 16 or 32 bit integers. Your main challenge is to design, implement, and analyze an extended precision arithmetic data type that can manipulate large (nonnegative) integers. To make it easier to check your work, we recommend working with integers represented using familiar decimal (base 10) notation. (We note that you could achieve superior performance by using a base that is a power of 2, e.g., 256 or 32,768.) Your data type will support the following operations: addition, subtraction, multiplication, division, modular exponentiation, and comparison. You may use the header file XP.h.

  • Data structure. The first and most critical step is to choose an appropriate data structure to represent N-digit extended precision integers. A natural approach is to store each digit as an element in an array. To avoid pointers and memory allocation and deallocation headaches, consider packaging the array up in a struct as follows: 
    #define N  100         // maximum number of digits supported
#define NN (2*N + 1)   // number of digits allocated

typedef struct {
   unsigned char digit[NN];
} XP;
    We declare our array to have slightly more than N elements to give ourselves a bit of extra scratch space to store intermediate results - the exact reason for using 2N + 1 will become clear later. Advanced students (who like pointers) may wish to make it a true first class ADT as in Sedgewick, p. 181.

  • Initialization. Implement a function XPinitDecimal() that takes a string of decimal digits as input, and returns the extended precision integer corresponding to this string. If you represent integers using decimal notation, this will be straightforward; if you use base 2 or 256, consider using Horner's method to do the conversion.

  • Display. Implement a function XPshowDecimal() that takes an extended precision integer as input and prints out a (decimal) representation of that integer.

  • Addition. Implement the function XPadd(). It should take two extended precision integers as input and return a third extended precision integer that is the sum of the two. Implement the method you learned in grade school. Observe that if a and b are 2N-digit integers, the sum will have at most 2N + 1 digits.

    Once you've written the above three function, you should be able to write code like: 

    XP a, b, c;                       // declare extended precision variables
a = XPinitDecimal("123456789");   // a   = 123456789
b = XPinitDecimal("54545454");    // b   =  54545454
c = XPadd(a, b);                  // c   =  a + b
XPshowDecimal(c);                 // print 178002243

  • Random number generation. Implement a function XPrand() that takes as input an integer n and returns a pseudo-random n-digit extended precision integer by choosing each digit at random. This will be useful in debugging the subsequent code, and also in analyzing its complexity.

  • Parity. Implement the function XPisOdd() that takes an extended precision integer as input and return 1 if and only if it is odd. You may assume that the base is even, so that this amount to checking the parity of the least significant bit.

  • Comparisons. Implement the following functions: XPgreater(), XPless(), and XPeq(). They should take two (2N+1)-digit extended precision integers as input and return 1 if and only if the first integer is greater than (less than, equal to) the second.

  • Subtraction. Implement the functions XPsub(). It should take two (2N+1)-digit extended precision integers as input and return a third extended precision integer that is the difference of the two. You should check that the first integer is greater than or equal to the second before subtracting; otherwise output an error message.

  • Multiplication. (NOT required for the warmup) Implement the function XPmul(). It should take two extended precision integers as input and return a third extended precision integer that is the product of the two. Observe that if a and b are N-digit integers, the product will have at most 2N digits.

  • Division. (NOT required for the warmup) Integer division is the most complicated of the arithmetic functions. Here is one of the simplest algorithms to compute q = a / b and r = a mod b, where a and b are extended precision integers, with b not equal to 0. This algorithm requires the least amount of code, but its correctness may not be immediately apparent. 
    div(a, b) {
    if (a < b)
        return (0, a)
    (q, r) = div(a, 2b)
    q = 2q
    if (r < b)
        return (q, r)
    else
        return (q + 1, r - b)
}
    Note that you should use extended precision arithmetic to perform each of the intermediate computations. The natural way to implement this algorithm is using recursion. Observe that if a and b are 2N-digit numbers, then the intermediate results will never have more than 2N+1 digits.

    • Part 2 (encryption and decryption).  This part is not required for the warmup. Please see the full description of the assignment for details on Part 2.

    Part 3 (analysis).  This part is not required for the warmup. Please see the full description of the assignment for details on Part 3.


    This assignment was created by Bob Sedgewick and Kevin Wayne.
    Copyright © 2000 Robert Sedgewick