【文章标题】: 密码学入门系列(三) 之 希尔密码(古典)
【文章作者】: jackozoo
【作者邮箱】: jackozoo@163.com
【作者声明】: 只是感兴趣，没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
系列声明: 见(一)
希尔密码(Hill Cipher)简介: 希尔密码是基于矩阵的线性变换, 希尔密码相对于前面介绍的移位密码以及仿射密码而言, 其最大的好处就是隐藏了字符的频率信息, 使得传统的通过字频来破译密文的方法失效.
安全性: 希尔密码不是足够安全的, 如今已被证实, 关于希尔密码的破解不在本文范围内, 有兴趣的朋友可以研读相关书籍以了解相关破译方法.
希尔密码所需要掌握的前置知识:
1) 线性代数基础知识.
2) 初等数论基础知识.
坦白来说, 大部分密码学都要用到线性代数以及初等数论中的知识, 所以我希望大家可以自行找来相关书籍完成基础知识的学习, 所以关于什么是矩阵,什么是单位矩阵我不打算细讲. 在希尔密码中, 具体的话, 会涉及到矩阵的运算, 及其初等变化等.
约定:
1) 希尔密码常使用Z26字母表, 在此贴中, 我们也以Z26最为字母表进行讲解.在附带源码中有两种字母表选择.
2) 大家都知道最小的质数是2, 1 既不是质数也不是合数. 在此我们定义1对任何质数的模逆为其本身.
因为对于任意质数n, 有: 1*1 % n = 1 的. 也应该是很好理解的.
相关概念:
线性代数中的逆矩阵: 在线性代数中, 大家都知道,对于一个n阶矩阵 M , 如果存在一个n阶矩阵 N ,使得 M * N = E (其中:
E为n阶单位矩阵), 则称矩阵 N 为 矩阵 M 的逆矩阵, 并记为 M^-1.
比如 2阶矩阵 M = [3,6] , 则很容易得知其逆矩阵 :
[2,7]
M^-1 = [7/9, -2/3]
[-2/9, 1/3] .
关于这个逆矩阵是如何计算出的, 通常的有两种方法:
一是使用伴随矩阵, 通过计算行列式得到. 所用公式为: M^-1 = M^* / D . (其中M^*为M的伴随矩阵, D为M的行列式的值)
二是通过增广矩阵, 在M右侧附加一个n阶单位矩阵, 再通过初等变换将增广矩阵的左侧变换为一个n阶单位矩阵, 这时右
侧便是所求的逆矩阵.
打住!! 我们到此先打住! 我们返回到希尔密码.
希尔密码原理:
加密者在对明文加密前会选择一个加密秘匙, 这个秘匙最终会以一个m矩阵的形式参与到加密算法中的. 在加密者选定了加密秘匙后, m便得到了确定,
这时,加密者将明文按m个字母一组的形式分成多组, 最后一组不足m个字母的按特定的方式补齐. 这样就形成了很多组由m个字母组成的单个向量, 然后
对每一个m阶向量, 我们用它去乘以确定好了的秘匙.
如下为其中的一个分组A向量加密后变为B向量的过程:
[A1,A2,A3 ... Am] * M = [B1,B2,B3 ... Bm] .
我们将所有相乘后的向量连在一起, 便得到了密文. 这便是希尔密码的加密.
加密是非常简单的, 我们接下来来看一下解密部分, 解密部分要比加密部分稍微复杂一点点.
上面我们提到了矩阵的逆矩阵. 大家可能会想, 既然明文A向量乘以秘匙M矩阵就得到了密文B向量, 那么我们将B向量乘以M的逆矩阵, 不就可以得到A了吗?
大家的想法不错, 但是请注意:
我们上面的那个例子 矩阵[3,6]的逆矩阵为[7/9, -2/3] , 发现了吧, 我们如果硬是去按常规方法计算M的逆矩阵的话, 你得到的
[2,7] [-2/9, 1/3]
很可能是一个含有分式的矩阵. 这显然是不符合要求的.(为什么? )
__asm
{
cmp you, "想知道为什么"
jnz @F
]
有的人会说,就算有分式又怎么样? 虽然分式在计算机中以浮点数体现, 但我还是让B乘以这个浮点数表示的M^1, 然后对结果进行
四舍五入, 不久OK了? 不错这样是可以达到效果. 但是! 有以下几个缺点:
1): 平白无辜的扯到了浮点运算, 还要进行四舍五入, 降低了算法效率使其看起来相当愚蠢.
2): 解密秘匙体现的局限性, 其实是这个意思: 假如现在为二战时期, 我们需要派一位特工在盟军的两个司令部之间传达密钥. 而且
规定密钥只能以A~Z这26个字母的形式体现. 也即你的秘匙只能是字母构成的, 接受方得到秘匙后按照Z26表对应将A当作0,B当作1,
... Z当作25 来翻译, 然后解密. 这种情况下, 上面的分式就不好表示了. 当然在真实情况下, 密钥是怎么个传输法, 那还要区
别对待.
@@:
于是, 我们想对于一个矩阵能否有另外一种的逆使得其各元素皆为Z26范围中的元素同时可以顺利地完成解密了? 当然有.
方法一: 最小公倍数法
这种方法是在前面的矩阵逆的基础上来做文章的. 如下.
我们接着上面那个带分式的M^-1来说, 大家观察一下, 很容易知道, 其中的分母9 其实为 原矩阵M的行列式值: 9 = 3*7 - 2*6;
那我们将M^-1乘以9, 不就可以消掉分母了吗? 呵呵. 不行的.
我们要想消掉分母, 肯定得乘以一个数, 那到底要乘以多少了. 这里因为我们是Z26的字母表. 我们要保证乘以一个数之后, 原来的明文
字母所增大的部分一定得是26的整数倍. 也即如下
第一步:
设a为明文中的一个字母. x 为 需要对当前的M^-1乘以的倍数. t为任意整数.
ax = a + 26t. 恒成立. ==>> t = a(x-1)/26 .
要想t为整数, 则 x = 26p+1 .p >=1. 这里我们一般取p =1 即可. 因此 x = 27.(及字母表个数加一)
第二步:
要消掉分母, 我们必须乘以分母D(M)的倍数. 其中D(M)为M的行列式值.
得结果:
所求 x = 最小公倍数( 27, D(M) ) .
具体到上例中, x = 最小公倍数(27,9) = 27.
我们将上面的M^-1 乘以27 得到: [21, -18]
[-6, 9 ]
到了这一步, 我们得到了含负数的希尔逆矩阵.(注意: 从这里开始我们区别对待两种逆矩阵).
而负数还是不能用Z26中的字母表示, 怎么办? 没关系, 对于负数我们加上26即可. 因为我们加上的是26,
所以对于最终的取模是没有影响的. 因此我们得到:
希尔逆矩阵 M^-1 = [21,8]
[20,9]
方法二:纯整数初等变化法 (这个名字和上面那个最小公倍数法都是我自己想出来的名字, 可能不好听. 呵呵.)
这一种方法的思想就是元素的模逆. 因为我们这里是Z26, 我们不关心元素的实际大小, 只关心它对26取模后的数值.
因此, 在对原矩阵M求逆时, 我们先将M变为增广矩阵A, 再对A的每一列进行循环, 在第j列中, 从第j行开始, 每个元素
遍历, 依次检查是否对26存在模逆. 否的话, 检查下一个, 是的话,乘以其模逆, 于是该元素结果得1, 再得到其行数为 i ,
将此行与第j行互换(目的就是为了形成对角线的n个1), 然后对余下的行, 用此行乘以余下行的第j个元素的值去依次减余下的行,
这样就使得当前第j列的n-1个0得以生成. 如果某列一直检查下去都没有元素存在模逆的话, 则该矩阵M不存在希尔逆矩阵.
文字有时还是不如代码好说话, 看代码吧:
(这次的希尔密码辅助软件,我使用的是C#.我嫌用C弄一些框框太麻烦,所以选择了简单的C#,弄一些框框是为了看中间过程.
同时, 也能布置大家一个作业: 即读懂附件中的C#代码, 用C或C++重写之. 呵呵, 我想未装.NET Framework的非Vista朋友
如果为了使用附件中的bin的话, 还是得自己用其他语言重写一边的吧 (-_*,坏笑中 ~~~))
//检查元素a是否对n存在模逆
public bool CheckReverse(int a)
{
int n = (int)zt;
int p = 2;
while(p*p<n)
{
if (a%p == n%p && 0 == a%p)
{
return false;
}
p++;
}
//when a equals with 1 , it's also reversiable
return true;
}
//得到元素a对n的模逆
public int GetReverse(int a)
{
int n = (int)zt;
int q, p, t;
int x = 0, y = 1, z;
q = n;
p = a;
z = (int)q / p;
while (1 != p && 1 != q)
{
t = p;
p = q % p;
q = t;
t = y;
y = x - y * z;
x = t;
z = (int)q / p;
}
y = y % n;
if (y < 0)
{
y += n;
}
//when a equals with 1 , it return 1.
return y;
}
//使用纯整数初等变换法计算M的希尔逆矩阵.
public bool Calc_M_1()
{
int[,] A = new int[nRank, nRank * 2];
int[] T = new int[nRank*2];
int i,j,k;
//construct the [M|E] matrix A
for (i = 0; i < nRank;++i)
{
for (j = 0; j < nRank * 2;++j)
{
if (j<nRank)
{
A[i, j] = nMatrix[i, j];
}
else
{
if (nRank == j-i)
{
A[i, j] = 1;
}
else
{
A[i, j] = 0;
}
}
}
}
//begin to metamorphose A
int a_1 = 0;
for (j = 0; j < nRank;++j)
{
//step1: get one reversiable element
for (i = j; i < nRank /*+ 1*/; ++i)
{
if (CheckReverse(A[i,j]))
{
a_1 = GetReverse(A[i, j]);
for (k = 0; k < nRank * 2;++k)
{
A[i, k] *= a_1;
A[i, k] %= (int)zt;
T[k] = A[i, k];
A[i, k] = A[j, k];
A[j, k] = T[k];
}
goto step2;
}
if (nRank - 1 == i) //last element of the column, still no one is reversiable
{
return false;
}
}
step2: //create the n-1 zeros of the column
for (i = 0; i < nRank ; ++i)
{
if (i != j)
{
int t = A[i, j]; //first element of Row i .
for (k = 0; k < nRank * 2; k++)
{
A[i, k] -= t * A[j, k];
A[i, k] %= (int)zt;
if (A[i, k]<0)
{
A[i, k] += (int)zt;
}
}
}
}
}
//construct M_1
for (i = 0; i < nRank;++i)
{
for (j = 0; j < nRank;++j)
{
nDeMatrix[i,j] = A[i,j+nRank];
}
}
return true;
}
效果图:
我们来截几张图看看:
n阶希尔逆矩阵的计算:
加密测试:(注意明文中的3个O分别变为了O,S,A . 很好地隐藏了字频信息.)
总结: 大概就讲这么多吧. 附件为辅助软件和C#源码.大家可以对这源码看文章. 也希望大家指出不足之处. 谢谢.
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!
2009年05月21日 PM 11:55:39