class="markdown_views prism-tomorrow-night">

Hill2密码

• Hill2密码的加密、解密、破译
• 概述
• 注意细节
• 模m逆
• 命题
• 模26倒数表
• 模m逆矩阵
• 代码实现（java）

Hill2密码的加密、解密、破译

概述

1. 选择二阶加密矩阵A
2. 将明文字母依次按每两个一组查出其表值。得到一组二维向量{åi}
3. 通过加密矩阵得到$left { eta _{i} ight }​$，而 $left { eta _{i} ight } = mathit{A}alpha _{i}left ( mod 26 ight )​$
4. 查向量$eta_i$的字母表值，及得到密文
5. 利用加密矩阵的逆矩阵，由密文得到明文$alpha _{i} = extit{A}^{-1}eta _{i}$

• 命题 整数a有m逆元 的充要条件为a与m无公共素因子
• 命题 矩阵A模m可逆<=>|A|与m无公共素因子，例子详见P6

注意细节

模m逆

​ 设$ain extit{Z}_{m}$，若存在$bin extit{Z}_{m}$使得$extit{b} = extit{a}^{-1}(mod m)$,称$a$ 有模$m$的逆，记作$b = a^{-1}(mod m)$。

命题

​ 整数 $a$有模$m$逆元的充要条件为$a$与$m$无公共素因子

模26倒数表

模m逆矩阵

代码实现（java）

使用第三方库ujmp package hill; import org.ujmp.core.Matrix; public class Hill2 { final static String table = new String("ZABCDEFGHIJKLMNOPQRSTUVWXY"); public static void main(String[] args) { String message = new String("ourmarshalwasshot"); int[][] tmp = {{1,2},{0,3}}; Matrix A = Matrix.Factory.importFromArray(tmp); Matrix Ainv = calDecodeKey(A); StringBuffer cipher = encodeORdecode(message,A); System.out.println(cipher); StringBuffer decodedMessage = encodeORdecode(cipher.toString(), Ainv); System.out.println(decodedMessage); String cipher1 = "OJWPISWAZUXAUUISEABAUCRSIPLBHAAMMLPJJOTENH"; Matrix decodeKey = Hill2attack("UCRS", "TACO"); StringBuffer plaintext = encodeORdecode(cipher1, decodeKey); System.out.print(plaintext); } /** * {@link encodeORdecode} 加密与解密过程相同，只是密钥不同。参数为输入消息，是明文或者密文， * 和加密或者解密矩阵。 * */ public static StringBuffer encodeORdecode(String message, Matrix keyAorAinv) { int[][][] messagenum; // int a; // a = extendEuclid(26, 3); messagenum = mesToArry(message,2,1); //分组为数组 Matrix[] matresult = new Matrix[messagenum.length]; //预备分组转为矩阵 int[][] numresultmp; //计算的数字结果暂存 int[] numresult = new int[messagenum.length*2]; //存放最终数字结果 Matrix[] matmessage = new Matrix[messagenum.length];//消息转对应向量 for (int i = 0; i < messagenum.length; i++) { matmessage[i]= Matrix.Factory.importFromArray(messagenum[i]);//消息数组转向量 matresult[i] = keyAorAinv.mtimes(matmessage[i]);//消息向量左乘加密矩阵 numresultmp = matresult[i].toIntArray(); //结果向量转数组并暂存 while(numresultmp[0][0]<0) { //若结果为负，变为正，加模值26 numresultmp[0][0]+=26; } while(numresultmp[1][0]<0) { //结果暂存数组存入最终结果数组 numresultmp[1][0]+=26; } numresult[i*2] = numresultmp[0][0]%26; //最终结果数组取模 numresult[i*2+1] = numresultmp[1][0]%26; } StringBuffer result = new StringBuffer(" "); //结果字符串 for (int i = 0; i < numresult.length; i++) { //数组按对应表转字符串 result.append(table.charAt(numresult[i])); } result.deleteCharAt(0); //删除开头空格 return result; //返回结果 } /** *{@link Hill2attack} 输入已知明文和已知密文，破译出解密矩阵。 * * */ public static Matrix Hill2attack(String knownCipher, String knownPlain) { Matrix decodeKey; int[][][] cipherArry = mesToArry(knownCipher,2,2); int[][][] plainArry = mesToArry(knownPlain,2,2); Matrix cipherMat = Matrix.Factory.importFromArray(cipherArry[0]); cipherMat = cipherMat.transpose(); Matrix plainMat = Matrix.Factory.importFromArray(plainArry[0]); plainMat = plainMat.transpose(); int detCipherMat = (int)cipherMat.det(); int detCipherMatinv = extendEuclid(26, detCipherMat); Matrix comCipherMat = companionMatrix(cipherMat); comCipherMat = comCipherMat.times(detCipherMatinv); comCipherMat = matModm(comCipherMat, 26); decodeKey = plainMat.mtimes(comCipherMat); decodeKey = matModm(decodeKey, 26); return decodeKey; } public static int[][][] mesToArry(String message,int rowNum, int columNum){ // 分组为几个rowNum*column的矩阵 while (message.length()%(columNum*rowNum)==1) { message = message + message.charAt(message.length()-1); } message = message.toUpperCase(); int[][][] messagenum = new int[message.length()/(columNum*rowNum)][rowNum][columNum]; for (int i = 0; i < message.length(); i++) { int tmp0 = i/(columNum*rowNum); int tmp1 = (i-(i/(columNum*rowNum))*(columNum*rowNum))/columNum; int tmp2 = (i-(i/(columNum*rowNum))*(columNum*rowNum))%columNum; messagenum[tmp0][tmp1][tmp2 ] = table.indexOf(message.charAt(i)); } return messagenum; } public static int extendEuclid(int e, int modValue){ //modValue^-1 mod e int D = 0; int x1, x2, x3, y1, y2, y3, t1, t2, t3; x1 = y2 = 1; x2 = y1= 0; x3 = e; y3 = modValue; int q = 0; while(true){ if(y3 == 1){ D = y2; break; } if(y3 == 0){ D = y2; break; } q = x3 / y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; } return D<0?e+D:D; } public static Matrix calDecodeKey(Matrix encodeKeyA) { Matrix decodeKeyAinv; int Adet = (int)encodeKeyA.det(); int AdetInv = extendEuclid(26, Adet); decodeKeyAinv = companionMatrix(encodeKeyA); decodeKeyAinv = decodeKeyAinv.times(AdetInv); decodeKeyAinv = matModm(decodeKeyAinv, 26); return decodeKeyAinv; } public static Matrix companionMatrix(Matrix A) { return A.inv().times(A.det()); } /** *{@link matModm} 是矩阵求模值的。 */ public static Matrix matModm(Matrix A, int m) { int[][] comCipherArry = A.toIntArray(); for (int i = 0; i < comCipherArry.length; i++) { for (int j = 0; j < comCipherArry[i].length; j++) { while(comCipherArry[i][j]<0) comCipherArry[i][j] += m; comCipherArry[i][j] %= m; } } Matrix AModM = Matrix.Factory.importFromArray(comCipherArry); return AModM; } }