HILL密码——密码学
- 格式：doc
- 大小：85.00 KB
- 文档页数：8
Hill 密码Hill 体制是1929年由Lester S.Hill 发明的，它实际上就是利用了我们熟知的线性变换方法，是在26Z 上进行的。
Hill 体制的基本思想是将n 个明文字母通过线性变换转化为n 个密文字母，解密时只需做一次逆变换即可，密钥就是变换矩阵。
设明文n n Z m m m m 2621),,(∈⋯+=,密文n n Z c c c c 2621),,.,(∈⋯=，密钥为26Z 上的n n ⨯阶可逆方阵n n ij k K ⨯=)(，则26mod 26mod 1-==cK m mK c 解密：明文加密：密文具体过程：1、 假设要加密的明文是由26个字母组成，其他字符省略。
2、 将每个字符与0-25的一个数字一一对应起来。
（例如：a/A —0，b/B —1，……z/Z —25）。
3、 选择一个加密矩阵n n A ⨯，其中矩阵A 必须是可逆矩阵，例如⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=15227132102123916296101571823055117A 4、 将明文字母分别依照次序每n 个一组（如果最后一组不足n 个的话，就将其补成n个），依照字符与数字的对应关系得到明文矩阵ming n n len ⨯/。
5、 通过加密矩阵A ，利用矩阵乘法得到密文矩阵mi n n len ⨯/= ming n n len ⨯/⨯n n A ⨯mod 26；6、 将密文矩阵的数字与字符对应起来，得到密文。
7、 解密时利用加密矩阵的逆矩阵1-A 和密文，可得到明文。
实例 随机产生一个5阶加密方阵⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=15227132102123916296101571823055117A得到方阵A 的逆矩阵⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=-9131341212252318151920391211824723102141871A加密过程：输入明文：Hill cipher is one of my favorite cipher分组：Hillc ipher isone ofmyf avori tecip her(aa)加密得到密文：SKSXAQERQQYDVDGBKNVSMWZATGIAPDOJBIO解密过程：输入密文：SKSXAQERQQYDVDGBKNVSMWZATGIAPDOJBIO解密得到密文：HILLCIPHERISONEOFMYFA VORITECIPHERAA代码部分：#include <iostream>#include <string>#include <math.h>#include <stdlib.h>using namespace std;int A[1000][1000];//转化矩阵int a[1000][1000];//[A E]int B[1000][1000];//A^(-1)int ming[1000][1000];//明文矩阵int mi[1000][1000];//密文矩阵int n;//矩阵的阶数void input()//输入数据{int i, j;//cout << "请输入矩阵的元素" << endl;for( i = 1; i <= n; i++ )for( j = 1; j <= n; j++ )//cin >> A[i][j];A[i][j] = rand() % 26;memcpy( a, A, sizeof( A ) );//将矩阵A 复制给afor( i = 1; i <= n; i++ )//将矩阵变成[a E]的形式，E 为单位矩阵{for( j = n + 1; j <= 2*n; j++ ){if( i + n == j )a[i][j] = 1;elsea[i][j] = 0;}}}void output(){int i,j;cout << "矩阵阶数:" << n <<endl;cout << "矩阵A的元素:" << endl;for( i = 1; i <= n; i++ ){for( j = 1; j <= n; j++ )cout << A[i][j] << " ";cout << endl;}cout << "A矩阵的逆矩阵B为" << endl;for( i = 1; i <= n; i++ )//输出A矩阵的逆矩阵B{for( j = 1; j <= n; j++ ){B[i][j] = a[i][j+n];cout << B[i][j] << " ";}cout << endl;}}int Extend_Gcd( int a, int b, int &x, int &y )//扩展欧几里得算法{if( b == 0 ){x = 1;y = 0;return a;}int r = Extend_Gcd( b, a % b, x, y ); //a'=b;b'=a%b; a'x + b'y <=> bx + (a-a/b*b)y <=> ay + b(x-a/b*y)int t = x;x = y;y = t - a / b * y;return r;}int ni( int a)//求逆a*x=1(mod n){int x, y;int d = Extend_Gcd( a, 26, x, y );if( d == 1 )return ( x % 26 + 26 ) % 26;elsereturn -1;}int gaosi()//高斯-约当消元求A矩阵的逆矩阵B{int i, j, k;for( k = 1; k <= n; k++ )//高斯-约当消元{int Ni = ni( a[k][k] );if( Ni == -1 ) return 0;//cout << Ni << endl;for( i = k + 1; i <= 2 * n; i++ )a[k][i] = ( a[k][i] * Ni % 26 + 26 ) % 26;for( i = 1; i <= n; i++ ){if( i == k ) continue;for( j = k + 1; j <= 2 * n; j++ )a[i][j] = ( ( a[i][j] - a[i][k] * a[k][j] % 26 ) % 26 + 26 ) % 26;}}return 1;}void jiami() //加密过程{int i, j, k;char mingstr[100];char mingc;cout << "请输入明文" << endl;cin >> mingstr;//getchar();//gets( mingstr );int len = strlen( mingstr );if( len % n ){for( i = len; i < len/n*n+n; i++)mingstr[i] = 'a';mingstr[i] = '\0';}puts( mingstr );int Len = strlen( mingstr );cout << "字符串长度:" << Len << endl;for( i = 1; i <= Len/n; i++ )//将明文分成len/n段{for( j = 1; j <= n; j++ )//求每一段的明文转换为矩阵{if( mingstr[(i-1)*n+j-1] >= 'a' && mingstr[(i-1)*n+j-1] <= 'z' )ming[i][j] = mingstr[(i-1)*n+j-1] - 'a';elseming[i][j] = mingstr[(i-1)*n+j-1] - 'A';//cout << ming[i][j] << " ";}//cout << endl;}for( k = 1; k <= Len/n; k++ )//求len/n段的密文矩阵{for( i = 1; i <= n; i++ )//利用矩阵的乘法{mi[k][i] = 0;for( j = 1; j <= n; j++ )mi[k][i] = ( mi[k][i] + ming[k][j] * A[j][i] % 26 + 26 ) % 26;//cout << mi[k][i] << endl;}}cout << "密文为" << endl;for( i = 1; i <= Len/n; i++ )//输出密文{for( j = 1; j <= n; j++ ){mingc = mi[i][j] + 'A';cout << mingc;}}cout << endl;}void jiemi()//解密过程{int i, j, k;char mistr[100];char mingc;cout << "请输入密文" << endl;cin >> mistr;//getchar();//gets( mistr );//puts( mistr );int len = strlen( mistr );for( i = 1; i <= len/n; i++ )//将密文分成len/n段{for( j = 1; j <= n; j++ )//求每一段的密文转换为矩阵{if( mistr[(i-1)*n+j-1] >= 'a' && mistr[(i-1)*n+j-1] <= 'z' )mi[i][j] = mistr[(i-1)*n+j-1] - 'a';elsemi[i][j] = mistr[(i-1)*n+j-1] - 'A';}}for( k = 1; k <= len/n; k++ )//求len/n段的明文矩阵{for( i = 1; i <= n; i++ )//利用矩阵的乘法{ming[k][i] = 0;for( j = 1; j <= n; j++ )ming[k][i] = ( ming[k][i] + mi[k][j] * B[j][i] % 26 + 26 ) % 26;// cout << mi[i] << endl;}}cout << "明文为" << endl;for( i = 1; i <= len/n; i++ )//输出明文{for( j = 1; j <= n; j++ ){mingc = ming[i][j] + 'A';cout << mingc;}}cout << endl;}int main(){bool flag = 1;cout << "欢迎使用Hill体制进行加解密！" << endl;while( flag ){cout << "请输入加密矩阵的阶数n:";cin >> n;do{input();//数据输入}while( !gaosi() );output();//gaosi();//用高斯-约当消元求矩阵A%26的逆Bjiami();//加密过程jiemi();//解密过程cout << "是否继续加密解密？1：继续，0：否" << endl;cin >> flag;}return 0;}/*abcdefghijklmnopqrstuvwxyz*/。
