How Public-Key Crypto Works

Public-key algorithms such as RSA (for developers Rivest, Shamir, and Adleman) encryption seem mind-bending to many people because they defy the conventions for how two-key systems should work. Everyone knows that bank safe-deposit boxes require two keys to be opened (although the one owned by the bank is a bit redundant if the vault is any good). But the two keys in public-key algorithms work differently. The secret one is used to create a digital signat ure; the public one is used to verify it.

The easiest way to understand RSA encryption is to remember two facts from basic algebra: First, numbers have multiplicative inverses, and second, {e^a}^b = e^{ab}. The multiplicative inverse of a number, a, is the number b where a*b=1. So the inverse of 4 is .25 in regular arithmetic.

RSA uses modular arithmetic that operates only on the integers between 0 and a certain number n. It is often compared with the remainder from division. The equation a*b mod n could be translated to mean "multiply a and b, then divide the result by n and return the remainder." Surprisingly enough, much of standard arithmetic rules still hold for this domain. Numbers can be added, subtracted, multiplied, and usually divided and the equations will obey the usual rules of commutation, associativity, and transitivity.

To construct a pair of keys for RSA, find two prime numbers p and q. The product is n. The two keys, e and d, are random n umbers chosen so that e*d mod ((p-1)(q-1)) = 1. That is, d is e's multiplicative inverse. (Additional details about the choice of p, q, d, and e are beyond the scope of this piece.)

The algorithm works because m^de= m mod n. (The reason this works is also beyond the scope of this explanation.) To encrypt a message, convert it into a number m and compute m^e mod n. Only the person who knows d can decrypt it by computing (m^e mod n)^d mod n = m^de mod n = m.

You can think of the public-key process like a string of n pearls. Let one pearl be the message. The public key is some number a, less than n, and the corresponding private key is n-a=b. A message is encrypted by counting along a pearls and decrypted by counting b pearls, which brings everything back to the beginning. This approach is just a metaphor and is obviously insecure. Anyone who knows a and n can figure out b. But this is not the case with RSA or Digital Signature Algorithm. With those algorithms, it is impossible to determine the pri vate key from the public key.