密码学sec-chap02.ppt
第二讲第二讲 常规加密常规加密第二讲的主要内容第二讲的主要内容经典密码经典密码n替代技术替代技术n置换技术置换技术分组密码的原理分组密码的原理nFeistelFeistel密码密码DESDESnDESDES加密加密nDESDES分析分析分组密码的设计准则分组密码的设计准则 1/2/20232常规加密常规加密加密与信息隐藏加密与信息隐藏信息隐藏：不知道信息存在于传输介质信息隐藏：不知道信息存在于传输介质的何处。的何处。(Information Hiding)(Information Hiding)加密：知道信息在何处，却不能理解信加密：知道信息在何处，却不能理解信息的意义。息的意义。1/2/20233常规加密常规加密信息隐藏的框架信息隐藏的框架 1/2/20234常规加密常规加密信息隐藏的媒体信息隐藏的媒体纯文本纯文本格式文本格式文本多媒体介质，如图像，音频，视频多媒体介质，如图像，音频，视频 1/2/20235常规加密常规加密信息隐藏的范围信息隐藏的范围 1/2/20236常规加密常规加密信息隐藏的例子信息隐藏的例子第二次世界大战从日本战俘营寄给美国联第二次世界大战从日本战俘营寄给美国联邦调查局的明信片：邦调查局的明信片：Dscf0053.jpg 1/2/20237常规加密常规加密信息隐藏的例子信息隐藏的例子小时候玩的游戏：小时候玩的游戏：老板催我早一点决定毕业去向的时候，已是初老板催我早一点决定毕业去向的时候，已是初夏树，我还是感到一阵阵凉意。看着老板已经夏树，我还是感到一阵阵凉意。看着老板已经斑白的头发，心里不禁酸楚。可这毕竟掩盖不斑白的头发，心里不禁酸楚。可这毕竟掩盖不了心底的无奈和郁闷，不过我知道我终究改变了心底的无奈和郁闷，不过我知道我终究改变不了什么，我清楚老板很器重我，私下里常对不了什么，我清楚老板很器重我，私下里常对他朋友说我是他最得意的弟子，是最有可能继他朋友说我是他最得意的弟子，是最有可能继承他衣钵的人。可是老板娘更喜欢文国，因为承他衣钵的人。可是老板娘更喜欢文国，因为他既将成为她的爱婿。我和文国都是老板今年他既将成为她的爱婿。我和文国都是老板今年要毕业的研究生，老板只能从两人中留下一个，要毕业的研究生，老板只能从两人中留下一个，老板说会为我努力。今天看到他从院长办公室老板说会为我努力。今天看到他从院长办公室出来的神色，一切都清楚地写在脸上，我已经出来的神色，一切都清楚地写在脸上，我已经没有什么机会了。没有什么机会了。1/2/20238常规加密常规加密信息隐藏的例子信息隐藏的例子藏头诗：藏头诗：神神箭一飞入蓝天，箭一飞入蓝天，舟舟中载人国力显。中载人国力显。五五岳三山河九曲，岳三山河九曲，号号子响彻长江边。子响彻长江边。扬扬眉吐气歌且舞，眉吐气歌且舞，我我握巨笔作诗篇。握巨笔作诗篇。国国运昌盛民安乐，运昌盛民安乐，威威龙狂舞万万年。龙狂舞万万年。1/2/20239常规加密常规加密替代和置换替代和置换替代技术替代技术 明文字母由其他字母或数字或符号所代替明文字母由其他字母或数字或符号所代替置换技术置换技术 对明文字母的某种置换取得一种类型完全对明文字母的某种置换取得一种类型完全不同的映射不同的映射肖国镇老师说：肖国镇老师说：“炒豆子炒豆子”。不同之处在。不同之处在于于?1/2/202310常规加密常规加密恺撒密码恺撒密码把字母表中的每个字母用该字母恺撒密码把字母表中的每个字母用该字母后面第三个字母进行代替后面第三个字母进行代替n明文：明文：n密文：密文：一个例子：一个例子：n明文：明文：we are studentswe are studentsn密文：密文：zhzh duh duh vwxghqwvvwxghqwv恺撒密码的数学表示恺撒密码的数学表示 c=E(m,k)=(m+k)mod q m=D(c,k)=(c-k)mod q 1/2/202311常规加密常规加密恺撒密码对对恺撒密码进行强行攻击密码分析恺撒密码进行强行攻击密码分析n加密和解密算法已知加密和解密算法已知n密钥空间大小为密钥空间大小为25，为什么，为什么n明文容易识别攻击明文容易识别攻击增大恺撒密码的密钥空间增大恺撒密码的密钥空间n随机替换，密钥空间随机替换，密钥空间26!，为什么，为什么利用语言的规律性利用语言的规律性 1/2/202312常规加密常规加密密码分析人类语言有冗余度人类语言有冗余度字母使用频率不相同字母使用频率不相同在英文中，在英文中，e的使用率最高的使用率最高其次，其次，T,R,N,I,O,A,S其他字母使用频率较低其他字母使用频率较低密文反应了明文字母出现的规律性密文反应了明文字母出现的规律性 1/2/202313常规加密常规加密英文字母使用频率 1/2/202314常规加密常规加密英文字母中常见的组合 1/2/202315常规加密常规加密恺撒密码的分析方法书书P21.首先单字频率确定首先单字频率确定e，t的范围。的范围。然后使用双字频率。然后使用双字频率。如有可能还可以使用如有可能还可以使用3字频率，字频率，the。1/2/202316常规加密常规加密Playfair密码构造关键字矩阵如下：构造关键字矩阵如下：MONRACHYDBEFGKI/JLPQTSUVWZX 1/2/202317常规加密常规加密Playfair密码加密规则加密规则n处理明文处理明文,填充字母填充字母wBalloon ba lx lo onn同行字母替代，同行字母替代，n同列字母替代同列字母替代n非同行同列字母替代非同行同列字母替代分析分析n2626种字母组合种字母组合n频率分析变得困难频率分析变得困难 1/2/202318常规加密常规加密Hill密码m个连续明文字母被个连续明文字母被m个个密文字母代替密文字母代替由由m个线性方程决定替代方法个线性方程决定替代方法m=3时的系统描述：时的系统描述：n编码（编码（a=0,b=1,z=25)CKP 1/2/202319常规加密常规加密Hill密码一个例子：一个例子：n明文为明文为pay more moneyn加密密钥为加密密钥为np=15,a=0,y=24nK(15,0,24)mod 26=(11,13,18)1/2/202320常规加密常规加密Hill密码破解破解Hill密码？密码？已知明文攻击的情况下解线性方程组。已知明文攻击的情况下解线性方程组。1/2/202321常规加密常规加密Vigenere密码Vigenere表格表格 1/2/202322常规加密常规加密Vigenere密码Vigenere加密加密n密钥密钥 deceptivedeceptivedecepitven明文明文 wearedicoveredsaveyourselfn密文密文 zicvtwqngrzgvtwavzhcqyglmgj 1/2/202323常规加密常规加密Vigenere密码密码分析密码分析n猜测关键字长度猜测关键字长度w两个相同明文字母序列出现在一定距离里，该距离是关键字长度的整数倍，那么它们将产生相同的密文序列n分割分割vigenere密码为单字母密码密码为单字母密码w密钥以关键字长度为周期改进改进n消除关键字的周期性消除关键字的周期性wAT&T的工程师设计一个使用非常长的密钥工作的系统w只要有足够的密文，或已知明文仍能够破译wP28的注解一次一密方案一次一密方案n使用与消息一样长的随机密钥使用与消息一样长的随机密钥n实际使用困难：发送者和接收者必须拥有该随机密钥实际使用困难：发送者和接收者必须拥有该随机密钥 1/2/202324常规加密常规加密置换技术栅栏技术areaer 明文：明文：wait me at the gate 加密：加密：wimateae atethgt 密密文：文：wimateaeatethgt 1/2/202325常规加密常规加密置换技术栅栏技术更为复杂一些的更为复杂一些的n密钥：密钥：43125674312567n明文：明文：attackpattackp ostponeostpone duntiltduntilt woamxyzwoamxyzn密文：密文：TTNAAPTMTSUOAODWCOIXKNLYPETZ 1/2/202326常规加密常规加密分组密码的原理流流密码和分组密码密码和分组密码当前对称加密算法几乎都基于当前对称加密算法几乎都基于Feistel分组密码分组密码乘积密码乘积密码n连续执行两个或多个密码基本运算单元连续执行两个或多个密码基本运算单元nFeistel提出用替代和置换交替的方式构造密码提出用替代和置换交替的方式构造密码nShannon提出用扰乱和扩散交替的方式构造密码提出用扰乱和扩散交替的方式构造密码扩散和扰乱扩散和扰乱n目的：挫败基于统计分析的密码分析方法目的：挫败基于统计分析的密码分析方法n扩散：明文的统计结构扩散到密文中扩散：明文的统计结构扩散到密文中n扰乱：密文的统计特性与密钥的取值之间的关系尽扰乱：密文的统计特性与密钥的取值之间的关系尽可能复杂可能复杂 1/2/202327常规加密常规加密Feistel密码Feistel加密加密 1/2/202328常规加密常规加密Feistel密码变换可以用下列函数表示变换可以用下列函数表示: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轮）轮）1/2/202329常规加密常规加密Feistel密码的设计准则分组大小分组大小n增加分组长度会提高安全性增加分组长度会提高安全性,但降低了密码运算速但降低了密码运算速度度密钥大小密钥大小n增加密钥长度增加密钥长度,可以提高安全性可以提高安全性(使得穷搜索困难使得穷搜索困难),同同样样,降低了密码速度降低了密码速度循环次数循环次数n增加轮数可以提高安全性增加轮数可以提高安全性,但降低速度但降低速度子密钥产生算法子密钥产生算法n子密钥生成越复杂子密钥生成越复杂,就越安全就越安全,但降低速度但降低速度Round函数函数n复杂的轮函数能够使的密码分析困难复杂的轮函数能够使的密码分析困难,但降低速度但降低速度 1/2/202330常规加密常规加密Feistel密码的设计准则所有问题就是平衡问题所有问题就是平衡问题n设计设计”安全安全”的密码算法并不难的密码算法并不难,只要使用足只要使用足够多的轮数就可以够多的轮数就可以,但降低速度但降低速度 快速的软件加解密快速的软件加解密便于分析便于分析 1/2/202331常规加密常规加密Feistel密码解密Feistel解密解密 1/2/202332常规加密常规加密（数据加密标准）简介简介n1977年被美国标准局作为数据加密标准年被美国标准局作为数据加密标准n64bit分组加密，密钥长度为分组加密，密钥长度为56bitn对称密钥体制对称密钥体制的由来的由来对的评论对的评论n密钥长度比较短密钥长度比较短n内部结构的设计标准保密内部结构的设计标准保密 1/2/202333常规加密常规加密一般描述一般描述 1/2/202334常规加密常规加密每个每个 循环的循环的 详细详细 过程过程 1/2/202335常规加密常规加密F（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比特串 1/2/202336常规加密常规加密S 盒的作用盒的作用n6bit4bitn输入的第一和最后两比特决定行输入的第一和最后两比特决定行n输入的中间四比特决定列输入的中间四比特决定列n被选中的数字转换成被选中的数字转换成4比特输出比特输出 1/2/202337常规加密常规加密密钥的产生密钥的产生n选择置换矩阵选择置换矩阵1n循环左移一位或两位循环左移一位或两位n选择置换矩阵选择置换矩阵2解密解密n逆次使用子密钥逆次使用子密钥KPC-1C0 D0LS1LS1C1 D1LS2LS2LS16LS16C16 D16PC-2PC-2K1K16 1/2/202338常规加密常规加密雪崩效应雪崩效应 明文或密钥的一点点变动应引起密文发明文或密钥的一点点变动应引起密文发生大的变化生大的变化的雪崩效应的雪崩效应 1/2/202339常规加密常规加密对的分析密钥的大小密钥的大小n的密钥空间为的密钥空间为2!56算法的性质算法的性质n不公开不公开S盒的设计准则盒的设计准则 1/2/202340常规加密常规加密分组密码设计原理的设计准则（了解的设计准则（了解）nS盒盒提供输入提供输入bits混合作用混合作用(confusion)nP盒盒提供扩散作用提供扩散作用(diffusion)1/2/202341常规加密常规加密分组密码设计原理循环次数循环次数n以密码分析的工作量大小为依据以密码分析的工作量大小为依据函数函数F的设计的设计n扰乱作用扰乱作用F 应该是非线性的应该是非线性的nSAC和和BICwSAC:对于任何i,j,当然任何一个输入比特i变化时，一个S盒子的任何输出比特j变化的概率为1/2wBIC:对于任意i,j,k,当任意输入比特变化时，输出j和k应当独立变化n古典密码没有这些性质古典密码没有这些性质密钥调度密钥调度n推测各子密钥和主密钥的难度尽可能大推测各子密钥和主密钥的难度尽可能大 1/2/202342常规加密常规加密密码设计的评价“好的好的”密码设计具有密码设计具有:雪崩特性雪崩特性,完备性完备性,不可不可预料性预料性(avalanche,completeness,unpredictability)差的密码设计缺乏随机性差的密码设计缺乏随机性,具有太大的可预料性具有太大的可预料性许多密码都被攻破许多密码都被攻破(mercial products like Wordperfect,pkzip,all current mobile phone ciphers)即使密码学专家也会犯这样的错误即使密码学专家也会犯这样的错误最好的办法是测试最好的办法是测试,通过实际检验证明它的安通过实际检验证明它的安全性全性 1/2/202343常规加密常规加密内容回顾替代和置换的概念替代和置换的概念*恺撒密码恺撒密码playfair密码密码Hill密码密码Vegenere密码及密码分析密码及密码分析*栅栏技术栅栏技术Feistel密码密码*DES*分组密码的设计原理分组密码的设计原理*1/2/202344常规加密常规加密 1/2/202345常规加密常规加密
