第2章 密码学的基本概念和信息理论基础.ppt

1、1,第2章 密码学的基本概念和信息理论基础,2,密码学的发展历史,第1阶段：1949年以前。 第2阶段：从1949年到1975年。 标志：1949年Shannon发表的保密系统的信息理论一文。 第3阶段：1976年至今。 标志：1976年Diffie和Hellman发表了密码学新方向一文。,3,古典加密,早妆未罢暗凝眉， 迎户愁看紫燕飞， 无力回天春已老， 双栖画栋不如归。,4,Shannon模型,5,组成部分,X,明文（plain-text）： 作为加密输入的原始信息。 Y,密文（cipher-text）：对明文变换的结果。 E,加密（encrypt）：是一组含有参数的变换。 D,解密（de

2、crypt）：加密的逆变换。 Z,密钥（key）：是参与加密解密变换的参数。,6,密码体制的分类,几种不同的分类标准 按操作方式进行分类 操作方式：是明文变换成密文的方法 替代操作、置换操作、复合操作 按照使用密钥的数量进行分类 对称密钥（单密钥） 公开密钥（双密钥） 按照对明文的处理方法进行分类 流密码 分组密码,7,Kerckhoffs假设,假定：密码分析者知道对方所使用的密码系统 包括明文的统计特性、加密体制（操作方式、处理方法和加/解密算法 ）、密钥空间及其统计特性。 不知道密钥。 在设计一个密码系统时，目标是在Kerckhoffs 假设的前提下实现安全 。,8,密码分析,密码分析 ：

3、从密文推导出明文或密钥 。 密码分析常用的方法有以下4类： 惟密文攻击（cybertextonly attack）； 已知明文攻击（knownplaintext attack）； 选择明文攻击（chosenplaintext attack）； 选择密文攻击（chosenciphertext attack）。,9,密码分析,惟密文攻击: 密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文。 已知明文攻击: 密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对

4、采用同一密钥加密的所有新消息进行解密。,10,密码分析,选择明文攻击: 密码分析者不仅知道一些消息的密文以及与之对应的明文，而且可以选择被加密的明文（这种选择可能导致产生更多关于密钥的信息），并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密） 选择密文攻击: 密码分析者能够选择不同的密文并能得到对应的明文，密码分析的目的是推导出密钥。,11,密码系统,一个好的密码系统应满足： 系统理论上安全，或计算上安全； 系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密； 加密和解密算法适用于密钥空间中的所有元素； 系统既易于实现又便于使用。,12,加密的功能,保密性

5、：基本功能，使非授权者无法知道消息的内容。 鉴别：消息的接收者应该能够确认消息的来源。 完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。 不可否认性：发送方不能否认已发送的消息。,13,古典加密技术,代替密码 置换密码,14,【例21】简单的加密形式，基于块加密和异或运算。 消息：00110101010001010011010100101011 10010101 消息块：00110101 01000101 00110101 00101011 10010101 密钥：01010101 01010101 01010101 01010101 01010101,密文：01100000 00

6、010000 01100000 01111110 11000000,15,代替密码（1）,代替密码（substitution cipher）：明文中的每个字符被替换成密文中的另一个字符。 简单代替，即单字母密码; 明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。如Caesar密码； 多码代替密码； 没有隐藏明文中不同字母的统计特性 ，安全性有所提高。,16,代替密码（2）,多字母代替密码 ： 字符块被成组加密 ，有利于抗击统计分析,如Playfair密码。 多表代替密码 ： 有多个映射表，可隐藏单字母出现的频率分布,如Vigenre密码。,17,【例22】

7、著名的Caesar密码：加密时26个英文字母循环后移3位，解密时则循环前移3位。该方法最早在公元前50年，被罗马大帝Julius Caesar使用。,ABCDEFGHIJKLMNOPQRSTUVWXYZ,则密文为： PRP,2.设明文为：CHINA,则密文为: FKLQD,1.设明文为：MOM,18,【例23】代替密码体制的一般定义，设P=C=K=Z26, 这里P,C,K, Z26分别表示明文空间，密文空间，密钥空间和26个整数（对应26个英文字母）组成的空间。很明显，明文，密文和密钥的取值范围是一样的，它们的空间也是相同的。 对于任意的 定义： 加密： 即明文为x，密钥为k（实际上就是非个英

8、文字母向后循环移k位），密文为y。 解密： 使用该方法时，要求26个字母与模26的剩余类集合建立一一对应关系，如A对应0，B对应1，Z对应25，不区分大小写。,19,A B C D E F G H I 0 1 2 3 4 5 6 7 8 J K L M N O P Q R 9 10 11 12 13 14 15 16 17 S T U V W X Y Z 18 19 20 21 22 23 24 25,20,当k=3时，即为著名的Caesar密码 设明文为：China，对应的数字为：2 7 8 13 0 加密：C: e3(2)=2+3(mod26)=5,对应着字母F h：e3(7)=7+3(m

9、od26)=10, 对应着字母K I: e3(8)=8+3(mod26)=11, 对应着字母L N: e3(13)=13+3(mod26)=16,对应着字母Q A: e3(0)=0+3(mod26)=3,对应着字母D 所以明文“China”基于Caesar密码被加密为“FKLQD”,21,解密就是加密过程的逆过程 解密：F:d3(5)=5-3(mod26)=2,对应着C K:d3(10)=10-3(mod26)=7,对应着H L:d3(11)=11-3(mod26)=8,对应着I Q:d3(16)=16-3(mod26)=13,对应着N D:d3(3)=3-3(mod26)=0,对应着A 即“

10、FKLQD“经Caesar密码解密恢复为”China”（不区分大小写） Caesar密码的特点：明文语言集已知，并且易于识别，结构过于简单，所以很容易被攻击。,22,【例24】（简单代替）移位密码，即向后移k位，k是任意的，故认为k是密钥，共有26个密钥，看看使用密钥的代替加密。选用一个英文短语或单词作为密钥，去掉其中重复的字母得到一个无重复字母的字符串，然后将字母表中的其他字母依此写于此字母串之后。 设密钥为：key 明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ 对应的密文：keyabcdfghijlmnopqrstuvwxz 因此，明文“China”,对应的密文为：“yfgm

11、k”,23,【例25】（多字母代替）Playfair密码，将明文中的一个字母组合作为一个单元对待，并将这些单元转换为密文双字母组合。Playfair密码是基于一个55字母矩阵，该矩阵使用一个关键词（密钥）来构造，构造方法是：从左到右，从上到下依此填入关键词的字母（去除重复的字母），然后再以字母表顺序依此填入其他字母。字母I和J被算做一个字母。 对每对明文字母P1,P2的加密方法如下：,24,1）若P1,P2在同一行上，则对应的密文C1,C2分别是紧靠在P1,P2右端的字母。其中第一列被看做是最后一列的右方（解密时反向） 2) 若P1,P2在同一列上，则对应的密文C1,C2分别是紧靠在P1,P2

12、下方的字母，其中其中第一行被看做是最后一行的下方（解密时反向） 3) 若P1,P2不在同一行上，也不在同一列上，则C1,C2是由P1,P2确定的矩阵的其他两角的字母。并且C1和P1，C2和P2同行。（解密时反向） 4) 若P1=P2，则插入一个字母（比如Q，需要事先约定）于重复字母之间，并用前述方法处理 5 ）若明文字母数是奇数，则在明文的末端添加某个事先约定的字母作为填充。,25,密钥是:PLAYFAIR IS A DIGRAM CIPHER,则构造的字母矩阵如图所示。,26,如果明文是：P=playfair cipher 先将明文分成两个一组：pl ay fa ir ci ph er,基于

13、表对应的密文为： LA YF PY RS MR AM CD,27,Vigenre密码,构成 明文：每个字符惟一对应一个025间的数字。 密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如a 表示位移 0，b 表示位移 1，c 表示位移 2，. ）。 加密过程： 将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模26），得到密文数字串； 最后，将密文数字串转换为字母串。,28,A B C D E F G H I 0 1 2 3 4 5 6 7 8 J K L M N O P Q R 9 10 11 12 13 14 15 16 17 S T U V W X Y Z 18

14、19 20 21 22 23 24 25,29,【例25】明文串：they will arrive tomorrow，采用密钥k=Monday对其加密的过程如 首先，依据上表，将密钥与明文转化为数字串： k=(12,14,13,3,0,24) m=(19,7,4,24,22,8,11,11,0,17,17,8,21,4,19,12,14,17,17,14,22) 其次，将明文数字串依据密钥匙长度分段，并逐一与密钥数字串相加（模26），得到密文数字串,30,19 7 4 24 22 8 11 11 0 17 17 8 12 14 13 3 0 24 12 14 13 3 0 24 5 21 17

15、 1 22 6 23 25 13 20 17 6 21 4 19 14 12 14 17 17 14 22 12 14 13 3 0 24 12 14 13 3 7 18 6 17 12 12 3 5 1 25,31,C=(5,21,17,1,22,6,23,25,13,20,17,6,7,18,6,17,12,12,3,5,1,25) 最后，依据上表将密文数字串转换为字母串 c=FVRBWG XZNURG HSGRMM DFBZ,32,置换密码,置换密码（permutation cipher）：又称换位密码（transposition cipher） ，并没有改变明文字母，只改变了这些字母的

16、出现顺序。,33,【例26】（置换密码） 为了理解更容易，先考虑下面字符置换的例子： 明文：MY_DOG_HAS_FLEAS(空格记数作为字符，以下划线显示) 密钥：1-4，2-8，3-1，4-5，5-7，6-2，7-6，8-3（位1移到位置4）明文字符块：MY_DOG_H AS_FLEAS 密文：_DYOHM_G AFSLSA_E,34,【例27】（置换密码） 明文：00100101 01101011 10010101 01010100 密钥：1-4，2-8，3-1，4-5，5-7，6-2，7-6，8-3 下面给出被分成8位块的明文，以及基于明文密钥的应用的相应密文。 明文8位块：00100

17、101 01101011 10010101 01010100 密文： 00001011 10111010 01001101 01100001,35,【例28】(置换密码)明文为cryptography is an applied science。假设密钥是encry。根据密钥中字母表中的出现次序可确定为23145。将明文按照密钥长度逐行列出，如下表所示。然后依照密钥决定的次序按列依次读出，因此，密文为：yripdn cohnii rgyaee paspsc tpalce。,密钥,36,密码分析,主要方法：1.频率分析2.考虑最有可能的字母及可能出现的单词3.重复结构分析4.持久性，组织性，创造

18、性和运气5.明文已知并且易于识别也很重要,37,英文统计,利用字母或单词在英文经典样本中出现的频率的一种技术 常见的单词有：the, to, of, I, a ,and ,is ,that , in ,it ,for ,you ,be ,。,38,英文统计,单字母中，每个字母有26中可能性。出现频率前五位：e, t, a, o, I 。e：12.7%，z：0.1%，相差100多倍，存在十分显著的统计偏差。 2个字母的所有组合有26*26=676种。常见：th, in , he , er, re, on , an , at , on , or, es, ha, to 3个字母的所有组合为26*2

19、6*26=17576种。不到1/70的3字母组占所有出现的三字母组的50%。常见：the, ing, and, hat, tha, ion, you, ent, for, tio, thi, her, ati,our,39,英文统计,作为一个统计特性，空格出现的频率是任何其他字符的2倍。在很多场合，加密之前就应将空格去除，要不然很可能被密码分析者利用。 2字母（包含空格）常见：E_, t_, th, s_, t_, _a, in, _I, he, er, d_ 3字母（包含空格）常见：_th, the, he_, ing, _to, to_, ng_,40,【例29】攻击一个密码，首先统计密文

20、中最常见出现的字母，例如在密文 QCIV XY KEO JLYYW JBRO XN KEO JKGOOK . TOK SO KX KEO AELGAE XY KBSO . KEO NBJE CGO MLSDBYT CYR KEO AXKKXY BJ EBTE. XLG JKCKO NCBG BJ KEO HOJK JKCKO NCBG.,K:18 0:16 E:11 B:9 J:9,41, 首先，设想K是e 或者t，E是两个中的另一个，首先，假定K=e, O=t， 得到（一部分）,QCIV XY eEt JLYYW JBRt XN eEt JeGtte TtE St Ex eEt AEUGAE

21、 XY.,“TtE”在第2个句子就出了问题。似乎任何一个字母替代“T”所形成的词来推导一个句子都是不可能的。因此，改试K=t,O=e;,42,QCIV XY tEe JLYYW JBRe XN tEe JtGeet. Tet Se tX tEe AELGAE XY tBSe. tEe NBJE CGe MLSDBYT CYR tEe AXttXY BJ EBTE. XLG JtCte NCBG BJ tEe HeJt JtCte NCBG “tEe”猜想E=h, “tX”猜想X=o, ”XY”猜想Y=n, 这就得到,43,QCIV on the JLnnW JBRe oN the JtGeet

22、. Tet Se to the AhLGAh on tBSe. the NBJh CGe MLSDBnT CnR the Aotton BJ hBTh. oLG JtCte NCBG BJ the HeJt JtCte NCBG ”Tet Se to the”猜想“get me to the”,有T=g并且S=m,“JtGeet”可能是”street”,因此J=s, G=r;,44,QCIV on the sLnnW sBRe oN the street. get me to the AhLGAh on tBme. the NBsh Cre MLmDBng CnR the Aotton Bs

23、hBgh. oLr stCte NCBr Bs the Hest stCte NCBr. 由“MUmDBng”的结尾和“Bs hBgh”，猜想B=i。由“oLr” 猜想L=u。,45,重新整理,得 QCIV on the sunnW siRe oN the street. get me to the AhLrAh on time. the Nish Cre MumDing CnR the Aotton is high. our stCte NCir is the Hest stCte NCir. 由“sunnW siRe oN”，猜想W=y, R=d,N=f。重新整理：,46,QCIV on

24、the sunny side of the street. get me to the AhurAh on time. the fish Cre MumDing Cnd the Aotton is high. our stCte fCir is the Hest stCte fCir. 由“Cre MumDing”，猜想C=a; 由“the Hest”，猜想H=b;由“AhurAh”，猜想A=c, 由“Aotton”，猜想A=c。,47,到这里，剩下的明文字母不多了，因为“b”已经存在，所以“MumDing”不能是M=b。经过反复实验后，我们可以认定M=j, D=p, 现在得到： QaIV o

25、n the sunny side of the street. get me to the church on time. the fish are jumping and the cotton is high. our state fair is the best state fair.,48,小结,如果保留了单词的边界，那么破译这样的密码就比较容易，这也是因为单词边界的保留可以使密码分析者充分利用短单词的信息。 密钥空间是巨大的，加密a有26种选择，剩下25种选择加密b，24种选择加密e，依次类推，这样就有： 26*25*24*5*4*3*2*1=403 291 461 126 605 6

26、35 584 000 000,49,Vigenre密码的密码分析（1）,第一步：确定密钥的长度，主要方法有： Kasiski测试法； 重合指数法。,50,Kasiski测试法,基本原理：对于密钥长度为d的Vigenre密码，如果利用给定的密钥表周期性地对明文字母进行加密，则当明文中有两个相同的字母组在明文序列中间隔的字母数为d的倍数时，这两个明文字母组对应的密文字母组一定相同；反之，如果密文中出现两个相同的字母组，则其对应的明文字母组不一定相同。 找出密文中的相同字母组，并研究其相间隔的字母数，确定这些字母数的最大公因子，便有可能得到有关密钥长度的信息,51,字典攻击,发送方和接收方会选择容易

27、记忆的词或短语做密钥。那么对于发送方和接收方熟悉的攻击者就可能会尝试这种密钥,只需要生成一个短的多的最有可能的密钥列表即可。 如果明文和密钥都不是没有意义的文字时，字典攻击就有可能成功。,52,重合指数法,基本思想：对于长度分别为n的密文串y=y1y2yn ，将其分为长度为n/d的d个子串Yi（i=1,2,d),如果密钥长度为d，则Ic(Yi)0.065(1id) ，否则，因为采用不同的密钥依位加密，子串Yi将更为随机。对于一个完全随机的密文串，Ic(y)26(1/26)2 =0.038。由于0.038与0.065的差值足够大，所以在一般情况下，依据重合指数法能够判断出正确的密钥长度。,53,

28、Shannon的保密系统信息理论,1949年， Shannon发表了一篇题为保密系统的信息理论的论文。 用信息论的观点对信息保密问题进行了全面的阐述。 宣告了科学的密码学时代的到来。,54,通信系统模型,目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。,55,保密系统模型,目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。,56,密码体制的安全性（1）,无条件安全或完善保密性（unconditionally secure）： 不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文； 具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析

29、者也无法破译某个密码系统。,57,完善保密性,一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法,则完善保密系统存在的必要条件是H(P)H(K)。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。 从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。 存在完善保密系统 如：一次一密（one-time pad）方案；不实用。,58,密码体制的安全性（2）,实际上安全 计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。 可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。,59,伪密钥,当分析者截获到密文c时，他首先利用所有的密钥对其进行解密，并得到明文mDk (c)，kK。接下来，对于所有有意义的消息m，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，