加密算法学习（一、中、1）——传统加密算法（playfair密码）_playfair加密算法

本博文借鉴自书本《密码编码学与网络安全——原理与实践（第七版）》，由William Stallings著，王后珍、李莉等译。

---

参考博客：信息安全-1:python之playfair密码算法详解[原创] - 张玉宝 - 博客园

参考论文：

---

 

二、代替技术

3.playfair密码

（1）例子：

最著名的多字母密码是playfair密码，他把明文中的双字母音节作为一个单元并将其转换成密文的“双字母音节”。playfair算法是基于一个由密钥词构成的5x5字母矩阵。下面的例子由Lord Peter Wimsey在Dorothy Sayers所著的Have His Carcase一书中给出。

本例使用的密钥词是monarchy，填充矩阵的方法是：首先将密钥词（去掉重复字母）从左至右、从上至下填在矩阵格子中，再将剩余的字母按照字母表的顺序从左至右、从上至下填在矩阵剩下的格子里。字母I和J暂且当成一个字母。对明文按照如下规则一次加密两个字母：

• 如果该字母对的两个字母是相同的，那么在他们之间加一个填充字母，比如x。例如balloon先把它变成ba lx lo on这样四个字母对。
• 落在矩阵同一行的明文字母对中的字母由其右边的字母来代替，每行中最右边的一个字母就落在该列中最左边的第一个字母来代替，比如ar变成RM。
• 落在矩阵同一列的明文字母对中的字母由其下面的字母来代替，每行最下面的一个字母就落在该列中最上面的第一个字母来代替，比如mu变成CM。
• 其他的每组明文字母对中的字母按如下方式代替，该字母所在行为密文所在行，另一个字母所在列为密文所在列。比如hs变成BP，ea变成IM（或JM）。

---

（2）前提约定

首先playfair密码算法适用于对解密后的内容大小写不敏感，因为密文全为大写，无法得知明文的大小写情况，解密的结果全为大写或小写。然后由于密钥中I和J被视为同一个，即明文中出现的I/J都将被被同时视为I或J来加密，那么解密出来的结果就具有二义性。而且当明文中出现两个字符相同的一组字母对时，在它们之间插入的填充字母也有可能出现在明文中。鉴于上面出现的二义性，做出如下约定：

• 密钥均为小写.
• 密钥中同时出现i和j时，我用i代替j(当然你也可以用j代替i).
• 对于明文中两个字符相同的一组字母对，我在它们之间插入大写字母'Z'，然后得到的明文长度若为奇数，则在末尾增加大写字母Z(你可以用X或Q这两个出现频率也比较低的字母代替).
• 解密的结果全为小写.
• 明文中不能有字母'j'或'J'，否则结果具有二义性，因为约定中用i代替了'j'，所以解密后的到的'I'不知道是对应'i'还是'j'
• 不存在明文长度为偶数时，明文从后向前数时，连续地'z'或'Z'字母只有一个。例如，明文"YZ"和"Y"加密前均变为"YZ"，那么解密得到的"YZ"不知道对应明文"YZ"还是明文"Y"，会具有二义性.
• 明文中不存在一种情况：'z'或'Z'出现在第偶数位，且其前后字符为不等于‘z’或‘Z’的相同字符，但明文末尾连续多个'z'或'Z'（超过一个）可以出现。

做出如上约定后，加密解密的过程中才不会出现计算机所无法处理的二义性。下面是对加密解密过程做详细分析，以及对前提约定的解释。

（3）过程详解

a、处理密钥

/**
* <h1>得到无重复字母的字符串</h1>
* <br>String str：字符串 
* */
private String getNoRepetionStr(String str) {
	String noRepetitionKey = " ";
	for (int i = 0; i < str.length(); i++) {
		int count = 0;
		for (int j = 0; j < noRepetitionKey.length(); j++) {
			if (str.charAt(i) != noRepetitionKey.charAt(j)) {
				count++;
			}
		}
		if (count == noRepetitionKey.length()) {
			noRepetitionKey += str.charAt(i);
		}
	}
	return noRepetitionKey.trim();
}

利用上面程序中的getNoRepetionStr()方法，得到无重复的密钥字符串。该方法的思想是，设置变量noRepetionKey等于由单独一个空格组成的字符串，可以处理密钥中存在空格的情况。

在遍历密钥字符串时，若当前字符在noRepetionKey中未出现过，则将其增加到noRepetionKey的末尾。

用count变量来记录noRepetionKey中与当前字符不相等的个数，若得到的count值等于noRepetionKey的length，则代表该字符未出现过。

 b、得到矩阵

/**
* <h1>根据无重复密钥得到填充完整的矩阵一维字符串</h1>
* <br>String noRepetitionStr：无重复的小写密钥字符串
* */
private String getMatrixStr(String noRepetitionKey) {
	noRepetitionKey = noRepetitionKey.toUpperCase();	//将无重复的密钥字符串全部转换为大写
	noRepetitionKey += " ";	//加空格是为了在密钥为空时也能生成矩阵
	if (noRepetitionKey.length() < 25) { //如果无重复的密钥字符串长度小于25,即没有包含所有字母（除去'J'）
		//填充密钥中未出现的字母
		for (int i = 0; i < 26 ; i++) {	
			int count = 0;
			char c = (char)('A' + i);
			for (int j = 0; j < noRepetitionKey.length(); j++) {
				if (c != noRepetitionKey.charAt(j)) {
					count++;
				}
			}
			if (count == noRepetitionKey.length()) {
				noRepetitionKey = noRepetitionKey.trim() + c;
			}
		}
		//除去填充的字符'J'
		noRepetitionKey = noRepetitionKey.split("J")[0] + noRepetitionKey.split("J")[1];
	}	
		return noRepetitionKey;//填充完整的矩阵一维字符串
}

上面程序中的getMatrixStr()方法作用是根据无重复的密钥字符串，和字母表顺序填充矩阵中剩余位置，得到填充完整的矩阵一维字符串。

无重复密钥字符串长度为25（去掉了'j',所以是25）时，即noRepetitionKey.length() == 25时，代表无重复密钥字符串已将矩阵填充完整，无需再用字母表填充。

若其长度小于25，则代表需要用字母表顺序填充，字母填充的结果中包含‘J’，所以要去除字母'J'

/**
* @author GDUYT
* <h1>矩阵中的每个元素单元</h1>
* */
class MatrixUnit {
		
        int row;		//行值，取值空间为[0,4]
        int column;		//列值，取值空间为[0,4]
        char UnitChar;	//数值
		
	public MatrixUnit() {
	}
		
	public MatrixUnit(int row, int column, char unitChar) {
		this.row = row;
		this.column = column;
		UnitChar = unitChar;
	}
 
	@Override
	public String toString() {
		return  UnitChar + "";
	}
}

上面程序的功能即定义矩阵单元类，其属性包含该矩阵单元在矩阵中的行值、列值、数值。

/**
* <h1>得到一维密钥矩阵字符串中每个单元在二维5x5字符矩阵中的行值、列值、数值</h1>
*<br> String matrixStr：一维的25位密钥矩阵字符串
* */
private MatrixUnit[] getMatrix(String matrixStr) {
	MatrixUnit matrixUnit[] = new MatrixUnit[25];
	for (int i = 0; i < 25; i++) {
		matrixUnit[i] = new MatrixUnit(i/5, i%5, matrixStr.charAt(i));
	}
	return matrixUnit;
}

 上述程序的功能即为根据前面得到的矩阵一维字符串，得到每个字符单元在矩阵中的元数据，然后组成矩阵单元类的一维数组。

c、处理明文

/**
* <h1>处理加密前的明文</h1>
* <br>String plaintextOperate：明文
* */
private String dealPlaintextBeforeEncrypt(String plaintext) {
	//明文全部转换为小写,并用字符'i'替换字符'j'
	plaintext = plaintext.toLowerCase().replace('j', 'i');
	//对于明文中两个一样的一组字母对，在其中间插入大写字母'Z'
	for (int i = 1; i < plaintext.length(); i+=2) {
		if (plaintext.charAt(i-1) == plaintext.charAt(i)) {
			StringBuilder sb = new StringBuilder();
			for (int j = 0; j < i; j++) {
				sb.append(plaintext.charAt(j));
			}
			sb.append("Z");
			for (int j = i; j < plaintext.length(); j++) {
				sb.append(plaintext.charAt(j));
			}
			plaintext = sb.toString();
			i=1;
		}
	}
	//对于明文长度为奇数时在末尾增加大写字母'Z'
	if ((plaintext.length() % 2) == 1) {
		plaintext += "Z";
	}
	return plaintext.toUpperCase();	//将明文全部转换为大写
}

上面程序中的dealPlaintextBeforeEncrypt()方法，其功能即为处理加密前的明文。首先需要将所有的明文转换为小写，然后用'i'代替明文中的所有的字符‘j’。

对于明文中两个一样的一组字母对，在其中间插入大写字母'Z'，因为明文都转换为了小写，所以‘Z’一定出现在偶数位上。遍历时，只需要检测偶数位的字符是否和前一位相同，相同则插入大写字母'Z'。

最终得到的明文长度若为奇数，则在其末尾增加字符'Z'。

d、加密

/**
* <h1>根据明文和密钥矩阵加密得到密文</h1>
* <br>String plaintext：处理后的明文
* <br>MatrixUnit[] matrix：密钥矩阵
* */
private String encryptOperate(String plaintext, MatrixUnit[] matrix) {
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < plaintext.length(); i += 2) {
		MatrixUnit plainUnit1 = new MatrixUnit();
		MatrixUnit plainUnit2 = new MatrixUnit();
			
		//得到两个一组的明文字符在矩阵中的位置"元数据"
		for (int j = 0; j < matrix.length; j++) {
			if (plaintext.charAt(i) == matrix[j].UnitChar) {
				plainUnit1 = matrix[j];
			}
			if (plaintext.charAt(i+1) == matrix[j].UnitChar) {
				plainUnit2 = matrix[j];
			}
		}
			
		//根据两个一组的明文在矩阵中的相对位置对其加密
		if (plainUnit1.row == plainUnit2.row) {	//如果两个明文在同一行
			plainUnit1 = matrix[plainUnit1.row*5 + (plainUnit1.column+1)%5];
			plainUnit2 = matrix[plainUnit2.row*5 + (plainUnit2.column+1)%5];
		} else if (plainUnit1.column == plainUnit2.column) {	//如果两个明文在同一列
			plainUnit1 = matrix[((plainUnit1.row+1)%5)*5 + plainUnit1.column];
			plainUnit2 = matrix[((plainUnit2.row+1)%5)*5 + plainUnit2.column];
		} else {	//两个明文既不在同一行，也不在同一列
			MatrixUnit tempUnit = plainUnit1;
			plainUnit1 = matrix[plainUnit1.row*5 + plainUnit2.column];
			plainUnit2 = matrix[plainUnit2.row*5 + tempUnit.column];
		}
		sb.append(plainUnit1.toString() + plainUnit2.toString());
	}
	return sb.toString();
}

上面的程序中的encryptOperate()方法，功能为根据处理后的明文和密钥矩阵进行加密，即为加密的核心操作。

先得到明文中一对字母对在矩阵中对应的行值、列值这些矩阵单元“元数据”。然后根据字母对在矩阵中的相对位置遵循变换规则进行变换。

/**
* <h1>加密方法</h1>
* <br>String plaintext：明文字符串
* <br>String key：密钥（小写字母组成的字符串）
* */
public String encrypt(String plaintext, String key) {
	//处理密钥
	//将密钥中出现的'j'字符用'i'代替
	String noRepetitionKey = key.replace("j", "i");
	//得到密钥的无重复字符串
	noRepetitionKey = getNoRepetionStr(noRepetitionKey);
	//得到填充完整的全大写的矩阵一维字符串
	String matrixStr = getMatrixStr(noRepetitionKey);
	//得到一维密钥矩阵字符串中每个单元在二维5x5字符矩阵中的元数据
	MatrixUnit[] matrix = getMatrix(matrixStr);
	System.out.println("密钥矩阵：");
	for (int i = 0; i < matrix.length; i++) {
		System.out.print(matrix[i].toString());
		if (i % 5 == 4) {
			System.out.println();
		}
	}
		
	//处理加密前的明文
	plaintext = dealPlaintextBeforeEncrypt(plaintext);
	System.out.println("处理后的明文：[" + plaintext + "]");
		
	//加密
	String ciphertext = encryptOperate(plaintext, matrix);
	return ciphertext;
}

上面程序即为对前面那些方法的调用，形成供外部调用的同一的encrypt(String plaintext, String key)方法接口。

e、解密

加密完成之后，解密就变得简单的，因为都是加密的逆过程，但每个步骤都不能少。

/**
* <h1>根据密文和密钥矩阵得到明文</h1>
* <br>String ciphertext：密文字符串(大写字母组成的字符串，长度为偶数个)
* <br>MatrixUnit[] matrix：密钥矩阵
* */
public String decryptOperate(String ciphertext, MatrixUnit[] matrix) {
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < ciphertext.length(); i += 2) {
		MatrixUnit plainUnit1 = new MatrixUnit();
		MatrixUnit plainUnit2 = new MatrixUnit();
			
		//得到两个一组的密文字符在矩阵中的位置"元数据"
		for (int j = 0; j < matrix.length; j++) {
			if (ciphertext.charAt(i) == matrix[j].UnitChar) {
				plainUnit1 = matrix[j];
			}
			if (ciphertext.charAt(i+1) == matrix[j].UnitChar) {
				plainUnit2 = matrix[j];
			}
		}
			
		//根据两个一组的密文在矩阵中的相对位置对其解密
		if (plainUnit1.row == plainUnit2.row) {	//如果两个密文在同一行
			plainUnit1 = matrix[plainUnit1.row*5 + (plainUnit1.column-1+5)%5];
			plainUnit2 = matrix[plainUnit2.row*5 + (plainUnit2.column-1+5)%5];
		} else if (plainUnit1.column == plainUnit2.column) {	//如果两个密文在同一列
			plainUnit1 = matrix[((plainUnit1.row-1+5)%5)*5 + plainUnit1.column];
			plainUnit2 = matrix[((plainUnit2.row-1+5)%5)*5 + plainUnit2.column];
		} else {	//两个密文既不在同一行，也不在同一列
			MatrixUnit tempUnit = plainUnit1;
			plainUnit1 = matrix[plainUnit1.row*5 + plainUnit2.column];
			plainUnit2 = matrix[plainUnit2.row*5 + tempUnit.column];
		}
		sb.append(plainUnit1.toString() + plainUnit2.toString());
	}
	return sb.toString();
}

首先就是根据密文进行解密，上面程序中的decryptOperate()方法的过程即为encryptOperate()方法的逆过程。

/**
* <h1>处理解密后的明文</h1>
* <br>String plaintext：解密后的明文
* */
private String dealPlaintextAfterDecrypt(String plaintext) {
		
	//末尾存在字符'Z'时的处理
	//如果末尾存在字符'Z',则用空格代替它，即删除它但保留字符串长度
	if (plaintext.charAt(plaintext.length()-1) == 'Z') {
		plaintext = plaintext.substring(0, plaintext.length()-1) + " ";
	}
		
	//去除加密时连续重复字母之间加入的'Z',其特点为一定出现在偶数位上，且其前后字母相同
	for (int i = plaintext.length() - 3; i > 0; i -= 2) {
		if (plaintext.charAt(i) == 'Z' 
				&& (plaintext.charAt(i-1) == plaintext.charAt(i+1))) {
			StringBuilder sb = new StringBuilder();
			for (int j = 0; j < i; j++) {
				sb.append(plaintext.charAt(j));
			}
			for (int j = i + 1; j < plaintext.length(); j++) {
				sb.append(plaintext.charAt(j));
			}
			plaintext = sb.toString();
		}
	}
	return plaintext.toLowerCase().trim();
}

然后便需要对解密后的结构进行处理，上面程序中，dealPlaintextAfterDecrypt()方法即为处理解密后的结果。

第一步是除去末尾填充的大写字母"Z"，用空格代替它，即保留其字符长度。根据前面约定的第六条：

• 不存在明文长度为偶数时，明文从后向前数时，连续地'z'或'Z'字母只有一个。例如，明文"YZ"和"Y"加密前均变为"YZ"，那么解密得到的"YZ"不知道对应明文"YZ"还是明文"Y"，会具有二义性.

即不存在单独的'z'或'Z'出现在明文末尾，那么解密后的结果末尾出现的大写字母"Z"，一定是因为加密时长度为奇数所增加的"Z"，那么这个"Z"一定需要删除。例如：（注意：此时的解密后的结果长度一定是偶数，因为密文长度为偶数）

解密后："YZ" ——> "Y"（对应明文）

解密后："ZZ" ——> "Z" （对应明文）

解密后："YZZZ" ——> "YZZ" （对应明文）

解密后："ZZZZ" ——> "ZZ"（对应明文）

解密后："YZZZZZ" ——> "YZZZ"（对应明文）

解密后："ZZZZZZ" ——> "ZZZ"（对应明文）

…………

 

第二步是去除加密时连续重复字母之间加入的大写字母'Z',其特点为一定出现在偶数位上，且其前后字母相同。根据前面约定的最后一条：

• 明文中不存在一种情况：'z'或'Z'出现在第偶数位，且其前后字符为不等于‘z’或‘Z’的相同字符，但明文末尾连续多个'z'或'Z'（超过一个）可以出现。

这是因为存在一种情况：当明为"HZHY"或"HHY"时，加密前对明文处理后得到的结果都是"HZHY"，那么经过加密和解密后，得到的待处理结构也都是"HZHY"，此时将无法得知对应的明文是"HZHY"还是"HHY"，即该"Z"可能是原文中的，也可能是增加的。所以做出上面的约定，去除二义性。

去除"Z"的过程借鉴自博客：信息安全-1:python之playfair密码算法详解[原创] - 张玉宝 - 博客园中的从后向前删除的思想。因为前面去除末尾"Z"的时候并未改变字符长度，故其长度还是为偶数。从倒数第三位开始检测，如果当前字符为"Z",且其前后字符相同，则删除这个"Z"。

比如：解密后得到的"ZZZZ"，去除末尾"Z",代替为空格，得到"ZZZ "(末尾有一个空格)，其长度依旧为4。从其到时第三个开始检测，即下标为1的第二个字符"Z"，其前后字符均为"Z",则删除这个"Z"，得到"ZZ "（末尾有一个空格），程序中步长为i  -= 2，因为1 - 2 = -1 < 0，所以循环结束。再去除末尾空格，变为全小写，得到正确明文"zz"。

再比如：解密后得到的"YZZZZZZZ"，去除末尾"Z",代替为空格，得到"YZZZZZZ "(末尾有一个空格)，其长度依旧为8。从其到时第三个开始检测，即下标为5的第六个字符"Z"，其前后字符均为"Z",则删除这个"Z"，得到"YZZZZZ "(末尾有一个空格)，程序中i = 5 - 2 = 3 > 0,循环继续。

检测下标为3的第四个字符"Z"，其前后字符均为"Z",则删除这个"Z"，得到"YZZZZ "(末尾有一个空格)，程序中i = 3 - 2 = 1 > 0，但下标为1的第二个字符"Z"前后字符不相同，所以不做删除。程序中i = 1 - 2 = -1 < 0,循环结束。进行后续操作后，得到正确明文"yzzzz"。

/**
* <h1>解密方法</h1>
* <br>String ciphertext：密文字符串(大写字母组成的字符串，长度为偶数个)
* <br>String key：密钥（小写字母组成的字符串）
* */
public String decrypt(String ciphertext, String key) {
	//处理密钥
	//将密钥中出现的'j'字符用'i'代替
	String noRepetitionKey = key.replace("j", "i");
	//得到密钥的无重复字符串
	noRepetitionKey = getNoRepetionStr(noRepetitionKey);
	//得到填充完整的全大写的矩阵一维字符串
	String matrixStr = getMatrixStr(noRepetitionKey);
	//得到一维密钥矩阵字符串中每个单元在二维5x5字符矩阵中的元数据
	MatrixUnit[] matrix = getMatrix(matrixStr);
		
	//解密
	String plaintext = decryptOperate(ciphertext, matrix);
		
	//处理解密后的明文
	plaintext = dealPlaintextAfterDecrypt(plaintext);
		
	return plaintext;
}

上面程序即为对前面那些方法的调用，形成供外部调用的同一的decrypt(String ciphertext, String key)方法接口。

---

下面是两个完整测试输出：

//测试1：
 
public static void main(String[] args) throws IOException {
		String plaintext = FileOperate.ReadIn
				("D:/programming/java/mec/java_ee/code/EncryptionAlgorithm/src/test/plaintext.txt");
		System.out.println("明文：[" + plaintext + "]");
		Playfair pf = new Playfair();
		String key = " ";
		System.out.println("密钥：[" + key + "]");
		String ciphertext = pf.encrypt(plaintext, key);
		System.out.println("加密后的密文：[" + ciphertext + "]");
		
		String plaintext1 = pf.decrypt(ciphertext, key);
		System.out.println("解密后的结果：[" + plaintext1 + "]");
}
 
 
//输出：
明文：[zzzzfhfijfhzzzzzz]
密钥：[ ]
密钥矩阵：
ABCDE
FGHIK
LMNOP
QRSTU
VWXYZ
处理后的明文：[ZZZZZZZFHFIZIFHZZZZZZZZZZZ]
加密后的密文：[VVVVVVVKIGKYKGKXVVVVVVVVVV]
解密后的结果：[zzzzfhfiifhzzzzzz]

//测试2：
 
public static void main(String[] args) throws IOException {
		String plaintext = FileOperate.ReadIn
				("D:/programming/java/mec/java_ee/code/EncryptionAlgorithm/src/test/plaintext.txt");
		System.out.println("明文：[" + plaintext + "]");
		Playfair pf = new Playfair();
		String key = "playfair";
		System.out.println("密钥：[" + key + "]");
		String ciphertext = pf.encrypt(plaintext, key);
		System.out.println("加密后的密文：[" + ciphertext + "]");
		
		String plaintext1 = pf.decrypt(ciphertext, key);
		System.out.println("解密后的结果：[" + plaintext1 + "]");
}
 
//输出：
明文：[abcdefghiiklmnopqrstuvwxyzz]
密钥：[playfair]
密钥矩阵：
PLAYF
IRBCD
EGHKM
NOQST
UVWXZ
处理后的明文：[ABCDEFGHIZIKLMNOPQRSTUVWXYZZZZ]
加密后的密文：[BHDIMPHKDUCEFGOQANCONZWXYCUUUU]
解密后的结果：[abcdefghiiklmnopqrstuvwxyzz]

---

完整代码如下：

package test;
 
import java.io.IOException;
 
import algorithm.Playfair;
import util.FileOperate;
 
public class PlayfairTest {
	public static void main(String[] args) throws IOException {
		String plaintext = FileOperate.ReadIn
				("D:/programming/java/mec/java_ee/code/EncryptionAlgorithm/src/test/plaintext.txt");
		System.out.println("明文：[" + plaintext + "]");
		Playfair pf = new Playfair();
		String key = "playfair";
		System.out.println("密钥：[" + key + "]");
		String ciphertext = pf.encrypt(plaintext, key);
		System.out.println("加密后的密文：[" + ciphertext + "]");
		
		String plaintext1 = pf.decrypt(ciphertext, key);
		System.out.println("解密后的结果：[" + plaintext1 + "]");
	}
}

package util;
 
import java.io.FileInputStream;
import java.io.IOException;
 
/**
 * @author GDUYT
 * 文件操作
 * */
public class FileOperate {
	
	/**
	 * 读取文件内容
	 * @param 明文路径地址
	 * */
	public static String ReadIn(String plaintextAdd) throws IOException {
		FileInputStream fin = new FileInputStream(plaintextAdd);
		int len;
		StringBuilder sb = new StringBuilder();
		while ((len = fin.read()) != -1) {
			sb.append((char)len);
		}
		fin.close();
		return sb.toString();
	}
	
}

//D:/programming/java/mec/java_ee/code/EncryptionAlgorithm/src/test/plaintext.txt
abcdefghiiklmnopqrstuvwxyzz

package algorithm;
 
/**
 * @author GDUYT
 * <h1>playfair加密（适用于对解密后的内容大小写不敏感，因为密文全为大写，无法得知明文的大小写情况，解密的结果全为大写或小写）</h1>
 * <h2>约定：</h2>
 * <br>（1）密钥均为小写
 * <br>（2）密钥中同时出现i和j时，用i代替j
 * <br>（3）对于明文中两个字符相同的一组字母对，在它们之间插入大写字母'Z'，然后得到的明文长度若为奇数，则在末尾增加大写字母Z
 * <br>（4）解密的结果全为小写
 * <br>（5）明文中不能有字母'j'或'J'，否则结果具有二义性，因为约定中用i代替了'j'，所以解密后的到的'I'不知道是对应'i'还是'j'
 * <br>（6）不存在明文长度为偶数时，明文从后向前数，连续地'z'或'Z'字母只有一个，因为例如明文"YZ"和"Y"加密后均为"YZ"，那么解密时具有二义性
 * <br>（7）明文中不存在一种情况：'z'或'Z'出现在第偶数位，且其前后字符为不等于‘z’或‘Z’的相同字符，但明文末尾连续多个'z'或'Z'（超过一个）可以出现。
 * */
public class Playfair {
	
	/**
	 * <h1>加密方法</h1>
	 * <br>String plaintext：明文字符串
	 * <br>String key：密钥（小写字母组成的字符串）
	 * */
	public String encrypt(String plaintext, String key) {
		//处理密钥
		//将密钥中出现的'j'字符用'i'代替
		String noRepetitionKey = key.replace("j", "i");
		//得到密钥的无重复字符串
		noRepetitionKey = getNoRepetionStr(noRepetitionKey);
		//得到填充完整的全大写的矩阵一维字符串
		String matrixStr = getMatrixStr(noRepetitionKey);
		//得到一维密钥矩阵字符串中每个单元在二维5x5字符矩阵中的元数据
		MatrixUnit[] matrix = getMatrix(matrixStr);
		System.out.println("密钥矩阵：");
		for (int i = 0; i < matrix.length; i++) {
			System.out.print(matrix[i].toString());
			if (i % 5 == 4) {
				System.out.println();
			}
		}
		
		//处理加密前的明文
		plaintext = dealPlaintextBeforeEncrypt(plaintext);
		System.out.println("处理后的明文：[" + plaintext + "]");
		
		//加密
		String ciphertext = encryptOperate(plaintext, matrix);
		return ciphertext;
	}
	
	/**
	 * <h1>解密方法</h1>
	 * <br>String ciphertext：密文字符串(大写字母组成的字符串，长度为偶数个)
	 * <br>String key：密钥（小写字母组成的字符串）
	 * */
	public String decrypt(String ciphertext, String key) {
		//处理密钥
		//将密钥中出现的'j'字符用'i'代替
		String noRepetitionKey = key.replace("j", "i");
		//得到密钥的无重复字符串
		noRepetitionKey = getNoRepetionStr(noRepetitionKey);
		//得到填充完整的全大写的矩阵一维字符串
		String matrixStr = getMatrixStr(noRepetitionKey);
		//得到一维密钥矩阵字符串中每个单元在二维5x5字符矩阵中的元数据
		MatrixUnit[] matrix = getMatrix(matrixStr);
		
		//解密
		String plaintext = decryptOperate(ciphertext, matrix);
		
		//处理解密后的明文
		plaintext = dealPlaintextAfterDecrypt(plaintext);
		
		return plaintext;
	}
	
	/**
	 * <h1>根据密文和密钥矩阵得到明文</h1>
	 * <br>String ciphertext：密文字符串(大写字母组成的字符串，长度为偶数个)
	 * <br>MatrixUnit[] matrix：密钥矩阵
	 * */
	public String decryptOperate(String ciphertext, MatrixUnit[] matrix) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < ciphertext.length(); i += 2) {
			MatrixUnit plainUnit1 = new MatrixUnit();
			MatrixUnit plainUnit2 = new MatrixUnit();
			
			//得到两个一组的密文字符在矩阵中的位置"元数据"
			for (int j = 0; j < matrix.length; j++) {
				if (ciphertext.charAt(i) == matrix[j].UnitChar) {
					plainUnit1 = matrix[j];
				}
				if (ciphertext.charAt(i+1) == matrix[j].UnitChar) {
					plainUnit2 = matrix[j];
				}
			}
			
			//根据两个一组的密文在矩阵中的相对位置对其解密
			if (plainUnit1.row == plainUnit2.row) {	//如果两个密文在同一行
				plainUnit1 = matrix[plainUnit1.row*5 + (plainUnit1.column-1+5)%5];
				plainUnit2 = matrix[plainUnit2.row*5 + (plainUnit2.column-1+5)%5];
			} else if (plainUnit1.column == plainUnit2.column) {	//如果两个密文在同一列
				plainUnit1 = matrix[((plainUnit1.row-1+5)%5)*5 + plainUnit1.column];
				plainUnit2 = matrix[((plainUnit2.row-1+5)%5)*5 + plainUnit2.column];
			} else {	//两个密文既不在同一行，也不在同一列
				MatrixUnit tempUnit = plainUnit1;
				plainUnit1 = matrix[plainUnit1.row*5 + plainUnit2.column];
				plainUnit2 = matrix[plainUnit2.row*5 + tempUnit.column];
			}
			sb.append(plainUnit1.toString() + plainUnit2.toString());
		}
		return sb.toString();
	}
	
	/**
	 * <h1>根据明文和密钥矩阵加密得到密文</h1>
	 * <br>String plaintext：处理后的明文
	 * <br>MatrixUnit[] matrix：密钥矩阵
	 * */
	private String encryptOperate(String plaintext, MatrixUnit[] matrix) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < plaintext.length(); i += 2) {
			MatrixUnit plainUnit1 = new MatrixUnit();
			MatrixUnit plainUnit2 = new MatrixUnit();
			
			//得到两个一组的明文字符在矩阵中的位置"元数据"
			for (int j = 0; j < matrix.length; j++) {
				if (plaintext.charAt(i) == matrix[j].UnitChar) {
					plainUnit1 = matrix[j];
				}
				if (plaintext.charAt(i+1) == matrix[j].UnitChar) {
					plainUnit2 = matrix[j];
				}
			}
			
			//根据两个一组的明文在矩阵中的相对位置对其加密
			if (plainUnit1.row == plainUnit2.row) {	//如果两个明文在同一行
				plainUnit1 = matrix[plainUnit1.row*5 + (plainUnit1.column+1)%5];
				plainUnit2 = matrix[plainUnit2.row*5 + (plainUnit2.column+1)%5];
			} else if (plainUnit1.column == plainUnit2.column) {	//如果两个明文在同一列
				plainUnit1 = matrix[((plainUnit1.row+1)%5)*5 + plainUnit1.column];
				plainUnit2 = matrix[((plainUnit2.row+1)%5)*5 + plainUnit2.column];
			} else {	//两个明文既不在同一行，也不在同一列
				MatrixUnit tempUnit = plainUnit1;
				plainUnit1 = matrix[plainUnit1.row*5 + plainUnit2.column];
				plainUnit2 = matrix[plainUnit2.row*5 + tempUnit.column];
			}
			sb.append(plainUnit1.toString() + plainUnit2.toString());
		}
		return sb.toString();
	}
	
	/**
	 * <h1>处理解密后的明文</h1>
	 * <br>String plaintext：解密后的明文
	 * */
	private String dealPlaintextAfterDecrypt(String plaintext) {
		
		//末尾存在字符'Z'时的处理
		//如果末尾存在字符'Z',则用空格代替它，即删除它但保留字符串长度
		if (plaintext.charAt(plaintext.length()-1) == 'Z') {
			plaintext = plaintext.substring(0, plaintext.length()-1) + " ";
		}
		
		//去除加密时连续重复字母之间加入的'Z',其特点为一定出现在偶数位上，且其前后字母相同
		for (int i = plaintext.length() - 3; i > 0; i -= 2) {
			if (plaintext.charAt(i) == 'Z' 
					&& (plaintext.charAt(i-1) == plaintext.charAt(i+1))) {
				StringBuilder sb = new StringBuilder();
				for (int j = 0; j < i; j++) {
					sb.append(plaintext.charAt(j));
				}
				for (int j = i + 1; j < plaintext.length(); j++) {
					sb.append(plaintext.charAt(j));
				}
				plaintext = sb.toString();
			}
		}
		return plaintext.toLowerCase().trim();
	}
	
	/**
	 * <h1>处理加密前的明文</h1>
	 * <br>String plaintextOperate：明文
	 * */
	private String dealPlaintextBeforeEncrypt(String plaintext) {
		//明文全部转换为小写,并用字符'i'替换字符'j'
		plaintext = plaintext.toLowerCase().replace('j', 'i');
		//对于明文中两个一样的一组字母对，在其中间插入大写字母'Z'
		for (int i = 1; i < plaintext.length(); i+=2) {
			if (plaintext.charAt(i-1) == plaintext.charAt(i)) {
				StringBuilder sb = new StringBuilder();
				for (int j = 0; j < i; j++) {
					sb.append(plaintext.charAt(j));
				}
				sb.append("Z");
				for (int j = i; j < plaintext.length(); j++) {
					sb.append(plaintext.charAt(j));
				}
				plaintext = sb.toString();
				i=1;
			}
		}
		//对于明文长度为奇数时在末尾增加大写字母'Z'
		if ((plaintext.length() % 2) == 1) {
			plaintext += "Z";
		}
		return plaintext.toUpperCase();	//将明文全部转换为大写
	}
		
	/**
	 * <h1>得到一维密钥矩阵字符串中每个单元在二维5x5字符矩阵中的行值、列值、数值</h1>
	 *<br> String matrixStr：一维的25位密钥矩阵字符串
	 * */
	private MatrixUnit[] getMatrix(String matrixStr) {
		MatrixUnit matrixUnit[] = new MatrixUnit[25];
		for (int i = 0; i < 25; i++) {
			matrixUnit[i] = new MatrixUnit(i/5, i%5, matrixStr.charAt(i));
		}
		return matrixUnit;
	}
	
	/**
	 * @author GDUYT
	 * <h1>矩阵中的每个元素单元</h1>
	 * */
	class MatrixUnit {
		
		int row;		//行值，取值空间为[0,4]
		int column;		//列值，取值空间为[0,4]
		char UnitChar;	//数值
		
		public MatrixUnit() {
		}
		
		public MatrixUnit(int row, int column, char unitChar) {
			this.row = row;
			this.column = column;
			UnitChar = unitChar;
		}
 
		@Override
		public String toString() {
			return  UnitChar + "";
		}
	}
	
	/**
	 * <h1>根据无重复密钥得到填充完整的矩阵一维字符串</h1>
	 * <br>String noRepetitionStr：无重复的小写密钥字符串
	 * */
	private String getMatrixStr(String noRepetitionKey) {
		noRepetitionKey = noRepetitionKey.toUpperCase();	//将无重复的密钥字符串全部转换为大写
		noRepetitionKey += " ";	//加空格是为了在密钥为空时也能生成矩阵
		if (noRepetitionKey.length() < 25) { //如果无重复的密钥字符串长度小于25,即没有包含所有字母（除去'J'）
			//填充密钥中未出现的字母
			for (int i = 0; i < 26 ; i++) {	
				int count = 0;
				char c = (char)('A' + i);
				for (int j = 0; j < noRepetitionKey.length(); j++) {
					if (c != noRepetitionKey.charAt(j)) {
						count++;
					}
				}
				if (count == noRepetitionKey.length()) {
					noRepetitionKey = noRepetitionKey.trim() + c;
				}
			}
			//除去填充的字符'J'
			noRepetitionKey = noRepetitionKey.split("J")[0] + noRepetitionKey.split("J")[1];
		}	
		return noRepetitionKey;//填充完整的矩阵一维字符串
	}
	
	/**
	 * <h1>得到无重复字母的字符串</h1>
	 * <br>String str：字符串 
	 * */
	private String getNoRepetionStr(String str) {
		String noRepetitionKey = " ";
		for (int i = 0; i < str.length(); i++) {
			int count = 0;
			for (int j = 0; j < noRepetitionKey.length(); j++) {
				if (str.charAt(i) != noRepetitionKey.charAt(j)) {
					count++;
				}
			}
			if (count == noRepetitionKey.length()) {
				noRepetitionKey += str.charAt(i);
			}
		}
		return noRepetitionKey.trim();
	}
}