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 (q1,r1)=Div16(x,h). We set s=x-(h*q1), x=q1*(m+r1), and add q1 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 2n, or n2 basic chip operations, where n is the number of bits in the dividend.