网络安全-09-密钥管理和其它公钥密码体制-DH-ElGamal-ECC要点

Chapter10

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

《计算机与网络安全》

2026/3/29西安电子科技大学计算机学院2§10.1Diffie-Hellman密钥交换第一个公钥算法

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

每个用户公开其公钥yA2026/3/29西安电子科技大学计算机学院7Diffie-Hellman密钥交换用户A和B共享的会话密钥是KAB:KAB=αxA.xBmodq=yAxBmodq(whichBcancompute)=yBxAmodq(whichAcancompute)会话密钥KAB

作为A和B两个用户在传统密码体制中的共享密钥来使用的可以一直使用前面产生的会话密钥，直到想重新选择新的会话密钥为止。攻击者需要解出x,必须求解离散对数。2026/3/29西安电子科技大学计算机学院8Diffie-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)2026/3/29西安电子科技大学计算机学院9密钥交换协议用户在每一次通信时都产生随机的公开的和保密的DH密钥对用户产生D-H密钥对，并公开其公钥在一个目录中，需要与其进行保密通信时，查询并使用这个目录。上述两种情况都存在中间相遇攻击认证是需要的2026/3/29西安电子科技大学计算机学院10DH交换的中间人攻击(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，计算2026/3/29西安电子科技大学计算机学院11DH交换的中间人攻击(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密码体系ElGamal算法2026/3/29西安电子科技大学计算机学院13ElGamal举例-加密

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的安全性依赖于Zp*上的离散对数问题;在加密过程中，对不同的消息m都应选取不同的随机数k，

否则的话，攻击者可以很容易攻击ElGamal公钥体系。攻击举例-k

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

于是

若M1已知，很容易计算M2ElGamaletc缺点需要随机数密文长度加倍ElGamal可以迁移到ECDLP上ElGamal签名和DSS§10.3椭圆曲线密码学背景RSA中用到了因子分解的困难性，而为了增加困难得加大数的位数，从而导致计算速度变慢。ECC可以用较小的密钥长度达到较高的计算难度EllipticCurve

y2＋axy＋by＝x3＋cx2＋dx＋e其中a、b、c、d、e是满足某个简单条件的实数另有O点被定义为无穷点/零点点加法P＋Q＝R定义为过P、Q和椭圆曲线相交的第三点的X轴对称点R EC：P＋Q＝R

EC：P＋P＝2P2026/3/29西安电子科技大学计算机学院21素域上的EC在有限域Zp上的简化EC y2≡x3＋ax＋bmodp其中4a3＋27b2modp≠0（这是一个离散点的集合）举例

y2≡x3＋18x＋15mod23

y2≡x3＋17x＋15mod23EC(1)

EC(2)EC上的离散对数问题（ECDLP）Q＝kP中的k计算也是极其困难的

kP表示k个P相加：P+P+…+P在DH密钥交换中 使用了y＝gxmodp中x的计算困难性 同样在ECC中 将使用Q＝kP中计算k的困难性有两个应用 密钥交换 加密解密使用EC的密钥交换（D-H）步骤y2≡x3＋ax＋bmodp

选择素数p(得约160＋比特)和参数a、b

选择一个生成点G＝(x1，y1) p、a、b和点G是公开的A：选取秘密的数ra，计算Pa＝raG B：选取秘密的数rb，计算Pb＝rbG

交换Pa，Pb A：计算K＝raPb＝rarbG B：计算K’＝rbPa＝rbraG分析攻击者得求ra和rb，就是P＝rG中的r用EC的加解密(Elgamal)准备曲线参数p、a、b、G，y2≡x3＋ax＋bmodp

A有自己的私钥ra，并产生公钥Pa＝raGB有自己的私钥rb，并产生公钥Pb＝rbG加密（A要给B发送消息）对明文m的编码点Pm，选择随机数k，密文

C＝{C1，C2}＝{kG，Pm＋kPb}解密：编码点Pm＝C2－rbC1，因为 ＝(Pm＋kPb)－rb×kG

＝Pm＋k×rbG－rb×kG＝Pm2026/3/29西安电子科技大学计算机学院28同等安全强度下密钥大小的比较Symmetricscheme(keysizeinbits)ECC-basedscheme(sizeofninbits)RSA/DSA(modulussizeinbits)56112512801601024112224204812825630721923847680