Public Key Cryptography

About a week ago, in a post about quantum computing, I mentioned the subject of public key cryptography, and its relationship to mathematics, particularly number theory.  The security of these algorithms depends, often, on the difficulty of factoring large integers.  (There are other functions that can be used: discrete logarithms, for example.)  The point is to find a “one-way” function; that is, a function that is easy to compute in one direction (the product of two primes) but difficult to compute in the other (factoring the product).

I had lunch with a very good friend a few days ago, and he asked me how this was used to do public key cryptography.  It had been a while since I looked at an implementation, and I couldn’t remember the details, but this note is an attempt to remedy that.  I’ll describe below, briefly, how the RSA encryption algorithm works.  This is meant to be an example that illustrates the algorithm, not an implementation guide for a complete crypto-system.  I have deliberately left out (for reasons of expository clarity, not secrecy) implementation considerations like padding functions.  The Wikipedia article on RSA has some more information, and there are references to more complete treatments at the end of this note.

RSA Key Generation

1. Select two random prime numbers, p and q. These should be large (see below) and of approximately the same magnitude.
2. Compute the modulus N:   N = pq
3. Compute Φ(N) = (p -1)·(q-1)
4. Select an integer e such that: 1 < e < Φ(N), and gcd( e, Φ(N) ) =1.  (That is, e and Φ(N) are relatively prime.)
5. Compute, using the extended Euclidean algorithm, the integer d such that: 1 < d < Φ(N) and ed≡1 mod (Φ(N)).

The public key is the pair (N, e), and the private key is the pair (N,d).

RSA Encryption and Decryption

Represent the message Μ as an integer m, 0 < m ≤ N-1.  Compute the ciphertext c for m as:

c = m^e mod N

The plain text m for ciphertext c is computed as:

m = c^d mod N

(For obvious reasons, e and d are sometimes called the encryption and decryption exponents, respectively.)

Observations

As I noted above, the security of the algorithm depends on the difficulty of factoring the modulus N.  Absent a practical quantum computer, the consensus of experts is that the length of N should be at least 2048 bits; few think there is any possibility of factoring a 4096-bit value in the foreseeable future.

Computationally, public-key encryption is significantly more expensive than symmetric-key encryption (such as the now-deprecated DES, or the AES).  Often, public key encryption is used to transmit a random session key, which is then used in a symmetric-key algorithm to encrypt the actual message.  If this approach is used, it is of obvious importance that the session keys be truly random.

If you are interested in more details, particularly with respect to implementation, RSA Security has available the PKCS-1 standard; there is also a more in-depth discussion at the site of DI Industries, an Australian software firm.