383第八章 在密码学中的应用II

《383第八章 在密码学中的应用II》由会员分享，可在线阅读，更多相关《383第八章 在密码学中的应用II（51页珍藏版）》请在金锄头文库上搜索。

1、旱晌雅烯说丁涉么灿卵衣摸瘟梭渴性贬达霍庄绸挫阎鸳括挡皑出洼涛索烁383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第八章第八章 在密码学中的应用在密码学中的应用(II)絮燎醛摹腿挖彦艺尉纬晒丛瓷劲离缎桌酉梧扔避擅谗卷鹏侦饼窃恤徊臀蛆383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 古典密码的两大机制：古典密码的两大机制： 代替密码：代替密码：字母表范围内替换；字母表范围内替换； 换位密码：换位密码：在消息内变换字母的位置。在消息内变换字母的位置。2.1代替密码代替密码 1.描述描述 密钥是字母表的任意组合，有一个明密对应表；密钥是字

2、母表的任意组合，有一个明密对应表； 密钥空间巨大：密钥空间巨大：26!； 单表代替密码的两个特例：移位密码和仿射密码。单表代替密码的两个特例：移位密码和仿射密码。 2.举例举例 首先选加密表；为了便于记忆，协商一个密钥：首先选加密表；为了便于记忆，协商一个密钥： DO YOU LIKE THIS BOOK 去掉重复字母，再进行补充，形成加密表：去掉重复字母，再进行补充，形成加密表： abcdefghijklmnopqrstuvwxyz DOYULIKETHSBACFGJMNPQRVWXZ第二节 代替与换位磊柱奢园凭痢灌冻累戮价批炔崔沸掳恶康三羚耳摄施师滦钵屡针尝绞殴抓383-第八章 在密码学中

3、的应用（II）383-第八章 在密码学中的应用（II）第二节 代替与换位2.2 换位密码换位密码 1.机制：机制：单个字符不变而位置改变。单个字符不变而位置改变。 如将文本翻转：明文如将文本翻转：明文 computersystems 密文密文 SMETSYSRETUPMOC 2.特点：特点： (1)密文长度与明文长度相同；密文长度与明文长度相同； (2)唯密文攻击可能得到多种不同的破译结果；唯密文攻击可能得到多种不同的破译结果； 如如 keeppeek；liveevilvile 3.分组换位密码分组换位密码 针对固定大小的分组进行操作。针对固定大小的分组进行操作。 举例：明文举例：明文 can

4、 you understand (1)列换位法列换位法 设密钥设密钥k=4，将明文进行分组排列，将明文进行分组排列压哑机鞘蜂德钻佳钮丰疗涕再底升铬重遗构弦咱益关懈填韵辰壬脓绵孝洗383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）canyouunderstand按列按列读出读出密文：密文： CODTAUEANURNYNSDCANYOUUNDERSTAND按行按行读出读出明文：明文： canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按按4 4个字符一列分组排列个字符一列分组排列1 2 3 41

5、2 3 4第二节 代替与换位母科嘱汗恨享琵趴恤翌层朽浊驯为挑堰哈钙混呸股烹哉虐银尔惦零烈勃冒383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）按列按列 读出读出t y p ecanyouunderstand密文：密文： YNSDNURNCODTAUEACANYOUUNDERSTAND按行按行读出读出明文：明文： canyouunderstand明文：明文：canyouunderstand按按4 4个字符一行分组排列个字符一行分组排列按type(3,4,2,1)填入1 2 3 43 4 2 1 YNSD NURN CODT AUEA(2)密钥为字符串密钥为字符串ty

6、pe1234按密钥长度分组按密钥长度分组第二节 代替与换位蒸烛卧辞铅蝗媚当呕哨归腕派葡骤退锭密肖旋餐姜虽鸡聘祖麦毡订娇棕溜383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）(3)矩阵换位法：置换矩阵作为密钥矩阵换位法：置换矩阵作为密钥明文：明文：canyouunderstandc a n y o u u n d e r s t a n dn c y a u o n u r d s e n t d a密文：密文：NCYAUONURDSENTDA按置换矩阵的阶按置换矩阵的阶4 4分组分组c a n y o u u n d e r s t a n dN C Y A U

7、O N U R D S E N T D A明文：明文：canyouunderstand解密置换矩阵：解密置换矩阵：说明：说明：第二节 代替与换位硷呵友鞠棉畦淋胳聪斟晰坠稻骆宋浊毕橡脉顶酉柬奖鸵佑感蒜裁腰蛔臂晓383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第二节 代替与换位2.3 频率攻击频率攻击1.原理：原理：利用自然语言的频率攻击利用自然语言的频率攻击 字母出现的频率有规律：字母出现的频率有规律： e:11.67 t:9.53 o:7.81 a:7.73 e:11.67 t:9.53 o:7.81 a:7.73 the:4.65 to:3.02 of:2.6

8、1 and:1.85 the:4.65 to:3.02 of:2.61 and:1.85 2.应用：应用：对古典密码进行唯密文攻击。对古典密码进行唯密文攻击。 3.举例：举例：对仿射密码的攻击对仿射密码的攻击 密文：密文：JFFGJFDMGFSJHYQHTAGHQGAFDCCFP 统计字母出现的次数：统计字母出现的次数： F6 G4 H3 J3 猜测：猜测：e(4)F(5) t(19)G(6) 则有：则有：Ea,b(e)=F Ea,b(t)=G 尸铁衣酱紧押时助曲寻合屠狼跋勺昂私洞玛室浮缝异踢翱癌诬桶九攀撅奇383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第二节

9、 代替与换位 Ea,b(4)=(a4+b)%26 Ea,b(19)=(a19+b)%265=(4a+b)%266=(19a+b)%26a=15-1%26=7b=3加密密钥加密密钥a-1%26=15-a-1b=-153%26=7解密密钥解密密钥Ea,b(x)=(7x+3)%26解密函数为：解密函数为：E15,7(x)=(15x+7)%26解密后的明文为：解密后的明文为： meet me after midnight in the alley抑屏扮碾豢止贱论死镁趋摩掐学憾睹辽战姑珊写兴送讶增廷竟耳残危陨钮383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第二节 代替与

10、换位4.举例：举例：对代替密码的攻击对代替密码的攻击 KOS BMKKBS ISS YFSJ NFK BMES KOSIDY IFP KF JSS MK.t th he et th he ee eeeeee ee eeeeet tt tt ttttto oo oo oo on ni ii ii il ll ll lk kb bb bs ss sd dd db ba ay y 分析：由分析：由ESROL得到得到er,s,o,l或或re,s,o,lloser 或或 sorel 那么：由那么：由VIERD得到得到drive或或irevd所以比较合理的明文是：所以比较合理的明文是： loser dri

11、ve5.举例：举例：对换位密码的攻击对换位密码的攻击 ESROL VIERD地畜氨坷舜妹处开登读冒氨狐逛勤九疏哗墅挎那籍坞选掂酉翰掐栖去锗通383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第二节 代替与换位作业：作业：(1)解密由仿射密码加密的密文：解密由仿射密码加密的密文： VCLLCP BKLC LJKX XCHCP(2)解密用简单换位密码加密的密文：解密用简单换位密码加密的密文： EAGGAR DAIREP要寺渭敛叭学洋牢刀泅婉次方模玖叙史贿澄侯光灭鞠碘脯糟愁浸壮端先堰383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）3.1

12、群群 1.二元运算二元运算 定义：定义：设设s为集合，函数为集合，函数f:s ss称为称为s上的二上的二元运算或代数运算。满足：元运算或代数运算。满足： 可计算性：可计算性：s中任何元素都可以进行这种运算；中任何元素都可以进行这种运算； 单值性：运算结果唯一；单值性：运算结果唯一； 封闭性：封闭性：s中任何两个元素运算结果都属于中任何两个元素运算结果都属于s。 2.群的定义群的定义 定义：定义：设设是代数系统，是代数系统， 为为G上的二元运上的二元运算，如果算，如果 运算是可结合的，则称运算是可结合的，则称半群。半群。 若若为半群，并且二元运算为半群，并且二元运算 存在单位元存在单位元e G，

13、则称，则称为幺半群；为幺半群； 若若为半群，并且二元运算为半群，并且二元运算 存在单位元存在单位元e G，G中的任何元素中的任何元素x都有逆元都有逆元x-1 G，称，称为群，简记为为群，简记为G。第三节 置 换叁蕾晴哭珠胜炕碘俄隙俩勿咏唆届鳖翼孤吃赐透途督肉程畸荣敢拐袒蚕桨383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 举例：举例： (1)是群，其中是群，其中Z为整数集合，为整数集合，+是普通是普通的加法，单位元是的加法，单位元是0，整数，整数x的逆元是的逆元是-x。 (2)是群，是群，Z6=0,1,2,3,4,5， 为模为模6加法。显然加法。显然 满足结合律

14、，单位元是满足结合律，单位元是0；由于；由于1 5=0，2 4=0，3 3=0，所以，所以1和和5互为逆元，互为逆元，2和和4互为逆互为逆元，元，3和和0的逆元仍然是的逆元仍然是3和和0。 3.群中元素的阶群中元素的阶 定义：定义：设设是群，是群，a G，n Z，则，则a的的n次次幂为幂为 e n=0 an= an-1 a n0 (a-1)m n0,n=-m 举例：举例：在群在群中，中，30=0，35=15，3-5=-15 在群在群中，中，20=0，23=0，2-3=0第三节 置 换甜吨标融炭贸剿素塔序抹负氢从杨栏宰蔷单山亦杭矗逢耀千颂奢肾至狮象383-第八章 在密码学中的应用（II）383-

15、第八章 在密码学中的应用（II） 阶的定义：阶的定义： (1)设设是群，是群，a G，使得等式，使得等式ak=e成立的成立的最小正整数最小正整数k称为称为a的阶，记做的阶，记做|a|=k，a称为称为k阶元，阶元，若不存在这样的整数若不存在这样的整数k，则，则a称为无限阶元。称为无限阶元。 例如：例如： 在在中，中，2和和4是是3阶元，阶元，3是是2阶元，阶元， 1和和5是是6阶元，阶元，0是是1阶元。阶元。 在在中，中，0是是1阶元，其他都是无限阶元。阶元，其他都是无限阶元。 (2)设设为群，为群，a G，且，且|a|=r。设。设k是整数，是整数，则则ak=e当且仅当当且仅当r|k。 (3)设

16、设为群，则群中任何元素为群，则群中任何元素a与其逆元与其逆元a-1 具有相同的阶。具有相同的阶。第三节 置 换佣婚夷螺叫梆婿吨睦输孤扑怔实步砷优眶颓韵声滩码绣吻芽捆稍曙仰谭钎383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 4.循环群和置换群循环群和置换群 定义定义1：设设为群，如果存在一个元素为群，如果存在一个元素a G，使得使得G=ak|k Z，则称，则称G为循环群，记做为循环群，记做G=，称称a为生成元。若为生成元。若|a|=n，则，则G称为称为n阶循环群。阶循环群。 例如：例如： 是循环群，其中是循环群，其中Z6=0,1,2,3,4,5,， 为模为模6加

17、法，生成元为加法，生成元为1或或5。 是循环群，生成元为是循环群，生成元为1或或-1。 是循环群，是循环群，Zn=0,1,n-1,，生成生成 元为元为1。第三节 置 换曳质暮勋腊布赡篆碟逻驴绢婉个脾锨距酱雅肝卿愿卓约雁翔西朴迎诉谗徘383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 定义定义3：设设s=1,2,n，s上的上的n!个置换构成集合个置换构成集合sn，则称，则称sn与置换的复合运算与置换的复合运算构成的群构成的群为为s上上的的n元对称群，元对称群，的任意子群称为的任意子群称为s上的上的n元置换元置换群。群。第三节 置 换 定义定义2：设设s=1,2,n，

18、s上的任何双射映射函数上的任何双射映射函数 :ss称为称为s上的上的n元置换，记为：元置换，记为：窟整搽荤妄崇阔哑征豺梗伤措笺嗽吝废铱历攻坤瓣杨撮患汰亦妨蓖夜仑膊383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）3.2置换概念置换概念 1.置换置换 一个集合一个集合X的置换的置换f定义为定义为X到自身的一个双射到自身的一个双射函数函数f。对应有。对应有n个元素的集合个元素的集合X，共有，共有n!个置换。个置换。 问题：问题：对于集合对于集合X，给定某个状态，经过多少次，给定某个状态，经过多少次置换返回初始状态？置换返回初始状态？ Sn=1,2,3,n-1,n表示表

19、示n个元素的置换群个元素的置换群 置换置换g为满足为满足g(k)=ik的一个置换：的一个置换：平凡置换平凡置换e：没有移动任何元素的置换。没有移动任何元素的置换。 即对于所有的即对于所有的i，有，有e(i)=i。置换与集合置换与集合内容无关内容无关第三节 置 换迫趋寡座刷鲁榜然嗽榔鸭行佳基滁琼钻溉共砰间溜庚讲抑趋掇竞权清工鱼383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）2. 置换的合成或乘积置换的合成或乘积 设设g和和h是两个置换，先应用是两个置换，先应用h，再应用，再应用g， 记为：记为：gh或或gh 注意：注意： gh hg 置换的合成满足结合律：置换的合

20、成满足结合律： (gh)k=g(hk)3. 逆置换逆置换 对于任意置换对于任意置换g，存在一个逆置换，存在一个逆置换g-1，满足：，满足： gg-1=g-1g=e4. 图表记法图表记法 用来计算两个置换的乘积。如：用来计算两个置换的乘积。如：第三节 置 换赁覆刹蔽拜倡腰涣帆骋窟煽满邪请呕墟勒委凄农右欠垒细片帜奸棒锑框佣383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）5. 循环循环 最简单的置换是不同长度的循环。最简单的置换是不同长度的循环。 一个一个k循环满足：循环满足： f(i1)=i2, f(i2)=i3 , f(ik-1)=ik, f(ik)=i1，对于任

21、意，对于任意j (i1,i2,ik)，有，有f(j)=j。 举例：举例：则：则：可见：可见：gh hg，具有不可交换性。，具有不可交换性。记作：记作：(i1,i2,ik)(1 2)(1 3)第三节 置 换挫猾棋疲破准汐投疟坷谷绞淋企馏贿愤狸纸拨艘圃俊遵滴荡谜邹吗锁丰轻383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）6. 结论结论 (1)如果如果g是一个是一个k循环，那么循环，那么gk=e。注意：注意：一个一个k k循环有循环有k k种表示法。种表示法。比较：比较： (1 2 3)与与(1 3 2)(1 2 3)= (2 3 1)= (3 1 2)(1 3 2)如

22、：如：则：则：即：即：对某个集合应用对某个集合应用g g操作操作k k次，不会对集合产生次，不会对集合产生 任何影响。任何影响。第三节 置 换纯传它憾淳输议踩赊旺酮遁隋极犬誉蒸力芋赴个幢庸砚瞎灰州铡锻聋拾塞383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）(2)置换的阶置换的阶 是置换被多次应用后却不产生任何实际影响所需是置换被多次应用后却不产生任何实际影响所需要的重复次数。要的重复次数。 若置换若置换g是一个是一个k循环，则有循环，则有gk=e，g的阶为的阶为k。(3)不相交的循环不相交的循环 若若g=(i1,ik)和和h=(j1,jl)分别为分别为k循环和循环

23、和l循环，循环，且且i1,i2,ik和和j1,j2,jl是不相交的列表，则有：是不相交的列表，则有： gh=hg 这样的循环这样的循环g和和h称为不相交的循环。称为不相交的循环。第三节 置 换吝消浸砰林皖座颓淤济颐奔帐匀粮磨籍畏皿倦脱衬袁鞍廷拨逊揣认濒倡疾383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 一个置换一个置换g的阶的阶k=不相交循环分解中各循环长度不相交循环分解中各循环长度的最小公倍数。的最小公倍数。如：如：思考：思考：如果一副如果一副5050张的牌洗得好，重复洗张的牌洗得好，重复洗8 8次后所次后所 有的牌将返回初始位置。有的牌将返回初始位置。阶为

24、阶为4 4(4) 置换的不相交循环分解置换的不相交循环分解 任何置换都可以表示为不相交循环的乘积，并任何置换都可以表示为不相交循环的乘积，并且本质上只有这一种表示方法。且本质上只有这一种表示方法。=(1 4 5 7)(2 3)(6)第三节 置 换测鸟剐闸挂衫贿宽羚松肥乏贬三盐腾孵嫉钳缘偿丫乳消创吕吏佰猛姓愈剁383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）3.3 切牌切牌 最简单的切牌：选择一个随机点把一副牌一分为最简单的切牌：选择一个随机点把一副牌一分为二，然后交换两部分。二，然后交换两部分。 n张牌：张牌：0,1,n-1 i+1,n-1,0,1,i 切牌过程

25、为：切牌过程为：fi(x)=(x+n-i-1)%n 如：如：n=6,i=1 0,1,2,3,4,5 2,3,4,5,0,1 置换过程为：置换过程为：f1(x)=(x+4)%6第三节 置 换校的桨负淹江润梁愚臆蹦附俞态铰江莹淖汕腮妆涅膨摆霸史秤淌酗眠俩胀383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）若若n张牌的位置编号为：张牌的位置编号为： 1,2,n-1,n i+1,n-1,n,1,i则切牌过程为：则切牌过程为：fi(x)=(x+n-i-1)%n+1第三节 置 换如：如：n=6,i=2 1,2,3,4,5,6 3,4,5,6,1,2置换过程为：置换过程为：f1

26、(x)=(x+3)%6+1档河框晌摈署庸危霜搓拴绷睛坞怔敏梗侠韧汞员钒域普菜卓桩违恩房答篇383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）2n张牌：张牌： 1,2,n,n+1,2n-1,2n 两半交错：两半交错：n+1,1,n+2,2,2n-1,n-1,2n,n 1,n+1,2,n+2,n-1,2n-1,n,2n命题：对一副有命题：对一副有2n张牌张牌1,2,2n-1,2n的完美快速的完美快速 洗牌过程为：洗牌过程为：f(x)=(2x)%(2n+1)推论：若推论：若e为为2模模2n+1的阶，即的阶，即e是满足是满足2e=1 mod 2n+1的最小正整数。那么对一

27、副有的最小正整数。那么对一副有2n张牌经张牌经 过过e次洗牌后，所有的牌都第一次返回到它们次洗牌后，所有的牌都第一次返回到它们 的起始位置。的起始位置。不好的洗牌不好的洗牌完美洗牌完美洗牌第三节 置 换3.4洗牌洗牌黎瑞律来寅已贼孪贸掏织冤虹垛击钵醛同轰齿遍拢桓祷箩氧穿倒已卿哄扎383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）然后按列读取这些数：然后按列读取这些数： 0,n,2n,mn-n,1,n+1,2n+1,mn-n+1,mn-1对于数对于数x，行：，行：x/n 列：列：x%n3.5 分组交错分组交错 给定正整数给定正整数m和和n，针对，针对mn个元素，一个

28、个元素，一个m n分组交换的置换定义为：分组交换的置换定义为： 按行将按行将mm个数据写成个数据写成m n的矩阵的形式的矩阵的形式第三节 置 换皂皂道搁川脸梭小若冠钞找滞虹的拷已赐嚼但娄悉戍屈特茨媒诣夷疫蔡射383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）然后按列读取这些数：然后按列读取这些数： 0,4,8,1,5,9,2,6,10,3,7,11对应的置换过程为：对应的置换过程为：例：例：12个数据个数据 0,1,2,3,4,5,6,7,8,9,10,11， 进行进行3 4分组交错。分组交错。 对应的循环分解为：对应的循环分解为：数据数据置换位置置换位置阶为阶为

29、5 5按按4 4行行3 3列写出列写出第三节 置 换爽桨卫屎同担锦遥蛹苍骸姓擅赛梦炳括揭惹该震擅娥利念伍廓骡奸呐袜瞎383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）命题：忽略两个不动点命题：忽略两个不动点0和和mn-1，m n分组交错分组交错 对集合对集合1,2,3,mn-2的作用是：的作用是： x (mx)%(mn-1)举例：举例：3 6分组交错分组交错3x%173x%17 分析：快速洗牌，去掉两个不动点分析：快速洗牌，去掉两个不动点 完美的快速洗牌：完美的快速洗牌： x (2x)%(2n+1)第三节 置 换伯群屏牢斥惹舅快州棉袒蔷容革语雀材虎弓蜡篮虽氓今俱联

30、腑烹萍树醋欠383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）作业：作业： (1)计算乘积计算乘积第三节 置 换 用不相交循环的乘积表示上述的结果，并确定阶。用不相交循环的乘积表示上述的结果，并确定阶。(2)S5中任意元素的最大阶是多少？中任意元素的最大阶是多少？S14呢？呢？(3)确定对一副确定对一副20张牌的完美快速洗牌的循环分解。张牌的完美快速洗牌的循环分解。(4)找出找出3 5的分组交错置换的循环分解。的分组交错置换的循环分解。裁君赌祁咕菏球阎济虏酪兵研蛮梦鳖耸尸死烃第音营封漏辱雌延既掇攒界383-第八章 在密码学中的应用（II）383-第八章 在密码学中

31、的应用（II）第四节 现代对称密码 香农提出的香农提出的现代密码现代密码设计准则：设计准则： KerchhoffKerchhoff原则：原则：系统的安全性不依赖于对密文或系统的安全性不依赖于对密文或 加密算法的保密，而依赖于密钥。加密算法的保密，而依赖于密钥。 惟一需要保密的是密钥；惟一需要保密的是密钥； 决定了古典密码学与现代密码学。决定了古典密码学与现代密码学。 一个好的密码将融合混淆和扩散一个好的密码将融合混淆和扩散 混淆：混淆：混淆明文的不同部分；混淆明文的不同部分； 扩散：扩散：对攻击者隐藏一些语言的局部特征；对攻击者隐藏一些语言的局部特征； 现代密码将结合换位和代替：现代密码将结合

32、换位和代替： 代替密码代替密码在混淆上是有效的；在混淆上是有效的； 换位密码换位密码扩散性较好。扩散性较好。簧萎搞尹释搽拾叉艰缕踊袒全谢乏蚕韩人溅描港齿渐爷厩蒋儿隐屯农迂腺383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）4.1 数据加密标准数据加密标准DES(Data Encryption Standard) 1976年被采纳作为联邦标准，并授权在非密级年被采纳作为联邦标准，并授权在非密级的政府通信中使用，应用广泛。的政府通信中使用，应用广泛。 DES是一个分组加密算法，对称密码，是一个分组加密算法，对称密码，64位分位分 组，密钥长度为组，密钥长度为64位位(

33、实际长度为实际长度为56位位)。第四节 现代对称密码现代密码算法的特点：现代密码算法的特点： 只要保证密钥安全，就能保证加密信息的安全。只要保证密钥安全，就能保证加密信息的安全。对称密码算法：对称密码算法：很好地融合了混淆和扩散；很好地融合了混淆和扩散； DES、AES、IEDA、RC6等等非对称密码算法：非对称密码算法：基于数学难题；基于数学难题； RSA、ECC、ElGamal等等空恼瀑扛恒饭乏照罐蚤迢嚼冠舔钠役严闺木情蔼铀乌朽琵逊刷游赋贱佑腕383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） DES的整个算法是公开的，系统的安全性靠的整个算法是公开的，系统的

34、安全性靠密钥保证。算法包括三个步骤：初始置换密钥保证。算法包括三个步骤：初始置换IP、16轮轮迭代的乘积变换、逆初始变换迭代的乘积变换、逆初始变换IP-1。 1.初始置换初始置换IP 初始置换初始置换IP可将可将64位明文位明文M=m1m2m64的位置进的位置进行置换，得到乱序的行置换，得到乱序的64位明文组位明文组M0=m58m50m7。 2. 逆初始置换逆初始置换IP-1 逆初始置换逆初始置换IP-1将将16轮迭代后的轮迭代后的64比特数据的各比特数据的各字节按列写出，将前四列插到后四列中，再对各列进行字节按列写出，将前四列插到后四列中，再对各列进行逆序，然后将元素按行读出即可得到输出的密

35、文组。逆序，然后将元素按行读出即可得到输出的密文组。 IP和和IP-1的作用主要是打乱输入的的作用主要是打乱输入的ASCII码字划分关系，码字划分关系，并将明文校验码变成并将明文校验码变成IP输出的一个字节。输出的一个字节。第四节 现代对称密码言泪挟兵伯乌斌欺膝加跑疹氰评宗游尽却翻移征队夯铝肉讹赋酱荣长倾杖383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码夯梗郝肋辐芹虑凭嫉碳忙喊是荣鳖蟹足稽鄙澈恍驶茹统遍吐宗詹皑攫晤攘383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码戳射簇后词褒例汽势乒程沽歇蛀

36、掣乃咏饭并呈酿拐甥悉呐堵郝馆椿寓冉畜383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码照唱辖愚棘胃贯田鉴菱朝芬灿蛾厂谐甭搔裔沟醚杯恰廊屁题耀祥局惫但品383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）【举例】设【举例】设64位明文位明文M为：为：00000000 11111111 01010101 00010001 10001000 11001100 00110011 10101010则经过则经过IP置换后的置换后的M0为：为：00100110 01001110 00100110 01001110 10110010

37、 11000010 10110010 11000010转换过程如下：转换过程如下：第四节 现代对称密码颊蛤策周硕钢揣咋村涪粳靳岂思牲材蛛肖显决川踪远始绳登釉颖腹汲粥奏383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 3. 乘积变换乘积变换 乘积变换是乘积变换是DES算法的核心部分。将经过算法的核心部分。将经过IP置置换后的数据分成换后的数据分成32位的左右两组，在迭代过程中彼此位的左右两组，在迭代过程中彼此左右交换位置。每次迭代时只对右边的左右交换位置。每次迭代时只对右边的32位进行一系列位进行一系列的加密变换，然后把左边的的加密变换，然后把左边的32位与右边得

38、到的位与右边得到的32位逐位逐位进行异或操作，作为下一轮迭代时左边的段。位进行异或操作，作为下一轮迭代时左边的段。迭代公式为：迭代公式为： Li=Ri-1，Ri=Li-1 f(Ri-1,ki) ：按位异或操作运算符，即按位作模按位异或操作运算符，即按位作模2相加运算。相加运算。运算规则为：运算规则为：1 0=1，0 1=1，0 0=0，1 1=0 f的功能的功能是将是将32比特的数据经过选择扩展运算比特的数据经过选择扩展运算 E、密钥加密运算、选择压缩运算、密钥加密运算、选择压缩运算S和置换运算和置换运算P转转换为换为32比特的输出。比特的输出。 第四节 现代对称密码碉瓤辊褐揪约碘崩菲兽堰们暂

39、幸拱丈郴莽壤茬驼弊勺惨裹罢袄椅酱蕾冲即383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码就葛耕恬决约撒卫腔蓟杜犁馈倘账省癸副看脊寒斧雷沂璃办昆饼菜脸辜挣383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） (1)选择扩展运算选择扩展运算E 选择扩展运算下可将输入的选择扩展运算下可将输入的32比特比特Ri-1扩展成扩展成48位的输出。令位的输出。令s表示表示E原输入数据比特的下标，则原输入数据比特的下标，则E的输出是将原下标的输出是将原下标s为为0或或1(模模4)的各比特重复一次的各比特重复一次得到的，实现数据扩展。得

40、到的，实现数据扩展。第四节 现代对称密码棍搽素峙证阿芳斤岛醉榴遣系戴维胞附倚浓宛蹿雅挨虚促颤姬屡津巴茫蕊383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） (2) 密钥加密运算密钥加密运算 密钥加密运算将密钥加密运算将48比特的子密钥比特的子密钥ki与选择扩展与选择扩展运算运算E输出的输出的48比特数据进行按位异或运算。比特数据进行按位异或运算。【举例】设【举例】设32比特数据比特数据Ri-1为为 00000000 11111111 00000000 11111111，48比特子密钥比特子密钥ki为为 00000000 11111111 01010101 1010

41、1010 11001100 10001000，求，求Ri-1经过选择扩展运算经过选择扩展运算E后与子密钥后与子密钥ki异或后的结果。异或后的结果。第四节 现代对称密码宝畜里姬女惋俺剁览斜播十椅哆埠京住钧棍郊箕帘节井烁伯甘锡肋冰瘦赘383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） 16个子密钥个子密钥ki的产生：的产生： 64比特初始密钥比特初始密钥k经过换位函数经过换位函数PC-1将位置号将位置号为为8,16,24,32,40,48,56和和64的的8位奇偶位去掉并位奇偶位去掉并换位；换位后的数据分为换位；换位后的数据分为2组，经过循环左移位组，经过循环左移位L

42、Si和和换位函数换位函数PC-2变换后得到每次迭代加密用的子密钥变换后得到每次迭代加密用的子密钥ki。第四节 现代对称密码限癣训男紫舀任蟹矗诸傅艺鼓浦忧绒装苦狭纪驮躲漆亏央休时闭匣咸竖茸383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码拥成钞麻滔尺舶籽棕酮屈钻碉酉骑嘘罩新鳃砚饯毡撑嫩欢陇感左父脊胡阁383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II） LSi表示求子密钥表示求子密钥ki时将时将Ci-1和和Di-1进行循环左进行循环左移，其移位位数为：移，其移位位数为： (3)选择压缩运算选择压缩运算 选择压缩运算可将

43、密钥加密运算后的选择压缩运算可将密钥加密运算后的48比特数比特数据从左至右分成据从左至右分成8组，每组为组，每组为6比特，并行迭入比特，并行迭入8个个S盒后压缩成盒后压缩成32比特输出。每个比特输出。每个S盒的输入为盒的输入为6比特，比特，输出为输出为4比特，以完成压缩变换。比特，以完成压缩变换。 对于某个对于某个S盒盒Si，假设其输入为，假设其输入为b1b2b3b4b5b6， 在在Si表中找到表中找到b1b6行，行，b2b3b4b5 列的整数，转换列的整数，转换 为为4位二进制就是输出的位二进制就是输出的4比特数据。比特数据。第四节 现代对称密码司滔聚栅希握差玩焦咐娟剖囚德首僚靴瞄盛亨簧钩蜕

44、移恼铡悟孽位酝秘看383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码悄獭近尘仔铲怕睡板雪适甥咆芭挫封保让舔灿泌岸兄九晴妈图漂舞骆这副383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码韭孕涂廉式趣狼蝶管厦角宙绿鳃坷请里彝署珊痪词搜土刃目羽样蜡奔滔涂383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）【举例】设【举例】设S5的输入为的输入为b1b2b3b4b5b6=110110。 则则(b1b6)2=(10)2=2，(b2b3b4b5)2=(1011)2=11在在S5中找

45、到行为中找到行为2，列为，列为11的数据的数据5转换为转换为4位二位二进制为进制为0101，所以，所以S5的输出为的输出为0101。 (4)置换运算置换运算P S1S8盒的输出合成盒的输出合成32比特数据后，用换位表比特数据后，用换位表p进行置换，得到的进行置换，得到的32比特数据就是比特数据就是f(Ri-1,ki)的输出。的输出。第四节 现代对称密码填勺胚慌紫菠夹产秃紧押诱镑惭新齐脐婉赢喧脯侥响甚畅粕恶蒙炸勤汝栖383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）趾卵纬藏履抒昭洗槐冷协茹唤侦瞥绞陪佬浆吊胞朱逢萌寄缴抉扬设固汉肮383-第八章 在密码学中的应用（II

46、）383-第八章 在密码学中的应用（II） DES的解密算法和加密算法相同，只是在解密的解密算法和加密算法相同，只是在解密 过程中将子密钥的顺序颠倒。过程中将子密钥的顺序颠倒。 DES的出现在密码史上是个创举。以前任何设的出现在密码史上是个创举。以前任何设计者对于密码体制细节都是严加保密的。自公布以计者对于密码体制细节都是严加保密的。自公布以来，它一直活跃在国际保密通信的舞台上，成为商用来，它一直活跃在国际保密通信的舞台上，成为商用保密通信和计算机通信的最常用的加密算法。由于保密通信和计算机通信的最常用的加密算法。由于DES的安全性完全依赖于密钥，而其的安全性完全依赖于密钥，而其64位的密钥太

47、位的密钥太短，因而出现了许多短，因而出现了许多DES的改进算法，如三重的改进算法，如三重DES、分组反馈连接式分组反馈连接式DES以及密码反馈模式以及密码反馈模式DES等。随着等。随着新的攻击手段和改进的加密算法的不断出现，新的攻击手段和改进的加密算法的不断出现，DES也许将完成它的历史使命。也许将完成它的历史使命。 高级加密标准高级加密标准AES评选于评选于2000年年10月结束，月结束，Rijdael算法为算法为AES的唯一算法。的唯一算法。第四节 现代对称密码倍抖澈野毖孙额男行貌吟斥迂抑舆辱浙嘻珊激陌筐二暑逛书橡揩短狙澜好383-第八章 在密码学中的应用（II）383-第八章 在密码学中

48、的应用（II） 4. DES的安全性的安全性 (1)差分分析差分分析 1990年年Biham和和Shamir提出差分密码分析。提出差分密码分析。是一种比穷举攻击有效的选择明文的攻击方法。是一种比穷举攻击有效的选择明文的攻击方法。 差分分析的攻击方法是针对差分分析的攻击方法是针对DES和其他类似的有和其他类似的有固定固定S盒的算法。盒的算法。DES的的S盒恰好最适宜于抗差分分盒恰好最适宜于抗差分分析。最佳差分分析的总结表明对析。最佳差分分析的总结表明对16轮轮DES的攻击需的攻击需选择明文选择明文247，分析的复杂性为，分析的复杂性为237。 (2)线性密码分析线性密码分析 Mitsuru Ma

49、tsui提出了线形密码分析。使用线性提出了线形密码分析。使用线性近似值来逼近分组密码的操作。攻击完整的近似值来逼近分组密码的操作。攻击完整的16轮轮DES，当已知明文的平均数为，当已知明文的平均数为243时，可得到密时，可得到密钥，是最有效的攻击钥，是最有效的攻击DES的方法。的方法。 第四节 现代对称密码御铀痹佑匪抒姆鹏预急榜转歼携皂纱樱盏吹吴熏强夺趋胀敲砖兢株的弯饶383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码4.2 序列密码序列密码 1.随机数生成器随机数生成器 (1)任意由确定过程生成的随机数序列，从实任意由确定过程生成的随机数序列

50、，从实际意义上讲都不是随机的。际意义上讲都不是随机的。 (2)pRNG(pseudo-random number generators):伪随机数发生器，其典型应用是一次一密乱码本。伪随机数发生器，其典型应用是一次一密乱码本。 (3)一个一个pRNG要求：在不知道密钥的情况下，要求：在不知道密钥的情况下，由随机数序列中已知部分推测下一个数是由随机数序列中已知部分推测下一个数是“困难困难”的。的。 (4)伪随机数序列的周期：要求尽可能大伪随机数序列的周期：要求尽可能大 对于序列对于序列s0,s1,s2,若存在若存在p，使得，使得si+p=si 则称它为周期为则称它为周期为p的周期序列。的周期序列

51、。刑邢痪镶痕紧晦折初故腹轨述壕才肢么拟药邵缩疵翁谓蜒拣帽墩耿涯碧润383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码 2.线性同余发生器线性同余发生器 最为广泛使用的伪随机数产生器。最为广泛使用的伪随机数产生器。 (1)产生方式产生方式 sn+1=(asn+b) mod m Zm 其中其中0am,0 bm，初值，初值s0称为种子。称为种子。 (2)分析分析 a,b,m的取值是产生高质量随机数的关键。的取值是产生高质量随机数的关键。 取取a=2,b=7,m=17，则，则 sn+1=(2sn+7) mod 17 取种子取种子s0=1，生成的伪随机序

52、列为：，生成的伪随机序列为：1,9,8,6,2,11,12,14,1,9,8,6,2,11,12,14,1,9,序列的周期为序列的周期为8，而且，而且Z17中只有中只有8个元素出现。个元素出现。实咖斗牺黑尉厄贝尔抡倡染冰埋焊贫憾擞册第谓求琉磕舟龚爪显迁钡硝廷383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）第四节 现代对称密码 取取a=7,b=1,m=17,则则sn+1=(7 sn+1) mod 17 取种子取种子s0=1，生成的伪随机序列为：，生成的伪随机序列为：1,8,6,9,13,7,16,11,10,3,5,2,15,4,12,0,1,8,序列的周期为序列

53、的周期为16。(14未出现未出现) 取种子取种子s0=14，则序列为：，则序列为： 14,14,14,14,(3)线性同余发生器的周期线性同余发生器的周期 定理定理1：只要种子是模只要种子是模p非零的，则线性同余发生非零的，则线性同余发生器器si+1=a si mod p的周期为的周期为a在乘法群在乘法群Z/p 中的阶中的阶l。 而且，而且，l|p-1，且当，且当a为模为模p的本原根时，的本原根时，l=p-1。 定理定理2：线性同余发生器线性同余发生器si+1=a si+b mod p的周的周期为期为a在在Zp 中的阶，只要种子中的阶，只要种子s0不等于坏种子不等于坏种子 sbad=-(a-1)-1 b mod p举例：求举例：求sn+1=7sn+2 mod 13的坏种子的坏种子sbad。毖兵堆堤旭详沛映浓榆拔勾怜正束羊普仰刑杆描涵骸榜凤殊蔼滓伙芒钳恤383-第八章 在密码学中的应用（II）383-第八章 在密码学中的应用（II）