2密码学基础

密码学基础吴汉炜海南大学信息科学与技术学院2基本概念密码学的用途:解决难题.密码学解决的难题围绕的安全需求:机密性、完整性、认证性、不可否认性、公平性加密方案:密钥产生算法,加密算法(不一定是确定性算法),解密算法3明文明文密文加密算法解密算法密钥密钥加密与解密加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(EncryptionKey)和解密密钥(DecryptionKey).4加密通信模型5密钥的必要性攻击者总能设法找到算法.除非你就是个密码学家,并开发了自己的算法,否则你就必须相信开发出算法的公司不会将算法有意无意地泄露.公开的算法更安全.算法公开后,密码分析者和计算机工程师就有了检验它弱点的机会.6密码算法分类对称密码体制:(私钥密码体制,秘密密钥密码体制）加密密钥和解密密钥相同,或实质上等同,即从一个容易推出另一个.非对称密码体制:（公钥密码体制）加密密钥和解密密钥不相同,从一个很难推出另一个.加密密钥可以公开,称为公钥,解密密钥必须保密,称为私钥.7密码分析唯密文攻击已知明文攻击选择明文攻击:例如公钥密码体制选择密文攻击8安全的密码体制具有的性质从密文恢复明文应该是难的，即使分析者知道明文空间（如明文是英语）。从密文计算出明文部分信息应该是难的。从密文探测出简单却有用的事实应该是难的，如相同的明文信息被加密发送了两次。9攻击结果完全攻破:敌手找到了相应的密钥部分攻破:敌手没有找到相应的密钥，但对于给定的密文，敌手能够获得明文的特定信息。密文识别:如对于两个给定的不同明文及其中一个明文的密文，敌手能够识别出该密文对应于哪个明文；或者能够识别出给定明文的密文和随机字符串。如果一个密码体制使得敌手不能在多项式时间内识别密文，这样的密码体制称为达到了语义安全（semanticsecurity）。10密码体制的安全性无条件安全性:如果密码分析者具有无限的计算能力，密码体制也不能被攻破,One-timePad计算安全性:如果攻破一个密码体制的最好的算法用现在或将来可得到的资源都不能在足够长的时间内破译.目前还没有任何一个实际的密码体制被证明是计算上安全的.密码体制对某一种类型的攻击（如蛮力攻击）是计算上安全的，但对其他类型的攻击可能是计算上不安全的11密码体制的安全性可证明安全性:把密码体制的安全性归结为某个经过深入研究的数学难题。例如如果给定的密码体制是可以破解的，那么就存在一种有效的方法解决大数的因子分解问题，而因子分解问题目前不存在有效的解决方法，于是称该密码体制是可证明安全的，即可证明攻破该密码体制比解决大数因子分解问题更难。可证明安全性只是说明密码体制的安全与一个问题是相关的，并没有证明密码体制是安全的，可证明安全性也有时候被称为归约安全性。12数论中的难题离散对数问题:指给定有限循环群G，G的生成元g，元素aG，求logga(求x满足a=gx)。表示问题:给定阶为m的有限循环群G，G的不同生成元组是g1，…，gnG，如果(x1，…，xn)满足称元组(x1，…，xn)为元素aG对应于(g1，…，gn)的一个表示。表示问题是指给定阶为m的有限循环群G，G的不同生成元组是g1，…，gnG，求元素aG对应于(g1，…，gn)的一个表示。1212...nxxxnaggg13数论中的难题Diffie-Hellman问题计算Diffie-Hellman(CDH)问题是指给定有限循环群G，G的生成元g，元素gu、gvG，求guvG。判定Diffie-Hellman(DDH)问题是指给定有限循环群G，G的生成元g，元素gu、gv、gwG，判定gw=guv是否成立。14数论中的难题强Diffie-Hellman问题G为阶p的有限循环群，gG是G的生成元，给定g，gx，，…，G，求元组(c，g1/(x+c))G。大数分解问题大数分解问题是指给定正整数n，找出它的因数分解。即求出素数p1，…，pk和整数e1，…，ek使得n=p1e1…pkek2xg（）qxg（）15数论中的难题RSA问题n是两个大素数的乘积n=pq，gcd(e，(n))=1，aZn*，求bZn*满足be=a(modn)。强RSA问题n是两个大素数的乘积n=pq，aZn*，求b、eZn*满足be=a(modn)。16伪随机序列不可预测性:敌对者获得伪随机序列y部分位的信息不应能预测到y其他位的信息与种子x的信息随机性:满足随机性统计检验。常用的统计检验包括：若p为偶数，则“0”和“1”的出现次数相同，均为p/2，若p为奇数，则“0”出现次数为(p1)/2。游程为l的串占1/2，即长度为1的串应占一半，长度为2的串应占1/4，长度为3的串应占等1/8等。长度为3的形如0串…10001…，1串…01110…。17用于加密和解密的密钥是一样的或相互容易推出。KeyA加密B解密明文明文密文对称密码体制18种类序列密码(流密码):将明文消息按字符位地加密分组密码:将明文消息分组(每组含有多个字符)，逐组地进行加密19分组密码将明文分成m个明文块x=(x1，x2，…，xm)。每一组明文在密钥k=(k1，k2，…，kt)的控制下变换成n个密文块y=(y1，y2，…，ym)，每组明文用同一个密钥k加密。优点:容易标准化,容易实现同步缺点:不能隐蔽数据模式。即相同的密文组蕴含着相同的明文组;不能抵抗组的重放、嵌入和删除等攻击;密钥管理困难DES,AES,IDEA20分组密码的操作模式电子密码本ECB密码分组链接CBC密码反馈CFB输出反馈OFB计数模式CTR21ECBx1x2x3x4y4y3y2y1DESDESDESDES22ECB剪切粘贴(CutandPaste)攻击假设明文是AlicedigsBob.TrudydigsTom.假设64位的明文块和8位的ASCII:P0=“Alicedi”,P1=“gsBob.”,P2=“Trudydi”,P3=“gsTom.”密文:C0,C1,C2,C3Trudy剪切并粘贴:C0,C3,C2,C1解密AlicedigsTom.TrudydigsBob.23ECB的缺陷假设Pi=Pj那么Ci=Cj，Trudy就知道了Pi=Pj即使T不知道Pi或Pj，他也了解了一些信息Trudy可能知道Pi这是一个严重的问题吗?24Alice讨厌ECB的模式Alice的压缩图像,Alice用ECB的方式加密(TEA)为什么会这样?同样的明文块同样的密文!25CBCx1++++IVx2x3x4y4y3y2y1DESDESDESDES26Alice喜欢CBC的模式Alice的压缩图像,Alice用CBC的方式加密(TEA)为什么会这样?相同的明文不同的密文27CFBIVeKeKy1+x1eKx2y2+28OFBIVeKeKy1+x1x2y2+29计数器模式xi-1xixi+1Yi-1ctr+i-1YiYi+1eKeKctr+ictr+i+1eK30公钥密码加密/解密：发送方用接收方的公开密钥加密报文数字签名：发送方用自己的私有密钥签署报文。密钥交换：两方合作以便交换会话密钥31将一个定义域映射到一个值域，使得每个函数值有一个唯一的原像。Y=f(X)容易X=f-1(Y)不可行单向函数单向陷门函数单向散列函数32单向陷门函数Y=fk(X)容易，知道k和XX=fk-1(Y)容易，知道k和YX=fk-1(Y)不可行，知道Y不知道k一个实用的公开密钥方案的发展依赖于找到一个单向陷门函数。33公钥密码体制的安全性是指计算上的安全性安全性的理论基础：复杂性理论一个算法的复杂性由该算法所需求的最大时间（T）和存储空间（S）度量。由于算法用于同一问题的不同规模实例所需求的时间和空间往往不同，所以总是将他们表示成问题实例的规模n的函数，n表示描述该实例所需的输入数据长度。34公钥密码体制的安全性一个密码系统的保密性依赖于它所依赖的问题的计算复杂性，但是以计算上困难的问题为基础，却不一定导致一个保密性很强的密码系统35公钥密码体制的安全性（1）计算复杂性理论通常分析一个问题的一个孤立的事例，但在密码分析时往往需要解决许多统计上相关的问题，例如，破译由同一个加密密钥生成的几段密文。（2）计算复杂性理论通常做的是最坏情形的度量，一个多项式时间内不可解的困难问题，完全有可能对其中大多数事例是多项式时间可解的。然而，一个对大多数事例是信息容易破解的密码系统却是毫无用处的。（3）计算复杂性理论对问题的难易分类时，通常只考虑是否存在确定的多项式时间算法。但是，一个可以通过某个概率多项式时间算法以很高的概率攻破的公开密钥密码系统，即使不存在确定的多项式时间算法去攻破它，也同样是没有用途的36公钥密码分析公钥体制可能受到强行攻击。防范措施：长密钥。但从实用性角度，要考虑折衷。另一种形式的攻击是找到某种根据公钥计算私钥的方法。目前为止，对于一个特定的公钥算法，尚未从数学上证明这种攻击不可能有一种形式上的攻击对公钥系统是特有的。假设发送的报文仅仅含有一个56比特的DES密钥。敌对方可以用公钥加密所有的可能密钥，然后匹配。因而无论密钥方案的密钥大小是多少，攻击都归结为对56bit密钥的强行攻击。37基于大整数因子分解问题的，比如RSA体制、Rabin体制基于离散对数问题的，比如ElGamal体制、椭圆曲线密码体制ECC、Diffie-Hellman密钥交换主要公钥密码体制38公钥密码经典算法RSA算法Diffie-Hellman密钥交换算法ElGamal加密算法Rabin加密算法39RSA算法（1）取两个随机大素数p和q（保密）（2）计算公开的模数n=pq(公开)（3）计算秘密的欧拉函数(n)=（p-1）(q-1)（保密）（4）随机选取整数e，满足gcd(e,(n))=1(公开e，加密密钥)（5）计算d，满足de≡1(mod(n))(保密d，解密密钥，e的逆元。陷门信息)（6）加密:y=xe(modn)（7）解密:x=yd(modn)40Diffie-Hellman密钥交换算法的数学基础41Diffie-Hellman密钥交换算法全局公开量:大素数qgq且是q的本原根用户密钥的产生（比如A）选择随机数:xAq计算公开量:yA=gxAmodq产生密钥（比如A）KAB=yAxBmodq=yBxAmodq=gxA.xBmodq42ElGamal密码体制：由ElGamal[1984,1985]提出，是一种基于离散对数问题的双钥密码体制，既可用于加密，又可用于签字。（1）方案：Zp:p个元素的有限域p:一个大素数g：是Zp*(Zp中除去0元素)中的一个本原元或其生成元明文集M：Zp*密文集C：Zp*×Zp*。公钥：选定g(gp的生成元)，计算公钥gmodp秘密钥：pElGamal密码体制43ElGamal密码体制(2)加密：选择随机数kZp-1，且gcd(k,p－1)=1，计算：y1=gkmodp(随机数k被加密)y2=Mkmodp(明文被随机数k和公钥加密)M是发送明文组。密文由y1、y2级连构成，即密文C=y1||y2。44特点：密文由明文和所选随机数k来定，因而是非确定性加密，一般称之为随机化加密，对同一明文由于不同时刻的随机数k不同而给出不同的密文。代价是使数据扩展一倍。(3)解密：收到密文组C后，计算M=y2/y1=Mk/gk=Mgk/gkmodp(4)安全性：本体制基于Zp*中有限群上的离散对数的困难性。ElGamal密码体制45Rabin加密体制1979年Rabin利用合数模下求解平方根的困难性构造了一种安全公钥体制。令p和q是两个素数(私钥)，在模4下与3同余，以n=pq为公钥。加密：设M为待加密消息，计算密文C=M2modn，0Mn解密：计算M1=C(p+1)/4modnM2=p－C(p+1)/4modnM