第二讲----古典密码学.ppt

1、第二讲第二讲 古典密码学古典密码学 2022-1-202第二讲的主要内容第二讲的主要内容经典密码经典密码n替代技术替代技术n置换技术置换技术分组密码的原理分组密码的原理nFeistelFeistel密码密码DESDESnDESDES加密加密nDESDES分析分析分组密码的设计准则分组密码的设计准则 2022-1-203加密与信息隐藏加密与信息隐藏信息隐藏：不知道信息存在于传输介质信息隐藏：不知道信息存在于传输介质的何处。的何处。(Information Hiding)(Information Hiding)加密：知道信息在何处，却不能理解信加密：知道信息在何处，却不能理解信息的意义。息的意义。

2、 2022-1-204信息隐藏的框架信息隐藏的框架MarkingalgorithmMarkedMediaStego-MediaMarkSecret/Public keyoralgorithmSecret/Public keyMarkingMark and/or original MediaMarked-MediaMarkconfidence measure 2022-1-205信息隐藏的媒体信息隐藏的媒体纯文本纯文本格式文本格式文本多媒体介质，如图像，音频，视频多媒体介质，如图像，音频，视频 2022-1-206信息隐藏的范围信息隐藏的范围InformationHidingChannelsCo

3、vertSteganographyAnonymityCopyrightMarkingLinguisticSteganographyTechnicalSteganographyRobust Copyright MarkingMarkingFragileWatermarkingFingerprintingWatermarkingImperceptibleVisibleWatermarking 2022-1-207信息隐藏的例子信息隐藏的例子第二次世界大战从日本战俘营寄给美国联第二次世界大战从日本战俘营寄给美国联邦调查局的明信片：邦调查局的明信片：Dscf0053.jpg 2022-1-208信息隐

4、藏的例子信息隐藏的例子小时候玩的游戏：小时候玩的游戏：老板催我早一点决定毕业去向的时候，已是初老板催我早一点决定毕业去向的时候，已是初夏树，我还是感到一阵阵凉意。看着老板已经夏树，我还是感到一阵阵凉意。看着老板已经斑白的头发，心里不禁酸楚。可这毕竟掩盖不斑白的头发，心里不禁酸楚。可这毕竟掩盖不了心底的无奈和郁闷，不过我知道我终究改变了心底的无奈和郁闷，不过我知道我终究改变不了什么，我清楚老板很器重我，私下里常对不了什么，我清楚老板很器重我，私下里常对他朋友说我是他最得意的弟子，是最有可能继他朋友说我是他最得意的弟子，是最有可能继承他衣钵的人。可是老板娘更喜欢文国，因为承他衣钵的人。可是老板娘更

5、喜欢文国，因为他既将成为她的爱婿。我和文国都是老板今年他既将成为她的爱婿。我和文国都是老板今年要毕业的研究生，老板只能从两人中留下一个，要毕业的研究生，老板只能从两人中留下一个，老板说会为我努力。今天看到他从院长办公室老板说会为我努力。今天看到他从院长办公室出来的神色，一切都清楚地写在脸上，我已经出来的神色，一切都清楚地写在脸上，我已经没有什么机会了。没有什么机会了。 2022-1-209信息隐藏的例子信息隐藏的例子藏头诗：藏头诗：神神箭一飞入蓝天，箭一飞入蓝天，舟舟中载人国力显。中载人国力显。五五岳三山河九曲，岳三山河九曲，号号子响彻长江边。子响彻长江边。扬扬眉吐气歌且舞，眉吐气歌且舞，我我

6、握巨笔作诗篇。握巨笔作诗篇。国国运昌盛民安乐，运昌盛民安乐，威威龙狂舞万万年。龙狂舞万万年。 2022-1-2010替代和置换替代和置换(易位易位)替代技术替代技术 明文字母由其他字母或数字或符号所代替，明文字母由其他字母或数字或符号所代替，进行逆运算恢复明文。进行逆运算恢复明文。置换技术置换技术 对明文字母的某种置换取得一种类型完全对明文字母的某种置换取得一种类型完全不同的映射，即明文中字母重新排列，本不同的映射，即明文中字母重新排列，本身未变，位置发生改变。身未变，位置发生改变。 2022-1-20111.单表替换单表替换n移位替换移位替换n乘法密码乘法密码n放射变换放射变换n密钥短语密码

7、密钥短语密码2.多表代替多表代替nVigenere密码密码nVername密码密码nHill密码密码 2022-1-2012单表替换对明文中胡所有字符都使用一个固定胡对明文中胡所有字符都使用一个固定胡映射，即：映射，即：,.,110naaaA,.,110nbbbBiibafBAf)(,: 2022-1-2013移位密码之恺撒密码恺撒密码把字母表中的每个字母用该字母恺撒密码把字母表中的每个字母用该字母后面第三个字母进行代替后面第三个字母进行代替n明文：明文：n密文：密文：一个例子：一个例子：n明文：明文：we are studentswe are studentsn密文：密文：zh duh vw

8、xghqwvzh duh vwxghqwv恺撒密码的数学表示恺撒密码的数学表示 c = E(m,k) = (m + k) mod q m = D(c,k) = (c - k) mod q 2022-1-2014恺撒密码对恺撒密码进行强行攻击密码分析对恺撒密码进行强行攻击密码分析n加密和解密算法已知加密和解密算法已知n密钥空间大小为密钥空间大小为25，为什么，为什么n明文容易识别攻击明文容易识别攻击增大恺撒密码的密钥空间增大恺撒密码的密钥空间n随机替换，密钥空间随机替换，密钥空间26!，为什么，为什么利用语言的规律性利用语言的规律性 2022-1-2015密码分析人类语言有冗余度人类语言有冗余度

9、字母使用频率不相同字母使用频率不相同在英文中，在英文中，e的使用率最高的使用率最高其次，其次，T,R,N,I,O,A,S其他字母使用频率较低其他字母使用频率较低密文反应了明文字母出现的规律性密文反应了明文字母出现的规律性 2022-1-2016英文字母使用频率 2022-1-2017英文字母中常见的组合 2022-1-2018恺撒密码的分析方法首先单字频率确定首先单字频率确定e，t的范围。的范围。然后使用双字频率。然后使用双字频率。如有可能还可以使用如有可能还可以使用3字频率，字频率，the。 2022-1-2019乘法密码加密变换为：加密变换为：解密变换为：解密变换为：其中其中，例如：英文字

10、母表例如：英文字母表n=26,选择密钥选择密钥k=9,则则k-1=3,明文字母到秘文字母替换为下明文字母到秘文字母替换为下表：表：1),(mod,)(nknikjaaEjik1),(mod,)(nknikjaaEjiknkjiaaDijkmod.,)(1)(mod1.11nkkkk的逆，为 2022-1-2020ABCDE FGHIJKLMAJSBK TCLUDM VENOPQR STUVW XYZNW FOX GPYHQZIR0 1 2 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 20 21 22 23 24 25 2022-1-2021密钥短语密码

11、选择一个英文短语作为密钥，去掉其中选择一个英文短语作为密钥，去掉其中重复胡字母，得到一个无重复的字母串，重复胡字母，得到一个无重复的字母串，依次写在明文字母表下，而后在将字母依次写在明文字母表下，而后在将字母表中未出现胡字母依次写于此短语之后，表中未出现胡字母依次写于此短语之后，构造一个字母替换表。构造一个字母替换表。例如：例如： 2022-1-2022例例 短语：短语：happy new year hapynewr明文：明文：persion abcde fghijklmhapyn ew rbcdfgnopqrstuvw xyzijklm oqstuvxz 2022-1-2023单表密码安全性

12、分析密钥量小密钥量小词频特性词频特性没将明文字母出现胡概率掩蔽起来。没将明文字母出现胡概率掩蔽起来。 2022-1-2024二 多表代替单表是明文字母与密文字母一一对应，单表是明文字母与密文字母一一对应，明文中字母统计特性在密文中没有得到明文中字母统计特性在密文中没有得到改变，所以容易破译。改变，所以容易破译。多表定义：以一系列代替表依次对明文多表定义：以一系列代替表依次对明文消息的字母进行替换的加密算法。消息的字母进行替换的加密算法。 2022-1-2025Vigenere密码 2022-1-2026Vigenere密码Vigenere加密加密n密钥密钥 deceptivedeceptive

13、decepitven明文明文 wearedicoveredsaveyourselfn密文密文 zicvtwqngrzgvtwavzhcqyglmgj 2022-1-2027Vigenere密码密码分析密码分析n猜测关键字长度猜测关键字长度w两个相同明文字母序列出现在一定距离里，该距离是关键字长度的整数倍，那么它们将产生相同的密文序列n分割分割vigenere密码为单字母密码密码为单字母密码w密钥以关键字长度为周期改进改进n消除关键字的周期性消除关键字的周期性wAT&T的工程师设计一个使用非常长的密钥工作的系统w只要有足够的密文，或已知明文仍能够破译一次一密方案一次一密方案n使用与消息一样长的随

14、机密钥使用与消息一样长的随机密钥n实际使用困难：发送者和接收者必须拥有该随机密钥实际使用困难：发送者和接收者必须拥有该随机密钥 2022-1-2028Playfair密码：英国陆军在密码：英国陆军在第一次世界第一次世界大战大战，美国陆军美国陆军在在第二次世界大战第二次世界大战期间期间大量使用的一种二字母组代替密码。密大量使用的一种二字母组代替密码。密钥由钥由26个个英文字母英文字母组成五阶方阵。组成五阶方阵。 矩阵的构造矩阵的构造:从左到右、从上到下填入关从左到右、从上到下填入关键词的字母（去除重复字母），然后再键词的字母（去除重复字母），然后再以以字母表字母表顺序将余下的字母填入矩阵剩顺序将

15、余下的字母填入矩阵剩余空间。余空间。 Playfair密码 2022-1-2029构造关键字矩阵如下：构造关键字矩阵如下：harpsichord HARSPI/JCOBDEFGLMNQUTVWXZYK 2022-1-2030Playfair密码加密规则加密规则n加密规则加密规则 m1,m2同行：同行：c1,c2在它们右边；在它们右边； m1,m2同列：同列：c1,c2在它们下边；在它们下边； m1,m2不同行列：不同行列：c1,c2是是m1,m2 组成的长方形组成的长方形的另两个顶点；的另两个顶点； m1=m2：在其间插入一无效字母；：在其间插入一无效字母； 明文由奇数个字母组成，则在明文后加

16、一无效字母明文由奇数个字母组成，则在明文后加一无效字母 分析分析n2626种字母组合种字母组合n频率分析变得困难频率分析变得困难 2022-1-2031例：例： M=bookstore M=bo xo ks to re C=id rg lp qd hg 2022-1-2032Hill密码m个连续明文字母被个连续明文字母被m个密文字母代替个密文字母代替由由m个线性方程决定替代方法个线性方程决定替代方法m=3时的系统描述：时的系统描述：n编码（编码（a=0,b=1,z=25) CKP26mod)(3132121111pkpkpkC26mod)(3232221212pkpkpkC26mod)(333

17、2321313pkpkpkC321333231232221131211321pppkkkkkkkkkCCC 2022-1-2033Hill密码一个例子：一个例子：n明文为明文为pay more moneyn加密密钥为加密密钥为np=15,a=0,y=24nK(15,0,24) mod 26 = (11,13,18)192221182151717K 2022-1-2034Hill密码破解破解Hill密码？密码？已知明文攻击的情况下解线性方程组。已知明文攻击的情况下解线性方程组。111213123212223123313233(,)( ,)kkkC C CkkkP P Pkkk1CK PKC P

18、2022-1-2035置换技术栅栏技术areaer 明文：明文： wait me at the gate 加密：加密： wimateae atethgt 密文：密文： wimateaeatethgt 2022-1-2036置换技术栅栏技术更为复杂一些的更为复杂一些的n密钥：密钥：43125674312567n明文：明文： attackpattackp ostponeostpone duntiltduntilt woamxyzwoamxyzn密文：密文：APTMTTNAAODWTSUOCOIXKNLYPETZ 2022-1-2037置换技术-倒置法报文倒置：将报文内容按顺序依次倒置，并报文倒置：

19、将报文内容按顺序依次倒置，并截成固定长度的字母组，形成密文。截成固定长度的字母组，形成密文。分组倒置：将明文截成固定长度的字母串，分组倒置：将明文截成固定长度的字母串，将每组字母倒置，形成密文。将每组字母倒置，形成密文。例如：例如：原文原文there was a small attendance at the meeting报文报文gnit eeme htta ecna dnet tall amsa sawe reht分组分组 ereth sasaw allam dnett aecna mehtt nitee g 2022-1-2038置换技术-方格易位法按双方约定的方格和填写顺序，将原文填入

20、方按双方约定的方格和填写顺序，将原文填入方格，再按约定的抄写次序写出规定长度的密码。格，再按约定的抄写次序写出规定长度的密码。例如：约定例如：约定5*n方格中，横向从上到下填写原方格中，横向从上到下填写原文，从左到右写出长度为文，从左到右写出长度为4的密码的密码明文明文she attended a concert密文密文stdc heae encr adot ten特点：简单易行，特点：简单易行， 但经不起穷举试验但经不起穷举试验sheattendedaconcert 2022-1-2039分组密码的原理流密码和分组密码流密码和分组密码当前对称加密算法几乎都基于当前对称加密算法几乎都基于Fei

21、stel分组密码分组密码乘积密码乘积密码n连续执行两个或多个密码基本运算单元连续执行两个或多个密码基本运算单元nFeistel提出用替代和置换交替的方式构造密码提出用替代和置换交替的方式构造密码nShannon提出用扰乱和扩散交替的方式构造密码提出用扰乱和扩散交替的方式构造密码扩散和扰乱扩散和扰乱n目的：挫败基于统计分析的密码分析方法目的：挫败基于统计分析的密码分析方法n扩散：明文的统计结构扩散到密文中扩散：明文的统计结构扩散到密文中n扰乱：密文的统计特性与密钥的取值之间的关系尽扰乱：密文的统计特性与密钥的取值之间的关系尽可能复杂可能复杂 2022-1-2040Feistel密码Feistel

22、加密加密 2022-1-2041Feistel密码变换可以用下列函数表示变换可以用下列函数表示: L(i) = R(i-1) L(i) = R(i-1) R(i) = L(i-1) XOR g(K(i), R(i-1)R(i) = L(i-1) XOR g(K(i), R(i-1) 求逆很容易求逆很容易 实际中，一些这样的连续变换形成完整实际中，一些这样的连续变换形成完整密码变换（典型：密码变换（典型：16轮）轮） 2022-1-2042Feistel密码的设计准则分组大小分组大小n增加分组长度会提高安全性增加分组长度会提高安全性, 但降低了密码运算速但降低了密码运算速度度密钥大小密钥大小n增

23、加密钥长度增加密钥长度,可以提高安全性可以提高安全性(使得穷搜索困难使得穷搜索困难),同样同样,降低了密码速度降低了密码速度循环次数循环次数n增加轮数可以提高安全性增加轮数可以提高安全性,但降低速度但降低速度子密钥产生算法子密钥产生算法n子密钥生成越复杂子密钥生成越复杂,就越安全就越安全,但降低速度但降低速度Round函数函数n复杂的轮函数能够使的密码分析困难复杂的轮函数能够使的密码分析困难,但降低速度但降低速度 2022-1-2043Feistel密码的设计准则所有问题就是平衡问题所有问题就是平衡问题n设计设计”安全安全”的密码算法并不难的密码算法并不难,只要使用只要使用足够多的轮数就可以足

24、够多的轮数就可以,但降低速度但降低速度 快速的软件加解密快速的软件加解密便于分析便于分析 2022-1-2044Feistel密码解密Feistel解密解密 2022-1-2045（数据加密标准）简介简介n1977年被美国标准局作为数据加密标准年被美国标准局作为数据加密标准n64bit分组加密，密钥长度为分组加密，密钥长度为56bitn对称密钥体制对称密钥体制的由来的由来对的评论对的评论n密钥长度比较短密钥长度比较短n内部结构的设计标准保密内部结构的设计标准保密 2022-1-2046一般描述一般描述 2022-1-2047每个每个 循环的循环的 详细详细 过程过程 2022-1-2048F（

25、R，K）A=R(32 bits)J=K(48 bits)EE(A)为48 bits+B1 B2 B3 B4 B5 B6 B7 B8 S1S2S3S4S5S6S7S8C1 C2 C3 C4 C5 C6 C7 C8P32 bits F(A,J)B写成8个6比特串 2022-1-2049S 盒的作用盒的作用n6bit4bitn输入的第一和最后两比特决定行输入的第一和最后两比特决定行n输入的中间四比特决定列输入的中间四比特决定列n被选中的数字转换成被选中的数字转换成4比特输出比特输出 2022-1-2050密钥的产生密钥的产生n选择置换矩阵选择置换矩阵1n循环左移一位或两位循环左移一位或两位n选择置换

26、矩阵选择置换矩阵2解密解密n逆次使用子密钥逆次使用子密钥KPC-1C0 D0LS1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 2022-1-2051雪崩效应雪崩效应 明文或密钥的一点点变动应引起密文发明文或密钥的一点点变动应引起密文发生大的变化生大的变化的雪崩效应的雪崩效应 2022-1-2052对的分析密钥的大小密钥的大小n的密钥空间为的密钥空间为2!56算法的性质算法的性质n不公开不公开S盒的设计准则盒的设计准则 2022-1-2053分组密码设计原理的设计准则（了解的设计准则（了解）nS盒盒提供输入提供输入bits混合作用混合作用 (confus

27、ion)nP盒盒提供扩散作用提供扩散作用(diffusion ) 2022-1-2054分组密码设计原理循环次数循环次数n以密码分析的工作量大小为依据以密码分析的工作量大小为依据函数函数F的设计的设计n扰乱作用扰乱作用F 应该是非线性的应该是非线性的nSAC和和BICwSAC: 对于任何i,j,当然任何一个输入比特i变化时，一个S盒子的任何输出比特j变化的概率为1/2wBIC: 对于任意i,j,k,当任意输入比特变化时，输出j和k应当独立变化n古典密码没有这些性质古典密码没有这些性质密钥调度密钥调度n推测各子密钥和主密钥的难度尽可能大推测各子密钥和主密钥的难度尽可能大 2022-1-2055密

28、码设计的评价“好的好的”密码设计具有密码设计具有: 雪崩特性雪崩特性,完备性完备性,不可不可预料性预料性(avalanche, completeness, unpredictability )差的密码设计缺乏随机性差的密码设计缺乏随机性,具有太大的可预料性具有太大的可预料性许多密码都被攻破许多密码都被攻破 (incl. commercial products like Wordperfect, pkzip, all current mobile phone ciphers) 即使密码学专家也会犯这样的错误即使密码学专家也会犯这样的错误最好的办法是测试最好的办法是测试, 通过实际检验证明它的安通过实际检验证明它的安全性全性 2022-1-2056内容回顾替代和置换的概念替代和置换的概念*恺撒密码恺撒密码playfair密码密码Hill密码密码Vegenere密码及密码分析密码及密码分析*栅栏技术栅栏技术Feistel密码密码*DES*分组密码的设计原理分组密码的设计原理* 2022-1-2057