-
-
[原创]密码学入门系列(三) 之 希尔密码(古典)
-
2009-5-21 23:56
-
【文章标题】: 密码学入门系列(三) 之 希尔密码(古典)
【文章作者】: 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存在模逆
//得到元素a对n的模逆
//使用纯整数初等变换法计算M的希尔逆矩阵.
效果图:
我们来截几张图看看:
n阶希尔逆矩阵的计算:
加密测试:(注意明文中的3个O分别变为了O,S,A . 很好地隐藏了字频信息.)
总结: 大概就讲这么多吧. 附件为辅助软件和C#源码.大家可以对这源码看文章. 也希望大家指出不足之处. 谢谢.
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!
2009年05月21日 PM 11:55:39
【文章作者】: 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
[培训]二进制漏洞攻防（第3期）；满10人开班；模糊测试与工具使用二次开发；网络协议漏洞挖掘；Linux内核漏洞挖掘与利用；AOSP漏洞挖掘与利用；代码审计。
|
|
|---|---|
|
|
|
|
|
|
|
|
 感觉没什么反响啊~~ |
|
|
|
|
|
1)
這幾天，人是少了一點。 但如 Loka 大大所說，就算是自己再複習一次囉。 2) 關於「曾经有位中国台湾人成功破解了希尔密码并获得了计算机界的诺贝尔奖 -- 图灵奖. 关于希尔密码的破解不在本文范围内」，他應該不是破解 Hill Cipher。 或許我記錯了也不一定。可否請 jackozoo 大大再 confirm 一次，如果不是的話，請把它刪了(就那幾個字)。 3) 還有一點我有點 confuse，您說【下载地址】: 自己搜索下载，是指： A) 搜索 or 找完之後，就直接轉載? B) 還是，看完那些資料後，再根據自己理解的，重新寫一個自己的版本(非抄襲)? 請問 是 A) or B)..... 4) 最後，我很感謝大家熱情參與。  謝謝。 |
|
|
|
|
|
1)
我個人認為，jackozoo 大大講的那位，會不會是 2000年圖靈獎（Turing Award）得主姚期智教授? 據我所知，他在 pseudorandom number 有很大的造詣，當然在計算機其它方面，貢獻也非常的大。 他是上海長大，大學畢業於台灣大學，雙博士學位是在美國獲得，後來回到兩岸三地的高等知名學府任教，培育優秀又有潛力的青年。 如果指的是同一人。那他應該不是 Break Hill Cipher, 但是傑出貢獻在 pseudorandom number。 3) 小的一篇拙作 「Stream Cipher + Magic Square」，裏面的 stream cipher 就是用到 pseudorandom number的技術與概念。 2) wofan 大大，小弟乃一介平民，是初學者，也是愛好者。  生也有涯，學海無涯矣。  歡迎 wofan 大大 及各位朋友們，持續熱情參與。
|
|
|
|
|
|
对(2):
的确不是破的Hill Cipher才得奖的, 失误, sorry.  对(3) (B) |
|
|
|
|
|
jackozoo 大大呀~
基本上，我的認定就是B 了。 因為這些內容都可能是要集結成冊的啊，所以我會要求嚴謹一些。  所以我才要問清楚，我也是顧及大廣大的讀者及您的權益啊。 如果您誤會了，我可真是覺得抱歉啊。 Ps. 關於「姚期智教授」是中國人那段，您怎麼把它給刪了，我對那句沒意見啊!? 他本來就是中國人。我比較 confuse 的事是，他不是破 Hill Cipher 的人，因為這樣可能會誤導讀者。 不要誤會我的意思啊。 |
|
|
常在看雪看破文的应该都知道，R大可能刚来不熟悉。
|
|
|
哈哈, 没有啦, 我也是因为他不是破Hill Cipher的人 才删掉的.
以前也是听我的一位老师说他破了Hill. 我查了下资料发现都没有提到他破Hill, 所以就把这句去掉算了. 免得有哗众取宠的感觉
|
|
|
姚期智 , 中国唯一一位获得图灵奖的人了 ~~
|
|
|
|
|
|
|
|
|
|
|
|
楼主就是牛人呀，学习了
|
|
|
|
|
|
学习
|
|
|
|
|
|
矩阵没对齐哦
|
