密码学详细介绍特此推荐.ppt

1、应用密码学,第1章 密码学概述 第2章 古典密码技术 第3章 分组密码 第4章 公钥密码体制 第5章 散列函数与消息鉴别 第6章 数字签名技术 第7章 密钥管理技术 第8章 身份鉴别技术 第9章 序列密码 第10章 密码技术应用,课程主要内容,第2章 古典密码技术,本章主要内容 替代密码 单表替代密码 多表替代密码 置换密码 周期置换密码 列置换密码 转轮机密码,第2章 古典密码技术,2.1 替代密码 本质：以一个字母替代另一个字母 使用一个固定的替代：单表替代密码 使用一个以上的替代：多表替代密码,第2章 古典密码技术,一般单表替代密码 【例2.1】设置换的对应关系如下： a b c d e

2、 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加密，所得 密文消息为： (m) (e) (s) (s) (a) (g) (e)=dtllqut,2.1.1 单表替代密码（续）,一般单表替代密码算法特点： 密钥空间K很大，|K|=26!=41026 ，破译者穷举搜索计算不可行， 1 微秒试一个密钥，遍历全部密钥需要10

3、13 年。 密钥不便记忆。,第2章 古典密码技术,移位密码 明文空间M、密文空间C都是和密钥空间K满足 即把26个英文字母与整数0，1，2，25一一对应，如表2.1所示。,2.1.1 单表替代密码（续）,表2.1 字母数字映射表,加密变换: E=E:Z26Z26, Ek (m) = m + k (mod26)| mM, kK 解密变换: D=D:Z26Z26, Dk (c) = ck (mod26)| cC, kK 显然，移位密码是前面一般单表替代密码的一个特例 当移位密码的 密钥k=3时，就是历史上著名的凯撒密码（Caesar） 根据其加密函数特 点，移位密码也称为加法密码,第2章 古典密码

4、技术,仿射密码 仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为 K=(k1，k2)| k1，k2Z26，gcd(k1，26)=1 对任意mM，cC，k = (k1，k2)K， 加密变换为: c = Ek (m) = k1 m +k2 (mod 26) 解密变换为： m = Dk (c) = k11 (ck2) (mod 26) 其中， 。 明显，k1=1时即为移位密码 另外，k2=1则称为乘法 密码,2.1.1 单表替代密码（续）,第2章 古典密码技术,【例2.3】设明文消息为china，密钥 试用仿射密码对其进行 加密，然后再进行解密。 解：利用扩展的欧几里德算法，可计算出 加密变

5、换为： 解密变换为： 其中， 明文消息对应的数字依次为2，7，8，13，0，用仿射密码对明文进行加密 如下：,2.1.1 单表替代密码（续）,第2章 古典密码技术,而解密过程如下： 即恢复明文消息为china。 仿射密码要求(k1, 26)=1 (同余方程唯一解条件) ，否则就会有多个明文字母对应一个密文字母的情况。由于与26互素的整数有12个，故仿射密码密钥空间大小为 |K|=1226=312,2.1.1 单表替代密码（续）,第2章 古典密码技术,密钥短语密码 选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后，就可构

6、造出一个字母替代表。如密钥为key时，替代表如表2.2所示。 表2.2 密钥为key的单表替代密码 当选择上面的密钥进行加密时，若明文为“china”，则密文为“yfgmk”。 显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语 的情况时，密钥短语密码最多可能有26!=41026个不同的替换表。,2.1.1 单表替代密码（续）,第2章 古典密码技术,2.1.1 单表替代密码（总结）,方便记忆,密码名称 编码规则 一般单表替代 杂乱无章 移位密码 加法 仿射密码 线性变换 多项式密码 多项式函数 密钥短语密码 短语,第2章 古典密码技术,2.1.2 多表替代密码 单表替代密码表现出明

7、文中单字母出现的频率分布与密文中相同，统计分析方法可用于此密码的破译。 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布，其中每个映射是简单替代密码中的一对一映射。 多表替代密码将明文字母划分为长度相同的消息单元，称为明文分组，对明文成组地进行替代，同一个字母有不同的密文，改变了单表替代密码中密文的唯一性，使密码分析更加困难。,第2章 古典密码技术,多表替代密码的特点是使用了两个或两个以上的替代表。著名的维吉尼亚密码和Hill密码等均是多表替代密码。 1.维吉尼亚密码 维吉尼亚密码是最古老而且最著名的多表替代密码体制之一，与位移密码体制相似，但维吉尼亚密码的密钥是动态

8、周期变化的。 该密码体制有一个参数n。在加解密时，同样把英文字母映射为025的数字再进行运算，并按n个字母一组进行变换。明文空间、密文空间及密钥空间都是长度为n的英文字母串的集合，因此可表示 设密钥 k=(k1,k2,kn), 明文m=(m1,m2,mn), 加密变换为： Ek(m)=(c1,c2,cn), 其中ci= (mi + ki)(mod26)，i =1,2,n 对密文 c=(c1,c2,cn), 解密变换为： Dk(c)=(m1,m2,mn), 其中 mi=(ci ki)(mod26)，i =1,2,n,2.1.2 多表替代密码（续）,第2章 古典密码技术,【例2.4】设密钥k =c

9、ipher，明文消息appliedcryptosystem， 试用维吉尼亚密码对其进行加密，然后再进行解密。 解：由密钥k=cipher，得n=6，密钥对应的数字序列为 (2，8，15，7，4，17)。然后将明文按每6个字母进行分组，并转换这些明文字母为相应的数字，再用模26加上对应密钥数字，其加密过程如表2.3所示。 表2.3 密钥为cipher的维吉尼亚密码加密过程 密文为：cxtsmvfkgftkqanzxvo。 解密使用相同的密钥，但用模26的减法代替模26加法，这里不再赘述。,2.1.2 多表替代密码（续）,2.希尔（Hill）密码 Hill密码算法的基本思想是将n个明文字母通过线性

10、变换，将它们转换为n个密文字母。解密只需做一次逆变换即可。 算法的密钥K = 上的 可逆矩阵，明文M与密文C 均为n维向量，记为 其中， 或写成 解密变换则为： 其中，K 1为K在模26上的逆矩阵，满足：K K 1 = K 1 K=I (mod 26) 这里 I 为单位矩阵。,第2章 古典密码技术,2.1.2 多表替代密码（续）,第2章 古典密码技术,3一次一密密码（One Time Pad） 若替代码的密钥是一个随机且不重复的字符序列，这种密码则称为一 次一密密码，因为它的密钥只使用一次。 该密码体制是美国电话电报公司的Joseph Mauborgne在1917年为电报 通信设计的一种密码，

11、所以又称为Vernam密码。Vernam密码在对明文加密 前首先将明文编码为（0，1）序列，然后再进行加密变换。,2.1.2 多表替代密码（续）,设m=(m1 m2 m3 mi )为明文,k=(k1 k2 k3 ki )为密钥,其中mi,ki (0,1), i1, 则加密变换为： c=(c1 c2 c3 ci ) ,其中ci mi ki , i1,m=(m1 m2 m3 mi ) ,其中mi ci ki , i1,这里为模2加法（或异或运算）,解密变换为：,第2章 古典密码技术,2.1.2 多表替代密码（续）,在应用Vernam密码时，如果对不同的明文使用不同的随机密钥，这时 Vernam密码

12、为一次一密密码。 由于每一密钥序列都是等概率随机产生的，敌手没有任何信息用来对密文进行密码分析。香农（Claude Shannon）从信息论的角度证明了这种密码体制在理论上是不可破译的。但如果重复使用同一个密钥加密不同的明文，则这时的Vernam密码就较为容易破译。,若敌手获得了一个密文c=(c1 c2 c3 ci ) 和对应明文m=(m1 m2 m3 mi ) 时，就很容易得出密钥 k=(k1 k2 k3 ki ) ，其中ki ci mi ，i1。 故若重复使用密钥，该密码体制就很不安全。,第2章 古典密码技术,实际上Vernam密码属于序列密码，加密解密方法都使用模2加，这使软 硬件实现都

13、非常简单。但是，这种密码体制虽然理论上是不可破译的，然而 在实际应用中，真正的一次一密系统却受到很大的限制，其主要原因在于该 密码体制要求： 密钥是真正的随机序列； 密钥长度大于等于明文长度； 每个密钥只用一次（一次一密）。 这样，分发和存储这样的随机密钥序列，并确保密钥的安全都是很因难 的；另外，如何生成真正的随机序列也是一个现实问题。因此，人们转而寻 求实际上不对攻破的密码系统。,2.1.2 多表替代密码（续）,第2章 古典密码技术,4Playfair密码 Playfair密码是一种著名的双字母单表替代密码，实际上Playfair密码 属于一种多字母替代密码，它将明文中的双字母作为一个单元

14、对待，并将这 些单元转换为密文字母组合。 例如，密钥K= playfair is a digram cipher，去除重复字母后，K=playfirsdgmche，可得字母矩阵如图2.1。 图2.1 Playfair密码字母矩阵示例,2.1.2 多表替代密码（续）,第2章 古典密码技术,对每一明文字母对P1、P2的加密方法如下： （1）若P1、P2在同一行，密文C1、C2分别是紧靠P1、P2右端的字母； （2）若P1、P2在同一列，密文C1、C2分别是紧靠P1、P2下方的字母； （3）若P1、P2不在同一行，也不在同一列，则C1、C2是由P1、P2确定的 矩形其它两角的字母，且C1和P1在同一

15、行，C2和P2在同一行； （4）若P1P2，则两个字母间插入一个预先约定的字母，如x，并用前述方法处理；如balloon，则以ba lx lo on 来加密。 （5）若明文字母数为奇数，则在明文尾填充约定字母。 算法还约定字母矩阵中第一列看做最后一列的右边一列，表中第一行看做最后一行的下一行。,2.1.2 多表替代密码（续）,第2章 古典密码技术,密码名称 编码规则 一次一密 杂乱无章 维吉尼亚 分组+加法 希尔 分组+线性变换 Playfair 分组+短语,2.1.2 多表替代密码（总结）,类似单表 添加分组,第2章 古典密码技术,置换密码又称为换位密码； 置换密码与替代密码的区别： 置换密

16、码通过改变明文消息各元素的相对位置，但明文消息元素本身的取值或内容形式不变； 在替代密码中，则可以认为是保持明文的符号顺序，但是将它们用其它符号来替代；,2.2 置换密码 ( Permutation Cipher ),第2章 古典密码技术,2.2.1 周期置换密码 周期置换密码是将明文字符按一定长度n分组，把每组中的字符按1， 2，n的一个置换重排位置次序来得到密文的一种加密方法。 其中的密钥就是置换，在的描述中包含了分组长度的信息。 解密时，对密文字符按长度n分组，并按的逆置换 把每组字符重排位置次序来得到明文。 周期置换密码可描述为：,2.2 置换密码 ( Permutation Ciph

17、er ),设n为固定的正整数，P = C = (Z26)n , K是由 1，2，n 的所有 置换构成。对一个密钥K，定义： 加密变换： E (m1, m2,., mn) = (m(1),., m(n) =( c1, c2,., cn) 解密变换： ;这里1为的逆置换 注意，这里的加密与解密变换仅仅用了置换，无代数运算。,第2章 古典密码技术,2.2.1 周期置换密码（续）,的置换密码对其进行加密，然后再对密文进行解密。 解：密钥长度是6，所以按周期长度6对明文分组，对每组字母用密钥 进行重排得到对应的加密结果。 明文分组为：crypto|graphy，再利用置换密钥进行加密变换，得： E (c

18、rypto) = (ytcopr); E (graphy) = (ahgypr) 即密文消息为ytcoprahgypr。,【例2.7】给定明文为cryptography，试用密钥=,显然由加密置换可求出逆置换， ，根据密文和逆置换即可直接明文。,第2章 古典密码技术,这种密码的加密方法就是将明文按行填写到一个列宽固定（设为m）的 表格或矩阵中；然后按（1，2，m）的一个置换交换列的位置次 序，再按列读出即得密文。 解密时，将密文按列填写到一个行数固定（也为m）的表格或矩阵中， 按置换的逆置换交换列的位置次序，然后按行读出即得到明文。置换 可看成是算法的密钥。 由于置换密码只需打乱原明文字符的排

19、列顺序形成乱码来实现加密变换 ，因此，置换的方法还有很多，例如，图形置换密码就是先按一定的方向把 明文输入到某种预先规定的图形中，再按另一种方向输出密文字符，不足部 分填入随机字符，这里就不一一列举了。,2.2.2 列置换密码,第2章 古典密码技术,2.3 转轮机密码,初始设置,AB BI CE ,AE BQ CT ,第2章 古典密码技术,Phaistos圆盘，直径约160mm的Creran-Minoan粘土圆盘，始于公元前17 世纪。表面有明显字间空格的字母，至今还没有破解。J.Friedrichs：“如 果没有进一步的线索，短的报文段不会提示其含义的。”,2.4 密码实例,第2章 古典密码

20、技术,双密码盘，估计始于18或19世纪。外层圆盘上有类似词汇表的明文，明文 中有字母，元音字母和常用单词。密文是由两位的十进制数组成的。,第2章 古典密码技术,惠斯通(Wheatstone) “密码”，一种钟表形式的设备，首次露面是在1867年 巴黎世纪展览会上。这是一个单表加密密码设备，顺时针旋转的指针每次 指向下一个明文字母 ，圆盘也随着混合的密文字母旋转。,第2章 古典密码技术,美国陆军圆柱形密码设备M-94，共有25个直径为35mm的铝盘，外缘上刻 有字母。它的设计思想可追溯到Jefferson(杰斐逊)和Bazeries(巴泽里埃斯) 于1922年在W.Friedman(威廉.弗里德

21、曼)的建议下投入使用，主要针对低级 的军事通信，1924年以前被广泛使用。,第2章 古典密码技术,二战中美国陆军和海军使用的条形密码设备M-138-T4，根据1914年Parker Hill的提议而设计。25个可选的纸条按预先编排的顺序编号、使用，加密强 度相当于M-94。,第2章 古典密码技术,Kryha密码机大约在1926年由Alexander von Kryha发明。这是一个多表加密 设备，密钥长度为442，周期固定。一个有数量不等的齿的轮子引导密文轮不 规则地运动。尽管它有弱点，但这台乘法密码机在许多国家很抢手。,第2章 古典密码技术,哈格林(Hagelin)密码机C-36，由Akti

22、ebolager Cryptoteknid Stocholm于1936 年制造。通过BEAUFORT(博福特)加密步骤完成自反加密，是哈格林的一个 发明。密钥的不同长度，即17、19、21、23、25个齿，导致产生不规则运动， 密钥周期的长度为3900225。对于纯机械的密码机来说，这已是非常不简单了,第2章 古典密码技术,M-209是哈格林对C-36改进后的产品，根据哈格林的许可，由Smith-Corna负责 为美国陆军生产。它增加了一个有26个齿的密钥轮，从而使密钥周期达到了101 405 950。手柄转动时，字母轮带动拨针和凸片，使鼓状筒上的横杆移位；这些横 杆的作用像齿轮上的齿那样，使

23、轮子转动，将密文字母大引导把手后面的卷纸上。,第2章 古典密码技术,转轮密码机ENNIGMA，由Arthur Scherbius(阿图尔.舍尔比乌斯)于1919年发明。 面板前有灯泡和插接板：4轮ENIGMA在1942年装备德国海军。它用3(最多为8)个 正规轮和1(至多为2)个反射轮(Griechenulzen ,)，这使得英国从1942年2月到12 月都没能解读德国潜艇的信号。,第2章 古典密码技术,ENNIGMA转轮：内部线路有26个电路连接。 上图：1轮，可以看见设置轮。 下图：细轮，由两个缺口。,第2章 古典密码技术,英国的TYPEX打字密码机，是德国ENIGMA的改进型密码机，它增加了两个轮 (操作中不动)，使得破译更加困难。它在英国通信中使用广泛，且在破译密钥后 帮助破解德国信号。面板上显示TYPEX为III型，序列号为NO.376。,第2章 古典密码技术,Uhr盒用来替换德国防军ENIGMA机插接板的机器，用非互反代替。可以选择40 个不同位置转动把手，轻易改变代替。尽管安全性有所增强，但没有广泛应用。,第2章 古典密码技术,在线密码电传机Lorentz SZ42，大约在1943年由Lorenz A.G制造。一种用于Baudot 信号的密码机，英国人称为“tunny”，用于战略级