如何使用Java优雅的破解维吉尼亚密码

对包括维吉尼亚密码在内的所有多表密码的破译都是以字母频率为基础的，但直接的频率分析却并不适用。例如，如果P是密文中出现次数最多的字母，则P很有可能对应E（前提是明文的语言为英语）。原因在于E是英语中使用频率最高的字母。然而，由于在维吉尼亚密码中，E可以被加密成不同的密文，因而简单的频率分析在这里并没有用。破译维吉尼亚密码的关键在于它的密钥是循环重复的。如果我们知道了密钥的长度，那密文就可以被看作是交织在一起的凯撒密码，而其中每一个都可以单独破解。使用卡西斯基试验和弗里德曼试验来得到密钥的长度。

package cn.tellyouwhat;

import java.util.*;

/**
 * @author harbo
 */
public class Decryption {

    //密文
    private static final String CIPHER = "OCWYIKOOONIWUGPMXWKTZD" +
            "WGTSSAYJZWYEMDLBNQAAAVSUWDVBRFLAUPLOOUBFGQHGCSCMGZL" +
            "ATOEDCSDEIDPBHTMUOVPIEKIFPIMFNOAMVLPQFXEJSMXMPGKCCAY" +
            "KWFZPYUAVTELWHRHMWKBBNGTGUVTEFJLODFEFKVPXSGRSORVGTAJ" +
            "BSAUHZRZALKWUOWHGEDEFNSWMRCIWCPAAAVOGPDNFPKTDBALSISU" +
            "RLNPSJYEATCUCEESOHHDARKHWOTIKBROQRDFMZGHGUCEBVGWCDQXG" +
            "PBGQWLPBDAYLOOQDMUHBDQGMYWEUIK";
    //英文字母频率数组
    private static final double[] FREQUENCIES = {8.167, 1.492, 2.782, 4.253, 12.702,
            2.228, 2.015, 6.094, 6.966, 0.153,
            0.772, 4.025, 2.406, 6.749, 7.507,
            1.929, 0.095, 5.987, 6.327, 9.056,
            2.758, 0.978, 2.360, 0.150, 1.974,
            0.074};

    /**
     * 通过右移密文，比较密文相同出现的次数，判断密钥的长度
     * 此方法输出提示信息，由用户来判断<br/>
     * <code>具体判断方式为，重合次数最多的那几次挪动的次数的最小公因数，一般就是密钥的长度</code>
     *
     * @param cipher 密文
     */
    private static void move(char[] cipher) {
        for (int j = 0; j < 26; j++) {
            int counter = 0;
            for (int i = 0; i < cipher.length; i++) {
                if (cipher[i] == cipher[(i + j) % cipher.length]) {
                    counter++;
                }
            }
            System.out.println("第" + j + "次挪动，" + counter + "个重合");
        }
    }

    /**
     * upper case litters only
     *
     * @param cipher upper case litters only
     * @return return the plaintext
     */
    public static String decrypt(String cipher) {
        //密钥
        StringBuilder key = new StringBuilder();
        char[] charArray = cipher.toCharArray();

        move(charArray);

        //读入用户判断的密钥长度
        Scanner scanner = new Scanner(System.in);
        System.out.print("Please input the most likely keyLength based on the tips above: ");
        int keyLength;
        try {
            keyLength = scanner.nextInt();
        } catch (InputMismatchException e) {
            throw new RuntimeException("你只能输入一个整数");
        }

        //划分为若干子串
        List<char[]> groups = divideIntoGroups(charArray, keyLength);

        //对于每一个子串，分别求他们的密钥字符
        for (char[] group : groups) {
            //分析子串的频数信息
            Map<Character, Integer> count = countAnalysis(group);
            //寻找该子串的密钥字符
            char aKey = findKey(count);
            key.append(aKey);
        }
        System.out.println("可能的k密钥是：" + key.toString());
        return decryptWithKey(cipher, key.toString());
    }

    /**
     * 利用基本的数学方法还原密文
     *
     * @param cipher 密文
     * @param key    密钥
     * @return 原文plaintext
     */
    private static String decryptWithKey(String cipher, String key) {
        char[] cipherArray = cipher.toCharArray();
        char[] keyArray = key.toCharArray();
        StringBuilder plaintext = new StringBuilder(314);
        for (int i = 0; i < cipherArray.length; i++) {
            char originChar = (char) (
                    (((cipherArray[i] - 65) - (keyArray[i % 6] - 65)) + 26) % 26 + 65);
            plaintext.append(originChar);
        }
        return plaintext.toString();
    }

    /**
     * 通过英文字母出现的频率，利用乘法，求出最有可能的密钥字符
     *
     * @param count 频数信息（各个字母出现的次数）
     * @return 最有可能的密钥字符
     */
    private static char findKey(Map<Character, Integer> count) {
        double maxProb = Double.MIN_VALUE;
        int bestI = 0;
        for (int i = 0; i < 26; i++) {
            double currentProb = 0;
            //累加概率
            for (int j = 0; j < 26; j++) {
                currentProb += FREQUENCIES[j] * count.get((char) (65 + (j + i) % 26));
            }
            if (currentProb > maxProb) {
                maxProb = currentProb;
                bestI = i;
            }
        }
        return (char) (bestI + 65);
    }

    /**
     * 对子串进行频数分析，得出A~Z出现的次数
     *
     * @param charArr 子串
     * @return 返回一个map，利用A~Z的字符作为key，value为该字符在子串中出现的次数
     */
    private static Map<Character, Integer> countAnalysis(char[] charArr) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        //利用char和int可以互转的技巧遍历
        for (int i = 65; i <= 90; i++) {
            char target = (char) i;
            int counter = 0;
            for (char ch : charArr) {
                if (ch == target) {
                    counter++;
                }
            }
            map.put(target, counter);
        }
        return map;
    }

    /**
     * 根据用户的输入，把密文分为密钥长度个子串
     * <p>如1,6,12；2,7,13；3,8,14。。。</p>
     *
     * @param charArray 密文
     * @param keyLength 密钥长度
     * @return 密文的各子串List
     */
    private static List<char[]> divideIntoGroups(char[] charArray, int keyLength) {
        ArrayList<char[]> list = new ArrayList<>();
        for (int i = 0; i < keyLength; i++) {
            int j = i;
            StringBuilder sb = new StringBuilder();
            while (j < charArray.length) {
                sb.append(charArray[j]);
                //j的跳跃宽度是密钥的长度
                j += keyLength;
            }
            list.add(sb.toString().toCharArray());
        }
        return list;
    }

    public static void main(String[] args) {
        System.out.println(decrypt(CIPHER.toUpperCase()));
    }
}