密码学与网络安全-第三章传统密码学(1).ppt

《密码学与网络安全-第三章传统密码学(1).ppt》由会员分享，可在线阅读，更多相关《密码学与网络安全-第三章传统密码学(1).ppt（68页珍藏版）》请在三一办公上搜索。

1、第三章 传统对称密钥密码,密码学(Cryptology):是研究信息系统安全保密的科学.密码编码学(Cryptography):研究对信息进行编码,实现对信息的隐蔽.密码分析学(Cryptanalytics):研究加密消息的破译或消息的伪造.,1 基本概念,明文（Plaintext）：原信息的初始形式 P 密文（CypherText）：编码后的加密信息 C 加密算法（Encryption Algorithm)：C=E(P)解密算法(Decryption Algorithm)：P=D(C)密码系统满足：P=D(E(P),密钥（Secret Key):需要使用密钥的加密算法，记为：C=E(K,P)

2、,加密与解密的密钥相同，即：P=D(K,E(K,P)加密与解密的密钥不同，则：P=D(KD,E(KE,P),加密和解密示意图,古希腊密码,明文 secure message transmission is of extreme importance in information based society的密文为：,密码分析（破译）是在不知道密钥的情况下，恢复出明文的科学。密码分析的任务是试图破译单条消息试图识别加密的消息格式，以便借助直接的解密算法破译后续的全部消息试图找到加密算法中的普遍缺陷（无须截取任何消息）成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得

3、到上述结果。如果密钥通过非密码分析方式丢失，叫做密码泄露。,密码分析,唯密文攻击（Cipher Text-Only Attack）。破译者只知加密算法、待破译的密文。破译者只能得到用同一加密算法加密的消息的密文。,已知明文攻击（Known-Plaintext Attack）破译者已知：加密算法和经密钥加密形成的一个或多个明文密文对，即可以知道一定数量的密文和对应的明文。,选择明文攻击（Chosen-Plaintext Attack）。破译者除了知道加密算法外，还可以选定明文消息，并可以知道对应的加密得到的密文，即知道选择的明文和对应的密文。例如，公钥密码体制中，攻击者可以利用公钥加密他任意选定

4、的明文，这种攻击就是选择明文攻击。,自适应选择明文攻击（Adaptive-Chosen-Plaintext Attack）。这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。在选择明文攻击中，密码分析者可以选择一大块被加密的明文，而在自适应选择明文攻击中，可选取较小的明文块，然后再基于第一块的结果选择另一明文块，依此类推。,选择密文攻击（Chosen-Cipher Text Attack）破译者除了知道加密算法外，还包括他自己选定的密文和对应的、已解密的原文，即知道选择的密文和对应的明文。,选择密钥攻击（Chosen-Key Attack）这

5、种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。,选择文本攻击（Chosen-Text Attack）选择明文攻击与选择密文攻击的结合。破译者已知：加密算法、由破译者选择的明文消息和它对应的密文，以及由破译者选择的猜测性密文和它对应的已破译的明文。,蛮力攻击（Brute-force Method）,穷举攻击（Exhausieve-key-search Mathod）,统计攻击（Statistical Attack）,模式攻击（Pattern Attack）,攻击方法,软磨硬泡攻击（Rubber-Hose Cryptanalysis）这种攻击是对密码分析

6、者威胁、勒索，或者折磨某人，直到他给出密钥为止。行贿有时称为购买密钥攻击（purchase-key attack）。这些是非常有效的攻击，并且经常是破译算法的最好途径。,理论安全与实际安全,1949年，Shannon 提出：,1.当破译者有无限制的时间和无限制的计算能力 时一个密码系统的安全性；,2.当破译者在有限的时间和有限的计算能力时，一个密码系统的安全性.,1883年Kerck hoffs 第一次提出了编码的原则：假设加密算法是公开的，预防攻击主要依赖密钥。如果密钥足够安全，加密算法则无必要隐藏。密钥域要足够大，才能使密钥足够安全。,加密方案的安全性,无条件安全：无论提供的密文有多少，如

7、果由一个加密方案产生的密文中包含的信息不足以唯一地决定对应的明文除了一次一密的方案外，没有无条件安全的算法密码安全性体现在：破译成本超过加密信息的价值破译时间超过该信息有用的生命周期,攻击的复杂性分析,数据复杂性（data complexity）完成攻击所需要处理的数据处理复杂性（processing complexity）完成攻击所需要的时间存储需求（storage requirement）进行攻击所需要的数据量,密钥搜索所需平均时间,代换密码（Substitution Cipher），又称替代密码，或替换密码，是用代换法进行加密所产生的密码。,2 代换密码（Substitution Cip

8、her),一、单码代换（Monoalphabetic subistitution),密码明文中的字符与密文中的字符总是一一对应。可以看成是 Z26 到Z26的一对一的映射。总共有26！种不同的映射。,破译以下密文：,C=wuhdwb lpsrvvleoh,P=TREATY IMPOSSIBLE,C=E(P)=P+3,加密算法：,字母表（密码本）ABCDEFGHIJKLMNOPQRSTUVWXYZ defghijklmnopqrstuvwxyzabc,1、凯撒(Caeser)密码,P=D(C)=C-3,解密算法：,这是循环移位密码 加密:字母向后移动3位；解密:字母向前移动3位。,Key=3,设

9、k3；对于明文 PCOMPUTE SYSTEMS 则 E（C）=（3+3）mod 26=6=F E（O）=（15+3）mod 26=18=R E（M）=（13+3）mod 26=16=P E（S）=（19+3）mod 26=22=V 密文 C=E（P）=FRPSXRWHUVBVWHPV,加密明文：,P=HELLO,C=wtaad,C=(P+k)mod 26,加密算法：,2、加法密码（additive cipher),解密算法：,循环移位密码 加密:字母向后移动k位；解密:字母向前移动k位。,P=(C-k)mod 26,字母表（k=15）ABCDEFGHIJKLMNOPQRSTUVWXYZ pq

10、rstuvwxyzabcdefghijklmno,H=07 E=04L=11O=14,07+15=22 mod 2604+15=19 11+15=0014+15=03,22=w 19=t00=a03=d,Key=k,密码域大小=26,加密明文(k=7)：,P=HELLO,C=xczzu,C=(Pk)mod 26,加密算法：,3、乘法密码（multiplicative cipher),解密算法：,P=(Ck-1)mod 26,H=07 E=04L=11O=14,77=23 mod 26 4 7=2 mod26 117=25 mod26147=20 mod26,23=x 2=c25=z20=u,k

11、Z*26=1,3,5,7,9,11,15,17,19,21,23,25,Key=k,密码域大小=12,解密：,C=xczzu,H=07 E=04L=11O=14,2315=7 mod 26 215=4 mod26 2515=11 mod26 2015=14 mod26,23=x 2=c25=z20=u,k=7，7-1=15 mod 26,P=HELLO,作业：key=7 时，作出相应的乘法密码的密码本。,k=3:E(P)=P*3 mod 26，字母表（密码本）：ABCDEFGHIJKLMNOPQRSTUVWXYZ adgjmpsvybehknqtwzcfilorux 字母对应顺序被打乱。,加密

12、明文(k1,k2)=(7,2),P=HELLO,C=zebbw,C=(Pk1+k2)mod 26,加密算法：,4、仿射密码（affine cipher),解密算法：,P=(C-k2)k1-1)mod 26,H=07 E=04L=11O=14,77+2=25 mod 26 4 7+2=4 mod26 117+2=1 mod26147+2=22 mod26,25=z 4=e 1=b22=w,k1Z*26=1,3,5,7,9,11,15,17,19,21,23,25,Key=(k1,k2),密码域大小12*26=312,解密：,C=zebbw,H=07 E=04L=11O=14,(25-2)15=7

13、 mod 26(4-2)15=4 mod26(1-2)15=11 mod26(22-1)15=14 mod26,k=7，7-1=15 mod 26,P=HELLO,作业：key=(7,2)时，作出相应的仿射密码的密码本。,25=z 4=e 1=b22=w,单表密码，利用一张字母映射表（密码本）建立明文与密文之间的一一映射。,5、单表密码,在单表代换密码中，字母表（密码本）中的字母顺序可以被任意打乱。26个字母的排列方法总共有26！，大约是41026，在抵抗蛮力攻击能力方面有所提高。,字母表（密码本）ABCDEFGHIJKLMNOPQRSTUVWXYZ gsphqrtumzvdwnxabceiy

14、jklof,PCOMPUTE SYSTEMS,Cpxwayiq eoeiqwe,常用的方法是在字母表中首先排列出密钥中出现的字母，然后在密钥后面填上剩余的字母。如密钥是HOW，那么新的字母表就是：HOWABCDEFGIJKLMNPQRSTUVXYZ这个密钥很短，多数明文字母离开其密文等价字母，仅有一个或几个位置。若用长的密钥字，则距离变大，因而便难于判断是何文字密钥。,密钥 spectacular ABCDEFGHIJKLMNOPQRSTUVWXYZ spectaulrbdfghijkmnoqvwxyz,密钥 key 构造字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ keyab

15、cdfghijlmnopqrstuvwxz,单字母密码（简单替换技术）简单，便于记忆缺点：结构过于简单，密码分析员只使用很少的信息就可预言加密的整个结构致命弱点：不能抵抗频率统计攻击。,6、代换密码小结：,加法密码（密钥域26）乘法密码（密钥域12）仿射密码（密钥域12*26=312）单表密码（密钥域 26！）,英语字母频率表：,例：使用频率分析破译如下密文：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHM

16、Q,高频单字母：E T A O N R I S H中频单字母：D L F C M U G P Y W B V低频单字母：K X J Q Z高频双字母：th he in er an re ed on es en at to nt ha nd ou ea ng as or ti is et it ar高频三字母：the ing and her ent ion,例子 设有密文如下,GJXXN GGOTZ NUCOT WMOHY JTKTA MTXOB YNFGO GINUG JFNZV QHYNG NEAJF HYOTW GOTHY NAFZN FTUIN ZBNEG NLNFU TXNXUFNEJ

17、C INHYA ZGAEU TUCQG OGOTH JOHOA TCZXK HYNUV OCOHO UHCNU GHHAF NUZHY NCUTW JUWNA EHYNA FOWOT UCHNP HOGLN FQZNG OFUVC NVJHT AHNGG NTHOU CGJXY OGHYN ABNTO TWGNT HNTXN AEBUF KNFYO HHGIU TJUCE AFHYN GACJH OATAE IOCOH UFQXO BYNFG,密文中字母按频数从大到小排列得：,N H O G T U F A Y C J X 36 26 25 23 22 20 17 16 14 13 12 9

18、E Z W B I Q V K L M P 7 7 6 5 5 5 4 3 2 2 1,频率分析：1.由于高频字母中的最底频率与中频字母的最高频率之差高达 0.0528-0.0378=0.015有理由认为N,H,O,G,T,U,F,A,Y就是E，T,A,O,N,I,R,S,H.并且N就是E的密文。,2.有高频字母N,H,O,G,T,U,F,A,Y出现的双字母频数：,3.考虑到元音a,i,o很少相联,猜测O,U,A就是 a,i,o.,4.考虑到相联的概率及以上猜测,进一步猜测.,二、多码代换（Polyalphabetic subistitution),在多码代换中，明文中的一个字符被代换成密文中

19、的多个字符，明文与密文中的字符总是一对多的对应关系。可以看成是 Z26 到 Z26 的一对多的映射。,由于在多码代换中，阴藏了字母的频率特征，可以防范频率统计攻击。,例如：用两张字母替换表E1和E2，分别替换明文信息中的奇数和偶数位置的字符，从而打乱密文中的字母分布频率特性，以避免遭受频率统计攻击，这种编码方法称为“双表密码”。类似地，可以构造出更复杂的“多表密码”。,例1：TREATY IMPOSSIBLE,第一替换表加密,第二替换表加密,第三替换表加密,第四替换表加密,选一个字母作密钥：m=12,1、自动密钥密码（Autokey Cipher),明文流：a t t a c k I s t

20、o d a y密钥流：m a t t a c k i s t o d a,加密 Ci=Pi+Ki mod 26解密 Pi=Ci-Ki mod 26,密 文：m t m t c m s a l h r d y,密钥域 26，易受蛮力攻击。,流密码,一战中英军使用的密码。密钥是一个5X5的字母方阵，把26个字母填入其中（i,j 填在同一格中）。,2、PlayFair 密码,将明文2 个字母组成一对。若两字母相同，嵌入一个伪字母。若最后时奇数，嵌入一个伪字母。,同行右移；同列下移；否则对角；解密反向。,密钥域 25！，不宜进行蛮力攻击。隐藏了单字母的频率。攻击可针对双字母组合的频率。,加密：同行右移

21、；同列下移；对角顺转。,明文 hello,he:EC,lx:QZ,lo:BX,密文：ECQZBX,EC：he,QZ：lx,BX：lo,解密：同行左移；同列上移；对角反转。,明文 helxlo,L映射为Q,B,Blaise de Vigenere,十六世纪法国数学家。密钥 k=(k1k2k3km),m26,循环使用。加密方法：对位相加（流密钥）Ci=Pi+Ki mod 26解密方法：Pi=Ci-Ki mod 26,3、Vigenere 密码,密钥:K=PASCAL（m=6）,明文:She is listening,i 映射为k,x,t,密钥:K=PASCAL,明文:She is listenin

22、g,加密时以明文字母选择列，以密钥字母选择行，交点是生成的密文字母。解密时以密钥字母选择行，从中找到密文字母，其所在列即为明文字母。,K=YOURP=HOWAREYOUK=YOURYOURYC=FCQRPSSFS,Vigenere字母表,Leste S Hill,分组加密，矩阵乘法,4、Hill 密码（矩阵密码）,密钥 K=(kij)mm，K mod26 可逆明文分成长度为 m 的分组 写成矩阵 P r x m,加密方法：矩阵乘法 C=P*K mod 26解密方法：P=C*K-1 mod 26,m=4明文：code is ready 排成3x4 矩阵,给定4x4密钥矩阵：K=,明文：code

23、is ready,密钥：K=,明文写成矩阵 P=,密文:*=,*=,密文：OHKNIHGKLISS,e 映射为N,K,K-1=,*=,解密：P=C*K-1 mod 26,*K-1=,密文：OHKNIHGKLISS,每发送一次信息，改变一次密钥。密钥完全随机生成，密钥长度固定。,5、一次一密密码（One-time-pad OTP）,加密方法：Ci=Pi*Ki mod 26解密方法：Pi=Ci-*Ki mod 26,明文：P=how are you,密钥：K=NCBTZQARX,加密下一条信息时,更换密码,使用非重复的随机字母序列加密，会使至今能使用的任何密码分析工具失效。“完美”的替换密码一次性

24、密钥（One Time PadOTP）相同的PAD，发方与收方绝对同步；打印、分发、保存与使用问题?长随机数序列（对OTP的近似实现）：ri+1=ri*c+b mod w 其中w c和b为常数,为计算机能表示的最大整数最初，AT&T 使用 Vernam密码机实现一次一密的加密，故又称 Vernam 密码。,导致密码机出 现,换位密码是采用移动字母位置的方法进行加密的。它把明文中的字母重新排列，字母本身不变，但位置变了。,3 换位密码（Transporsition Cipher),如：把明文中的字母的顺序倒过来写，然后以固定长度的字母组发送或记录。明文：computer systems密文：sm

25、 etsy sretupmoc,换位并没有改变字母，可能的攻击方法：单字母频率攻击 蛮力攻击：考虑所有可能的排列 模式攻击：,1、无密钥换位,栅栏密码（rail fence cipher)明文：WHAT YOU CAN LEARN FROM THIS BOOK分组排列为两排：,W A Y U A L A N R M H S O K,H T O C N E R F O T I B O,得到密文 WAYUALANRMHSOK HTOCNERFOTIBOX,加密：竖写横读,解密：横写竖读,将明文字符分割成为五个一行的分组，排进表格中。明文：WHAT YOU CAN LEARN FROM THIS B

26、OOK分组排列为：,表格换位,密文则以下面的形式读出：WOLFHOHUERIKACAOSXTARMBXYNNTOX这里的密钥是分组数5。,解密：竖写横读,加密：横写竖读,明文：meet me at the park分组排列为：,加密：MMTAEEHREAEKTTPX,换位对应一个置换：,2、有密钥换位,密钥 K 就是一个指定的置换。,明文：Enemy attacks tonight!,例如：把明文分成5个字母一段。每段都按照密钥指定的置换方式进行换位。,密钥 K=,K-1=,密文：EEMYNTAACTTKONSHITZG,换位盒,明文：Enemy attacks tonight!,把长度为20

27、的明文横排在45的矩阵里,每一列都按照密钥指定的置换方式进行换位。,密钥 K=,K-1=,横读得密文：EEMYNTAACT TKONSHI TZG,K,明文：Enemy attacks tonight!,密钥 K=,K-1=,竖读得密文：ETTHEAKIMA OTYCNZNTSG,K,解密：竖写入表格中；逆向换列；横读即可,横读得密文：EEMYNTAACT TKONSHITZG,解密：横写入表格中；逆向换列；横读即可,矩阵表示换位：,K=,K-1=,=,=,3、双换位与组合换位,将换位方法重复两次经过两次换位盒,明文：Enemy attacks tonight!,中间文本：ETTHEAKIMA

28、OTYCNZNTSG（按列读出）,密文：TIYTEAOZHMCSEANGTKTN（按列读出）,K=,组合换位：不同密钥，多次组合,换位盒K1,K2=,K3=,K1=,换位盒K2,换位盒K3,4、换位密码的分析,密文：ETTHEAKIMAOTYCNZNTSG（20个字）,1、频率攻击 特征：保留单字频率，但不保留双字母、三字母频率 攻击：判断是换位密码，然后单字母频率攻击,2、蛮力攻击 攻击1：遍历所有可能的20字母排列，20！,攻击2：遍历所有可能的密钥 k，列数未知，可能有 1!+2!+20!,攻击3：猜测列数，20=1*2*2*5，因子有 1,2,4,5,10,20 1!+2!+4!+5!

29、+10!+20!最可能是 4和5，找出长度4,5的全部可能的K 4!=24,5!=120,4、换位密码的分析,密文：ETTHEAKIMAOTYCNZNTSG,3、模式攻击 攻击：寻找字母位置的排布模式，进而猜测列数 n,明文：Enemy attacks tonight,密文顺序：3,8,13,18,1,6,11,16,4,9,14,19 5,10,15,20 2,7,12,17,前后相差为5，提供n=5的踪迹,组合换位可减少模式攻击的威胁！,1、转轮密码（rotor cipher）,3 密码机（Cipher Machin),2、Enigma 密码机,Sherbius 发明，第二次世界大战中德军

30、使用。,二战中已被破解（盟军获得了机器的复制品，加上计算机）“埃尼格玛”之父谢尔比乌斯却未能看到“埃尼格玛”被广泛使用并对第二次世界大战所产生的重大影响，他于1929年5月因骑马时发生意外伤重而死,按鍵(keyboard),燈泡(lamp),滾輪(rotor),接線板(stecker,plug board),反射器(Reflector),Enigma 密码机的构造,Enigma 密码机的构造,基于转轮密码的原理 26键的键盘，用于输入明文和密文装有26个灯泡的灯板，加密时显示密文字符，解密时显示明文字符26个插头的接线板，13条连线，其连接每天更换3个转轮，每天从5个转轮中选出。转轮分成快、中

31、、慢三种。转轮有26格，快轮每打一字转一格，快轮转一圈使中轮转一格，中轮转一圈使慢轮转一格。有一反射器，固定但不事先接线,密码本规定 转轮选择转轮安装顺序线路连接板一天的三字母代码，对应转轮的起始位置,Plug-board最多可接13條電線 若接06條電線，將產生105,578,918,576 種可能 3個滾輪之位置將产生3!=6種組合，加上滾輪之初始字母位置 263，共為105,456種可能，故有 105,578,918,576 X 105,456=11,133,930,437,350,656(約1016)種可能的設定,加上以下變化 反射器種類 滾輪上Ringsettings設定Enigma

32、可能設定數可達1023,Enigma 的安全分析,习题三（p84）,13，15，21，22，23，25，26，28，29，32，34，36，37,大作业一：古典密码攻防分组对抗,（1）A组负责产生密码 设计出密码加密程序，产生密码，给出适当提示（2）B组们负责破译密码。可向A组索要提示。（3）由A组根据所给提示的多少进行评分,MajpjMVcyzj21HLfrvy96dv02lPPfYgxUS7IYmZkyEmZ0kGeYZS3bpLCkYH1lt4EK7CxmUX3ijoYSOer7ZuaVWYgz4EpZrUirVpMzzvNtf1XZw5oswSXOtFaejnOcmfE1lZgnN1R

33、SXg8wLCG8CVQ3XPJMvodPFWcpiYJgZazNSEPNIaklYSu7qSd1UpaxmZDlpN9zW7kljfsLCLi26Yv109ffbnDH8LbUN1G6ACURQ39eG12KHL9tXsZ1jzgoCK8g1kuNOh5eFvcmVT5ZYVQt9zk3rp3qLnf02FovEXxVRxjCcFRNppiJljNiOuk6fONnyX7fyGg7sXZ49BmCN5oy9VesHpKzdjTKwjrkCEQCFDehVmGax3lrOEbw63VscA3YSijtUKoCyiLzAlVRp7l4QgPNHxvJFFDyjUVN3oHlMah0XBd4uTb

34、kfPIhHtw0evPmYOrdhEDoPwvYhzlGplU1AU9mpyiCXH8gpPCBRYjq77VcnbXumNE1yGfyTsbSj89J63kRTKDkKUg3mdS5sJ4X5cQ8dK7oW9IkScssECQdz2O9UTlpRjAFPChjhLdzopQzwxQf8ozdzOhogwAooXpUF83BX4C3jRgjDJiiXEUDMaNz4vQ4n164vspddHvOIVuBBdMA4xp1YhiHk0vOJ8TL1BxogzVlMpmod6ianYGmksQq6NWCEd56hZF4wfaNyZcrGfNxnPiG6ZAxSkfmhJAKtNmCqbRmppeXp8inz4eq3HkWCMSORyMMX522xpHG6basNr6KQfbZsFbHjzyNlJrruLolKFcC84dqfijBO5Dy2NaBcNEBPgQrT12PgpcKx2or2YChN5DPjs80zzdtdAdTKuW4uVv9bbZu3K2SZ2aEhTlIC1UqrIWibkzwHh6p8gLv26zr01mJybfOzFc4T7kQH1IpPwOzMDnAKPLsLrznXGjFNIA9bSWWms6ibKZwQIKrMzalwbFrQJvOP1rPH8rx2KkyYqrtQk5VRwM1HSX,