COS 126
RSA
PublicKey Cryptosystem

Programming Assignment
Due: 11:59pm 
Overview.
Write a program to implement the RSA publickey cryptosystem.
The RSA (RivestShamirAdleman)
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 integers.
To thwart eavesdroppers, the RSA cryptosystem must manipulate
huge integers (hundreds of digits). The builtin 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 integer parameters 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 n1.
Then she computes:
E(M) = M^{e} 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) = 2003^{7} 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 = 746^{2563} 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 builtin C types int and long 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.
Part 2 (encryption and decryption).
Now it's time to put all your hard work to use.
The encryption and decryption processes are identical, except
that they involve different encryption/decryption keys.
Write a program rsa.c that takes in one command line
arguments (the name of the encryption key), reads in a decimal
string from standard input, and applies the RSA function
to the message. It should work as follows.
In real applications, you might want to send an ASCII text message
instead of a decimal integer; however, you are only responsible for
handling decimal inputs.
% gcc126 rsa.c xp.c o rsa # compile
% rsa bob.pub < message.txt > message.encrypted # Alice encrypts
% mail bob@princeton.edu < message.encrypted # Alice emails Bob
% rsa bob.pri < message.encrypted # Bob decrypts
Part 3 (analysis).
Perform a complexity analysis of the following operations for
Ndigit extended precision arithmetic:
addition, multiplication, division, RSA encryption
(RSA exponent is small, say 7), and RSA decryption (RSA exponent has
roughly N digits) algorithms.
For each operation, give the exponent and coefficient of the leading
term in its asymptotic running time,
e.g., 1.3 × 10^{5} N^{2} seconds.
Justify your answers with empirical and/or theoretical evidence.
Using this analysis, estimate the largest input (measured in
number of digits) that each of your functions could handle
in 1 day (86,400 seconds).
Depending on your conclusions, you may wish to modify your design
and implementation to improve performance.
You may find it helpful to use the
program
timing.c to estimate the running times of your functions.
Legal notice.
It is a violation of US law to export your solution for this assignment
to foreign governments or embargoed destinations
(Cuba, Iran, Iraq, Libya, North Korea, Serbia,
Sudan, Syria, and Talibancontrolled areas of Afghanistan as of January 2000).
It is also illegal to import your solution into several countries, including
France, Iran, Iraq, and Russia.
Extra credit.
Write a program that compute two large pseudorandom prime numbers
p and q of a specified number of digits.
Compute φ = (p  1) (q  1), and select
a small integer e that is relatively prime with
φ.
Use these to generate a public key (e, n)
and its companion secret key (d, n).
This assignment was created by Bob Sedgewick and Kevin Wayne.
Copyright © 2000
Robert Sedgewick