PUBLIC KEY CRYPTOGRAPHY

Up to this point all the examples have assumed that the encryption process is undertaken with the same key as the decryption process, and that only the sender and the receiver possess the secret key. However, this can cause problems.

The Key Distribution Problem

A major problem in the practical use of single-key cryptography is the key distribution problem. This problem basically occurs because both the sender and receiver must hold a copy of the key, but they must also prevent others from gaining a copy of the key.

This does not, on the face of it, appear to be a problem, but it can be one as is probably best illustrated by an example.

Suppose that two individuals, O and L, wish to exchange information securely but can not guarantee the security of the transmission itself. They would probably use some sort of encryption to ensure that even if the message was intercepted its contents would remain secret. In order for this to operate they would both have to know a secret key which could be used to encrypt the data. However, since the transmission medium is not secure they would have to meet in person to decide upon the key. Once this was done, however, they could exchange information happily, encrypted with this secret key, in the knowledge that to anyone without the key it would simply look like garbage. O and L must protect the security of the key in their possession since if a cryptanalyst, C, obtained it, he could read, alter or fake a message from either O or L.

This appears to be working perfectly, except a problem could soon arrive. Suppose that O or L then wanted to correspond with another individual, T. If they were to give T the key they would further compromise it because C would now have another source from which he might obtain it. In order to ensure that each message is not intercepted by another party both O and L would have to create different keys to exchange with T so that they would all each hold two keys (because otherwise O could alter T’s message to L and so forth).

Now consider a system with 1,000 members, all of whom wish to communicate in secret with each other. In this case, each individual would need to hold a key for every individual besides himself, in other words 999 keys for other people. Each individual would also have to protect those 999 keys from being compromised.

It is possible to calculate the number of keys present in a system with any number of members using these facts as I have done below, calculating the number of keys required by multiplying the number of members minus one by the number of members and divided by two.

Keys = [n ´ (n-1)]/2

Members	#/Members2	# of keys required
2	4	1
3	9	3
4	16	6
5	25	10
6	36	15
7	49	21
8	64	28
9	81	36
10	100	45
100	10000	4950
1000	1000000	499500

The number of keys is divided by two because some of the keys are duplicated (the key A uses to send to B is the same which B uses to send to A). The reason why I have included a column containing the number of members squared is made obvious below.

Here is a graph of the number of members squared against the number of keys required (I have excluded the final two rows to ensure that there is a practical scale).

As you can see the number of different keys required is nearly proportional to the square of the number of members in the system. This is the key distribution problem.

A Solution To The Key Distribution Problem

A solution to the key distribution problem can be found in public key, or two-key, cryptography. Public Key cryptography is based on the idea that a user can possess two keys - one public and one private key. The public key can only be used to encrypt the data to be sent and the private key can only be used to decrypt it. Although single-key cryptography has been in use for centuries, public key cryptography is a relatively new invention with the first discussion about the subject in open literature being in 1976.

The fact that anyone can use a single "locking" key to encrypt a message which they are confident can still only be read by a single authorised user means that the number of keys required can be greatly reduced. For example, in the 1000 member system above the number of keys necessary could be reduced from 499,500 to 2000 (1000 public and 1000 private keys).

For example I will use a far simpler three user system. An individual, say P, could distribute his public key to two other individuals, A and C. A could then send a message to P by encrypting it with the public key. When P receives the message he could then decrypt and read the message using his private key. Supposing C was a nosy individual then he might attempt to spy on the communications between A and P, however, because he only possesses the encrypting key, he can not decrypt the message.

There is a problem with this solution however. In this example, although C can not read or alter a message sent to P by A, he or she could easily fake a message because C has the same public key as A. Therefore, with a public key system the ability to authenticate messages has been given up in return for privacy. In many cases this will not be a problem however there are times when it will be so.

There is an alternative to this method. A could send P and C his or her private (unlocking) key and keep the public key secret. A could then encrypt messages with his public key and send them to either P or C. This system has the advantage that the person receiving the message knows that it must have come from A; however, both P and C can now decrypt the message. In this example secrecy has been sacrificed in order to maintain an ability to authenticate the message.

This is a problem with the public key system which can only be solved by increasing the number of keys in the system. It can be solved however, by combining the two methods outlined above. If each user had two sets of public and private keys and distributed one key from each set then the capability to authenticate messages and to keep them secret would be maintained.

For example, another three individuals P, D and W are using this system. Each user holds, in addition to their normal private (unlocking) key and everyone else’s public keys, a public key which is paired with a private key which they then distribute. P could then encrypt a message with his own public key, thus authenticating it, and then encrypt it with the public key of whoever the message was intended for (thus ensuring secrecy).

Under this system each message is encrypted twice, once in a way which only the intended receiver can decrypt it, and once in which only the authentic sender could have encrypted it. Even though the number of keys required has been increased it still does not approach the number of keys which would be required for a single-key system of the same size.

It is this idea of nested encryption processes with public and private keys which makes public-key cryptography so attractive.

Properties For A Two-Key Cryptosystem

For two-key cryptography to be possible a cryptosystem must have the following properties:

1. It must be easy for the cryptographer to calculate a pair of keys (private and public) but virtually impossible for a cryptanalyst to recover either key, regardless of how much ciphertext is available.
2. The encryption and decryption operations should be easy (computationally speaking) for legitimate users to carry out.
3. At least one of the keys must be virtually impossible for the cryptanalyst to recover even when he knows the other key and many matching plaintext and ciphertext pairs.

At present no cryptosystem ever devised has satisfied all of these conditions in a provable way. However, cryptographers have devised cryptosystems of this sort by starting with a difficult mathematical problem such as factoring a product of large prime numbers and attempting to make the cryptanalysis of the scheme be equivalent to solving the problem. If this can be done then the security of the scheme is at least as good as the underlying problem is hard to solve.

There are a number of problems that are commonly used as the basis for public key cryptosystems.

Knapsack Problem

Ralph Merkle, XEROX and Martin Hellman, Stanford University, put forward one of the best known proposals for a public-key cryptosystem in 1976. In 1997 the six co-founders of public key cryptography were awarded the Paris Kanellakis Theory and Practice Award, named after a researcher who died in 1995, for their work. Hellman and Merkle were among those who received the award.

They suggested using the knapsack, or subset-sum, problem as the basis for a public key cryptosystem. This problem entails determining whether a number can be expressed as a sum of some subset of a given sequence of numbers and, more importantly, which subset has the desired sum.

Given a sequence of numbers A, where A = (a₁ ... a_n), and a number C, the knapsack problem is to find a subset of a₁ ... a_n which sums to C.

For a specific example:

n = 5, C = 14, A = (1, 10, 5, 22, 3)

Solution = 14 = 1 + 10 + 3

In general, all the possible sums of all subsets can be expressed by:

m₁a₁ + m₂a₂ + m₃a₃ + ... + m_na_n where each m_i is either 0 or 1.

The solution is therefore a binary vector M = (1, 1, 0, 0, 1).

There is a total number 2ⁿ of such vectors (in this example 2⁵ = 32)

Obviously not all values of C can be formed from the sum of a subset and some can be formed in more than one way. For example, when A = (14, 28, 56, 82, 90, 132, 197, 284, 341, 455, 515) the figure 515 can be formed in three different ways but the number 516 can not be formed in any ways.

The only known solution to the general knapsack problem (as above) is a brute force test - testing all the possible subsets until either the sum is found or you run out of subsets.

However, there is a special case if A is sorted and when each progressive term is larger than the one which follows it (called the simple knapsack problem) and there is an easy solution (this type of sequence is described as superincreasing). The value of C is compared to each value of A, starting with the largest. If A is larger than C then that number is not in the subset, if it is smaller then that value is in the subset. The next value is then compared to C less the sum of all the values found already.

For example:

A = (1, 3, 5, 10, 22), C = 14

14 £ 22 m₅ = 0

14 ³ 10 m₄ = 1

4 £ 5 m₃ = 0

4 ³ 3 m₂ = 1

1 ³ 1 m₁ = 1

M = (1, 1, 0, 1, 0)

The cryptographer uses a secret transformation to turn a simple knapsack into a hard one. Legitimate users, knowing the secret transformation, could easily invert the hard knapsack back to the simple knapsack. This can be done using a private multiplier and a private modulus, the original sequence is multiplied by the multiplier and then dividing by the modulus (finds the remainder). This has the effect of scrambling the values. The plaintext is then converted into a set of binary bits which are then multiplied by the values of the public sequence and the result is recorded. To decrypt them is the equivalent of the hard knapsack problem for anyone who doesn’t know the secret information.

For example:

Taking the following private information:

A = (1, 3, 5, 10), b = 20, k = 7 (b is the private modulus, k is the private multiplier)

\ A = (7 ´ 1 mod 20, 7 ´ 3 mod 20, 7 ´ 5 mod 20, 7 ´ 10 mod 20)

Public key = (7, 1, 15, 10)

To encrypt the plaintext we must convert in into a binary number. For this simple example I will convert the letter to a value describing its position in the alphabet.

Let plaintext P = m (= 13) = 1101

Assigning each of these values a "size" from the public key and multiplying produces the following code, C.

C = 1 ´ 7 + 1 ´ 1 + 0 ´ 15 + 1 ´ 10 = 18 (= r)

The code letter is therefore r.

To decrypt this code letter without the secret transformation would be computationally infeasible, so we must perform the operation on the letter r (18).

To decrypt, use the inverse key k^-1.

Let k^-1 = 3 (any value for which k ´ k^-1 mod 20 = 1)

Let C = 18

C’ = 3 ´ 18 mod 20 = 14

Now we can use the value of 14 to solve the simple knapsack problem.

(1, 3, 5, 10)

14 ³ 10 m₄ = 1

4 £ 5 m₃ = 0

4 ³ 3 m₂ = 1

1 ³ 1 m₁ = 1

\ M = (1, 1, 0, 1) corresponds to binary 1101 = 13 = m

Unfortunately, it has been shown that it is possible, in a reasonable length of time, to derive the private key from the public key thus knapsack-based cryptosystems have been shown not to be secure. However, although of little practical use, they are an excellent introduction to the idea of public key encryption.

Rivest-Shamir-Adleman (RSA) Algorithm

The main contenders for two-key cryptosystems in the mid-1980s were those based on factoring large integers. Of these, the best known is the RSA algorithm, developed by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977.

In this system a user chooses a pair of prime numbers so large that factoring the product is beyond all computing capabilities. This is possible because testing for primes is easy whereas factoring the product is very difficult.

In practise, RSA works as follows. The user takes two large primes, p and q, and computes their product n = pq. n is called the modulus. The user then chooses a number, e, less than n and with no common factors (except 1) with (p-1)(q-1). Another number, d, is then found, subject to the condition that (ed-1) is divisible by (p-1)(q-1). e is called the public exponent, d is called the private exponent. The public key is therefore the pair n and e, the private key is the pair n and d. The factors of n, p and q, can either be kept secret with the private key or destroyed.

It is currently virtually impossible to obtain the private key, d, from the public key (n and e). However, if n could easily be factored into p and q then a cryptanalyst could obtain the private key, d. The security of RSA is therefore based upon the assumption that factoring is difficult.

Here are the stages in sending a message using this method:

1. The receiver, M, distributes his public key pair.
2. The sender, F, composes a plaintext message, m, and then uses Ms public key to encrypt the message and form the ciphertext, c. c is the remainder left when m is raised to the power of e and divided by the modulus n.

c = m^e mod n (where e and n are Ms public key pair).

3. F sends the ciphertext, c, to M.
4. The receiver, M, decrypts the ciphertext and retrieves the plaintext message, m. m is the remainder obtained when c is raised to the power of d and divided by n.

m = c^d mod n

5. As you can see, this process requires d, which only M knows. Another person, I, who intercepts the message, can not decrypt it.

For example:

Let p = 5, q = 11, n = pq = 55

The least common multiple of (p-1)(q-1) is 20 = 2² ´ 5.

Therefore, in this case, any key, e, not divisible by 2 or 5 will have a matching key, d (e must be relatively prime to (p-1)(q-1) for it to be the key).

Let e = 7

(ed -1) mod (p-1)(q-1) = 0 \ d = 3

Let the plaintext message, m = b = 2

\ The ciphertext, c = m^e mod n = 2⁷ mod 55 = 18

To decrypt this information it is necessary to know d.

m’ = c^d mod n = 18³ mod 55 = 2 \ The message has been successfully decrypted.

This example used small primes so it can be seen that the product, n, is not at all difficult to factor to retrieve the original primes. In using RSA it has always been suggested to use "strong" primes which have certain properties making their product especially difficult to factor using certain factoring methods. However, advances in factoring techniques over the last decade have near completely negated the advantage of strong primes, the elliptic curve factoring algorithm is one such advance. Therefore, it is not choosing traditionally "strong" primes which matters but rather choosing large primes.

In 1997, a specific assessment of the security of 512-bit RSA keys shows that one may be factored for less than $1,000,000 in cost and eight months of effort. It is therefore believed that 512-bit keys provide insufficient security for anything other than short-term needs. RSA Laboratories currently recommends key sizes of 768 bits for personal use, 1024 bits for corporate use, and 2048 bits for extremely valuable keys like the root-key pair used by a certifying authority. Security can be increased by changing a users keys regularly and it is typical for a user’s key to expire after two years (the opportunity to change keys also allows for a longer length key to be chosen).

It should be noted that the key sizes for RSA (and other public-key techniques) are much larger than those for block ciphers like DES, but the security of an RSA key cannot be compared to the security of a key in another system purely in terms of length. It should also be noted that although increasing the length of the modulus may increase the security of the system it also significantly increases the amount of time required to perform encryption, decryption and authentication - doubling the modulus will, on average, quadruple the amount of time taken for encryption and increase the time taken for decryption by a factor of eight.

"Real World" Usage Of The RSA Algorithm

DES, and other block ciphers, are much faster in operation than RSA. Typically, in software, DES is approximately 100 times faster than RSA and in hardware can be between 1000 and 10000 times faster depending on the implementation. Because of the length of time taken for public key encryption a public key system such as RSA is often used in conjunction with a secret-key system such as DES. In this case the message is encrypted with a randomly chosen DES key and the key itself is encrypted and sent with RSA. This method combines the low number of keys required for RSA with the high-speed operation of DES.

RSA is the most widely used public-key cryptosystem available currently and has often been referred to as a de-facto standard regardless of official recognition. In fact, RSA is part of many official standards worldwide. These include ISO 9796 which lists RSA as a compatible cryptographic algorithm and many internet standards and proposals including S/MIME.