COS 126 RSA Cryptosystem Assignment Hints


Part 0:   preparation  

  • Review the lecture notes on the RSA cryptosystem.

  • Copy the files from the rsa-warmup and the rsa directories.

  • Think about how you plan to break up the various pieces of the assignment. Use the client-interface-implementation paradigm as in the rational arithmetic assignment. The interface XP.h includes prototypes for all of the standard extended precision arithmetic functions: add, multiply, divide, mod, parity, and comparisons. The implementation contains code to implement all of these operations. The client program reads in the cryptographic key from a file and applies the RSA function to it.

    • Extended precision arithmetic data type

    First, make sure you understand the data structure XP that will be used to store extended precision integers. 

    #define N  40
#define NN (2*N + 1)

typedef struct {
   unsigned char digit[NN];
} XP;

  • The array digit[] stores the decimal digits. The least significant digit is stored in index 0. So the integer 789 would be represented by digit[0] = 9, digit[1] = 8, digit[2] = 7, and all the other array entries are 0.

  • Why is the type char and not int? Each digit is a number between 0 and 9. An unsigned char can store an integer between 0 and 255, so this provides sufficient storage. There is no need to waste space with an int. Note that you are still storing the integers 0 through 9, not the characters '0' through '9'.

  • Why don't I just represent an extended precision integer with an array, rather than an array wrapped up inside a struct? This means that when you pass a variable of type XP to a function, it will create a copy of the integer (unlike with arrays that would just pass a pointer to the first item). This makes memory management much easier - you'll never have to use malloc() or free(). The downside is that things will take a bit longer (but only by a small percentage). For novices, this tradeoff is well worth it.

  • Why NN = 2N + 1 instead of N?
    • If you follow our suggestions, then pay careful attention to the input requirements for each function described in XP.h. Some assume that the inputs handle integers of up to N digits, while others require up to 2N or 2N+1. The most common mistake is ignoring these details.


    XPinitDecimal()

    Write a function 

    XP XPinitDecimal(char s[]);
    so that you can initialize an extended precision integer with the following syntax. 
    XP a;
a = XPinitDecimal("123456789");
    Basically you just want to copy the string s[] into the digit[] field of a variable of type XP. But there are a number of design issues that will significantly affect the rest of your code (and life for the week).

  • Do convert the integers '0' through '9' to the integers 0 through 9 (or prepare to pay an enormous price in debugging later on). Here's a useful snippet of code: 
    unsigned char c, d;
c = '8';             // c is the integer 56 (ASCII for the character '8')
d = c - '0';         // d is now the integer 8 ('8' - '0' = 56 - 48 = 8)

  • We recommend filling the remaining array elements with the value 0 (instead of storing some arbitrary character like 'x'). This will greatly simplify your code, since now you can treat all digits in a uniform manner.

  • We suggest copying the string in reverse order, so that a.digit[0] is the least significant digit.

  • Check that the input consists solely of digits, and has at most N of them. A small investment in safety checks like this can save huge amounts of time in tracing down future bugs.


    • XPshowDecimal()

    Write a function 

    void XPshowDecimal(XP a);
    that prints out the decimal representation of a by looping through the NN digits of a.digit[] and printing them out in the appropriate order. Test out your function with the following code: 
    XP a;
a = XPinitDecimal("123456789");
XPshowDecimal(a);
    It should print out: 
    123456789
    For debugging purposes, leave in the leading 0s (and leave them in until you have finished implementing and debugging all of the other interface functions). If N = 10, and NN = 21, print out 
    000000000000123456789

    XPadd()

    Write a function 

    XP XPadd(XP a, XP b);
    that computes a + b and return the sum. Add two integers using pencil and paper, and observe that at each step you compute a new output digit and a carry digit. You can test your function with the following code: 
    XP a, b;
a = XPinitDecimal("123456789");
b = XPinitDecimal("54545454");
c = XPadd(a, b);
XPshowDecimal(c);

  • Be sure that your function can handle inputs with as many as 2N digits. N is not sufficient.

  • We recommend that you check that both inputs are 2N digits or less. Consider writing a helper function digits() that computes the number of significant digits.


    • Comparisons

    Devise an algorithm for determining whether one integer is greater (less, equal) to another. Instead of writing 3 separate functions (that have almost the exact same code), consider writing a helper function 

    int compare(XP a, XP b);
    that returns 1 if a > b; -1 if a < b; and 0 if they are equal. If you do this, you can quickly crank out code for XPless() as follows: 
    int XPless(XP a, XP b) { return compare(a, b) == - 1; }

    Your functions should correctly handle inputs with up to 2N+1 digits.


    Parity

    Hint: this requires only one line of code.


    Subtraction

    This should be fairly similar to addition.

  • You do not need to handle negative integers. The subtract function need only subtract correctly when the first integer is greater than or equal to the second.

  • Your function should handle inputs with up to 2N+1 digits.

  • We strongly recommend checking that the first integer is indeed greater than or equal to the second (using your comparison functions). This can help you in tracing down future bugs.




    • You can stop here for the warmup. But if you feel like you're on a roll, then keep going with multiplication and division.




    Multiplication

    Your multiply function need only work if the two inputs are N digits or less. This will ensure that the result will not overflow. It would be a good debugging idea to check this condition at the beginning of the function.

    Bonus hint: you might find an extremely relevant question in the Fall 2000 final exam.


    Division

    This is the hardest of the arithmetic functions.

  • We suggest writing a helper function division() that computes the quotient and remainder of two extended precision integers. Then, have the interface functions XPmod() and XPdiv() call division() and return the remainder and quotient, respectively.

  • One obstacle is that you want the function division() to return both the quotient and remainder when you divide a into b. Since C functions are only allowed to return one value, consider defining a new struct that contains two extended precision integers 
    typedef struct {
   XP quotient;
   XP remainder;
} DivisionType;

  • If you're algorithm is excessively slow (proportional to N3), try to figure out why. Consult a preceptor if you get stuck.

  • Note: it is important that you compute 2b via addition instead of multiplication. Otherwise, you might pass an integer with too many digits to XPmul(). Moreover, your XPadd() function is much faster than XPmul().

    • RSA function

  • Don't be surprised if you code runs slow. After you perform the complexity analysis, you'll understand why. This is a valuable lesson in analysis of algorithms. Professional implementations of RSA need to use more sophisticated algorithms (with significantly lower asymptotic running times) for multiplication and division so that they can encrypt/decrypt in real-time, even for keys with thousands of digits.

  • The assignment specifies an efficient algorithm. Note that it is recursive, so be sure to insert an appropriate base case.


    • rsa.c

    Now, use your extended precision data type to write a client program to encrypt and decrypt messages using RSA. Be sure that you have debugged and tested all of the interface functions before proceeding.

  • The program rsa.c should take one command-line argument (using argv and argc) - the name of the file containing the encryption/decryption key. 
    int main(int argc, char *argv[])

  • Your program will read in the exponent and modulus from the given key file (in that order). To do this, read in each decimal integer into a string via the %s formatting option of fscanf(). As an example 
    FILE *filename;                     // file pointer
char string[N+1];                   // allow enough room for '\0'
. . .
filename = fopen(argv[1], "r");     // open the file named in argv[1] for reading
fscanf(filename, "%s", string);     // read in a string from the file
. . .
fclose(filename);                   // close the file when finished reading
    Then, pass the string to XPinitDecimal() to initialize an appropriate variable of type XP. Be sure to test your program by printing out these variables using XPshowDecimal().

  • If you use fgets(), please note that it inserts the trailing '\n' into the string. Also, the order of the filename and string are swapped.

  • To encrypt/decrypt, you should read in the message from standard input. Read it in as a decimal string using scanf() as above. Apply the RSA function and print out the result to standard output.


    • Kevin Wayne