Skip to main content

Posts

Showing posts from May, 2015

The effectiveness of Turing's Vigenère cipher breaking technique

In Turing's paper The Applications of Probability to Cryptography he describes a technique for breaking the Vigenère Cipher using Bayes Theorem. The paper was declassified in 2012 and a computer typeset version has been released (Turing used a typewriter and pen to produce the original). Having used Bayes Theorem quite a few times (for example in POPFile ) I was interested to see how it was being applied to Vigenère by Turing. Bayes Theorem is surprisingly powerful even when great simplifications (such as assuming, for example, independence of the occurrence of words or letters in an English sentence: something that's clearly not the case). Briefly Turing's technique is to use Bayes Theorem to 'weigh the evidence' that each of the 26 letters of the alphabet could be one of the letters in the key and output weights for each letter. His technique outputs weights for each letter in each position in the key and by picking the most likely it's possible to have