密码学导论˙第7章公开密钥密码 8学时李卫海.

密码学导论˙第7章公开密钥密码 8学时李卫海

本章内容第一节公开密钥密码的概念第二节 RSA公开密钥标准第三节椭圆曲线密码第四节其它公钥密码体制
密钥生成算法、加/解密算法及原理、数学攻击、计时攻击、选择密文攻击第三节椭圆曲线密码椭圆曲线算术、椭圆曲线密码学第四节其它公钥密码体制 Rabin密码、ElGamal密码、背包公钥加密、概率公钥密码第五节公钥密码系统的密钥管理公钥密码的密钥长度、公钥发布方式、公钥授权、公钥证书、CPK Diffie-Hellman、EKE 密码学导论--中国科学技术大学

第一节公开密钥密码的概念密码学导论--中国科学技术大学

对称密码体制的问题加密能力与解密能力是捆绑在一起的密钥更换、传递和交换需要可靠信道，密钥分发困难密钥管理困难
能加密即能解密，能解密也能加密不能实现数字签名密钥更换、传递和交换需要可靠信道，密钥分发困难密钥管理困难如有N用户，则需要C=N(N-1)/2个密钥，N=1000时，C(1000,2)≈500000 无法满足不相识的人之间通信的保密要求对称密码体制中，密钥至少为两人拥有，不能用于签名密码学导论--中国科学技术大学

1976年，Whitfield Diffie和Martin Hellman设想：
每个用户A有一加密密钥ka，不同于解密密钥ka' 将加密密钥ka公开，ka'保密，ka的公开不影响ka'的安全若B要向A秘密发送明文m，可查A的公开密钥ka，加密得密文C=E(ka,m) A收到C后用只有A才拥有的解密密钥ka'对C进行解密得m=D(ka',C) 实用方案的发展依赖于单向陷井函数密码学导论--中国科学技术大学

对称和非对称密钥加密的主要区别对称密码加/解密密钥相同，密钥为双方共享密钥必须保密已知算法和密文不易推导出密钥非对称钥密码
加/解密密钥不同，双方各持一个其中一个密钥必须保密——私钥已知算法和公钥，不易推导出私钥密码学导论--中国科学技术大学

非对称密码体制的基本特点加密能力与解密能力是分开的密钥分发简单需要保存的密钥量大大减少，N个用户只需要N个密钥
从密码算法和加密密钥来确定解密密钥在计算上是不可行的两个密钥的任何一个都可用来加密，另一个用来解密。如何使用，取决于需求密钥分发简单需要保存的密钥量大大减少，N个用户只需要N个密钥可满足不相识的人之间保密通信可以实现数字签名密码学导论--中国科学技术大学

公开密钥密码体制公钥密码体制的组成明文：算法的输入，可读信息或数据加密算法：对明文进行各种转换
公钥和私钥：算法的输入，分别用于加密和解密每一用户产生一对密钥，用来加密和解密消息其中一个密钥（公钥）存于公开的寄存器或其他可访问的文件中；另一密钥（私钥）秘密保存密文：算法的输出，依赖于明文和密钥解密算法：根据密文和密钥，还原明文密码学导论--中国科学技术大学

公钥密码体制的主要应用保密：Alice要发消息给Bob Alice用Bob的公钥对消息加密C=E(PUb,m)
Bob收到消息后，用其私钥对消息解密M=D(PRb,C) 只有Bob知道自身的私钥，其他接收者均不能解密消息密码学导论--中国科学技术大学

认证：Alice在自己的消息上加认证信息
示证方Alice用自己的私钥加密消息(签名)S=E(PRa,m) 验证方Bob用示证方Alice的公钥解密消息(验证)m=D(PUa,S) 若结果证实公钥与示证方的私钥相吻合，则可以确认消息来自示证方 (认证) 密码学导论--中国科学技术大学

密钥交换：例如Diffie-Hellman
即保密又认证：把保密和认证过程结合起来密钥交换：例如Diffie-Hellman C = E(PUb, D(PRa, m)) m = E(PUa, D(PRb, C)) 密码学导论--中国科学技术大学

对公开密钥密码编码系统的要求计算是容易的分析是不可行的加密变换和解密变换可以互换顺序
产生一对密钥(公钥ke和私钥kd)在计算上是容易的不难计算C=E(ke,m)和m=D(kd,C) 分析是不可行的知道ke, 计算kd不可行不知道kd，即使知道ke, E, D及C，计算m不可行加密变换和解密变换可以互换顺序即D(E(m))=E(D(m)) 密码学导论--中国科学技术大学

公钥密码的常规分析公钥密码易受穷举密钥攻击从给定的公钥计算出私钥是第二种攻击方法穷举消息攻击是第三种攻击形式解决方法是使用长密钥
同时为了便于实现加密和解密，又希望密钥足够短目前仅限于密钥管理和签名从给定的公钥计算出私钥是第二种攻击方法多数公钥算法尚未在数学上证明可以抵抗这种攻击穷举消息攻击是第三种攻击形式攻击者用公钥对所有可能的消息加密，并与传送的密文匹配，从而解密任何消息抵抗的方法是在要发送的消息后附加随机数。密码学导论--中国科学技术大学

第二节 RSA公开密钥标准密码学导论--中国科学技术大学

概述 1977年，Rivest、Shamir、Adleman基于大合数的质因子分解问题的困难性，提出RSA密码体制
2005年已能分解十进制200位的大合数 2009年，数百台设备运行2年，分解一个十进制232位大数密码学导论--中国科学技术大学

RSA算法满足公开密钥加密的要求，基本思路：
找到适当的e,d,n，使得对所有m<n有med mod n=m 对于所有m<n的值，要计算me和Cd是相对容易的在给定e和n时，计算出d是不可行的几个关系 mp-1 mod p=1，mk(p-1)+1 mod p=m ed=k(p-1)+1 ? ed=1 mod (p-1) p必须公开，p-1也是公开的。由e计算d是容易的 mΦ(n) mod n=1，mkΦ(n)+1 mod n=m ed=kΦ(n)+1 ? ed=1 mod Φ(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 = me mod n 解密：m = Cd mod n = med mod n = m 密码学导论--中国科学技术大学

例：p=17,q=11,e=7 n=pq=17×11=187, Φ(n)=(p-1)(q-1)=16×10=160
选择e=7, gcd(7,160)=1, 23×7=161，所以d=23 公钥PU={7,187}，私钥PR={23,187} 消息m=88 加密计算C=887 mod 187=11 解密计算m=1123 mod 187=88

注意：在欧拉定理中，mΦ(n)=1 mod n 要求gcd(m,n)=1，即要求m不能被p或q整除。那么p或q的倍数能否不能出现在明文中？
从解密角度考虑由费马定理，qp-1 mod p =1，即qΦ(n) mod p =1 则qΦ(n) -1 = kp 两边同乘q，有qΦ(n)+1 -q = kpq，即qΦ(n)+1 mod n =q 考虑任意m=bq，gcd(b,n)=1,有(bq)Φ(n)+1 mod n =bq 当明文是p或q的倍数时，仍可以正确解密 m不能是0、±1，否则密文就是明文（e必为奇数）密码学导论--中国科学技术大学

实现方面的考虑加密与解密公钥的有效运算模指数运算，可通过下面两个手段减少运算量
模运算特性 [(a mod n) op (b mod n)] mod n = (a op b) mod n 快速指数算法公钥的有效运算 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 mod n1, C2=m3 mod n2, C3=m3 mod n3 各用户的素数是随机生成的，因此模数n1,n2,n3两两互素的可能很大由中国剩余定理可以计算C=CRT(n1,n2,n3,C1,C2,C3) 显然有C=m3 mod n1n2n3 由RSA算法规则，m<ni，因此m3 < n1n2n3 因而可以直接计算m=C1/3 密码学导论--中国科学技术大学

私钥的有效运算运用中国剩余定理简化运算：求m=Cd mod n 比直接运算m=Cd mod n快4倍
计算：Xp=q×(q-1 mod p), Xq=p×(p-1 mod q) 定义：Vp=Cd mod p=Cd mod (p-1) mod p Vq=Cd mod q=Cd mod (q-1) mod q 则m=(VpXp+VqXq) mod n 比直接运算m=Cd mod n快4倍密码学导论--中国科学技术大学

RSA的安全性有四种可能的对RSA的攻击方法穷举攻击：数学攻击：计时攻击：选择密文攻击：尝试所有可能的密钥
对两个素数乘积的因子分解(FAC问题) 计时攻击：依赖于解密算法的运行时间选择密文攻击：利用了RSA算法的性质密码学导论--中国科学技术大学

数学攻击数学攻击： RSA的安全性问题依赖于大合数的素因子分解，即factorization problem (FAC)
分解n为两个素数p,q，并进而求出d 直接找出Φ(n)，并进而求出d 直接找出d RSA的安全性问题依赖于大合数的素因子分解，即factorization problem (FAC) 2005年分解了200位十进制（约664 bits）大合数 2009年分解了232位十进制（768 bits）大合数当前，密钥应选取1024或2048位密码学导论--中国科学技术大学

密码学导论--中国科学技术大学

p和q的选取约束 p和q应该是随机的，且不包含在素数表中强素数p： p和q大小不能太接近总可以查表或遍历特殊形式的素数
p-1有一个大的素因子r p+1有一个大的素因子 r-1有一个大的素因子 p和q大小不能太接近否则p和q接近n1/2，容易被穷举攻击选择p和q在长度上有几个比特差异是可行的密码学导论--中国科学技术大学

(p-1)和(q-1)都应有一个不相等的大素因子
可能存在基于重复加密的攻击：ce,(ce)e,… 若cet ≡ c (mod n)，则cet-1 ≡ m (mod n)，即met-1=m (mod n) 当(p-1)和(q-1)都有一个不相等的大素因子时，这种攻击可以忽略 GCD(p-1, q-1)应该较小 d>n1/4 若d<n1/4，则可以用Wiener攻击在多项式时间内分解n “Cryptanalysis of short RSA secret exponents”, 1990. 密码学导论--中国科学技术大学

先找出Φ(n)，再分解n p和q是方程x2-(p+q)x+pq=0的根 pq=n
若找到Φ(n)，Φ(n)=(p-1)(q-1)=n-(p+q)+1 则方程为x2-[n-Φ(n)+1]x+n=0 密码学导论--中国科学技术大学

计时攻击计时攻击可能的解决办法 RSA数据安全公司在产品中实现M=Cd mod n的过程：
类似通过观察转动老式电话拨号盘的时间长短来猜测密码可能的解决办法不变的幂运行时间，可能会降低性能在求幂运算中加入随机延时隐蔽：在执行幂运算之前先将密文乘上一个随机数 RSA数据安全公司在产品中实现M=Cd mod n的过程：产生0～n-1之间的秘密随机数r 计算C'=C×(re) mod n, e是公开的指数计算M'=(C')d mod n 计算M=M'r-1 mod n, 其中r-1是r模n的乘法逆元密码学导论--中国科学技术大学

共模攻击为简化问题，可能会给多个用户相同的n（p和q由密钥管理中心保管，不公开），但不同的e和d 不应使用公共的n
若明文m用不同的指数e1,e2加密，公共模数为n，则密文c1=me1 (mod n), c2=me2 (mod n) 不同用户的指数e往往是互素的，由扩展欧几里得算法可以找到r和s，满足re1+se2=1。有c1rc2s=mre1+se2=m r和s必有一个是负数，不妨设是r，则(c1-1)-rc2s=m 不应使用公共的n 若e1,e2非互素，则可找到d=gcd(e1,e2), re1+se2=d，并进而计算得到md。开方即可密码学导论--中国科学技术大学

选择密文攻击乘法同态对RSA算法，有E(PU,M1)×E(PU,M2)=E(PU,M1×M2)
若有密文C=Me mod n，则攻击过程如下：计算X=(C×2e) mod n 解密X，得到Y=Xd mod n 因为X=(C mod n)×(2e mod n) =(Me mod n)×(2e mod n) =(2M)e mod n 所以Y=(2M) mod n，M=Y/2 mod n 可以在加密之前对明文随机填充 RSA安全公司推荐最优非对称加密填充(OAEP) 使明文符合一定规则，解密后可以检验合法性密码学导论--中国科学技术大学

针对使用过程的攻击 E截获了用A的公钥加密的密文c，想读出m：永远不要对一个陌生人提交的随机文件签名
对RSA算法，有E(PU,M1)×E(PU,M2)=E(PU,M1×M2) 生成一个随机数r，并用A的公钥加密x=re (mod n) 计算y=xc (mod n)，并让A签名y A签名后将u=yd (mod n)发送给E E计算r-1u = r-1yd = r-1redcd = m (mod n) 永远不要对一个陌生人提交的随机文件签名可以在加密之前对明文随机填充 RSA安全公司推荐最优非对称加密填充(OAEP) 使明文符合一定规则，解密后可以检验合法性密码学导论--中国科学技术大学

最优非对称加密填充 P：填充参数 M：待填充消息 H：Hash函数 DB：数据块 MGF：掩码生成函数 EM：填充后的消息

盲签名盲签名方案是发送者A和签名者B之间的协议盲签名的应用实例：基本思想：目的：
A发送给B一段消息，B对它签名并送回给A 由这个签名，A能够计算B关于A预先所选消息m的签名但B既不知道消息m，也不知道消息m的签名目的：防止B看到消息和签名——与“不在不知道内容的消息上签名”原则相背盲签名的应用实例：用户A进行电子购物时，需要银行B的签名。但A不希望银行知道他的购物喜好，此时即可使用盲签名密码学导论--中国科学技术大学

Chaum盲签名协议 B的RSA公钥是(n,e)，私钥是d。可以形象化为： A随机选取k，0 ≤ k ≤ n-1, gcd(n,k)=1
（盲化）A计算m'=mke mod n，并发送给B （签名）B计算s'=(m')d mod n，并发送给A （去盲）A计算s=k-1s' mod n，它就是B对m的签名可以形象化为：文件盲化——装入信封中（还包括一张复写纸）去盲化——拆开信封签名——在信封上签名，签名通过复写纸复印到文件上密码学导论--中国科学技术大学

完全盲签名完全盲签名一个例子：过程：盲化－签名－去盲一般人不是愿意在随机文件上签名的
有一组特工，其身份是秘密的，连自己所属机构也不知道他们是谁。特工头子想给每个特工一个签名的文件：“××人享有完全的外交豁免权。” 特工对外用的是化名，因此文件必须签发给这个化名化名是不能被任何人知道的，包括特工头子特工头子也不愿意盲目地在特工送来的文件上签名，他担心是否有特工的文件上会写：“××已经退休，并获得每年一百万美金的养老金。” 密码学导论--中国科学技术大学

假设特工并不关心自己将在哪个化名下得到外交豁免权特工Alice，特工头子Bob
Alice准备n份文件，每个使用一个不同的化名，并给予那个化名外交豁免权 Alice用不同的盲因子盲化每个文件 Alice把n份盲化文件交给Bob Bob随机选择n-1份文件，向Alice索要相应盲因子 Alice向Bob提交盲因子 Bob打开n-1份文件，确认它们都是正确的 Bob在第n份文件上签名，并送给Alice Alice去盲，获得签名的外交豁免证书密码学导论--中国科学技术大学

以上方法称为分割选择技术 Alice的一种欺骗方式：
Alice准备n份待签名的文件，Bob随机抽查n-1份验证其内容合理性，然后在未检测的文件上签名 Alice成功欺骗Bob的机会只有1/n 一旦Bob发现Alice欺骗自己，惩罚是极重的 Alice的一种欺骗方式：对两份文件m1,m2准备两个不同的盲因子k1,k2，使得m1k1e=m2k2e。当Bob索要盲因子时，交给他k1，而去盲化时使用k2。问题是寻找这样的k1和k2是困难的密码学导论--中国科学技术大学

第三节椭圆曲线密码密码学导论--中国科学技术大学

椭圆曲线密码编码学ECC 大多数公开密钥密码系统如RSA, 都使用具有非常大数目的整数或多项式，计算量大，密钥和报文存储量也大
计算能力的提高使得密钥长度一直在增加椭圆曲线密码系统，可以达到同样安全程度，但位数要少得多密码学导论--中国科学技术大学

一、椭圆曲线算术椭圆曲线算数椭圆曲线并非椭圆，它指的是由Weierstrass方程所确定的平面曲线：
y2 + axy + by = x3 + cx2 + dx + e 满足上述方程的数偶(x, y)称为椭圆曲线E上的点。同时定义无穷点(point at infinity)或零点(zero point)的O。椭圆曲线算数实数域有限域密码学导论--中国科学技术大学

实数域上的椭圆曲线一般简化形式 y2=x3+ax+b x3+ax+b=0没有重根的条件 4a3+27b2 ≠ 0 例子：
y2=x3-4x=x(x-2)(x+2) 密码学导论--中国科学技术大学

椭圆曲线的加法椭圆曲线上的点集及其上的加法操作构成一个群点集：椭圆曲线上的所有点和无穷远点
加法规则：若椭圆曲线上的三个点处于一条直线上，则它们的和为O O是加法的单位元(additive identity)，O=-O；对于椭圆曲线上的任一点P，有 P + O = P 密码学导论--中国科学技术大学

逆元：一条垂直线与曲线相交于P=(x,y)和P'=(x,-y)，也相交于无穷点O，有P+P'+O=O。即P=-P'
单位元： P+O=P 密码学导论--中国科学技术大学

加法：连接PQ做直线得交点R' P+Q+R'=O P+Q=-R' 密码学导论--中国科学技术大学

　　　　y2=x3-x　　　　　　　　y2=x3+x+1 密码学导论--中国科学技术大学

二倍：过点P(x, y)的切线 P+P+R'=O P+P=2P=-R' 密码学导论--中国科学技术大学

数乘，多次累加： kP=P+…+P 密码学导论--中国科学技术大学

数学描述 PQ直线g: y=x+y0 =(yQ-yP)/(xQ-xP) y0=yP-xP 与曲线相交： (x+y0)2=x3+ax+b R点坐标： xR=2-xP-xQ yR=-(xR+y0) 密码学导论--中国科学技术大学

切线g：y=sx+y0 s=dy/dx =(3xp2+a)/(2yp) y0=yp-sxp 与曲线相交： (sx+y0)2=x3+ax+b R点坐标： xR=s2-2xP yR=-(sxR+y0)

有限域上的椭圆曲线可以将椭圆曲线定义于有限域GFP上： y2=x3+ax+b mod p 椭圆曲线密码使用变量和参数都在有限域上的椭圆曲线
{0，1，…，p-1}是模p加的交换群(Abelian) ； {1，…， p-1}是模p乘的交换群椭圆曲线密码使用变量和参数都在有限域上的椭圆曲线密码学导论--中国科学技术大学

两种有限域上的椭圆曲线定义在Zp上的素曲线Ep(a,b) 定义在GF(2m)上的二元曲线E2m(a,b) 整数运算对素数p取模
适于软件实现定义在GF(2m)上的二元曲线E2m(a,b) 二值系数的多项式运算适于硬件实现密码学导论--中国科学技术大学

定义在Zp上的素曲线Ep(a,b) Ep(a,b)表示满足下列条件的模p椭圆群，群中元素(x,y)是满足方程y2≡x3+ax+b (mod p)的小于p的非负整数对，另外加上无穷点O。若(x3+ax+b) mod p没有重复因子（没有重根），则基于集合Ep(a,b)可定义一个有限阿贝尔群。即要求：　(4a3+27b2) ≠ 0 (mod p) 例如： p=23, y2=x3+x+1 4×13+27×12 mod 23 = 8 ≠ 0，满足条件密码学导论--中国科学技术大学

椭圆曲线上的点对于每个满足0≤x<p的x，计算x3+ax+b mod p 对于上面每个结果确定它是否有一个模p的平方根
如果没有，在Ep(a, b)中就没有具有这个x值的点如果有，就有两个满足平方根运算的y值(除非这个值是单个的y值0)。这些(x, y)就是Ep(a, b)中的点密码学导论--中国科学技术大学

例：GF11上椭圆曲线方程y2=x3+x+6 mod 11的点
共有N=13个点，N称为椭圆曲线群的阶有限椭圆曲线群 Ep(a, b)的阶N的范围是： x y2 y1,2 P(x,y) P'(x,y) 6 - 8 1 7 4 2,9 (7,2) (7,9) 2 5 4,7 (2,4) (2,7) 9 3,8 (8,3) (8,8) 3 5,6 (3,5) (3,6) 10 (10,2) (10,9) (5,2) (5,9) ∞ O 密码学导论--中国科学技术大学

例：E23(1,1)上的点（除O点外） y2=x3+x+1 mod 23 密码学导论--中国科学技术大学

Ep(a, b)中的加法运算定义与实数上椭圆曲线中的定义相同，但运算均在GF(p)中。若P,Q
P+O=P；若P=(xp, yp)，则-P=(xp, -yp)，P+(-P)=O；加法公式： xR=2-xP-xQ yR=-(·xR+y0) =(yQ-yP)/(xQ-xP) 乘法定义为重复相加。如4P=P+P+P+P 密码学导论--中国科学技术大学

定义在GF(2m)上的二元曲线E2m(a,b)
y2+xy=x3+ax2+b 其中所有变量及运算均在GF(2m)中所有满足该方程的点和无穷远点O组成集合E2m(a,b) 密码学导论--中国科学技术大学

例：素多项式f(x)=x4+x+1定义的有限域GF(24)，其生成元g满足f(g)=0，g=0010，则元素为
该有限域中椭圆曲线y2+xy=x3+g4x2+1上的点为（不含O） g0=0001 g4=0011 g8 =0101 g12=1111 g1=0010 g5=0110 g9 =1010 g13=1101 g2=0100 g6=1100 g10=0111 g14=1001 g3=1000 g7=1011 g11=1110 g15=0001 (0,1) (g5,g3) (g9,g13) (1,g6) (g5,g11) (g10,g) (1,g13) (g6,g8) (g10,g8) (g3,g8) (g6,g14) (g12,0) (g3,g13) (g9,g10) (g12,g12)

当b≠0时，集合E2m(a,b)可构造一个阿贝尔群，加法规则为：
P+O=P -P=(xp,xp+yp)，P+(-P)=O 若P ≠-Q且P ≠Q时，R=P+Q xR=λ2+λ+xP+xQ+a yR=λ(xP+xR)+xR+yP λ=(yQ+yP)/(xQ+xP) R=2P xR=λ2+λ+a yR=xP2+(λ+1)xR λ=xP +yP/xP 密码学导论--中国科学技术大学

二、椭圆曲线密码学 ECC与RSA的对比 ECC中的加法运算与RSA中的乘法运算相对应 ECC中的数乘运算与RSA中的模幂运算相对应给定曲线y2=x3+ax+b mod p以及其上一点P，我们可以通过连续自加k-1次计算Q=kP（或Q=Pk）存在与快速指数运算类似的快速算法问题：当Q已知时能否计算k? 这是一个被称为椭圆曲线离散对数的难题密码学导论--中国科学技术大学

椭圆曲线密码系统的定义椭圆曲线公钥系统域标识：定义椭圆曲线采用的有限域椭圆曲线：系数 a和b
基准点(base):指定的椭圆曲线上的点G 阶 (order): G点的阶n，使得：nG=O 椭圆曲线公钥系统 E(a, b), GF(p) 基点G(x, y) 选择正整数e作为私有密钥公开密钥为Q=eG 密码学导论--中国科学技术大学

ECC加/解密利用ECC实现加/解密的技术有多种，下面是一种简单的方法：首先，将消息m编码为椭圆曲线上形如x-y的一点Pm
选择适当的椭圆曲线和基点G 每个用户选择私钥 nA<n 并计算公钥 PA=nAG 加密Pm过程：Cm={kG, Pm+kPB}，其中k为随机正整数解密Cm过程：Pm+kPB–nB(kG) = Pm+k(nBG)–nB(kG) = Pm 密码学导论--中国科学技术大学

例: P=751，Ep(-1,188)，即y2=x3-x+188,，取G=(0,376) A发送给B的消息编码为点Pm=(562,201)
A随机选择 k=386，B的公钥为PB=(201,5) 计算： kG=386(0,376)=(676,558) Pm + kPb = (562,201) + 386(201,5)=(385,328) 因此，密文为Cm={kG, Pm+kPB}={(676,558),(385,328)}

消息映射算法有多种方法，下面给出一例：编码：解码：将域p划分为长256的小段
对明文进行分组：使得每个分组0 ≤ m ≤ p/256 对明文分组进行编码，使之成为由域参数给出的椭圆曲线上的点Pm 在256m≤x<256(m+1)中找到一个x，使得椭圆曲线方程有解一般地，对所有的满足256m≤x<256(m+l)的x，椭圆曲线方程都无解的概率是很小的。从而可以完成编码。解码：若解密横坐标落在256m≤x<256(m+1)中，则解码为m 密码学导论--中国科学技术大学

Menozes-Vanstone椭圆曲线密码
令E是GF(p)上的椭圆曲线，点数为N。选取基点G 私钥：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 mod p, y2=c2x2 mod p 解密：用私钥e计算：ey0=evG=vQ=(c1,c2) m=(x1,x2)=(y1c1-1mod p, y2c2-1 mod p) 密码学导论--中国科学技术大学

Massey-Omura公钥体制不需要交换公钥。 GF(q)上 A将消息m发送给B 用户A 加密、解密密钥：eA, dA
gcd(eA,q-1)=1, eA dA =1 mod (q-1) 用户B 加密、解密密钥：eB, dB gcd(eB,q-1)=1, eB dB =1 mod (q-1) A将消息m发送给B A B meA meA eB (meA eB)dA = meB B: ( meB )dB = m 密码学导论--中国科学技术大学

Massey-Omura在椭圆曲线上实现
m编码为椭圆曲线上的点Pm N: 椭圆曲线上的点数用户随机选择e: 1<e<N, gcd(e, N)=1, ed=1 mod N A将消息m发送给B： A B eAPm B:dB(eBPm)=Pm eBeAPm dA(eBeAPm)=eBPm 密码学导论--中国科学技术大学

ECC的安全性建立在椭圆曲线对数难题上同等密码强度下，所需密钥量和计算量都小于RSA算法 “Pollard rho方法”是目前最快的方法

第四节其它公钥密码体制密码学导论--中国科学技术大学

一、Rabin密码人们相信破译RSA密码和大数分解问题同等困难 Rabin密码是第一个证明了的安全公钥加密方案但这种等价性没有严格的证明
破译它和大数分解问题同等困难密码学导论--中国科学技术大学

密钥生成：加密：B为A加密消息解密：随机生成两个不同但大小相近的大素数p和q 计算n=pq 公钥为n，私钥为(p,q)
将消息分组表示成{0,1,…,n-1}中的整数m，n是A的公钥计算c=m2 mod n作为密文解密：求解c的四个平方根从四个平方根中选取正确的一个密码学导论--中国科学技术大学

安全性讨论： N的因子分解问题和计算模n的平方根在计算上是等价的，因此破译Rabin算法与大数分解是同等困难的
不能抵抗选择密文攻击，理由同“不经意传输” 敌手随机选择x，计算c=x2 mod n。提交c去正常解密，得到明文y。此时有1/2的几率使得gcd(x+y,n)就是n的一个素因子讨论： p和q模4余3时，利于求解平方根加密前一般在m中嵌入冗余，据此从四个解中选择正确的解。若四个解中均无特定冗余，则拒绝返回答案密码学导论--中国科学技术大学

使用冗余方案时的安全性：若敌手在生成的x中嵌入了冗余，则解密器会以极大的概率返回x（其它三个平方根不大可能也碰巧具有该冗余）。此时破译攻击失败；若敌手在生成的x中不嵌入冗余，则解密器会以极大的概率拒绝接受密文。此时破译攻击失败。可以抵抗选择密文攻击。密码学导论--中国科学技术大学

二、ElGamal密码 ElGamal密码属于离散对数密码体制离散对数密码例：Pohlig-Hellman Scheme
安全性基于DLP问题离散对数密码例：Pohlig-Hellman Scheme 加密：C = Me mod P 解密：M = Cd = (Me)d mod P ed mod Φ(P) = 1，P为大素数，Φ(P)为欧拉函数因为P是素数，Φ(P)容易获得，因此e和d都需要保密显然，并非公开密钥密码密码学导论--中国科学技术大学

ElGamal密码 A和B共享大素数P，本原元素α，消息0≤m≤P-1 加密：解密： A选择k∈(1, P-1)，k的作用其实即为私钥xA
A访问公共区域获取B的公钥YB = αxB mod P。计算： K = (YB)k mod P，即K = αxBk mod P c1 = αk mod P，c2 = mK mod P 密文即为 (c1, c2) 解密： B首先恢复K：K = c1xB mod P = αkxB mod P 然后恢复m：m = c2/K mod P = c2K-1 mod P 密码学导论--中国科学技术大学

得m1/m2=c2,1/c2,2 mod P。如果m1已知，m2即可算出
这里特别注意，k不能重复使用，如果 (1) c1,1 = αk mod P c2,1 = m1K mod P (2) c1,2 = αk mod P c2,2 = m2K mod P 得m1/m2=c2,1/c2,2 mod P。如果m1已知，m2即可算出 ElGamal密码体制是概率密码体制，相同明文每次加密得到不同的密文加密效率是50％，因为密文大小是明文的两倍。破译难度等价于离散对数难题密码学导论--中国科学技术大学

例：P=17，α=3，xA=2，xB=5，m=11，A发送m到B 公钥计算：加密： A选择k = 7
YB = αxB mod P = 35 mod 17 = 5 加密： A选择k = 7 K = (YB)k mod P = 57 mod 17 = 10 c1 = αk mod P = 37 mod 17 = 11 c2 = mK mod P = 10×11 mod 17 = 8 所以，密文C = (c1, c2) = (11, 8) 解密： K = c1xB mod P = 115 mod 17 = 10 c2 = mK mod P = 10m mod 17 = 8 m = c2/K mod P = c2K-1 mod P K·K-1 mod P = 1，即10 K-1 mod 17 = 1，得K-1 = 12 所以，明文m = c2K-1 mod P = 8x12 mod 17 = 11

ElGamal算法在椭圆曲线上实现 E(a,b)，基点G∈E B选择a并保密, 0<a<N，N为G的阶(order)
公开密钥为aG A向B发送消息m: A将m嵌入点Pm，选择随机数k, A B (kG, Pm +k(aG)) B：Pm = (Pm +k(aG)) –a(kG) 密码学导论--中国科学技术大学

三、背包公钥加密背包公钥加密基于子集和问题
基本思想：选择一个容易求解的子集和问题实例（私钥），然后将它伪装成一个很难求解的一般子集和问题实例（公钥）。 Merkle-Hellman背包加密方案是第一个具体实现了的公钥加密方案有着重要的历史意义已有一个攻击它的多项式时间算法密码学导论--中国科学技术大学

Merkle-Hellman背包加密超递增序列(b1,b2,…,bn)是一个正整数序列，其中每个元素都大于前面所有元素之和。
求解超递增序列子集和问题输入(b1,b2,…,bn)，整数s 输出(x1,x2,…,xn)，其中xi=1表示选中bi i=n 当i ≥ 1时，执行若s ≥ bi，则xi=1, s=s - bi 。否则xi=0 i=i-1 返回(x1,x2,…,xn) 密码学导论--中国科学技术大学

公/私钥生成：公共参数n 选择一个超递增序列(b1,b2,…,bn)和模数M，使得M>sum(bi)
随机选择一个整数W，1 ≤ W ≤ M-1，gcd(W,M)=1 随机选择整数{1,2,…,n}的一个置换π 计算ai=Wbπ(i) mod M, i=1,2,…,n 公钥为(a1,a2,…,an) ，私钥为(π,M,W, (b1,b2,…,bn)) 密码学导论--中国科学技术大学

加密：消息m 解密：将消息表示为二进制串，m=m1,m2,…,mn 计算c=m1a1+m2a2+…+mnan，作为密文
计算d=W-1c mod M 求满足d=r1b1+r2b2+…+rnbn的二进制数r1,r2,…,rn 消息比特是mi=rπ(i), i=1,2,…,n 密码学导论--中国科学技术大学

四、概率公钥密码确定性的密码体制存在缺点：概率密码利用随机性得到一个可证的高强度安全性在对称密码体制中实现概率密码:
密码体制对消息空间的所有概率分布未必是安全的例如：RSA中，消息0或1总是加密成其本身同一消息发送两次时，密文重复，容易被检测有利于密码分析概率密码利用随机性得到一个可证的高强度安全性在对称密码体制中实现概率密码: 在消息中嵌入随机数通过可逆变换使得该随机数影响到所有比特位加密密码学导论--中国科学技术大学

Blum-Goldwasser概率加密是已知的最有效的概率加密方案密钥生成：在速度和消息扩展方面可以与RSA相比
若大数分解是困难的，则它是理想安全的易受选择密文攻击，在实际应用中受限密钥生成：随机选择两个大素数p,q，p ≡ q ≡ 3 mod 4 计算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=r2 mod n 对i=1…t执行：计算xi=xi-12 mod n 记pi为xi的最低h位比特计算ci=pi⊕mi 计算xt+1=xt2 mod n 发送密文c = (c1,c2,…,ct,xt+1) 密码学导论--中国科学技术大学

解密：计算d1=((p+1)/4)t+1 mod (p-1) 计算d2=((q+1)/4)t+1 mod (q-1)
计算u=xt+1d1 mod p, v=xt+1d2 mod q 计算x0=vap+ubq mod n 对于i=1…t，执行计算xt=xi-12 mod n 记pi为xi的最低h位比特计算mi=pi⊕ci 密码学导论--中国科学技术大学

解密的证明：注意到xt+1(p+1)/4 mod p = xt 重复计算t+1次， u ≡ xt+1d1 ≡ x0 (mod p)
同理v ≡ x0 (mod q) ∵ ap+bq=1 ∴ vap+ubq ≡ x0 (mod p), vap+ubq ≡ x0 (mod q) ∴ x0 = vap+ubq (mod n) x0解出，即可逐个恢复明文密码学导论--中国科学技术大学

第五节公钥密码系统的密钥管理密码学导论--中国科学技术大学

一、密钥长度公开密钥算法的安全性基于NP数学难题大数因子分解技术的发展比数学家的预计还要快主要的大数分解算法二次筛选法
1983年，分解71位的数据需要0.1mips-year 1994年，分解129位的数据需要5000mips-year 主要的大数分解算法二次筛选法一般数域筛选法对116位以上的大数分解比二次筛选法快得多特殊数域筛选法分解一些特殊形式的数密码学导论--中国科学技术大学

当前，民用公钥密码一般取1024～2048位，政府往往取2048位或4096位。
1995年公布的大数分解能力当前，民用公钥密码一般取1024～2048位，政府往往取2048位或4096位。预测大数分解能力是非常困难的位一般数域筛选法 (mips-year) 特殊数域筛选法 (mips-year) 512 3000 <200 768 2×108 100000 1024 3×1011 3×107 1280 1×1014 3×109 1536 3×1016 2×1011 2048 3×1020 4×1014 密码学导论--中国科学技术大学

DNA技术：利用DNA链来求解NP问题量子技术图的哈密尔顿环问题：可以解决NP问题结点由一段DNA分子表示
制备大量分子，充分反应后，利用重力析解出特定的分子链量子技术可以解决NP问题威胁基于大数分解或离散对数的密码系统 2008年，分解21 密码学导论--中国科学技术大学

密码系统的安全性有最薄弱环节决定应注意，安全强度是随时间变化的选择安全强度相当的密钥长度密钥长度随着运算能力的增加而增加——对称密钥
密钥长度随着算法的改进而增加——公开密钥对称密钥 56 80 112 128 192 256 RSA密钥 512 1024 2048 3072 7680 15360 ECC密钥 161 224 384 密码学导论--中国科学技术大学

二、公钥密码系统的密钥分配公钥的管理/分配方法：公开发布公开可访问目录公钥授权公钥证书密码学导论--中国科学技术大学

1、公钥的公开发布用户直接将公钥发送给另一方，或进行广播通知主要弱点是可以被伪造例如：将PGP密钥附在邮件上或发布给新闻组/邮件组
假冒者可以冒充用户A，将公钥公开发布在用户A发现，并通知所有人之前，假冒者可以解读所有发往A的消息密码学导论--中国科学技术大学

2、公开可访问的目录在一个公开可访问目录下注册公钥该目录应由可信实体或组织负责，内容包括：仍有被假冒的风险提供更高的安全性
包括条目｛姓名，公钥｝公钥的注册必须亲自进行，或通过安全认证的通信进行用户可以在任何时刻更新公钥该目录应定期更新该目录可以通过网络访问仍有被假冒的风险目录管理员的密钥泄漏管理目录的服务器被攻破密码学导论--中国科学技术大学

3、公钥授权获取Bob公钥获取Alice公钥原始请求，确认原始请求未被篡改原始时间戳，确认消息是即时的双向身份认证

可以更严格的控制目录中的密钥分配第1,2,4,5步是A和B分别获得对方的公钥第3,6,7步用于A和B的相互认证，防止他人假冒
每个用户拥有管理员的公钥第1,2,4,5步是A和B分别获得对方的公钥 A、B可以保存已获得的公钥，而不必每次都重新获得考虑到对方可能更换公钥，应定期重新申请第3,6,7步用于A和B的相互认证，防止他人假冒密码学导论--中国科学技术大学

4、公钥证书管理员成为系统安全性的瓶颈证书内容用认证中心CA（或其他可信第三方）的私钥进行签名证书将用户身份与公钥绑定在一起
通常还包括：有效期、权限等信息公钥证书保证密钥交换不需要与公钥授权中心的实时连接通信各方使用证书来交换密钥任何知道CA公钥的用户都可以对证书进行验证密码学导论--中国科学技术大学

公钥证书满足如下条件：对于申请者A，管理员提供的证书为：其他人读取并验证：任何通信方可以读取证书，确定证书拥有者的姓名和公钥
任何通信方可以验证证书出自证书管理员只有证书管理员可以产生并更新证书注意，获得管理员的密码，并不意味着得到管理员的私钥对于申请者A，管理员提供的证书为： CA = E(PRauth,T||IDA||PUa)，T是时间戳其他人读取并验证： D(PUauth,CA)= T||IDA||PUa 密码学导论--中国科学技术大学

获取自己公钥证书获取自己公钥证书交换证书注意，这里没有认证对方身份密码学导论--中国科学技术大学

一个证书的例子版本号用户名用户ID 公钥有效期使用权限备用公钥 HASH(以上内容) E (PRauth, HASH)

5、X.509认证服务 ITU-T建议书中X.500系列中定义目录服务的部分定义了认证服务框架定义了认证协议
存储公钥证书的目录公钥证书由CA签发定义了认证协议是基于公钥密码体制和数字签名的服务密码学导论--中国科学技术大学

公钥证书的产生过程密码学导论--中国科学技术大学

证书 Subject主体；Issuer发行商密码学导论--中国科学技术大学

证书链与证书的获取公钥证书可公开存放利用证书链验证其它CA签名的证书例：A获取B的公钥证书
X<<W>>  W<<V>>  V<<Y>>  Y<<Z>>  Z<<B>> 前向证书：发给X 后向证书：X签发密码学导论--中国科学技术大学

证书的撤销未到有效期而撤销证书撤销表CRL 如何有效管理、查找撤销列表？用户私钥被认为不安全用户不再信任该CA

认证过程密码学导论--中国科学技术大学

X.509 v3 基本特性多算法支持多种命名机制限制证书(公钥)的用途定义证书遵循的策略证书链的处理
报文摘要：MD2、MD5、SHA－1 加密签名：RSA、DSA 持钥者密钥对类型：RSA密钥、DSA签名密钥、D-H交换密钥、KEA密钥、ECDSA密钥多种命名机制地址、IPv4/v6地址、DNS、URL 限制证书(公钥)的用途签名、无否认、密钥加密、密钥协商、数据加密、证书签发、CRL签发定义证书遵循的策略证书链的处理密码学导论--中国科学技术大学

6、公钥基础设施 RFC 2822（互联网安全术语）定义： PKI系统(Public Key Infrastructure)是由硬件、软件、人、策略和相应处理构成的一整套体系。用来创建、管理、存储、分发和撤销数字证书提供网络信息安全服务，保证用户安全、便捷、高效地获取公钥密码学导论--中国科学技术大学

互联网工程任务组(IETF)的PKIX工作组在X.509基础上建立了一个基本模型，包括：
端实体认证机构(CA)：生成、发放证书，也承担部分管理任务注册机构(RA)：承担部分管理任务证书撤销列表(CRL)发布点证书存取库密钥备份、恢复、历史档案等等密码学导论--中国科学技术大学

三、组合公钥 1999年提出CPK(Combined Public Key) 基于离散对数或椭圆曲线实现实现海量公/私钥产生、管理与分发
KDC产生私钥矩阵（保密），公钥矩阵（公开） KDC将用户的私钥和公钥矩阵发送给各个用户用户可以根据通信对方的ID，由公钥矩阵算出对方的公钥 mh的矩阵可以提供mh个公、私钥对密码学导论--中国科学技术大学

生成密钥矩阵基于DLP的密钥矩阵生成：确定大素数p, q, n=pq, Φ(n) 随机生成私钥矩阵SSK={rij}
计算公钥矩阵PSK={dij=rij-1 mod Φ(n)} 密码学导论--中国科学技术大学

基于ECC的密钥矩阵生成：确定椭圆曲线Ep(a,b), 基点G 随机生成私钥矩阵SSK={rij} 计算公钥矩阵PSK={rijG}

若mh个用户共谋，就有可能恢复私钥矩阵
公、私钥生成：对用户ID做HASH，再经过一系列变换，得到h个坐标：(x1,y1),(x2,y2),…,(xh,yh)（每列选一个元素）公钥为： DLP：PU=dx1y1×dx2y2×…×dxhyh ECC：PU=(xx1y1,yx1y1)+(xx2y2,yx2y2)+…+(xxhyh,yxhyh) 私钥为： DLP：PR=rx1y1×rx2y2×…×rxhyh ECC：PR=rx1y1+rx2y2+…+rxhyh 密钥量：mh（m=h=32时，密钥量为2160个）若mh个用户共谋，就有可能恢复私钥矩阵密码学导论--中国科学技术大学

四、利用公钥密码分配对称密钥获得公钥后，可用于加密、认证等工作公钥密码算法计算量大，速度慢，不适用于大数据量的实时加密
公钥密码通常用于管理会话密钥，即用公/私钥作为主密钥用对称密码加密数据，会话密钥一般使用对称密钥有多种协议用于协商会话密钥密码学导论--中国科学技术大学

简单的密钥交换协议 Merkle于1979年提出：主要缺陷是存在中间人攻击 A产生临时公私钥对 A将公钥和他的ID发送给B
B产生会话密钥K，并A提供的公钥加密，并发给A A解密获得会话密钥，舍弃临时公私钥对主要缺陷是存在中间人攻击密码学导论--中国科学技术大学

中间人攻击 E干扰密钥交换并窃取会话密钥后，可以不必再干扰AB的正常通信，只需监听即可获得所有消息 A E B PUa||IDa
PUe||IDe EPUe(K) EPUa(K) 密码学导论--中国科学技术大学

具有保密和认证的密钥分配 A发出请求 A确认B B确认A 传递会话密钥密码学导论--中国科学技术大学

混合密钥分配使用KDC KDC与每个用户间共享一个秘密的主密钥使用主密钥来分配会话密钥公钥用于分发主密钥主要考虑：
当用户分布比较分散时特别有效主要考虑：性能：需要频繁更换会话密钥时，公钥算法的计算量会影响系统性能。在混合系统中，KDC只偶尔更新主密钥兼容性：易于应用到传统KDC系统中密码学导论--中国科学技术大学

五、密钥协商协议 Diffie和Hellman于1976提出的首次利用公钥算法实现密钥分配
轶闻：Williamson(UK CESG)于1970年已在机密文件中提出了该算法，并用于开发商业产品 D-H协议用于安全协商密钥不能用于交换确定消息可用于建立共享的密钥仅有通信双方知道密钥的值取决与通信双方（及他们的公私钥）实现基于有限域上的指数运算——容易安全性依赖于离散指数运算——困难密码学导论--中国科学技术大学

1、D-H协议算法所有用户的公共参数：各用户（例如用户A）产生自己的密钥用户A、B查找对方公钥，再分别计算会话密钥KAB
大素数或素多项式q、模q的本原根α 各用户（例如用户A）产生自己的密钥选择私钥：XA< q 计算公钥：YA = αXA mod q，并公开YA 用户A、B查找对方公钥，再分别计算会话密钥KAB KAB = αXAXB mod q = YAXB mod q (B的运算) = YBXA mod q (A的运算) 用户需要更新公私钥，以产生新的会话密钥攻击者必须解离散对数问题密码学导论--中国科学技术大学

例：用户A和B交换密钥：公共参数q=353 及 α=3 选择随机私钥：计算公钥：计算共享会话密钥：
A选择XA=97，B选择XB=233 计算公钥： A：YA=397 mod 353 = 40 B：YB=3233 mod 353 = 248 计算共享会话密钥： A：KAB= YBXA mod 353 = mod 353 = 160 B：KAB= YAXB mod 353 = mod 353 = 160 密码学导论--中国科学技术大学

中间人攻击 E与A共享会话密钥：αXA·XE2 E与B共享会话密钥：αXB·XE1 在AB通信期间，E需要持续的截获、解密、重加密
使用数字签名和公钥证书可以避免中间人攻击 A E B αXA αXE1 αXE2 αXB 密码学导论--中国科学技术大学

Hughes对Diffie-Hellman方法的改进
双方密钥的生成是异步进行的某些场合下，需要一方事前准备好密钥 A可以事先生成密钥，而B可以通过接收到的数据计算出该密钥 A: K = αXA mod P B: Y = αXB mod P  A A: X = YXA mod P = αXAXB mod P  B B: x'B=xB-1, K' = XX'B mod P = αXA mod P = K 密码学导论--中国科学技术大学

Diffie-Hellman的椭圆曲线实现
D-H协议：素数p，本原根g ECC实现：选定椭圆曲线Ep(a,b)，及基点G ，n是G的阶 A、B分别随机选取a<n、b<n并保密。 A: Q = aB = abG B: Q = bA = baG = abG A=ga mod p B=gb mod p 密钥S=Ab=Ba=gab mod p A=aG mod p B=bG mod p 密码学导论--中国科学技术大学

例： P=211; Ep(0, -4), 即y2=x3-4, G=(2, 2) 可求得241G=O
nA=121, PA=121(2, 2)=(115, 48) nB=203, PB=203(2, 2)=(130, 203) K = 121(130, 203) =203(115, 48)=(161, 169) 密码学导论--中国科学技术大学

2、MTI密钥协商协议可信中心TA签发公钥：密钥协商：特点：用户不需要计算任何签名所有用户公有：素数p，本原元α∈GF(p)
用户A选取私钥aA，计算bA=αaA mod p发给TA TA签发公钥证书CA={IDA,bA,E(PRauth,IDA||bA)} 密钥协商： A随机选取rA≤p-2，计算SA=αrA mod p，发送{CA,SA}给B B随机选取rB≤p-2，计算SB=αrB mod p，发送{CB,SB}给A K = SAaB·bArB = SBaA·bBrA = αaArB+ aBrA 特点：用户不需要计算任何签名攻击者由于不知道aA和aB，不能计算出K。由于公钥证书参与计算，不能进行中间人攻击密码学导论--中国科学技术大学

3、加密密钥交换协议EKE Steves Bellovin和Michael Merritt设计
用共享的对称密钥P来保护随机产生的会话密钥K： A 随机产生一对公开/隐蔽密钥，使用对称密钥算法和密钥P将公开密钥PU加密，将标识符A和E(P,PU)发给B B知道P，可解PU。B产生随机会话密钥K，向A发送E(P,E(PU,K)) A解出K A产生随机数RA，向B发送E(K,RA) B产生RB，向A发送E(K,RA||RB) A收到后，确认B知道K。向B发送E(K,RB) B收到后，确认A知道K。则交换与鉴别成功。前三步交换密钥，后四步双向身份认证。密码学导论--中国科学技术大学

若直接用P加密K，则攻击者E可以猜测K的值，并验证猜测
为什么这么复杂？若直接用P加密K，则攻击者E可以猜测K的值，并验证猜测人们总是选择坏的口令 EKE协议中，P可以是一个弱口令。攻击者E仅能知道E(P,PU), E(P,E(PU,K))和一些用K来加密的随机数在没有破译公钥算法前，E无法验证他对P的猜测公钥密码系统的密钥很长，穷举攻击工作量比对称密码系统的大得多 EKE将对称密码和公开密钥密码系统相结合，通过弱口令P来建立安全性强的会话密钥密码学导论--中国科学技术大学

加强的EKE 进一步加强：分析：第4步，A产生一个新随机数SA，发送E(K,RA||SA)
第5步，B产生一个新随机数SB，发送E(K,RA||RB||SB) 会话密钥为S=SASB，K被舍弃分析： P没有直接用来加密可直接导出S的东西 K仅用来加密少量随机数据，且S从没有单独加密过密码学导论--中国科学技术大学

密码学导论˙第7章公开密钥密码 8学时李卫海.

Similar presentations

Presentation on theme: "密码学导论˙第7章公开密钥密码 8学时李卫海."— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

密码学导论˙第7章 公开密钥密码 8学时 李卫海.

Similar presentations

Presentation on theme: "密码学导论˙第7章 公开密钥密码 8学时 李卫海."— Presentation transcript:

Similar presentations

About project

反馈

密码学导论˙第7章公开密钥密码 8学时李卫海.

Presentation on theme: "密码学导论˙第7章公开密钥密码 8学时李卫海."— Presentation transcript: