Finding the key length of a Vigenere cipher when it is even

76 views Asked by At

I am programming an automatic Vigenere Cipher decoder using a frequency analysis. To be able to do that, I need the length of the key used. I am programming in Java.

My program works perfectly fine, but only with key lengths that are prime numbers. Example: The key has a length of 6. My program detects a key length of 3, as it is the smallest factor.

My input would look like this: [196, 231, 15, 67, 93, 26]. These are the distances between matching substrings in the ciphered text. These are only example numbers, not sure if they would work. The output should be a single number, the key length associated to the numbers.

This is my code for determining the key length:

public class LengthDeterminer {
     public static int getLength(int[] matchDistances) {
         if (matchDistances == null) return -1;
         Map<Integer, Integer> factorsToOccurency = factorsToOccurency(matchDistances); // Collect factors with occurency count
         if (VigenereDecipher.debugMode()) {
             System.out.println(factorsToOccurency);
         }
         return Collections.max(factorsToOccurency.entrySet(), Map.Entry.comparingByValue()).getKey();

    }

    private static Map<Integer, Integer> factorsToOccurency (int[] matchDistances) {
        Map<Integer, Integer> returnMap = new HashMap<>();

        for (int i = 0; i < matchDistances.length; i++) { 

            if (matchDistances[i] <= 1) continue; // Negative distances would only double every number, maybe a problem of a other part of my program

            int smallFactor = smallestFactor(matchDistances[i]);

            if (returnMap.containsKey(smallFactor)) {
                returnMap.put(smallFactor, returnMap.get(smallFactor) +1);
            } else {
                returnMap.put(smallFactor, 1);
            }
        }

        return returnMap;

    }

    private static int smallestFactor(int x)
    {
        if(x < 1)  return -1;
        if(x == 1) return  1;

        for(int i=3; i<=x; i++)
            if(x % i == 0)
                return i;

        return -1; // To stop compiler's complaints.
    }
}

The getLength() class is the one being initially called. I input the distances between matching substrings in the ciphered text. When using non-prime keys it doesnt work, it just spits out the smallest prime factor of the key length.

Can anybody help me?

0

There are 0 answers