古典密码之希尔密码Cpp源码

希尔密码介绍

希尔（Hill）密码是1929年由数学家Lester Hill发明的，加密算法将m个连续的明文字母替换成m个密文字母，并且由m个线性等式决定变换的方式。在线性等式里字母与数值一对一映射， $a\rightarrow0,b\rightarrow1,...,z\rightarrow25$ ，例如当 $m=3$ 时系统可以表示为：

$c_{1}=(k_{11}p_{1}+k_{12}p_{2}+k_{13}p_{3})mod26$ ，

$c_{2}=(k_{21}p_{1}+k_{22}p_{2}+k_{23}p_{3})mod26$ ，

$c_{3}=(k_{31}p_{1}+k_{32}p_{2}+k_{33}p_{3})mod26$

用列矢量和矩阵表示为：

$\left[ \begin{matrix} c_{1}\\ c_{2}\\ c_{3}\\ \end{matrix} \right ] = \left[ \begin{matrix} k_{11} & k_{12} & k_{13} \\ k_{21} & k_{22} & k_{23} \\ k_{31} & k_{32} & k_{33} \\ \end{matrix} \right] \left[ \begin{matrix} p_{1} \\ p_{2} \\ p_{3} \\ \end{matrix} \right] mod26$

上式可以表达为： $c=Kp mod 26$ 。

其中，c和p是长度为m的列矢量，分别代表密文和明文，K是一个 $m\times m$ 矩阵，代表加密密钥，运算按模26执行。

解密过程是加密过程的逆过程，希尔密码算法的解密过程可以表示为： $p=K^{-1}c mod 26$ ，其中 $K^{-1}$ 是加密密钥 $K$ 的逆。

希尔密码算法在实际计算中字母与数字对应的多少是根据实际情况来确定的。在很多应用算法中，加入了“，”、“？”和空格“ ”，使得解密后得到的明文可以与原来的明文一致，其映射关系见下表。

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	.	?	空格
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28

采用29个字母映射的加密方法与采用26个字母映射的计算方法是完全一致的。

希尔密码算法中涉及在模运算下计算矩阵的逆，因此，加密矩阵必须在模运算下可逆才能用于加密计算。
希尔密码算法采用的加密和解密矩阵通常为 $2\times 2$ 矩阵，解密矩阵通过计算加密矩阵在模运算下的逆获得。如果加密矩阵为： $K=\left[ \begin{matrix} a & b \\ c & d \\ \end{matrix} \right]$ ，可逆，即 $ad-bc\ne 0$ ，则其逆矩阵为：

$K^{-1}=\left[ \begin{matrix} a & b \\ c & d \\ \end{matrix} \right] ^{-1} = \frac{1}{ad-bc}\left[ \begin{matrix} d & -b \\ -c & a \\ \end{matrix} \right]$
在计算加密矩阵在模运算下的逆时，必须存在 $ad-bc$ 的乘法逆元。如果采用26个字母的映射，那么 $ad-bc$ 模26必须1,3,5,7,9,11,15,17,19,21,23或25中的一个；否则不能进行解密。

例子1：采用映射表为26个字母与数字的映射，加密矩阵为 $\left[ \begin{matrix} a & b \\ c & d \\ \end{matrix} \right]= \left[ \begin{matrix} 9 & 4 \\ 5 & 7 \\ \end{matrix} \right]$ ，试计算解密矩阵。
解： $ad-bc=9\times 7 - 4\times 5 =43\equiv 17 mod 26$ 。

由于17存在模26的乘法逆元，因此，加密矩阵的逆为： $\left[ \begin{matrix} \frac{7}{17} & \frac{-4}{17} \\ \frac{-5}{17} & \frac{9}{17} \\ \end{matrix} \right] mod 26$ 。

计算得17模26的乘法逆元为23，即 $17\times 23 =1 mod 26$ ，于是有

$\left[ \begin{matrix} \frac{7}{17} & \frac{-4}{17} \\ \frac{-5}{17} & \frac{9}{17} \\ \end{matrix} \right]mod 26 \equiv \left[ \begin{matrix} 7\times23 & -4\times23 \\ -5\times23 & 9\times23 \\ \end{matrix} \right]mod 26 \equiv \left[ \begin{matrix} 161 & -92 \\ -115 & 207 \\ \end{matrix} \right]mod 26 \equiv \left[ \begin{matrix} 5 & 12 \\ 15 & 25 \\ \end{matrix} \right]mod26$ 。

对计算结果进行验算，有：

$\left[ \begin{matrix} 9 & 4 \\ 5 & 7 \\ \end{matrix} \right] \left[ \begin{matrix} 5 & 12 \\ 15 & 25 \\ \end{matrix} \right] mod 26 \equiv \left[ \begin{matrix} 45+60 & 108+100 \\ 25+105 & 60+175 \\ \end{matrix} \right] mod 26 \equiv \left[ \begin{matrix} 105 & 208 \\ 130 & 235 \\ \end{matrix} \right] mod 26 \equiv \left[ \begin{matrix} 1 & 0 \\ 0 & 1 \\ \end{matrix} \right] mod 26$ 。

乘法逆元的计算方法参考扩展的欧几里得算法。

在程序设计过程中要注意除法问题，当存在除法时需要先计算分母的乘法逆元，将除法转换为乘法运算。否则，得不到正确的运算结果。
希尔密码算法在一般的情况下是采用二阶方阵作为加密密钥。采用二阶密钥隐蔽了明文的二元统计信息，若需要隐蔽二元以上的明文统计信息，则需要采用更高阶的方阵作为密钥。例如，有时候会采用三阶方阵作为加密密钥。

三阶以上的矩阵计算逆矩阵可以采用初等变换法或伴随矩阵法等。

例2：采用映射表为26个字母与数字的映射，加密矩阵为 $A=\left[ \begin{matrix} 1 & 2 & 3 \\ 0 & 1 & 4 \\ 5 & 6 & 0 \\ \end{matrix} \right]$ ，试采用初等变换方法计算解密矩阵。

解：

计算方法为 $[A|I]\rightarrow [I|A^{-1}]$ 。

$\left[ \begin{matrix} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 5 & 6 & 0 & 0 & 0 & 1 \\ \end{matrix} \right] \rightarrow-5r_{1}+r_{3}\rightarrow \left[ \begin{matrix} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 0 & -4 & -15 & -5 & 0 & 1 \\ \end{matrix} \right] \rightarrow 4r_{2}+r_{3}\rightarrow \left[ \begin{matrix} 1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 0 & 0 & 1 & -5 & 4 & 1 \\ \end{matrix} \right] \rightarrow-2r_{2}+r_{1}\rightarrow \left[ \begin{matrix} 1 & 0 & -5 & 1 & -2 & 0 \\ 0 & 1 & 4 & 0 & 1 & 0 \\ 0 & 0 & 1 & -5 & 4 & 1 \\ \end{matrix} \right] \rightarrow(5r_{3}+r_{1})、(-4r_{3}+r_{2})\rightarrow \left[ \begin{matrix} 1 & 0 & 0 & -24 & 18 & 5 \\ 0 & 1 & 0 & 20 & -15 & -4 \\ 0 & 0 & 1 & -5 & 4 & 1 \\ \end{matrix} \right]$

于是得到解密矩阵：

$A^{-1}=\left[ \begin{matrix} -24 & 18 & 5 \\ 20 & -15 & -4 \\ -5 & 4 & 1 \\ \end{matrix} \right]\equiv \left[ \begin{matrix} 2 & 18 & 5 \\ 20 & 11 & 22 \\ 21 & 4 & 1 \\ \end{matrix} \right] mod 26$

在本示例中， $a_{11}$ 正好为1，若为非1整数，则需要计算 $a_{11}$ 的乘法逆元，将 $a_{11}$ 转换为1，这样可以在后续计算中避免计算过多的乘法逆元，而降低计算速度。

Cpp源码

Hill.h的源码如下：

#ifndef HILL_H
#define HILL_H
#include <string>
#include <vector>

using namespace std;

struct ExtEuc{
	int d;
	int s;
	int t;
	
	ExtEuc(){
	}
	
	ExtEuc(int dd,int ss,int tt){
		d = dd;
		s = ss;
		t = tt;
	}
};

class Hill{
	private:
		int key[2][2];					//加密密钥
		int decKey[2][2];				//解密密钥
		int det;						//密钥的行列式
		string plainText;				//加密前明文
		vector<char> cipherText;		//加密后密文
		vector<char> vinText;			//临时存储明文数据
		vector<char> decText;			//解密后的文件数据
	public:
		Hill() ;
		void init();					//初始化密钥、明文
		void cutPlainText();			//分割明文存储到向量
		void getDecKey();				//获取解密密钥
		void encryption();				//加密明文
		void decryption();				//解密密文
		void showResult();				//显示计算结果
		int gcd(int n, int k);			//计算最大公因子
		ExtEuc* ExtEuclid(int a, int b);	//用于计算乘法逆元的函数
};
#endif

Hill.cpp的源码如下：

#include "Hill.h"
#include <iostream>

using namespace std;

void Hill::init(){
	int i,j;
	while(1){
		cout<<"Input the key:"<<endl;
		for(i=0;i<2;i++){
			for(j=0;j<2;j++){
				cin>>key[i][j];
			}
		}
		det=key[0][0] * key[1][1]-key[0][1] * key[1][0];
		if((det==0) | (gcd(det,26)!=1)){
			cout<<"The key can't be inversed, reinput the key!"<<endl;
		}else{
			break;
		}
	}
	getDecKey();
	cout<<"Input the plaintext:"<<endl;
	cin>>plainText; 
}

Hill::Hill(){
	init();
}

void Hill::getDecKey(){
	ExtEuc* eu;
	int inverseDet;			//det的乘法逆元 
	int i,j;
	eu=ExtEuclid(det,26);
	inverseDet=eu->s;		//获得det的乘法逆元 
	decKey[0][0]= key[1][1];
	decKey[0][1]= -key[0][1];
	decKey[1][0]= -key[1][0];
	decKey[1][1]= key[0][0];
	for(i=0;i<2;i++){
		for(j=0;j<2;j++){
			decKey[i][j]=(decKey[i][j]*inverseDet)%26;
			if(decKey[i][j]<0){
				decKey[i][j]+=26;
			}
		}
	}
}

void Hill::cutPlainText(){
	int i;
	if(plainText.length()%2==1){
		plainText+="z";
		for(i=0;i<plainText.length();i++){
			vinText.push_back(plainText[i]);
		}
	}
}

void Hill::encryption(){
	cutPlainText(); 
	int ciphText[2]={0,0};		//处理临时密文数据
	int plaiText[2]={0,0};		//处理临时明文数据
	int i,j,k;
	for(i=0; i<vinText.size(); i+=2){
		plaiText[1%2] = int(vinText[i])-int('a');
		plaiText[(i+1)%2] = int(vinText[i+1])-int('a');
		for(j=0; j<2; j++){
			for(k=0; k<2; k++){
				ciphText[j] += key[j][k] * plaiText[k];
			}
		}
		for (j=0;j<2;j++){
			ciphText[j] = ciphText[j]%26;
			cipherText.push_back(char(ciphText[j]+int('a')));
			ciphText[j]=0;		//还原临时数据
		}
	}
}
		
void Hill::decryption(){
	int ciphText[2] = {0,0};		//处理临时密文数据
	int plaiText[2] = {0,0};		//处理临时明文数据
	int i,j,k;
	for(i=0; i<cipherText.size(); i+=2){
		ciphText[i%2]= int (cipherText[i])-int('a');
		ciphText[(i+1)%2]= int(cipherText[i+1])-int('a');
		for(j=0;j<2;j++){
			for(k=0;k<2;k++){
				plaiText[j]+=decKey[j][k]*ciphText[k];
			}
		}
		for(j=0;j<2;j++){
			plaiText[j]=plaiText[j]%26;
			decText.push_back(char(plaiText[j]+int('a')));
			plaiText[j]=0;
		}
	}
}

int Hill::gcd(int n, int k){
	if(n == 0){
		return k;
	}
	if(k == 0){
		return n;
	}
	return gcd(k, n%k); 
}

ExtEuc* Hill::ExtEuclid(int a, int b){
	if(b==0){
		ExtEuc* res = new ExtEuc(a,1,0);
		return res;
	}
	
	ExtEuc* ans = ExtEuclid(b, a%b);
	int d = ans->d;
	int s = ans->t;
	int t = ans->s-(a/b)*ans->t;
	return new ExtEuc(d,s,t);
}

void Hill::showResult(){
	for (vector<char>::const_iterator i = cipherText.begin(); i != cipherText.end(); i++) {
		cout << *i;
	}
	cout<<endl;
}

main.cpp源码如下：

#include <iostream>
#include "Hill.h"

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char** argv) {
	Hill* h = new Hill();
	h->encryption();
	h->showResult();
	h->decryption();
	return 0;
}

执行效果：