密码学课件 公开密钥密码

密码学导论IntroductiontoCryptology主讲教师：李卫海、胡红钢第8章公开密钥密码公开密钥密码RSA密码其它公钥密码ElGamal密码椭圆曲线密码公开密钥密码RSA密码其它公钥密码ElGamal密码椭圆曲线密码单向函数举例公开密钥密码的设计关键：将单向函数构造为单向陷门函数因数分解问题(IntegerFactorization)给定大素数p和q，求n=p×q,只要一次乘法给定n，求p和q，即为因数分解问题IF，最快方法需要T(n)=exp{c((lnn)1/3ln(lnn))2/3}次运算，其中c为大于1的正整数。离散对数问题(DiscreteLogarithmProblem)令素数p满足p-1含有另一大质数q(q整除p-1)，及一整数g,1<g<p-1。若给定整数x，求y=gxmodp是简单的但是若给定p,g及y，求x，则为DLP问题，是困难的。背包问题(KnapsackProblem)给定有限个自然数序列集合B=(b1,b2,…bn)及二进制序列x=(x1,x2,…xn),xi∈(0,1),求S＝∑xibi最多只需n-1次加法；但若给定B和S，求x则非常困难。穷举时有2n种可能，当n很大时为计算上不可行。RSA设计思路1977年，Rivest、Shamir、Adleman基于大数分解难题，提出RSA密码体制RSA专利于2000年9月20日到期RSA算法满足公开密钥加密的要求，基本思路：找到适当的e,d,n，使得对所有m<n有medmodn=m对于所有m<n的值，要计算me和Cd是相对容易的在给定e和n时，计算出d是不可行的算法依据mp-1modp=1，mk(p-1)+1modp=med=k(p-1)+1?ed=1mod(p-1)p必须公开，由e计算d是容易的。不满足公开密钥条件mΦ(n)modn=1，mkΦ(n)+1modn=med=kΦ(n)+1?ed=1modΦ(n)n是公开的，但将n分解并计算Φ(n)是困难的RSA算法流程随机选择两个秘密大质数p和q计算公开模数n=p*q计算秘密的欧拉指数函数Φ(n)=(p-1)(q-1)选择一个与Φ(n)互素的数，作为e计算e模Φ(n)的乘法逆元素，作为d公开密钥PU={e,n}；私有密钥PR={d,n}加密：C=memodn解密：m=Cdmodn=medmodn=m例：RSA，p=17,q=11,e=7，加密消息m=88并解密解：n=pq=17×11=187Φ(n)=(p-1)(q-1)=16×10=160gcd(7,160)=1,d=7-1mod

160=23公钥PU={7,187}，私钥PR={23,187}加密计算C=887mod187=11解密计算m=1123mod187=88实现方面的考虑前面已证明，当m是p或q的倍数时，仍可以正确加解密m不能是0、±1，否则密文就是明文（e必为奇数）加密与解密模指数运算，可通过下面两个手段减少运算量模运算特性[(amodn)op(bmodn)]modn=(aopb)modn快速指数算法公钥的有效运算e常选65537(即216+1)：仅有两个比特为1，乘法次数最小应用中也可以先选择e，再选择p,q。为保证gcd(e,Φ(n))=1，选择p,q时应保证gcd(e,p-1)=gcd(e,q-1)=1实现方面的考虑：小公钥的危险e有时也选3或17。但过小的e可能受到攻击例如：假设有三个用户的e都选择3，但模数分别为n1,n2,n3若要向他们发送m，密文分别为

C1=m3

modn1,C2=m3modn2,C3=m3modn3各用户的素数是随机生成的，因此模数n1,n2,n3两两互素的可能很大由中国剩余定理可以计算C=CRT(n1,n2,n3,C1,C2,C3)显然有C=m3modn1n2n3由RSA算法规则，m<ni，

因此m3<n1n2n3因而可以直接计算m=C1/3实现方面的考虑：共模攻击为简化问题，可能会给多个用户分配相同的n（p和q由密钥管理中心保管，不公开），但给不同用户分配不同的e和d若明文m用不同的公钥e1,e2加密，公共模数为n则密文c1=me1(modn),c2=me2(modn)不同用户的指数e往往是互素的，由扩展欧几里德算法可以找到r和s，满足re1+se2=1有c1r

c2s=mre1+se2=mr和s必有一个是负数，不妨设是r，则(c1-1)-r

c2s=m不应使用公共的模数n实现方面的考虑私钥d应不小于1/3n1/4若d<1/3n1/4，则可以用Wiener攻击在多项式时间内分解n“CryptanalysisofshortRSAsecretexponents”,1990私钥的有效运算运用中国剩余定理简化运算：求m=Cdmodn计算：Xp=q×(q-1modp),Xq=p×(p-1modq)定义：Vp=Cdmodp=Cdmod(p-1)modp Vq=Cdmodq=Cdmod(q-1)modq则m=CRT(n,p,q,Vp,Vq)=(VpXp+VqXq)modn比直接运算m=Cdmodn快4倍RSA的安全性四种潜在的攻击方法穷举攻击：尝试所有可能的密钥数学攻击：对两个素数乘积的因子分解(IF问题)计时攻击：依赖于解密算法的运行时间选择密文攻击：利用了RSA体制的性质数学攻击数学攻击：分解n为两个素数p,q，并进而求出d主要的大数分解算法二次筛选法一般数域筛选法对116位以上的大数分解比二次筛

选法快得多特殊数域筛选法分解一些特殊形式的数数学攻击RSA的安全性问题依赖于大合数的素因子分解，即FactorizationProblem(IF)2005年分解了200位十进制（约664bits）大合数2009年分解了232位十进制（768bits）大合数（数百台设备运行2年）p、q应选取1024或2048位数学攻击选择适当的大素数，避免被已知方法分解大素数应该是随机的，且不包含在素数表中查表或遍历特殊形式的素数总是容易的选择强素数，素数p应满足：p-1有一个大的素因子rp+1有一个大的素因子r-1有一个大的素因子p和q大小不能太接近否则p和q接近n1/2，容易被穷举攻击选择p和q在长度上有几个比特差异是可行的(p-1)和(q-1)都应有一个不相等的大素因子可能存在基于重复加密的攻击：ce,(ce)e,…若cet≡c

(modn)，则cet-1≡m(modn)，即met-1=m(modn)当(p-1)和(q-1)都有一个不相等的大素因子时，这种攻击可以忽略GCD(p-1,q-1)应该较小计时攻击计时攻击依据加密或解密算法对于不同输入所花的时间上的细微差别，进行分析类似通过观察转动老式电话拨号盘的时间长短来猜测密码可能的解决办法快速指数算法也会泄露部分信息不变的幂运行时间，可能会降低性能在求幂运算中加入随机延时干扰：在执行幂运算之前先将密文乘上一个随机数RSA数据安全公司在产品中实现M=Cdmodn的过程：产生0～n-1之间的秘密随机数s计算C'=C×(se)modn,e是公开的指数计算M'=(C')dmodn计算M=M's-1modn,其中s-1是r模n的乘法逆元通过s来干扰运算中的耗时，同一个密文解密时间也会发生变化明文分解的中间相遇攻击

选择密文攻击对RSA算法，有E(PU,M1)×E(PU,M2)=E(PU,M1×M2)若有密文C=Memodn，则攻击过程如下：选取随机数s计算X=(C×se)modn=(Ms)emodn诱使用户解密X，并返回Y=Xdmodn=(Ms)modn攻击者计算M=Ys-1

modn封装攻击：攻击者做为协议参与一方，将他所需要的消息封装为合法消息的一部分，诱使另一方解密、签名等。例如：“我用你的公钥加密了一个随机数，你解密发还给我，来证实你的身份”永远不要对一个陌生人提交的随机文件直接进行私钥运算（数字签名）可以在加密之前对明文随机填充最优非对称加密填充OAEP，使明文符合一定规则，解密后可以检验消息的合法性对于不符合格式的消息，拒绝给出解密结果乘法同态最优非对称加密填充M消息；L可选的标签公开密钥密码RSA密码其它公钥密码ElGamal密码椭圆曲线密码离散对数密码示例离散对数密码例：Pohlig-HellmanScheme加密：C=MemodP解密：M=Cd=(Me)dmodPedmodΦ(P)

=1，P为大素数，Φ(P)为欧拉函数因为P是素数，Φ(P)容易获得，因此e和d都需要保密显然，并非公开密钥密码ElGamal密码属于离散对数密码体制安全性基于DLP问题ElGamal密码算法公共模数素数P，本原元素α，私钥x，公钥Y=αxmodP加密，消息1≤m≤P-1：A随机选择k∈(1,P-1)A访问公共区域获取B的公钥YB=αxBmodP。计算： K=(YB)kmodP，即K=αxBkmodP c1=αkmodP，c2=mKmodP密文即为(c1,c2)解密：B首先恢复K：K=c1xBmodP=αkxBmodP然后恢复m：m=c2/KmodP=c2K-1modPElGamal密码体制是概率密码体制，相同明文每次加密得到不同的密文加密效率是50％，因为密文大小是明文的两倍例：P=17,α=3,xA=2,xB=5,AB:m=11公钥计算：YB=αxBmodP=35mod17=5加密：A选择k=7K=(YB)kmodP=57mod17=10c1=αkmodP=37mod17=11c2=mKmodP=11×10mod17=8所以，密文C=(c1,c2)=(11,8)解密：K=c1xBmodP=115mod17=10K-1modP=10-1mod17=12m=c2K-1modP=8×12mod17=11实现方面的考虑特别注意，k不能重复使用，如果 (1)c1,1=αkmodP c2,1=m1KmodP (2)c1,2=αkmodP c2,2=m2KmodP

得m1/m2=c2,1/c2,2modP

如果m1已知，m2即可算出公开密钥密码RSA密码其它公钥密码ElGamal密码椭圆曲线密码椭圆曲线密码ECCECC与RSA的对比ECC中的加法运算与RSA中的乘法运算相对应ECC中的数乘运算与RSA中的模幂运算相对应同等密码强度下，ECC所需密钥量和计算量都小于RSA算法同等密钥长度下，ECC计算量与RSA相当给定曲线y2=x3+ax+bmodp以及其上一点P，我们可以通过连续自加k-1次计算Q=kP存在与快速指数运算类似的快速算法问题：当Q已知时能否计算k?这是一个被称为椭圆曲线离散对数的难题“Pollardrho方法”是目前最快的方法椭圆曲线公钥系统椭圆曲线公钥密码系统域标识GF(p)：定义椭圆曲线采用的有限域椭圆曲线E(a,b)：系数a和b基准点(base)G：指定的椭圆曲线上的一点阶(order):G点的阶N，使得：NG=O选择正整数e作为私有密钥公开密钥为Q=eGMenozes-Vanstone椭圆曲线密码利用ECC实现加/解密的技术有多种Menozes-Vanstone是其中一种令E是GF(p)上的椭圆曲线，选取基点G，阶为N私钥：e<N公钥：E，GF(p)，Q=eG加密：明文m=(x1,x2)，x1,x2<p任取v<N，vQ=(c1,c2)密文(y0,y1,y2)，y0=vG,y1=c1x1

modp,y2=c2x2modp解密：用私钥e计算：ey0=evG=vQ=(c1,c2)m=(x1,x2)=(y1c1-1modp,y2c2-1modp)ElGamal算法在椭圆曲线上实现E(a,b)，基点G∈EB选择a并保密,0<a<N，N为G的阶(order)，公钥为aGA向B发送消息m:

A将m嵌入点Pm，选择随机数k,

AB(kG,Pm+k(aG))B：Pm=(Pm+k(aG))–a(kG)一种将消息m映射到点Pm的算法编码：将域p划分为长256的小段对明文进行分组：使得每个分组0≤m≤

p/256

对明文分组进行编码，使之成为由域参数给出的椭圆曲线上的点Pm在256m≤x<256(m+1)中找到一个x，使得椭圆曲线方程有解一般地，对所有的满足256m≤x<256(m+l)的x，椭圆曲线方程都无解的概率是很小的。从而可以完成编码。解码：若解密横坐标落在256m≤x<256(m+1)中，则解码为m0123402565127681024xmMassey-Omura公钥体制不需要交换公钥。GF(q)上用户A加密、解密密钥：eA,dA

gcd(eA,q-1)=1,eAdA=1mod(q-1)用户B加密、解密密钥：eB,dB

gcd(eB,q-1)=1,eBdB=1mod(q-1)A将消息m发送给BABmeAmeAeB(meAeB)dA=meBB:

(

meB)dB=mE(a,b)上m编码为椭圆曲线上的点PmN:椭圆曲线上的点数用户随机选择e:1<e<N,gcd(e,N)=1,ed=1modNA将消息m发送给B：A将m嵌入点PmABeAPmB:dB(eBPm)=PmeBeAPmdA(eBeAPm)=eBPm公开密钥密码RSA密码其它公钥密码ElGamal密码椭圆曲线密码Rabin密码人们相信破译RSA密码和大数分解问题同等困难，但缺乏严格的证明Rabin密码是第一个证明了的安全公钥加密方案破译它和大数分解问题同等困难密钥生成：随机生成两个不同但大小相近的大素数p和q计算n=pq（p和q模4余3时，利于计算）公钥为n，私钥为(p,q)加密：B为A加密消息将消息分组表示成{0,1,…,n-1}中的整数m，n是A的公钥计算c=m2modn作为密文解密：求解c的四个平方根从四个平方根中选取正确的一个Rabin密码的安全性安全性n的因子分解问题和计算模n的平方根在计算上是等价的，因此破译Rabin算法与大数分解是同等困难的不能抵抗选择密文攻击敌手随机选择x，计算c=x2modn提交c去正常解密，得到明文y此时有1/2的几率使得gcd(x+y,n)就是n的一个素因子冗余方案：加密前一般在m中嵌入冗余，据此从四个解中选择正确的解。若四个解中均无特定冗余，则拒绝返回答案使用冗余方案时的安全性：若敌手在x中嵌入了冗余，则解密器会以极大的概率返回x（其它三个平方根不大可能也碰巧具有该冗余）。此时破译攻击失败若敌手在x中不嵌入冗余，则解密器会以极大的概率拒绝接受密文。此时破译攻击失败可以抵抗选择密文攻击gcd(z1＋z1,n)=？gcd(z1＋z2,n)=qgcd(z1＋z3,n)=pgcd(z1＋z4,n)=n背包公钥加密背包公钥加密基于子集和问题基本思想：选择一个容易求解的子集和问题实例（私钥），然后将它伪装成一个很难求解的一般子集和问题实例（公钥）Merkle-Hellman背包加密方案是第一个具体实现了的公钥加密方案有着重要的历史意义已有一个攻击它的多项式时间算法超递增序列超递增序列(b1,b2,…,bn)是一个正整数序列，其中每个元素都大于前面所有元素之和求解超递增序列子集和问题输入(b1,b2,…,bn)，整数s输出(x1,x2,…,xn)，其中xi=1表示选中bii=n当i≥

1时，执行若s≥bi，则xi=1,s=s

-bi。否则xi=0i=i-1返回(x1,x2,…,xn)Merkle-Hellman背包加密公/私钥生成：公共参数n选择一个超递增序列(b1,b2,…,bn)和模数M，使得M>sum(bi)随机选择一个整数W，1≤W≤M-1，gcd(W,M)=1随机选择整数{1,2,…,n}的一个置换π计算ai=Wbπ(i)modM,i=1,2,…,n公钥为(a1,a2,…,an)，私钥为(π,M,W,(b1,b2,…,bn))加密：消息m将消息表示为二进制串，m=m1,m2,…,mn计算c=m1a1+m2a2+…+mnan，作为密文解密：计算d=W-1cmodM求满足d=r1b1+r2b2+…+rnbn的二进制数r1,r2,…,rn消息比特是mi=rπ(i),i=1,2,…,n概率公钥密码确定性的密码体制存在缺点：密码体制对消息空间的所有概率分布未必是安全的例如：RSA中，消息0或1总是加密成其本身同一消息发送两次时，密文重复，容易被检测有利于密码分析概率密码利用随机性得到一个可证的高强度安全性在对称密码体制中实现概率密码:在消息中嵌入随机数通过可逆变换使得该随机数影响到所有比特位加密Blum-Goldwasser概率加密是已知的最有效的概率加密方案在速度和消息扩展方面可以与RSA相比若大数分解是困难的，则它是理想安全的易受选择密文攻击，在实际应用中受限密钥生成：随机选择两个大素数p,q，p≡q≡3mod4计算n=pq用扩展欧几里得算法计算整数a和b，使得ap+bq=1公钥是n，私钥是(p,q,a,b)Blum-Goldwasser概率密码加密：n为接收方公钥令k=

log2n

,h=

log2k，将消息表示为长度为t的串m=m1m2…mt，其中mi是长度为h的二进制串

//用BBS生成器产生密钥流加密m随机选择r，并计算x0=r2modn对i=1…t执行：计算xi=xi-12modn记pi为xi的最低h位比特计算ci=pi⊕mi计算xt+1=xt2modn发送密文c=(c1,c2,…,ct,xt+1)Blum-Goldwasser概率密码解密：计算d1=((p+1)/4)t+1mod(p-1)计算d2=((q+1)/4)t+1mod(q-1)计算u=xt+1d1modp,v=xt+1d2modq计算x0=vap+ubqmodn对于i=1…t，执行计算xi=xi-12

modn记pi为xi的最低h位比特计算mi=pi⊕ci解密的证明：注意到xt+1(p+1)/4modp=xt重复计算t+1次，u≡xt+1d1≡x0(modp)同理v≡x0(modq)∵ap+bq=1∴vap+ubq≡x0(modp),vap+ubq≡x0(modq)∴x0=vap+ubq(modn)x0解出，即可逐个恢复明文SM2椭圆曲线公钥密码

SM2椭圆曲线公钥密码私钥：1<d<n-1公钥：P=dGS=hP，h为余因子，是椭圆曲线上所有点的个数与n相除的整数部分若S是无穷远点，则需要重新设置私钥加密算法：消息为m，len为m的长度随机选取k，1<k<n-1C1=kG