Jumat, 16 Mei 2008

Great minds in Cryptography


There are many notable personalities who participated in the evolution of Cryptography. The Greek philosopher and writer Polybius arranged the alphabet into a squared grid or matrix. By numbering the rows and columns, letters could be transformed into other paired characters. The Polybius square's features of splitting a character into two parts, reducing the number of characters needed and ability to convert letters into numbers is still used in modern algorithms.

Julius Caesar used his famous substitution cipher (the 'Caesar Cipher'), which shifted each letter four places further through the alphabet. The first European manual on cryptography (c. 1379) was a compilation of ciphers by Gabriele de Lavinde of Parma, who served Pope Clement VII. This manual, now in the Vatican archives, contains a set of keys for 24 correspondents and embraces symbols for letters, nulls, and several two-character code equivalents for words and names.

The Italian architect and writer Leon Battista Alberti is known as "The Father of Western Cryptology" in part because of his development of polyalphabetic substitution. Polyalphabetic substitution is any technique which allows different ciphertext symbols to represent the same plaintext symbol. This makes it more difficult to interpret ciphertext using frequency analysis. He did this by designing a cipher disk to simplify the process (c. 1466-7). This class of cipher was apparently not broken until the 1800's. The next major step was taken in 1518, by Trithemius, a German monk. He wrote Polygraphia, the first printed work on cryptology. He devised a table that repeated the alphabet with each row a duplicate of the one above it, shifted over one letter.

The resulting series of words would be a legitimate prayer. He also described polyalphabetic ciphers in the now-standard form of rectangular substitution tables. He introduced the notion of changing alphabets with each letter. In 1553, Giovan Batista Belaso came up with the idea of the password. He chose a keyword that is written above the plaintext, in a letter-to-letter correspondence. The keyword is restarted at the beginning of each new plaintext word. The letter of the keyword above the letter of the plaintext is the first letter of the cipher line to be used. In other words, if the plaintext letter is 'c', and it's keyword letter is 's', then the line of the Trithemius cipher beginning with 's' is used to encipher the letter 'c'.

Giovanni Battista Porta wrote in 1563 a text on ciphers, introducing the digraphic cipher. He said that the three types of ciphers were transposition, substitution, and symbol-substitution (use of a strange alphabet).

The most famous cryptographer of the 16th century was Blaise de Vigènere (1523-1596). In 1585, he wrote Tracte des Chiffres in which he used a Trithemius table, but changed the way the key system worked. One of his techniques used the plaintext, as it's own key. Another used the ciphertext. Sir Francis Bacon celebrated bilateral cipher (1623) was an arrangement of the letters «a» and «b» in five-letter combinations, each representing a letter of the alphabet. This code illustrates the important principle that a code employing only two different signs can be used to transmit information.

The 'wheel cipher' was invented by Thomas Jefferson around 1795, and although he never did very much with it, a very similar system was re-invented for use in World War II by the US Navy, which then called it the Strip Cipher. Jefferson's wheel cipher consisted of twenty-six cylindrical wooden pieces, each threaded onto an iron spindle. The letters of the alphabet were inscribed on the edge of each wheel in a random order. Turning these wheels, words could be scrambled and unscrambled.

In 1859, Pliny Earle Chase, developed what is known as the fractionating or tomographic cipher. A two-digit number was assigned to each character of plaintext by means of a table. These numbers were written so that the first numbers formed a row on top of the second numbers. The bottom row was multiplied by nine, and the corresponding pairs are put back in the table to form the ciphertext.

The British scientist Sir Charles Wheatstone (1802-1875) developed the Playfair Code, a table system that was easy to use. Although not difficult to analyse, it did muddle character frequency techniques by the use of digraphs (coding two letters at a time).

Friedrich W. Kasiski developed a cryptanalysis method in 1863 which broke almost every existing cipher of that time. The method was to find repetitions of strings of characters in the ciphertext. The distance between these repetitions is then used to find the length of the key. This technique makes cryptanalysis of polyalphabetic substitution ciphers quite straight forward.

In 1883, the French teacher and writer Auguste Kerckhoffs wrote 'La Cryptographie Militaire' in which he set forth six basic requirements of cryptography. He formulated procedures for long-term diplomatic codes as well as inventing the superpositioning technique for code breaking.

In 1917, the Americans formed the cryptographic organization MI-8, with Herbert Osborne Yardley as the director. They analyzed all types of secret messages, including codes, secret inks and encryptions. They continued with much success during and after WW1. Yardley wrote a best seller, The American Black Chamber, describing the workings of MI-8. Another American, William Frederick Friedman, worked with his wife, Elizebeth Smith, and they became an important husband-and-wife team in the history of cryptology.

In 1929, Lester S. Hill published an article Cryptography in an Algebraic Alphabet in which a block of plaintext is enciphered by a matrix operation. Hill's major contribution was the use of mathematics to design and analyze cryptosystems.

Arthur Scherbius, inventor of the Enigma Machine, tried to sell it commercially, but he had no success with that. It was eventually taken over and improved by the German government who used it to encrypt military communications in World War II. It was broken by the Polish mathematician, Marian Rejewski, based only on captured ciphertext and one list of three months worth of daily keys obtained through a spy. Continued breaks were based on developments during the war by Alan Turing, Gordon Welchman and others at Bletchley Park in England (1933 - 1945). The British engineer Tommy Flowers built Colossus (the world's first programmable electronic computer) to also help Bletchley Park crack German codes.

The Japanese Purple machine was invented in response to revelations by Herbert O. Yardley and broken by a team headed by William Frederick Friedman. The Purple machine used telephone stepping relays instead of rotors and thus had a totally different permutation at each step rather than the related permutations of one rotor in different positions.

In 1948, Shannon published A Communications Theory of Secrecy Systems. Shannon was one of the first modern cryptographers to attribute advanced mathematical techniques to the science of ciphers. Although the use of frequency analysis for solving substitution ciphers was begun many years earlier, Shannon's analysis demonstrates several important features of the statistical nature of language that make the solution to nearly all previous ciphers very straight forward.

Dr. Horst Feistel led a research project at the IBM Watson Research Lab in the 1960's which developed the Lucifer cipher. In 1976, Whitfield Diffie and Martin Hellman published "New Directions in Cryptography", introducing the idea of public key cryptography. They also put forth the idea of authentication by powers of a one-way function. Inspired by the Diffie-Hellman paper and acting as complete novices in cryptography, Ronald L. Rivest, Adi Shamir and Leonard M. Adleman had been discussing how to make a practical public key system. They invented the RSA computer-encryption algorithm. RSA is a public key algorithm based on the difficulty of factoring large numbers.

The algorithm was published in the September 1977 issue of Scientific American. Even today, it is used to keep text secret. Pretty Good Privacy (PGP) was released in 1991 by American Phil Zimmerman. To this day, it is considered a very secure way of communication across the Internet. PGP employs a public key system so that the sender cannot determine the key used to decrypt the message, even if he knows the key for encrypting the message. PGP is designed so that it can be integrated into email packages, thus allowing it to be used by the average citizen.

1 komentar:

Amber Salm mengatakan...

Nice. This blog post helped me to learn so many interesting facts about cryptography. There are so many people who gave their valuable contribution in the popularity of this great security technique. I am fortunate to know about them with the help of your blog.
digital signature software