1、Chapter 10 密钥管理和其它公钥密码体制密钥管理和其它公钥密码体制 2022-5-31西安电子科技大学计算机学院210.1 Diffie-Hellman密钥交换密钥交换n第一个公钥算法第一个公钥算法 n1976由由Diffie 和和 Hellman 提出提出nDH算法是一个实用的密钥公开交换的算法算法是一个实用的密钥公开交换的算法n算法本身只限于进行密钥交换算法本身只限于进行密钥交换n已应用在许多商业产品中已应用在许多商业产品中n“New directions in cryptography ”2022-5-31西安电子科技大学计算机学院32022-5-31西安电子科技大学计算机学院4
2、Diffie - Hellman密钥交换密钥交换n是一个公钥分配方案是一个公钥分配方案q不能用于交换任意的消息不能用于交换任意的消息q只限于进行公共密钥的建立只限于进行公共密钥的建立q只对通信的双方已知只对通信的双方已知n密钥的值依赖于通信的参与者密钥的值依赖于通信的参与者 (以及他们的以及他们的私钥和公钥信息）私钥和公钥信息）n有限域中的指数运算（模一个素数）是相对有限域中的指数运算（模一个素数）是相对容易的，而离散对数的计算是相对困难的。容易的，而离散对数的计算是相对困难的。2022-5-31西安电子科技大学计算机学院52022-5-31西安电子科技大学计算机学院6Diffie-Hellm
3、an的建立的建立n所有用户均已知全局参数所有用户均已知全局参数:q一个大素整数一个大素整数(或多项式或多项式)：qq一个模一个模 q 的本原根：的本原根：n每个用户每个用户 (如如 A) 产生自己的密钥产生自己的密钥q选择一个保密的随机数选择一个保密的随机数: xA q q计算其公钥计算其公钥: yA = xA mod qn 每个用户公开其公钥每个用户公开其公钥 yA2022-5-31西安电子科技大学计算机学院7Diffie-Hellman密钥交换密钥交换n用户用户A 和和 B共享的会话密钥是共享的会话密钥是 KAB: KAB = xA.xB mod q= yAxB mod q (which
4、B can compute) = yBxA mod q (which A can compute) n会话密钥会话密钥KAB 作为作为A和和B两个用户在传统密码体制中的两个用户在传统密码体制中的共享密钥来使用的共享密钥来使用的n可以一直使用前面产生的会话密钥，直到想重新选择新可以一直使用前面产生的会话密钥，直到想重新选择新的会话密钥为止。的会话密钥为止。n攻击者需要解出攻击者需要解出x, 必须求解离散对数。必须求解离散对数。2022-5-31西安电子科技大学计算机学院8Diffie-Hellman 举例举例n用户用户 Alice 和和 Bob 想交换密钥想交换密钥:n双方同意使用全局参数双方同
5、意使用全局参数 q = 353 和和=3n随机选择一个保密的私钥随机选择一个保密的私钥: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-5-31西安电子科技大学计算机学院9密钥交换协议密钥交换协议n用户在每一次通信时都产生随机的公开
6、的和保密用户在每一次通信时都产生随机的公开的和保密的的DH密钥对密钥对n用户产生用户产生D-H密钥对，并公开其公钥在一个目录密钥对，并公开其公钥在一个目录中，需要与其进行保密通信时，查询并使用这个中，需要与其进行保密通信时，查询并使用这个目录。目录。n上述两种情况都存在中间相遇攻击上述两种情况都存在中间相遇攻击n认证是需要的认证是需要的2022-5-31西安电子科技大学计算机学院10DH交换的中间人攻击交换的中间人攻击n(1) Darth生成两个随机数生成两个随机数XD1和和XD2，随后计算相，随后计算相应的公钥应的公钥YD1和和YD2；n(2) Alice将将YA传递给传递给Bob；n(3)
7、 Darth截获了截获了YA，将，将YD1传给传给Bob，同时计算，同时计算n(4) Bob收到收到YD1，计算，计算n (5) Bob将将YB传给传给Alice；n(6) Darth截获了截获了YB，将，将YD2传给传给Alice，Darth计算计算n(7) Alice收到收到YD2，计算，计算22()modDXAKYq11()modBXDKYq11()modDXBKYq22()modAXDKYq2022-5-31西安电子科技大学计算机学院11DH交换的中间人攻击交换的中间人攻击n(1) Alice 发送机密消息发送机密消息 M：E(K2，M)；n(2) Darth 截获了该消息，解密，恢复
8、出截获了该消息，解密，恢复出M；n(3) Darth 将将E(K1，M)或或 E (K1，M)发送给发送给Bob。n Taher Elgamal在1984和1985年间提出了一种基于离散对数问题的公钥密码体系，其类似于Diffie-Hellman的密钥协商协议。10.2 ElGamal密码体系密码体系ElGamal算法算法2022-5-31西安电子科技大学计算机学院13ElGamal举例举例-加密加密 Alice选择XA=5； 计算 Alice的私钥为5；公钥为 假如Bob想将值M=17发送，则作如下计算： (1) Bob选择 k = 6 (2) 计算 (3) 计算 Bob发送密文（11, 5
9、）5modmod193AXAYq , ,19,10,3AqY6() mod3 mod19729mod197kAKYq612mod10 mod1911mod7 17mod19119mod195kCqCKMqElGamal举例举例-解密解密 Alice选择 在GF(19) 中 计算 A51()mod11 mod197XKCq117mod1911K12()mod5 11mod1917MC Kq安全性安全性 p 破解ElGamal相当于解Diffie-Hellman问题。p ElGamal的安全性依赖于Zp*上的离散对数离散对数问题;p在加密过程中，对不同的消息m都应选取不同的随机数k， 否则的话，攻
10、击者可以很容易攻击ElGamal公钥体系。攻击举例攻击举例-k 如果k用于多个分块，利用信息的分块m1，攻击者计算1,12,111,22,22mod ;modmod ;modkkCq CKMqCq CKMq 于是 2,1112,222modmodmodmodCKMqMqCKMqMq 若M1已知，很容易计算M2122,12,21()modMCCMqElGamal etcn缺点q需要随机数q密文长度加倍nElGamal可以迁移到ECDLP上nElGamal签名和DSS10.3 椭圆曲线密码学椭圆曲线密码学n背景qRSA中用到了因子分解的困难性，而为了增加困难得加大数的位数，从而导致计算速度变慢。q
11、ECC可以用较小的密钥长度达到较高的计算难度nElliptic Curvey2axybyx3cx2dxeq其中a、b、c、d、e是满足某个简单条件的实数q另有O点被定义为无穷点/零点n点加法PQR定义为q过P、Q和椭圆曲线相交的第三点的X轴对称点REC：PQRn EC：PP2P2022-5-31西安电子科技大学计算机学院21素域上的EC n在有限域Zp上的简化ECy2x3axb mod p 其中4a327b2 mod p 0（这是一个离散点的集合）n举例y2x318x15 mod 23 y2x317x15 mod 23EC (1)n EC (2)EC上的离散对数问题（ECDLP）nQkP中的k
12、计算也是极其困难的kP表示k个P相加：P + P + + Pn在DH密钥交换中使用了ygx mod p中x的计算困难性同样在ECC中将使用QkP中计算k的困难性n有两个应用密钥交换加密解密使用EC的密钥交换（D-H）n步骤qy2x3axb mod p 选择素数p(得约160比特)和参数a、b选择一个生成点G(x1，y1)p、a、b和点G是公开的qA：选取秘密的数ra，计算ParaGB：选取秘密的数rb，计算PbrbG交换Pa，PbA：计算KraPbrarbGB：计算KrbParbraGn分析q攻击者得求ra和rb，就是PrG中的r用EC的加解密(Elgamal)n准备q曲线参数p、a、b、G，
13、y2x3axb mod p qA有自己的私钥ra，并产生公钥ParaGqB有自己的私钥rb，并产生公钥PbrbGn加密 （A要给B发送消息）q对明文m的编码点Pm，选择随机数k，密文CC1，C2 kG，PmkPbn解密：q编码点PmC2rbC1，因为 (PmkPb)rbkG PmkrbGrbkG Pm2022-5-31西安电子科技大学计算机学院28同等安全强度下密钥大小的比较同等安全强度下密钥大小的比较Symmetric scheme(key size in bits)ECC-based scheme(size of n in bits)RSA/DSA(modulus size in bits)5611251280160102411222420481282563072192384768025651215360关于速度n速度q在密钥长度相等的情况下，RSA和ECC的速度相当；q但是在相同的安全强度要求下，ECC可以使用较少的位数就可以；n故qECC较好q适合嵌入式设备中2022-5-31西安电子科技大学计算机学院30小小 结结q 公钥的分配公钥的分配q 用公钥实现传统密码体制中秘密钥的分配用公钥实现传统密码体制中秘密钥的分配q Diffie-Hellman密钥交换协议密钥交换协议q ElGamal密码体系密码体系q 椭圆曲线密码学椭圆曲线密码学
