1、1基本概念n密码学的用途:解决难题.n密码学解决的难题围绕的安全需求:机密性、完整性、认证性、不可否认性、公平性 n加密方案:密钥产生算法,加密算法(不一定是确定性算法),解密算法2明文明文密文加密算法解密算法密钥密钥加密与解密加密和解密算法的操作通常都是在一组密钥的控制下进行的,分别称为加密密钥(Encryption Key)和解密密钥(Decryption Key).3加密通信模型4密钥的必要性n攻击者总能设法找到算法.除非你就是个密码学家,并开发了自己的算法,否则你就必须相信开发出算法的公司不会将算法有意无意地泄露.n公开的算法更安全.算法公开后,密码分析者和计算机工程师就有了检验它弱点
2、的机会.5密码算法分类n对称密码体制:(私钥密码体制,秘密密钥密码体制）加密密钥和解密密钥相同,或实质上等同,即从一个容易推出另一个.n非对称密码体制:（公钥密码体制）加密密钥和解密密钥不相同,从一个很难推出另一个.加密密钥可以公开,称为公钥,解密密钥必须保密,称为私钥.6密码分析n唯密文攻击n已知明文攻击n选择明文攻击:例如公钥密码体制n选择密文攻击7安全的密码体制具有的性质n从密文恢复明文应该是难的，即使分析者知道明文空间（如明文是英语）。n从密文计算出明文部分信息应该是难的。n从密文探测出简单却有用的事实应该是难的，如相同的明文信息被加密发送了两次。8攻击结果n完全攻破:敌手找到了相应的
3、密钥n部分攻破:敌手没有找到相应的密钥，但对于给定的密文，敌手能够获得明文的特定信息。n密文识别:如对于两个给定的不同明文及其中一个明文的密文，敌手能够识别出该密文对应于哪个明文；或者能够识别出给定明文的密文和随机字符串。如果一个密码体制使得敌手不能在多项式时间内识别密文，这样的密码体制称为达到了语义安全（semantic security）。9密码体制的安全性n无条件安全性:如果密码分析者具有无限的计算能力，密码体制也不能被攻破,One-time Pad n计算安全性:如果攻破一个密码体制的最好的算法用现在或将来可得到的资源都不能在足够长的时间内破译.目前还没有任何一个实际的密码体制被证明是
4、计算上安全的.密码体制对某一种类型的攻击（如蛮力攻击）是计算上安全的，但对其他类型的攻击可能是计算上不安全的10密码体制的安全性n可证明安全性:把密码体制的安全性归结为某个经过深入研究的数学难题。例如如果给定的密码体制是可以破解的，那么就存在一种有效的方法解决大数的因子分解问题，而因子分解问题目前不存在有效的解决方法，于是称该密码体制是可证明安全的，即可证明攻破该密码体制比解决大数因子分解问题更难。可证明安全性只是说明密码体制的安全与一个问题是相关的，并没有证明密码体制是安全的，可证明安全性也有时候被称为归约安全性。11数论中的难题n离散对数问题离散对数问题:指给定有限循环群G，G 的生成元g
5、，元素a G，求logg a(求x满足a=g x)。n表示问题表示问题:给定阶为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.nxxxnaggg12数论中的难题nDiffie-Hellman问题问题n计算Diffie-Hellman(CDH)问题是指给定有限循环群G，G的生成元g，元素gu、gv G，求g uv G。n判定Diffie-Hellman(DDH)问题是指给
6、定有限循环群G，G的生成元g，元素gu、gv、gw G，判定gw=guv是否成立。13数论中的难题n强强Diffie-Hellman问题问题nG为阶p的有限循环群，g G是G的生成元，给定g，gx，G，求元组(c，g 1/(x+c)G。n大数分解问题大数分解问题n大数分解问题是指给定正整数n，找出它的因数分解。即求出素数p1，pk和整数e1，ek使得n=p1e1 pkek2xg（）qxg（）14数论中的难题nRSA问题问题nn是两个大素数的乘积n=p q，gcd(e，(n)=1，a Zn*，求b Zn*满足be=a(mod n)。n强强RSA问题问题nn是两个大素数的乘积n=pq，a Zn*，
7、求b、e Zn*满足b e=a(mod n)。15伪随机序列n不可预测性不可预测性:敌对者获得伪随机序列y部分位的信息不应能预测到y其他位的信息与种子x的信息 n随机性随机性:满足随机性统计检验。常用的统计检验包括：若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。16用于加密和解密的密钥是一样的或相互容易推出用于加密和解密的密钥是一样的或相互容易推出。Key A加密加密B解密解密明文明文明文明文密文
8、密文对称密码体制17 种类种类 序列密码序列密码(流密码流密码):将明文消息按字符位地加密将明文消息按字符位地加密分组密码分组密码:将明文消息分组将明文消息分组(每组含有多个字符每组含有多个字符)，逐组地进行加密逐组地进行加密 18分组密码n将明文分成m个明文块x=(x1，x2，xm)。每一组明文在密钥k=(k1，k2，kt)的控制下变换成n个密文块y=(y1，y2，ym)，每组明文用同一个密钥k 加密。n优点:容易标准化,容易实现同步n缺点:不能隐蔽数据模式。即相同的密文组蕴含着相同的明文组;不能抵抗组的重放、嵌入和删除等攻击;密钥管理困难nDES,AES,IDEA19分组密码的操作模式n电
9、子密码本ECB n密码分组链接CBC n密码反馈CFBn输出反馈OFBn计数模式CTR20ECBx1x2x3x4y4y3y2y1DESDESDESDES21ECB 剪切粘贴(Cut and Paste)攻击n假设明文是 Alice digs Bob.Trudy digs Tom.n假设64位的明文块和8位的ASCII:P0=“Alice di”,P1=“gs Bob.”,P2=“Trudy di”,P3=“gs Tom.”n密文:C0,C1,C2,C3nTrudy 剪切并粘贴:C0,C3,C2,C1n解密Alice digs Tom.Trudy digs Bob.22ECB 的缺陷n假设 Pi
10、=Pjn那么 Ci=Cj，Trudy 就知道了 Pi=Pjn即使T不知道Pi 或 Pj，他也了解了一些信息nTrudy 可能知道 Pin这是一个严重的问题吗?23Alice 讨厌 ECB 的模式nAlice的压缩图像,Alice 用ECB的方式加密(TEA)n为什么会这样?n同样的明文块 同样的密文!24CBCx1+IVx2x3x4y4y3y2y1DESDESDESDES25Alice 喜欢 CBC 的模式nAlice的压缩图像,Alice 用CBC的方式加密(TEA)n为什么会这样?n相同的明文不同的密文26CFB IVeKeKy1+x1eKx2y2+27OFB IVeKeKy1+x1x2y
11、2+28计数器模式xi-1xixi+1Yi-1ctr+i-1YiYi+1eKeKctr+ictr+i+1eK29公钥密码n加密/解密：发送方用接收方的公开密钥加密报文n数字签名：发送方用自己的私有密钥签署报文。n密钥交换：两方合作以便交换会话密钥30将一个定义域映射到一个值域，使得每个函数值有一个唯一的原像。Y=f(X)容易 X=f-1(Y)不可行单向函数n单向陷门函数单向陷门函数n单向散列函数单向散列函数31单向陷门函数 Y =fk(X)容易，知道k 和X X =fk-1(Y)容易，知道k 和Y X =fk-1(Y)不可行，知道Y 不知道k一个实用的公开密钥方案的发展依赖于找到一个单向陷门函
12、数。32公钥密码体制的安全性n是指计算上的安全性n安全性的理论基础：复杂性理论n一个算法的复杂性由该算法所需求的最大时间（T）和存储空间（S）度量。由于算法用于同一问题的不同规模实例所需求的时间和空间往往不同，所以总是将他们表示成问题实例的规模n的函数，n表示描述该实例所需的输入数据长度。33公钥密码体制的安全性n一个密码系统的保密性依赖于它所依赖的问题的计算复杂性，但是以计算上困难的问题为基础，却不一定导致一个保密性很强的密码系统 34公钥密码体制的安全性n（1）计算复杂性理论通常分析一个问题的一个孤立的事例，但在密码分析时往往需要解决许多统计上相关的问题，例如，破译由同一个加密密钥生成的几
13、段密文。n（2）计算复杂性理论通常做的是最坏情形的度量，一个多项式时间内不可解的困难问题，完全有可能对其中大多数事例是多项式时间可解的。然而，一个对大多数事例是信息容易破解的密码系统却是毫无用处的。n（3）计算复杂性理论对问题的难易分类时，通常只考虑是否存在确定的多项式时间算法。但是，一个可以通过某个概率多项式时间算法以很高的概率攻破的公开密钥密码系统，即使不存在确定的多项式时间算法去攻破它，也同样是没有用途的 35公钥密码分析n公钥体制可能受到强行攻击。防范措施：长密钥。但从实用性角度，要考虑折衷。n另一种形式的攻击是找到某种根据公钥计算私钥的方法。目前为止，对于一个特定的公钥算法，尚未从数
14、学上证明这种攻击不可能n有一种形式上的攻击对公钥系统是特有的。假设发送的报文仅仅含有一个56比特的DES密钥。敌对方可以用公钥加密所有的可能密钥，然后匹配。因而无论密钥方案的密钥大小是多少，攻击都归结为对56bit密钥的强行攻击。36基于大整数因子分解问题的，比如RSA体制、Rabin体制基于离散对数问题的，比如ElGamal体制、椭圆曲线密码体制ECC、Diffie-Hellman密钥交换 主要公钥密码体制37公钥密码经典算法nRSA算法nDiffie-Hellman 密钥交换算法nElGamal加密算法nRabin加密算法38RSA算法 n（1）取两个随机大素数p和q（保密）n（2）计算公
15、开的模数n=pq(公开)n（3）计算秘密的欧拉函数(n)=（p-1）(q-1)（保密）n（4）随机选取整数e，满足gcd(e,(n)=1(公开e，加密密钥)n（5）计算d，满足de1(mod(n)(保密d，解密密钥，陷门信息)n（6）加密:y=xe(mod n)n（7）解密:x=yd(mod n)39RSA加密标准OAEP DB=lHashPSMseed00MGFMGFEM=00maskedSeedmaskedDB40Diffie-Hellman密钥交换算法的数学基础41Diffie-Hellman密钥交换算法n全局公开量:n大素数 qng q且是q的本原根n用户密钥的产生（比如A）n选择随机
16、数:xA q n计算公开量:yA=gxA mod qn 产生密钥（比如A）nKAB=yAxB mod q =yBxA mod q =gxA.xB mod q42n ElGamal密码体制：由ElGamal1984,1985提出，是一种基于离散对数问题的双钥密码体制，既可用于加密，又可用于签字。（1）方案：Zp:p个元素的有限域 p:一个大素数 g：是Zp*(Zp中除去0元素)中的一个本原元或其生成元 明文集M：Zp*密文集C：Zp*Zp*。公钥：选定g(g p的生成元)，计算公钥 g mod p 秘密钥：p ElGamal密码体制密码体制43ElGamal密码体制密码体制(2)加密：选择随机数
17、kZp-1，且(k,p1)=1，计算：y1=g k mod p(随机数k被加密)y2=M k mod p(明文被随机数k和公钥加密)M 是发送明文组。密文由y1、y2级连构成，即密文C=y1|y2。44 特点特点：密文由明文和所选随机数k来定，因而是非确定性加密，一般称之为随机化加密，对同一明文由于不同时刻的随机数k不同而给出不同的密文。代价是使数据扩展一倍。(3)解密：收到密文组C后，计算 M=y2/y1=M k/gk=Mgk/gk mod p (4)安全性：本体制基于Zp*中有限群上的离散对数的困难性。ElGamal密码体制密码体制45Rabin加密体制n 1979年Rabin利用合数模下
18、求解平方根的困难性构造了一种安全公钥体制。令p和q是两个素数，在模4下与3同余，以n=pq为公钥。加密加密：设M为待加密消息，计算密文C=M2 mod n，0Mn 解密解密：计算 M1=C(p+1)/4 mod n M2=pC(p+1)/4 mod n M3=C(q+1)/4 mod n M4=qC(q+1)/4 mod n 其中必有一个与M相同，若M是文字消息则易于识别；若M是随机数字流，则无法确定哪一个Mi是正确的消息。n 安全性安全性：等价于分解大整数。46散列函数 Hash Function Hash函数用于封装或数字签名过程之中，需具有下列特性：1）函数必须是真正单向的，即对一个给定
19、的消息摘要，构造一个输入消息将其映射为该消息摘要是计算上不可行的；2）构造两个不同的消息将它们映射为同一个消息摘要必须是计算上不可行的。（无碰撞）difficultxxfeasyxfx:)(:)(difficultxfxf:)()(2147几种重要的散列算法n系列Hash函数，例如MD2,MD4和MD5。这些函数都产生128比特输出。MD4的速度更快一些，特别是在32比特处理器中更快一些。MD5比MD4慢一些，并且人们认为MD5较弱一些。n美国政府的安全Hash标准（SHA-1）。SHA-1是MD4的一个变形，产生160比特的输出，与DSA算法匹配使用。n常见的散列算法有MD5、SHA-1、S
20、HA-2、SHA-3、SM3等等消息认证n消息认证就是认证消息的完整性，当接收方收到发送方的消息时，接收方能够验证收到的消息是真实的和未被篡改的n它包含两层含义：一是验证信息的发送者是真正的而不是冒充的，即数据起源认证；二是验证信息在传送过程中未被篡改、重放或延迟等 消息认证n一个消息认证方案是一个三元组(K,T,V)：n（1）密钥生成算法K。K是一个生成密钥k的随机函数。n（2）标签算法T。由密钥k及消息M生成标签=Tk(M)。n（3）验证算法V。由密钥k、消息M、标签验证是否保持了数据完整性，输出1位d，d=Vk(M,)。我们要求对于明文空间中的所有消息M满足：当=Tk(M)时，Vk(M,
21、)=1，否则Vk(M,)=0。消息认证码(MAC)起点(K)目的地(K)消息 my=hk(m)检查y=hk(m)m,tag y消息认证码（Message Authentication Code，MAC）采用共享密钥，是一种广泛使用的消息认证技术。消息认证码(MAC)n发送方A要发送消息M时，使用一个双方共享的密钥k产生一个短小的定长数据块，即消息认证码MAC=Tk(M)，发送给接收方B时，将它附加在消息中。这个过程可以表示为A B:M|Tk(M)。n接收方对收到的消息使用相同的密钥k执行相同的计算，得到新的MAC。n接收方将收到的MAC与计算得到的MAC进行比较，如果相匹配，那么可以保证消息的
22、传输过程中保持了完整性。52消息认证码(MAC)nOscar(攻击者)的目的:n构造一对有效的(x,y),但他不知道密钥knOscar 所知道的n有效对 Pairs=(x1,y1),(x2,y2),.,(xq,yq)n伪造nOscar 输出一对(x,y)，其中 x 并不在所知的有效对中53构造MAC的方法n利用已有的分组密码构造，如利用DES构造的CBC-MAC n利用已有的Hash函数构造，因为Hash函数并不依赖一个密钥，所以不能直接用于MAC n已有许多将一个密钥与一个现有的Hash函数结合起来的提议，HMAC就是获得众多支持的一种 n创建一个自定义的MAC 54HMACn嵌套MAC算法
23、 n基于 SHA-1n使用 512bit的密钥 kn2个512-bit 常数，ipad 和 opadn160-bit MACnHMACk(M)=SHA-1(k+opad)|SHA-1(k+ipad)|M5556CBC MACx1+IVx2x3x4y4y3y2y1DESDESDESDES57CBC MACn分组密码的工作模式：CBCn固定IVn最常见的攻击是生日攻击58数字签名 n签名方案是一个满足下列条件的五元组（P,A,K,S,V）：nP是所有可能的消息组成的有限集。nA是所有可能的签名组成的有限集。nK是所有可能的密钥组成的有限集。n对每一个kK，有一个签名算法SkS和一个相应的验证算法V
24、kV。对每一个消息xP和每一个签名yA，每一个签名算法Sk：PA和验证算法Vk：PA0,1满足：当y=Sk(x)时，Vk(x,y)=1，否则Vk(x,y)=0。59数字签名 n安全性要求：不可伪造n公钥算法的效率是相当低的，不易用于长文件的加密，为此我们采用Hash函数，将原文件x通过一个单向的Hash函数作用，生成相当短的输出H，即Hash（x）=H。n然后再将公钥算法作用在H上生成签名y，记为Sk1（H）=y，k1为A的私钥，A将x|y传给BnB收到x|y后，需要验证y是否为A的签名，即验证Vk2(x,y)是否为1。60RSA数字签名 n签名者取两个随机大素数p和q（保密），计算公开的模数
25、n=pq(公开)，计算秘密的欧拉函数(n)=（p-1）(q-1)（保密）。n随机选取整数e，满足gcd(e,(n)=1(公开e，验证密钥)n计算d，满足de1(mod(n)(签名密钥)n签名:y=H(x)d(mod n),把x|y发送给验证者n验证:检查下式是否成立yd=H(x)(mod n).61RSA数字签名 yeH(x)d比较消息x消息xy消息xyHH(x)ye62RSA签名标准PSS bc padding2 maskedDB M M padding1 mHash salt salt H MGF M=DB=EM=a Hash Hash 63EIGamal签名方案n该方案是特别为签名的目的
26、而设计的。1985年提出，很大程度上为Diffie-Hellman密钥交换算法的推广和变形。这个方案的改进已被美国NIST（国家标准和技术研究所）采纳作为数字签名标准。方案的安全性依赖于求离散对数的困难性。64n公钥：p:素数，gp（p,g可由一组用户共享）y=gx(mod p)n私钥：xpn签名：k:随机选取，与p-1互素，na（签名）=g k mod p，nb（签名）满足 M=(xa+kb)mod(p-1)(即有：b=(M-xa)k-1 mod(p-1)n验证：如果 ya ab(mod p)=gM(mod p)，则签名有效。EIGamal签名方案65n全局公钥（p，q，g）np为51210
27、24bit的大素数，nq是（p1）的素因子，为160比特的素数，ng:=h(p-1)/q mod p,且1h1n用户私钥x：x为0 xq内的随机数n用户公钥y：y=gx mod p数字签名标准数字签名标准DSS66n用户每个消息用的秘密随机数k：0kq;n签名过程：对报文M，签名为（r，s）nr=(gk mod p)mod qns=(k-1(H(M)+xr)mod qn验证：nw s-1 mod q na=(H(M)w)mod q b=rw mod qnv=(ga,yb)mod p)mod qnVer（M，r，s）真 if v=r数字签名标准数字签名标准DSS67Schnorr签名 n令待签消
28、息为M，对给定的M做下述运算：n任选一秘密随机数kZqn计算签名S=(e,s)nr gk mod pns k-xe mod qn式中e=H(r|M)。n验证签名S=(e,s)nr gs ye mod p而后计算H(r|M)。n验证H(r|M)=e Okamoto签名体制签名体制(1)体制参数p：大素数，且p 2512；q：大素数，q|(p 1)，且q 2512；g1、g2：两个与q同长的随机数；x1、x2：用户A的私钥，两个小于q的随机数；y：用户A的公钥，(mod p)Okamoto签名体制签名体制n(2)签名的产生过程n对于待签名的消息m，A执行一下步骤：n选择两个小于q的随机数k1、k2
29、 RZq*；n计算杂凑值：e=H(,m)；n计算：s1=(k1+e x1)(mod q)；n计算：s2=(k2+e x2)(mod q)；n以(e,s1,s2)作为对m的数字签名 1212(mod)kkg gpOkamoto签名体制签名体制n收方在收到消息m和数字签名(e,s1,s2)后，通过一下步骤来验证签名的有效性：n计算 ；n计算e=H(v,m)；n验证：Ver(y,(e,s1,s2),m)=True e=e；n其正确性可通过下式证明 1212(mod)xxev g g yp121122121212121212(mod)(mod)(mod)ssk exkexexexkkev g g yp
30、ggggpg gp基于椭圆曲线的数字签名算法基于椭圆曲线的数字签名算法ECDSA n椭圆曲线数字签名算法（ECDSA：Elliptic Curve Digital Signature Algorthm）和RSA与DSA的功能相同，并且数字签名的产生与验证速度要比RSA和DSA快 基于椭圆曲线的数字签名算法基于椭圆曲线的数字签名算法ECDSA n设待签的消息为m；全局参数D=(q,FR,a,b,G,n,h)，还有签名者的公钥私钥对(Q,d)。n签名的算法步骤描述如下：(1)选择一个随机数k，k 1,n 1；(2)计算k G=(x1,y1)；(3)计算r=x1 mod n；如果r=0，则回到步骤(
31、1)；(4)计算k 1 mod n；(5)计算e=SHA1(m)；(6)计算s=k 1(e+d r)mod n，如果s=0，则回到步骤(1)；(7)对消息的签名为(r,s)。n最后签名者就可以把消息m和签名(r,s)发送给接收者 基于椭圆曲线的数字签名算法基于椭圆曲线的数字签名算法ECDSAn当接收者收到消息m和签名(r,s)之后，验证消息签名的有效性，需要取得如下参数：全局参数D=(q,FR,a,b,G,n,h)，发送者的公钥Q。n验证算法可以描述如下：(1)检验r、s，要求r、s 1,n 1；(2)计算e=SHA1(m)；(3)计算w=s1 mod n；(4)计算u1=e w mod n；
32、u2=r w mod n；(5)计算X=u1 G+u2 Q；(6)如果X=0，表示签名无效；否则，X=(x1,y1)，计算v=x1 mod n；(7)如果v=r，表示签名有效；否则表示签名无效。74数字证书n证明公钥/属性的真实性n证书类型：n1）X.509公钥证书n2）简单PKI 证书n3）PGP（Pretty Good Privacy）证书n4）属性（Attribute）证书n5）代理证书等75nITU-T X.509标准 版本V3序列号1234567890签名算法标识（算法、参数）RSA 和 MD5签发者c=CN，o=JIT-CA有效期（起始日期、结束日期）01/08/00-01/08/
33、07主体c=CN，o=SX Corp，cn=John Doe主体公钥信息（算法、参数、公开密钥）56af8dc3a4a785d6ff4/RSA/SHA发证者唯一标识符Value主体唯一标识符Value类型关键程度Value类型ValueCA的数字签名76证书认证系统n资料审核n证书颁发n证书查询n证书作废基于身份的密码系统与基于基于身份的密码系统与基于PKI的的密码系统的比较密码系统的比较 n参数的真实性（Authenticity of system parameters）n注册（Registration at the authority）n密钥托管（Key escrow）n密钥撤销和更新（Key revocation and key rollover）n密钥发布（Key distribution）n主密钥安全性（Master-key security）n规模化（Scalability）n商业成熟度（Commercial maturity）
