Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I read the $K$-Friedman test to determine the period of a Vigenère ciphertext, and I understand something like this:
$K$-Friedman test tries to find out what period of the cipher by calculating some values of $K(C,C^n)n$, where $C^n$ is the ciphertext with $n$ shifts to the left, thereby determining the most likely value of the cipher.
But deep down, what the Friedman Test does? Overlaps two texts and see coincident indexes? Can anybody explain this method better?
Just for simplicity lets assume that your short period "password" was just XORed with plaintext. So we have encryption procedure like:
for(int i = 0; i < plaintext_len; i++){
ciphertext[i] = plaintext[i] ^ password[i % password_len];
}
When you shift your ciphertext by password_len and XOR it with original ciphertext, you'll cancel out your password and get XOR of original plaintext and shifted version of plaintext.
ciphertext[i] ^ ciphertext[i + password_len] =
plaintext[i] ^ password[i % password_len] ^ plaintext[i + password_len] + password[ (i + password_len) % password_len] =
plaintext[i] ^ plaintext[i + password_len]
Note that if you have a 0 char in the result, than the corresponding symbols in plaintexts are equal. The probability of such event for natural text is far from uniform and depends on plaintext language (for English it's 0,0644). If the period guess is wrong, the probability that a particular character in the result is 0 equals $1/m$ where $m$ is the number of symbols in your alphabet, for English it's about 0,03856.
So, you've got the rule how to decide on whether period guess is correct or wrong - just shift ciphertext, XOR it with original one, calculate the frequency of zeroes. If it's close to 0,0644 - your guess is likely to be correct, it it's close to 0,03856 - your guess is hardly correct.
