基于频率分析的Vigenere破解

Vigenere密码简介:

信息代码:X=(x1,x2,…,xd)∈(Z/26)d

密钥:K=(k1,k2,…,kd) ∈(Z/26)d

加密函数:E(x)=X+K=( x1+k1,x2+k2,…,xd+kd);

解密函数: D(x)=X-K=( x1-k1,x2-k2,…,xd-kd);

其实，vigenere密码本身也是一种凯撒挪移密码，但是比起凯撒密码，这个密码存在比较难确定的两个因素:区域长度d的选定和密钥K向量;但是，这种密码并非不可破解，而且破解思路也比较简单(如果不深究其中深刻的数学原理)，接下来给出破解思路和代码实现:

          一些公用代码:

求模函数:

public class OperationUtil {
      /**
        * @param start
        * @param end exclude
        * @param result
        * @return
        */
      public static int mod(int start,int end,int result) {
            int res;
            int difference=end-start;
            int resultFromStart=result-start;
            res=start+resultFromStart%difference;
            while(res<start) {
                    res+=difference;
            }
            return res;
}

      //把文本text分成""+text[0]+text[0+keyLength]...+,""+text[1]+text[1+keyLength]+...,..如
      //此分组
      public static ArrayList<String> groupText(String text, int keyLength) {
            ArrayList<String> groups = new ArrayList<String>();
            for (int i = 0; i < keyLength; ++i) {
                    StringBuilder tempGroup = new StringBuilder();
                    for (int j = 0; i + j * keyLength < text.length(); ++j) {
                          tempGroup.append(text.charAt(i + j * keyLength));
                    }
                    groups.add(tempGroup.toString());
            }
            return groups;
      }

      /**
        * 计算密文字母频率向量和统计字母使用频率向量左旋g的内积
        * @param frequencies
        *            密文字母频率
        * @param w
        *            统计字母使用频率
        * @param g
        *            左旋步长
        * @param subTextLength
        *            区域段密文长度
        * @return 拟重合指数
        */
      public static double transvection(Map<Character, Integer> frequencies, double[] w, int g, int subTextLength) {
            double MG = 0.0D;
            for (char ch = 'A'; ch <= 'Z'; ++ch) {
                    // int的除法
                    double fi = frequencies.get(ch) * 1.0 / subTextLength;
                    int index = OperationUtil.mod(0, 26, ch - 'A' - g);
                    MG += fi * w[index];
            }
            return MG;
      }
      }

  吻合指数计算方法[图片来源《密码学--加密演算法》]

基于频率分析的Vigenere破解

      /**
        * 计算吻合指数
        * @param wordMap 字符频率映射表
        * @param textLength groupText产生每个分组的长度
        * @return
        */
      public static double calculateCoincidence(Map<Character, Integer> wordMap, int textLength) {
            double IC = 0.0D;
            double denominator = Math.pow((double) textLength, 2);
            for (int k = 0; k < 26; ++k) {
                    double frequency = (double) wordMap.get((char) (k + 65));
                    IC += frequency * (frequency - 1);
            }
            IC /= denominator;
            return IC;
      }

      /**
        * 统计每个字符出现次数
        * @param text groupText分组文本
        * @return
        */
      public static Map<Character, Integer> countEveryWord(String text) {
            Map<Character, Integer> map = new HashMap<>();
            for (int i = 0; i < 26; ++i) {
                    map.put((char) (i + 65), 0);
            }
            for (int i = 0; i < text.length(); ++i) {
                    char current = text.charAt(i);
                    int frenquency = map.get(current) + 1;
                    map.put(current, frenquency);
            }
            return map;
      }

          一、求出密钥的长度(区域长度d)

大致思路:在猜测最大密钥长度范围内找出平均重合指数最大的密钥长度

      /**
        * Friedman解密
        * @param text 密文
        * @param guess 猜测密钥最大长度
        * @return 密钥长度
        */
      public static int Friedman(String text,int guess) {
            // 重合指数
            double[] Ic = null;
            // 平均重合指数
            double avgIc = 0;
            // 密文分组
            ArrayList<String> groups=null;
            double max=0;
            int keyLength=0;
            // 可能密钥长度
            int possibleLength = 1;
            while (possibleLength<=guess) {
                    Ic = new double[possibleLength];
                    avgIc = 0;
                    // 1 先根据密钥长度分组
                    groups = groupText(text, possibleLength);
                    // 2 再计算每一组的重合指数
                    for (int i = 0; i < possibleLength; ++i) {
                          String subCipher = groups.get(i); // 子串
                          Map<Character, Integer> frequencies = countEveryWord(subCipher);
                          Ic[i] = calculateCoincidence(frequencies, subCipher.length());
                    }
                    for (int i = 0; i < possibleLength; ++i) {
                          avgIc += Ic[i];
                    }
                    avgIc /= (double) possibleLength;
                    //求最大重合指数
                    if (avgIc >= max) {
                          max=avgIc;
                          keyLength=possibleLength;
                    }
                    possibleLength++;
            }
            return keyLength;
      }

二、确定密钥

大致思路:因为字母移位周期为26，所以就相当于在26中寻找密文频率比例和字母统计频率内积值最大的就是密钥

      /**
        * 重合指数获取密钥
        * @param keyLength 密钥长度
        * @param text 密文
        * @return 密钥
        */
      public static int[] decryptCipher(int keyLength, String text) {
            int[] key = new int[keyLength];
            //字母常用频率分布表
            double[] probability = new double[] { 0.082, 0.015, 0.028, 0.043, 0.127, 0.022, 0.02, 0.061, 0.07, 0.002, 0.008,
                          0.04, 0.024, 0.067, 0.075, 0.019, 0.001, 0.06, 0.063, 0.091, 0.028, 0.01, 0.023, 0.001, 0.02, 0.001 };
            ArrayList<String> groups = groupText(text, keyLength);
            for (int i = 0; i < keyLength; ++i) {
                    double MG;
                    double maxMG=0;
                    for (int g=0;g<26;++g) {
                          MG = 0;
                          String subCipher = groups.get(i);
                          Map<Character, Integer> frequencies = countEveryWord(subCipher);
                          MG = transvection(frequencies, probability, g, subCipher.length());
                          if (MG >= maxMG) {
                                maxMG=MG;
                                key[i] = g;
                          }
                    }
            }
            return key;
      }

三、根据密钥得出明文

      public static String decrypt(String text,int[]keys) {
            StringBuilder plainText=new StringBuilder();
            for (int i=0;i<text.length();++i) {
                    plainText.append((char)OperationUtil.mod(65, 91, text.charAt(i)-keys[i%keys.length]));
            }
            return plainText.toString();
      }

四、测试文本

OCWYIKOOONIWUGPMXWKTZDWG

TSSAYJZWYEMDLBNQAAAVSUWD

VBRFLAUPLOOUBFGQHGCSCMGZ

LATOEDCSDEIDPBHTMUOVPIEK

IFPIMFNOAMVLPQFXEJSMXMPG

KCCAYKWFZPYUAVTELWHRHMWK

BBVGTGUVTEFJLODFEFKVPXSG

RSORVGTAJBSAUHZRZALKWUOW

HGEDEFNSWMRCIWCPAAAVOGPD

NFPKTDBALSISURLNPSJYEATC

UCEESOHHDARKHWOTIKBROQRD

FMZGHGUCEBVGWCDQXGPBGQWL

PBDAYLOOQDMUHBDQGMYWEUIK

密钥:7,14,11,12,4,18

真实密钥:7,14,11,12,4,10

最后一个误差可以通过考虑单词特征纠错