Thursday 11 June 2009
In Cryptography the distribution of secret keys is an important problem. For years it was believed that the only possibility to solve the key distribution problem was to send some physical medium — a disk for example — containing the key. In the digital era, this requirement is clearly unpractical. In addition, it is not possible to check whether this medium was intercepted — and its content copied — or not.
In the late sixties and early seventies, researchers of the British “Government Communication Headquarters” (GCHQ) invented an algorithm solving this problem. To take an image, it is as if they replaced the safe mentioned in the cryptography introduction by a padlock: before the communication, the intended recipient sends an open padlock to the party that will be sending valuable information, while keeping the padlock key. The sender uses this open padlock to protect the data. The recipient is then the only one who can unlock the data with the key he kept. “Public Key Cryptography” was born. This invention however remained classified and was independently rediscovered in the mid-seventies by American researchers.
Formally, these padlocks are mathematical expressions called “one-way functions”, because they are easy to compute but difficult to reverse.
As public key cryptography algorithms require complex calculations, they are slow. They can thus not be used to encrypt large amount of data and are exploited in practice to exchange short sessions keys for secret-key algorithms such as AES.
In spite of the fact that it is extremely practical, the exchange of keys using public key cryptography suffers from two major flaws. First, it is vulnerable to technological progress. Reversing a one-way function can be done, provided one has sufficient computing power or time available. The resources necessary to crack an algorithm depend on the length of the key, which must thus be selected carefully. One must indeed assess the technological progress over the course of the time span during which the data encrypted will be valuable. In principle, an eavesdropper could indeed record communications and wait until he can afford a computer powerful enough to crack them. This assessment is straightforward when the lifetime of the information is one or two years, as in the case of credit card numbers, but quite difficult when it spans a decade. In 1977, the three inventors of RSA — the most common public key cryptography algorithm — issued in an article entitled “A new kind of cipher that would take million of years to break” a challenge to crack a cipher encrypted with a 428-bits key. They predicted at the time that this might not occur before 40 quadrillion years. The 100$ prize was however claimed in 1994 by a group of scientists who distributed the calculations over a large number of computers using the Internet. Besides, Peter Shor has proposed in 1994 an algorithm, which would run on a quantum computer (Quantum computers are computers that exploit the laws of quantum physics to process information. They are still in the realm of experimental research, but will eventually be built.) and allow to reverse one-way functions, to crack public key cryptography. The development of the first quantum computer will consequently immediately make the exchange of a key with public key algorithms insecure.
The second flaw is the fact that public key cryptography is vulnerable to progress in mathematics. In spite of tremendous efforts, mathematicians have not been able yet to prove that public key cryptography is secure. It has not been possible to rule out the existence of algorithms that allow reversing one-way functions. The discovery of such an algorithm would make public key cryptography insecure overnight. It is even more difficult to assess the rate of theoretical progress than that of technological advances. There are examples in the history of mathematics where one person was able to solve a problem, which kept busy other researchers for years or decades. It is even possible that an algorithm for reversing one-way functions has already been discovered, but kept secret. These threats simply mean that public key cryptography cannot guarantee future-proof key distribution.
Quantum Key Distribution is a technology that uses the laws of quantum physics to solve the key distribution problem over optical networks.