Vigenere cipher text：
ivikdkdqmjglpwlzgmpfbjiidbbysljdxfgbiwwehapheysgnccyootstzabcobvrtazeywvwwazaidgazpethpvbpwobvjxgfmdobcgpfkxkszzaigcjrpetacjhuthpvhkjhpzhfpmevzeqsbyomhsdvftasfgztcobzcghfmdobcwvnvbrvkrgxdbmkfbtgbvgmptbvfmtgblbmxzweshgcbyskdtbysfwoarqhcjqeqbcuidcnchwwgnedwihptkqczgdkigdenhpzgigwvtwiasbfhatqijsbcdwzbmpgqkkthtqigmefmjsgislkcfthpvfxlszvhagsmgclhwjcsxmdtrbtiwweghuhpvgxrzcjwhcczzbvpfkvftiwwecyivqjuxchtvatcwvrbhjhpfiltcnywluobyskhaiegbdbbysktkijhatsfgztcobzcgivikvxloazbaxrqeuydfitfbbswihaphpvkthaiuogshprhmwsgnwlwslkctkcquogpggcifdfbyomwsprrldamuwltoavkaxqptonhslywlhsoiszphqfbbrcccrmwwvbcyccwkvxgolvenphmjcejhqfblivmjsmwsvyowicjvgbuhmuogspicogrslrutxbakstrvwkvxg
这题中的使用的Vigenere维吉尼亚密码：就是确定密钥后，分组多次使用凯撒密码。所以破解维吉尼亚密码：关键在于确定密钥的长度t。分解后每组就是一个凯撒密码，即组内的位移量是一致的，对每一组即可用频度分析法来解密。 确定密钥长度主要有两种方法，Kasiski 测试法相对简单很多，但Friedman 测试法的效果明显优于Kasiski 测试法。 方法一 Kasiski方法： 当密文很长的时候，可以找出几组重复的密文段，找出它们间距的相同约数，就是密钥长度。在密文中出现相同的子串之间的距离可能是t的倍数，找出所有的相同的子串的距离，尤其出现次数较多的(避免巧合)，t是这些距离的最大公约数。 方法二 Friedman试验： 首先我们需要知道重合指数（IC, index of coincidence）的概念：任意取两个字母(取后放回)，使之结果相同的概率。 英语中的重合指数定义如下:
由老师给每个字母出现的概率图片，可算得其结果为0.065 破解维吉尼亚密码的两个步骤： 1、确定密钥长度。 遍历密钥长度，使得某一个密钥长度下的分组算得的重合因子其结果接近0.065，可用以下公式：
其中，i为英文字母顺序表中的第i个字母,ni为其在密文分组中出现的频数，N为该分组的长度。如果该密钥长度下的各个分组算得的平均重合因子的结果接近0.065，则找到正确的密钥长度。否则，换下一个密钥长度测试。 2、进行频率分析。 密文确定密钥长度后，可将密文划分成相应的分组。在划分出来的任一分组中，明文和密文都是通过同一个字母实现移位加密的，此时，只需将密文相对于明文进行移位测试，找出具有重合因子接近0.065的位移，即可确定该分组的偏移量，其他分组同理。可用以下公式：
(j的取值为[0,25]，即我们需要求的偏移量)。可理解成：明文中出现的第i个字母可能映射成了密文中的第i+j个字母(两个"字母"都已经按顺序排好，但出现的频数不一定相同) 单字母替换(Mono-Alphabetic Substitution):将明文中的字母进行随机替换，密钥空间为26! 在这里，我采用的是Friedman测试法确定密钥长度，整个解密过程大致如下： 1、Friedman测试法确定密钥长度（找到某个密钥长度下的各个分组算得的平均重合因子的结果接近0.065）。 2、根据密钥长度分组。 3、确定密钥（根据每个字母出现的频率和英文字母频率表对照）。 4、根据密钥和分组，分别解密。 5、最后合并输出。 源代码：Vigenere.java
public class Vigenere { public static void main(String[] args) { /*密文*/ String cipher = "ivikdkdqmjglpwlzgmpfbjiidbbysljdxfgbiwwehapheysgnccyootstzabcobvrtazeywvwwazaidgazpethpvbpwobvjxgfmdobcgpfkxkszzaigcjrpetacjhuthpvhkjhpzhfpmevzeqsbyomhsdvftasfgztcobzcghfmdobcwvnvbrvkrgxdbmkfbtgbvgmptbvfmtgblbmxzweshgcbyskdtbysfwoarqhcjqeqbcuidcnchwwgnedwihptkqczgdkigdenhpzgigwvtwiasbfhatqijsbcdwzbmpgqkkthtqigmefmjsgislkcfthpvfxlszvhagsmgclhwjcsxmdtrbtiwweghuhpvgxrzcjwhcczzbvpfkvftiwwecyivqjuxchtvatcwvrbhjhpfiltcnywluobyskhaiegbdbbysktkijhatsfgztcobzcgivikvxloazbaxrqeuydfitfbbswihaphpvkthaiuogshprhmwsgnwlwslkctkcquogpggcifdfbyomwsprrldamuwltoavkaxqptonhslywlhsoiszphqfbbrcccrmwwvbcyccwkvxgolvenphmjcejhqfblivmjsmwsvyowicjvgbuhmuogspicogrslrutxbakstrvwkvxg"; String ciphertext = cipher.toUpperCase(); Vigenere vigenere = new Vigenere(); /*Vigenere解密*/ vigenere.decryptCipher(vigenere.Friedman(ciphertext), ciphertext); } // Friedman测试法确定密钥长度 private int Friedman(String ciphertext) { // 猜测密钥长度 int keyLength = 1; // 重合指数 double[] Ic; // 平均重合指数 double avgIc; // 密文分组 ArrayList<String> cipherGroup; while (true) { /*各个属性的实例化*/ Ic = new double[keyLength]; cipherGroup = new ArrayList<>(); avgIc = 0; // 1 先根据密钥长度分组 for (int i = 0; i < keyLength; ++i) { StringBuilder tempGroup = new StringBuilder(); for (int j = 0; i + j * keyLength < ciphertext.length(); ++j) { tempGroup.append(ciphertext.charAt(i + j * keyLength)); } cipherGroup.add(tempGroup.toString()); } // 2 再计算每一组的重合指数 for (int i = 0; i < keyLength; ++i) { // 子串 String subCipher = cipherGroup.get(i); // 字母及其出现的次数 HashMap<Character, Integer> occurrenceNumber = new HashMap<>(); // 2.1 初始化字母及其次数键值对 for (int h = 0; h < 26; ++h) { occurrenceNumber.put((char) (h + 65), 0); } // 2.2 统计每个字母出现的次数 for (int j = 0; j < subCipher.length(); ++j) { occurrenceNumber.put(subCipher.charAt(j), occurrenceNumber.get(subCipher.charAt(j)) + 1); } // 2.3 计算重合指数 double denominator = Math.pow((double) subCipher.length(), 2); for (int k = 0; k < 26; ++k) { double o = (double) occurrenceNumber.get((char) (k + 65)); Ic[i] += o * (o - 1); } Ic[i] /= denominator; } // 3 判断退出条件,重合指数的平均值是否大于0.065 for (int i = 0; i < keyLength; ++i) { avgIc += Ic[i]; } avgIc /= (double) keyLength; if (avgIc >= 0.06) { break; } else { keyLength++; } } // while--end // 打印密钥长度，分组，重合指数，平均重合指数 System.out.println("密钥长度为：" + String.valueOf(keyLength)); System.out.println("密文分组及其重合指数为："); for (int i = 0; i < keyLength; ++i) { System.out.println(cipherGroup.get(i).toLowerCase() + " 重合指数: " + Ic[i]); } System.out.println("平均重合指数为： " + String.valueOf(avgIc)); return keyLength; }// Friedman--end // 再次使用重合指数法确定密钥 private void decryptCipher(int keyLength, String ciphertext) { /*密钥数组，密钥字符对应的ascii码*/ int[] key = new int[keyLength]; /*密文分组*/ ArrayList<String> cipherGroup = new ArrayList<>(); /*英文中26个字母的频率*/ 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}; // 1 先根据密钥长度分组 for (int i = 0; i < keyLength; ++i) { /*密文分组的中间字符串对象*/ StringBuilder temporaryGroup = new StringBuilder(); for (int j = 0; i + j * keyLength < ciphertext.length(); ++j) { /*按照密钥的长度将密文分组*/ temporaryGroup.append(ciphertext.charAt(i + j * keyLength)); } /*将每个密文分组加到数组表中去*/ cipherGroup.add(temporaryGroup.toString()); } // 2 确定密钥 for (int i = 0; i < keyLength; ++i) { // 重合指数 double MG; // 移动位置 int flag; // 密文移动g个位置 int g = 0; // 字母出现次数 HashMap<Character, Integer> occurrenceNumber; // 子串，用来接收每个密文分组 String subCipher; while (true) { MG = 0; flag = 65 + g; /*取出密文分组*/ subCipher = cipherGroup.get(i); occurrenceNumber = new HashMap<>(); // 2.1 初始化字母及其次数 for (int h = 0; h < 26; ++h) { /*在哈希图中将键设为26个字母对应的ascii码，初值设为0*/ occurrenceNumber.put((char) (h + 65), 0); } // 2.2 统计字母出现次数 for (int j = 0; j < subCipher.length(); ++j) { /*出现对应的字母，就将它出现的次数+1*/ occurrenceNumber.put(subCipher.charAt(j), occurrenceNumber.get(subCipher.charAt(j)) + 1); } // 2.3 计算当前分组各个字母的重合指数，得到该组的重合指数 for (int k = 0; k < 26; ++k, ++flag) { double p = probability[k]; flag = (flag == 91) ? 65 : flag; double f = (double) occurrenceNumber.get((char) flag) / subCipher.length(); MG += p * f; } // 2.4 判断退出条件 if (MG >= 0.055) { key[i] = g; break; } else { ++g; } } // while--end } // for--end // 3 打印密钥 StringBuilder keyString = new StringBuilder(); for (int i = 0; i < keyLength; ++i) { /*将密钥的ascii码装换成字符，再添加再字符串后面*/ keyString.append((char) (key[i] + 65)); } System.out.println("密钥为: " + keyString.toString()); // 4 解密 StringBuilder plainBuffer = new StringBuilder(); for (int i = 0; i < ciphertext.length(); ++i) { /*每个密文字母编号对应的密钥字母编号*/ int keyFlag = i % keyLength; /*用每个密文字母的ascii码减去对应的密钥字母的ascii码*/ int change = (int) ciphertext.charAt(i) - 65 - key[keyFlag]; /*将ascii码转换成字符*/ char plainLetter = (char) ((change < 0 ? (change + 26) : change) + 65); /*添加在字符串后面*/ plainBuffer.append(plainLetter); } System.out.println("明文为：\n" + plainBuffer.toString().toLowerCase()); } }实验结果截图：
最后解密的明文为：That process said is tarts upon the supposition that when you have eliminated all which is impossible,then whatever remain show ever improbable must be the truth.It may well be that several explanations remain in which case one tries test after test until one or other of them has a convincing amount of support. We will now apply this principle to the case in point as it was first presented to me. There were three possible explanations of these exclusion or incarceration of this gentle man in an out house of his father’s mansion. There was the explanation that he was in hiding for a crime or that he was mad and that they wished to avoid an asylum or that he had some disease which caused his segregation. I could think of no other adequate solutions, these then had to be sifted and balanced against each other.
