密码学导论˙第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密钥 多种命名机制 E-mail地址、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 = 24897 mod 353 = 160 B：KAB= YAXB mod 353 = 40233 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从没有单独加密过 密码学导论--中国科学技术大学