如何使用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()));
    }
}


   转载规则


《如何使用Java优雅的破解维吉尼亚密码》 Harbor Zeng 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
如何使用Java手写实现一个RSA加密算法 如何使用Java手写实现一个RSA加密算法
8到16位RSA实现RSA这种算法非常可靠,密钥越长,它就越难破解。 第一步,随机选择两个不相等的质数p和q。 第二步,计算p和q的乘积n。 第三步,计算n的欧拉函数φ(n)。 第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。 第五步,计算e对于φ(n)的模反元素d。 第六步,将n和e封装成公钥,n和d封装成私钥。 实现效果 代码密钥的父类: pub
2018-03-27
下一篇 
通过Xposed的hook机制探究加固的app的密码盐值实战 通过Xposed的hook机制探究加固的app的密码盐值实战
原文章发表在 https://www.jianshu.com/p/5cc402b67aaa 现在有了自己的静态博客,特意搬过来 1. 前言此文章仅适用于兴趣研究,不可作为损坏他人或其他机构等利益之用,本文只是提出一个设想,并不保证具有普适性 2. 开题对于安全来说,app是毫无安全性可言的。 不管您是用了proGuard来混淆app,还是用了360加固宝,腾讯加固,等加固产品,最终都会被以各种
2018-01-17
  目录