密码编码学与网络安全（第五版）课件：07-密钥管理和其它公钥密码体制

Chapter10

密钥管理和其它公钥密码体制

WhyPublicKeyCryptography?私钥密码体制的一个问题如何解决这些问题?要进行保密通信，事先不秘密传送密钥行不行？已学到的方法AliceBob带一把锁的对称密码体制能否实现？Shamir盒AliceBob对你的启示？WhitfieldDiffie&MartinHellman

"NewDirectionsinCryptography",IEEETrans.InformationTheory,IT-22,pp644-654,Nov19761.不事先交换密钥就能进行秘密通信2.加密、解密的密钥可以分开2023/1/11华中农业大学信息学院7§10.1Diffie-Hellman密钥交换第一个公钥算法

1976由Diffie和Hellman提出DH算法是一个实用的密钥公开交换的算法算法本身只限于进行密钥交换已应用在许多商业产品中“Newdirectionsincryptography”2023/1/11华中农业大学信息学院82023/1/11华中农业大学信息学院9Diffie-Hellman密钥交换是一个公钥分配方案不能用于交换任意的消息只限于进行公共密钥的建立只对通信的双方已知密钥的值依赖于通信的参与者(以及他们的私钥和公钥信息）有限域中的指数运算（模一个素数）是相对容易的，而离散对数的计算是相对困难的。2023/1/11华中农业大学信息学院102023/1/11华中农业大学信息学院11Diffie-Hellman的建立所有用户均已知全局参数:一个大素整数(或多项式)：q一个模q的本原根：α每个用户(如A)产生自己的密钥选择一个保密的随机数:xA<q计算其公钥:yA=αxAmodq

每个用户公开其公钥yA2023/1/11华中农业大学信息学院12Diffie-Hellman密钥交换用户A和B共享的会话密钥是KAB:KAB=αxA.xBmodq=yAxBmodq(whichBcancompute)=yBxAmodq(whichAcancompute)会话密钥KAB

作为A和B两个用户在传统密码体制中的共享密钥来使用的可以一直使用前面产生的会话密钥，直到想重新选择新的会话密钥为止。攻击者需要解出x,必须求解离散对数。2023/1/11华中农业大学信息学院13Diffie-Hellman举例用户Alice和Bob想交换密钥:双方同意使用全局参数q=353和α=3随机选择一个保密的私钥:A选择xA=97,B选择xB=233分别计算各自的公钥:yA=397mod353=40 (Alice)yB=3233mod353=248 (Bob)计算共享的会话密钥:KAB=yBxAmod353=24897=160 (Alice)KAB=yAxBmod353=40233=160 (Bob)2023/1/11华中农业大学信息学院14密钥交换协议用户在每一次通信时都产生随机的公开的和保密的DH密钥对用户产生D-H密钥对，并公开其公钥在一个目录中，需要与其进行保密通信时，查询并使用这个目录。上述两种情况都存在中间相遇攻击认证是需要的2023/1/11华中农业大学信息学院15DH交换的中间人攻击(1)Darth生成两个随机数XD1和XD2，随后计算相应的公钥YD1和YD2；(2)Alice将YA传递给Bob；(3)Darth截获了YA，将YD1传给Bob，同时计算(4)Bob收到YD1，计算(5)Bob将YB传给Alice；(6)Darth截获了YB，将YD2传给Alice，Darth计算(7)Alice收到YD2，计算2023/1/11华中农业大学信息学院16DH交换的中间人攻击(1)Alice发送机密消息M：E(K2，M)；(2)Darth截获了该消息，解密，恢复出M；(3)Darth将E(K1，M)或E(K1，M’)发送给Bob。TaherElgamal在1984和1985年间提出了一种基于离散对数问题的公钥密码体系，其类似于Diffie-Hellman的密钥协商协议。§10.2ElGamal密码体系2023/1/11华中农业大学信息学院182023/1/11华中农业大学信息学院19ElGamal举例-加密

Alice选择XA=5；

计算Alice的私钥为5；公钥为

假如Bob想将值M=17发送，则作如下计算：(1)Bob选择k=6(2)计算(3)计算Bob发送密文（11,5）ElGamal举例-解密

Alice选择

在GF(19)中

计算安全性

对于给定的参数，破解ElGamal相当于解Diffie-Hellman问题。实际上，ElGamal可以被看成是Diffie-Hellman密钥的一种变形，基于这个原因，ElGamal的安全性依赖于Zp*上的离散对数问题;在加密过程中，对不同的消息m都应选取不同的随机数k，否则的话，攻击者可以很容易攻击ElGamal公钥体系。攻击举例-k

如果k用于多个分块，利用信息的分块m1，攻击者计算

于是

若M1已知，很容易计算M22023/1/11华中农业大学信息学院24§10.3椭圆曲线密码学EllipticCurveCryptography2023/1/1125概述获得同样的安全性，密钥长度较RSA短得多被IEEE公钥密码标准P1363采用2023/1/1126椭圆曲线椭圆曲线的曲线方程是以下形式的三次方程y2+axy+by=x3+cx2+dx+ea,b,c,d,e是满足某些简单条件的实数。定义中包含一个称为无穷远点的元素，记为O.2023/1/1127椭圆曲线加法的定义如果其上的3个点位于同一直线上，那么它们的和为O。O为加法单位元，即对ECC上任一点P,有P+O=P设P1=(x,y)是ECC上一点，加法逆元定义为P2=-P1=(x,-y)P1,P2连线延长到无穷远，得到ECC上另一点O,即P1,P2,O三点共线，所以P1+P2+O=O,P1+P2=O,P2=-P1O＋O＝O,O=-O2023/1/1128椭圆曲线加法的定义Q,R是ECC上x坐标不同的两点，Q+R定义为：画一条通过Q,R的直线与ECC交于P1(交点是唯一的，除非做的Q,R点的切线，此时分别取P1=Q或P1=R)。由Q+R+P1=O,得Q+R=-P1点Q的倍数定义如下：在Q点做ECC的一条切线，设切线与ECC交于S,定义2Q=Q+Q=-S。类似可定义3Q=Q+Q+Q,…,上述加法满足加法的一般性质，如交换律、结合律等2023/1/1129有限域上的椭圆曲线曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+bmod(p)(a,b∈GF(p),4a3+27b2≠0modp)例：p=23,a=b=1,4a3+27b2=8≠0(mod23),方程为y2=x3+x+1mod(p)，图形为连续图形。我们感兴趣的是在第一象限的整数点。设Ep(a,b)表示ECC上点集{(x,y)|0≤x<p,0≤y<p,且x,y均为整数}并上O.

2023/1/1130有限域上的椭圆曲线点集产生方法对每一x(0≤x<p且x为整数），计算x3+ax+bmodp决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两个平方根。2023/1/1131Ep(a,b)上加法如果P,Q∈Ep(a,b)P+O=P如果P＝(x,y),则(x,y)+(x,-y)＝OP＝(x1,y1),Q=(x2,y2),P≠-Q,P+Q=(x3,y3)x3=l2-x1-x2（modp）y3=l(x1-x3)-y1(modp)2023/1/1132例：E23(1,1)P=(3,10),Q(=9,7)2023/1/1133ECC上的密码ECC上的离散对数问题在ECC构成的交换群Ep(a,b)上考虑方程Q＝kP，P,Q∈Ep(a,b),k<p.由k和P求Q容易，由P,Q求k则是困难的。由ECC上离散对数问题可以构造Diffie-Hellman密钥交换和Elgamal密码体制2023/1/11华中农业大学信息学院34同等安全强度下密钥大小的比较Symmetricscheme(keysizeinbits)ECC-basedscheme(sizeofninbits)RSA/DSA(modulussizein