希尔密码的破解
希尔密码(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,

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。