Encryption’s
history has been one of unceasing efforts to devise uncrackable codes—and equally unceasing efforts to crack them. Early ciphers were relatively simple systems, easy for both sender and receiver to use. Julius Caesar, for instance, encoded messages with a “substitution cipher” in which each letter is replaced by the third letter after it in the alphabet: A is replaced by D, B by E, etc. At the end of the alphabet, the pattern wraps around to the beginning: X becomes A, Y becomes B, and Z becomes C. Unfortunately, simplicity of use is a double-edged sword: The ciphertext thus encoded is highly susceptible to being decoded. Caesar’s cipher can be cracked simply by moving each letter in the encoded message back three spaces in the alphabet. More sophisticated substitution ciphers, in which the alphabet is thoroughly scrambled, are nevertheless easy enough for amateurs to break, as fans of the “Cryptoquote” puzzles in today’s magazines and newspapers can attest. In any sufficiently long passage of English text, the most common letter is usually “E,” the second most common is “T,” and a three-letter word that appears repeatedly is probably “THE.” By applying this type of “frequency analysis,” an eavesdropper can easily guess which letters in the ciphertext represent “E,” “T” and so on.
Over the years, people who wanted greater secrecy came up with more elaborate coding schemes. In the 1500s, Blaise de Vigenère, a French diplomat, invented a method for encrypting different letters in a message with different ciphers. Thus, an “E” in one position might be coded as “M,” while an “E” in another position might be coded as “K,” thereby foiling anyone attempting to decode the message using frequency analysis.
In the Vigenère cipher, the sender and recipient had to agree on a keyword (or perhaps a literary passage) whose letters told them how far forward or backward to shift the alphabet for every letter in the message. If the keyword “BIG” was used for example, the sender would code the message in sets of three letters. The first letter of the first trio would need to be shifted forward by one (since “B” is one letter after “A”), the second letter would need to be shifted forward by eight (“I” is eight letters after “A”), and the third letter would need to be shifted forward by six (“G” is six letters after “A”). After that, the pattern would repeat itself as in the following example:
Plaintext: THE BUTCHER THE BAKER AND THE CANDLESTICK MAKER
Key: BIG BIGBIGB IGB IGBIG BIG BIG BIGBIGBIGBI GBIGB
Ciphertext: UPK CCZDPKS BNF JGLMX BVJ UPK DITETKTBODS SBSKS
Knowing that “BIG” was the key, the recipient could easily decipher the message by shifting its letters back the corresponding amounts.
For many years Vigenère’s cipher was considered unbreakable, but Charles Babbage, an independently wealthy Englishman known mostly for his pioneering work in computer science, showed in the 1850s that it was not so. Babbage hacked the system by looking for repeated strings of letters. Of course, the strength of Vigenère’s cipher was supposed to be that it encoded letters differently in different places. The first “THE” in the message above is rendered as “UPK” and the second as “BNF”. Also, the two “AKER”s code differently. But the first and third “THE”s both code as “UPK.” The “T” in the first “THE” is coded with a “B,” and so is the “T” in the third “THE.” This happens because the third “THE” begins 21 letters after the first “THE”; hence the 3-letter keyword “BIG” has cycled around 7 times and is back to the beginning again.
In any message that is much longer than the key, some repeats of this sort are bound to occur. How would an eavesdropper exploit this fact? If, say, the ciphertext “UPK” appeared twice, 21 letters apart, then he could deduce that 21 was probably a multiple of the keyword’s length. Or to put it another way, the number of letters in the keyword was a divisor of 21. (A divisor or factor of a number is a number that goes into it with no remainder. The divisors of 21 are 1, 3, 7, and 21.)
Given enough clues of this sort, an eavesdropper could pin down the exact length of the keyword. Once he knew the length, he could do ordinary frequency analysis to decode the message. Notice that the math comes first: The eavesdropper figures out the length of the keyword before even attempting to figure out what its letters are.
Babbage’s ingenious technique broke new ground in cryptography, by introducing mathematical tools to a subject that previously had seemed to be about words. Even if an encryption system does not use mathematics explicitly, its hidden patterns can often be teased out that way. Mathematics is, after all, the science of patterns.
