1、1加密签名密钥分发生产密钥公钥加密私钥解密根据公钥推私钥单向陷门函数大素数p、q模数n=pq（n）私钥(e,n)公钥(d,n)e*d=1 mod (n)加密：ME mod N = C解密：CD mod N = M2pDiffie-Hellman 密钥交换pElGamal密码体制p椭圆曲线p基于公钥密码的伪随机数发生器3pDiffie和Hellman在其里程碑意义的文章中，p虽然给出了密码的思想p但是没有给出真正意义上的公钥密码实例p也既没能没能找出一个真正带真正带陷门陷门的单向函数的单向函数p然而，他们给出给出单向函数单向函数的实例p并且基于此提出Diffie-Hellman密钥交换算法4p
2、允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程p 算法的安全性依赖于依赖于计算离散对数的难度p 素数p的本原根定义：如果a是素数p的本原根，则数a mod p, a2 mod p, , ap-1 mod pp 是不同的并且包含1到p-1的整数的某种排列。p 对任意的整数b，我们可以找到唯一的幂i满足b=ai mod p 0=i=(p-1)p i 在离散对数算法中称为以a为基的指数 mod p。记为dloga,p(b)5协议准备阶段协议准备阶段p Alice和Bob协商好一个大素数p，和大的整数g，1gp，g最好是FP中的本原根本原根，即FP*pp和g无须保密无须保密，可为网络上的所
3、有用户共享Diffie-Hellman密钥交换协议描述密钥交换协议描述6协议准备阶段：协议准备阶段：大素数p、大整数g，g为FP中的本原根p 当Alice和Bob要进行保密通信时： (1) Alice选取大的随机数XA，并计算 YA = g XA(mod P) (2) Bob选取大的随机数XB，并计算 YB = g XB (mod P) (3) Alice将YA传送给Bob；Bob将YB传送给Alice (4) Alice计算K= (YB ) XA(mod P); Bob计算K = (YA ) XB(mod P), 易见，K = K =g XA XB(mod P)p 由(4)知，Alice和B
4、ob已获得了相同的秘密值Kp 双方以K作为加解密钥以传统对称密钥算法进行保密通信Diffie-Hellman密钥交换协议描述密钥交换协议描述7Diffie-Hellman密钥交换协议描述密钥交换协议描述Generate randomXa pCalculateYa=aXa mod pGenerate randomXb pCalculateYb=aXb mod pUser AUser BYaYbCalculateK=(Yb)Xa mod pCalculateK=(Ya)Xb mod p8910p 离散对数的计算: y gx mod pp 已知g,x,p,计算y是容易的p 已知y,g,p,计算x是困
5、难的Diffie-Hellmanan安全性安全性11对对Diffie-Hellmanan攻击攻击 replay攻击攻击中间人攻击图示中间人攻击图示ABK = aXaXbOABK = aXaXoOK = aXbXo12对对Diffie-Hellmanan攻击攻击中间人攻击中间人攻击1. 双方双方选择素数选择素数p以及以及p的一个原根的一个原根a(假定假定O知道知道)2. A选择选择Xap,计算计算Ya=aXa mod p, AB: Ya3. O截获截获Ya,选选Xo,计算计算Yo=aXo mod p,冒充冒充AB:Yo4. B选择选择Xbp,计算计算Yb=aXb mod p, BA: Yb5.
6、O截获截获Yb,冒充冒充BA:Yo6. A计算计算: (Xo)Xa (aXo)Xa aXoXa mod p7. B计算计算: (Xo)Xb (aXo)XXb aXoXb mod p8. O计算计算: (Ya)Xo aXaXo mod p, (Yb)Xo aXbXo mod pO无法计算出无法计算出aXaXb mod pO永远必须实时截获并冒充转发永远必须实时截获并冒充转发,否则会被发现否则会被发现13防御措施防御措施1，使用共享的对称密钥加密DH交换；2，使用公钥加密DH交换；3，使用私钥签名DH交换；14 Taher Elgamal在1984和1985年间提出了一种基于离散对数问题的公钥密码
7、体系，其类似于Diffie-Hellman的密钥协商协议。1516ElGamal举例举例-加密加密 Alice选择XA=5； 计算 Alice的私钥为5；公钥为 假如Bob想将值M=17发送，则作如下计算： (1) Bob选择 k = 6 (2) 计算 (3) 计算 Bob发送密文（11, 5）5modmod193AXAYq , ,19,10,3AqY6() mod3 mod19729mod197kAKYq612mod10 mod1911mod7 17mod19119mod195kCqCKMq17ElGamal举例举例-加密加密 Alice选择XA=5； 计算 Alice的私钥为5；公钥为 假
8、如Bob想将值M=17发送 Bob发送密文（11, 5）Alice选择 在GF(19) 中 计算 5modmod193AXAYq , ,19,10,3AqYA51()mod11 mod197XKCq117mod1911K12()mod5 11mod1917MC Kq18ElGamal安全性安全性p 对于给定的参数，破解对于给定的参数，破解ElGamal相当于解相当于解Diffie-Hellman问题。问题。p实际上，ElGamal可以被看成是Diffie-Hellman密钥的一种变形，基于这个原因，ElGamal的安全性依赖于Zp*上的离散对数问题;p在加密过程中，对在加密过程中，对不同的消息
9、不同的消息m都应都应选取不同的随选取不同的随机数机数k，否则的话，攻击者可以很容易攻击，否则的话，攻击者可以很容易攻击ElGamal公钥公钥体系。体系。19ElGamal攻击相同随机数攻击相同随机数k 如果k用于多个分块，利用信息的分块m1，攻击者计算1,12,111,22,22mod ;modmod ;modkkCq CKMqCq CKMq 于是 2,1112,222modmodmodmodCKMqMqCKMqMq 若M1已知，很容易计算M2122,12,21()modMCCMq20椭圆曲线密码学椭圆曲线密码学21椭圆曲线密码学椭圆曲线密码学p 在在2005年年2月月16日，美国国家安全局日
10、，美国国家安全局(NSA)宣布决定采用椭宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护圆曲线密码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。敏感但不保密的信息。p NSA推荐了一组被称为推荐了一组被称为Suit B的算法，包括用来密钥交换的算法，包括用来密钥交换的的Menezes-Qu-Vanstone椭圆曲线和椭圆曲线和Diffie-Hellman椭圆曲椭圆曲线，用来数字签名的椭圆曲线数字签名算法。这一组中也线，用来数字签名的椭圆曲线数字签名算法。这一组中也包括包括AES和和SHA。22椭圆曲线密码学椭圆曲线密码学 1985年年Miller和和Koblitz
11、分别独立分别独立提出提出y2+axy+by=x3+cx2+dx+e 曲线曲线上的点连同上的点连同无穷远点无穷远点O的集合的集合(定义见下页定义见下页） 运算定义：运算定义： 若曲线三点在一条直线上若曲线三点在一条直线上,则其和为则其和为O O用作加法的单位：用作加法的单位：O = -O; P+O = P 一条竖直线交一条竖直线交X轴两点轴两点P1、P2，则，则P1+P2+O=O，于是，于是P1 = -P2 如果两个点如果两个点Q和和R的的X轴不同，则画一连线，得到第三点轴不同，则画一连线，得到第三点P1，则，则Q+R+P1=O，即，即Q+R=-P1 2倍，一个点倍，一个点Q的两倍是，找到它的切
12、线与曲线的另一个的两倍是，找到它的切线与曲线的另一个交点交点S，于是，于是Q+Q=2Q=-S23 无穷远元素（无穷远点，无穷远直线）无穷远元素（无穷远点，无穷远直线） 平面上任意两相异直线的位置关系有相交和平行两种平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。引入无穷远点，是两种不同关系统一。 ABL1， L2L1，直线直线AP由由AB起绕起绕A点依逆时针方向转点依逆时针方向转动，动，P为为AP与与L1的交点。的交点。Q=BAP /2 AP L2可设想可设想L1上有一点上有一点P，它为，它为L2和和L1的交点，称之为的交点，称之为。直线直线L1上的无穷远点只
13、能有一个。上的无穷远点只能有一个。（因为过（因为过A点只能有一条平行于点只能有一条平行于L1的直线的直线L2，而两直线的，而两直线的交点只能有一个。）交点只能有一个。）L2L1PBAPQ24椭圆曲线密码示意图椭圆曲线密码示意图25有限域上的椭圆曲线有限域上的椭圆曲线有限域上椭圆曲线有限域上椭圆曲线y2 x3+ax+b mod p p是奇素数是奇素数,且且4a3+27b2 0 mod p针对所有的针对所有的0= x p，可以求出有效的，可以求出有效的y，得到曲线上的，得到曲线上的点点(x,y)，其中，其中x,y p。记为。记为Ep(a,b)Ep(a,b)中也包括中也包括O加法公式加法公式:P+O
14、=P如果如果P=(x,y)，则则P+(x,-y)=O，(x,-y)点是点是P的负点，记为的负点，记为-P。而且而且(x,-y)也在也在Ep(a,b)中中如果如果P=(x1,y1)，Q=(x2,y2)，则则 P+Q=(x3,y3)为为x3= 2-x1-x2 (mod p)y3= (x1-x3)-y1 (mod p)其中，其中，如果如果P Q，则，则 = (y2-y1)/(x2-x1) 如果如果P=Q，则，则 = (3x12+a)/(2y1)26椭圆曲线用于加密椭圆曲线用于加密找到一个难题：找到一个难题：考虑等式考虑等式Q=kP，其中，其中Q、P属于属于Ep(a,b)，kp已知已知k和和P，计算，
15、计算Q，是容易的，是容易的已知已知Q和和P，计算计算k，是困难的，是困难的选择选择Ep(a,b)的元素的元素G,使得使得G的阶的阶n是一个大素数是一个大素数G的阶是指满足的阶是指满足nG=O的最小的最小n值值秘密选择整数秘密选择整数r，计算，计算P=rG，然后，然后公开公开(p,a,b,G,P)，P为公钥为公钥保密保密r加密加密M：先把消息：先把消息M变换成为变换成为Ep(a,b)中一个点中一个点Pm然后，选择随机数然后，选择随机数k，计算密文，计算密文Cm=kG,Pm+kP)如果如果k使得使得kG或者或者kP为为O，则要重新选择，则要重新选择k.解密解密Cm: (Pm+kP)-r(kG)=P
16、m+krG-rkG=Pm加密信息有扩张加密信息有扩张27椭圆曲线用密码的安全性椭圆曲线用密码的安全性 难点难点: 从从P和和kP获得获得k 对椭圆曲线研究的时间短对椭圆曲线研究的时间短 椭圆曲线要求密钥长度短椭圆曲线要求密钥长度短,速度快速度快28椭圆曲线用密码的安全性椭圆曲线用密码的安全性与经典的与经典的RSA，DSA等公钥密码体制相比，椭圆密码体制等公钥密码体制相比，椭圆密码体制有以有以下优点下优点：1.安全性高安全性高.有研究表示有研究表示160位的椭圆密钥与位的椭圆密钥与1024位的位的RSA密钥密钥安全性相同。安全性相同。2.处理速度快处理速度快. 在私钥的加密解密速度上，在私钥的加
17、密解密速度上，ecc算法比算法比RSA、DSA速度更快。速度更快。3.存储空间占用小。存储空间占用小。4.带宽要求低带宽要求低.29ECC和和RSA性能比较性能比较ECC密钥长度密钥长度mRSA密钥长度密钥长度MIPS-年年 160 10241012 320 51201036 600 210001078 1200 1200001016830同等安全强度下密钥大小的比较同等安全强度下密钥大小的比较Symmetric scheme(key size in bits)ECC-based scheme(size of n in bits)RSA/DSA(modulus size in bits)561
18、125128016010241122242048128256307219238476802565121536031基于公钥密码的基于公钥密码的PRNG32协商大素数p，本原根g选择随机数XA、XB计算YA=gXA，YB=gXB (mod p)Alice计算K= (YB ) XA(mod p); Bob计算K = (YA ) XB(mod p), K = K =g XA XB(mod p)协商大素数q，本原根选择随机数XAAlice计算YA= XA (mod q); PU= q, , YA SU= XAK = K =g XA XB(mod P)Bob随机选择k，K= YakC1= k, C2=KMAliceK=C1XAM=C2K-1
