维吉尼亚密码加解密原理及其实现
维吉尼亚密码加解密原理及其实现
维吉尼亚密码（又译维热纳尔密码）是一种使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。本文将详细介绍维吉尼亚密码的加解密原理及其实现方法。
维吉尼亚密码的背景
为了说清楚维吉尼亚密码，得从移位替换密码说起，比较典型的就是凯撒密码。
恺撒密码 是一种替换加密的技术，明文中的所有字母都在字母表上向后（或向前）按照一个固定数目进行偏移后被替换成密文。
例如，当偏移量是3的时候，所有的字母A将被替换成D，B变成E，以此类推。
因为概率论的出现这种简单的移位或替换就容易破解了，其原理很简单，英文中字母出现的频率是不一样的。比如字母e是出现频率最高的，占12.7%；其次是t，9.1%；然后是a，o，i，n等，最少的是z，只占0.1%。
各语言中字母频率统计
只要字符总量足够，全部收集到一起，统计各个字符出现的频率，然后再加上字母前后的关联关系，以及所要加密的语言本身语法搭配就可大幅度降低字母的排列组合的可能性，这样密码就破解了。
当然维吉尼亚密码也属于古典密码学的范畴，都是对单个字符或符号进行移位或替代。
维吉尼亚加密原理
核心：为了掩盖字母使用中暴露的频率特征，解决的办法就是用多套符号代替原来的文字。
比如原来的字母是A，从前只把它替换成F，现在把它替换成F或者G这两个。那什么时候用F什么时候用G呢？可以自行规定，比如说，字母在奇数位时用F代替，字母在偶数位时用G代替。
这样频率分析法暂时失效了。
而且，多套符号加密法并没满足于2~3套，后来典型使用的是26套，这就是第三代密码“维吉尼亚加密法”。
它是一个表格，第一行代表原文的字母，下面每一横行代表原文分别由哪些字母代替，每一竖列代表我们要用第几套字符来替换原文。一共26个字母，一共26套代替法，所以这个表是一个26*26的表。
维吉尼亚密码表
每一行就可以代表一套凯撒密码加密方法。
加密方法
加密公式：C = (P + K)%26
C：密文
P：原文
K：第几套加密方式
使用第几套加密方式是通过约定一个规则来确定的，这个规则就是“密钥”。
这样一个密钥字母代表一套加密方式，比如：t代表第19套加密方式，h代表第7套加密方式，i代表第8套加密方式，s代表第18套加密方式。
这样密钥和原文每个字符一一对应，如果密钥长度不足，那么循环替代。
原文中的两个“l”分别加密成T和D，而且密文中的同样的字符也可能代表不同的原文，比如密文中的L，分别代表了原文中的“e”和“d”。
解密方法
解密公式：P = (C - K)%26
C：密文
P：原文
K：第几套加密方式
如果P<0,P+26取得正序
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Optional;
/**
* 维吉尼亚加密解密
*/
public class VirginiaPassword {
//Virginia Password table
private static final String VIRGINIA_PASSWORD_TABLE_ARRAY[] = {"A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
public static final List<String> VIRGINIA_PASSWORD_TABLE_ARRAY_LIST = Arrays.asList(VIRGINIA_PASSWORD_TABLE_ARRAY);
/**
* 判断对象是否为空，为空返回false，非空返回true
* @param object
* @return
*/
public static boolean isNotNull(Object object) {
return Optional.ofNullable(object).isPresent();
}
/**
* 判断字符串非null，并且不为空字符串
* @param str
* @return
*/
public static boolean isStringNotEmpty(String str) {
return isNotNull(str)&&str.trim()!="";
}
/**
* C = P + K (mod 26).
* 维吉尼亚加密
* @param original 原文
* @param secretKey 密钥
* @return
*/
public static String virginiaEncode(String original,String secretKey) {
if(isStringNotEmpty(secretKey)&&isStringNotEmpty(original)){
char[] secretCharArray = secretKey.toCharArray();
char[] originalCharArray = original.toCharArray();
int length = originalCharArray.length;
List<Integer> list = getSecretKeyList(secretCharArray, length);
StringBuffer sb = new StringBuffer();
for(int m=0;m<length;m++) {
char ch = originalCharArray[m];
int charIndex = VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.indexOf(String.valueOf(ch).toUpperCase());
if(charIndex==-1) {
sb.append(String.valueOf(ch));
continue;
}
int size = VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.size();
//C = P + K (mod 26). 获取偏移量索引
int tmpIndex = (charIndex + list.get(m))%size;
sb.append(VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.get(tmpIndex));
}
return sb.toString();
}
return null;
}
/**
* P = C - K (mod 26).
* 维吉尼亚解密
* @param cipherText 密文
* @param secretKey 密钥
* @return
*/
public static String virginiaDecode(String cipherText,String secretKey) {
if(isStringNotEmpty(cipherText)&&isStringNotEmpty(secretKey)) {
char[] secretCharArray = secretKey.toCharArray();
char[] cipherCharArray = cipherText.toCharArray();
int length = cipherCharArray.length;
List<Integer> list = getSecretKeyList(secretCharArray, length);
StringBuffer sb = new StringBuffer();
for(int m=0;m<length;m++) {
char ch = cipherCharArray[m];
int charIndex = VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.indexOf(String.valueOf(ch).toUpperCase());
if(charIndex==-1) {
sb.append(String.valueOf(ch));
continue;
}
int size = VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.size();
//P = C - K (mod 26). 模逆运算求索引
int len = (charIndex - list.get(m))%size;
//索引小于零，加模得正索引
int tmpIndex = len<0?len+size:len;
sb.append(VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.get(tmpIndex));
}
return sb.toString();
}
return null;
}
/**
* 获取密钥集合
* @param secretCharArray 密钥字符数组
* @param length 原文或密文的长度
* @return
*/
private static List<Integer> getSecretKeyList(char[] secretCharArray, int length) {
List<Integer> list = new ArrayList<Integer>();
for (char c : secretCharArray) {
int index = VIRGINIA_PASSWORD_TABLE_ARRAY_LIST.indexOf(String.valueOf(c).toUpperCase());
list.add(index);
}
if(list.size()>length) {
//截取和目标原文或密文相同长度的集合
list = list.subList(0, length);
}else {
Integer[] keyArray = list.toArray(new Integer[list.size()]);
int keySize = list.size();
//整除
int count = length/keySize;
for(int i=2;i<=count;i++) {
for (Integer integer : keyArray) {
list.add(integer);
}
}
//求余
int mold = length%keySize;
if(mold>0) {
for(int j=0;j<mold;j++) {
list.add(keyArray[j]);
}
}
}
return list;
}
}
注：以上代码在JDK1.8上编译通过
维吉尼亚加密难以破解的关键是同一种原文对应上亿种密文，相同的密文也一样对应上亿种原文。
维吉尼亚密码的破解方法
以上代码是知道密钥的情况，通过加密的求余逆运算计算出来的，但是真实的情况下，我们只有密文，没有密钥，那么怎么破解维吉尼亚密码呢？
同样的原文“the”被两次加密成“DPR”，这是巧合？
其实不然，密钥KING由4个字母构成，而在密文中代表the的DPR间隔了12个字母，间隔距离刚好是密钥的3倍。
正好在KING这个密钥循环到整数倍的时候，如果也正好赶上出现了同样的原文，那巧合就出现了——原文就会被加密成相同的密文。
而此处即是破解维吉尼亚密码的关键。
在不知道密钥的情况下，分析出密钥的长度，那么密码就被破解了。
怎么分析出密钥的长度呢？
把密文中完全一样的单词挑出来，分析总结其规律。
密文对应的原文虽然理论上数量巨大，但拼写规则一卡，数据量就急剧减少了。
而且密文里的字符串长度越长，对应真实存在的单词数量就越少。
你可以翻翻字典，或者在头脑中找找4个字母的单词和12个字母的单词，看看其数量对比。
步骤：
1.从密文中找出拼写完全相同的字符串
2.数第一次到第二次出现中间间隔的字母数
如果间隔了30个字母
密钥长度为2，那么正好反复出现了15次；
密钥长度为3，那么正好反复出现了10次；
密钥长度为5，那么正好反复出现了6次；
密钥长度为6，那么正好反复出现了5次；
密钥长度为30，那么正好反复出现了1次。
比如还存在B、C、D，只要看同样的因数都出现，那么这个因数就是密钥的长度。
我们通过密钥的长度，就可以使用频率分析方法把原文分析出来。
比如我们知道密钥的长度为6，那么第1、7、13等字母放到一组，因为它们都是通过同一套加密方式加密出来的，然后用频率分析法。
其它组别也按照此方式分析出来。
所以，猜中密钥长度就等于，把维吉尼亚密码化简为N套最基础的移位法。
