Editing Vigenère cipher (section)

=== Kasiski examination ===
{{further|Kasiski examination}}

In 1863, [[Friedrich Kasiski]] was the first to publish a successful general attack on the Vigenère cipher.<ref>{{cite book|last1=Kasiski|first1=F. W.|title=Die Geheimschriften und die Dechiffrir-Kunst|trans-title=Cryptograms and the art of deciphering|date=1863|publisher=E.S. Mittler und Sohn|location=Berlin, (Germany)|url=https://books.google.com/books?id=fB5dAAAAcAAJ&pg=PP7|language=de}}</ref> Earlier attacks relied on knowledge of the plaintext or the use of a recognizable word as a key. Kasiski's method had no such dependencies. Although Kasiski was the first to publish an account of the attack, it is clear that others had been aware of it. In 1854, [[Charles Babbage]] was goaded into breaking the Vigenère cipher when John Hall Brock Thwaites submitted a "new" cipher to the ''Journal of the Society of the Arts''.<ref>See:
*  {{cite journal|last1=Thwaites|first1=J.H.B.|title=Secret, or cypher writing|journal=Journal of the Society of Arts|date=11 August 1854|volume=2|issue=90|pages=663–664|url=https://books.google.com/books?id=nxw9AQAAIAAJ&pg=PA663}}
*  {{cite journal|last1="C." (Charles Babbage)|title=Mr. Thwaites's cypher|journal=Journal of the Society of Arts|date=1 September 1854|volume=2|issue=93|pages=707–708|url=https://books.google.com/books?id=nxw9AQAAIAAJ&pg=PA707}}
*  {{cite book|last1=Babbage|first1=Charles|title=Passages from the Life of a Philosopher|date=1864|publisher=Longman|location=London, England|page=[https://archive.org/details/bub_gb_2T0AAAAAQAAJ/page/n509 496]|url=https://archive.org/details/bub_gb_2T0AAAAAQAAJ}}</ref><ref>Thwaites filed for a patent for his "new" cipher system:
*  [https://babel.hathitrust.org/cgi/pt?id=gri.ark:/13960/t4gn2h303;view=1up;seq=798 "Weekly list of patents sealed. … 1727. John Hall Brock Thwaites, Bristol – Improvements in apparatus to facilitate communication by cypher."] in: ''Journal of the Society of Arts'', '''2''' (99): 792 (13 October 1854).
*  [https://books.google.com/books?id=7xEFAAAAQAAJ&pg=PA211 "Thwaites, John Hall Brock, of Bristol, dentist. ''Improvements in apparatus to facilitate the communication by cypher''.  Application dated August 7, 1854. (No. 1727.)"] in:  ''The Mechanics' Magazine'', '''62''' (1647): 211 (3 March 1855).</ref> When Babbage showed that Thwaites' cipher was essentially just another recreation of the Vigenère cipher, Thwaites presented a challenge to Babbage: given an original text (from Shakespeare's ''[[The Tempest]]'': Act 1, Scene 2) and its enciphered version, he was to find the key words that Thwaites had used to encipher the original text. Babbage soon found the key words: "two" and "combined".  Babbage then enciphered the same passage from Shakespeare using different key words and challenged Thwaites to find Babbage's key words.<ref>See:
*  {{cite journal|last1=Thwaites|first1=John H.B.|title=Secret or cypher writing|journal=Journal of the Society of Arts|date=15 September 1854|volume=2|issue=95|pages=732–733|url=https://babel.hathitrust.org/cgi/pt?id=gri.ark:/13960/t4gn2h303;view=1up;seq=738}}
*  {{cite journal|last1="C" (Charles Babbage)|title=Mr. Thwaites's cypher|journal=Journal of the Society of Arts|date=6 October 1854|volume=2|issue=98|pages=776–777|url=https://babel.hathitrust.org/cgi/pt?id=gri.ark:/13960/t4gn2h303;view=1up;seq=782}}</ref> Babbage never explained the method that he used. Studies of Babbage's notes reveal that he had used the method later published by Kasiski and suggest that he had been using the method as early as 1846.<ref name="Franksen1985">{{cite book|author=Ole Immanuel Franksen|title=Mr. Babbage's Secret: The Tale of a Cypher and APL|url=https://books.google.com/books?id=53dQAAAAMAAJ|year=1985|publisher=Prentice Hall|isbn=978-0-13-604729-2}}</ref>

The [[Kasiski examination]], also called the Kasiski test, takes advantage of the fact that repeated words are, by chance, sometimes encrypted using the same key letters, leading to repeated groups in the ciphertext. For example, consider the following encryption using the keyword <code>ABCD</code>:

 Key:        '''''ABCDAB'''''CDABCDABCD'''''ABCDAB'''''CDABCD
 Plaintext:  '''''crypto'''''isshortfor'''''crypto'''''graphy
 Ciphertext: '''''CSASTP'''''KVSIQUTGQU'''''CSASTP'''''IUAQJB

There is an easily noticed repetition in the ciphertext, and so the Kasiski test will be effective.

The distance between the repetitions of <code>CSASTP</code> is 16. If it is assumed that the repeated segments represent the same plaintext segments, that implies that the key is 16, 8, 4, 2, or 1 characters long. (All [[factorization|factors]] of the distance are possible key lengths; a key of length one is just a simple [[Caesar cipher]], and its [[cryptanalysis]] is much easier.) Since key lengths 2 and 1 are unrealistically short, one needs to try only lengths 16, 8, and 4. Longer messages make the test more accurate because they usually contain more repeated ciphertext segments. The following ciphertext has two segments that are repeated:
 Ciphertext: {{color|light-dark(red, lightcoral)|'''''VHVS'''''}}SP{{color|light-dark(blue, lightblue)|'''''QUCE'''''}}MRVBVBBB{{color|light-dark(red, lightcoral)|'''''VHVS'''''}}URQGIBDUGRNICJ{{color|light-dark(blue, lightblue)|'''''QUCE'''''}}RVUAXSSR
The distance between the repetitions of <code>VHVS</code> is 18. If it is assumed that the repeated segments represent the same plaintext segments, that implies that the key is 18, 9, 6, 3, 2, or 1 characters long. The distance between the repetitions of <code>QUCE</code> is 30 characters. That means that the key length could be 30, 15, 10, 6, 5, 3, 2, or 1 characters long. By taking the [[intersection (set theory)|intersection]] of those sets, one could safely conclude that the most likely key length is 6 since 3, 2, and 1 are unrealistically short.<!-- the key is CARBON and the message is THERECOULDYETBEANOTHERGEOGRAPHERWHOWOULDDISAGREE -->