(C) Daily Kos
This story was originally published by Daily Kos and is unaltered.
. . . . . . . . . .



Hidden History: The Vigenere Cipher [1]

['This Content Is Not Subject To Review Daily Kos Staff Prior To Publication.']

Date: 2025-02-18

The Vigenere Cipher is an encryption system that was developed over 500 years ago, and a variant of it was still being used by Soviet KGB spies in the 1950s.

"Hidden History" is a diary series that explores forgotten and little-known areas of history.

Vigenere cipher wheel

Ever since people have been writing, they have been searching for ways to make their written messages secure. This has historically been most important for military orders, diplomatic communications, and clandestine conspirators or resistance networks.

In the first century BCE, Julius Caesar encrypted his military communications using a system that is today referred to as a “single substitution cipher”. For each letter in his written message (known as the “clear text”), he would substitute another letter that was a specified number of letters away (known as the “cipher text”). For example, if he wanted to send the message “attack at dawn” and the agreed-upon system was to use the third following cipher letter for each clear, he would send the message “DWWDFN DW GDZQ”. The receiver would then decipher the message by counting back three letters from the ciphertext to obtain the clear message.

But the “Caesar Cipher”, as it became known, had severe weaknesses. Clear text words with spaces and doubled letters (such as “attack”) would retain these patterns when ciphered, making it easier to guess what the actual message said. And since each clear letter was always enciphered by the same cipher letter, the system was vulnerable to a “frequency analysis”, in which the number of occurrences of each letter would be counted and tabulated. By assuming that the most frequently-appearing cipher letters would correspond to the most frequent letters in the English language (e,t,a,o,n,i,s,h), one can break the cipher scheme and work out the entire message.

In the middle of the 15th century CE, a Catholic Church official named Giovan Battista Bellaso, working in the Lombardy province of Italy, made a significant improvement on the Caesar cipher. Bellaso’s system was “polyalphabetic”, in which each letter of the clear message could be encrypted with a different alphabet. This was done using a “key text”, a string of letters or words that had been agreed upon by the correspondents, and a table of 26 alphabetical rows, each shifted by one letter:

Polyalphabetic table

Now, each letter of the clear message was enciphered using a different alphabet, determined by the key text. For example, to encipher the clear message “attack at dawn” with the key text “dog”, we look for the first letter of the clear message (“a”) in the “clear” row across the top of the table, and the first letter of the key text (“d”) in the “key” column at the left edge, and find our cipher letter where the two intersect (which would be “d”). Continuing the process, we then encipher the next letter of the clear message with the next letter of the key text, repeating the key text as many times as necessary for the entire length of the message.

We get the cipher text ”DHZDQQ DH JDKT”. Note that the doubled letters are now obscured, and each “t” is enciphered by a different letter. This can be further obscured by eliminating the spacing between words and using five-letter blocks instead. So the ciphered message we would send is “DHZDQ QDHJD KTJDY” (the letters tacked on to the end are “nulls”—they are meaningless and are there simply to complete the five-letter block). This method defeats the “frequency analysis”, since there is no longer a one-to-one correspondence between clear letters and cipher letters.

The “polyalphabetic” system was further modified in the late 16th century by a Frenchman named Blaise de Vigenere, and today the system is known as the “Vigenere Cipher”, even though he didn’t invent it. His contribution was to introduce the concept of an “auto-key”, in which the first letter of the clear text is encrypted using any single agreed-upon key letter, and then the resulting cipher letter is used as the key to encrypt the next letter of the clear text, and so on and so on. This has the advantage that the sender and receiver only have to remember the single key letter that is used to begin the process, and the key did not repeat for its entire length. But there is a crushing weakness in the auto-key: because each step is dependent upon the previous step, if a mistake is made in the encryption or decryption and a letter is lost or an incorrect letter inserted, all of the message after this error will become unreadable gibberish.

Because of this issue, the French Army rejected Vigenere’s auto-key system, but simplified the polyalphabetic process by introducing a mechanical device—the cipher wheel—consisting of two concentric disks, each with a full alphabet and the numbers 1 through 0. It is sometimes called the St Cyr Wheel, after the French military academy.

To use the Vigenere cipher wheel, we turn the inner disc until the first letter of the key text is aligned with the “a” on the outer plaintext wheel, then we look for the first letter of the plain text on the outer disc, and cipher it with the corresponding letter on the inner disc.

Aligning the wheel with the first letter of the key text

We continue by turning the inner disc to align the next letter of the key text with the outer “a” and looking for the next letter of the plain text on the outer disc to find the corresponding cipher.

Aligning the second letter of the key text

At the end, using our previous “attack at dawn” message and the key text “dog”, we have the cipher text “D8ZDQ QD8JD AT8R4” (with nulls at the end).

To decipher, we align each letter of the key text, and search for the cipher letter on the inner disc to find the clear text letter on the outer.

The Vigenere system remained secure until the 19th century, when it was cracked by a Prussian military officer named Friedrich Kasiski. Kasiski found that if the key text used for a Vigenere cipher was repeated, he could look for duplicated segments within the encryption and use them to make a series of educated guesses until he hit upon the correct length that matched the key text, allowing him to transform the ciphered message into a series of single-substitution Caesar ciphers which could be defeated using frequency analysis. And the shorter the keyword or key phrase is, the easier it is to identify repeats.

To combat this “Kasiski analysis”, cryptographers began using very long texts, such as printed books, as their key. This, however, also proved to be vulnerable to attack, since each message that was sent would use the same repeated key text—thus, each letter of the plain text was always encrypted with the same corresponding letter of the cipher text. Given enough messages to work with, a codebreaker would be able to form a series of single-substitution columns which could then be solved with frequency analysis, and identify the words in the key text. In addition, a German professor named Auguste Kerckhoff also found a mathematical way to extract short repeated sequences from inside the cipher text, which would allow him to eventually identify the key text that was being used and break the code.

Kerckhoff’s success led to yet another modification: the one-time pad.

Contrary to popular belief, there is indeed a pen-and-paper cipher system that is completely unbreakable by any cryptological method, including attacks by NSA’s supercomputers. This method depends upon using a key text that (1) does not repeat, (2) is completely random, and (3) is only used once. That is the essence of the one-time pad. This system was used by Soviet KGB spies in the US during the 1950s.

At the center of this system is the “pad”. This is simply a booklet that contains page after page of random letters and numbers in blocks of five, with no structure or repeated segments, which can be used as the key text for encrypting a message. Each message uses as many pages as needed from the pad, in order: this insures that the sender and receiver are both using the same pages for encryption and decryption. And once each page has been used for a message, it is destroyed and never used again.

Sample one-time pad key groups

Now, encrypting our clear text “attack at dawn” with this one-time key, we get the cipher text “Z0PM0 EVUGJ M7F49”. We then destroy that page of key text so it cannot be used again. Likewise, the recipient destroys his copy of that page after decrypting.

If used properly, the system cannot be broken from the outside. Because it is polyalphabetic it is not subject to frequency analysis, and because the key does not repeat and has no internal structure it is not vulnerable to Kasiski or Kerckhoff analysis. Even a brute-force computer attack will not be successful—because the relationship between plain text and cipher text is completely random, the computer will simply spit out every possible combination of letters that can fit into the allotted length.

In every instance in which a one-time pad system has been broken (such as the “Venona” intercepts) it was because the sender or receiver made a mistake in procedure that ruined the security of the system (most often by using the same key text twice).

But even the one-time pad system has a weakness—though the flaw is logistical in nature, not cryptological. In order to communicate securely, both the sender and receiver must have copies of the same identical pads, and that presents security issues during distribution. The Soviets used a system of couriers and “dead drops” to distribute new or replacement cipher pads to all of their operatives in the field, leading to a number of them being detected and captured. On the whole, however, the system worked well, and many of the old Soviet encryptions have still not been broken.

[END]
---
[1] Url: https://dailykos.com/stories/2025/2/18/2303689/-Hidden-History-The-Vigenere-Cipher?pm_campaign=front_page&pm_source=more_community&pm_medium=web

Published and (C) by Daily Kos
Content appears here under this condition or license: Site content may be used for any purpose without permission unless otherwise specified.

via Magical.Fish Gopher News Feeds:
gopher://magical.fish/1/feeds/news/dailykos/

You are viewing proxied material from magical.fish. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.