Currently At: Internet Encyclopedia > Concepts > Cryptography > Algorithms > Public Key Ciphers

Public Key Ciphers

One of the most exciting developments in cryptography has been the advent of public key cryptosystems.

Public key systems

Public key cryptosystems are based on asymmetric ciphers. A symmetric cipher, such as all the block ciphers in common use, use a single key for both encryption and decryption. If you know the key, you can decrypt the message - it's as simple as that. Asymmetric ciphers, on the other hand, use at least two different keys - one for encryption, and one for decryption. If you possess only the encryption key, it is impossible to use it to decrypt the data. Likewise, if you possess only the decryption key, it is impossible to encrypt data that will decrypt with that key. These unique properties make some fascinating possibilities. Typically, we publish one of two keys, called the "public key", and thus the common name for these systems. The other key we keep secret; this is termed the "private key". Now, if the encryption key is published, then anyone can use it to encrypt messages which can only be read by the private key holder. Even though the encryption key is public knowledge, it can't be used to decrypt the messages it encodes. Likewise, if we publish the decryption key, then anyone can decode its messages, but only the private key holder can encrypt them. This can be used to implement a digital signature scheme; by running a hash function over a message, then encrypting the signature with the private (encrypting) key, a signed message has been created that can be verified by anyone with the public (decrypting) key, but can't be tampered with without invalidating the signature. Note that this is similar to, but different from, HMAC (RFC 2104) which implements a signature using conventional, symmetric ciphers and a shared secret key.

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 2⁵¹² (considered breakable), 2⁷⁶⁸, 2¹⁰²⁴ (recommended), and 2²⁰⁴⁸ (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

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; 3³ mod 15 = 12 since 3³ = 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 (x^y)^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 x²¹ 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.

15³ = 3375

33 × 102 = 3366

15³ mod 33 = 3375 - 3366 = 9

So 15 encrypts as 9. Now let's decrypt it, using the private exponent:

9⁷ = 4782969

33 × 144938 = 4782954

9⁷ mod 33 = 4782969 - 4782954 = 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!

El Gamel

El Gamel is probably the second most widely-used public key cipher. It gained popularity because of the patented nature of RSA (the patent has now expired).

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 = y^z, then z = log_y 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 = y^z 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 = b^s 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:

y₁ = b^k mod m

y₂ = y^k M mod m

and sends both y₁ and y₂; this is the encrypted message. To decrypt the message requires knowledge of s, which allows the following computation:

y₁^-s y₂ mod m = b^-ks b^ks M mod m = M

Essentially, b^ks is a message key, with one of its factors (k and s) known to each side in the exchange, used to encode the message in y₂. y₁ encodes k in such a way that the private key can be used to compute the message key and recover the original message. El Gamel can also be used for authentication.

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:

y = b^s mod m = 6⁵ mod 31 = 7776 mod 31 = 26

So, we publish 31 (m), 6 (b), and 26 (y). Again, we'll encrypt 15, and we'll pick 2 as k, our secret message key

y₁ = b^k mod m

y₂ = y^k M mod m

So, our message encrypts as (5,3). Note that a single number encrypts into two numbers; this doubling of size is one of the disadvantages of El Gamel. Now let's decrypt it

y₁^-s y₂ mod m = (5^-5 × 3) mod 31 = (25⁵ × 3) mod 31 = (9765625 × 3) mod 31 = 29296875 mod 31 = 15

In the decryption, I used the fact that in the mod 31 field, 5 and 25 are inverses (since 5 × 25 mod 31 = 1) to change the negative exponent into a positive one. Remember, so long as the modulus is prime (a requirement for El Gamel), division is defined, so numbers can be inverted and negative exponents are legal.

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.