10
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I'm assuming you took a look at this section on Wikipedia's Vigenere cipher article about the test. The last paragraph, beginning with "A better approach..", to me seems to explain what you are looking for. $\endgroup$ – mikeazo Jan 4 '16 at 18:27
  • $\begingroup$ Yes is that section but I can't understand this. Can you give me an example more simple ? I can't undestand if two texts are overlaped and the function gives to us the index-of-coincidence. I'm very confused. $\endgroup$ – PRVS Jan 5 '16 at 10:23
  • $\begingroup$ Did you see this example (also on Wikipedia)? $\endgroup$ – mikeazo Jan 5 '16 at 12:41
  • $\begingroup$ Yes but I want to know if two texts are overlaped and the function gives to us the index-of-coincidence. I'm very confused. $\endgroup$ – PRVS Jan 9 '16 at 14:57
  • $\begingroup$ I suggest you to take a look at nku.edu/~christensen/1402%20Friedman%20test%202.pdf $\endgroup$ – Raoul722 Jun 3 '16 at 12:07
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.