1、Chapter 10 密钥管理和其它公钥密码体制密钥管理和其它公钥密码体制 Why Public Key Cryptography?n私钥密码体制的一个问题如何解决这些问题?要进行保密通信，事先不秘密传送密钥行不行？已学到的方法AliceBob带一把锁的对称密码体制能否实现？Shamir盒AliceBob对你的启示？Whitfield Diffie & Martin Hellman New Directions in Cryptography, IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976 1.不事先交换密钥就能进行秘密通
2、信 2.加密、解密的密钥可以分开2022-1-20华中农业大学信息学院710.1 Diffie-Hellman密钥交换密钥交换n第一个公钥算法第一个公钥算法 n1976由由Diffie 和和 Hellman 提出提出nDH算法是一个实用的密钥公开交换的算法算法是一个实用的密钥公开交换的算法n算法本身只限于进行密钥交换算法本身只限于进行密钥交换n已应用在许多商业产品中已应用在许多商业产品中n“New directions in cryptography ”2022-1-20华中农业大学信息学院82022-1-20华中农业大学信息学院9Diffie - Hellman密钥交换密钥交换n是一个公钥分
3、配方案是一个公钥分配方案q不能用于交换任意的消息不能用于交换任意的消息q只限于进行公共密钥的建立只限于进行公共密钥的建立q只对通信的双方已知只对通信的双方已知n密钥的值依赖于通信的参与者密钥的值依赖于通信的参与者 (以及他们的以及他们的私钥和公钥信息）私钥和公钥信息）n有限域中的指数运算（模一个素数）是相对有限域中的指数运算（模一个素数）是相对容易的，而离散对数的计算是相对困难的。容易的，而离散对数的计算是相对困难的。2022-1-20华中农业大学信息学院102022-1-20华中农业大学信息学院11Diffie-Hellman的建立的建立n所有用户均已知全局参数所有用户均已知全局参数:q一个
4、大素整数一个大素整数(或多项式或多项式)：qq一个模一个模 q 的本原根：的本原根：n每个用户每个用户 (如如 A) 产生自己的密钥产生自己的密钥q选择一个保密的随机数选择一个保密的随机数: xA q q计算其公钥计算其公钥: yA = xA mod qn 每个用户公开其公钥每个用户公开其公钥 yA2022-1-20华中农业大学信息学院12Diffie-Hellman密钥交换密钥交换n用户用户A 和和 B共享的会话密钥是共享的会话密钥是 KAB: KAB = xA.xB mod q= yAxB mod q (which B can compute) = yBxA mod q (which A
5、can compute) n会话密钥会话密钥KAB 作为作为A和和B两个用户在传统密码体制中的两个用户在传统密码体制中的共享密钥来使用的共享密钥来使用的n可以一直使用前面产生的会话密钥，直到想重新选择新可以一直使用前面产生的会话密钥，直到想重新选择新的会话密钥为止。的会话密钥为止。n攻击者需要解出攻击者需要解出x, 必须求解离散对数。必须求解离散对数。2022-1-20华中农业大学信息学院13Diffie-Hellman 举例举例n用户用户 Alice 和和 Bob 想交换密钥想交换密钥:n双方同意使用全局参数双方同意使用全局参数 q = 353 和和=3n随机选择一个保密的私钥随机选择一个保
6、密的私钥:qA 选择选择 xA = 97, B 选择选择 xB = 233n分别计算各自的公钥分别计算各自的公钥:qyA=397 mod 353 = 40(Alice)qyB=3233 mod 353 = 248(Bob)n计算共享的会话密钥计算共享的会话密钥:qKAB= yBxA mod 353 = 24897 = 160(Alice)qKAB= yAxB mod 353 = 40233 = 160 (Bob)2022-1-20华中农业大学信息学院14密钥交换协议密钥交换协议n用户在每一次通信时都产生随机的公开的和保密用户在每一次通信时都产生随机的公开的和保密的的DH密钥对密钥对n用户产生用
7、户产生D-H密钥对，并公开其公钥在一个目录密钥对，并公开其公钥在一个目录中，需要与其进行保密通信时，查询并使用这个中，需要与其进行保密通信时，查询并使用这个目录。目录。n上述两种情况都存在中间相遇攻击上述两种情况都存在中间相遇攻击n认证是需要的认证是需要的2022-1-20华中农业大学信息学院15DH交换的中间人攻击交换的中间人攻击n(1) Darth生成两个随机数生成两个随机数XD1和和XD2，随后计算相，随后计算相应的公钥应的公钥YD1和和YD2；n(2) Alice将将YA传递给传递给Bob；n(3) Darth截获了截获了YA，将，将YD1传给传给Bob，同时计算，同时计算n(4) B
8、ob收到收到YD1，计算，计算n (5) Bob将将YB传给传给Alice；n(6) Darth截获了截获了YB，将，将YD2传给传给Alice，Darth计算计算n(7) Alice收到收到YD2，计算，计算22()modDXAKYq11()modBXDKYq11()modDXBKYq22()modAXDKYq2022-1-20华中农业大学信息学院16DH交换的中间人攻击交换的中间人攻击n(1) Alice 发送机密消息发送机密消息 M：E(K2，M)；n(2) Darth 截获了该消息，解密，恢复出截获了该消息，解密，恢复出M；n(3) Darth 将将E(K1，M)或或 E (K1，M)
9、发送给发送给Bob。n Taher Elgamal在1984和1985年间提出了一种基于离散对数问题的公钥密码体系，其类似于Diffie-Hellman的密钥协商协议。10.2 ElGamal密码体系密码体系2022-1-20华中农业大学信息学院182022-1-20华中农业大学信息学院19ElGamal举例举例-加密加密 Alice选择XA=5； 计算 Alice的私钥为5；公钥为 假如Bob想将值M=17发送，则作如下计算： (1) Bob选择 k = 6 (2) 计算 (3) 计算 Bob发送密文（11, 5）5modmod193AXAYq , ,19,10,3AqY6() mod3 m
10、od19729mod197kAKYq612mod10 mod1911mod7 17mod19119mod195kCqCKMqElGamal举例举例-解密解密 Alice选择 在GF(19) 中 计算 A51()mod11 mod197XKCq117mod1911K12()mod5 11mod1917MC Kq安全性安全性 p 对于给定的参数，破解ElGamal相当于解Diffie-Hellman问题。实际上，ElGamal可以被看成是Diffie-Hellman密钥的一种变形，基于这个原因，ElGamal的安全性依赖于Zp*上的离散对数问题;p在加密过程中，对不同的消息m都应选取不同的随机数k
11、，否则的话，攻击者可以很容易攻击ElGamal公钥体系。攻击举例攻击举例-k 如果k用于多个分块，利用信息的分块m1，攻击者计算1,12,111,22,22mod ;modmod ;modkkCq CKMqCq CKMq 于是 2,1112,222modmodmodmodCKMqMqCKMqMq 若M1已知，很容易计算M2122,12,21()modMCCMq2022-1-20华中农业大学信息学院2410.3 椭圆曲线密码学椭圆曲线密码学nElliptic Curve Cryptography2022-1-2025概述概述n获得同样的安全性，密钥长度较获得同样的安全性，密钥长度较RSARSA短
12、得多短得多n被被IEEEIEEE公钥密码标准公钥密码标准P1363P1363采用采用2022-1-2026椭圆曲线椭圆曲线n椭圆曲线的曲线方程是以下形式的三次方程椭圆曲线的曲线方程是以下形式的三次方程y y2 2+axy+by=x+axy+by=x3 3+cx+cx2 2+dx+e+dx+ea,b,c,d,ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个称是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为为无穷远点的元素，记为OO.2022-1-2027椭圆曲线加法的定义椭圆曲线加法的定义n如果其上的如果其上的3 3个点位于同一直线上，那么它们个点位于同一直线上，那么
13、它们的和为的和为OO。qOO为加法单位元，即对为加法单位元，即对ECCECC上任一点上任一点P,P,有有P+O=PP+O=Pq设设P P1 1=(x,y)=(x,y)是是ECCECC上一点，加法逆元定义为上一点，加法逆元定义为P P2 2=-=-P P1 1=(x,-y)=(x,-y)nP P1 1,P,P2 2连线延长到无穷远，得到连线延长到无穷远，得到ECCECC上另一点上另一点O,O,即即P P1 1,P,P2 2,O,O三点共线，所以三点共线，所以P P1 1+P+P2 2+O=O, P+O=O, P1 1+P+P2 2=O, P=O, P2 2=-P=-P1 1nOOOOO,O=-O
14、O,O=-O2022-1-2028椭圆曲线加法的定义椭圆曲线加法的定义qQ,RQ,R是是ECCECC上上x x坐标不同的两点，坐标不同的两点，Q+RQ+R定义为：画一定义为：画一条通过条通过Q,RQ,R的直线与的直线与ECCECC交于交于P P1 1( (交点是唯一的，除交点是唯一的，除非做的非做的Q,RQ,R点的切线，此时分别取点的切线，此时分别取P P1 1=Q=Q或或P P1 1=R)=R)。由由Q+R+PQ+R+P1 1=O,=O,得得Q+R=-PQ+R=-P1 1q点点QQ的倍数定义如下：在的倍数定义如下：在QQ点做点做ECCECC的一条切线，的一条切线，设切线与设切线与ECCECC
15、交于交于S, S,定义定义2Q=Q+Q=-S2Q=Q+Q=-S。类似可定。类似可定义义3Q=Q+Q+Q,3Q=Q+Q+Q, ,q上述加法满足加法的一般性质，如交换律、结合律上述加法满足加法的一般性质，如交换律、结合律等等2022-1-2029有限域上的椭圆曲线有限域上的椭圆曲线n曲线方程中的所有系数都是某一有限域曲线方程中的所有系数都是某一有限域GF(p)GF(p)中的元素中的元素(p(p为一大素数为一大素数) )，最为常用的曲线方程为，最为常用的曲线方程为y2=x3+ax+b mod(p) (a,bGF(p),4a3+27b20 mod p)n例：例：p=23,a=b=1, 4a4a3 3+
16、27b+27b2 2=8 =8 0 (mod23),方程为方程为y2=x3+x+1 mod(p)，图形为连续图形。我们感兴趣的图形为连续图形。我们感兴趣的是在第一象限的整数点。设是在第一象限的整数点。设Ep(a,b)表示表示ECC上点集上点集(x,y)|0 xp,0 yp,x,y)|0 xp,0 yp,且且x,yx,y均为整数均为整数并上并上O. 2022-1-2030有限域上的椭圆曲线点集产生方法有限域上的椭圆曲线点集产生方法n对每一x(0 xp0 xp且且x x为整数），计算为整数），计算x x3 3+ax+b +ax+b mod pmod pn决定求出的值在模决定求出的值在模p p下是否
17、有平方根，如果没有下是否有平方根，如果没有则椭圆曲线上没有与这一则椭圆曲线上没有与这一x x对应的点；如果有，对应的点；如果有，则求出两个平方根。则求出两个平方根。2022-1-2031E Ep p(a,b)(a,b)上加法上加法n如果如果P,Q EP,Q Ep p(a,b)(a,b)qP+O=PP+O=Pq如果如果P P(x,y),(x,y),则则(x,y)+(x,-y)(x,y)+(x,-y)OOqP P(x(x1 1,y,y1 1),Q= (x),Q= (x2 2,y,y2 2),P),P-Q,P+Q= (x(x3 3,y,y3 3) )x x3 3=l l2 2-x-x1 1-x-x2
18、 2（mod pmod p）y y3 3=l l(x(x1 1-x-x3 3)-y)-y1 1 (mod p) (mod p)QPyaxQPxxyy121121223l2022-1-2032例：E23(1,1)nP=(3,10),Q(=9,7)12, 7(223mod123410)73(623mod73033623mod641205102133:2) 1 , 1 ()20,17(23mod2016410)173(1123mod17109931123mod11222216339107323223323PyxPEQPyxll2022-1-2033ECCECC上的密码上的密码nECCECC上的离散对
19、数问题上的离散对数问题q在在ECCECC构成的交换群构成的交换群E Ep p(a,b)(a,b)上考虑方程上考虑方程QQkPkP，P,QEP,QEp p(a,b),kp.(a,b),kp.由由k k和和P P求求QQ容易，由容易，由P,QP,Q求求k k则是则是困难的。困难的。n由由ECCECC上离散对数问题可以构造上离散对数问题可以构造Diffie-Diffie-HellmanHellman密钥交换和密钥交换和ElgamalElgamal密码体制密码体制2022-1-20华中农业大学信息学院34同等安全强度下密钥大小的比较同等安全强度下密钥大小的比较Symmetric scheme(key
20、size in bits)ECC-based scheme(size of n in bits)RSA/DSA(modulus size in bits)56112512801601024112224204812825630721923847680256512153602022-1-20华中农业大学信息学院35小小 结结q 公钥的分配公钥的分配q 用公钥实现传统密码体制中秘密钥的分配用公钥实现传统密码体制中秘密钥的分配q Diffie-Hellman密钥交换协议密钥交换协议q ElGamal密码体系密码体系q 椭圆曲线密码学（略）椭圆曲线密码学（略）2022-1-20华中农业大学信息学院36作业作业n习题习题 ：10.1 10.2
