密码第二章.

《密码第二章.》由会员分享，可在线阅读，更多相关《密码第二章.（63页珍藏版）》请在金锄头文库上搜索。

1、应用密码学应用密码学 密码技术 密码学概述1 分组密码3 公钥密码4 散列函数与消息鉴别5 古典密码2古典密码 古典密码 置换密码1 转轮机密码3 替代密码2 古典密码 2.1 置换密码 v 本质：明文和密文所含的元素是相同的，仅仅是位置不同而已， 加密过程可看作是将明文中字母顺序进行重排列。 (1) 实例1：斯巴达-scytale密码(天书) 古典密码 2.1 置换密码 v 密文：sesb_ettr_nroi_dotd_mohg_opee_r 明文：send more troops to the bridge 古典密码 2.1 置换密码 (2) 实例2：栅栏密码 v 密文： TEOGSDYU

2、TAENNHLNETAMSHVAED T E O G S D Y U T A E N N H L N E T A M S H V A E D 明文：THE LONGEST DAY MUST HAVE AN END 古典密码 2.1 置换密码 (2) 实例2：栅栏密码变异 v 密文： IVOUOOKWALEUTUNNTTOYBYDTOH 密钥：3行 I V O U O O K W A L E U T U N N T T O Y B Y D T O H 明文： I LOVE YOU， BUT YOU DONT KNOW THAT 古典密码 古典密码 古典密码 的置换密码对其进行加密，然后再对密文进

3、行解密。 解：密钥长度是6，所以按周期长度6对明文分组，对每组字母用密钥 进行 重排得到对应的加密结果。 明文分组为：crypto|graphy，再利用置换密钥进行加密变换，得： E (crypto) = (ytcopr); E (graphy) = (ahgypr) 即密文消息为ytcoprahgypr。 【例2.7】给定明文为cryptography，试用密钥= 显然由加密置换可求出逆置换， ，根据密文和逆置 换即可直接明文。 古典密码 2.1.2 列置换密码 古典密码 hsetteneruayvedswseeeebutrehlfatfirhirelidlodeeligvbebnuhtlt

4、hmoriarofr 解： 密钥为长度为7的置换，可知该矩阵列数 为7，共70个字母，则知该矩阵行数为10； 将密文每10个字母为一列排成矩阵，如右 h a e a i v h s y e t d b m e v b f l e o t e u i o b r t d t r d n i e s r h e u a n w e i e h r e s h r l t o r e l e i l f u e f l g t r 古典密码 按照上述置换交换矩阵的列，结果如下 i h a v e h a d m y b e s t l o v e b e f o r e b u t i d I d

5、n t t r e a s u r e h e r w h e n i l o s t h e r i f e l l r e g r e t f u l 按行读出，即得明文 I have had my best love before, but I didnt treasure her. When I lost her, I fell regretful. 古典密码 2.2 替代密码 v 本质：字母的位置不变，但原字母已被其他字母替换，以达到隐 藏密文的目的的密码。 v 最早替换密码的描述 关于替换加密的最早描述出现在爱经中，此文建议女人学会 64种技艺。其中第45种就是密文术，在密文术中，

6、介绍一种加密 方法，即先随机将字母两两配对，然后将原始信息中的每一个字 母用它的配对字母来代替。 n 原字母： Q W E R T Y U I O P A S D n 替换字母： F G H J K L Z X C V B N M 明文：Walls have tears 密文：Gbyyn ebph hbjn. 古典密码 2.2 替代密码 v 公元16世纪晚期，英国的菲利普斯利用频度分析法成功破解苏格 兰女王玛丽的密码信，信中策划暗杀英国女王伊丽莎白，这次解 密将玛丽送上了断头台。 福尔摩斯剧集中跳舞的人 古典密码 v 一般单表替代密码 【例2.1】设置换的对应关系如下： a b c d e f

7、 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 微秒试一个密钥，遍历全部密钥需要1013

8、 年。 密钥不便记忆。 古典密码 移位密码-实例 恺撒 恺撒是古罗马共和国末期的统帅和政治家，虽然他一生从未登上过皇位， 但是直到今天，他的名字依旧是君主的代名词。 2.1.1 单表替代密码（续） 恺撒密码 最早的关于替换密码用于战争的文献记录是恺撒的高卢战记中，也 就是后来出现的恺撒密码。 恺撒详细描写了他怎样把消息传送给西塞罗，那个时候西塞罗的军队正 被高卢人围困，而且已经到了投降的边缘。 古典密码 v 移位密码-原理 明文空间M、密文空间C都是和密钥空间K满足 即把26个英文字母与整数0，1，2，25一一对应，如表2.1所示。 2.1.1 单表替代密码（续） 表2.1 字母数字映射表 加

9、密变换: E=E:Z26Z26, Ek (m) = m + k (mod26)| mM, kK 解密变换: D=D:Z26Z26, Dk (c) = ck (mod26)| cC, kK 显然，移位密码是前面一般单表替代密码的一个特例 当移位密码的 密钥k=3时，就是恺撒密码 根据其加密函数特 点，移位密码也称为加法密码 古典密码 仿射密码-原理 仿射密码的明文空间和密文空间与移位密码相同，但密钥空间为 K=(k1，k2)| k1，k2Z26，gcd(k1，26)=1 对任意mM，cC，k = (k1，k2)K， 加密变换为: c = Ek (m) = k1 m +k2 (mod 26) 解密

10、变换为： m = Dk (c) = k11 (ck2) (mod 26) 其中， 明显，k1=1时即为移位密码 另外，k2=1则称为乘法 密码 2.1.1 单表替代密码（续） 古典密码 古典密码 【例2.3】设明文消息为china，密钥 试用仿射密码对其进行 加密，然后再进行解密。 解：利用扩展的欧几里德算法，可计算出 加密变换为： 解密变换为： 其中， 明文消息对应的数字依次为2，7，8，13，0，用仿射密码对明文进行加密 如下： 2.1.1 单表替代密码（续） 古典密码 而解密过程如下： 即恢复明文消息为china。 仿射密码要求(k1, 26)=1 (同余方程唯一解条件) ，否则就会有多

11、个明文字 母对应一个密文字母的情况。由于与26互素的整数有12个，故仿射密码密钥 空间大小为 |K|=1226=312 2.1.1 单表替代密码（续） 古典密码 密钥短语密码 选用一个英文短语或单词串作为密钥，去掉其中重复的字母得到一个无 重复字母的字符串，然后再将字母表中的其它字母依次写于此字母串后， 就可构造出一个字母替代表。如密钥为key时，替代表如表2.2所示。 表2.2 密钥为key的单表替代密码 当选择上面的密钥进行加密时，若明文为“china”，则密文为“yfgmk”。 显然，不同的密钥可以得到不同的替换表，对于明文为英文单词或短语 的情况时，密钥短语密码最多可能有26!=410

12、26个不同的替换表。 2.1.1 单表替代密码（续） 古典密码 2.1.1 单表替代密码（总结） 方便记忆 密码名称 编码规则 一般单表替代 杂乱无章 移位密码 加法 仿射密码 线性变换 多项式密码 多项式函数 密钥短语密码 短语 古典密码 2.1.1 单表替代密码危机 频度分析法-由来 神学家们校对可兰经中默罕默德启示录，他们对建立一个启示录 的年鉴非常感兴趣，于是就计算每一个启示录中各个单词出现的频率 。由于某些特定的单词出现的较晚，那么这些新单词出现较多的启示 录年代就处于较后的时期。 宗教学者并没有停留在单词的水平上，他们也分析单独的字母，这导 致了密码破译术上一次伟大的突破。 9世纪

13、的科学家阿尔-金迪在关于破译加密信息的手稿中最早描述 了利用字母频率差异可用来破译密码的技术。 古典密码 2.1.1 单表替代密码危机 频度分析法-结果 古典密码 2.1.2 多表替代密码 不同：使用从明文字母到密文字母的多个映射来隐藏单字母出现 的频率分布，其中每个映射是简单替代密码中的一对一映射。 操作：将明文字母划分为长度相同的消息单元，称为明文分组，对明 文成组地进行替代。 优点：同一个字母有不同的密文，改变了单表替代密码中密文的唯一 性，使密码分析更加困难。 古典密码 2.1.2 多表替代密码 1.维吉尼亚密码(维热纳尔密码) 吉奥万巴蒂斯塔贝拉索，在1553年所著的书吉奥万巴蒂斯塔

14、贝拉 索先生的算术中出现 布莱斯德维吉尼亚于1586年亨利三世时期发明了更为简单却又更有效 的自动密钥密码 之后，19世纪时贝拉索的方法被误认为是由维吉尼亚首先发明的。维吉 尼亚密码以其简单易用而著称，同时初学者通常难以破解，因而又被称 为“不可破译的密码”。 大卫卡恩在破译者中对此表示遗憾，他写道“历史忽略了这一重要 贡献，将其归功于维吉尼亚，虽然他对此并不知道”。 古典密码 2.1.2 多表替代密码 1.维吉尼亚密码(维热纳尔密码) 维 热 纳 尔 方 阵 举例： (1) 明文：abc 密钥：cba 则密文：ccc (2) 密文：abc 密钥：cba 则明文：yac 古典密码 1.维吉尼亚

15、密码 该密码体制有一个参数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.4】设密钥k =cipher，明文消息appliedcryptosystem， 试用维吉尼 亚密码对其进行加密，然后再