用加密矩阵加密算法为a=(1 3 2 0 )的希尔密码加密明文:the sky is blue and
点击联系发帖人
时间：2015-06-10 07:55
密码学入门系列(三) 之 希尔密码(古典)
标 题：密码学入门系列(三) 之 希尔密码(古典)
作 者：jackozoo
时 间：<font color="#09-05-21 23:56:29 链 接：
【文章标题】:&密码学入门系列(三)&之&希尔密码(古典)
【文章作者】:&jackozoo
【作者邮箱】:&
【作者声明】:&只是感兴趣，没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
&&系列声明:&见(一)
&&希尔密码(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]&
&&很可能是一个含有分式的矩阵.&这显然是不符合要求的.(为什么?&)
&&&&&&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)
&&&&&&&&&&&&&&int&p&=&2;
&&&&&&&&&&&&&&while(p*p&n)
&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&if&(a%p&==&n%p&&&&&0&==&a%p)
&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&return&
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&p++;
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&//when&a&equals&with&1&,&it's&also&reversiable
&&&&&&&&&&&&&&return&
&&&&&&&&&&}
&&//得到元素a对n的模逆
public&int&GetReverse(int&a)
&&&&&&&&&&{
&&&&&&&&&&&&&&int&n&=&(int)
&&&&&&&&&&&&&&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&&&nR++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&&&nR++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)&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&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&
&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&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)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if&(A[i,&k]&0)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&A[i,&k]&+=&(int)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&//construct&M_1
&&&&&&&&&&&&&&for&(i&=&0;&i&&&nR++i)
&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&for&(j&=&0;&j&&&nR++j)
&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&nDeMatrix[i,j]&=&A[i,j+nRank];
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&return&
&&&&&&&&&&}
&&我们来截几张图看看:
&&n阶希尔逆矩阵的计算:
&&screen.width*0.6) {this.width=screen.width*0.6;this.alt='';this.onmouseover=this.style.cursor='pointer';this.onclick=function(){window.open('/picture.php?albumid=7&pictureid=78')}}" />
&&加密测试:(注意明文中的3个O分别变为了O,S,A&.&很好地隐藏了字频信息.)
&&screen.width*0.6) {this.width=screen.width*0.6;this.alt='';this.onmouseover=this.style.cursor='pointer';this.onclick=function(){window.open('/picture.php?albumid=7&pictureid=79')}}" />
&&总结:&大概就讲这么多吧.&附件为辅助软件和C#源码.大家可以对这源码看文章.&也希望大家指出不足之处.&谢谢.
--------------------------------------------------------------------------------
【版权声明】:&本文原创于看雪技术论坛,&转载请注明作者并保持文章的完整,&谢谢!
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&日&PM&11:55:39上传的附件课程主要内容第1 章 第2 章 第3 章 第4 章 第5 章 第6 章 第7 章 第8 章 第9 章 10章 第10章 密码学概述 古典密码技术 分组密码 公钥密码体制 散列函数与消息鉴别 数字签名技术 密钥管理技术 身份鉴别技术 序列密码 密码技术应用 第2章 古典密码技术本章主要内容 替代密码
置换密码 周期置换密
码 列置换密码
转轮机密码
古典密码的统计分析 单表替代密码分析 多表替代密码分析 Hill密码的已知明文分析 对Hill密码的已知明文分析2/67 第2章 古典密码技术2.1 替代密码
替代是古典密码中用到的最基本的处理技巧之一 ;
替代密码是指先建立一个替换表,加密时将需要加密 替代密码是指先建立一个替换表, 的明文依次通过查表,替换为相应的字符, 的明文依次通过查表,替换为相应的字符,明文字符 被逐个替换后,生成无任何意义的字符串,即密文, 被逐个替换后,生成无任何意义的字符串,即密文, 替代密码的密钥就是其替换表 ;
根据密码算法加解密时使用替换表多少的不同,替代 根据密码算法加解密时使用替换表多少的不同, 密码又可分为单表替代密码和多表替代密码. 密码又可分为单表替代密码和多表替代密码.
单表替代密码的密码算法加解密时使用一个固定的替 换表; 换表;
多表替代密码的密码算法加解密时使用多个替换表. 多表替代密码的密码算法加解密时使用多个替换表.3/67 第2章 古典密码技术2.1.1 单表替代密码 单表替代密码对明文中的所有字母都使用一个固定的映 射(明文 字母表到密文字母表). 字母表到密文字母表). 为包含了n 设A={a0, a1,…, an-1}为包含了n个字母的明文字母表; 为包含了 个字母的明文字母表; B={b0, b1,…, bn-1} 为包含n个字母的密文字母表,单表替 为包含n个字母的密文字母表, 代密码使用了A 的映射关系: 代密码使用了A到B的映射关系: f:A→B, f ( ai )= bj 一般情况下, 是一一映射,以保证加密的可逆性. 一般情况下,f 是一一映射,以保证加密的可逆性. 加密变换过程就是将明文中的每一个字母替换为密文字母 表的一个字母. 表的一个字母.而单表替代密码的密钥就是映射f或密文 字母表. 字母表. 经常密文字母表与明文字母表的字符集是相同的, 经常密文字母表与明文字母表的字符集是相同的,这时 的密钥就是映射f.下面给出几种典型的单表替代密码. 的密钥就是映射 下面给出几种典型的单表替代密码.4/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续)
一般单表替代密码一般单表替代密码的原理是以26个英文字母集合上的一个置换π 一般单表替代密码的原理是以26个英文字母集合上的一个置换π为 26个英文字母集合上的一个置换 密钥,对明文消息中的每个字母依次进行变换. 密钥,对明文消息中的每个字母依次进行变换. 可描述为: 都是26个英文字母的集合, 26个英文字母的集合 可描述为:明文空间M和密文空间C都是26个英文字母的集合,密 钥空间K={π:Z26→Z26|π是置换 ,是所有可能置换的集合. 是置换}, 钥空间 : 是置换 是所有可能置换的集合. 定义: 对任意π∈K,定义: 加密变换: )=c 加密变换:eπ(m)=π(m)= )= )= 解密变换:dπ(c) = π-1(c)=m, π-1是π的逆置换. 解密变换: , 的逆置换. 的逆置换 2.1】设置换π的对应关系如下: 【例2.1】设置换π的对应关系如下: a b c d e f g h i j k l m n o p q r s t u v w x y z q w e r t y u i o p a s d f g h j k l z x c v b n m 试用单表替代密码以π为密钥对明文消息message加密, message加密 试用单表替代密码以π为密钥对明文消息message加密,然后写出逆 并对密文解密. 置换 ,并对密文解密. 为密钥用单表替代密码对明文消息message加密, message加密 解:以π为密钥用单表替代密码对明文消息message加密,所得 密文消息为: 密文消息为: π(m) π(e) π(s) π(s) π(a) π(g) π(e)=dtllqut5/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续) 一般单表替代密码算法特点: 一般单表替代密码算法特点:密钥空间K很大, 破译者穷举搜索计算不可行, 微秒试 密钥空间 很大,|K|=26!=4×1026 ,破译者穷举搜索计算不可行,1微秒试 很大 一个密钥,遍历全部密钥需要10 一个密钥,遍历全部密钥需要 13 年. 移位密码体制是替换密码体制的一个特例,它仅含26个置换做为密钥空间 个置换做为密钥空间. 移位密码体制是替换密码体制的一个特例,它仅含 个置换做为密钥空间. 密钥π不便记忆 不便记忆. 密钥 不便记忆. 针对一般替换密码密钥π不便记忆的问题 不便记忆的问题, 针对一般替换密码密钥 不便记忆的问题,又衍生出了各种形式单表替代密码 .
移位密码 明文空间M,密文空间C都是和密钥空间 都是和密钥空间K满足 明文空间 ,密文空间 都是和密钥空间 满足 P = C = K = {0,1, 2,...,25} = Z 26 即把26个英文字母与整数 个英文字母与整数0, , , , 一一对应 如表2.1所示 一一对应, 所示. 即把 个英文字母与整数 ,1,2,…,25一一对应,如表 所示. 表2.1 字母数字映射表6/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续) 加密变换, 加密变换,E={E:Z26→Z26, Ek (m) = m + k (mod26)| m∈M, k∈K } 解密变换, 解密变换,D={D:Z26→Z26, Dk (c) = c-k (mod26)| c∈C, k∈K } 解密后再把Z26中的元素转换英文字母. 解密后再把 中的元素转换英文字母. 显然,移位密码是前面一般单表替代密码的一个特例.当移 显然,移位密码是前面一般单表替代密码的一个特例. 密钥k=3时,就是历史上著名的凯撒密码(Caesar) 位密码的 密钥 时 就是历史上著名的凯撒密码( ) 移位密码也称为加法密码. .根据其加密函数特 点,移位密码也称为加法密码. 仿射密码 仿射密码也是一般单表替代密码的一个特例, 仿射密码也是一般单表替代密码的一个特例,是一种线性 变换.仿射密码的明文空间和密文空间与移位密码相同, 变换.仿射密码的明文空间和密文空间与移位密码相同,但 密钥空间为 K={(k1,k2)| k1,k2∈Z26,gcd(k1,26)=1} 对任意m∈ , ∈ , 对任意 ∈M,c∈C,k = (k1,k2)∈K,定义加密变换为 定义加密变换为 c = Ek (m) = k1 m +k2 (mod 26) 相应解密变换为: 相应解密变换为: m = Dk (c) = k1-1 (c-k2) (mod 26)7/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续)m (c)=k1 (c
k 2)(mod 26) 相应解密变换为: 相应解密变换为: = D k 1 k 其中, 很明显, 时即为移位密码, 其中,1k 1 = 1mod 26 .很明显,k1=1时即为移位密码,而k2=1则称为乘法 时即为移位密码 则称为乘法 密码. 密码.12.3】设明文消息为china china, 【例2.3】设明文消息为china,密钥 k = (k 1,k 2) = (9, 2)试用仿射密码对其进行 加密,然后再进行解密. 加密,然后再进行解密. 1 利用扩展的欧几里德算法(参见附录A.1.2 A.1.2) 解:利用扩展的欧几里德算法(参见附录A.1.2)可计算出 k 1 = 3 加密变换为: 加密变换为: E k (m) = k 1m + k 2(mod 26) = 9 × m + 2(mod 26)1 解密变换为: 解密变换为: D k (c) = k 1 (c
k 2)(mod 26) = 3 × (c
2)(mod 26) = (3c
6)(mod 26)明文消息对应的数字依次为 , , , , , 明文消息对应的数字依次为2,7,8,13,0,用仿射密码对明文进行加密 消息对应的数字依次为 如下: 如下:
E k ( m ) = 9 ×
c 8/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续)密文消息为unwpc.而解密过程如下: 密文消息为unwpc.而解密过程如下: unwpc 20
h Dk (m ) = 3 ×
即恢复明文消息为china china. 即恢复明文消息为china. 仿射密码要求(k 仿射密码要求 1, 26)=1 ,否则就会有多个明文字母对应 一个密文字母的情况.由于与26互素的整数有 互素的整数有12个 一个密文字母的情况.由于与 互素的整数有 个,故仿射密码密钥空间大 小为|K|=12×26=312. 小为 × .若将仿射密码的加密函数换为多项式函数时, 若将仿射密码的加密函数换为多项式函数时,即为多项式密码.密钥短语密码选用一个英文短语或单词串作为密钥, 选用一个英文短语或单词串作为密钥,去掉其中重复的字母得到一个无 短语或单词串作为密钥 重复字母的字符串,然后再将字母表中的其它字母依次写于此字母串后, 重复字母的字符串,然后再将字母表中的其它字母依次写于此字母串后,就 可构造出一个字母替代表.如密钥为key时 替代表如表2.2所示 所示. 可构造出一个字母替代表.如密钥为 时,替代表如表 所示.9/67 第2章 古典密码技术密钥为key key的单表替代密码 表2.2 密钥为key的单表替代密码当选择上面的密钥进行加密时,若明文为 当选择上面的密钥进行加密时,若明文为&china&,则密文为 进行加密时 ,则密文为&yfgmk& . 显然,不同的密钥可以得到不同的替换表, 显然,不同的密钥可以得到不同的替换表,对于明文为英文单词或短语 的情况时,密钥短语密码最多可能有26!=4×1026个不同的替换表. 个不同的替换表. 的情况时,密钥短语密码最多可能有 ×2.1.2 多表替代密码单表替代密码表现出明文中单字母出现的频率分布与密文中相同, 单表替代密码表现出明文中单字母出现的频率分布与密文中相同, 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布,每个映射是简单替代密码中的一对一映射多表替代密码将 的频率分布, 明文字母划分为长度相同的消息单元,称为明文分组 分组, 明文字母划分为长度相同的消息单元,称为明文分组,对明文成组地进 行替代,同一个字母有不同的密文, 行替代,同一个字母有不同的密文,改变了单表替代密码中密文的唯一 使密码分析更加困难. 性,使密码分析更加困难.10/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(多表替代密码的特点是使用了两个或两个以上的替代表. 多表替代密码的特点是使用了两个或两个以上的替代表.著名的维吉 尼亚密码和Hill密码等均是多表替代密码. Hill密码等均是多表替代密码 尼亚密码和Hill密码等均是多表替代密码.1.维吉尼亚密码 1.维吉尼亚密码维吉尼亚密码是最古老而且最著名的多表替代密码体制之一,与位移 维吉尼亚密码是最古老而且最著名的多表替代密码体制之一, 密码体制相似, 维吉尼亚密码的密钥是动态周期变化的. 密码体制相似,但维吉尼亚密码的密钥是动态周期变化的. 该密码体制有一个参数n.在加解密时,同样把英文字母映射为0-25 在加解密时,同样把英文字母映射为0 的数字再进行运算, 个字母一组进行变换.明文空间, 的数字再进行运算,并按n个字母一组进行变换.明文空间,密文空间及密 P = C = K = (Z 26 ) 的英文字母串的集合, 钥空间都是长度为n的英文字母串的集合,因此可表示n加密变换定义如下: 加密变换定义如下: 明文m=(m1,m2,…,mn), 加密变换为: 加密变换为: 设密钥 k=(k1,k2,…,kn), 明文 Ek(m)=(c1,c2,…,cn), 其中c 其中 i(mi + ki)(mod26),i =1,2,…,n , 解密变换为: 对密文 c=(c1,c2,…,cn), 解密变换为: Dk(c)=(m1,m2,…,mn), 其中 mi=(ci -ki)(mod26),i =1,2,…,n11/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( =cipher,明文消息appliedcryptosystem appliedcryptosystem, 【例2.4】设密钥k =cipher,明文消息appliedcryptosystem, 2.4】 试用维吉尼亚密码对其进行加密,然后再进行解密. 试用维吉尼亚密码对其进行加密,然后再进行解密. =cipher, n=6, (2, 解:由密钥k=cipher,得n=6,密钥对应的数字序列为 (2,8, 15, 17).然后将明文按每6个字母进行分组, 15,7,4,17).然后将明文按每6个字母进行分组,并转换这 些明文字母为相应的数字,再用模26加上对应密钥数字, 26加上对应密钥数字 些明文字母为相应的数字,再用模26加上对应密钥数字,其加 密过程如表2.3所示. 2.3所示 密过程如表2.3所示.表2.3 密钥为cipher的维吉尼亚密码加密过程 密钥为cipher cipher的维吉尼亚密码加密过程密文为:cxtsmvfkgftkqanzxvo. 密文为:cxtsmvfkgftkqanzxvo. 解密使用相同的密钥,但用模26的减法代替模26加法, 26的减法代替模26加法 解密使用相同的密钥,但用模26的减法代替模26加法,这里 不再赘述. 不再赘述.12/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( 2.希尔 Hill) 希尔( 2.希尔(Hill)密码Hill密码算法的基本思想是将 个明文字母通过线性变换, Hill密码算法的基本思想是将n个明文字母通过线性变换,将它们转换为n 个密文字母. 个密文字母.解密只需做一次逆变换即可. 可逆矩阵｝ 维向量, 算法的密钥K =｛ Z 26上的 n × n 可逆矩阵｝,明文M与密文C 均为n维向量, 记为 m1
,K=(kij )n×n =
c1 = k 1 1 m 1 + k 1 2 m 2 + . . . + k 1 n m n m o d 2 6
c = k m + k m + ... + k m m o d 2 6
2 21 1 22 2 2n n
c n = k n1m 1 + k n 2 m 2 + ... + k nn m n m o d 2 6 其中, 其中,或写成C = K
M (mod 26)解密变换则为: M = K 1
C (mod 26). 解密变换则为:13/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(其中,K –1为K在模 上的逆矩阵,满足:K K –1 = K –1 K=I (mod 26) 其中, 在模26上的逆矩阵,满足: 在模 上的逆矩阵 为单位矩阵. 这里 I 为单位矩阵. 定理2.1:假设A = ( ai,j) 为一个定义在Z26上的n×n矩阵,若A 在模26上可 定理2.1:假设 为一个定义在 上的 × 矩阵, 在模 上可 2.1 矩阵 则有: 这里A 为矩阵A的伴随矩阵 逆,则有: A –1= ( det A ) –1 A* (mod 26 ) ;这里 *为矩阵 的伴随矩阵 在n = 2的情况下,有下列推论: 的情况下,有下列推论: 的情况下det A = a1,1a2,2
a1,2a2,1例如, 例如, a1,1 假设 A=
是一个Z 上的2 矩阵,它的行列式:
,是一个Z26上的2×2矩阵,它的行列式: a2,2 1 111 8
3 × 8(mod 26) = 77
24(mod 26) = 53(mod 26) = 1
3 7 a2,2 a1,2
是可逆的,那么: 是可逆的,那么: = (det A)
a2,1 a1,1 14/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(的逆矩阵为: 这时 1
1 m o d 2 6 = 1 ,所以K的逆矩阵为:K111 =
71=11 7 ×
m od 26 11 11 8 Hill密码对其 的 Hill密码对其 7设明文消息为good good, 【例 2.5】设明文消息为 good ,试用n= 2,密钥 K =
行加密,然后再进行解密. 进 行加密,然后再进行解密. 加密过程如下: 加密过程如下:将明文划分为两组:(g, (o, 14) 14, 解:将明文划分为两组:(g,o ) 和 (o,d ),即(6,14)和(14,3). c1
w = K 1= = ≡
w =K 3= = ≡
因此,good的加密结果是 显然,明文不同位置的字母& 加密成 因此,good的加密结果是wmwl.显然,明文不同位置的字母&o&加密成 的密文字母不同.为了解密, 的密文字母不同.为了解密,由前面计算有 K 1 =
7 18 ,可由密文解密计 算出明文: 算出明文:
23 11 15/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( m1
d 因此,解密得到正确的明文&good&. 因此,解密得到正确的明文&good . Hill密码特点 密码特点: Hill密码特点: 可以较好地抑制自然语言的统计特性, 可以较好地抑制自然语言的统计特性,不再有单字母替换的一一 对应关系,对抗&惟密文攻击&有较高安全强度. 对应关系,对抗&惟密文攻击&有较高安全强度. 密钥空间较大,在忽略密钥矩阵K可逆限制条件下 可逆限制条件下, 密钥空间较大,在忽略密钥矩阵 可逆限制条件下,|K|=26n×n 易受已知明文攻击及选择明文攻击(详见2.3节相关分析 节相关分析). 易受已知明文攻击及选择明文攻击(详见 节相关分析).Pad) 3.一次一密密码(One Time Pad) 一次一密密码(若替代码的密钥是一个随机且不重复的字符序列, 若替代码的密钥是一个随机且不重复的字符序列,这种密码则称为一 次一密密码,因为它的密钥只使用一次. 次一密密码,因为它的密钥只使用一次. 该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报 该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报 通信设计的一种密码,所以又称为Vernam密码.Vernam密码在对明文加密 Vernam密码 通信设计的一种密码,所以又称为Vernam密码.Vernam密码在对明文加密 前首先将明文编码为( 序列,然后再进行加密变换. 前首先将明文编码为(0,1)序列,然后再进行加密变换.16/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(设m=(m1 m2 m3 … mi …)为明文,k=(k1 k2 k3 … ki …)为密钥,其中mi,ki ∈(0,1), 为明文, 为密钥,其中 , 为明文 为密钥 i≥1, 则加密变换为: 则加密变换为: c=(c1 c2 c3 … ci …) ,其中 i = mi ⊕ ki , i≥1, 其中c 其中这里为模2加法(或异或运算) 这里为模 加法(或异或运算) 加法 解密变换为: 解密变换为: m=(m1 m2 m3 … mi …) ,其中 i = ci ⊕ ki , i≥1, 其中m 其中在应用Vernam密码时,如果对不同的明文使用不同的随机密钥,这时 密码时,如果对不同的明文使用不同的随机密钥, 在应用 密码时 Vernam密码为一次一密密码. 密码为一次一密密码 密码为一次一密密码. 由于每一密钥序列都是等概率随机产生的, 由于每一密钥序列都是等概率随机产生的,敌手没有任何信息用来对密文 进行密码分析.香农( 进行密码分析.香农(Claude Shannon)从信息论的角度证明了这种密码体 ) 制在理论上是不可破译的.但如果重复使用同一个密钥加密不同的明文, 制在理论上是不可破译的.但如果重复使用同一个密钥加密不同的明文,则 这时的Vernam密码就较为容易破译. 密码就较为容易破译. 这时的 密码就较为容易破译 若敌手获得了一个密文c=(c1 c2 c3 … ci …) 和对应明文 和对应明文m=(m1 m2 m3 … mi …) 若敌手获得了一个密文 其中k 时,就很容易得出密钥 k=(k1 k2 k3 … ki …) ,其中 i = ci ⊕ mi ,i≥1. . 故若重复使用密钥,该密码体制就很不安全. 故若重复使用密钥,该密码体制就很不安全.17/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(实际上Vernam密码属于序列密码,加密解密方法都使用模2加,这使软 实际上Vernam密码属于序列密码,加密解密方法都使用模2 Vernam密码属于序列密码 硬件实现都非常简单.但是,这种密码体制虽然理论上是不可破译的, 硬件实现都非常简单.但是,这种密码体制虽然理论上是不可破译的,然而 在实际应用中,真正的一次一密系统却受到很大的限制, 在实际应用中,真正的一次一密系统却受到很大的限制,其主要原因在于该 密码体制要求: 密码体制要求: 密钥是真正的随机序列; ① 密钥是真正的随机序列; 密钥长度大于等于明文长度; ② 密钥长度大于等于明文长度; 每个密钥只用一次(一次一密). ③ 每个密钥只用一次(一次一密). 这样,分发和存储这样的随机密钥序列, 这样,分发和存储这样的随机密钥序列,并确保密钥的安全都是很因难 另外,如何生成真正的随机序列也是一个现实问题.因此, 的;另外,如何生成真正的随机序列也是一个现实问题.因此,人们转而寻 求实际上不对攻破的密码系统. 求实际上不对攻破的密码系统.4.Playfair密码 Playfair密码Playfair密码是一种著名的双字母单表替代密码,实际上Playfair密码 Playfair密码是一种著名的双字母单表替代密码,实际上Playfair密码 密码是一种著名的双字母单表替代密码 Playfair 属于一种多字母替代密码,它将明文中的双字母作为一个单元对待, 属于一种多字母替代密码,它将明文中的双字母作为一个单元对待,并将这 些单元转换为密文字母组合. 些单元转换为密文字母组合.18/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( 替代时基于一个5 替代时基于一个5×5的字母矩阵.字母矩阵构造方法同密钥 的字母矩阵. 短语密码类似,即选用一个英文短语或单词串作为密钥, 短语密码类似,即选用一个英文短语或单词串作为密钥,去掉其 中重复的字母得到一个无重复字母的字符串, 中重复的字母得到一个无重复字母的字符串,然后再将字母表中 剩下的字母依次从左到右,从上往下填入矩阵中,字母I 剩下的字母依次从左到右,从上往下填入矩阵中,字母I,j占同 一个位置. 一个位置. 例如,密钥K= cipher, 例如,密钥K= playfair is a digram cipher,去除重复字 母后,K=playfirsdgmche,可得字母矩阵如图2.1 2.1. 母后,K=playfirsdgmche,可得字母矩阵如图2.1.Playfair密码字母矩阵示例 图2.1 Playfair密码字母矩阵示例19/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( 对每一明文字母对P1,P2的加密方法如下: 对每一明文字母对P1,P2的加密方法如下: P1 的加密方法如下 P1,P2在同一行 密文C1 C2分别是紧靠P1,P2右 在同一行, C1, 分别是紧靠P1 (1)若P1,P2在同一行,密文C1,C2分别是紧靠P1,P2右 端的字母; 端的字母; P1,P2在同一列 密文C1 C2分别是紧靠P1,P2下 在同一列, C1, 分别是紧靠P1 (2)若P1,P2在同一列,密文C1,C2分别是紧靠P1,P2下 方的字母; 方的字母; P1,P2不在同一行 也不在同一列, C1,C2是由 不在同一行, (3)若P1,P2不在同一行,也不在同一列,则C1,C2是由 P1,P2确定的矩形其它两角的字母 确定的矩形其它两角的字母, C1和P1在同一行 在同一行, P1,P2确定的矩形其它两角的字母,且C1和P1在同一行, C2和P2在同一行 在同一行; C2和P2在同一行; P1=P2,则两个字母间插入一个预先约定的字母, (4)若P1=P2,则两个字母间插入一个预先约定的字母, 并用前述方法处理; 如x,并用前述方法处理; balloon,则以ba 来加密. 如balloon,则以ba lx lo on 来加密. 若明文字母数为奇数,则在明文尾填充约定字母. (5)若明文字母数为奇数,则在明文尾填充约定字母. 算法还约定字母矩阵中第一列看做最后一列的右边一列, 算法还约定字母矩阵中第一列看做最后一列的右边一列, 表中第一行看做最后一行的下一行. 表中第一行看做最后一行的下一行.20/67 第2章 古典密码技术2.2 置换密码 ( Permutation Cipher )置换密码又称为换位密码; 置换密码又称为换位密码; 置换密码通过改变明文消息各元素的相对位置, 置换密码通过改变明文消息各元素的相对位置,但明文消息元素本身 的取值或内容形式不变; 的取值或内容形式不变; 在前面的替代密码中,则可以认为是保持明文的符号顺序, 在前面的替代密码中,则可以认为是保持明文的符号顺序,但是将它 们用其它符号来替代; 们用其它符号来替代; 这种密码是把明文中各字符的位置次序重新排列来得到密文的一种密 码体制.实现的方法多种多样.直接把明文顺序倒过来, 码体制.实现的方法多种多样.直接把明文顺序倒过来,然后排成固 定长度的字母组作为密文就是一种最简单的置换密码. 定长度的字母组作为密文就是一种最简单的置换密码. 下面再给出几种典型的置换密码算法. 下面再给出几种典型的置换密码算法.2.2.1 周期置换密码周期置换密码是将明文字符按一定长度n分组,把每组中的字符按1 周期置换密码是将明文字符按一定长度n分组,把每组中的字符按1, 2,…,n的一个置换π重排位置次序来得到密文的一种加密方法. , 的一个置换π重排位置次序来得到密文的一种加密方法. 其中的密钥就是置换π 的描述中包含了分组长度的信息. 其中的密钥就是置换π,在π的描述中包含了分组长度的信息.
1 解密时,对密文字符按长度n分组,并按π 解密时,对密文字符按长度n分组,并按π的逆置换π 把每组字符重排 位置次序来得到明文. 位置次序来得到明文. 周期置换密码可描述为: 周期置换密码可描述为:21/67 第2章 古典密码技术周期置换密码( 2.2.1 周期置换密码(续)为固定的正整数, K是由 {1, 设n为固定的正整数,P = C = (Z26)n , K是由 {1,2,…,n} 的所有 , 置换构成.对一个密钥π∈K 定义: π∈K, 置换构成.对一个密钥π∈K,定义: 加密变换: 加密变换: Eπ (m1, m2,.., mn) = (mπ(1),..., mπ(n)) =( c1, c2,.., cn) 解密变换: 解密变换: π (c1 , c2 ,..., cn ) = (c Dπ1cπ 1 (2) ......cπ 1 ( n ) ) ;这里π-1为π的逆置换 (1)1 2 3 4 5 6
3 6 1 5 2 4注意,这里的加密与解密变换仅仅用了置换,无代数运算. 注意,这里的加密与解密变换仅仅用了置换,无代数运算.【例2.7】给定明文为 明文为cryptography,试用密钥 】 ,试用密钥π= = (3 5 1 6 4 2)的置换密码对其进行加密,然后再对密文进 的置换密码对其进行加密, 的置换密码对其进行加密 行解密. 行解密. 对明文分组, 解:密钥长度是6,所以按周期长度 对明文分组,对每组字 密钥长度是 ,所以按周期长度6对明文分组 母用密钥π 进行重排得到对应的加密结果. 母用密钥 进行重排得到对应的加密结果. 明文分组为: 明文分组为:crypto|graphy,再利用置换密钥 进行加密变 ,再利用置换密钥π进行加密变 换,得:Eπ (crypto) = (ytcopr); Eπ (graphy) = (ahgypr) 即密文消息为ytcoprahgypr. 即密文消息为 .22/67 第2章 古典密码技术2.2.1周期置换密码(续) 周期置换密码(1 1显然由加密置换可求出逆置换, 4), ),根 显然由加密置换可求出逆置换, π =(3 6 1 5 2 4),根 即可直接明文. 据密文和逆置换 π 即可直接明文. 必须要指出的是,置换密码在实质上是Hill密码的特例, Hill密码的特例 必须要指出的是,置换密码在实质上是Hill密码的特例,下面给出 分析. 分析. 给定一个集合{1 {1, .,n}的置换 的置换π 写出置换矩阵为: 给定一个集合{1,2, . . .,n}的置换π,写出置换矩阵为:Kπ = (kij )n×n 1 若j = π (i) kij =
否则 0;表示仅第 i 行中第π(i)个元素为1, 其余为零.这时,置换矩阵是每一行和每一列都刚好有一个 这时,置换矩阵是每一行和每一列都刚好有一个&1&,而其余元素为 , π &0&的稀疏矩阵.如例2.7的加解密置换π=(3 5 1 6 4 2), 的稀疏矩阵. 2.7的加解密置换 2), = 的稀疏矩阵 如例2.7的加解密置换π=(3 ( 0 4),对应的置换矩阵为: ),对应的置换矩阵为 3 6 1 5 2 0 41 0 0对应的置换矩阵为: 0 0 1 0 0 0 ), 010
00 0 0 1 0
0 0 0 0 1 0 0 1 0 0
1 0 0 0 0K π 10
00 0 0 0 1
0 0 0 1 0 1 0 0 0 0
0 0 1 0 023/67 第2章 古典密码技术2.2.1周期置换密码(续) 周期置换密码(E 加密变换: π 加密变换: (M)=E π (m1,m 2,...m n) = (m π (1),...,m π ( n )) = K π i M = (c1,c 2,...c n ) 解密变换: 解密变换: π (C ) = Dπ ( c1 , c2 ,..., cn ) = ( cπ 1 (1) cπ 1 ( 2 ) ......cπ 1 ( n ) ) D= 所以,置换密码实质上是输入分组的一个线性变换. 所以,置换密码实质上是输入分组的一个线性变换.K π 1 i C = M24/67 第2章 古典密码技术2.2.2列置换密码这种密码的加密方法就是将明文按行填写到一个列宽固定(设为m)的 这种密码的加密方法就是将明文按行填写到一个列宽固定( 的一个置换π 表格或矩阵中;然后按( 表格或矩阵中;然后按(1,2,…,m)的一个置换π交换列的位置次 再按列读出即得密文. 序,再按列读出即得密文. 解密时,将密文按列填写到一个行数固定( 的表格或矩阵中, 解密时,将密文按列填写到一个行数固定(也为m)的表格或矩阵中, 按置换π的逆置换交换列的位置次序,然后按行读出即得到明文. 按置换π的逆置换交换列的位置次序,然后按行读出即得到明文.置换 可看成是算法的密钥. π可看成是算法的密钥. 2.8略 参见课本, 例2.8略,参见课本, 请读者思考, 2.8列置换密码中 列置换密码中, 请读者思考,在例2.8列置换密码中,如果明文字母的长度不是列宽m的 整倍数,加解密时会有什么问题,应如何处理? 整倍数,加解密时会有什么问题,应如何处理? 由于置换密码只需打乱原明文字符的排列顺序形成乱码来实现加密变换 ,因此,置换的方法还有很多,例如,图形置换密码就是先按一定的方向把 因此,置换的方法还有很多,例如, 明文输入到某种预先规定的图形中,再按另一种方向输出密文字符, 明文输入到某种预先规定的图形中,再按另一种方向输出密文字符,不足部 分填入随机字符,这里就不一一列举了. 分填入随机字符,这里就不一一列举了.25/67 第2章 古典密码技术2.3 转轮机密码转轮机的基本结构由一个键盘,若干灯泡和一系列转轮组成,如图1.4 1.4( 转轮机的基本结构由一个键盘,若干灯泡和一系列转轮组成,如图1.4( 所示.键盘一共有26个键,键盘上方就是标示了字母的26个小灯泡, 26个键 26个小灯泡 a)所示.键盘一共有26个键,键盘上方就是标示了字母的26个小灯泡,当键 盘上的某个键被按下时, 盘上的某个键被按下时,与这个字母被加密后的密文字母所对应的小灯泡就亮 了起来.在显示器的上方是几个转轮,每个转轮是26个字母的任意组合. 26个字母的任意组合 了起来.在显示器的上方是几个转轮,每个转轮是26个字母的任意组合. 如图2.2是一个三转轮的原理示意图,图中3个矩形框代表3个转轮, 2.2是一个三转轮的原理示意图 如图2.2是一个三转轮的原理示意图,图中3个矩形框代表3个转轮,从左到 右分别称为慢转子,中转子和快转子.每个转轮有26个输入引脚和26 26个输入引脚和26个输出引 右分别称为慢转子,中转子和快转子.每个转轮有26个输入引脚和26个输出引 其内部连线将每个输入引脚连接到一个对应的输出引脚, 脚,其内部连线将每个输入引脚连接到一个对应的输出引脚,这样每个转轮内 部相当于一个单表替代.当按下某一键时,电信号从慢转子的输入引脚进入, 部相当于一个单表替代.当按下某一键时,电信号从慢转子的输入引脚进入, 通过内部连线经过每个转轮, 通过内部连线经过每个转轮,最后从快转子的输出引脚信号输出对应密文字母 点亮).例如,在图2.2 ).例如 2.2( 如果按下字母B (点亮).例如,在图2.2(a)中,如果按下字母B,则相应电信号被加到慢 转子的输入引脚25 并通过内部连线连接到慢转子的输出引脚25 25, 25, 转子的输入引脚25,并通过内部连线连接到慢转子的输出引脚25,经过中转子 的输入引脚22和输出引脚22 连接到快转子的输入引脚13 22和输出引脚22, 13, 的输入引脚22和输出引脚22,连接到快转子的输入引脚13,最后从快转子的输 出引脚13输出密文字母( 13输出密文字母 出引脚13输出密文字母(I).26/67 第2章 古典密码技术 如果转轮密码机始终保持图2.2( 如果转轮密码机始终保持图2.2(a)的连接状态,则按下字母键B,输出的 2.2 的连接状态,则按下字母键B 密文字母始终是I 按下字母键A 输出的密文字母则始终是B 等等), ),转轮 密文字母始终是I(按下字母键A,输出的密文字母则始终是B,等等),转轮 密码机为了能够实现复杂的多表替代密码, 密码机为了能够实现复杂的多表替代密码,打破明文与密文之间固定的替代关 在每次击键输出密文字母后,快转子都要转动一个位置, 系,在每次击键输出密文字母后,快转子都要转动一个位置,以改变中转子与 快转子之间的对应关系.例如,在图2.2 2.2( 的初始状态下, 快转子之间的对应关系.例如,在图2.2(a)的初始状态下,如果按下任意一 个键( 转轮密码机输出密文字母( 键对应密文字母为I),然后 个键(如B键)后,转轮密码机输出密文字母(B键对应密文字母为I),然后 快转子转动一个位置,即快转子的所有引脚向下循环移动一个位置, 快转子转动一个位置,即快转子的所有引脚向下循环移动一个位置,此时转轮 密码机的状态如图2.2 2.2( 所示.显然,这时若再按下B 密码机的状态如图2.2(b)所示.显然,这时若再按下B键,最后从快转子输 出的密文变为字母Q 而不是上一次的字母I 出的密文变为字母Q,而不是上一次的字母I. 转轮密码机的每个转子都有可能转动,当快转子转动26次后, 转轮密码机的每个转子都有可能转动,当快转子转动26次后,中转子就转动 26次后 一个位置;当中转子转动26次后,慢转子就转动一个位置.因此,在加密( 26次后 一个位置;当中转子转动26次后,慢转子就转动一个位置.因此,在加密(或 解密)26×26×26=17576个字母后 所有转轮就会恢复到初始状态. 个字母后, 解密)26×26×26=17576个字母后,所有转轮就会恢复到初始状态.也就是 的多表替代密码.实际上, 说,有n个转轮的转轮密码机是一个周期长度为 26 的多表替代密码.实际上, 转轮密码机还利用了键盘和第一个转子之间的连接板实现的简单替换, 转轮密码机还利用了键盘和第一个转子之间的连接板实现的简单替换,以增加 输出的可能性来对抗穷举破译法,其详细过程这里就不再赘述. 输出的可能性来对抗穷举破译法,其详细过程这里就不再赘述.n27/67 A 24 21 B 25 03 C 26 15 D 01 01 E 02 19 F 03 10 G 04 14 H 05 26 I 06 20 J 07 08 K 08 16 L 09 07 M 10 22 N 11 04 O 12 11 P 13 05 Q 14 17 R 15 09 S 16 12 T 17 23 U 18 18 V 19 02 W 20 25 X 21 06 Y 22 24 Z 23 慢 1326 20 01 01 02 06 03 04 04 15 05 03 06 14 07 12 08 23 09 05 10 16 11 02 12 22 13 19 14 11 15 18 16 25 17 24 18 13 19 07 20 10 21 08 22 21 23 09 24 26 25 中 1701 08 02 18 03 26 04 17 05 20 06 22 07 10 08 03 09 13 10 11 11 04 12 23 13 05 14 24 15 09 16 12 17 25 18 16 19 19 20 06 21 15 22 21 23 02 24 07 25 01 26 快 14A B C D E F G H I J K L M N O P Q R S T U V W X Y ZA→B B→I C→E ……A→E B→Q C→T ……A 24 21 B 25 03 C 26 15 D 01 01 E 02 19 F 03 10 G 04 14 H 05 26 I 06 20 J 07 08 K 08 16 L 09 07 M 10 22 N 11 04 O 12 11 P 13 05 Q 14 17 R 15 09 S 16 12 T 17 23 U 18 18 V 19 02 W 20 25 X 21 06 Y 22 24 Z 23 慢 1326 20 01 01 02 06 03 04 04 15 05 03 06 14 07 12 08 23 09 05 10 16 11 02 12 22 13 19 14 11 15 18 16 25 17 24 18 13 19 07 20 10 21 08 22 21 23 09 24 26 25 中 1726 14 01 08 02 18 03 26 04 17 05 20 06 22 07 10 08 03 09 13 10 11 11 04 12 23 13 05 14 24 15 09 16 12 17 25 18 16 19 19 20 06 21 15 22 21 23 02 24 07 25 快 01A B C D E F G H I J K L M N O P Q R S T U V W X Y Z初始设置在一次击键后的设置 第2章 古典密码技术使用转轮密码机通信时, 使用转轮密码机通信时,发送方首先要调节各个转轮的 位置(这个转轮的初始位置就是密钥), ),然后依次键入 位置(这个转轮的初始位置就是密钥),然后依次键入 明文,并把显示器上灯泡闪亮的字母依次记下来, 明文,并把显示器上灯泡闪亮的字母依次记下来,最后 把记录下的闪亮字母按照顺序用正常的电报方式发送出 去; 接收方收到电文后,只要也使用同样一台转轮机, 接收方收到电文后,只要也使用同样一台转轮机,并按 照原来的约定, 照原来的约定,把转轮的位置调整到和发送方相同的初 始位置上,然后依次键入收到的密文, 始位置上,然后依次键入收到的密文,显示器上自动闪 亮的字母就是明文了. 亮的字母就是明文了.29/67 第2章 古典密码技术2.4 古典密码的统计分析在对密码进行安全分析时,一般假设密码分析者知道密码体制,这就是 在对密码进行安全分析时,一般假设密码分析者知道密码体制, Kerckhoffs假设,密码分析重点在获取密钥. Kerckhoffs假设,密码分析重点在获取密钥. 假设 移位密码,仿射密码,维吉尼亚密码,置换密码等对己知明文攻击都是 移位密码,仿射密码,维吉尼亚密码, 非常脆弱的.即使用惟密文攻击,大多数古典密码体制都容易被攻破.大多 非常脆弱的.即使用惟密文攻击,大多数古典密码体制都容易被攻破. 数古典密码体制都不能很好隐藏明文消息的统汁特征. 数古典密码体制都不能很好隐藏明文消息的统汁特征. 下面就针对单表替代密码,多表替代密码和Hill密码来介绍利用英文语 下面就针对单表替代密码,多表替代密码和Hill密码来介绍利用英文语 Hill 言的统计特征和密码特点,运用惟密文攻击或已知明文攻击等方式破译古典 言的统计特征和密码特点, 密码的基本方法. 密码的基本方法.2.4.1 单表替代密码分析对于单表替代密码,加法密码和乘法密码的密钥量比较小, 对于单表替代密码,加法密码和乘法密码的密钥量比较小,可利用穷举 密钥的方法进行破译.仿射密码,多项式密码的密钥量也只有成百上千, 密钥的方法进行破译.仿射密码,多项式密码的密钥量也只有成百上千,古 代密码分析者企图用穷举全部密钥的方法破译密码可能会有一定困难, 代密码分析者企图用穷举全部密钥的方法破译密码可能会有一定困难,然而 计算机出现后这就很容易了. 计算机出现后这就很容易了.30/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 本质上,密文字母表是明文字母表的一种排列. 本质上,密文字母表是明文字母表的一种排列.但企 图使用计算机穷举一切密钥来破译密钥词组替代密码也 是计算不可行的. 是计算不可行的. 穷举不是攻击密码的惟一方法, 穷举不是攻击密码的惟一方法,密码分析者便可利 用语言的统计特性进行分析. 用语言的统计特性进行分析.如果明文语言的这种统计 特性在明文中有所反映, 特性在明文中有所反映,密码分析者便可通过分析明文 和密文的统计规律而破译密码. 和密文的统计规律而破译密码. 通过对大量英文语言的研究可以发现, 通过对大量英文语言的研究可以发现,每个字母出现 的频率不一样, 出现的频率最高. 的频率不一样,e出现的频率最高.如果所统计的文献足 够长,便可发现各字母出现的频率比较稳定.如表2.4 2.4所 够长,便可发现各字母出现的频率比较稳定.如表2.4所 示(表中字母出现频率为字母出现次数除以文本字母总 数).31/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)表2.4 26个英文字母出现频率统计表 26个英文字母出现频率统计表字母 a b c d e f g h i j k l m出现频率 0.9 0.8 0.9 0.8 0.3 0.9 0.0249字母 n o p q r s t u v w x y z出现频率 0.7 0.2 0.7 0.9 0.9 0.9 0.000832/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)通过对26个英文字母出现频率的分析,可以有以下结果: 通过对26个英文字母出现频率的分析,可以有以下结果: 26个英文字母出现频率的分析出现的频率最大,约为0.13 0.13; (1)e出现的频率最大,约为0.13; (2)t,a,o,i,n,s,h,r出现的频率约在0.06～0.1之 出现的频率约在0.06～0.1之 0.06 间; 出现的频率在0.04附近; 0.04附近 (3)d,l出现的频率在0.04附近; 出现的频率约在0.015 0.015～ (4)c,u,m,w,f,g,y,p,b出现的频率约在0.015～ 0.029之间 之间; 0.029之间; 出现的频率小于0.01 0.01. (5)v,k,j,x,q,z出现的频率小于0.01.在密码分析中,除了考虑单字母统计特性外,掌握双字母, 在密码分析中,除了考虑单字母统计特性外,掌握双字母,三字母的 统计特性以及字母之间的连缀关系等信息也是很有用的. 统计特性以及字母之间的连缀关系等信息也是很有用的. 出现频率最高的30个双字母组合依次是: 30个双字母组合依次是 出现频率最高的30个双字母组合依次是:th he stin ener atan tore nted haones33/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)nd ou ea ng as et it ar te se 出现频率最高的20个三字母组合依次是: 20个三字母组合依次是 出现频率最高的20个三字母组合依次是: the ere was hat his ing ent eth she sth and tha for ion ers or hi ti of her nth dth int ver is 特别的,the出现的频率几乎是ing的3倍,这在密码分析中很有用.此 特别的,the出现的频率几乎是ing的 出现的频率几乎是ing 这在密码分析中很有用. 统计资料还表明:英文单词以e 字母结尾的超过一半. 外,统计资料还表明:英文单词以e,s,d,t字母结尾的超过一半.英 文单词以t 为起始字母的约占一半. 文单词以t,a,s,w为起始字母的约占一半.
以上这些统计数据是通过非专业性文献中的字母进行统计得到的.对于 以上这些统计数据是通过非专业性文献中的字母进行统计得到的. 密码分析者来说,这些都是十分有用的信息.除此之外, 密码分析者来说,这些都是十分有用的信息.除此之外,密码分析者对 明文相关知识的掌握对破译密码也是十分重要的. 明文相关知识的掌握对破译密码也是十分重要的.34/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)字母和字母组的统计数据对于密码分析者是十分重要的. 字母和字母组的统计数据对于密码分析者是十分重要的.因为它们可以 提供有关密钥的许多信息. 提供有关密钥的许多信息. 对于字母e比其它字母的频率都高得多,如果是单表替代密码, 对于字母e比其它字母的频率都高得多,如果是单表替代密码,可以预 计大多数密文都将包含一个频率比其它字母都高的字母. 计大多数密文都将包含一个频率比其它字母都高的字母.当出现这种情况 猜测这个字母所对应的明文字母为e 时,猜测这个字母所对应的明文字母为e,进一步比较密文和明文的各种统 计数据及其分布,便可确定出密钥,从而破译单表替代密码. 计数据及其分布,便可确定出密钥,从而破译单表替代密码. 下面通过一个具体实例来说明如何借助于英文语言的统计规律来破译单 表替代密码.该例子取自参考文献[1] [1]. 表替代密码.该例子取自参考文献[1]. 2.9】设某一段明文经单表替代密码加密后的密文如下, 【例2.9】设某一段明文经单表替代密码加密后的密文如下, YIFQ FMZR WQFY VECF MDZP CVM R ZWNM DZVE JBTX CDDUMJ NDIF EFMD ZCDM QZKC EYFC JMYR NCWJ CSZR EXCH ZUNMXZ NZUC DRJX YYSM RTMEYIFZ WDYV ZVYF ZUMR ZCRW NZDZJJ XZWG CHSM RNMD HNCM FQCH ZJMX JZWI EJYU CFWD JNZDIR 试分析出对应密文.为了表述更加清楚,本例的密文用大写字母, 试分析出对应密文.为了表述更加清楚,本例的密文用大写字母,明文 用小写字母. 用小写字母.35/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)将加密变换记为Ek 解密变换记为Dk 密文中共有168个字母. Ek, Dk, 168个字母 解:将加密变换记为Ek,解密变换记为Dk,密文中共有168个字母. 第一步:统计密文中各个字母的出现次数和频率,如表2.5所示. 2.5所示 第一步:统计密文中各个字母的出现次数和频率,如表2.5所示.表2.5 例2.9中各个密文字母的出现次数和频率 2.9中各个密文字母的出现次数和频率36/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)第二步:从出现频率最高的几个字母及双字母组合,三字母组合开始, 第二步:从出现频率最高的几个字母及双字母组合,三字母组合开始, 并假定它们是英语言中出现频率较高的字母及字母组合对应的密文, 并假定它们是英语言中出现频率较高的字母及字母组合对应的密文,逐步推测 各密文字母对应的明文字母. 各密文字母对应的明文字母. 从表2.5可以看出,密文字母Z出现的次数高于任何其他密文字母,出现 从表2.5可以看出,密文字母Z出现的次数高于任何其他密文字母, 2.5可以看出 频率约为0.12 因此,可以猜测: 0.12. 出现至少10 10次的密文字母 频率约为0.12.因此,可以猜测:D K ( Z ) = e,除Z外,出现至少10次的密文字母 它们的出现频率约在0.06 0.095之间 因此, 0.06～ 之间. 为C,D,F,J,M,R,Y,它们的出现频率约在0.06～0.095之间.因此,可以 猜测密文字母{C {C, Y}可能对应于明文字母集合{t, 可能对应于明文字母集合{t 猜测密文字母{C,D,F,J,M,R,Y}可能对应于明文字母集合{t,a,o,i, 中的字母,但不能肯定是哪一个. n,s,h,r} 中的字母,但不能肯定是哪一个. 因为已经假设密文Z解密成e,现在考虑密文中形如-Z和Z-的双字母的出 因为已经假设密文Z解密成e 现在考虑密文中形如- 现情况, 的双字母情况如表2.6所示. 2.6所示 现情况,Z的双字母情况如表2.6所示.37/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)表2.6 例2.9密文中包含字母Z的双字母出现次数 2.9密文中包含字母Z 密文中包含字母从表2.6可以发现,DZ和ZW出现4 从表2.6可以发现,DZ和ZW出现4次;NZ和ZU出现3次;RZ,HZ,XZ, 2.6可以发现 出现 NZ和ZU出现3 出现 RZ,HZ,XZ, FZ,ZR,ZV,ZC,ZD和ZJ出现 出现2 FZ,ZR,ZV,ZC,ZD和ZJ出现2次. 由于ZW出现4次而WZ一次也为出现,同时W出现的频率为0.048 ZW出现 WZ一次也为出现 0.048, 由于ZW出现4次而WZ一次也为出现,同时W出现的频率为0.048,故可 猜测 D K (W ) = d38/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 又因为DZ出现4 又因为DZ出现4次,ZD出现2次,故可猜测 D (W ) ∈{r , s, t} DZ出现 ZD出现2 出现 但具体是哪一个还不太清楚. 但具体是哪一个还不太清楚. 的假设前提下, 在 D K (W ) = d 和 D ( Z ) = e 的假设前提下,继续观察 密文会注意到密文开始部分出现的ZRW RZW, ZRW和 密文会注意到密文开始部分出现的ZRW和RZW,并且在后 面还出现了RW 因为R在密文中频繁出现, nd是一个 RW, 面还出现了RW,因为R在密文中频繁出现,而nd是一个 明文中常见的双字母组, 明文中常见的双字母组,因此可以猜测 D K ( R) = n 到目前为止,已经得到了3 到目前为止,已经得到了3个密文字母可能对应的 明文字母,下面列出明文与密文的部分对应关系: 明文字母,下面列出明文与密文的部分对应关系:KK39/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)40/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)由于NZ是密文中出现较多的双字母组, ZN不出现, 由于NZ是密文中出现较多的双字母组,而ZN不出现,所以可以猜测 NZ是密文中出现较多的双字母组 不出现 如果这个猜测是正确的,则根据明文片段ne ndhe又可以猜 ne- D k ( N ) = h .如果这个猜测是正确的,则根据明文片段ne-ndhe又可以猜 结合这个假设,明文与密文的部分对应关系进一步又有: 测 D k (c) = a .结合这个假设,明文与密文的部分对应关系进一步又有:41/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 现在再考虑出现次数排在第二的密文字母M 现在再考虑出现次数排在第二的密文字母M,由前面 分析,已密文段RNM对应的明文为nh-,这说明 RNM对应的明文为nh-,这说明h 分析,已密文段RNM对应的明文为nh-,这说明h-可能 是一个明文单词的首字母,所以M 是一个明文单词的首字母,所以M可能代表明文中的一 个元音字母. 个元音字母.因为前面猜测已经使用了 D ( c ) = a 和 D k (Z ) = e 因为明文双字母ai ao的出现次 ai比 所以猜测 D ( M ) ∈ {i, o} .因为明文双字母ai比ao的出现次 数更多, 数更多,所以可以先猜测 D k ( M ) = i ,这样明文与密 文的部分对应关系进一步又有: 文的部分对应关系进一步又有:kk42/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)43/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 下面再来确定明文o对应的密文.因为o 下面再来确定明文o对应的密文.因为o是一个常见的明文 字母,所以可以猜测相应的密文字母是D 中的一个. 字母,所以可以猜测相应的密文字母是D,F,J,Y中的一个. 的可能性最大,否则由密文片段CFM CJM将得到长串的元音 CFM或 Y的可能性最大,否则由密文片段CFM或CJM将得到长串的元音 字母aoi 这在英文中是不太可能的.因此, aoi, 字母aoi,这在英文中是不太可能的.因此,可以猜测 D k (Y ) = o 剩下密文字母中三个出现次数较高的字母是D 剩下密文字母中三个出现次数较高的字母是D,F,J,可以 密文中三字母NMD NMD出现了两 猜测它们 {D ( D ), D ( F ), D ( J )} ∈ {r , s , t } ,密文中三字母NMD出现了两 次,故可猜测 D k ( D) = s ,这样,密文NMD对应的明文三字母组 这样,密文NMD对应的明文三字母组 NMD his, 是一致的. 为his,这与前面假设 D k ( D) ∈ {r , s, t}是一致的. 对于密文片段HNCMF 可猜测它对应的明文可能是chair HNCMF, chair, 对于密文片段HNCMF,可猜测它对应的明文可能是chair, 这样, 由此又有 D k ( H ) = c ,D k ( F ) = r .这样,通过排除法有 D k ( J ) = t .k k k44/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)45/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 第三步:利用与上述分析类似的方法, 第三步:利用与上述分析类似的方法,可以很容易地 确定其余密文字母和明文字母的对应关系,最后, 确定其余密文字母和明文字母的对应关系,最后,将得 到的明文加上标点符号,得到完整的明文如下: 到的明文加上标点符号,得到完整的明文如下: Our friend from Paris examined his empty glass surprise, with surprise,as if evaporation had taken place wasn' looking. while he wasn't looking.I poured some more wine and he settled back in his chair, face tilted up sun. towards the sun. 以上讨论的是破解一般单表替代密码的统计分析方法, 以上讨论的是破解一般单表替代密码的统计分析方法, 如果已知所用的密码体制(例如,对于位移密码, 如果已知所用的密码体制(例如,对于位移密码,加法密 乘法密码和仿射密码等), ),则相内的分析工作会更简 码,乘法密码和仿射密码等),则相内的分析工作会更简 单一些. 单一些.46/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 从该例子可以看出, 从该例子可以看出,破译单表替代密码的大致过程 是: 首先,统计密文的各种统计特征, 首先,统计密文的各种统计特征,如果密文量比较 则完成这步后便可确定出大部分密文字母; 多,则完成这步后便可确定出大部分密文字母; 然后,分析双字母,三字母密文组,以区分元音和 然后,分析双字母,三字母密文组, 辅音字母; 辅音字母; 最后,分析字母较多的密文, 最后,分析字母较多的密文,在这一过程中大胆使 用猜测的方法,如果猜对一个或几个词, 用猜测的方法,如果猜对一个或几个词,就会大大加快 破译过程. 破译过程.47/67 第2章 古典密码技术2.4.2 多表替代密码分析多表替代密码从一定程度上隐藏了明文消息的一些统计特征, 多表替代密码从一定程度上隐藏了明文消息的一些统计特征,破译相 对较为困难; 对较为困难; 在多表替代密码的分析中,首先要确定密钥的长度, 在多表替代密码的分析中,首先要确定密钥的长度,也就是要确定所 使用的加密表的个数,然后再分析确定具体的密钥; 使用的加密表的个数,然后再分析确定具体的密钥; 确定密钥长度的常用方法两种, Kasiski测试法 测试法( test) 确定密钥长度的常用方法两种 , 即 Kasiski 测试法 ( Kasiski test ) 和重合指数法( coincidence) 和重合指数法(index of coincidence). 下面以维吉尼亚密码为例来说明多表替代密码的分析方法. 下面以维吉尼亚密码为例来说明多表替代密码的分析方法.Kasiski测试 1. Kasiski测试Kasiski测试的基本思想是: Kasiski测试的基本思想是: 测试的基本思想是 用给定的n个字母表周期性地对明文字母加密, 用给定的 n 个字母表周期性地对明文字母加密 , 则当两个相同的明文 段在明文序列中间隔的字母数为n的整数倍时, 段在明文序列中间隔的字母数为 n 的整数倍时 , 将加密成相同的密文 段; 如果有两个相同的密文段,对应的明文段不一定相同, 如果有两个相同的密文段,对应的明文段不一定相同,但相同的可能 性大.将密文中相同的字母组找出来, 性大.将密文中相同的字母组找出来,并对其相同字母组的距离综合 分析,找出它们相同字母组距离的最大公因子, 分析,找出它们相同字母组距离的最大公因子,就有可能提取出密钥 的长度n 的长度n.48/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)考虑下面一个维吉尼亚密码的简单例子: 考虑下面一个维吉尼亚密码的简单例子: 明文: 明文:requests additional test 密钥: T E L E X T E L E X 密钥:T E L E X T E L E X T E 密文: B L T E U Q W S W J G E 密文:C A V K T A L T B L 明文包含字母序列est两次,而这两次又碰巧被同样的密钥片段加密, est两次 明文包含字母序列est两次,而这两次又碰巧被同样的密钥片段加密, 因而对应的密文都是TBL TBL. 因而对应的密文都是TBL. 出现这种情况反映了如下事实:序列est位于密钥长度(或周期) 出现这种情况反映了如下事实:序列est位于密钥长度(或周期)的整 est位于密钥长度 倍数处.显然,相同字母组的距离反映了密钥长度n的相关信息. 倍数处.显然,相同字母组的距离反映了密钥长度n的相关信息. Kasiski的测试过程如下 搜索长度至少为2 的测试过程如下: Kasiski的测试过程如下:搜索长度至少为2的相邻的一对对相同的密 文段,记下它们之间的距离. 密钥长度n 文段,记下它们之间的距离.而密钥长度n可能就是这些距离的最大公因 子.49/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)表2.7 重复字母组及距离示例50/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续) 2. 重合指数法如果考虑来自26个字母表的完全随机文本, 如果考虑来自26个字母表的完全随机文本,则每个字母都以相同的 26个字母表的完全随机文本 概率1/26出现,假定另一个随机文本放在第一个的下面, 1/26出现 概率1/26出现,假定另一个随机文本放在第一个的下面,在上下位置出 (1 现相同字母a 现相同字母a的概率为 26) 在两个随机文本的上下位置找到任意两个 , 2 26 (1 26)= 1 26 = 0.0385.但实际上,由于英文字母出 但实际上, 相同字母总的概率为 现的概率是不同的(见表2.4),设字母a,b,c,…,z出现的概率分别 现的概率是不同的(见表2.4),设字母a , 2.4),设字母 25225, 为 这样找到两个相同字母的概率为 ∑ pi = 0.065.这 i=0 个值比随机文本的概率大得多,称为重合指数. 个值比随机文本的概率大得多,称为重合指数. 1≤ i ≤ n 个字母构成, 定义 设一个语言由n个字母构成,每个字母出现的概率 p i , , 则重合指数是指其中两个随机元素相同的概率, 则重合指数是指其中两个随机元素相同的概率,记为 n 0, 1, 2,2pp p...pCI = ∑ pi2i =1=0.0385, 这样对于一个完全随机的文本CI=0.0385,与一个有意义的英语文本 =0.065,差异是比较明显的. CI=0.065,差异是比较明显的.51/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)实际分析中,重合指数的利用体现在几个方面. 实际分析中,重合指数的利用体现在几个方面. 如果密文的重合指数较低,那么就可能是多表替代密码. 如果密文的重合指数较低,那么就可能是多表替代密码.维吉尼亚密 码将密文分行,每行是单表替代密码. 码将密文分行,每行是单表替代密码. 在单表替代时,明文的字母被其它字母代替, 在单表替代时,明文的字母被其它字母代替,但不影响文本的统计属 即加密后密文的重合指数仍不变, 明文) 密文), ),由 性,即加密后密文的重合指数仍不变,CI(明文)= CI(密文),由 此可以判断文本是用单表还是用多表替代加密的. 此可以判断文本是用单表还是用多表替代加密的. 如果密钥长度(即密文分行的列数)正确, 如果密钥长度(即密文分行的列数)正确,同一行密文有相同字母的 概率接近0.065 如果密钥长度不对,则概率将大大小于0.065 0.065; 0.065, 概率接近0.065;如果密钥长度不对,则概率将大大小于0.065,显得 更随机,由此得到密钥长度(可与Kasiski测试的结果对比). Kasiski测试的结果对比 更随机,由此得到密钥长度(可与Kasiski测试的结果对比). 重合指数的估算能用于分析两个不同密文, 重合指数的估算能用于分析两个不同密文,比如接收到两段文本C1, 如果它们用同样的方式加密, C2,如果它们用同样的方式加密,则 CI (C 1) ≈ CI (C 2) . 实际密文长度有限,从密文中计算的重合指数值总是不同于理论值, 实际密文长度有限,从密文中计算的重合指数值总是不同于理论值, CI' 以字母出现的频度近似表示概率, 所以通常用CI的估计值CI',以字母出现的频度近似表示概率,则CI ' =∑Ci =1m2 xi/C =2 L∑ x (xi =1 imi 1) / L ( L
1)52/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)其中L代表密文长, 其中L代表密文长, CI' 的无偏估计值. CI'是CI的无偏估计值. 是密文出现的频度(数目).可以证明, ).可以证明 x 是密文出现的频度(数目).可以证明,i在古典密码的分析中,除了Kasiski测试和使用重合指数确定密钥 在古典密码的分析中,除了Kasiski测试和使用重合指数确定密钥 Kasiski 长度外,测试可用来确定是否采用了相同或不同的替代, 长度外,测试可用来确定是否采用了相同或不同的替代,也能用来简化 多表替代为单表替代. 多表替代为单表替代. Chi 测试(χ-test)提供了一个比较两个频率分布的直接方式.计 测试( test)提供了一个比较两个频率分布的直接方式. 算下面的和: 算下面的和: nχ =∑i =1piqi其中, 表示符号在第一个分布发生的概率, 其中, p i 表示符号在第一个分布发生的概率, q i 表示符号在第二个分 布中发生的概率. 布中发生的概率. C 当两个频率分布类似时,χ的值相对较高.假定收到两个密文 C , , 当两个频率分布类似时, 的值相对较高. 它们都是位移密码加密的结果. 它们都是位移密码加密的结果.设第一个替代表是通过源字母表移动 k 1 个字母得到, 个字母得到的. 个字母得到,第二个替代表是源字母表移动 k 个字母得到的.如果k 1 = k 2 C 是由同样位移替代密码加密的,这时χ值较大, ,说明 C , 是由同样位移替代密码加密的,这时χ值较大,因为 C 的统 k 类似.反之, 值将要小一些. 计特性与 C 类似.反之, ≠ k ,χ值将要小一些.1 2 21 2 1 21253/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)除了用来确定是否采用相同或不同的替代外, χ 除了用来确定是否采用相同或不同的替代外,也能用来简化多表 替代为单表替代. 替代为单表替代. 2.10】一个密钥为RADIO RADIO, Vigenere密码加密的明密文如下 密码加密的明密文如下: 【例2.10】一个密钥为RADIO,用Vigenere密码加密的明密文如下: 明文: 明文:execute these commands 密钥: 密钥:R A D I O R A D I O R A D I O R A D I O 密文: K E W P 密文:V X H K I S J E F W A D A Q L G 为了还原密文到明文,用下面的矩阵表示(列数等于密钥长度): 为了还原密文到明文,用下面的矩阵表示(列数等于密钥长度): R A D I O V K J D X E E A H W F Q K P W L I S A G54/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)可以看出,矩阵的第一行为密钥,第一列R下的密文字母通过 减 可以看出,矩阵的第一行为密钥,第一列R下的密文字母通过&减 &R R 解密.第二列A下的密文字母通过& 解密,等等. 解密.第二列A下的密文字母通过&减&A解密,等等.密文的第一列和 第 二列是两个不同的移位密码加密的结果. 二列是两个不同的移位密码加密的结果. 考虑密钥中每个字母和第一个字母R在字母表中的相对距离如下: 考虑密钥中每个字母和第一个字母R在字母表中的相对距离如下:现在,把第二列所有字母提前9个位置,第三列所有字母提前12个位 现在,把第二列所有字母提前9个位置,第三列所有字母提前12个位 12 其它类似,可获得下面的文本块: 置,其它类似,可获得下面的文本块:V K J DO V V RV K T ET Y F UL V D J55/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续) 这样,用密钥RADIO加密的文字,就转化为只用R 这样,用密钥RADIO加密的文字,就转化为只用R RADIO加密的文字 加密的密文, 加密的密文,即把基于多表替代密码的解密问题转化 为基于单表替代密码的解密问题. 为基于单表替代密码的解密问题. 尽管密码分析者可能没有密钥字母的相对距离这 个信息,然而,Chi测试提供了发现这个距离的线索 测试提供了发现这个距离的线索. 个信息,然而,Chi测试提供了发现这个距离的线索. 在该例中, 在该例中,密文列被移位使得它们都用同一个替代 密码解密.如果两列是用同样单表替代加密的, 密码解密.如果两列是用同样单表替代加密的,则两 列的χ值将相同,而且是最大值. 列的χ值将相同,而且是最大值.分析者通过尝试距离 直到得到这一列和第一列的χ最大值出现, 值,直到得到这一列和第一列的χ最大值出现,然后就 可用和第一列同样的方式解密. 可用和第一列同样的方式解密.56/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)2.11】在很短的时间内收到两段密文: 【例2.11】在很短的时间内收到两段密文: 密文C1: K O O M M A C O M O Q E G L X X M Q C C K U E Y F C U R Y L Y L I G Z S X C X V B C K M Y O P N P O G D G I A Z T X D D I A K N V O M X H I E M R D E Z V X B M Z R N L Z A Y Q I Q X G K K K P N E V H O V V B K K T C S S E P K G D H X Y V J M R D K B C J U E F M A K N T D R X B I E M R D P R R J B X F Q N E M X D R L B C J H P Z T V V I X Y E T N I I A W D R G N O M R Z R R E I K I O X R U S X C R E T V 密文C2: Z A O Z Y G Y U K N D W P I O U O RI Y R H H B Z X R C E A Y V X U V T X K C M A X S T X S E P B R X C S L R U K V B X T G Z U G G D W H X M X C S B I K T N S L R J Z H B X M S P U N G Z R G K U D X N A U F C M R Z X J R Y W Y M I57/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续) 由于这两段密文相隔时间很短, 由于这两段密文相隔时间很短,很有可能是用同样方式 加密的. CI'值来证实( 加密的.这个猜想可以通过计算两个文本的CI'值来证实( 计算过程从略): 计算过程从略):CI '(C 1) = 0.0421, CI '(C 2) = 0.0445这两个值近似相等, 这两个值近似相等,所以可假定这两段文本是用同样方 式加密的. 式加密的. CI' CI' 考虑到CI'值处在随机文本和有意义的英语文本的CI'值之 间,因此可猜想是用多表替代加密的. 因此可猜想是用多表替代加密的. 采用Kasiski测试, Kasiski测试 采用Kasiski测试,首先找到重复的字母序列及它们之间 的距离;分解这些距离值为素因子的乘积,数字7 的距离;分解这些距离值为素因子的乘积,数字7出现最频 周期可能为7 现在把密文写成是7列的矩阵形式( 繁,周期可能为7,现在把密文写成是7列的矩阵形式(见表 2.8). 2.8).58/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)表2.8 密文的矩阵表示59/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)然后计算每列的重合指数, 然后计算每列的重合指数,有: CI' CI' CI'(列1)=0.0522 CI'(列2)=0.0801 CI' CI' CI'(列4)=0.0744 CI'(列5)=0.0705 CI' CI'(列7)=0.0606CI' CI'(列3)=0.0734 CI' CI'(列6)=0.0717但观察每一列的重合指数, 但观察每一列的重合指数,似乎每一列都是用一个单表替代密码加 密的.现在试图将多表替代的密文转化为某个单表替代加密的密文. 密的.现在试图将多表替代的密文转化为某个单表替代加密的密文.首 重复移动各列字母,移动的距离分别是1 25, 先,重复移动各列字母,移动的距离分别是1～25,并分别计算相对于 第一列的χ 并把最大值用下划线标识出来. 第一列的χ值,并把最大值用下划线标识出来. 列1和2:0.7 0.6 0.0 0.2 0.0 0.1 0.0 0.9 0.1 0.8 0.8 0.5 0.030260/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)列1和3:0.4 0.2 列1和4:0.8 0.6 列1和5:0.6 0.1 0.1 0.0 0.1 0.3 0.1 0.0 0.4 0.2 0.1 0.6 0.9 0.2 0.3 0.2 0.0 0.9 0.7 0.0 0.9 0.8 0.7 0.9 0.1 0.8 0.4 0.1 0.5 0.6 0.5 0.0 0.6 0.041161/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)列1和6:0.2 0.5 列1和7:0.7 0.4 0.2 0.2 0.4 0.6 0.5 0.4 0.1 0.0 0.8 0.4 0.03380.2 0.7 0.3 0.3 0.6 0.0 0.8 0.4 0.7 0.9 0.0295根据以上结果推知,各列相对于第一列的距离分别是: 根据以上结果推知,各列相对于第一列的距离分别是: 列2:13 列3:22 列4:7 列5:2 列6:19 列7:1562/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)到下列文本: 用这些值来转化密文C1,C2到下列文本: K B K T O T R O Z K X G Z A X K I X E V Z U R U M E N G Y Y U S K Z O S K Y G X U R K Z U V R G E O T Z N K T O T K Z K K T Z N I K T Z A X E Z N K G S K X O I G T G A Z N U X K J M G X G R R G T V U K C X U Z K G Y Z U X E K T Z O Z R K J Z N K M U R J H A M O T Z N G Z Y Z U X C Z N K R K G J O T M S G T M K Z Y N U R J U L G V O K I K U L V G X I N S K T Z C O Z N G T K T I X E V Z K J S K Y Y G M K Z N K G A Z N U X J K Y I X O H K Y K R G H U X G Z K R E N U C Z N K R K G J O T M S G T Z G I Q R K Y Z N K J K I X E V Z O U T C K Y A M M K Y Z Z U X K G J Z N K Y Z U X E O L E U A C G T Z Z U Q T U C N U C Z N G Z C G Y J U T K63/67 第2章 古典密码技术Hill密码的已知明文分析 2.4.3 对Hill密码的已知明文分析Hill密码能较好地抵抗字母频率的统计分析,采用惟密文攻击是较 密码能较好地抵抗字母频率的统计分析, 密码能较好地抵抗字母频率的统计分析 难攻破,但采用已知明文攻击就容易破译. 难攻破,但采用已知明文攻击就容易破译. 假定密码分析者知道加密分组长度n值 且有至少 ( & ) 假定密码分析者知道加密分组长度 值,且有至少N(N&n)个不同 的明文/密文分组对, 满足: 的明文 密文分组对,M1/ C1, M 2/ C 2,……, M N/ C N 满足: 密文分组对 , C 1= K M1(mod26), C 2= K M1(mod26),...,C N = K M N(mod26) 记为: 记为:(C1 C2 C3 … C N )=(M1 M2 M3 … M N )K (mod26) 其中M i,C i(i=1,2,…,N)均为 维列向量,K为未知密钥方阵. 维列向量, 为未知密钥方阵 为未知密钥方阵. 其中 , , , )均为n维列向量 利用n个已知的明文 密文分组对定义两个 方阵: 利用 个已知的明文/密文分组对定义两个 ×n方阵: 个已知的明文 密文分组对定义两个n× 方阵 M =(M1 M2 M3 … M n ) , C = (C1 C2 C3 … C n ) 有矩阵方程:C 有矩阵方程 = K M(mod26) ( ) 若提供的矩阵M是可逆的,则能计算出 若提供的矩阵 是可逆的,则能计算出K = C M-1(mod26),从而破译 是可逆的 , 该密码体制. 该密码体制. 若方阵M关于模 不可逆 攻击者可通过尝试其它明文/密文对来产 若方阵 关于模26不可逆,攻击者可通过尝试其它明文 密文对来产 关于模 不可逆, 生新的方阵M 直到找到一个可逆的明文矩阵M就可破译 就可破译Hill密码. 密码. 生新的方阵 ,直到找到一个可逆的明文矩阵 就可破译 密码64/67 第2章 古典密码技术Hill密码的已知明文分析 密码的已知明文分析( 2.4.3 对Hill密码的已知明文分析(续)2.12】假设明文worker worker利用 =2的Hill密码加密 得到密文qihryb 密码加密, qihryb, 【例2.12】假设明文worker利用n=2的Hill密码加密,得到密文qihryb, 求密钥K 求密钥K. 将明文,密文划分为三组:(w, ),(r, ),(e, (q, 解:将明文,密文划分为三组:(w,o ),(r,k ),(e,r ) 和 (q,I (h, (y, ), 22,14),(17, ),(17 (4, )和 ) ,(h,r ) ,(y,b ),即(22,14),(17,10 ) ,(4,17 )和( 16, ),(7 (7, (24, ),分别满足: 16,8),(7,17 ) ,(24,1 ),分别满足: 16
利用前两个明文-密文对,构造矩阵方程: 利用前两个明文-密文对,构造矩阵方程:16 7
14 10 22 17 det
= 18, 计算明文方阵行列式, 计算明文方阵行列式, 14 10 由于(-18,26) (-18,26 即该矩阵没有逆元,于是考虑第二, 由于(-18,26)≠1,即该矩阵没有逆元,于是考虑第二,第三组明 密文对,得到矩阵方程: 文-密文对,得到矩阵方程: 7 24
65/67 第2章 古典密码技术Hill密码的已知明文分析 密码的已知明文分析( 2.4.3 对Hill密码的已知明文分析(续) ∵ ∴17 4
= 249, 249 × 7 ≡ 1 mod 26 10 17
mod 26 17 1
1显然,通过对比第一个明文—密文对很容易验证该密钥. 显然,通过对比第一个明文—密文对很容易验证该密钥. 如果密码分析者不知道加密分组长度l的值,那么可以通 的值, 值来得到密钥. 过逐一尝试不同的l值来得到密钥. Hill密码体制的重要性在于它无可辩驳地表明数学方 Hill密码体制的重要性在于它无可辩驳地表明数学方 法在密码学中的地位是不容置疑的. 法在密码学中的地位是不容置疑的.66/67 第2章 古典密码技术本章小结本章主要介绍了古典密码技术,包括替代密码, 本章主要介绍了古典密码技术,包括替代密码,置 换密码以及转轮机密码, 换密码以及转轮机密码,重点阐述了古典密码的统计分 包括: 析,包括:
单表替代密码分析
多表替代密码分析
对Hill密码的已知明文分析密码系统的安全性 Hill密码的已知明文分析 密码的已知明文分析密码系统的安全性67/67
第2章 古典密码学——为大家提供各种日常写作指导，同时提供范文参考。主要栏目有：范文大全、个人简历、教案下载、课件中心、 优秀作文、考试辅导、试题库、诗词鉴赏。
相关文档：
下载文档：
搜索更多：
All rights reserved Powered by
copyright ©right 。甜梦文库内容来自网络，如有侵犯请联系客服。|}
标 题：密码学入门系列(三) 之 希尔密码(古典)
作 者：jackozoo
时 间：<font color="#09-05-21 23:56:29 链 接：
【文章标题】:&密码学入门系列(三)&之&希尔密码(古典)
【文章作者】:&jackozoo
【作者邮箱】:&
【作者声明】:&只是感兴趣，没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
&&系列声明:&见(一)
&&希尔密码(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]&
&&很可能是一个含有分式的矩阵.&这显然是不符合要求的.(为什么?&)
&&&&&&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)
&&&&&&&&&&&&&&int&p&=&2;
&&&&&&&&&&&&&&while(p*p&n)
&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&if&(a%p&==&n%p&&&&&0&==&a%p)
&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&return&
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&p++;
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&//when&a&equals&with&1&,&it's&also&reversiable
&&&&&&&&&&&&&&return&
&&&&&&&&&&}
&&//得到元素a对n的模逆
public&int&GetReverse(int&a)
&&&&&&&&&&{
&&&&&&&&&&&&&&int&n&=&(int)
&&&&&&&&&&&&&&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&&&nR++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&&&nR++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)&
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&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&
&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&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)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if&(A[i,&k]&0)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&A[i,&k]&+=&(int)
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&//construct&M_1
&&&&&&&&&&&&&&for&(i&=&0;&i&&&nR++i)
&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&for&(j&=&0;&j&&&nR++j)
&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&nDeMatrix[i,j]&=&A[i,j+nRank];
&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&return&
&&&&&&&&&&}
&&我们来截几张图看看:
&&n阶希尔逆矩阵的计算:
&&screen.width*0.6) {this.width=screen.width*0.6;this.alt='';this.onmouseover=this.style.cursor='pointer';this.onclick=function(){window.open('/picture.php?albumid=7&pictureid=78')}}" />
&&加密测试:(注意明文中的3个O分别变为了O,S,A&.&很好地隐藏了字频信息.)
&&screen.width*0.6) {this.width=screen.width*0.6;this.alt='';this.onmouseover=this.style.cursor='pointer';this.onclick=function(){window.open('/picture.php?albumid=7&pictureid=79')}}" />
&&总结:&大概就讲这么多吧.&附件为辅助软件和C#源码.大家可以对这源码看文章.&也希望大家指出不足之处.&谢谢.
--------------------------------------------------------------------------------
【版权声明】:&本文原创于看雪技术论坛,&转载请注明作者并保持文章的完整,&谢谢!
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&日&PM&11:55:39上传的附件课程主要内容第1 章 第2 章 第3 章 第4 章 第5 章 第6 章 第7 章 第8 章 第9 章 10章 第10章 密码学概述 古典密码技术 分组密码 公钥密码体制 散列函数与消息鉴别 数字签名技术 密钥管理技术 身份鉴别技术 序列密码 密码技术应用 第2章 古典密码技术本章主要内容 替代密码
置换密码 周期置换密
码 列置换密码
转轮机密码
古典密码的统计分析 单表替代密码分析 多表替代密码分析 Hill密码的已知明文分析 对Hill密码的已知明文分析2/67 第2章 古典密码技术2.1 替代密码
替代是古典密码中用到的最基本的处理技巧之一 ;
替代密码是指先建立一个替换表,加密时将需要加密 替代密码是指先建立一个替换表, 的明文依次通过查表,替换为相应的字符, 的明文依次通过查表,替换为相应的字符,明文字符 被逐个替换后,生成无任何意义的字符串,即密文, 被逐个替换后,生成无任何意义的字符串,即密文, 替代密码的密钥就是其替换表 ;
根据密码算法加解密时使用替换表多少的不同,替代 根据密码算法加解密时使用替换表多少的不同, 密码又可分为单表替代密码和多表替代密码. 密码又可分为单表替代密码和多表替代密码.
单表替代密码的密码算法加解密时使用一个固定的替 换表; 换表;
多表替代密码的密码算法加解密时使用多个替换表. 多表替代密码的密码算法加解密时使用多个替换表.3/67 第2章 古典密码技术2.1.1 单表替代密码 单表替代密码对明文中的所有字母都使用一个固定的映 射(明文 字母表到密文字母表). 字母表到密文字母表). 为包含了n 设A={a0, a1,…, an-1}为包含了n个字母的明文字母表; 为包含了 个字母的明文字母表; B={b0, b1,…, bn-1} 为包含n个字母的密文字母表,单表替 为包含n个字母的密文字母表, 代密码使用了A 的映射关系: 代密码使用了A到B的映射关系: f:A→B, f ( ai )= bj 一般情况下, 是一一映射,以保证加密的可逆性. 一般情况下,f 是一一映射,以保证加密的可逆性. 加密变换过程就是将明文中的每一个字母替换为密文字母 表的一个字母. 表的一个字母.而单表替代密码的密钥就是映射f或密文 字母表. 字母表. 经常密文字母表与明文字母表的字符集是相同的, 经常密文字母表与明文字母表的字符集是相同的,这时 的密钥就是映射f.下面给出几种典型的单表替代密码. 的密钥就是映射 下面给出几种典型的单表替代密码.4/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续)
一般单表替代密码一般单表替代密码的原理是以26个英文字母集合上的一个置换π 一般单表替代密码的原理是以26个英文字母集合上的一个置换π为 26个英文字母集合上的一个置换 密钥,对明文消息中的每个字母依次进行变换. 密钥,对明文消息中的每个字母依次进行变换. 可描述为: 都是26个英文字母的集合, 26个英文字母的集合 可描述为:明文空间M和密文空间C都是26个英文字母的集合,密 钥空间K={π:Z26→Z26|π是置换 ,是所有可能置换的集合. 是置换}, 钥空间 : 是置换 是所有可能置换的集合. 定义: 对任意π∈K,定义: 加密变换: )=c 加密变换:eπ(m)=π(m)= )= )= 解密变换:dπ(c) = π-1(c)=m, π-1是π的逆置换. 解密变换: , 的逆置换. 的逆置换 2.1】设置换π的对应关系如下: 【例2.1】设置换π的对应关系如下: a b c d e f g h i j k l m n o p q r s t u v w x y z q w e r t y u i o p a s d f g h j k l z x c v b n m 试用单表替代密码以π为密钥对明文消息message加密, message加密 试用单表替代密码以π为密钥对明文消息message加密,然后写出逆 并对密文解密. 置换 ,并对密文解密. 为密钥用单表替代密码对明文消息message加密, message加密 解:以π为密钥用单表替代密码对明文消息message加密,所得 密文消息为: 密文消息为: π(m) π(e) π(s) π(s) π(a) π(g) π(e)=dtllqut5/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续) 一般单表替代密码算法特点: 一般单表替代密码算法特点:密钥空间K很大, 破译者穷举搜索计算不可行, 微秒试 密钥空间 很大,|K|=26!=4×1026 ,破译者穷举搜索计算不可行,1微秒试 很大 一个密钥,遍历全部密钥需要10 一个密钥,遍历全部密钥需要 13 年. 移位密码体制是替换密码体制的一个特例,它仅含26个置换做为密钥空间 个置换做为密钥空间. 移位密码体制是替换密码体制的一个特例,它仅含 个置换做为密钥空间. 密钥π不便记忆 不便记忆. 密钥 不便记忆. 针对一般替换密码密钥π不便记忆的问题 不便记忆的问题, 针对一般替换密码密钥 不便记忆的问题,又衍生出了各种形式单表替代密码 .
移位密码 明文空间M,密文空间C都是和密钥空间 都是和密钥空间K满足 明文空间 ,密文空间 都是和密钥空间 满足 P = C = K = {0,1, 2,...,25} = Z 26 即把26个英文字母与整数 个英文字母与整数0, , , , 一一对应 如表2.1所示 一一对应, 所示. 即把 个英文字母与整数 ,1,2,…,25一一对应,如表 所示. 表2.1 字母数字映射表6/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续) 加密变换, 加密变换,E={E:Z26→Z26, Ek (m) = m + k (mod26)| m∈M, k∈K } 解密变换, 解密变换,D={D:Z26→Z26, Dk (c) = c-k (mod26)| c∈C, k∈K } 解密后再把Z26中的元素转换英文字母. 解密后再把 中的元素转换英文字母. 显然,移位密码是前面一般单表替代密码的一个特例.当移 显然,移位密码是前面一般单表替代密码的一个特例. 密钥k=3时,就是历史上著名的凯撒密码(Caesar) 位密码的 密钥 时 就是历史上著名的凯撒密码( ) 移位密码也称为加法密码. .根据其加密函数特 点,移位密码也称为加法密码. 仿射密码 仿射密码也是一般单表替代密码的一个特例, 仿射密码也是一般单表替代密码的一个特例,是一种线性 变换.仿射密码的明文空间和密文空间与移位密码相同, 变换.仿射密码的明文空间和密文空间与移位密码相同,但 密钥空间为 K={(k1,k2)| k1,k2∈Z26,gcd(k1,26)=1} 对任意m∈ , ∈ , 对任意 ∈M,c∈C,k = (k1,k2)∈K,定义加密变换为 定义加密变换为 c = Ek (m) = k1 m +k2 (mod 26) 相应解密变换为: 相应解密变换为: m = Dk (c) = k1-1 (c-k2) (mod 26)7/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续)m (c)=k1 (c
k 2)(mod 26) 相应解密变换为: 相应解密变换为: = D k 1 k 其中, 很明显, 时即为移位密码, 其中,1k 1 = 1mod 26 .很明显,k1=1时即为移位密码,而k2=1则称为乘法 时即为移位密码 则称为乘法 密码. 密码.12.3】设明文消息为china china, 【例2.3】设明文消息为china,密钥 k = (k 1,k 2) = (9, 2)试用仿射密码对其进行 加密,然后再进行解密. 加密,然后再进行解密. 1 利用扩展的欧几里德算法(参见附录A.1.2 A.1.2) 解:利用扩展的欧几里德算法(参见附录A.1.2)可计算出 k 1 = 3 加密变换为: 加密变换为: E k (m) = k 1m + k 2(mod 26) = 9 × m + 2(mod 26)1 解密变换为: 解密变换为: D k (c) = k 1 (c
k 2)(mod 26) = 3 × (c
2)(mod 26) = (3c
6)(mod 26)明文消息对应的数字依次为 , , , , , 明文消息对应的数字依次为2,7,8,13,0,用仿射密码对明文进行加密 消息对应的数字依次为 如下: 如下:
E k ( m ) = 9 ×
c 8/67 第2章 古典密码技术单表替代密码( 2.1.1 单表替代密码(续)密文消息为unwpc.而解密过程如下: 密文消息为unwpc.而解密过程如下: unwpc 20
h Dk (m ) = 3 ×
即恢复明文消息为china china. 即恢复明文消息为china. 仿射密码要求(k 仿射密码要求 1, 26)=1 ,否则就会有多个明文字母对应 一个密文字母的情况.由于与26互素的整数有 互素的整数有12个 一个密文字母的情况.由于与 互素的整数有 个,故仿射密码密钥空间大 小为|K|=12×26=312. 小为 × .若将仿射密码的加密函数换为多项式函数时, 若将仿射密码的加密函数换为多项式函数时,即为多项式密码.密钥短语密码选用一个英文短语或单词串作为密钥, 选用一个英文短语或单词串作为密钥,去掉其中重复的字母得到一个无 短语或单词串作为密钥 重复字母的字符串,然后再将字母表中的其它字母依次写于此字母串后, 重复字母的字符串,然后再将字母表中的其它字母依次写于此字母串后,就 可构造出一个字母替代表.如密钥为key时 替代表如表2.2所示 所示. 可构造出一个字母替代表.如密钥为 时,替代表如表 所示.9/67 第2章 古典密码技术密钥为key key的单表替代密码 表2.2 密钥为key的单表替代密码当选择上面的密钥进行加密时,若明文为 当选择上面的密钥进行加密时,若明文为&china&,则密文为 进行加密时 ,则密文为&yfgmk& . 显然,不同的密钥可以得到不同的替换表, 显然,不同的密钥可以得到不同的替换表,对于明文为英文单词或短语 的情况时,密钥短语密码最多可能有26!=4×1026个不同的替换表. 个不同的替换表. 的情况时,密钥短语密码最多可能有 ×2.1.2 多表替代密码单表替代密码表现出明文中单字母出现的频率分布与密文中相同, 单表替代密码表现出明文中单字母出现的频率分布与密文中相同, 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布,每个映射是简单替代密码中的一对一映射多表替代密码将 的频率分布, 明文字母划分为长度相同的消息单元,称为明文分组 分组, 明文字母划分为长度相同的消息单元,称为明文分组,对明文成组地进 行替代,同一个字母有不同的密文, 行替代,同一个字母有不同的密文,改变了单表替代密码中密文的唯一 使密码分析更加困难. 性,使密码分析更加困难.10/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(多表替代密码的特点是使用了两个或两个以上的替代表. 多表替代密码的特点是使用了两个或两个以上的替代表.著名的维吉 尼亚密码和Hill密码等均是多表替代密码. Hill密码等均是多表替代密码 尼亚密码和Hill密码等均是多表替代密码.1.维吉尼亚密码 1.维吉尼亚密码维吉尼亚密码是最古老而且最著名的多表替代密码体制之一,与位移 维吉尼亚密码是最古老而且最著名的多表替代密码体制之一, 密码体制相似, 维吉尼亚密码的密钥是动态周期变化的. 密码体制相似,但维吉尼亚密码的密钥是动态周期变化的. 该密码体制有一个参数n.在加解密时,同样把英文字母映射为0-25 在加解密时,同样把英文字母映射为0 的数字再进行运算, 个字母一组进行变换.明文空间, 的数字再进行运算,并按n个字母一组进行变换.明文空间,密文空间及密 P = C = K = (Z 26 ) 的英文字母串的集合, 钥空间都是长度为n的英文字母串的集合,因此可表示n加密变换定义如下: 加密变换定义如下: 明文m=(m1,m2,…,mn), 加密变换为: 加密变换为: 设密钥 k=(k1,k2,…,kn), 明文 Ek(m)=(c1,c2,…,cn), 其中c 其中 i(mi + ki)(mod26),i =1,2,…,n , 解密变换为: 对密文 c=(c1,c2,…,cn), 解密变换为: Dk(c)=(m1,m2,…,mn), 其中 mi=(ci -ki)(mod26),i =1,2,…,n11/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( =cipher,明文消息appliedcryptosystem appliedcryptosystem, 【例2.4】设密钥k =cipher,明文消息appliedcryptosystem, 2.4】 试用维吉尼亚密码对其进行加密,然后再进行解密. 试用维吉尼亚密码对其进行加密,然后再进行解密. =cipher, n=6, (2, 解:由密钥k=cipher,得n=6,密钥对应的数字序列为 (2,8, 15, 17).然后将明文按每6个字母进行分组, 15,7,4,17).然后将明文按每6个字母进行分组,并转换这 些明文字母为相应的数字,再用模26加上对应密钥数字, 26加上对应密钥数字 些明文字母为相应的数字,再用模26加上对应密钥数字,其加 密过程如表2.3所示. 2.3所示 密过程如表2.3所示.表2.3 密钥为cipher的维吉尼亚密码加密过程 密钥为cipher cipher的维吉尼亚密码加密过程密文为:cxtsmvfkgftkqanzxvo. 密文为:cxtsmvfkgftkqanzxvo. 解密使用相同的密钥,但用模26的减法代替模26加法, 26的减法代替模26加法 解密使用相同的密钥,但用模26的减法代替模26加法,这里 不再赘述. 不再赘述.12/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( 2.希尔 Hill) 希尔( 2.希尔(Hill)密码Hill密码算法的基本思想是将 个明文字母通过线性变换, Hill密码算法的基本思想是将n个明文字母通过线性变换,将它们转换为n 个密文字母. 个密文字母.解密只需做一次逆变换即可. 可逆矩阵｝ 维向量, 算法的密钥K =｛ Z 26上的 n × n 可逆矩阵｝,明文M与密文C 均为n维向量, 记为 m1
,K=(kij )n×n =
c1 = k 1 1 m 1 + k 1 2 m 2 + . . . + k 1 n m n m o d 2 6
c = k m + k m + ... + k m m o d 2 6
2 21 1 22 2 2n n
c n = k n1m 1 + k n 2 m 2 + ... + k nn m n m o d 2 6 其中, 其中,或写成C = K
M (mod 26)解密变换则为: M = K 1
C (mod 26). 解密变换则为:13/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(其中,K –1为K在模 上的逆矩阵,满足:K K –1 = K –1 K=I (mod 26) 其中, 在模26上的逆矩阵,满足: 在模 上的逆矩阵 为单位矩阵. 这里 I 为单位矩阵. 定理2.1:假设A = ( ai,j) 为一个定义在Z26上的n×n矩阵,若A 在模26上可 定理2.1:假设 为一个定义在 上的 × 矩阵, 在模 上可 2.1 矩阵 则有: 这里A 为矩阵A的伴随矩阵 逆,则有: A –1= ( det A ) –1 A* (mod 26 ) ;这里 *为矩阵 的伴随矩阵 在n = 2的情况下,有下列推论: 的情况下,有下列推论: 的情况下det A = a1,1a2,2
a1,2a2,1例如, 例如, a1,1 假设 A=
是一个Z 上的2 矩阵,它的行列式:
,是一个Z26上的2×2矩阵,它的行列式: a2,2 1 111 8
3 × 8(mod 26) = 77
24(mod 26) = 53(mod 26) = 1
3 7 a2,2 a1,2
是可逆的,那么: 是可逆的,那么: = (det A)
a2,1 a1,1 14/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(的逆矩阵为: 这时 1
1 m o d 2 6 = 1 ,所以K的逆矩阵为:K111 =
71=11 7 ×
m od 26 11 11 8 Hill密码对其 的 Hill密码对其 7设明文消息为good good, 【例 2.5】设明文消息为 good ,试用n= 2,密钥 K =
行加密,然后再进行解密. 进 行加密,然后再进行解密. 加密过程如下: 加密过程如下:将明文划分为两组:(g, (o, 14) 14, 解:将明文划分为两组:(g,o ) 和 (o,d ),即(6,14)和(14,3). c1
w = K 1= = ≡
w =K 3= = ≡
因此,good的加密结果是 显然,明文不同位置的字母& 加密成 因此,good的加密结果是wmwl.显然,明文不同位置的字母&o&加密成 的密文字母不同.为了解密, 的密文字母不同.为了解密,由前面计算有 K 1 =
7 18 ,可由密文解密计 算出明文: 算出明文:
23 11 15/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( m1
d 因此,解密得到正确的明文&good&. 因此,解密得到正确的明文&good . Hill密码特点 密码特点: Hill密码特点: 可以较好地抑制自然语言的统计特性, 可以较好地抑制自然语言的统计特性,不再有单字母替换的一一 对应关系,对抗&惟密文攻击&有较高安全强度. 对应关系,对抗&惟密文攻击&有较高安全强度. 密钥空间较大,在忽略密钥矩阵K可逆限制条件下 可逆限制条件下, 密钥空间较大,在忽略密钥矩阵 可逆限制条件下,|K|=26n×n 易受已知明文攻击及选择明文攻击(详见2.3节相关分析 节相关分析). 易受已知明文攻击及选择明文攻击(详见 节相关分析).Pad) 3.一次一密密码(One Time Pad) 一次一密密码(若替代码的密钥是一个随机且不重复的字符序列, 若替代码的密钥是一个随机且不重复的字符序列,这种密码则称为一 次一密密码,因为它的密钥只使用一次. 次一密密码,因为它的密钥只使用一次. 该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报 该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报 通信设计的一种密码,所以又称为Vernam密码.Vernam密码在对明文加密 Vernam密码 通信设计的一种密码,所以又称为Vernam密码.Vernam密码在对明文加密 前首先将明文编码为( 序列,然后再进行加密变换. 前首先将明文编码为(0,1)序列,然后再进行加密变换.16/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(设m=(m1 m2 m3 … mi …)为明文,k=(k1 k2 k3 … ki …)为密钥,其中mi,ki ∈(0,1), 为明文, 为密钥,其中 , 为明文 为密钥 i≥1, 则加密变换为: 则加密变换为: c=(c1 c2 c3 … ci …) ,其中 i = mi ⊕ ki , i≥1, 其中c 其中这里为模2加法(或异或运算) 这里为模 加法(或异或运算) 加法 解密变换为: 解密变换为: m=(m1 m2 m3 … mi …) ,其中 i = ci ⊕ ki , i≥1, 其中m 其中在应用Vernam密码时,如果对不同的明文使用不同的随机密钥,这时 密码时,如果对不同的明文使用不同的随机密钥, 在应用 密码时 Vernam密码为一次一密密码. 密码为一次一密密码 密码为一次一密密码. 由于每一密钥序列都是等概率随机产生的, 由于每一密钥序列都是等概率随机产生的,敌手没有任何信息用来对密文 进行密码分析.香农( 进行密码分析.香农(Claude Shannon)从信息论的角度证明了这种密码体 ) 制在理论上是不可破译的.但如果重复使用同一个密钥加密不同的明文, 制在理论上是不可破译的.但如果重复使用同一个密钥加密不同的明文,则 这时的Vernam密码就较为容易破译. 密码就较为容易破译. 这时的 密码就较为容易破译 若敌手获得了一个密文c=(c1 c2 c3 … ci …) 和对应明文 和对应明文m=(m1 m2 m3 … mi …) 若敌手获得了一个密文 其中k 时,就很容易得出密钥 k=(k1 k2 k3 … ki …) ,其中 i = ci ⊕ mi ,i≥1. . 故若重复使用密钥,该密码体制就很不安全. 故若重复使用密钥,该密码体制就很不安全.17/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码(实际上Vernam密码属于序列密码,加密解密方法都使用模2加,这使软 实际上Vernam密码属于序列密码,加密解密方法都使用模2 Vernam密码属于序列密码 硬件实现都非常简单.但是,这种密码体制虽然理论上是不可破译的, 硬件实现都非常简单.但是,这种密码体制虽然理论上是不可破译的,然而 在实际应用中,真正的一次一密系统却受到很大的限制, 在实际应用中,真正的一次一密系统却受到很大的限制,其主要原因在于该 密码体制要求: 密码体制要求: 密钥是真正的随机序列; ① 密钥是真正的随机序列; 密钥长度大于等于明文长度; ② 密钥长度大于等于明文长度; 每个密钥只用一次(一次一密). ③ 每个密钥只用一次(一次一密). 这样,分发和存储这样的随机密钥序列, 这样,分发和存储这样的随机密钥序列,并确保密钥的安全都是很因难 另外,如何生成真正的随机序列也是一个现实问题.因此, 的;另外,如何生成真正的随机序列也是一个现实问题.因此,人们转而寻 求实际上不对攻破的密码系统. 求实际上不对攻破的密码系统.4.Playfair密码 Playfair密码Playfair密码是一种著名的双字母单表替代密码,实际上Playfair密码 Playfair密码是一种著名的双字母单表替代密码,实际上Playfair密码 密码是一种著名的双字母单表替代密码 Playfair 属于一种多字母替代密码,它将明文中的双字母作为一个单元对待, 属于一种多字母替代密码,它将明文中的双字母作为一个单元对待,并将这 些单元转换为密文字母组合. 些单元转换为密文字母组合.18/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( 替代时基于一个5 替代时基于一个5×5的字母矩阵.字母矩阵构造方法同密钥 的字母矩阵. 短语密码类似,即选用一个英文短语或单词串作为密钥, 短语密码类似,即选用一个英文短语或单词串作为密钥,去掉其 中重复的字母得到一个无重复字母的字符串, 中重复的字母得到一个无重复字母的字符串,然后再将字母表中 剩下的字母依次从左到右,从上往下填入矩阵中,字母I 剩下的字母依次从左到右,从上往下填入矩阵中,字母I,j占同 一个位置. 一个位置. 例如,密钥K= cipher, 例如,密钥K= playfair is a digram cipher,去除重复字 母后,K=playfirsdgmche,可得字母矩阵如图2.1 2.1. 母后,K=playfirsdgmche,可得字母矩阵如图2.1.Playfair密码字母矩阵示例 图2.1 Playfair密码字母矩阵示例19/67 第2章 古典密码技术2.1.2 多表替代密码(续) 多表替代密码( 对每一明文字母对P1,P2的加密方法如下: 对每一明文字母对P1,P2的加密方法如下: P1 的加密方法如下 P1,P2在同一行 密文C1 C2分别是紧靠P1,P2右 在同一行, C1, 分别是紧靠P1 (1)若P1,P2在同一行,密文C1,C2分别是紧靠P1,P2右 端的字母; 端的字母; P1,P2在同一列 密文C1 C2分别是紧靠P1,P2下 在同一列, C1, 分别是紧靠P1 (2)若P1,P2在同一列,密文C1,C2分别是紧靠P1,P2下 方的字母; 方的字母; P1,P2不在同一行 也不在同一列, C1,C2是由 不在同一行, (3)若P1,P2不在同一行,也不在同一列,则C1,C2是由 P1,P2确定的矩形其它两角的字母 确定的矩形其它两角的字母, C1和P1在同一行 在同一行, P1,P2确定的矩形其它两角的字母,且C1和P1在同一行, C2和P2在同一行 在同一行; C2和P2在同一行; P1=P2,则两个字母间插入一个预先约定的字母, (4)若P1=P2,则两个字母间插入一个预先约定的字母, 并用前述方法处理; 如x,并用前述方法处理; balloon,则以ba 来加密. 如balloon,则以ba lx lo on 来加密. 若明文字母数为奇数,则在明文尾填充约定字母. (5)若明文字母数为奇数,则在明文尾填充约定字母. 算法还约定字母矩阵中第一列看做最后一列的右边一列, 算法还约定字母矩阵中第一列看做最后一列的右边一列, 表中第一行看做最后一行的下一行. 表中第一行看做最后一行的下一行.20/67 第2章 古典密码技术2.2 置换密码 ( Permutation Cipher )置换密码又称为换位密码; 置换密码又称为换位密码; 置换密码通过改变明文消息各元素的相对位置, 置换密码通过改变明文消息各元素的相对位置,但明文消息元素本身 的取值或内容形式不变; 的取值或内容形式不变; 在前面的替代密码中,则可以认为是保持明文的符号顺序, 在前面的替代密码中,则可以认为是保持明文的符号顺序,但是将它 们用其它符号来替代; 们用其它符号来替代; 这种密码是把明文中各字符的位置次序重新排列来得到密文的一种密 码体制.实现的方法多种多样.直接把明文顺序倒过来, 码体制.实现的方法多种多样.直接把明文顺序倒过来,然后排成固 定长度的字母组作为密文就是一种最简单的置换密码. 定长度的字母组作为密文就是一种最简单的置换密码. 下面再给出几种典型的置换密码算法. 下面再给出几种典型的置换密码算法.2.2.1 周期置换密码周期置换密码是将明文字符按一定长度n分组,把每组中的字符按1 周期置换密码是将明文字符按一定长度n分组,把每组中的字符按1, 2,…,n的一个置换π重排位置次序来得到密文的一种加密方法. , 的一个置换π重排位置次序来得到密文的一种加密方法. 其中的密钥就是置换π 的描述中包含了分组长度的信息. 其中的密钥就是置换π,在π的描述中包含了分组长度的信息.
1 解密时,对密文字符按长度n分组,并按π 解密时,对密文字符按长度n分组,并按π的逆置换π 把每组字符重排 位置次序来得到明文. 位置次序来得到明文. 周期置换密码可描述为: 周期置换密码可描述为:21/67 第2章 古典密码技术周期置换密码( 2.2.1 周期置换密码(续)为固定的正整数, K是由 {1, 设n为固定的正整数,P = C = (Z26)n , K是由 {1,2,…,n} 的所有 , 置换构成.对一个密钥π∈K 定义: π∈K, 置换构成.对一个密钥π∈K,定义: 加密变换: 加密变换: Eπ (m1, m2,.., mn) = (mπ(1),..., mπ(n)) =( c1, c2,.., cn) 解密变换: 解密变换: π (c1 , c2 ,..., cn ) = (c Dπ1cπ 1 (2) ......cπ 1 ( n ) ) ;这里π-1为π的逆置换 (1)1 2 3 4 5 6
3 6 1 5 2 4注意,这里的加密与解密变换仅仅用了置换,无代数运算. 注意,这里的加密与解密变换仅仅用了置换,无代数运算.【例2.7】给定明文为 明文为cryptography,试用密钥 】 ,试用密钥π= = (3 5 1 6 4 2)的置换密码对其进行加密,然后再对密文进 的置换密码对其进行加密, 的置换密码对其进行加密 行解密. 行解密. 对明文分组, 解:密钥长度是6,所以按周期长度 对明文分组,对每组字 密钥长度是 ,所以按周期长度6对明文分组 母用密钥π 进行重排得到对应的加密结果. 母用密钥 进行重排得到对应的加密结果. 明文分组为: 明文分组为:crypto|graphy,再利用置换密钥 进行加密变 ,再利用置换密钥π进行加密变 换,得:Eπ (crypto) = (ytcopr); Eπ (graphy) = (ahgypr) 即密文消息为ytcoprahgypr. 即密文消息为 .22/67 第2章 古典密码技术2.2.1周期置换密码(续) 周期置换密码(1 1显然由加密置换可求出逆置换, 4), ),根 显然由加密置换可求出逆置换, π =(3 6 1 5 2 4),根 即可直接明文. 据密文和逆置换 π 即可直接明文. 必须要指出的是,置换密码在实质上是Hill密码的特例, Hill密码的特例 必须要指出的是,置换密码在实质上是Hill密码的特例,下面给出 分析. 分析. 给定一个集合{1 {1, .,n}的置换 的置换π 写出置换矩阵为: 给定一个集合{1,2, . . .,n}的置换π,写出置换矩阵为:Kπ = (kij )n×n 1 若j = π (i) kij =
否则 0;表示仅第 i 行中第π(i)个元素为1, 其余为零.这时,置换矩阵是每一行和每一列都刚好有一个 这时,置换矩阵是每一行和每一列都刚好有一个&1&,而其余元素为 , π &0&的稀疏矩阵.如例2.7的加解密置换π=(3 5 1 6 4 2), 的稀疏矩阵. 2.7的加解密置换 2), = 的稀疏矩阵 如例2.7的加解密置换π=(3 ( 0 4),对应的置换矩阵为: ),对应的置换矩阵为 3 6 1 5 2 0 41 0 0对应的置换矩阵为: 0 0 1 0 0 0 ), 010
00 0 0 1 0
0 0 0 0 1 0 0 1 0 0
1 0 0 0 0K π 10
00 0 0 0 1
0 0 0 1 0 1 0 0 0 0
0 0 1 0 023/67 第2章 古典密码技术2.2.1周期置换密码(续) 周期置换密码(E 加密变换: π 加密变换: (M)=E π (m1,m 2,...m n) = (m π (1),...,m π ( n )) = K π i M = (c1,c 2,...c n ) 解密变换: 解密变换: π (C ) = Dπ ( c1 , c2 ,..., cn ) = ( cπ 1 (1) cπ 1 ( 2 ) ......cπ 1 ( n ) ) D= 所以,置换密码实质上是输入分组的一个线性变换. 所以,置换密码实质上是输入分组的一个线性变换.K π 1 i C = M24/67 第2章 古典密码技术2.2.2列置换密码这种密码的加密方法就是将明文按行填写到一个列宽固定(设为m)的 这种密码的加密方法就是将明文按行填写到一个列宽固定( 的一个置换π 表格或矩阵中;然后按( 表格或矩阵中;然后按(1,2,…,m)的一个置换π交换列的位置次 再按列读出即得密文. 序,再按列读出即得密文. 解密时,将密文按列填写到一个行数固定( 的表格或矩阵中, 解密时,将密文按列填写到一个行数固定(也为m)的表格或矩阵中, 按置换π的逆置换交换列的位置次序,然后按行读出即得到明文. 按置换π的逆置换交换列的位置次序,然后按行读出即得到明文.置换 可看成是算法的密钥. π可看成是算法的密钥. 2.8略 参见课本, 例2.8略,参见课本, 请读者思考, 2.8列置换密码中 列置换密码中, 请读者思考,在例2.8列置换密码中,如果明文字母的长度不是列宽m的 整倍数,加解密时会有什么问题,应如何处理? 整倍数,加解密时会有什么问题,应如何处理? 由于置换密码只需打乱原明文字符的排列顺序形成乱码来实现加密变换 ,因此,置换的方法还有很多,例如,图形置换密码就是先按一定的方向把 因此,置换的方法还有很多,例如, 明文输入到某种预先规定的图形中,再按另一种方向输出密文字符, 明文输入到某种预先规定的图形中,再按另一种方向输出密文字符,不足部 分填入随机字符,这里就不一一列举了. 分填入随机字符,这里就不一一列举了.25/67 第2章 古典密码技术2.3 转轮机密码转轮机的基本结构由一个键盘,若干灯泡和一系列转轮组成,如图1.4 1.4( 转轮机的基本结构由一个键盘,若干灯泡和一系列转轮组成,如图1.4( 所示.键盘一共有26个键,键盘上方就是标示了字母的26个小灯泡, 26个键 26个小灯泡 a)所示.键盘一共有26个键,键盘上方就是标示了字母的26个小灯泡,当键 盘上的某个键被按下时, 盘上的某个键被按下时,与这个字母被加密后的密文字母所对应的小灯泡就亮 了起来.在显示器的上方是几个转轮,每个转轮是26个字母的任意组合. 26个字母的任意组合 了起来.在显示器的上方是几个转轮,每个转轮是26个字母的任意组合. 如图2.2是一个三转轮的原理示意图,图中3个矩形框代表3个转轮, 2.2是一个三转轮的原理示意图 如图2.2是一个三转轮的原理示意图,图中3个矩形框代表3个转轮,从左到 右分别称为慢转子,中转子和快转子.每个转轮有26个输入引脚和26 26个输入引脚和26个输出引 右分别称为慢转子,中转子和快转子.每个转轮有26个输入引脚和26个输出引 其内部连线将每个输入引脚连接到一个对应的输出引脚, 脚,其内部连线将每个输入引脚连接到一个对应的输出引脚,这样每个转轮内 部相当于一个单表替代.当按下某一键时,电信号从慢转子的输入引脚进入, 部相当于一个单表替代.当按下某一键时,电信号从慢转子的输入引脚进入, 通过内部连线经过每个转轮, 通过内部连线经过每个转轮,最后从快转子的输出引脚信号输出对应密文字母 点亮).例如,在图2.2 ).例如 2.2( 如果按下字母B (点亮).例如,在图2.2(a)中,如果按下字母B,则相应电信号被加到慢 转子的输入引脚25 并通过内部连线连接到慢转子的输出引脚25 25, 25, 转子的输入引脚25,并通过内部连线连接到慢转子的输出引脚25,经过中转子 的输入引脚22和输出引脚22 连接到快转子的输入引脚13 22和输出引脚22, 13, 的输入引脚22和输出引脚22,连接到快转子的输入引脚13,最后从快转子的输 出引脚13输出密文字母( 13输出密文字母 出引脚13输出密文字母(I).26/67 第2章 古典密码技术 如果转轮密码机始终保持图2.2( 如果转轮密码机始终保持图2.2(a)的连接状态,则按下字母键B,输出的 2.2 的连接状态,则按下字母键B 密文字母始终是I 按下字母键A 输出的密文字母则始终是B 等等), ),转轮 密文字母始终是I(按下字母键A,输出的密文字母则始终是B,等等),转轮 密码机为了能够实现复杂的多表替代密码, 密码机为了能够实现复杂的多表替代密码,打破明文与密文之间固定的替代关 在每次击键输出密文字母后,快转子都要转动一个位置, 系,在每次击键输出密文字母后,快转子都要转动一个位置,以改变中转子与 快转子之间的对应关系.例如,在图2.2 2.2( 的初始状态下, 快转子之间的对应关系.例如,在图2.2(a)的初始状态下,如果按下任意一 个键( 转轮密码机输出密文字母( 键对应密文字母为I),然后 个键(如B键)后,转轮密码机输出密文字母(B键对应密文字母为I),然后 快转子转动一个位置,即快转子的所有引脚向下循环移动一个位置, 快转子转动一个位置,即快转子的所有引脚向下循环移动一个位置,此时转轮 密码机的状态如图2.2 2.2( 所示.显然,这时若再按下B 密码机的状态如图2.2(b)所示.显然,这时若再按下B键,最后从快转子输 出的密文变为字母Q 而不是上一次的字母I 出的密文变为字母Q,而不是上一次的字母I. 转轮密码机的每个转子都有可能转动,当快转子转动26次后, 转轮密码机的每个转子都有可能转动,当快转子转动26次后,中转子就转动 26次后 一个位置;当中转子转动26次后,慢转子就转动一个位置.因此,在加密( 26次后 一个位置;当中转子转动26次后,慢转子就转动一个位置.因此,在加密(或 解密)26×26×26=17576个字母后 所有转轮就会恢复到初始状态. 个字母后, 解密)26×26×26=17576个字母后,所有转轮就会恢复到初始状态.也就是 的多表替代密码.实际上, 说,有n个转轮的转轮密码机是一个周期长度为 26 的多表替代密码.实际上, 转轮密码机还利用了键盘和第一个转子之间的连接板实现的简单替换, 转轮密码机还利用了键盘和第一个转子之间的连接板实现的简单替换,以增加 输出的可能性来对抗穷举破译法,其详细过程这里就不再赘述. 输出的可能性来对抗穷举破译法,其详细过程这里就不再赘述.n27/67 A 24 21 B 25 03 C 26 15 D 01 01 E 02 19 F 03 10 G 04 14 H 05 26 I 06 20 J 07 08 K 08 16 L 09 07 M 10 22 N 11 04 O 12 11 P 13 05 Q 14 17 R 15 09 S 16 12 T 17 23 U 18 18 V 19 02 W 20 25 X 21 06 Y 22 24 Z 23 慢 1326 20 01 01 02 06 03 04 04 15 05 03 06 14 07 12 08 23 09 05 10 16 11 02 12 22 13 19 14 11 15 18 16 25 17 24 18 13 19 07 20 10 21 08 22 21 23 09 24 26 25 中 1701 08 02 18 03 26 04 17 05 20 06 22 07 10 08 03 09 13 10 11 11 04 12 23 13 05 14 24 15 09 16 12 17 25 18 16 19 19 20 06 21 15 22 21 23 02 24 07 25 01 26 快 14A B C D E F G H I J K L M N O P Q R S T U V W X Y ZA→B B→I C→E ……A→E B→Q C→T ……A 24 21 B 25 03 C 26 15 D 01 01 E 02 19 F 03 10 G 04 14 H 05 26 I 06 20 J 07 08 K 08 16 L 09 07 M 10 22 N 11 04 O 12 11 P 13 05 Q 14 17 R 15 09 S 16 12 T 17 23 U 18 18 V 19 02 W 20 25 X 21 06 Y 22 24 Z 23 慢 1326 20 01 01 02 06 03 04 04 15 05 03 06 14 07 12 08 23 09 05 10 16 11 02 12 22 13 19 14 11 15 18 16 25 17 24 18 13 19 07 20 10 21 08 22 21 23 09 24 26 25 中 1726 14 01 08 02 18 03 26 04 17 05 20 06 22 07 10 08 03 09 13 10 11 11 04 12 23 13 05 14 24 15 09 16 12 17 25 18 16 19 19 20 06 21 15 22 21 23 02 24 07 25 快 01A B C D E F G H I J K L M N O P Q R S T U V W X Y Z初始设置在一次击键后的设置 第2章 古典密码技术使用转轮密码机通信时, 使用转轮密码机通信时,发送方首先要调节各个转轮的 位置(这个转轮的初始位置就是密钥), ),然后依次键入 位置(这个转轮的初始位置就是密钥),然后依次键入 明文,并把显示器上灯泡闪亮的字母依次记下来, 明文,并把显示器上灯泡闪亮的字母依次记下来,最后 把记录下的闪亮字母按照顺序用正常的电报方式发送出 去; 接收方收到电文后,只要也使用同样一台转轮机, 接收方收到电文后,只要也使用同样一台转轮机,并按 照原来的约定, 照原来的约定,把转轮的位置调整到和发送方相同的初 始位置上,然后依次键入收到的密文, 始位置上,然后依次键入收到的密文,显示器上自动闪 亮的字母就是明文了. 亮的字母就是明文了.29/67 第2章 古典密码技术2.4 古典密码的统计分析在对密码进行安全分析时,一般假设密码分析者知道密码体制,这就是 在对密码进行安全分析时,一般假设密码分析者知道密码体制, Kerckhoffs假设,密码分析重点在获取密钥. Kerckhoffs假设,密码分析重点在获取密钥. 假设 移位密码,仿射密码,维吉尼亚密码,置换密码等对己知明文攻击都是 移位密码,仿射密码,维吉尼亚密码, 非常脆弱的.即使用惟密文攻击,大多数古典密码体制都容易被攻破.大多 非常脆弱的.即使用惟密文攻击,大多数古典密码体制都容易被攻破. 数古典密码体制都不能很好隐藏明文消息的统汁特征. 数古典密码体制都不能很好隐藏明文消息的统汁特征. 下面就针对单表替代密码,多表替代密码和Hill密码来介绍利用英文语 下面就针对单表替代密码,多表替代密码和Hill密码来介绍利用英文语 Hill 言的统计特征和密码特点,运用惟密文攻击或已知明文攻击等方式破译古典 言的统计特征和密码特点, 密码的基本方法. 密码的基本方法.2.4.1 单表替代密码分析对于单表替代密码,加法密码和乘法密码的密钥量比较小, 对于单表替代密码,加法密码和乘法密码的密钥量比较小,可利用穷举 密钥的方法进行破译.仿射密码,多项式密码的密钥量也只有成百上千, 密钥的方法进行破译.仿射密码,多项式密码的密钥量也只有成百上千,古 代密码分析者企图用穷举全部密钥的方法破译密码可能会有一定困难, 代密码分析者企图用穷举全部密钥的方法破译密码可能会有一定困难,然而 计算机出现后这就很容易了. 计算机出现后这就很容易了.30/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 本质上,密文字母表是明文字母表的一种排列. 本质上,密文字母表是明文字母表的一种排列.但企 图使用计算机穷举一切密钥来破译密钥词组替代密码也 是计算不可行的. 是计算不可行的. 穷举不是攻击密码的惟一方法, 穷举不是攻击密码的惟一方法,密码分析者便可利 用语言的统计特性进行分析. 用语言的统计特性进行分析.如果明文语言的这种统计 特性在明文中有所反映, 特性在明文中有所反映,密码分析者便可通过分析明文 和密文的统计规律而破译密码. 和密文的统计规律而破译密码. 通过对大量英文语言的研究可以发现, 通过对大量英文语言的研究可以发现,每个字母出现 的频率不一样, 出现的频率最高. 的频率不一样,e出现的频率最高.如果所统计的文献足 够长,便可发现各字母出现的频率比较稳定.如表2.4 2.4所 够长,便可发现各字母出现的频率比较稳定.如表2.4所 示(表中字母出现频率为字母出现次数除以文本字母总 数).31/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)表2.4 26个英文字母出现频率统计表 26个英文字母出现频率统计表字母 a b c d e f g h i j k l m出现频率 0.9 0.8 0.9 0.8 0.3 0.9 0.0249字母 n o p q r s t u v w x y z出现频率 0.7 0.2 0.7 0.9 0.9 0.9 0.000832/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)通过对26个英文字母出现频率的分析,可以有以下结果: 通过对26个英文字母出现频率的分析,可以有以下结果: 26个英文字母出现频率的分析出现的频率最大,约为0.13 0.13; (1)e出现的频率最大,约为0.13; (2)t,a,o,i,n,s,h,r出现的频率约在0.06～0.1之 出现的频率约在0.06～0.1之 0.06 间; 出现的频率在0.04附近; 0.04附近 (3)d,l出现的频率在0.04附近; 出现的频率约在0.015 0.015～ (4)c,u,m,w,f,g,y,p,b出现的频率约在0.015～ 0.029之间 之间; 0.029之间; 出现的频率小于0.01 0.01. (5)v,k,j,x,q,z出现的频率小于0.01.在密码分析中,除了考虑单字母统计特性外,掌握双字母, 在密码分析中,除了考虑单字母统计特性外,掌握双字母,三字母的 统计特性以及字母之间的连缀关系等信息也是很有用的. 统计特性以及字母之间的连缀关系等信息也是很有用的. 出现频率最高的30个双字母组合依次是: 30个双字母组合依次是 出现频率最高的30个双字母组合依次是:th he stin ener atan tore nted haones33/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)nd ou ea ng as et it ar te se 出现频率最高的20个三字母组合依次是: 20个三字母组合依次是 出现频率最高的20个三字母组合依次是: the ere was hat his ing ent eth she sth and tha for ion ers or hi ti of her nth dth int ver is 特别的,the出现的频率几乎是ing的3倍,这在密码分析中很有用.此 特别的,the出现的频率几乎是ing的 出现的频率几乎是ing 这在密码分析中很有用. 统计资料还表明:英文单词以e 字母结尾的超过一半. 外,统计资料还表明:英文单词以e,s,d,t字母结尾的超过一半.英 文单词以t 为起始字母的约占一半. 文单词以t,a,s,w为起始字母的约占一半.
以上这些统计数据是通过非专业性文献中的字母进行统计得到的.对于 以上这些统计数据是通过非专业性文献中的字母进行统计得到的. 密码分析者来说,这些都是十分有用的信息.除此之外, 密码分析者来说,这些都是十分有用的信息.除此之外,密码分析者对 明文相关知识的掌握对破译密码也是十分重要的. 明文相关知识的掌握对破译密码也是十分重要的.34/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)字母和字母组的统计数据对于密码分析者是十分重要的. 字母和字母组的统计数据对于密码分析者是十分重要的.因为它们可以 提供有关密钥的许多信息. 提供有关密钥的许多信息. 对于字母e比其它字母的频率都高得多,如果是单表替代密码, 对于字母e比其它字母的频率都高得多,如果是单表替代密码,可以预 计大多数密文都将包含一个频率比其它字母都高的字母. 计大多数密文都将包含一个频率比其它字母都高的字母.当出现这种情况 猜测这个字母所对应的明文字母为e 时,猜测这个字母所对应的明文字母为e,进一步比较密文和明文的各种统 计数据及其分布,便可确定出密钥,从而破译单表替代密码. 计数据及其分布,便可确定出密钥,从而破译单表替代密码. 下面通过一个具体实例来说明如何借助于英文语言的统计规律来破译单 表替代密码.该例子取自参考文献[1] [1]. 表替代密码.该例子取自参考文献[1]. 2.9】设某一段明文经单表替代密码加密后的密文如下, 【例2.9】设某一段明文经单表替代密码加密后的密文如下, YIFQ FMZR WQFY VECF MDZP CVM R ZWNM DZVE JBTX CDDUMJ NDIF EFMD ZCDM QZKC EYFC JMYR NCWJ CSZR EXCH ZUNMXZ NZUC DRJX YYSM RTMEYIFZ WDYV ZVYF ZUMR ZCRW NZDZJJ XZWG CHSM RNMD HNCM FQCH ZJMX JZWI EJYU CFWD JNZDIR 试分析出对应密文.为了表述更加清楚,本例的密文用大写字母, 试分析出对应密文.为了表述更加清楚,本例的密文用大写字母,明文 用小写字母. 用小写字母.35/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)将加密变换记为Ek 解密变换记为Dk 密文中共有168个字母. Ek, Dk, 168个字母 解:将加密变换记为Ek,解密变换记为Dk,密文中共有168个字母. 第一步:统计密文中各个字母的出现次数和频率,如表2.5所示. 2.5所示 第一步:统计密文中各个字母的出现次数和频率,如表2.5所示.表2.5 例2.9中各个密文字母的出现次数和频率 2.9中各个密文字母的出现次数和频率36/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)第二步:从出现频率最高的几个字母及双字母组合,三字母组合开始, 第二步:从出现频率最高的几个字母及双字母组合,三字母组合开始, 并假定它们是英语言中出现频率较高的字母及字母组合对应的密文, 并假定它们是英语言中出现频率较高的字母及字母组合对应的密文,逐步推测 各密文字母对应的明文字母. 各密文字母对应的明文字母. 从表2.5可以看出,密文字母Z出现的次数高于任何其他密文字母,出现 从表2.5可以看出,密文字母Z出现的次数高于任何其他密文字母, 2.5可以看出 频率约为0.12 因此,可以猜测: 0.12. 出现至少10 10次的密文字母 频率约为0.12.因此,可以猜测:D K ( Z ) = e,除Z外,出现至少10次的密文字母 它们的出现频率约在0.06 0.095之间 因此, 0.06～ 之间. 为C,D,F,J,M,R,Y,它们的出现频率约在0.06～0.095之间.因此,可以 猜测密文字母{C {C, Y}可能对应于明文字母集合{t, 可能对应于明文字母集合{t 猜测密文字母{C,D,F,J,M,R,Y}可能对应于明文字母集合{t,a,o,i, 中的字母,但不能肯定是哪一个. n,s,h,r} 中的字母,但不能肯定是哪一个. 因为已经假设密文Z解密成e,现在考虑密文中形如-Z和Z-的双字母的出 因为已经假设密文Z解密成e 现在考虑密文中形如- 现情况, 的双字母情况如表2.6所示. 2.6所示 现情况,Z的双字母情况如表2.6所示.37/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)表2.6 例2.9密文中包含字母Z的双字母出现次数 2.9密文中包含字母Z 密文中包含字母从表2.6可以发现,DZ和ZW出现4 从表2.6可以发现,DZ和ZW出现4次;NZ和ZU出现3次;RZ,HZ,XZ, 2.6可以发现 出现 NZ和ZU出现3 出现 RZ,HZ,XZ, FZ,ZR,ZV,ZC,ZD和ZJ出现 出现2 FZ,ZR,ZV,ZC,ZD和ZJ出现2次. 由于ZW出现4次而WZ一次也为出现,同时W出现的频率为0.048 ZW出现 WZ一次也为出现 0.048, 由于ZW出现4次而WZ一次也为出现,同时W出现的频率为0.048,故可 猜测 D K (W ) = d38/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 又因为DZ出现4 又因为DZ出现4次,ZD出现2次,故可猜测 D (W ) ∈{r , s, t} DZ出现 ZD出现2 出现 但具体是哪一个还不太清楚. 但具体是哪一个还不太清楚. 的假设前提下, 在 D K (W ) = d 和 D ( Z ) = e 的假设前提下,继续观察 密文会注意到密文开始部分出现的ZRW RZW, ZRW和 密文会注意到密文开始部分出现的ZRW和RZW,并且在后 面还出现了RW 因为R在密文中频繁出现, nd是一个 RW, 面还出现了RW,因为R在密文中频繁出现,而nd是一个 明文中常见的双字母组, 明文中常见的双字母组,因此可以猜测 D K ( R) = n 到目前为止,已经得到了3 到目前为止,已经得到了3个密文字母可能对应的 明文字母,下面列出明文与密文的部分对应关系: 明文字母,下面列出明文与密文的部分对应关系:KK39/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)40/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)由于NZ是密文中出现较多的双字母组, ZN不出现, 由于NZ是密文中出现较多的双字母组,而ZN不出现,所以可以猜测 NZ是密文中出现较多的双字母组 不出现 如果这个猜测是正确的,则根据明文片段ne ndhe又可以猜 ne- D k ( N ) = h .如果这个猜测是正确的,则根据明文片段ne-ndhe又可以猜 结合这个假设,明文与密文的部分对应关系进一步又有: 测 D k (c) = a .结合这个假设,明文与密文的部分对应关系进一步又有:41/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 现在再考虑出现次数排在第二的密文字母M 现在再考虑出现次数排在第二的密文字母M,由前面 分析,已密文段RNM对应的明文为nh-,这说明 RNM对应的明文为nh-,这说明h 分析,已密文段RNM对应的明文为nh-,这说明h-可能 是一个明文单词的首字母,所以M 是一个明文单词的首字母,所以M可能代表明文中的一 个元音字母. 个元音字母.因为前面猜测已经使用了 D ( c ) = a 和 D k (Z ) = e 因为明文双字母ai ao的出现次 ai比 所以猜测 D ( M ) ∈ {i, o} .因为明文双字母ai比ao的出现次 数更多, 数更多,所以可以先猜测 D k ( M ) = i ,这样明文与密 文的部分对应关系进一步又有: 文的部分对应关系进一步又有:kk42/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)43/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 下面再来确定明文o对应的密文.因为o 下面再来确定明文o对应的密文.因为o是一个常见的明文 字母,所以可以猜测相应的密文字母是D 中的一个. 字母,所以可以猜测相应的密文字母是D,F,J,Y中的一个. 的可能性最大,否则由密文片段CFM CJM将得到长串的元音 CFM或 Y的可能性最大,否则由密文片段CFM或CJM将得到长串的元音 字母aoi 这在英文中是不太可能的.因此, aoi, 字母aoi,这在英文中是不太可能的.因此,可以猜测 D k (Y ) = o 剩下密文字母中三个出现次数较高的字母是D 剩下密文字母中三个出现次数较高的字母是D,F,J,可以 密文中三字母NMD NMD出现了两 猜测它们 {D ( D ), D ( F ), D ( J )} ∈ {r , s , t } ,密文中三字母NMD出现了两 次,故可猜测 D k ( D) = s ,这样,密文NMD对应的明文三字母组 这样,密文NMD对应的明文三字母组 NMD his, 是一致的. 为his,这与前面假设 D k ( D) ∈ {r , s, t}是一致的. 对于密文片段HNCMF 可猜测它对应的明文可能是chair HNCMF, chair, 对于密文片段HNCMF,可猜测它对应的明文可能是chair, 这样, 由此又有 D k ( H ) = c ,D k ( F ) = r .这样,通过排除法有 D k ( J ) = t .k k k44/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续)45/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 第三步:利用与上述分析类似的方法, 第三步:利用与上述分析类似的方法,可以很容易地 确定其余密文字母和明文字母的对应关系,最后, 确定其余密文字母和明文字母的对应关系,最后,将得 到的明文加上标点符号,得到完整的明文如下: 到的明文加上标点符号,得到完整的明文如下: Our friend from Paris examined his empty glass surprise, with surprise,as if evaporation had taken place wasn' looking. while he wasn't looking.I poured some more wine and he settled back in his chair, face tilted up sun. towards the sun. 以上讨论的是破解一般单表替代密码的统计分析方法, 以上讨论的是破解一般单表替代密码的统计分析方法, 如果已知所用的密码体制(例如,对于位移密码, 如果已知所用的密码体制(例如,对于位移密码,加法密 乘法密码和仿射密码等), ),则相内的分析工作会更简 码,乘法密码和仿射密码等),则相内的分析工作会更简 单一些. 单一些.46/67 第2章 古典密码技术单表替代密码分析( 2.4.1 单表替代密码分析(续) 从该例子可以看出, 从该例子可以看出,破译单表替代密码的大致过程 是: 首先,统计密文的各种统计特征, 首先,统计密文的各种统计特征,如果密文量比较 则完成这步后便可确定出大部分密文字母; 多,则完成这步后便可确定出大部分密文字母; 然后,分析双字母,三字母密文组,以区分元音和 然后,分析双字母,三字母密文组, 辅音字母; 辅音字母; 最后,分析字母较多的密文, 最后,分析字母较多的密文,在这一过程中大胆使 用猜测的方法,如果猜对一个或几个词, 用猜测的方法,如果猜对一个或几个词,就会大大加快 破译过程. 破译过程.47/67 第2章 古典密码技术2.4.2 多表替代密码分析多表替代密码从一定程度上隐藏了明文消息的一些统计特征, 多表替代密码从一定程度上隐藏了明文消息的一些统计特征,破译相 对较为困难; 对较为困难; 在多表替代密码的分析中,首先要确定密钥的长度, 在多表替代密码的分析中,首先要确定密钥的长度,也就是要确定所 使用的加密表的个数,然后再分析确定具体的密钥; 使用的加密表的个数,然后再分析确定具体的密钥; 确定密钥长度的常用方法两种, Kasiski测试法 测试法( test) 确定密钥长度的常用方法两种 , 即 Kasiski 测试法 ( Kasiski test ) 和重合指数法( coincidence) 和重合指数法(index of coincidence). 下面以维吉尼亚密码为例来说明多表替代密码的分析方法. 下面以维吉尼亚密码为例来说明多表替代密码的分析方法.Kasiski测试 1. Kasiski测试Kasiski测试的基本思想是: Kasiski测试的基本思想是: 测试的基本思想是 用给定的n个字母表周期性地对明文字母加密, 用给定的 n 个字母表周期性地对明文字母加密 , 则当两个相同的明文 段在明文序列中间隔的字母数为n的整数倍时, 段在明文序列中间隔的字母数为 n 的整数倍时 , 将加密成相同的密文 段; 如果有两个相同的密文段,对应的明文段不一定相同, 如果有两个相同的密文段,对应的明文段不一定相同,但相同的可能 性大.将密文中相同的字母组找出来, 性大.将密文中相同的字母组找出来,并对其相同字母组的距离综合 分析,找出它们相同字母组距离的最大公因子, 分析,找出它们相同字母组距离的最大公因子,就有可能提取出密钥 的长度n 的长度n.48/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)考虑下面一个维吉尼亚密码的简单例子: 考虑下面一个维吉尼亚密码的简单例子: 明文: 明文:requests additional test 密钥: T E L E X T E L E X 密钥:T E L E X T E L E X T E 密文: B L T E U Q W S W J G E 密文:C A V K T A L T B L 明文包含字母序列est两次,而这两次又碰巧被同样的密钥片段加密, est两次 明文包含字母序列est两次,而这两次又碰巧被同样的密钥片段加密, 因而对应的密文都是TBL TBL. 因而对应的密文都是TBL. 出现这种情况反映了如下事实:序列est位于密钥长度(或周期) 出现这种情况反映了如下事实:序列est位于密钥长度(或周期)的整 est位于密钥长度 倍数处.显然,相同字母组的距离反映了密钥长度n的相关信息. 倍数处.显然,相同字母组的距离反映了密钥长度n的相关信息. Kasiski的测试过程如下 搜索长度至少为2 的测试过程如下: Kasiski的测试过程如下:搜索长度至少为2的相邻的一对对相同的密 文段,记下它们之间的距离. 密钥长度n 文段,记下它们之间的距离.而密钥长度n可能就是这些距离的最大公因 子.49/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)表2.7 重复字母组及距离示例50/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续) 2. 重合指数法如果考虑来自26个字母表的完全随机文本, 如果考虑来自26个字母表的完全随机文本,则每个字母都以相同的 26个字母表的完全随机文本 概率1/26出现,假定另一个随机文本放在第一个的下面, 1/26出现 概率1/26出现,假定另一个随机文本放在第一个的下面,在上下位置出 (1 现相同字母a 现相同字母a的概率为 26) 在两个随机文本的上下位置找到任意两个 , 2 26 (1 26)= 1 26 = 0.0385.但实际上,由于英文字母出 但实际上, 相同字母总的概率为 现的概率是不同的(见表2.4),设字母a,b,c,…,z出现的概率分别 现的概率是不同的(见表2.4),设字母a , 2.4),设字母 25225, 为 这样找到两个相同字母的概率为 ∑ pi = 0.065.这 i=0 个值比随机文本的概率大得多,称为重合指数. 个值比随机文本的概率大得多,称为重合指数. 1≤ i ≤ n 个字母构成, 定义 设一个语言由n个字母构成,每个字母出现的概率 p i , , 则重合指数是指其中两个随机元素相同的概率, 则重合指数是指其中两个随机元素相同的概率,记为 n 0, 1, 2,2pp p...pCI = ∑ pi2i =1=0.0385, 这样对于一个完全随机的文本CI=0.0385,与一个有意义的英语文本 =0.065,差异是比较明显的. CI=0.065,差异是比较明显的.51/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)实际分析中,重合指数的利用体现在几个方面. 实际分析中,重合指数的利用体现在几个方面. 如果密文的重合指数较低,那么就可能是多表替代密码. 如果密文的重合指数较低,那么就可能是多表替代密码.维吉尼亚密 码将密文分行,每行是单表替代密码. 码将密文分行,每行是单表替代密码. 在单表替代时,明文的字母被其它字母代替, 在单表替代时,明文的字母被其它字母代替,但不影响文本的统计属 即加密后密文的重合指数仍不变, 明文) 密文), ),由 性,即加密后密文的重合指数仍不变,CI(明文)= CI(密文),由 此可以判断文本是用单表还是用多表替代加密的. 此可以判断文本是用单表还是用多表替代加密的. 如果密钥长度(即密文分行的列数)正确, 如果密钥长度(即密文分行的列数)正确,同一行密文有相同字母的 概率接近0.065 如果密钥长度不对,则概率将大大小于0.065 0.065; 0.065, 概率接近0.065;如果密钥长度不对,则概率将大大小于0.065,显得 更随机,由此得到密钥长度(可与Kasiski测试的结果对比). Kasiski测试的结果对比 更随机,由此得到密钥长度(可与Kasiski测试的结果对比). 重合指数的估算能用于分析两个不同密文, 重合指数的估算能用于分析两个不同密文,比如接收到两段文本C1, 如果它们用同样的方式加密, C2,如果它们用同样的方式加密,则 CI (C 1) ≈ CI (C 2) . 实际密文长度有限,从密文中计算的重合指数值总是不同于理论值, 实际密文长度有限,从密文中计算的重合指数值总是不同于理论值, CI' 以字母出现的频度近似表示概率, 所以通常用CI的估计值CI',以字母出现的频度近似表示概率,则CI ' =∑Ci =1m2 xi/C =2 L∑ x (xi =1 imi 1) / L ( L
1)52/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)其中L代表密文长, 其中L代表密文长, CI' 的无偏估计值. CI'是CI的无偏估计值. 是密文出现的频度(数目).可以证明, ).可以证明 x 是密文出现的频度(数目).可以证明,i在古典密码的分析中,除了Kasiski测试和使用重合指数确定密钥 在古典密码的分析中,除了Kasiski测试和使用重合指数确定密钥 Kasiski 长度外,测试可用来确定是否采用了相同或不同的替代, 长度外,测试可用来确定是否采用了相同或不同的替代,也能用来简化 多表替代为单表替代. 多表替代为单表替代. Chi 测试(χ-test)提供了一个比较两个频率分布的直接方式.计 测试( test)提供了一个比较两个频率分布的直接方式. 算下面的和: 算下面的和: nχ =∑i =1piqi其中, 表示符号在第一个分布发生的概率, 其中, p i 表示符号在第一个分布发生的概率, q i 表示符号在第二个分 布中发生的概率. 布中发生的概率. C 当两个频率分布类似时,χ的值相对较高.假定收到两个密文 C , , 当两个频率分布类似时, 的值相对较高. 它们都是位移密码加密的结果. 它们都是位移密码加密的结果.设第一个替代表是通过源字母表移动 k 1 个字母得到, 个字母得到的. 个字母得到,第二个替代表是源字母表移动 k 个字母得到的.如果k 1 = k 2 C 是由同样位移替代密码加密的,这时χ值较大, ,说明 C , 是由同样位移替代密码加密的,这时χ值较大,因为 C 的统 k 类似.反之, 值将要小一些. 计特性与 C 类似.反之, ≠ k ,χ值将要小一些.1 2 21 2 1 21253/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)除了用来确定是否采用相同或不同的替代外, χ 除了用来确定是否采用相同或不同的替代外,也能用来简化多表 替代为单表替代. 替代为单表替代. 2.10】一个密钥为RADIO RADIO, Vigenere密码加密的明密文如下 密码加密的明密文如下: 【例2.10】一个密钥为RADIO,用Vigenere密码加密的明密文如下: 明文: 明文:execute these commands 密钥: 密钥:R A D I O R A D I O R A D I O R A D I O 密文: K E W P 密文:V X H K I S J E F W A D A Q L G 为了还原密文到明文,用下面的矩阵表示(列数等于密钥长度): 为了还原密文到明文,用下面的矩阵表示(列数等于密钥长度): R A D I O V K J D X E E A H W F Q K P W L I S A G54/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)可以看出,矩阵的第一行为密钥,第一列R下的密文字母通过 减 可以看出,矩阵的第一行为密钥,第一列R下的密文字母通过&减 &R R 解密.第二列A下的密文字母通过& 解密,等等. 解密.第二列A下的密文字母通过&减&A解密,等等.密文的第一列和 第 二列是两个不同的移位密码加密的结果. 二列是两个不同的移位密码加密的结果. 考虑密钥中每个字母和第一个字母R在字母表中的相对距离如下: 考虑密钥中每个字母和第一个字母R在字母表中的相对距离如下:现在,把第二列所有字母提前9个位置,第三列所有字母提前12个位 现在,把第二列所有字母提前9个位置,第三列所有字母提前12个位 12 其它类似,可获得下面的文本块: 置,其它类似,可获得下面的文本块:V K J DO V V RV K T ET Y F UL V D J55/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续) 这样,用密钥RADIO加密的文字,就转化为只用R 这样,用密钥RADIO加密的文字,就转化为只用R RADIO加密的文字 加密的密文, 加密的密文,即把基于多表替代密码的解密问题转化 为基于单表替代密码的解密问题. 为基于单表替代密码的解密问题. 尽管密码分析者可能没有密钥字母的相对距离这 个信息,然而,Chi测试提供了发现这个距离的线索 测试提供了发现这个距离的线索. 个信息,然而,Chi测试提供了发现这个距离的线索. 在该例中, 在该例中,密文列被移位使得它们都用同一个替代 密码解密.如果两列是用同样单表替代加密的, 密码解密.如果两列是用同样单表替代加密的,则两 列的χ值将相同,而且是最大值. 列的χ值将相同,而且是最大值.分析者通过尝试距离 直到得到这一列和第一列的χ最大值出现, 值,直到得到这一列和第一列的χ最大值出现,然后就 可用和第一列同样的方式解密. 可用和第一列同样的方式解密.56/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)2.11】在很短的时间内收到两段密文: 【例2.11】在很短的时间内收到两段密文: 密文C1: K O O M M A C O M O Q E G L X X M Q C C K U E Y F C U R Y L Y L I G Z S X C X V B C K M Y O P N P O G D G I A Z T X D D I A K N V O M X H I E M R D E Z V X B M Z R N L Z A Y Q I Q X G K K K P N E V H O V V B K K T C S S E P K G D H X Y V J M R D K B C J U E F M A K N T D R X B I E M R D P R R J B X F Q N E M X D R L B C J H P Z T V V I X Y E T N I I A W D R G N O M R Z R R E I K I O X R U S X C R E T V 密文C2: Z A O Z Y G Y U K N D W P I O U O RI Y R H H B Z X R C E A Y V X U V T X K C M A X S T X S E P B R X C S L R U K V B X T G Z U G G D W H X M X C S B I K T N S L R J Z H B X M S P U N G Z R G K U D X N A U F C M R Z X J R Y W Y M I57/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续) 由于这两段密文相隔时间很短, 由于这两段密文相隔时间很短,很有可能是用同样方式 加密的. CI'值来证实( 加密的.这个猜想可以通过计算两个文本的CI'值来证实( 计算过程从略): 计算过程从略):CI '(C 1) = 0.0421, CI '(C 2) = 0.0445这两个值近似相等, 这两个值近似相等,所以可假定这两段文本是用同样方 式加密的. 式加密的. CI' CI' 考虑到CI'值处在随机文本和有意义的英语文本的CI'值之 间,因此可猜想是用多表替代加密的. 因此可猜想是用多表替代加密的. 采用Kasiski测试, Kasiski测试 采用Kasiski测试,首先找到重复的字母序列及它们之间 的距离;分解这些距离值为素因子的乘积,数字7 的距离;分解这些距离值为素因子的乘积,数字7出现最频 周期可能为7 现在把密文写成是7列的矩阵形式( 繁,周期可能为7,现在把密文写成是7列的矩阵形式(见表 2.8). 2.8).58/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)表2.8 密文的矩阵表示59/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)然后计算每列的重合指数, 然后计算每列的重合指数,有: CI' CI' CI'(列1)=0.0522 CI'(列2)=0.0801 CI' CI' CI'(列4)=0.0744 CI'(列5)=0.0705 CI' CI'(列7)=0.0606CI' CI'(列3)=0.0734 CI' CI'(列6)=0.0717但观察每一列的重合指数, 但观察每一列的重合指数,似乎每一列都是用一个单表替代密码加 密的.现在试图将多表替代的密文转化为某个单表替代加密的密文. 密的.现在试图将多表替代的密文转化为某个单表替代加密的密文.首 重复移动各列字母,移动的距离分别是1 25, 先,重复移动各列字母,移动的距离分别是1～25,并分别计算相对于 第一列的χ 并把最大值用下划线标识出来. 第一列的χ值,并把最大值用下划线标识出来. 列1和2:0.7 0.6 0.0 0.2 0.0 0.1 0.0 0.9 0.1 0.8 0.8 0.5 0.030260/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)列1和3:0.4 0.2 列1和4:0.8 0.6 列1和5:0.6 0.1 0.1 0.0 0.1 0.3 0.1 0.0 0.4 0.2 0.1 0.6 0.9 0.2 0.3 0.2 0.0 0.9 0.7 0.0 0.9 0.8 0.7 0.9 0.1 0.8 0.4 0.1 0.5 0.6 0.5 0.0 0.6 0.041161/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)列1和6:0.2 0.5 列1和7:0.7 0.4 0.2 0.2 0.4 0.6 0.5 0.4 0.1 0.0 0.8 0.4 0.03380.2 0.7 0.3 0.3 0.6 0.0 0.8 0.4 0.7 0.9 0.0295根据以上结果推知,各列相对于第一列的距离分别是: 根据以上结果推知,各列相对于第一列的距离分别是: 列2:13 列3:22 列4:7 列5:2 列6:19 列7:1562/67 第2章 古典密码技术多表替代密码分析( 2.4.2 多表替代密码分析(续)到下列文本: 用这些值来转化密文C1,C2到下列文本: K B K T O T R O Z K X G Z A X K I X E V Z U R U M E N G Y Y U S K Z O S K Y G X U R K Z U V R G E O T Z N K T O T K Z K K T Z N I K T Z A X E Z N K G S K X O I G T G A Z N U X K J M G X G R R G T V U K C X U Z K G Y Z U X E K T Z O Z R K J Z N K M U R J H A M O T Z N G Z Y Z U X C Z N K R K G J O T M S G T M K Z Y N U R J U L G V O K I K U L V G X I N S K T Z C O Z N G T K T I X E V Z K J S K Y Y G M K Z N K G A Z N U X J K Y I X O H K Y K R G H U X G Z K R E N U C Z N K R K G J O T M S G T Z G I Q R K Y Z N K J K I X E V Z O U T C K Y A M M K Y Z Z U X K G J Z N K Y Z U X E O L E U A C G T Z Z U Q T U C N U C Z N G Z C G Y J U T K63/67 第2章 古典密码技术Hill密码的已知明文分析 2.4.3 对Hill密码的已知明文分析Hill密码能较好地抵抗字母频率的统计分析,采用惟密文攻击是较 密码能较好地抵抗字母频率的统计分析, 密码能较好地抵抗字母频率的统计分析 难攻破,但采用已知明文攻击就容易破译. 难攻破,但采用已知明文攻击就容易破译. 假定密码分析者知道加密分组长度n值 且有至少 ( & ) 假定密码分析者知道加密分组长度 值,且有至少N(N&n)个不同 的明文/密文分组对, 满足: 的明文 密文分组对,M1/ C1, M 2/ C 2,……, M N/ C N 满足: 密文分组对 , C 1= K M1(mod26), C 2= K M1(mod26),...,C N = K M N(mod26) 记为: 记为:(C1 C2 C3 … C N )=(M1 M2 M3 … M N )K (mod26) 其中M i,C i(i=1,2,…,N)均为 维列向量,K为未知密钥方阵. 维列向量, 为未知密钥方阵 为未知密钥方阵. 其中 , , , )均为n维列向量 利用n个已知的明文 密文分组对定义两个 方阵: 利用 个已知的明文/密文分组对定义两个 ×n方阵: 个已知的明文 密文分组对定义两个n× 方阵 M =(M1 M2 M3 … M n ) , C = (C1 C2 C3 … C n ) 有矩阵方程:C 有矩阵方程 = K M(mod26) ( ) 若提供的矩阵M是可逆的,则能计算出 若提供的矩阵 是可逆的,则能计算出K = C M-1(mod26),从而破译 是可逆的 , 该密码体制. 该密码体制. 若方阵M关于模 不可逆 攻击者可通过尝试其它明文/密文对来产 若方阵 关于模26不可逆,攻击者可通过尝试其它明文 密文对来产 关于模 不可逆, 生新的方阵M 直到找到一个可逆的明文矩阵M就可破译 就可破译Hill密码. 密码. 生新的方阵 ,直到找到一个可逆的明文矩阵 就可破译 密码64/67 第2章 古典密码技术Hill密码的已知明文分析 密码的已知明文分析( 2.4.3 对Hill密码的已知明文分析(续)2.12】假设明文worker worker利用 =2的Hill密码加密 得到密文qihryb 密码加密, qihryb, 【例2.12】假设明文worker利用n=2的Hill密码加密,得到密文qihryb, 求密钥K 求密钥K. 将明文,密文划分为三组:(w, ),(r, ),(e, (q, 解:将明文,密文划分为三组:(w,o ),(r,k ),(e,r ) 和 (q,I (h, (y, ), 22,14),(17, ),(17 (4, )和 ) ,(h,r ) ,(y,b ),即(22,14),(17,10 ) ,(4,17 )和( 16, ),(7 (7, (24, ),分别满足: 16,8),(7,17 ) ,(24,1 ),分别满足: 16
利用前两个明文-密文对,构造矩阵方程: 利用前两个明文-密文对,构造矩阵方程:16 7
14 10 22 17 det
= 18, 计算明文方阵行列式, 计算明文方阵行列式, 14 10 由于(-18,26) (-18,26 即该矩阵没有逆元,于是考虑第二, 由于(-18,26)≠1,即该矩阵没有逆元,于是考虑第二,第三组明 密文对,得到矩阵方程: 文-密文对,得到矩阵方程: 7 24
65/67 第2章 古典密码技术Hill密码的已知明文分析 密码的已知明文分析( 2.4.3 对Hill密码的已知明文分析(续) ∵ ∴17 4
= 249, 249 × 7 ≡ 1 mod 26 10 17
mod 26 17 1
1显然,通过对比第一个明文—密文对很容易验证该密钥. 显然,通过对比第一个明文—密文对很容易验证该密钥. 如果密码分析者不知道加密分组长度l的值,那么可以通 的值, 值来得到密钥. 过逐一尝试不同的l值来得到密钥. Hill密码体制的重要性在于它无可辩驳地表明数学方 Hill密码体制的重要性在于它无可辩驳地表明数学方 法在密码学中的地位是不容置疑的. 法在密码学中的地位是不容置疑的.66/67 第2章 古典密码技术本章小结本章主要介绍了古典密码技术,包括替代密码, 本章主要介绍了古典密码技术,包括替代密码,置 换密码以及转轮机密码, 换密码以及转轮机密码,重点阐述了古典密码的统计分 包括: 析,包括:
单表替代密码分析
多表替代密码分析
对Hill密码的已知明文分析密码系统的安全性 Hill密码的已知明文分析 密码的已知明文分析密码系统的安全性67/67
第2章 古典密码学——为大家提供各种日常写作指导，同时提供范文参考。主要栏目有：范文大全、个人简历、教案下载、课件中心、 优秀作文、考试辅导、试题库、诗词鉴赏。
相关文档：
下载文档：
搜索更多：
All rights reserved Powered by
copyright ©right 。甜梦文库内容来自网络，如有侵犯请联系客服。|}
我要回帖
更多推荐
- ·老美评选：最佳全空气空调系统品牌系统空调品牌你会选择哪个？
- ·这个女女明星演员表全部名单叫什么？
- ·大张伟是姓大吗叫什么
- ·把一个人的照片和八字压在香炉下压八字照片好不好？
- ·vivoy5s手机来电闪光灯怎么设置一直有小红点闪，肉眼看不见，手机可以看到，这样也是吗？
- ·$.getJSON()函数内的数据不能传到在函数中定义全局变量量是怎么回事？
- ·在preamble fomat0配置下，那么prah重配置白玉兰树下可配置置多少条
- ·19楼怎么加入爱情幸运星之打望号
- ·thinkpad t440和t450T440本16Gssd+1Thdd硬盘关于IRST的问题
- ·别克君威空调滤芯位置的电脑接线头在什么位置
- ·我想跳舞，特别是古典舞演出。我吗不给我学了，可我太喜欢了!上次学校文化演出，已经两年没写的我自己编了一
- ·ios7越狱safari闪退后Safari/邮件/天气/计算器闪退，7.1.1版本
- ·能录音的嗽叭还能用的云点播播优盘用，那优盘中放什么格式的音乐能识别
- ·一个谷歌地图下载器下载器，上边是一个大G的附号
- ·GSK990M，斜槽风机程序编写
- ·《 嗜血穿越女特工嗜血太子妃安曦禾：异能太子妃》的小说在哪下载？
- ·西,原,日,目,北,心,青,少,女,月项目管理机构组成表字
- ·bfg 3dm简体中文硬盘版3dm的gta5怎么安装装啊
- ·photoshop cs6错误16配置错误16怎么解决啊~~~
- ·58同城网上兼职招聘 工资日结 58同城兼职是真的吗吗
- ·用加密矩阵加密算法为a=(1 3 2 0 )的希尔密码加密明文:the sky is blue and
- ·用银行卡在支付宝钱包转银行卡交电费后怎么把银行卡号删除
- ·sexi vediosNSEX新地址是多少给发个
- ·vb.net的不将查询结果导入excel怎么导出为excel或word
- ·hadoop工作流程原理
- ·苹果彻底删除微信记录手机6微信聊天记录删除了怎么恢复
- ·支付宝退款账单显示收入的钱数是不是就说明退款成功了
- ·cmake的使用怎么开始使用
- ·有人诋毁自己做微商软文的产品怎么发软文
- ·ledled 投影机 高清usb接口不能用
- ·我电脑玩不了大型玩游戏的电脑配置，如何要玩该如何配置
- ·大主宰 月流水今日6月10怎么登不了
- ·求PS小手拉大手尤克里里谱帮忙修图
- ·为什么手机系统打开wifi老是进入qqwifi驱动呢?
- ·我想自学安卓编程软件开发基础，有什么建议啊?我想两个月内学会~
