Saturday, February 28, 2015

It's a secret (11)

The Vigenère cipher reigned supreme from around the mid-16th century to the mid-19th, and for much of that time was considered unbreakable.  But then Charles Babbage in England and Friedrich Kasiski in Prussia, working independently, showed that it could be broken.  It had been known for some time that if you knew the length of the keyword you could crack it.  Suppose you knew somehow that the keyword was seven letters long - you would take the ciphertext and write the numbers 1,2,3,4,5,6 and 7 above it over and over again.  You would now isolate all the ciphertext letters with a "1" written above them.  Now you would know that all these letters had been encrypted using the same letter - the first letter of the keyword, whatever that is.  In other words, it becomes a monoalphabetic cipher! And as such you can use frequency distribution to work out what that letter probably is.  Then do the same with all the letters with "2" above them, and so on. But how are you to find out the length of the keyword?  And this is where Babbage and Kasiski had their inspiration. They realised that, provided the ciphertext was of a reasonable length it was pretty well inevitable that sooner or later the same two or more letters of the keyword would coincide with the same two or more letters of the plaintext - thus producing the same two or more ciphertext letters. So they looked for repeating groups of letters in the ciphertext and counted how many letters apart these appeared.  Of course some of these might be simply coincidence, but those that are the result of the same letters of the keyword hitting the same letters of the plaintext will be a multiple of the length of the keyword apart.  And there you are.

No comments: