All asymmetric ciphers are based on bizarre mathematical properties; the elaborate bit shuffling of block ciphers won't cut it here. One of the consequences of this is that asymmetric ciphers are slow, and are therefore rarely used to encrypt large blocks of data. Instead, the usual approach is to encrypt data with a conventional cipher using a randomly generated key; that key is first communicated using the public key cipher, effectively increasing the amount of data the public key can encrypt. Another advantage of this approach is that it exposes only a single, fairly small, public key operation to an attacker; see the Key Management page for more discussion on this topic.
Since all asymmetric ciphers depend on mathematical properties, they require data to be represented in the form of numbers. Typically, a particular set of key values will be chosen to allow numbers from 1 up until a certain power of two, and the larger the numbers, the more secure the cipher. Commonly used limits, for both RSA and El Gamel, are 2512 (considered breakable), 2768, 21024 (recommended), and 22048 (for extremely valuable keys). PKCS #1 (RFC 2437) specifies, among other things, how to convert a block of data (up to a size limit) into a single large integer that is then used in the cipher algorithms.
RSA was the first and most widely used public key cryptosystem. Developed in 1977 by three M.I.T. professors, it's based on the mathematical properties of modulo arithmetic.
Modulo arithmetic is much like normal arithmetic, but only uses integers no larger than a limiting number, the modulus. Any result larger than the modulus has the modulus subtracted from it repeatedly until it is less than the modulus. Thus, instead of the numbers forming a line, as is conventional, modulo numbers can be though of as forming a ring, when the largest numbers loops back to 0.
For example, 8 + 8 mod 15 = 1 since 16 is larger than the modulus (15) and 16 - 15 = 1. Likewise, 4 × 7 mod 15 = 13 since 28 - 15 = 13. Exponentiation is similarly defined; 33 mod 15 = 12 since 33 = 27 and 27 - 15 = 12. If the result were larger, we'd just subtract out the appropriate number of m's (as the modulus is usually written) to get back into the range 0 to m-1.
Modulo fields have some bizarre properties, though. For example, if the modulus is prime, division is defined, even though all the numbers are integers. Thus 3 ÷ 2 mod 11 = 7 (!) since 7 × 2 mod 11 = 3. RSA depends on a property of modulo fields related to exponentiation. It can be shown that every modulo field has a special power, called the Euler totient function and written ø(m), so that any number raised to this power equals 1, i.e. xø(m) mod m = 1. Furthermore, ø(m) is difficult to compute without knowing the prime factorization of m. If m is the product of two primes, typically called p and q, then ø(m) = (p-1)(q-1).
This is how RSA works. Pick two large prime numbers p and q. Multiply them together to form an even larger modulus m. Now compute ø(m) = (p-1)(q-1). Since xø(m) mod m = 1, it stands to reason that xø(m)+1 mod m = x. We now have a special power, typically very large, that will produce an identity transformation on any number. Factor this special power into two factors. Since (xy)z = x(yz) for any numbers, raising a number of one of these two factors produces gibberish, and raising the gibberish to the second factor produces the original number (since yz = ø(m)+1). Publish one of these powers (y); this is the public exponent and in conjunction with m forms the public key. The other power (z) is kept secret, this secret exponent allows the original number to be recovered.
Here's an example, using very small numbers. Let's choose 33 (3 × 11) to be our modulus, so ø(m) = 2 × 10 = 20 and ø(m)+1 = 21. Thus, we know that x21 mod 33 = x, for any x. Now, factor 21 = 3 × 7. So, to raise a number to the twenty-first power, we can raise it first to the third power, then raise that result to the seventh power. We'll use 3 as our public exponent, and keep 7 as our private exponent. Now, our published public key consists of the modulus (33) and the public key (3). We can encrypt any number between 1 and 32 (one less than the modulus). Let's encrypt 15.
Even based on small numbers, we end up dealing with large enough numbers to require a calculator, so you can see that when based on large numbers, RSA becomes very difficult to crack!
Like RSA, El Gamel operates using modulo arithmetic, but depends on the difficulty of the discrete logarithm problem. As you may remember, taking a logarithm is the inverse of exponentiation. So, if x = yz, then z = logy x; i.e, z (the power) is the logarithm of the x (the result of exponentiation). Using normal arithmetic, logarithms are often long decimal numbers. The discrete logarithm problem computes logarithms in a modulo field - all of the numbers involved are integers. Furthermore, it is computationally very difficult to compute discrete logarithms, unlike conventional logarithms, which can be computed fairly easily. So, if x = yz mod m, then it is nearly impossible to invert this calculation and compute z, given only x, y, and m. Just as RSA will be cracked if anyone figures out how to quickly factor large prime numbers, El Gamel will be cracked if anyone can devise a scheme to easily compute discrete logarithms.
Here's how El Gamel works. Pick a modulo m (a very large prime number), and two random numbers b (the base) and s (the secret key) between 1 and m-1. Now compute the public key y = bs mod m, and publish m, b, and y, keeping s secret. Presumably, the difficulty of computing discrete logarithms prevents someone from figuring out s from the published information. Now, to send a message M (a number between 1 and m-1), the sender picks a random number k between 1 and m-1, and computes:
Here's an example of El Gamel in operation, again using very small numbers. We'll use 31 as our modulus, 6 as our base, and 5 as our secret exponent. Our public key is:
Other public key systems include knapsack ciphers (largely broken)
and elliptic curve cryptosystems (not widely used). For more
information, see RSA Laboratory's
Cryptography FAQ.