This post is to tie up some loose ends in regards to actually performing the RSA computations. I've avoided including too much math in the earlier posts to make them easier to read. Here are some references that help explain the individual steps.

The algorithm starts with generating n, a product of large primes, and e, the encryption exponent. Large primes are typically found by generating large random numbers and testing whether they're probably prime. It's easy to eliminate the random numbers that are obviously not prime, such as multiples of small primes, leaving only a few hundred tests necessary to find a 1024-bit or 2048-bit random prime number. The encryption exponent is frequently a fixed, small value, such as 65537. Using e = 3 used to be relatively popular because the exponentiation step becomes very cheap, but we've seen how this is sometimes dangerous.

The decryption exponent, d, is the modular inverse of the encryption exponent. Modular inverses can be found using the Euclidean algorithm.

Messages are encrypted by exponentiating the plain text message with the encryption exponent.

M' = Me mod n

Messages are chunked into fixed-size blocks to make them easier to work with. Messages are decrypted by exponentiating the encrypted message with the decryption exponent.

M'd mod n = (Me mod n)d mod n = Me*d mod n

For both of the large primes that make up n, we can use Fermat's Little Theorem to show that Me*d = M modulo the prime number. We can then use the Chinese Remainder Theorem to combine these congruences and show that Me*d = M mod n.

Next time: ROT 128 Stream Upgrade Sample, Part 1