The RSA algorithm.

The most used cryptography system is the RSA algorithm proposed by Rivest, Shamir, and Adleman in their article "On Digital Signatures and Public Key Cryptosystems," Communications of the ACM 21 (1978): 120-126.

This is a public-key system in which the key needed to encode messages is made public, but the key needed to decode messages is kept private. It works because the private key cannot be determined from the public key. (At least it can't be determined easily.)

The RSA algorithm is based on exponentiation modulo n. The encoding and decoding algorthims are actually functions from the set of integers modulo n, Z_n, to itself. That means that the message has to start out as an element a in Z_n, that is, a nonnegative integer a less than n. A real message is actually a string of characters, so a preliminary coding is needed to convert that into a string of numbers modulo n.

This RSA system is public-key which means the algorithm for coding is made public, but the inverse algorithm for decoding is kept private. You would think that if you knew one function, it wouldn't be hard to find the inverse function. But there are a number of these trap-door functions that don't seem to be easily inverted.

Here are the steps in creating the two keys for the encoding and decoding functions for the RSA system.

1. Select two large prime numbers p and q, and let n = pq. Then the Euler phi function has the value Phi(n) = Phi(p)Phi(q) = (p–1)(q–1).
2. Select a number e relatively prime to Phi(n). (This number e can be pretty small, as low as e = 3.)
3. Compute the inverse d of e modulo Phi(n). That is, solve the congruence ex congruent to 1 modulo Phi(n), and call the solution d. Solving that linear congruence will involve the Euclidean algorithm.
4. The encoding algorithm is the function on Z_n which converts the original message a into the coded message a^e modulo n. Make public this encoding algorithm, that is, make public n and e.
5. The decoding algorithm is the function Z_n which converts an coded message b back into the original message a^d modulo n. Keep private this decoding algorthm, that is, don't tell anyone d, and don't tell anyone p or q either, because then d could be determined.

Source files:

• LongPair.java Routines for GCD and solving linear Diophantine equations.
• Mod.java Routines for modular arithmetic.
• PublicKey.java The applet.

David E. Joyce
Department of Mathematics and Computer Science,
Clark University