3
$\begingroup$

I'm trying to write a Vigenere decipher script. I defined a couple of possible keylengths using the Kasiski method, using roughly this method:

  • find recurring strings in the ciphertext between 3 and 12 characters
  • make a list of the distances between them
  • loop through the list of distances and calculate the greatest common denominator between each distance[n] and distance[n+1]
  • count the GCDs and send the top 3 to the Friedman function

In the Friedman function:

For each of the GCDs (= possible keylengths) that my Kasiski function returns I calculate the IC, but sometimes a multiple of the keylength is closer to the standard English IC than the actual keylength. This is usually a difference of only 1-3%. Since I do not weigh them by the amount of times the keylength came out in the GCDs counter, it sometimes happens that for a key of 3 characters my function returns 6 as the most likely keylength.

My question is, should I:

  1. Preserve the amount of times a GCD was established between two distances in the Kasiski function, weighing the outcome of the Friedman function with it to prefer the most occurring GCD
  2. In the Friedman function, check if a possible keylength is a multiple of another possible keylength, comparing the ICs and discarding the multiple if the difference is (for example) less than a few %
  3. Both, neither, anything else?
Improve this question
$\endgroup$
4
  • $\begingroup$ Do you need a solution that is 100% automated (no human involvement), or are you OK with involving human judgement? If the latter, it seems pretty easy for a human to recognize this situation and choose the smaller keylength. $\endgroup$
    – D.W.
    Sep 30 '13 at 6:00
  • $\begingroup$ No, I definitely need an automated solution, that's the whole point of this script. (It's a programming excercise, but I'm getting stuck on the specifics of solving the vigenere code, not the coding itself) $\endgroup$
    – Stephan Muller
    Sep 30 '13 at 6:01
  • 1
    $\begingroup$ OK. I suspect, when the IC was invented, it was typically used together with human judgement, so there might not be any standard rules to address this issue. Anyway, it seems like it might be easy to add a special case for this situation: choose the one with the highest IC, except that if it has a divisor whose IC is within 5% of it, choose the divisor. Another plausible solution would be to try running the rest of your attack on both candidates. I would imagine either of these might work fine. Have you tried either of these approaches? $\endgroup$
    – D.W.
    Sep 30 '13 at 6:05
  • $\begingroup$ In the end it won't make a huge difference since a multiple of the key will still solve the encryption, I realised later. Afterwards I can always check if the key is repeating itself and then truncate it. I decided to go for 10%, that's a range of 0.0609 - 0.0767 which is still clearly around the English IC and far away from the .0038 for random text. If you put your comment in an answer I'll accept it! $\endgroup$
    – Stephan Muller
    Sep 30 '13 at 8:51
3
$\begingroup$

I suspect, when the IC was invented, it was typically used together with human judgement, so there might not be any standard rules to address this issue.

Anyway, it seems like there are two plausible solutions:

  1. It might be easy to add a special case for this situation: choose the keylength with the highest IC, except that if it has a divisor whose IC is within 10% of it, choose the divisor.

  2. Another plausible solution would be to try running the rest of your attack on both candidates.

I would imagine either of these might work fine.

Improve this answer
$\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.