A cryptographic top ten

Who doesn’t love a “top 10” list? Having just finished writing a cryptography textbook, here is my list of the top ten. It’s a very personal list, but inclusion on the list is based in part on importance, history, and new paradigms. (Really, they’re just personal favorites.) So, in roughly chronological order:

  1. The Caesar cipher. This is one of the earliest systems: every letter in the message is shifted forward by 3, so that “ATTACK TONIGHT” becomes “DWWDFN WRQLJKW”. It is supposed to have been used by Julius Caesar. This cipher is quite abstract – there is no requirement of any physical objects such as sticks or bones. At the time, 2000 years ago, it would have been quite secure.
  2. The Vigenère cipher. This was invented by Giovan Battista Bellaso in 1553, but has been consistently misattributed ever since to Blaise de Vigenère (1523–1596), who in fact developed an even stronger cipher. In any case, this particular cipher was a huge advance on previous ciphers. It works by the use of a keyword, repeated as many times as required to fill up the message. Then each letter in the message is shifted by an amount given by the keyword letter: A giving a shift of zero, B a shift of 1 etc. So strong was this cipher in comparison to previous ciphers that it was used for hundreds of years, and was considered to be unbreakable.
  3. The Playfair cipher. Another misnamed cipher, which was in fact invented by Charles Wheatstone in 1854. Unlike the above ciphers, this one works on pairs of letters, or “digraphs”. It is thus one of the earliest examples of a block cipher. It is surprisingly hard to break without a lot of ciphertext, and has been used seriously as recently as World War II, by the future US President, John Kennedy.

    Honorable runner-up: Félix Delastelle’s bifid cipher. I actually like this more than the Playfair cipher, but for some reason it never caught on, and has never been used for any serious purpose. Maybe what Delastelle lacked was a champion, like Baron Playfair for Charles Wheatstone’s cipher.

  4. The Hill cipher. Defined by mathematician Lester Hill in the late 1920’s, this was one of the first applications of mathematics to cryptography, rather than using tables of letters or of digraphs. Hill’s original description used a permutation of the alphabet as well as a matrix multiplication; this permutation is ignored by almost all modern writers.
  5. The Feistel construction. Horst Feistel, the German-born American cryptographer, considered the father of modern block cipher design, developed this construction as part of the definition of the Data Encryption Standard. It works like this: the current state is divided into left and right halves L_i and R_i. The right half is mixed with the current subkey k_i by a non-linear function f. Then:

    L_{i+1}=R_i

    R_{i+1}=L_ioplus f(R_i,k_i).

    The beauty of these equations is that they are invertible:

    R_i=L_{i+1}

    Latex L_i=R_{i+1}oplus f(L_{i+1},k_i).

    This is a really beautiful and elegant construction, and has been used in many other block ciphers since.

  6. The RSA cryptosystem. After Diffie and Hellman proposed the idea of public key cryptography, this was one of the first really powerful and useful such systems proposed. And after over 30 years, it still stands as one of the most efficient, strong, and elegant public-key systems of all, and is still much used. It marks a true paradigm shift in cryptography.
  7. El Gamal signatures. All public key systems can be turned around, so to speak, and used for digital signatures, but the system developed by Taher Elgamal is better than most. And it is the basis for the Digital Signature Standard.

    Honorable runner-up: Elliptic curve systems. These provide the same security as other public key systems, but with much smaller keys, at the cost of a little more mathematical sophistication.

  8. The Merkle–Damgård construction. For some reason cryptographic hash functions get short shrift by textbook writers, in spite of their immense importance to digital security. The Merkle–Damgård construction relates a hash function to a “compression function” which takes two inputs: current message block and current hash state, to produce a new state. Ralph Merkle and Ivan Damgård were able to prove that the strength and security of a hash function is entirely dependent on the security of the compression function.
  9. Brands’ digital cash. To create a digital cash protocol: creating a coin, obtaining a coin from the bank, spending a coin, all with appropriate security, Stefan Brands put together a whole lot of protocols and algorithms in an absolute tour-de-force of mathematical cryptography.

    Honorable runner-up: zero-knowledge proofs. To be able to prove to somebody that you are in possession of some fact (say, a factorization of a large integer), without giving anything away; that is, no information which will allow the “verifier” to factorize the integer, requires some wonderful cryptographic juggling. And the uses, for example identification, are numerous.

  10. The Boneh-Franklin identity-based encryption scheme. Public key systems work by first choosing a private key, and then using your private knowledge (prime factors of a large integer, for example) to compute your public key. “Identity-based encryption” (IBE) is a public key system for which something well known, such as your email address, is your public key. On the face of it this seems impossible – a contradiction in terms – and yet Dan Boneh and Matthew Franklin in 2001 developed a workable IBE scheme. Another brilliant cryptographic tour-de-force.

2 thoughts on “A cryptographic top ten

  1. My top ten are:

    Angus
    Edward
    Fenella
    William
    Finlay
    Bishop
    Hepsibah
    Zoltan
    Zadok
    Charlie and Snowy

    Okay – that’s really eleven, but if you divide by zero it all works out.

  2. That list of top 10 is fascinating! I can’t wait to get a chance to work through them in depth – apart from the Caesar cipher which I already know. I’m planning to put some examples perhaps of the TEA or TINY algorithms you have told me about on my website one day soon. I want to devise a short series of perhaps three lessons for A level students on cryptography, to be done in a computer lab.

Leave a Reply

Your email address will not be published. Required fields are marked *