第二章：密码学基分析

第二章：密码学基础2.1、密码学分类2.2、香浓理论2.3、认证系统的信息理论2.4、复杂度理论主讲：钟德林、薛占硕、黄良富、黄顺团12.1、密码学的基本概念密码学(Cryptology)：研究信息系统安全保密的科学。它包含两个分支：密码编码学(Cryptography)，对信息进行编码实现隐蔽信息的一门学问。密码分析学(Cryptanalytics)，研究分析破译密码的学问。2密码体制的分类密码体制有2大类：单钥体制(One-keysystem)：加密密钥和解密密钥相同。双钥体制(Twokeysystem)：加密密钥和解密密钥不同。3现代密码学研究的内容现代密码学研究的相关内容保密性认证性不可否认完整性对称加密单向函数公钥加密Hash函数消息认证码数字签名身份鉴别随机数生成器Hash函数4(1)单钥体制（对称密码体制）单钥体制主要研究问题：密钥产生(Keygeneration)，密钥管理(Keymanagement)。分类：流密码(Streamcipher)分组密码(Blockcipher)单钥体制不仅可用于数据加密，也可用于消息的认证。5(2)双钥体制（非对称密码体制）双钥体制或公钥体制(Publickeysystem)(Diffie和Hellman,1976)每个用户都有一对选定的密钥(公钥k1；私钥k2)，公开的密钥k1可以像电话号码一样进行注册公布。6双钥体制的主要特点加密和解密能力分开可以实现多个用户加密的消息只能由一个用户解读（用于公共网络中实现保密通信）只能由一个用户加密消息而使多个用户可以解读（可用于认证系统中对消息进行数字签字）无需事先分配密钥7密码分析截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下，对密文进行分析，试图获取机密信息。研究分析解密规律的科学称作密码分析学。密码分析在外交、军事、公安、商业等方面都具有重要作用，也是研究历史、考古、古语言学和古乐理论的重要手段之一。8密码分析密码设计和密码分析是共生的、又是互逆的，两者密切有关但追求的目标相反，两者解决问题的途径有很大差别。密码设计是利用数学来构造密码密码分析除了依靠数学、工程背景、语言学等知识外，还要靠经验、统计、测试、眼力、直觉判断能力。有时还靠点运气。9信息的安全性评价无条件安全性和有条件安全性的区别无条件安全性与攻击者的计算能力和时间无关，有条件安全性是根据破解密码系统所需要的计算量来评价安全性的。10保密体制模型明文(消息)(Plaintext)：被隐蔽消息密文(Ciphertext)或密报(Cryptogram)：明文经密码变换成的一种隐蔽形式加密(Encryption)：将明文变换为密文的过程解密(Decryption)：加密的逆过程，即由密文恢复出原明文的过程加密员或密码员(Cryptographer)：对明文进行加密操作的人员11保密体制模型加密算法(Encryptionalgorithm)：密码员对明文进行加密时所采用的一组规则。接收者(Receiver)：传送消息的预定对象。解密算法：接收者对密文进行解密时所采用的一组规则。密钥(Key)：控制加密和解密算法操作的数据处理，分别称作加密密钥和解密密钥。截收者(Eavesdropper)：在信息传输和处理系统中的非受权者，通过搭线窃听、电磁窃听、声音窃听等来窃取机密信息。12保密体制模型密码分析(Cryptanalysis)：截收者试图通过分析从截获的密文推断出原来的明文或密钥。密码分析员(Cryptanalyst)：从事密码分析的人。被动攻击(Passiveattack)：对一个保密系统采取截获密文进行分析的攻击。主动攻击(Activeattack)：非法入侵者(Tamper)、攻击者(Attcker)或黑客(Hacker)主动向系统窜扰，采用删除、增添、重放、伪造等窜改手段向系统注入假消息，达到利已害人的目的。13保密系统模型信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭线信道（主动攻击）C’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道14保密系统应当满足的要求系统即使达不到理论上是不可破的，即pr{m’=m}=0，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。这是著名的Kerckhoff原则。加密和解密算法适用于所有密钥空间中的元素。系统便于实现和使用。15密码可能经受的攻击攻击类型攻击者拥有的资源唯密文攻击加密算法截获的部分密文已知明文攻击加密算法，截获的部分密文和相应的明文选择明文攻击加密算法加密黑盒子，可加密任意明文得到相应的密文选择密文攻击加密算法解密黑盒子，可解密任意密文得到相应的明文16认证与认证系统认证系统(Authenticationsystem)：防止消息被窜改、删除、重放和伪造的一种有效方法,使发送的消息具有被验证的能力，使接收者或第三者能够识别和确认消息的真伪。实现这类功能的密码系统称作认证系统。保密性：保密性是使截获者在不知密钥条件下不能解读密文的内容。认证性：使任何不知密钥的人不能构造一个密报，使意定的接收者解密成一个可理解的消息(合法的消息)。17认证与认证系统目前的认证系统分类：一、无仲裁者的认证系统模型；二、有仲裁者的认证系统模型。认证系统模型的目标：能使发送者通过一个公开无干扰信道将消息发送给接收者，接收者能够确认消息是否来自发送者以及消息是否被敌手篡改。18安全认证系统应满足下述条件意定的接收者能够检验和证实消息的合法性和真实性。消息的发送者对所发送的消息不能抵赖。除了合法消息发送者外，其它人不能伪造合法的消息。而且在已知合法密文c和相应消息m下，要确定加密密钥或系统地伪造合法密文在计算上是不可行的。必要时可由第三者作出仲裁。192.2、香农理论香农(1916,2001),生于密执安州的加洛德。1940年获得麻省理工学院数学博士学位和电子工程硕士学位。1941年他加入了贝尔实验室数学部，在此工作了15年。20熵及其性质例3设电脑彩票由8个10进制数组成，在开奖之前，108个可能号码成为特等奖的概率相同,都是10-8.一旦开奖,我们就知道了特等奖的8个具体号码,因而就获得了8个十进制数的信息。我们获得的信息量与开奖前每个可能号码成为特等奖的概率10-8有何关系?显然,有8=-log1010-8信息量的定量刻划:21熵的数学定义定义1：设p(xi)是一个实验中事件xi发生的概率,则称I(xi)=log2p(xi)为事件xi包含的自信息量。定义2(随机事件的熵)：设一个实验X有x1,x2,...,xn共n个可能的结果，则称H(x)=为实验X的熵(Entropy),其中约定0log0=0。11()()()log()nniiiiiiPxIxPxPx22熵的数学定义引理3.1(Jensen不等式)设f是区间I上的一个连续的严格凸函数，并且ai0,a1+a2+...+an=1,xi∈I,1≤i≤n,则有且上式成立的充要条件是x1=x2=...=xn11()()nniiiiiiafxfax23熵的数学定义推论1：在区间x0时是严格凸的，因而当实数P1,P2,...,Pn满足Pi≥0且P1+P2+...+Pn=1时有且上式成立的充要条件是P1=P2=...=Pn()log(1)bfxxb1loglognibibiPpn24熵的数学定义定义3(联合熵)：实验X与实验Y的可能结果分别为和定义X和Y的联合熵为因此,实验X与实验Y的联合熵(JointEntropy)就是事件(xi,yj)的自信息量的数学期望，它反映了联合分布P(x,y)包含的信息量。12,,...,nxxx12,,...,nyyy11(|)(,)(|)nmijijijHXYPxyIxy11(,)log(|)nmijijijPxyPxy25熵的数学定义定义5(条件熵)：实验X与实验Y的可能结果分别为和定义X与Y的条件熵：(1)称为在实验Y的结果为yj的条件下,事件xi的条件自信息量。(2)称为在实验Y的结果为yj的条件下,实验X的条件熵。12,,...,nxxx12,,...,nyyy(|)log(|)ijijIxyPxy11(|)()(|)()log(|)nnHXypxIxypxpxyjiijiijii26熵的数学定义(3)称为在实验X关于实验Y的条件熵。反映了Y的结果是yj条件下,实验X包含的信息量。反应了Y的结果已知条件下,实验X平均包含的信息量。1111(|)(,)(|)(,)log(|)nmijijijnmijijijHXYpxyIxypxypxy(|)HXyj(|)HXY27联合熵与各自的熵的关系定理3.2：且等号成立，充要条件是X与Y独立。直观含义:两个实验提供的信息总量一定不超过这两个实验分别提供的信息量之和;当且仅当两个实验独立时,二者才相等。(,)()()HXYHXHY28联合熵与条件熵的关系定理3.3直观含义:两个实验提供的信息总量等于第一个信息提供的信息量加上在第一个实验的结果已知条件下,第二个实验提供的信息量.(,)()(|)()(|)HXYHYHXYHXHYX29联合熵与熵的关系定理3.2指出:定理3.3指出：故有推论3.1且等号成立X与Y独立(,)()()HXYHXHY(,)()(|)HXYHYHXY()(|)()()HYHXYHYHX(|)()HXYHX(|)()HXYHX30熵的数学定义定义3.3(平均互信息):称为实验X与实验Y的平均信息。结论：直观地含义：将X包含的未知信息量减去在实验Y的结果已知条件下，X仍具有的未知信息量。就是实验Y提供的X的信息了。(;)()()(,)IXYHXHYHXY(;)()(|)()(|)IXYHXHXYHYHYX31完善保密性的熵的定义一个密码体制称为完善保密的，如果对于任意的x∈P和y∈C,有Pr(x|y)=Pr(x)。一个保密系统（P，C，K，E，D）称为完善的无条件的保密系统，如果H(P)=H(P|C),其中，P为明文集合，C为密文集合，K为密钥集合，E为加密算法,D为解密算法.32完善保密性的熵的定义完善保密系统存在的必要条件是H(P)≤H(K)。可见，要构造一个完善保密系统，其密钥量的对数（密钥空间为均匀分布的条件下）必须不小于明文集的熵。从熵的基本性质可推知，保密系统的密钥量越小，其密文中含有的关于明文的信息量就越大。33伪密钥定义：若H(K|C)=0，则意味着密钥已找到密码体制被攻破。若H(K|C)0，则意味着，给一段密文y，则存在两个或以上的密钥可被用来产生同一个密文y。一般来说，Eve能排除某些密钥，但仍存在许多可能的密钥，这其中只有一个密钥是正确的。我们称那些可能的但不正确的密钥称为伪密钥。34伪密钥定理2.11：假设(P,C,K,E,D)是一个密码体制，|C|=|P|并且密钥是等概率选取的，设RL表示明文的自然语言的冗余度，则给定一个充分长（长n）的密文串，伪密钥的期望满足1||||LnnRKsP35伪密钥密码体制的唯一解距离，就是使得伪密钥的期望数等于0的n的值，记为：即在给定充足的时间下，密码分析者能唯一计算出密钥所需密文的平均量。202log||log||LKnRP362.3、认证系统的信息理论认证理论的主要研究目标：一是推导攻击者成功欺骗的概率下界；二是构造攻击者欺骗成功的概率尽可能小的认证码。认证码是保证消息完整性、认证性的重要工具，也就是保证消息没有被篡改。37认证矩阵的定义认证矩阵是一个矩阵，它的行由密钥来标记，列由信源状态来标记，对每一个k∈K和s∈S，该矩阵的第k行第s列的元素是。||*||ks()ses38认证码攻击中的