天天看點
傳回

古典密碼之hill密碼的加密與解密程式實作

*歡迎閱讀小明哥的部落格*

這裡主要介紹的是：古典密碼之 hill密碼加密解密過程的程式設計實作。

首先，請看對我對hill密碼做的簡單介紹。

hill密碼是古典密碼中多表代換密碼部分的重要一環，以下的介紹節選自百度，想要深入了解的請查閱書籍補充相關知識。

原理：希爾密碼(Hill Password)是運用基本矩陣論原理的替換密碼，由Lester S. Hill在1929年發明。每個字母當作26進制數字:A=0, B=1, C=2... 一串字母當成n維向量，跟一個n×n的矩陣相乘，再将得出的結果模26。注意用作加密的矩陣(即密匙)在\mathbb_^n必須是可逆的，否則就不可能譯碼。隻有矩陣的行列式和26互質，才是可逆的。

需要的知識儲備：

1)線性代數基礎知識.

2) 初等數論基礎知識.

約定：

       1)希爾密碼常使用Z26字母表，在此貼中，我們也以Z26最為字母表進行講解.在附帶源碼中有兩種字母表選擇.

2) 大家都知道最小的質數是2,1 既不是質數也不是合數. 在此我們定義1對任何質數的模逆為其本身.

因為對于任意質數n，有: 1*1 % n = 1 的. 也應該是很好了解的.

過程：

1）加密：密文=明文*密鑰矩陣  （注：明文要被分割成與密鑰維數相同的一維行列式）

2）解密：明文=密文*密鑰矩陣的逆 （注：要求與加密過程相同）

加密解密過程如下圖：

古典密碼之hill密碼的加密與解密程式實作
例：
古典密碼之hill密碼的加密與解密程式實作
古典密碼之hill密碼的加密與解密程式實作
加密過程：
古典密碼之hill密碼的加密與解密程式實作
解密：
古典密碼之hill密碼的加密與解密程式實作
古典密碼之hill密碼的加密與解密程式實作
對上述過程進行程式設計，主要的函數聲明如下： 

/*
*
*  頭檔案名稱：hillcrypto.h
*  實作檔案名稱：hillcrypto.cpp
*  項目名稱：多表代換密碼之hill密碼
*  作者：鄒明
*  完成時間：2016.3.14
*
*/

#ifndef  __HILLCRTPTO_H__
#define __HILLCRTPTO_H__

#include<iostream>
using namespace std;

#include<assert.h>
#include <iomanip>

#define ROW 4  //密鑰行數為4
#define COV 4   //密鑰列數為4

void InputKeys(float keys[ROW][COV]);   //輸入密鑰
void InputWords(char *words);        //輸入明文
void InputObwords(char *words);      //輸入密文
void PopKeys(float keys[ROW][COV]);     //輸出密鑰
void Encryption(float keys[ROW][COV], char *words, char *crypto);   //明文加密
void Decode(float keys[ROW][COV], char *words, char *crypto);     //密文解密
bool Gauss(float A[ROW][COV], float B[ROW][COV], int n);          //高斯消去法求逆矩陣
void 	ObMatrix(float a[ROW][COV], float b[ROW][COV], int n);      //求密鑰逆矩陣
void menu();   //菜單

#endif

函數實作過程中的主函數實作以及菜單函數實作如下：

/*   實作檔案名稱：hillcrypto.cpp    */
#include"hillcrypto.h"

int main()
{
	menu();   //菜單+選擇
	system("pause");
	return 0;
}

void menu()
{
	float keys[ROW][COV] = { 8, 6, 9, 5, 6, 9, 5, 10, 5, 8, 4, 9, 10, 6, 11, 4 };  //加密矩陣（預設密鑰）
	float obkeys[ROW][COV] = { 0 };  //解密矩陣 （密鑰逆矩陣）
	char words[100] = { 0 };
	char crypto[100] = { 0 };
	char obwords[100] = { 0 };
	bool flag = true;   //菜單選擇
	bool chose = false;    //密鑰選擇
	char cn = 0;
	while (flag)
	{
		int n = 0;
		cout << endl;
		cout << "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << endl;
		cout << "\t\t\t1.輸入密鑰" << endl;
		cout << "\t\t\t2.明文加密" << endl;
		cout << "\t\t\t3.密文解密" << endl;
		cout << "\t\t\t4.退出" << endl << endl;
		cout << "\t~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~" << endl;
		cout << "請選擇->：";
		cin >> n;
		switch (n)
		{
		case 1:
			system("cls");
			cout << "預設密鑰為："; 
			PopKeys(keys);
			cout << "請問您要重新輸入密鑰？ y/n" << endl << "請選擇->:";
			cin >> cn;
			if ((cn == 'y') || (cn == 'Y'))
			{
				InputKeys(keys);   //輸入密鑰
			}
			else if ((cn == 'n') || (cn == 'N'))
			{
				cout << "感謝您選擇使用預設密鑰！" << endl;
			}
			else
				cout << "輸入有誤，請重新選擇！" << endl;
			system("pause");
			break;
		case 2:
			system("cls");
			InputWords(words);  //輸入明文
			Encryption(keys, words, crypto);  //加密
			cout << "密文是->：" << crypto << endl;
			system("pause");
			break;
		case 3:
			system("cls");
			InputObwords(crypto);  //輸入密文
			ObMatrix(keys, obkeys, COV);  //計算解密矩陣
			Decode(obkeys, obwords, crypto);  //解密
			cout << "明文是->：" << obwords << endl;
			system("pause");
			break;
		case 4:
			system("cls");
			cout << endl << endl << endl;
			cout << setw(15) << "謝謝使用！" << endl;
			flag = false;
			system("pause");
			break;
		default:
			cout << "選擇有誤，請重新選擇！" << endl;
			system("pause");
			break;
		}
	}
}

輸入明文函數和輸入密文函數：

void InputWords(char *words)  //輸入明文
{
	assert(words);
	cout << "請輸入明文：";
	char *start = words;
	int flag = 1;
	getchar();
	while (flag)
	{
		*words = getchar();
		words++;
		if (*(words - 1) == '\n')
		{
			*words = '\0';
			flag = 0;
		}
	}
	words = start;
	while (*start)
	{
		if (('A' <= *start) && (*start <= 'Z'))
		{
			*words = *start;
			words++;
		}
		else if (('a' <= *start) && (*start <= 'z'))
		{
			*words = *start - 32;
			words++;
		}
		start++;
	}
	*words = '\0';
	cout << "輸入成功 ！" << endl;
}

void InputObwords(char *words)  //輸入密文
{
	assert(words);
	cout << "請輸入密文：";
	char *start = words;
	int flag = 1;
	getchar();
	while (flag)
	{
		*words = getchar();
		words++;
		if (*(words - 1) == '\n')
		{
			*words = '\0';
			flag = 0;
		}
	}
	words = start;
	while (*start)
	{
		if (('A' <= *start) && (*start <= 'Z'))
		{
			*words = *start;
			words++;
		}
		else if (('a' <= *start) && (*start <= 'z'))
		{
			*words = *start - 32;
			words++;
		}
		start++;
	}
	*words = '\0';
	cout << "輸入成功 ！" << endl;
}

輸入密鑰與輸出密鑰函數：

void InputKeys(float keys[ROW][COV])  //輸入密鑰
{
	cout << "請輸入密鑰：" << endl;
	for (size_t i = 0; i < ROW; i++)
	{
		cout << "請輸入第" << i << "行密鑰("<<ROW<<"個數):";
		for (size_t j = 0; j < COV; j++)
		{
			cin >> keys[i][j];
		}
	}
	cout << "輸入成功 !" << endl;
}

void PopKeys(float keys[ROW][COV])  //輸出密鑰
{
	cout << "密鑰為：" << endl;
	for (size_t i = 0; i < ROW; i++)
	{
		for (size_t j = 0; j < COV; j++)
		{
			cout << keys[i][j] << "   ";
		}
		cout << endl;
	}
}

加密函數：

void Encryption(float keys[ROW][COV], char *words, char *crypto)  //加密函數
{
	assert(words);
	int len = strlen(words);
	char *start = words;

	while (len > 0)
	{
		int matrix[ROW] = { 0 };
		for (int i = 0; i < ROW; i++)
		{
			if (*start)
				matrix[i] = *start - 'A';
			else
				matrix[i] = 0;
			start++;
		}
		len -= ROW;
		int cry[ROW] = { 0 };
		for (int i = 0; i < ROW; i++)
		{
			int temp = 0;
			for (int j = 0; j < COV; j++)
			{
				temp = matrix[j] * keys[j][i] + temp;
			}
			cry[i] = temp % 26;
			*crypto = 'A' + cry[i];  //計算密文
			crypto++;
		}
	}
}

解密函數，以及求逆矩陣函數：

void Decode(float obkeys[ROW][COV], char *words, char *crypto)//解密函數
{
	assert(crypto);
	int len = strlen(crypto);
	char *start = crypto;
	while (len > 0)
	{
		int matrix[ROW] = { 0 };
		for (int i = 0; i < ROW; i++)
		{
			if (*start)
				matrix[i] = *start - 'A';
			else
				matrix[i] = 0;
			start++;
		}
		len -= ROW;
		int cry[ROW] = { 0 };
		for (int i = 0; i < ROW; i++)
		{
			int temp = 0;
			for (int j = 0; j < COV; j++)
			{
				temp = matrix[j] * obkeys[j][i] + temp;
			}
			cry[i] = temp % 26;
			*words = 'A' + cry[i];  //計算明文
			words++;
		}
	}
}

void 	ObMatrix( float a[ROW][COV], float b[ROW][COV], int n)  //求逆矩陣函數
{
		int i, j;         //定義矩陣的行列式
	if (Gauss(a, b, n))
	{
		cout << "該方陣的逆矩陣為: \n";
		for (i = 0; i < n; i++)
		{
			cout << setw(4);
			for (j = 0; j < n; j++)
			{
				int temp =b[i][j]/ 1;
				float num = b[i][j] - temp;
				if (fabs(num) < 0.50)
					b[i][j] = (int)temp;
				else
					b[i][j] = temp + (int)(num * 2);
				cout << b[i][j] << setw(10);
			}
			cout << endl;
		}
	}
	cout << "逆矩陣（mod26）:" << endl;
	for (int i = 0; i < ROW; i++)
	{
		cout << setw(4);
		for (int j = 0; j < COV; j++)
		{
			if (b[i][j] >= 0)
			{
				b[i][j] = (int)b[i][j] % 26;
			}
			else
			{
				b[i][j] = 26 + (int)b[i][j] % 26;
			}
			cout << b[i][j] << setw(6);
		}
		cout << endl;
	}

}


bool Gauss(float A[ROW][COV], float B[ROW][COV], int n) //高斯消去法
{
	int i, j, k;
	float max, temp;
	float t[ROW][COV];                //臨時矩陣
	//将A矩陣存放在臨時矩陣t[n][n]中
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			t[i][j] = A[i][j];
		}
	}
	//初始化B矩陣為機關陣
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			B[i][j] = (i == j) ? (int)1 : 0;
		}
	}
	for (i = 0; i < n; i++)
	{
		//尋找主元
		max = t[i][i];
		k = i;
		for (j = i + 1; j < n; j++)
		{
			if (fabs(t[j][i]) > fabs(max))
			{
				max = t[j][i];
				k = j;
			}
		}
		//如果主元所在行不是第i行，進行行交換
		if (k != i)
		{
			for (j = 0; j < n; j++)
			{
				temp = t[i][j];
				t[i][j] = t[k][j];
				t[k][j] = temp;
				//B伴随交換
				temp = B[i][j];
				B[i][j] = B[k][j];
				B[k][j] = temp;
			}
		}
		//判斷主元是否為0, 若是, 則矩陣A不是滿秩矩陣,不存在逆矩陣
		if (t[i][i] == 0)
		{
			cout << "There is no inverse matrix!";
			return false;
		}
		//消去A的第i列除去i行以外的各行元素
		temp = t[i][i];
		for (j = 0; j < n; j++)
		{
			t[i][j] = t[i][j] / temp;        //主對角線上的元素變為1
			B[i][j] = B[i][j] / temp;        //伴随計算
		}
		for (j = 0; j < n; j++)        //第0行->第n行
		{
			if (j != i)                //不是第i行
			{
				temp = t[j][i];
				for (k = 0; k < n; k++)        //第j行元素 - i行元素*j列i行元素
				{
					t[j][k] = t[j][k] - t[i][k] * temp;
					B[j][k] = B[j][k] - B[i][k] * temp;
				}
			}
		}
	}
	return true;
}

程式運作結果：

古典密碼之hill密碼的加密與解密程式實作

選擇：1

古典密碼之hill密碼的加密與解密程式實作

選擇：y

古典密碼之hill密碼的加密與解密程式實作

選擇：n

古典密碼之hill密碼的加密與解密程式實作

選擇 2.明文加密：

古典密碼之hill密碼的加密與解密程式實作

選擇 3.密文解密：

古典密碼之hill密碼的加密與解密程式實作

選擇 4.退出：

加密解密 古典密碼 hill密碼 程式實作
上一篇: Navicat 密碼加密算法
下一篇: Atitit 資料安全 密碼學原理與概論 1.1. 密碼學方向（公鑰方向） 2 1.2. 古典密碼主要靠算法，現代靠密鑰 2 1.3. 香農三大定理 2 2. 古典密碼 2 2.1. 古典密碼

繼續閱讀