COS 126 RSA Cryptosystem Assignment Hints

Part 0: preparation

Review the lecture notes on the RSA cryptosystem.

Copy the files from /u/cs126/files/rsa to an empty directory.

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 uses this data type and implements the RSA function.

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 {
   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?

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.

You'll make your life alot easier if you convert the integers '0' through '9' to the integers 0 through 9. Here's a useful snippet of code:

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). This will greatly simplify your code, since now you can treat all digits in the same manner.

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

It's probably wise to check that the input consists solely of digits, and has at most N of them.

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, it would be a good idea to leave in the leading 0's. 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);

If you feel like you're on a roll now, you may wish to write code for subtraction and multiplication, as they're quite similar in style.

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; }

Parity

Hint: this requires only one line of code.

Subtraction

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. It would be a good debugging idea to check this condition (using your comparison functions) at the beginning of the function.

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.

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 fucntions 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 N³), try to figure out why. Consult a preceptor if you get stuck.

RSA function

Don't be surprized 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.

XPinitASCII()

Given a small piece of text, you're job is to convert it into a decimal integer.

The most direct way is to use the ASCII encoding. Each character is stored as an integer between 0 and 127. For example, the character 'h' is 104, 'e' is 101, 'l' is 108, 'o' is 111, and '!' is 33. Thus, we can represent the text "hello" as the extended precision integer 104101108108111033. Note that we use 3 decimal digits for each character. This will make it easy to invert the process later.

To carry out this direct solution, examine each character c in the text one at a time. For each character, extract each digit one at a time. For example, c % 10 is the least significant decimal digit in character c.

The above method is a bit wasterful, but perfectly acceptable for this assignment. A more parsimonious solution is to treat the ASCII text as a base 128 integer and convert it to base 10.

XPshowASCII()

Now you want to "undo" the transformation above. If you use the direct method above, then if the function XPshowASCII() is called with the integer 104101108108111033, it should print "hello!".

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

The program rsa.c should take two command-line argument (using argv and argc). The first argument is either the string "-e" or "-d" for encryption mode or decryption mode. Consider using the string library function strcmp() to determine whether this first command-line input is "-e" or "-d". If it is neither, print out an error message, and stop the program.

The second argument is the name of the file containing the encryption/decryption key. Your program will read in the exponent and modulus (from the given key file) as strings, and then use these strings to initialize appropriate variables of type XP. Be sure to test your program by printing out these variables using XPshowDecimal().

To decrypt, you should repeatedly read in extended precision integers from standard input. To do this, read it in as a string (using the %s formatting option with scanf()), and then use your XPinitDecimal() function to initialize a variable of type XP. Apply the decryption function. Then use the function XPshowASCII() to convert the integer back into ASCII.

To encrypt, you should repeatedly read in text characters from standard input (using getchar()). When you have enough of them, you will convert this chunk to an extended precision integer using XPinitASCII(). You want to make the chunk size as large as possible, but at the same time ensure that when you convert the chunk into an integer, it is less than the modulus. Using the implementation of XPinitASCII() described above, each text character uses up 3 decimal digits of storage. Thus, your chunk size should be approximately one-third of the number of digits in the modulus. To do this, read it in as a string (using the %s formatting option with scanf()), and then use your XPinitDecimal() function to initialize a variable of type XP. Apply the decryption function. Then use the function XPshowASCII() to convert the integer back into ASCII.

Kevin Wayne