CSEC3616Cybersecurity Engineering

    The Vigenère cipher and the Kasiski examination

    The Vigenère cipher encrypted and decrypted letter by letter on the lecture's own example, why a polyalphabetic cipher flattens ciphertext letter frequencies, and the Kasiski examination's repeat-distance reasoning worked from what the slides actually state.

    • Encrypt and decrypt using the Vigenère formula on the lecture's own worked example.
    • Explain why a polyalphabetic cipher flattens ciphertext letter frequencies compared to Caesar.
    • Recover a Vigenère key length from two repeat distances using the Kasiski examination.
    • State why the common factor across multiple repeat distances, not either distance alone, gives the most likely key length.

    20 min read

    Intuition

    Caesar’s fatal flaw is that it applies one substitution to the whole message, so the plaintext’s letter-frequency shape survives untouched into the ciphertext. The Vigenère cipher fixes this by cycling through several different Caesar shifts across the message, one per letter of a repeating key, so the same plaintext letter can land on different ciphertext letters depending on where it falls.

    Mechanism

    Vigenère is a poly-alphabetic cipher: each plaintext character is encrypted with a different Caesar cipher, and which Caesar cipher applies is decided by the corresponding letter of the key, cycled to match the length of the plaintext. Assigning each letter A-Z the numeric value 0-25 gives the formula below.

    Formula

    Vigenère encryption and decryption

    Ci=(Pi+Ki mod L) mod 26,Pi=(Ci−Ki mod L+26) mod 26C_i = (P_i + K_{i \bmod L}) \bmod 26, \qquad P_i = (C_i - K_{i \bmod L} + 26) \bmod 26
    Pi,CiP_i, C_i
    the numeric value of the i-th plaintext and ciphertext letter
    KjK_j
    the numeric value of the j-th letter of the key
    LL
    the length of the key

    i mod L cycles the key to match however long the plaintext is.

    Worked example

    AnswerTHISISAGREATDAY, key CRYPTO -> VYGHBGCXPTTHFRW

    The lecture’s own example: key CRYPTO, plaintext THISISAGREATDAY. The key repeats to match the plaintext’s length: C R Y P T O C R Y P T O C R Y.

    1. T(19) + C(2) = 21 mod 26 = 21 -> V
    2. H(7) + R(17) = 24 mod 26 = 24 -> Y
    3. I(8) + Y(24) = 32 mod 26 = 6 -> G
    4. S(18) + P(15) = 33 mod 26 = 7 -> H
    5. I(8) + T(19) = 27 mod 26 = 1 -> B
    6. S(18) + O(14) = 32 mod 26 = 6 -> G
    7. A(0) + C(2) = 2 mod 26 = 2 -> C
    8. G(6) + R(17) = 23 mod 26 = 23 -> X
    9. R(17) + Y(24) = 41 mod 26 = 15 -> P
    10. E(4) + P(15) = 19 mod 26 = 19 -> T
    11. A(0) + T(19) = 19 mod 26 = 19 -> T
    12. T(19) + O(14) = 33 mod 26 = 7 -> H
    13. D(3) + C(2) = 5 mod 26 = 5 -> F
    14. A(0) + R(17) = 17 mod 26 = 17 -> R
    15. Y(24) + Y(24) = 48 mod 26 = 22 -> W

    Ciphertext: VYGHBGCXPTTHFRW.

    Worked example

    AnswerVYGHBGCXPTTHFRW, key CRYPTO -> THISISAGREATDAY

    Decryption reverses the same table, subtracting the key value instead of adding it.

    1. V(21) - C(2) = 19 mod 26 = 19 -> T
    2. Y(24) - R(17) = 7 mod 26 = 7 -> H
    3. G(6) - Y(24) = -18 mod 26 = 8 -> I
    4. H(7) - P(15) = -8 mod 26 = 18 -> S
    5. B(1) - T(19) = -18 mod 26 = 8 -> I
    6. G(6) - O(14) = -8 mod 26 = 18 -> S
    7. C(2) - C(2) = 0 mod 26 = 0 -> A
    8. X(23) - R(17) = 6 mod 26 = 6 -> G
    9. P(15) - Y(24) = -9 mod 26 = 17 -> R
    10. T(19) - P(15) = 4 mod 26 = 4 -> E
    11. T(19) - T(19) = 0 mod 26 = 0 -> A
    12. H(7) - O(14) = -7 mod 26 = 19 -> T
    13. F(5) - C(2) = 3 mod 26 = 3 -> D
    14. R(17) - R(17) = 0 mod 26 = 0 -> A
    15. W(22) - Y(24) = -2 mod 26 = 24 -> Y

    Plaintext recovered: THISISAGREATDAY.

    Exam detail

    This is why a polyalphabetic cipher resists frequency analysis so much better than Caesar. Look at the letter I in the plaintext above: it appears at position 3 and position 5, but the key letter at those positions differs (Y and T), so the two occurrences encrypt to different ciphertext letters, G and B. Under Caesar, every occurrence of I would encrypt to the same letter, every time. With the key cycling through several different shifts, a single plaintext letter no longer maps to one fixed ciphertext letter, and a ciphertext letter-count no longer points at a single dominant peak the way it does under a monoalphabetic cipher. The distribution flattens because what used to be one substitution rule is now, effectively, several running at once.

    Classical cipher workbench

    Encrypt or decrypt with Caesar, Vigenere or rail fence, then read the ciphertext's letter frequencies and Kasiski trigram gaps.

    Result

    Letter frequency of the current ciphertext (bars) vs English (dashed line)

    Kasiski examination

    SequencePositionsGaps

    Mechanism

    If the key length is already known, Vigenère degrades back into several separate Caesar ciphers running side by side. Splitting the ciphertext by position modulo the key length groups together every letter that was encrypted by the same key character. Each of those groups is a plain Caesar shift, and ordinary frequency analysis recovers one key letter at a time: find the ciphertext letter that occurs most often within a group, assume it stands for the plaintext’s most common letter, and solve for the shift that connects them. Repeat once per key position.

    Aside

    The lecture’s own worked step through this method is hard to follow exactly as printed. The equation it gives for recovering the first key character does not fully reconcile with the letter values it names, reading like a term dropped somewhere in extraction from the original PDF. The paragraph above states the same reasoning in a form that checks out: assume the most frequent ciphertext letter in a position-group stands for the plaintext’s most frequent letter, and solve for the key letter that connects the two.

    Mechanism

    Not knowing the key length at all is the normal case, and trying every plausible length by hand is slow. The Kasiski examination shortcuts this. Natural language repeats itself: the word “the” recurs constantly in English, and a short Vigenère key means the same stretch of plaintext will occasionally line up with the same stretch of key more than once. When that happens, the ciphertext repeats too, at a gap that is a multiple of the key length. Search the ciphertext for repeated sequences, note the distance between each repeat, and the greatest common factor across those distances is the most likely key length.

    Aside

    The lecture does not print a full worked Kasiski example, a step-by-step search through an actual ciphertext for its repeated sequences and their positions. It links out to an external walkthrough (crypto.interactive-maths.com) for that, and gives only the final distances from its own example below. What follows is the reasoning worked from exactly what the lecture states: the plaintext, the key, and the two distances it reports, not a reconstruction of the missing step.

    Worked example

    AnswerDistances 33 and 27 -> most likely key length 3

    The lecture’s example: plaintext THE BELOW IS AN EXAMPLE FOR KASISKI TEST. THE TEXT IS ENCRYPTED UTILISING THE VIGENERE CIPHER., encrypted with the repeating key KEY. It reports the first three repeats found in the resulting ciphertext at these distances apart:

    1. Distance between the 1st and 2nd repetition: 33. Factors of 33: 1, 3, 11, 33; the key length must be one of these.
    2. Distance between the 2nd and 3rd repetition: 27. Factors of 27: 1, 3, 9, 27; the key length must also be one of these.
    3. Common factors of 33 and 27: 1 and 3.
    4. Discard 1: a one-character key is trivial to brute-force and is never treated as a real candidate.
    5. The remaining common factor is 3, so the most likely key length is 3.

    This matches the actual key, KEY, which is three letters long.

    Exam detail

    The general rule behind step 3: with more than two repeated patterns, take the greatest common divisor across all of the observed distances, not just one of them. A single repeat distance only tells you that the key length divides that number; it takes a second, independent repeat to narrow the candidates down to one likely answer.

    Threat

    The Kasiski examination turns “guess the key length” from an open-ended search into a small set of candidates. Once a likely key length is known, the ciphertext splits into that many separate Caesar-shift groups, each breakable by ordinary frequency analysis. Recovering the full key still involves some guesswork and trial and error, but the search space has collapsed from “every possible length” to a handful of common factors.

    Control

    The only real fix is to remove the repetition Kasiski depends on entirely: a key at least as long as the message, used once and never reused. That is precisely the condition the next topic’s one-time pad imposes, and precisely why a repeating-key one-time pad can be broken the same way a repeating-key Vigenère can.

    Pitfall

    Do not read a single repeat distance as the key length itself. A distance of 33 only says the key length divides 33: it could be 1, 3, 11 or 33. It takes the common factor across at least two independent repeats to narrow that down to one strong candidate.

    Recall

    Why does finding one repeated ciphertext sequence with a gap of 33 not, by itself, tell you the key length?

    Because 33 only bounds the key length to one of its factors (1, 3, 11 or 33), it does not pick out which one. A second repeat at a different distance, and the factor the two distances share, is what narrows the field down to a single likely answer.

    Source

    Week 4 notes PDF