希尔密码（原理+代码）_hill密码原理

目录

希尔密码

1、原理

2、流程图

3、编程实现

4、总结

希尔密码

1、原理

        希尔密码是一种运用基本矩阵论原理的代换密码，由Lester S. Hill在1929年发明。

        首先将字母转换为数字，将字母分成多个n维向量，跟一个n×n的矩阵相乘，再将得出的结果模26。需要注意的是密钥矩阵必须是可逆的，即矩阵的行列式和26互质。

        Hill密码能较好地抵抗统计分析法，对抗唯密文攻击的强度较高，但易受到已知明文攻击。

2、流程图

3、编程实现

        难点：如何根据密钥矩阵求密钥逆矩阵

        行列式可逆的充分条件：方阵的行列式不等于零 在这里行列式的值还需要和26互质 矩阵求逆可以使用伴随矩阵法和LU分解法

        为了减少计算量和实现难度，这里使用3*3的密钥矩阵。同时伴随矩阵法求逆一般使用下面公式

                                                                        （行列式值的逆乘以伴随矩阵）

        参考：希尔密码  矩阵求逆

        具体代码如下：

        默认输入小写英文字母明文不带空格，以及3*3的密钥矩阵存在逆矩阵且为正整数。（因为这样实现简单。。。）

        主函数：

#include"Hill.h"
 
int main() {
	while (1) {
		show();		//菜单界面
		keyDown();	//按键处理
		system("pause");
		system("cls");
	}
}

          Hill.h

#pragma once
#include<cstdio>
#include<iostream>
#include<cstring>
#include<Windows.h>
#include<vector>
using namespace std;
void init();
void show();
void keyDown();
void readFile();
void saveFile();
void encrypt();
void decrypt();
int gcd(int a, int b, int& x, int& y);
int getInv(int a, int m);
void getAntiKey(int key[][3]);

        Hill.cpp 

#include "Hill.h"
string fileStr = "";
string finalStr = "";
int x = 0, y = 0;
int antikey[3][3];//密钥的逆
int key[3][3];//密钥
/*
0 11 15
7 0 1
4 19 0
*/
void init()//初始化
{
	x = 0;
	y = 0;
	fileStr = "";
	finalStr = "";
	memset(antikey, 0, sizeof(antikey));
	memset(key, 0, sizeof(key));
}
void show()
{
	cout << "*****************希尔密码*****************" << endl;
	cout << "\t\t1.加密文件" << endl;
	cout << "\t\t2.解密文件" << endl;
	cout << "\t\t3.退出" << endl;
	cout << "******************************************" << endl;
 
}
 
void keyDown()//按键处理
{
	int userkey = 0;
	cin >> userkey;
	switch (userkey) {
	case 1:
		cout << "-----------------加密文件-----------------" << endl;
		readFile();
		encrypt();
		saveFile();
		init();
		break;
	case 2:
		cout << "-----------------解密文件-----------------" << endl;
		readFile();
		decrypt();
		saveFile();
		init();
		break;
	case 3:
		exit(0);
		break;
	}
}
 
void readFile()//读取文件
{
	cout << "请输入文件名：" << endl;
	string fileName;
	cin >> fileName;
	FILE* fp = fopen(fileName.c_str(), "r+");
	if (fp == nullptr) {
		cout << "未找到相关文件" << endl;
		return;
	}
	else {
		cout << "成功打开文件" << endl;
	}
	char ch;
	int pos = 0;
	while ((ch = fgetc(fp)) != EOF) {
		fileStr += ch;
	}
	cout << endl << "待处理的文件为：" << endl;
	cout << fileStr << endl;
	fclose(fp);
}
 
 
 
void saveFile()//保存文件
{
	string fileName;
	cout << endl << "请输入要保存信息的文件名：" << endl;
	cin >> fileName;
	FILE* fp = fopen(fileName.c_str(), "w+");
	if (fp == nullptr) {
		cout << endl << "保存文件失败" << endl;
		return;
	}
	else {
		cout << endl << "保存成功" << endl;
	}
	fprintf(fp, "%s", finalStr.c_str());
	fclose(fp);
 
}
 
void encrypt()//加密文件
{
	vector< vector<int> >  c;//明文矩阵
	vector< vector<int> >  a;//密文矩阵 
 
	if (fileStr.size() % 3 == 1)fileStr += "xx";//补充两个
	if (fileStr.size() % 3 == 2)fileStr += "x";
 
	int* m = new int[fileStr.size()];//明文按列分组并转化为数字 
 
	//分成多个3个字母的列向量
	for (int i = 0; i < fileStr.size(); i++) {
		m[i] = fileStr[i] - 'a';
	}
 
	for (int i = 0; i < fileStr.size(); i += 3) {
		vector<int> temp = { m[i],m[i + 1],m[i + 2] };
		c.push_back(temp);
	}
	cout << endl << "明文矩阵为：" << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < c.size(); j++) {
			cout << c[j][i] << " ";//明文矩阵 
		}
		cout << endl;
	}
	cout << endl;
 
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < c.size(); j++) {
			cout << char(c[j][i] + 97) << " ";//明文矩阵 
		}
		cout << endl;
	}
	cout << endl;
 
 
	cout << "请输入密钥矩阵（默认矩阵可逆且为整数）" << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> key[i][j];
		}
	}
 
	cout << endl << "按下任意键进行加密" << endl;
	char ch = getchar(); ch = getchar();
 
	//矩阵乘法
	for (int i = 0; i < c.size(); i++) {//矩阵的列数 
		vector<int> temp;
		for (int j = 0; j < 3; j++) {
			int pos = 0;
			for (int k = 0; k < 3; k++) {
				pos += key[j][k] * c[i][k];
			}
			temp.push_back((pos) % 26);
		}
		a.push_back(temp);
	}
 
	cout << "密文矩阵" << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < a.size(); j++) {
			cout << a[j][i] << " ";//密文矩阵 
		}
		cout << endl;
	}
	cout << endl;
 
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < a[0].size(); j++) {
			finalStr += char(a[i][j] + 97);
		}
	}
 
	delete[]m;
	cout << endl << "得到的密文为:" << endl;
	cout << finalStr << endl;
}
 
void decrypt()//解密文件
{
	vector< vector<int> >  c;//密文矩阵
	vector< vector<int> >  a;//明文矩阵 
 
	int* m = new int[fileStr.size()];//密文按列分组并转化为数字 
 
	//分成多个3个字母的列向量
	for (int i = 0; i < fileStr.size(); i++) {
		m[i] = fileStr[i] - 'a';
	}
 
	for (int i = 0; i < fileStr.size(); i += 3) {
		vector<int> temp = { m[i],m[i + 1],m[i + 2] };
		c.push_back(temp);
	}
 
	cout << endl << "密文矩阵为：" << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < c.size(); j++) {
			cout << c[j][i] << " ";//密文矩阵 
		}
		cout << endl;
	}
	cout << endl;
 
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < c.size(); j++) {
			cout << char(c[j][i] + 97) << " ";//密文矩阵 
		}
		cout << endl;
	}
	cout << endl;
 
 
	cout << "请输入密钥矩阵（默认矩阵可逆且为整数）" << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> key[i][j];
		}
	}
 
	getAntiKey(key);//求逆矩阵
	cout << endl << "成功求出密钥矩阵的逆" << endl;
 
	//密钥矩阵的逆矩阵
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cout << antikey[i][j] << " ";
		}
		cout << endl;
	}
 
	cout << endl << "按下任意键进行解密" << endl;
	char ch = getchar(); ch = getchar();
 
	//矩阵乘法
	for (int i = 0; i < c.size(); i++) {//矩阵的列数 
		vector<int> temp;
		for (int j = 0; j < 3; j++) {
			int pos = 0;
			for (int k = 0; k < 3; k++) {
				pos += antikey[j][k] * c[i][k];
			}
			temp.push_back((pos) % 26);
		}
		a.push_back(temp);
	}
 
	cout << "解密后的矩阵" << endl;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < a.size(); j++) {
			cout << a[j][i] << " ";
		}
		cout << endl;
	}
	cout << endl;
 
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < a[0].size(); j++) {
			finalStr += char(a[i][j] + 97);
		}
	}
	delete[]m;
	cout << endl << "得到的明文为:" << endl;
	cout << finalStr << endl;
}
 
int gcd(int a, int b, int& x, int& y)//求最大公约数
{
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	int g = gcd(b, a % b, x, y);
	int temp = x;
	x = y;
	y = temp - (a / b) * y;
	return g;
}
 
int getInv(int a, int m)//求乘法逆元
{
	gcd(a, m, x, y);
	return (x % m + m) % m;
}
 
void getAntiKey(int key[][3]) {
 
	//求行列式值 
	int v1 = key[0][0] * (key[1][1] * key[2][2] - key[1][2] * key[2][1]);
	int v2 = -key[0][1] * (key[1][0] * key[2][2] - key[2][0] * key[1][2]);
	int v3 = key[0][2] * (key[1][0] * key[2][1] - key[1][1] * key[2][0]);
	//cout<<v1<<" "<<v2<<" "<<v3<<endl;
 
	int d = (v1 + v2 + v3) % 26;
	//cout<<d<<endl;
 
	int dinv = getInv(d, 26);
	//cout<<dinv<<endl;
 
	//求伴随矩阵 
	int temp[4];
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			memset(temp, 0, sizeof(temp));
			int pos = 0;
			for (int x = 0; x < 3; x++) {
				for (int y = 0; y < 3; y++) {
					if (x != i && y != j) {
						temp[pos++] = key[x][y];
					}
				}
			}
			int cur = pow(-1, i + 1 + j + 1) * (temp[0] * temp[3] - temp[2] * temp[1]);
			antikey[j][i] = (dinv * (cur % 26 + 26)) % 26;
		}
	}
 
}

4、总结

        通过采用线性代数中的矩阵乘法运算和逆运算，能够较好地抵抗频率分析，很难被攻破。当加密矩阵的阶数n越大，破译的难度就会增大，此时计算量也大。

        希尔密码体系为破译者至少设置了三道关口，加大了破译难度。破译希尔密码的关键是猜测文字被转换成几维向量（列矩阵的行数）、所对应的字母表是怎样排列的，更为重要的是要设法获取加密矩阵A。要破解密码，向量的维数、字母的排列表和加密矩阵三者缺一不可。（百度百科）