The idea behind any public-key cryptosystem is that a user can
release a *public key* which can be used only for encryption;
in other words, that key cannot be used to decipher encrypted text
without performing a lot of work. In the RSA cryptosystem, that
work is factoring, a problem believed to be difficult. An RSA
public key consists of two elements: an exponent *e* and a
modulus *n*. To encrypt a message, split it up into
components whose values are no more than *n* apiece, and then
run them through the encryption function

where "*x* mod
*y*" denotes the function that returns the unique integer
*z* equivalent to *x* modulo *y*. A useful fact is
that this function defines a permutation when *n* is the
product of two primes *p* and *q* and when *e* is
the multiplicative inverse of an integer *d* modulo
*(p-1)(q-1)* that is also relatively prime to
*(p-1)(q-1)*.

To decrypt, we run the value E(x) through the decryption function

where *d* is as we stated above. This is the inverse
permutation of E(x). We thus consider the secret key to be the
exponent *d* and the modulus *n*, with *d* being
the "trapdoor" information (i.e., the information needed to easily
invert E(x)).

In order to implement the RSA cryptosystem securely, large
integers must be used. If the factorization of *n* is known,
then the multiplicative inverse of *e* modulo
*(p-1)(q-1)* -- meaning *d*, the "trapdoor" information
-- is very easily found using Euclid's GCD algorithm. Thus, we
must prevent the user from finding the factorization of
*n*.

In order to work with large integers, code must be written to handle them. Typical integer routines on modern-day computers deal only with 32 bits; in order to be secure, 200 bits or more are required. I thus created a large integer package which allows addition, multiplication, division, and exponentiation on integers with an arbitrary number of bits.

The addition and multiplication algorithms work as expected, and the exponentiation algorithm uses a very simple application of dynamic programming. The division algorithm, however, was quite a work of art. Since we are working with 32-bit integers at the chip level, we want to have an algorithm that does as few multi-integer operations as possible. This motivates the creation of a helper function:

This function divides a large integer x by a 16-bit integer, or halfword, and returns a large integer quotient q and a halfword remainder r. This is easily done using long division as learned in grade school.

The large integer divison function

is quite a bit more complicated. It works on an iterative
basis. First, it splits y into two pieces: h and m, where h is
the y rounded up to the nearest high-order halfword and m=h-y.
Then, we execute (q_{1},r_{1})=Div16(x,h). We
set s=x-(h*q_{1}), x=q_{1}*(m+r_{1}),
and add q_{1} to a running sum, q. It turns out that
this algorithm eventually produces the quotient q and the
remainder r. (The proof is omitted due to the difficulty of
entering math formulae in HTML.)

This division algorithm has a running time of *n* log
*2 ^{n}*, or