密码学基础资料课件

密码学基础刘昆中国矿业大学徐海学院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，…，gnG，求元素a

G对应于(g1，…，gn)的一个表示。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的有限循环群，gG是G的生成元，给定g，gx，，…，

G，求元组(c，g1/(x+c))G。大数分解问题大数分解问题是指给定正整数n，找出它的因数分解。即求出素数p1，…，pk和整数e1，…，ek使得n=p1e1…pkek15数论中的难题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

用于加密和解密的密钥是一样的或相互容易推出。

Key

A加密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,C3Trudy剪切并粘贴: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)为什么会这样?相同的明文不同的密文27CFB

IVeKeKy1

+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和X

X=fk-1(Y)容易，知道k

和Y

X=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，解密密钥，陷门信息)（6）加密:y=xe(modn)（7）解密:x=yd(modn)40RSA加密标准OAEPDB=lHashPSMseed00MGFMGFEM=00maskedSeedmaskedDB41Diffie-Hellman密钥交换算法的数学基础42Diffie-Hellman密钥交换算法全局公开量:大素数qg<q且是q的本原根用户密钥的产生（比如A）选择随机数:xA<q计算公开量:yA=gxAmodq

产生密钥（比如A）KAB=yAxBmodq=yBxAmodq=gxA.xBmodq43

ElGamal密码体制：由ElGamal[1984,1985]提出，是一种基于离散对数问题的双钥密码体制，既可用于加密，又可用于签字。（1）方案：

Zp:p个元素的有限域p:一个大素数

g：是Zp*(Zp中除去0元素)中的一个本原元或其生成元明文集M：Zp*

密文集C：Zp*×Zp*。公钥：选定g(g<p的生成元)，计算公钥gmodp

秘密钥：<p

ElGamal密码体制44ElGamal密码体制(2)加密：选择随机数kZp-1，且(k,p－1)=1，

计算： y1=g

kmodp(随机数k被加密) y2=Mkmodp(明文被随机数k和公钥加密)

M是发送明文组。

密文由y1、y2级连构成，即密文C=y1||y2。45

特点：密文由明文和所选随机数k来定，因而是非确定性加密，一般称之为随机化加密，对同一明文由于不同时刻的随机数k不同而给出不同的密文。代价是使数据扩展一倍。

(3)解密：收到密文组C后，计算

M=y2/y1=Mk/gk=Mgk/gkmodp(4)安全性：本体制基于Zp*中有限群上的离散对数的困难性。ElGamal密码体制46Rabin加密体制1979年Rabin利用合数模下求解平方根的困难性构造了一种安全公钥体制。令p和q是两个素数，在模4下与3同余，以n=pq为公钥。加密：设M为待加密消息，计算密文C=M2modn，0M<n

解密：计算M1=C(p+1)/4modnM2=p－C(p+1)/4modnM3=C(q+1)/4modnM4=q－C(q+1)/4modn

其中必有一个与M相同，若M是文字消息则易于识别；若M是随机数字流，则无法确定哪一个Mi是正确的消息。安全性：等价于分解大整数。47散列函数

HashFunction

Hash函数用于封装或数字签名过程之中，需具有下列特性：

1）函数必须是真正单向的，即对一个给定的消息摘要，构造一个输入消息将其映射为该消息摘要是计算上不可行的；

2）构造两个不同的消息将它们映射为同一个消息摘要必须是计算上不可行的。（无碰撞）48几种重要的散列算法系列Hash函数，例如MD2,MD4和MD5。这些函数都产生128比特输出。MD4的速度更快一些，特别是在32比特处理器中更快一些。MD5比MD4慢一些，并且人们认为MD5较弱一些。

美国政府的安全Hash标准（SHA-1）。SHA-1是MD4的一个变形，产生160比特的输出，与DSA算法匹配使用。消息认证消息认证就是认证消息的完整性，当接收方收到发送方的消息时，接收方能够验证收到的消息是真实的和未被篡改的它包含两层含义：一是验证信息的发送者是真正的而不是冒充的，即数据起源认证；二是验证信息在传送过程中未被篡改、重放或延迟等消息认证一个消息认证方案是一个三元组(K,T,V)：（1）密钥生成算法K。K是一个生成密钥k的随机函数。（2）标签算法T。由密钥k及消息M生成标签δ=Tk(M)。（3）验证算法V。由密钥k、消息M、标签δ验证是否保持了数据完整性，输出1位d，d=Vk

(M,δ)。我们要求对于明文空间中的所有消息M满足：当δ=Tk

(M)时，Vk

(M,δ)=1，否则Vk

(M,δ)=0。消息认证码(MAC)起点(K)目的地(K)消息my=hk(m)检查y=hk(m)m,tag

y消息认证码（MessageAuthenticationCode，MAC）采用共享密钥，是一种广泛使用的消息认证技术。消息认证码(MAC)发送方A要发送消息M时，使用一个双方共享的密钥k产生一个短小的定长数据块，即消息认证码MAC=Tk(M)，发送给接收方B时，将它附加在消息中。这个过程可以表示为AB:M||Tk(M)。接收方对收到的消息使用相同的密钥k执行相同的计算，得到新的MAC。接收方将收到的MAC与计算得到的MAC进行比较，如果相匹配，那么可以保证消息的传输过程中保持了完整性。53消息认证码(MAC)Oscar(攻击者)的目的:构造一对有效的(x,y),但他不知道密钥kOscar所知道的有效对Pairs={(x1,y1),(x2,y2),...,(xq,yq)} 伪造Oscar输出一对(x,y)，其中x

并不在所知的有效对中54构造MAC的方法利用已有的分组密码构造，如利用DES构造的CBC-MAC利用已有的Hash函数构造，因为Hash函数并不依赖一个密钥，所以不能直接用于MAC已有许多将一个密钥与一个现有的Hash函数结合起来的提议，HMAC就是获得众多支持的一种创建一个自定义的MAC55HMAC嵌套MAC算法基于SHA-1使用512bit的密钥k2个512-bit常数，ipad和opad160-bitMACHMACk(M)=SHA-1[(k+

opad)||SHA-1[(k+ipad)||M]]5657CBCMACx1++++IVx2x3x4y4y3y2y1DESDESDESDES58CBCMAC分组密码的工作模式：CBC固定IV最常见的攻击是生日攻击59数字签名签名方案是一个满足下列条件的五元组（P,A,K,S,V）：P是所有可能的消息组成的有限集。A是所有可能的签名组成的有限集。K是所有可能的密钥组成的有限集。对每一个kK，有一个签名算法SkS和一个相应的验证算法VkV。对每一个消息xP和每一个签名yA，每一个签名算法Sk：PA和验证算法Vk：PA{0,1}满足：当y=Sk(x)时，Vk(x,y)=1，否则Vk(x,y)=0。60数字签名安全性要求：不可伪造公钥算法的效率是相当低的，不易用于长文件的加密，为此我们采用Hash函数，将原文件x通过一个单向的Hash函数作用，生成相当短的输出H，即Hash（x）=H。然后再将公钥算法作用在H上生成签名y，记为Sk1（H）=y，k1为A的私钥，A将x||y传给BB收到x||y后，需要验证y是否为A的签名，即验证Vk2(x,y)是否为1。61RSA数字签名签名者取两个随机大素数p和q（保密），计算公开的模数n=pq(公开)，计算秘密的欧拉函数(n)=（p-1）(q-1)（保密）。随机选取整数e，满足gcd(e,(n))=1(公开e，验证密钥)计算d，满足de≡1(mod(n))(签名密钥)签名:y=H(x)d(modn),把x||y发送给验证者验证:检查下式是否成立ye=H(x)(modn).62RSA数字签名yeH(x)d比较消息x消息xy消息xyHH(x)ye63RSA签名标准PSS

64EIGamal签名方案该方案是特别为签名的目的而设计的。1985年提出，很大程度上为Diffie-Hellman密钥交换算法的推广和变形。这个方案的改进已被美国NIST（国家标准和技术研究所）采纳作为数字签名标准。方案的安全性依赖于求离散对数的困难性。65公钥：p:素数，

g<p（p,g可由一组用户共享）

y=gx(modp)私钥：x<p签名：k:随机选取，与p-1互素，a（签名）=gkmodp，b（签名）满足

M=(xa+kb)mod(p-1)(即有：b=(M-xa)k-1mod(p-1))验证：如果yaab(modp)=gM(modp)，则签名有效。EIGamal签名方案66全局公钥（p，q，g）p为512～1024bit的大素数，q是（p－1）的素因子，为160比特的素数，g:=h(p-1)/qmodp,且1<h<(p-1),使得h(p-1)/qmodp>1用户私钥x：x为0<x<q内的随机数用户公钥y：y=gxmodp数字签名标准DSS67用户每个消息用的秘密随机数k：0<k<q;签名过程：对报文M，签名为（r，s）r=(gkmodp)modqs=(k-1(H(M)+xr))modq验证：w＝s-1modqa=(H(M)w)modqb=rwmodqv=((ga,yb)modp)modqVer（M，r，s）＝真ifv=r数字签名标准DSS68Schnorr签名令待签消息为M，对给定的M做下述运算：任选一秘密随机数k∈Zq计算签名S=(e,s)r≡gk

modpsk-xemodq式中e=H(r||M)。验证签名S=(e,s)r’≡gsyemodp而后计算H(r’||M)。验证H(r’||M)=eOkamoto签名体制(1)体制参数p：大素数，且p

2512；q：大素数，q|(p

1)，且q

2512；g1、g2：两个与q同长的随机数；x1、x2：用户A的私钥，两个小于q的随机数；y：用户A的公钥，(modp)Okamoto签名体制(2)签名的产生过程对于待签名的消息m，A执行一下步骤：选择两个小于q的随机数k1、k2

RZq*；计算杂凑值：e=H(,m)；计算：s1=(k1+ex1)(modq)；计算：s2=(k2+ex2)(modq)；以(e,s1,s2)作为对m的数字签名Okamoto签名体制收方在收到消息m和数字签名(e,s1,s2)后，通过一下步骤来验证签名的有效性：计算；计算e’=H(v,m)；验证：Ver(y,(e,s1,s2),m)=True

e’=e；其正确性可通过下式证明基于椭圆曲线的数字签名算法ECDSA

椭圆曲线数字签名算法（ECDSA：EllipticCurveDigitalSignatureAlgorthm）和RSA与DSA的功能相同，并且数字签名的产生与验证速度要比RSA和DSA快基于椭圆曲线的数字签名算法ECDSA

设待签的消息为m；全局参数D=(q,FR,a,b,G,n,h)，还有签名者的公钥私钥对(Q,d)。签名的算法步骤描述如下：(1)选择一个随机数k，k[1,n

1]；(2)计算kG=(x1,y1)；(3)计算r=x1modn；如果r=0，则回到步骤