Because the nature of html does not facilitate publishing math formulae, and the most widely available browsers do not support MathML, I shall use Mathematica notebooks throughout the site. One need not purchase the entire Mathemaica package to view these notebooks, however. A front end program, Math Reader, is available for download from Wolfram. This does not allow any of the calculations to be tried (i.e. you won't be able to use the interpreter) but the examples are all viewable.
Here follows a brief outline of the RSA system. The notebooks are accessible from the front page.
RSA is a public-key cryptosystem. This means that one publishes part of the encryption key to allow people to encrypt a message. The rest of the key is kept secret and it is used to decrypt messages. Given the public encrypting key, in is not possible to decrypt the messages. This solves what was known as the Key Distribution Problem. Before public key cryptogrphy, people who wanted to communicate using encryption needed to share a single secret key, which both encrypted and decrypted the message. The problem was that these keys needed to be frequently changed in case one had become compromised. The cost of distributing keys (for example between banks that wished to communicate) was very expensive. With public key cryptography, one can distribute the key to as many people as possible without compromising security.
Another use for public keys is in the authentication of messages. It takes advantage of the fact that if the private decryption key is used to encrypt the message, the encryption key can be used to decrypt it. This enables the sender to prove that they did in fact write the message (as no one else should have access to the private key).
To generate a key pair, a user must first choose two large prime numbers. Some recommend that these be "safe" or "strong" primes, but for the moment large primes will suffice. Let's call these primes p and q. Then the user must calculate n = p * q . This is the public modulus and is part of the published public key.
The next step is to chose an encryption exponent, e, such that the
greatest common divisor of e and (p - 1) * (q - 1) is 1;
i.e. that gcd(e, (p - 1) * (q - 1)) = 1. We now have a public key
and can publish the public exponent and modulus (e, n) so that
people can send us encrypted messages.
Finding the decryption exponent, d, is trivial ONLY if one knows the
values of p and q. We calculate it so that
d.e = 1 (mod (p-1)*(q-1)). This, along with the modulus n
must be kept secret.
So how is this of use to us? Assume that the message, M, can be written as a number or list of numbers less than the modulus, n. To compute C, the ciphertext, for M, we raise M to the power of e modulus n.
The reverse of this process is similar. We raise the ciphertext, C, to the power of d modulus n.
I have been very brief in the description. It hopefully will remind people who have forgotten the details. If you are still not happy, please check back here in a few days - I will provide a Mathematica notebook which will give practical examples and can be worked through. If you can't wait that long, :-), use the link to the original report at the bottom of this page that describes the system in the authors words in more detail.
The security of RSA is based on two difficult problems. Firstly when we encrypt, we are raising to the
The original paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", describing the RSA cryptosystem, was first published in the Communications of the ACM (Feb. 1978). A Latex source or a postscript version can be found on the publications page at MIT.
Ronan Killeen
Back to home.