Really High, Technology
Lies at the Speed of Light
The Science of Secrets
The best-kept secret in the world is the recipe for Coca Cola. The company says the recipe is kept in a very secure vault. Of course, it is not clear how the stuff is manufactured without any access to the recipe. The worst kept secret in the world is the fact that Israel possesses nuclear weapons.
Everyone has secrets. Governments have secret plans for various initiatives, policies, strategies and espionage. Businesses and corporations have lots of secrets. Even normal people have secrets—such as, financial information, family related information and many tidbits of personal information. A letter written by Alice to Bob is private communication, whose contents are to be known only to Alice and Bob, and no one else.
The best way to keep a secret is to memorize it, not to tell anyone, and not to write it down. This strategy is not always feasible. Many secrets have to be documented and sometimes they have to be securely communicated. Given the need for writing and communicating, it is imperative to find methods of writing that would be understandable only to the intended recipient and no one else. This transformation of ordinary writing (known as plaintext) to some convoluted form (known as ciphertext) is called encryption. The reversal of the process is used to decode the ciphertext back to plaintext is decryption. Encryption can be achieved by one of many methods; each such method is called a cipher.
The maintenance of confidentiality of sensitive information has intrigued humans ever since the dawn of civilization. There is evidence that suggests that some Egyptian scribes (about 3000 BC) used an alternate form of hieroglyphics to write down secret information. Julius Caesar is credited for inventing, and using a simple encryption technique, known as the Caesar Cipher.
The Caesar Cipher is simple. It works by replacing each character by another character three steps to the right, i.e. the character A is replaced by D, B is replaced by E and so on. There are two problems with this scheme. The first is that it is very easy to “break”. Anybody who spends some time, trying to decipher an encoded message, can do so, in a matter of tens of minutes (even if this person has never heard of the Caesar Cipher). Secondly, once the cipher is broken, it cannot be reused—we can change the 3 step transposition to 4 steps or 5 steps—but there is a very small number of variations.
Encryptions technology was very heavily studied and used during World War II, when radio was heavily used for communication between troops involved in the fighting. The enemy could listen to the radio transmissions and hence encryption was used to ensure that the messages sent over radio were not comprehensible to the wily enemy. Several machines to perform encryption were invented during this time, the best known of them are the Enigma Machine used by the German, the Purple machine used by the Japanese and the SIGABA and M-209 machines used by the Americans. Common to all of these are that they used were typewriter like things. They used some form of mechanical rotors (or electrical relays) to transform whatever was typed into something that looked gibberish. This gibberish was then sent out and when the gibberish was typed into another machine at the receiving end, with the same rotor setting, the original message appeared on paper. The settings of the rotors changed how the machines transformed the text and hence by changing settings the encryption algorithms could be changed. This usage of transformation and rotor settings was the forerunner of modern cryptographic techniques.
The science underlying the principles used to preserve confidentiality is called Cryptography (in Greek, Crypto = secret, graphy = to write). Encryption using cryptographic techniques relies on mathematics properties of numbers. Number theory plays a serious role in the design of cryptographic techniques. Number theory is the study of properties of integers (numbers such as 1, 2, 3). Numbers always fascinated mathematicians. A simple property such as primality, is not so simple, in fact its quite difficult to find large prime numbers. Factorization—decomposition of a number into its prime factors, is considered to be a very intractable problem. Some very simple looking problems are still unsolved after 300 years of number theory research. For example, no one knows the answer to the question “Is there an even number greater than 2 that is not the sum of two primes?”
Number theory was considered to be “purest” form of mathematics. So pure and so untainted that it has no practical value, whatsoever. That was the charm and beauty of number theory—a theory completely devoid of any practical reason for its existence. Today, number theory forms the basis of modern cryptography. The dead number theorists of the 1700s and 1800s would not only be turning over in their graves but would be quite upset to find their lifetimes of hard work, meant to be completely devoid of use, is actually very useful.
Mathematicians with some knowledge of number theory were the doom of the Enigma machine. The Enigma machine was eventually “broken”. That is, some very clever mathematicians from Poland and England figured out how to convert the gibberish back to the text without knowing the rotor settings (ingenious reverse engineering). This code breaking caused significant damage to the Germans, as they were not aware that their secret communication was no longer secret.
The most successful secret communication method used in WWII was not based on cryptographic techniques, but an ad-hoc scheme that today is called obfuscation. The Americans used this method by utilizing some people who came to be known as “The Navajo Code Talkers”. The Navajo is an ancient tribe of people indigenous to North America. They have an almost extinct language that is very complicated an at that time undocumented. Just a few thousand people alive during WWII spoke Navajo. The US military recruited about 500 of them, and trained them using with a convoluted set of words and phrases to be used for communication. The Navajo Code Talkers were then physically shipped to all the communication centers around the world and they conversed over radio and passed all sensitive information around. The language and he code they used were so bizarre that in spite of enormous efforts put in by the Germans and Japanese. The Navajo code was never broken. It was so successful that the US military used the Navajo Code Talkers again during the Korean War (1950’s) and the Vietnam War (1960’s)..
Of course, the machines and the code talkers and all such artifacts are rendered obsolete by the invention of the microcomputer and subsequently by the advances in cryptography. Cryptographic techniques make is possible to transform plaintext into ciphertext using an encryption algorithm, and then reverse the process too. Mathematically, the encryption algorithm, or cipher, is a “one-way trapdoor function”. A one-way function is a function that takes an input value and produces and output value, such that the input value of the function cannot be determined from the output value. For example, a function that takes a number and produces the digit 0 if the number is even and 1 if the number is odd is a one-way function. Of course, this one way function is useless as it “lossy”—many different input values produces the same output value. Functions used as ciphers have the property that every input value produces a different output value i.e. the function is lossless.
A real one-way function is not suitable for encryption either—as there would be no way to decrypt. Hence the use of the trapdoor functions. These functions can be reversed if you know a particular secret—the trapdoor. This secret is called the “key”. The key is provided to the encrypting function during encryption and then the cipher generated can be transformed back to the plaintext, if you know the key.
Encryption is just one of the tricks in the cryptography bag. Provably correct techniques exists for performing digital monetary transactions (cheques, cash, money orders), secret and fair balloting, identity verification and various methods of handling of privacy.
Cryptographic techniques can also do some baffling tricks. For example, suppose Alice and Bob want to go out to dinner, and Alice wants to eat at a Continental restaurant while Bob prefers Chinese. In order to decide the venue they decide to toss a coin. The problem is that they are discussing dinner plans on the telephone.
Bob says, “I will toss the coin, and you guess, if you guess right you win, else you loose”. Of course, Alice will not fall for this trick, as Alice will always be wrong (Bob will wait for Alice to guess, and then declare the toss had the opposite result).
Can Alice and Bob really toss a coin on the telephone? Surprisingly the answer is Yes. There are many methods to do this, here is one. Alice asks Bob to write two sentences (1) “Lets go Continental” and (2) “Lets go Chinese”, and then encrypt these sentences using a key of Bob’s choosing and then send the encrypted ciphertext to Alice (in some random order). Then Alice picks one of the encrypted sentences, and tells Bob which one. Since these sentences are in ciphertext, Alice has no idea which is what (but Bob does). Next Bob reveals the encryption key and then it is quite obvious which sentence Alice picks (i.e. whether she won or lost). Due to the nature of encryption,. Bob cannot find another key that will change the outcome, in case Alice picks the right sentence.
Today, in the web wired world, cryptography has become the new weapon in guarding the traffic, enforcing rules, verifying identities and is beginning to unleash monetary transactions. The use and impact of cryptography on daily life is expected to grow significantly, and to use a favorite phrase from Ronald Reagan’s vocabulary, “You ain’t seen nothing yet”.
Partha Dasgupta is on the faculty of the Computer Science and Engineering Department at Arizona State University in Tempe. His specializations are in the areas of Operating Systems, Cryptography and Networking.