Do you know that the information you send when shopping over the Internet is encrypted to protect your privacy? The history of encryption is also a long battle between code developers and code breakers. In 1994 it was revealed that encryptions we use on a daily basis on the net may soon be broken almost instantaneously. The development of absolutely unbreakable encryption codes has begun.
The tragedy of Queen Mary
Mary, Queen of Scots (1542-1587), is said to have been beautiful and sharp-witted. She was married three times and spent her stormy life caught up in the struggle of the time between Catholics and Protestants.
©The Granger Collection/PPS
“In My End Is My Beginning”
With these words, which were found embroidered into cloth in the room in which she was imprisoned, Mary, Queen of Scots, went to the executioner's block in 1587 for plotting to assassinate Queen Elizabeth of England. Mary was charged with the crime and imprisoned after the conspiracy came to light.
Mary's letters of the plot were hidden inside the bung of a beer barrel and smuggled out. Furthermore, to avoid detection if the letters fell into enemy hands, all messages were ciphered. Nevertheless, the letters were copied in secret and deciphered.
Mary may have made two mistakes: First, she believed in the loyalty of her retainer, who turned out to be a double agent; second, she put too much trust in her cipher. As she believed her secret code was unbreakable, she described the assassination plot in detail.
Instead, her letters fell into the hands of cryptographers in Europe, and the messages were quickly deciphered. They used a method of frequency analysis. In this method, the frequency of the use of certain letters or symbols in cipher texts was studied. Using poor encryption can lead to fatal mistakes.
Throughout history, cryptography has played an important role and even determined the fates of politics and nations themselves. For example, the history of cryptography dates as far back as Julius Caesar, a military and political leader of ancient Rome, who is known to have used what is called Caesar's cipher, in which each letter in the text is replaced by another letter at a fixed numerical point in the alphabet. (For example, with a shift of 3, A would be replaced by D and B would be E.)
Mary's cipher includes 23 alphabetical letters substituted with symbols (top line), four decoy symbols (second line, left side), a symbol for repetition of the same word (second line, right side), and 35 symbols for frequently used words (bottom three lines). Nevertheless, this code was broken and Mary's assassination plot came to light.
Courtesy of The Code Book by Simon Singh
Cryptography has evolved significantly. During wartime in particular, top-end technologies and human brainpower were called upon to develop or break new cryptographic technology. Alan Turing, an Englishman known as the father of the computer, was involved in breaking the German cipher machine Enigma during World War II.
These encryption codes can readily be broken by finding patterns of regularity within seeming randomness. How then can encrypted data sent over the Internet be securely protected?
Today's encryption that can be decrypted
Mary's cipher was broken due to regularity in the text. The ultimate way to absolutely guarantee security is to change the “key” used to encode and decode a given message for every single character (letter, number, or symbol). This method, called the “one-time pad,” was proven unbreakable by Claude Shannon. One-time pad cipher is perfectly secure, but requires as many keys as the encrypted messages themselves. Also, the sender and the intended recipient of the code must both have a copy of the key before the encrypted message is sent. This presents numerous difficulties.
One solution to the problem of both sender and recipient having the same key is a “public key distribution system” that was invented in 1976. Unlike the conventional private key distribution system, in which a private key for encoding and decoding is owned in common between the sender and the recipient, in public key cryptography, there are two keys: the public key for encoding and the private key for decoding. As public keys are available to anyone, distribution of the public keys (or encoding keys) over the Internet is possible. Today's RSA encryption commonly used over the Internet is based on the public key distribution system.
The recipient creates a set of keys: the public key to encrypt and the private key to decrypt. The public key is available to anyone, but the private key is kept secret. Therefore, anyone can encrypt messages, but only the recipient can decrypt them.
RSA is an encryption method that takes advantage of the fact that there are some tasks today's computers are not very good at. Specifically, computers take an extremely long time to factorize large numbers into prime numbers. Prime factorization is to decompose an integer into a product of factors that are prime numbers such as 3 or 5. Prime numbers are numbers that can only be divided by themselves and one.
For example, it is easy to evaluate 10433 · 16453. However, given the number 200949083, it is extremely difficult to decompose the number into prime numbers. Even with today's high-performance computer, it would currently take years to perform prime factorization of 200-digit numbers. RSA encryption uses the factorization principle to complicate the regularity of patterns in encrypted texts and make it more difficult to decode RSA encryption. Military-use RSA codes would take a good 20 billion years to fully crack with current technology. In this way, RSA encryption utilizes the fact that current computers cannot decompose large numbers into prime numbers within realistic time frames. However, if this problem were ever overcome, then private keys for any given public keys could be worked out easily and all public key cryptography schemes exposed. In 1994, researchers pointed out that this was a possibility.
Cracking codes with light-based computers
Two binary bits can represent four different combinations: [00], [01], [10], and [11]. However, since an individual quantum bit is a superposition of both 0 and 1 states simultaneously, these four combinations can be represented with only two quantum bits. Further, five quantum bits (such as [00001], [00010], [00100].) can represent 32 (25 =32) different states, due to the fact that 2 quantum bits can represent 4 (22 =4) states simultaneously. In a similar way, 100 quantum bits represent 2100 different states. As the number of quantum bits increases, the possible combinations increase exponentially, showing the great advantage of quantum bits.
Quantum computers will be able to perform vast amounts of calculations significantly faster than today's computers. Researchers had long ago predicted and studied the possibility of quantum computers. In 1994, Shor's Algorithm, a quantum algorithm for instantly finding prime factors of large numbers on a quantum computer, was announced. This was an epoch-making year for researchers studying quantum computers. The announcement has attracted the attention of quantum computer researchers and cryptographers, and has encouraged development competition.
“Quantum” means characteristics shown by microscopic substances such as photons and atoms. Quantum computers use photons and atoms for quantum memory. Photons (particles of light) and atoms show superposition states, meaning single particles represent two different characteristics (0 and 1) simultaneously. Using microscopic substances for memory and controlling superposition states make it possible to save large data with less number of bits. Instantly processing complicated calculations that until now have been processed one at a time becomes possible.
Currently, quantum computers with several quantum bits are available. However, researchers estimate it will take another 20 years to engineer computers capable of wielding several dozen quantum bits, because controlling a number of quantum bits all together is extremely difficult. Researchers do not know when, or even if, quantum computers capable of handling several hundreds of quantum bits necessary to break RSA encryption will come into being.
If these computers ever were developed, however, Shor's Algorithm would make it possible to crack RSA encryption. This shocking fact spurred research into a new kind of cryptography that would be invulnerable even to quantum computing. This research has proceeded apace with basic research in quantum computing itself.
Absolutely secure encryption using photons
Interestingly enough, the most powerful form of encryption is not necessarily made of impenetrable elements, but instead photons (or particles of light) of which properties change when handled.
Researchers have found that encryption codes can be made safe through the use of quantum properties, such as atoms and photons. Quantum cryptography, they believe, will be the answer to the security risks that will inevitably arise with the development of quantum computers. Once quantum computers are put into use, private keys will become obtainable through public keys, and the public key distribution system will no longer be an option. The only way to send uncrackable messages will be with a private key distribution system using the same quantum aspects as quantum computers themselves. There is another mysterious quantum property in addition to superposition: an original quantum state breaks down when observed. This means that the very act of listening in will break the key itself, alerting the sender and recipient to the unwanted eavesdropper's presence.
Quantum cryptography system
In 1984, Charles H. Bennett and Gilles Brassard proposed a method of realizing a quantum cryptography system using photons. This idea became known as “BB84,” after the names of its inventors and the year it was published. In this protocol, a secret key is transmitted by sending photons one by one. The private key is transmitted through photon polarization. Each photon has a specific direction polarization, which is the direction of propagation of the light wave.
Polarization refers to a light wave with a specific direction. Some possible states are vertical, horizontal, 45°, and 135°. Every photon has its own state of polarization.
The state varies when observed
When a transmission is made with the BB84 protocol, the eavesdropper changes the state of the photons, alerting the recipient to the eavesdropper's presence. In this case, all the sender needs to do is discard the private key already sent and resend another private key. And, since all data sent was the decryption key, not the message itself, the interception does not compromise security. Once the sender and recipient are sure that their private key has been sent securely, they can securely communicate using the one-time pad method and shared private key.
Simple quantum cryptography systems are already at the practical application stage. The history of cryptography has always been a struggle between code developers and code breakers, but now it has evolved to the very boundaries of nature's physical laws, far beyond the inventiveness of developers and breakers.
Editorial contributor / Date of article posted
Professor Hiroshi Imai and Adjunct Associate Professor Masahito Hayashi of the University of Tokyo / April 2006