第2讲密码学基本概念和信息理论基础

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第2讲,密码学的基本概念和信息理论基础,1,密码学的发展历史,第,1,阶段：,1949,年以前。,第,2,阶段：从,1949,年到,1975,年。,标志：,1949,年,Shannon,发表的,保密系统的信息理论,一文。,第,3,阶段：,1976,年至今。,标志：,1976,年,Diffie,和,Hellman,发表了,密码学新方向,一文。,2,Shannon模型,3,组成部分,X,明文（,plain-text,）： 作为加密输入的原始信息。,Y,密文（,cipher-text,）：对明文变换的结果。,E,加密（,encrypt,）：是一组含有参数的变换。,D,解密（,decrypt,）：加密的逆变换。,Z,密钥（,key,）：是参与加密解密变换的参数。,4,密码体制的分类,几种不同的分类标准,按操作方式进行分类,操作方式：是明文变换成密文的方法。,替代操作、置换操作、复合操作。,按照使用密钥的数量进行分类,对称密钥（单密钥）。,公开密钥（双密钥）。,按照对明文的处理方法进行分类,流密码。,分组密码。,5,Kerckhoffs假设,假,定：密码分析者知道对方所使用的密码系统,包括明文的统计特性、加密体制（操作方式、处理方法和加,/,解密算法 ）、密钥空间及其统计特性。,不知道密钥。,在设计一个密码系统时，目标是在,Kerckhoffs,假设的前提下实现安全 。,6,密码分析,密码分析 ：从密文推导出明文或密钥 。,密码分析：常用的方法有以下,4,类：,惟密文攻击（,cybertextonly attack,）；,已知明文攻击（,knownplaintext attack,）；,选择明文攻击（,chosenplaintext attack,）；,选择密文攻击（,chosenciphertext attack,）。,7,惟密文攻击,密码分析者知道一些消息的密文（加密算法相同），并且试图恢复尽可能多的消息明文，并进一步试图推算出加密消息的密钥（以便通过密钥得出更多的消息明文。,8,已知明文攻击,密码分析者不仅知道一些消息的密文，也知道与这些密文对应的明文，并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密。,9,选择明文攻击,密码分析者不仅知道一些消息的密文以及与之对应的明文，而且可以选择被加密的明文（这种选择可能导致产生更多关于密钥的信息），并试图推导出加密密钥或算法（该算法可对采用同一密钥加密的所有新消息进行解密）。,10,选择密文攻击,密码分析者能够选择不同的密文并能得到对应的明文，密码分析的目的是推导出密钥。,11,密码系统,一个好的密码系统应满足：,系统理论上安全，或计算上安全；,系统的保密性是依赖于密钥的，而不是依赖于对加密体制或算法的保密；,加密和解密算法适用于密钥空间中的所有元素；,系统既易于实现又便于使用。,12,加密的功能,保密性：基本功能，使非授权者无法知道消息的内容。,鉴别：消息的接收者应该能够确认消息的来源。,完整性：消息的接收者应该能够验证消息在传输过程中没有被改变。,不可否认性：发送方不能否认已发送的消息。,13,古典加密技术,代替密码,置换密码,14,代替密码,代替密码（,substitution cipher,）：明文中的每个字符被替换成密文中的另一个字符。,简单代替，即单字母密码，如,Caesar,密码；,多码代替密码；,多字母代替密码；,多表代替密码，如,Vigenre,密码。,15,置换密码,置换密码（,permutation cipher,）：又称换位密码（,transposition cipher,） ，并没有改变明文字母，只改变了这些字母的出现顺序。,16,代替密码的特点,单字母代换密码 ：明文中字母的出现频度、重复字母的模式和字母相互之间的结合模式等统计特性不变，安全性差。,多码代替密码 ：没有隐藏明文中不同字母的统计特性 ，安全性有所提高。,多字母代替密码 ：字符块被成组加密 ，有利于抗击统计分析。,多表代替密码 ：有多个映射表，可隐藏单字母出现的频率分布。,17,Vigenre密码,构成,明文：每个字符惟一对应一个,025,间的数字。,密钥：一个字符串，其中每个字符同明文一样对应一个数字，代表位移值，如,a,表示位移,0,，,b,表示位移,1,，,c,表示位移,2,，,.,）。,加密过程：,将明文数字串依据密钥长度分段，并逐一与密钥数字串相加（模,26,），得到密文数字串；,最后，将密文数字串转换为字母串。,18,Vigenre密码的密码分析（1）,第一步：确定密钥的长度，主要方法有：,Kasiski,测试法；,重合指数法。,19,Kasiski,测试法,基本原理：对于密钥长度为的,Vigenre,密码，如果利用给定的密钥表周期性地对明文字母进行加密，则当明文中有两个相同的字母组在明文序列中间隔的字母数为的倍数时，这两个明文字母组对应的密文字母组一定相同；反之，如果密文中出现两个相同的字母组，则其对应的明文字母组不一定相同。,20,重合指数法,基本思想：对于长度分别为,n,的密文串,y=y1y2yn,，将其分为长度为,n/d,的,d,个子串,Yi,（,i=1,2,d),如果密钥长度为,d,，则,Ic(Yi)0.065(1id),，否则，因为采用不同的密钥依位加密，子串,Yi,将更为随机。对于一个完全随机的密文串，,Ic(y)26(126)2=0.038,。由于,0.038,与,0.065,的差值足够大，所以在一般情况下，依据重合指数法能够判断出正确的密钥长度。,21,Vigenre密码的密码分析（2）,第二步：确定密钥。,通常采用重合互指数法 。对于长度分别为,n,及,n,的字母串,x=x1x2xn,和,y=y1y2yn,，“重合互指数”指的是,x,的一个随机元素与,y,的一个随机元素相同的概率，记为,MIc(x,y),。,通过采用重合互指数法，可以获得任何两个子串,Yi,与,Yj,的相对移位。,22,Shannon的保密系统信息理论,1949,年，,Shannon,发表了一篇题为,保密系统的信息理论,的论文。,用信息论的观点对信息保密问题进行了全面的阐述。,宣告了科学的密码学时代的到来。,23,通信系统模型,目的：在信道有干扰的情况下，使接收的信息无错误或差错尽可能小。,24,保密系统模型,目的：使窃听者即使在完全准确地收到了接收信号的情况下也无法恢复出原始消息。,25,密码体制的安全性（,1,）,无条件安全或完善保密性（,unconditionally secure,）,：,不论提供的密文有多少，密文中所包含的信息都不足以惟一地确定其对应的明文；,具有无限计算资源（诸如时间、空间、资金和设备等）的密码分析者也无法破译某个密码系统。,26,完善保密性,一个保密系统（,P,，,C,，,K,，,E,，,D,）称为完善的无条件的保密系统，如果,H(P)=H(P|C),其中，,P,为明文集合，,C,为密文集合，,K,为密钥集合，,E,为加密算法,D,为解密算法,则完善保密系统存在的必要条件是,H(P)H(K),。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。,从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。,存在完善保密系统,如：一次一密（,one-time pad,）方案；不实用。,27,密码体制的安全性（,2,）,实际上安全,计算上是安全：算出和估计出破译它的计算量下限，利用已有的最好的方法破译该密码系统所需要的努力超出了破译者的破译能力（诸如时间、空间、资金等资源）。,可证明安全：从理论上证明破译它的计算量不低于解已知难题的计算量。,28,伪密钥和惟一解距离,当分析者截获到密文,c,时，他首先利用所有的密钥对其进行解密，并得到明文,m,Dk(c),，,kK,。接下来，对于所有有意义的消息,m,，他记录下与之对应的密钥。这些密钥构成的集合通常含有多个元素，并且至少含有一个元素，即正确的密钥。人们把那些可能在这个集合中出现但并不正确的密钥称为伪密钥（,spurious key,）。,一个保密系统的惟一解距离定义为使得伪密钥的期望数等于零的,n,的值，记为,n0,，即在给定的足够的计算时间下分析者能惟一地计算出密钥所需要的密文的平均量。,用于衡量在惟密文攻击下破译一个密码系统时，密码分析者必须处理的密文量的理论下界。,29,Simmons认证系统的信息理论,内容：将信息论用于研究认证系统的理论安全性和实际安全性问题，指出认证系统的性能极限以及设计认证码所必须遵循的原则。,目的：一个是推导欺骗者欺骗成功的概率的下界；另一个是构造欺骗者欺骗成功的概率尽可能小的认证码。,30,认证码,基本要素有,3,个：,信源集合；,消息集合；,编码规则集合，其中每一个编码规则由一个秘密密钥来控制。,31,认证系统模型,一种是无仲裁者的认证系统模型。在这种模型中，只有,3,种参加者，即消息的发送者、接收者和入侵者。消息的发送者和接收者之间相互信任，他们拥有同样的秘密信息。,另一种是有仲裁者的认证系统模型。在这种模型中，有,4,种参加者，即消息的发送者、接收者、入侵者和仲裁者，信息的发送者和接收者之间相互不信任，但他们都信任仲裁者，仲裁者拥有所有的秘密信息并且不进行欺骗。,32,无仲裁者的认证系统模型,33,无仲裁者的认证系统数学描述,一个无分裂的、没有保密功能的、无仲裁者的认证系统，可由满足下列条件的四重组（,S,，,A,，,K,，,）来描述：, S,是所有可能的信源状态构成的一个有限集，称为信源集；, A,是所有可能的认证标签构成的一个有限集；, K,是所有可能的密钥构成的一个有限集，称为密钥空间；,对每一个,kK,有一个认证规则：,ek,：,S-A,。,消息集,M,定义为,M = SA。,34,