Playfair密码与实现
背景
这种加密方法是1854年Charles Wheatstone发明的，由Lord Playfair推广，所以命名为Playfair密码。它在一战和二战中都有使用，虽然在一战中就被破译，但是由于使用简单，可以用来保护一些敏感但不很关键的信息，即使被破译，信息也已经过时。
详细流程
创建矩阵
这种密码使用一个5*5的矩阵作为一个密码表，用作加密解密时的秘钥。这个矩阵由一个关键词生成，首先将关键词从左到右，从上到下填入矩阵，遇到重复元素则省略，写完之后按照字母表顺序，将未出现的字母填充到剩余位置，知道整个矩阵被填满。
如以PLAYFAIREXAMPLE为关键词，生成的矩阵如下：
你可能注意到，密码表中缺少J，由于只有25个空位，对于字母大于25的语言，可以将某两个合并，或者省去出现频率少的，这里把i和j进行了合并
加密
加密之前首先将明文两两分组），对每一组分别进行以下处理
- 在密码表中找到每组中两个字母的位置
- 若果两个字母相同或组中只有一个字母，则插入一个字母，如X或Q（如果最后一个字母或者重复的字母是X，可以添加Q，替换方法可自定义）
- 如果两个字母在密码表的同一行，则用这两个字母右边的字母进行替换，如(I,E)替换为(R,X)。我们定义第一列是最后一列的右边
- 如果两个字母在密码表的同一列，则用这两个字母的下方字母进行替换，如(E,O)替换为(D,V)。我们定义第一行是最后一行的下边
- 如果两个字母不在同一行同一列，则用对角线上的字母进行替换，至于是行替换或列替换可以自行定义。如(M,Y)替换为(X,F)，使用的是行替换
解密
解密就很简单了，基本就是加密的逆过程，还是利用密码表，如在同一行的话，用左边替换，同一列用上面的替换，在对角线上的还是不变。具体过程见后面实现。
示例
如还以PLAYFAIREXAMPLE为关键词，明文为MYNAMEISTOM，加密过程如下：
- 生成矩阵，如上图
- 分组：MY NA ME IS TO MX (最后一个单独字母补X)
- 根据密码表替换 XF OL IX MK VK IM
- 最后密文为： XFOLIXMKVKIM
简单实现
这里只是简单实现了Playfair密码原理，有些地方如包含标点符号，非英文字母的情况并没有处理，有兴趣的可以自行修改
public class PlayFair {
char[][] table = new char[5][5]; //密码表
PlayFair(String key){
generateTable(key);//根据关键字生成密码表
}
private void generateTable(String key){
key = key.replaceAll(" ","").toUpperCase();
char[] keys = key.toCharArray();
int count = 0;
char alphabet = 'A';
ArrayList<Character> list = new ArrayList<>();
for (int i = 0;i<5;i++){
for (int j = 0;j<5;j++){
while(count < keys.length && list.contains(keys[count])){ //寻找关键字中不重复的字母
count++;
}
if (count < keys.length){
table[i][j] = keys[count];
list.add(keys[count]);
count++;
}else{
while (alphabet <= 'Z' && (list.contains(alphabet) || alphabet == 'J')){ //按顺序从字母表中填充
alphabet++;
}
table[i][j] = alphabet;
alphabet++;
}
}
}
}
public String encryption(String msg){ //加密算法
msg = msg.replaceAll(" ","").toUpperCase();
char[] msgs = msg.toCharArray();
StringBuffer result = new StringBuffer();
for (int i = 0;i<msgs.length;i++){
char a = msgs[i];//获取分组第一个字母
i++;
char b;
if (i<msgs.length){ //判读是否越界
if (msgs[i] == a){ //是否重复
if (a == 'X'){ //若是X重复，添加Q
b = 'Q';
}else{
b = 'X';
}
i--;
}else{
b = msgs[i];
}
}else{ //越界，就是最后只剩一个字母
if (a == 'X'){ //若最后一个是X，补Q
b = 'Q';
}else{
b = 'X';
}
}
int[] locA = find(a); //寻找分组第一个字母位置
int[] locB = find(b); //寻找分组第二个字母位置
if(locA[0] == locB[0]){ //若在同一行
a = locA[1]+1<5?table[locA[0]][locA[1]+1]:table[locA[0]][0];
b = locB[1]+1<5?table[locB[0]][locB[1]+1]:table[locB[0]][0];
}else if(locA[1] == locB[1]){ //若在同一列
a = locA[0]+1<5?table[locA[0]+1][locA[1]]:table[0][locA[1]];
b = locB[0]+1<5?table[locB[0]+1][locB[1]]:table[0][locB[1]];
}else{ //不在同一行同一列，行替换
a = table[locA[0]][locB[1]];
b = table[locB[0]][locA[1]];
}
result.append(a);
result.append(b);
}
return result.toString();
}
public String decrypt(String msg){ //解密算法
msg = msg.replaceAll(" ","").toUpperCase();
char[] msgs = msg.toCharArray();
if (msgs.length%2!=0){ //密文不是偶数个，报错
return "error: The length of ciphertext is odd";
}
StringBuffer result = new StringBuffer();
for (int i = 0;i<msgs.length;i++){
char a = msgs[i];
i++;
char b = msgs[i];
int[] locA = find(a);//寻找分组第一个字母位置
int[] locB = find(b);//寻找分组第二个字母位置
if(locA[0] == locB[0]){ //若在同一行
a = locA[1]-1>-1?table[locA[0]][locA[1]-1]:table[locA[0]][4];
b = locB[1]-1>-1?table[locB[0]][locB[1]-1]:table[locB[0]][4];
}else if(locA[1] == locB[1]){ //若在同一列
a = locA[0]-1>-1?table[locA[0]-1][locA[1]]:table[4][locA[1]];
b = locB[0]-1>-1?table[locB[0]-1][locB[1]]:table[4][locB[1]];
}else{ //不在同一行同一列
a = table[locA[0]][locB[1]];
b = table[locB[0]][locA[1]];
}
result.append(a);
result.append(b);
}
return result.toString();
}
private int[] find(char c){ //寻找字母在表中位置
if (c == 'J')//对于J当做I处理
c = 'I';
for (int i = 0;i<5;i++){
for (int j = 0;j<5;j++){
if (table[i][j] == c)
return new int[]{i,j};
}
}
return new int[]{-1,-1};
}
public static void main(String[] args) {//测试代码
PlayFair p = new PlayFair("PLAYFAIREXAMPLE");
String msg = p.encryption("MYNAMEISTOM");
System.out.println("ciphertext：" + msg);
System.out.println("plaintext：" + p.decrypt(msg));
}
}
小结
本质上Playfair密码仍然是替换型的密码算法。与一般的替换算法相比，他的替换不固定，每个字母都有可能替换为任意一个其他字母。另外实现简单，一个不同秘钥生成不同密码表，产生不同的替换可能。但是它依然可以被破解，首先它是按照顺序读取的，密文与明文基本上一一对应，从而也暴露的密文结构；其次，密码表最后填充时是按照字母表顺序填充，可借助字母出现频率构造密码表，一旦一部分被构造出来，剩下的很容易破解；