《密钥管理及其他公钥体制》由会员分享，可在线阅读，更多相关《密钥管理及其他公钥体制（22页珍藏版）》请在金锄头文库上搜索。
1、Copyright by 王鲲鹏 2012年年3月月18日日计算机安全技术与实践计算机安全技术与实践 密钥管理和其他公钥密码体制密钥管理和其他公钥密码体制Copyright by 王鲲鹏 10.1 Diffie-Hellman密钥交换密钥交换离散对数问题离散对数问题ygx mod p，其中，其中g是生成元是生成元求求x的困难性的困难性目前没有有效的方法目前没有有效的方法实际使用时常用实际使用时常用Zp*和和ECC上的点加法群上的点加法群 Pohlig-Hellman algorithm如果如果p-1是小素数的乘积，则易求是小素数的乘积，则易求因此，因此，p-1应含有大素因子应含有大素因子Cop
2、yright by 王鲲鹏 Diffie-Hellman密钥交换协议密钥交换协议 DH76，Diffie-Hellman步骤步骤选取大素数选取大素数q和它的一个生成元和它的一个生成元g，这些参数公开，这些参数公开A选择随机数选择随机数Xa，B选择随机数选择随机数Xb A计算计算YagXa mod q，B计算计算YbgXb mod q 交换交换Ya，YbA计算计算KYbXa mod q，B计算计算KYaXb mod q 事实上，事实上，KKCopyright by 王鲲鹏 证明、分析和例子证明、分析和例子证明证明KKKYbXa mod qKYaXb mod q (gXb)Xa mod q (gX
3、a)Xb mod q g(XbXa) mod q g(XaXb) mod q举例举例 q97，g5A选选Xa36，B选选Xb58，则，则Ya5369750，Yb5589744交换交换50，44A算算K44369775，B算算K50589775分析（别人怎么计算分析（别人怎么计算K?）别人看到了别人看到了Ya和和Yb，但需要计算，但需要计算Xa或或Xb，即要算离散对数，即要算离散对数YagXa mod q，或，或YbgXb mod qCopyright by 王鲲鹏 中间人攻击中间人攻击交换交换Y的过程中，的过程中，Y有可能被替换假冒，而且不能有可能被替换假冒，而且不能发现发现形式上，可以理解为
4、一个中间人在跟双方同时通形式上，可以理解为一个中间人在跟双方同时通信，当然通信内容在中间人那里是可见的信，当然通信内容在中间人那里是可见的* 一个现实的例子就是：可以同时开两盘一个现实的例子就是：可以同时开两盘QQx棋，棋，一个后手，一个先手，一个后手，一个先手，Copyright by 王鲲鹏 Man-in-the-middleAEBXaXb XaXbYaYb YaYbK=YbXaK=YaXbCopyright by 王鲲鹏 相关结论相关结论maurer94towardsTowards the Equivalence of Breaking the Diffie-Hellman Protoc
5、ol and Computing Discrete Logarithmshttp:/ by 王鲲鹏 10.1a PKCS#3PKCS#3 Diffie-Hellman Key-Agreement Standard进一步参阅进一步参阅 pkcs#3PVpublic valuepprimePVothers public valuexprivate valueSKsecret keyxothers private valueg baseyinteger public valuek length of prime in octetsyothers integer public valuellength
6、 of private value in bitszinteger secret keymod n modulo nCopyright by 王鲲鹏 10.2 ElGamal密码体制密码体制准备准备素数素数p，Zp*中本原元中本原元g，公开参数，公开参数私钥私钥a，公钥，公钥b=ga mod p加密加密对明文对明文1=m=p-1，选随机数，选随机数k密文密文(c1, c2)c1=gk mod p, c2=mbk mod p解密解密mc2 (c1a)-1mbk (gk)a)-1 m(ga)k (g-ka) m mod pCopyright by 王鲲鹏 ElGamal etc基于离散对数难题基于
7、离散对数难题缺点缺点需要随机数需要随机数密文长度加倍密文长度加倍ElGamal可以迁移到可以迁移到ECDLP上上ElGamal签名和签名和DSSCopyright by 王鲲鹏 10.3 椭圆曲线椭圆曲线背景背景RSA中用到了因子分解的困难性，而为了增加困难得加中用到了因子分解的困难性，而为了增加困难得加大数的位数，从而导致计算速度变慢。大数的位数，从而导致计算速度变慢。ECC可以用较小的密钥长度达到较高的计算难度可以用较小的密钥长度达到较高的计算难度Elliptic Curvey2axybyx3cx2dxe其中其中a、b、c、d、e是满足某个简单条件的实数是满足某个简单条件的实数另有另有O点
8、被定义为无穷点点被定义为无穷点/零点零点点加法点加法PQR定义为定义为过过P、Q和椭圆曲线相交的第三点的和椭圆曲线相交的第三点的X轴对称点轴对称点RCopyright by 王鲲鹏 EC：PQR Copyright by 王鲲鹏 素域上的素域上的EC 在有限域在有限域Zp上的简化上的简化ECy2x3axb mod p 其中其中4a327b2 mod p 0（这是一个离散点的集合）（这是一个离散点的集合）举例举例y2x318x15 mod 23 y2x317x15 mod 23Copyright by 王鲲鹏 EC (1) Copyright by 王鲲鹏 EC (2)Copyright by
9、王鲲鹏 EC上的离散对数问题（上的离散对数问题（ECDLP）QkP中的中的k计算也是极其困难的计算也是极其困难的kP表示表示k个个P相加：相加：P + P + + P在在DH密钥交换中密钥交换中使用了使用了ygx mod p中中x的计算困难性的计算困难性同样在同样在ECC中中将使用将使用QkP中计算中计算k的困难性的困难性有两个应用有两个应用密钥交换密钥交换加密解密加密解密Copyright by 王鲲鹏 10.4 椭圆曲线密码学椭圆曲线密码学ECCECC利用利用EC上的离散对数难题上的离散对数难题(ECDLP)，这和利，这和利用用Zp*上的离散对数难题上的离散对数难题(DLP)是一样的方法。
10、是一样的方法。在一般数域上的离散对数问题（以及大数分解问题）在一般数域上的离散对数问题（以及大数分解问题）存在亚指数级时间复杂度求解算法，而存在亚指数级时间复杂度求解算法，而ECDLP只有只有纯指数算法。纯指数算法。Copyright by 王鲲鹏 使用使用EC的密钥交换（的密钥交换（D-H）步骤步骤y2x3axb mod p 选择素数选择素数p(得约得约160比特比特)和参数和参数a、b选择一个生成点选择一个生成点G(x1，y1)p、a、b和点和点G是公开的是公开的A：选取秘密的数：选取秘密的数Na，计算，计算PaNaGB：选取秘密的数：选取秘密的数Nb，计算，计算PbNbG交换交换Pa，P
11、bA：计算：计算KNaPbNaNbGB：计算：计算KNbPaNbNaG分析分析攻击者得求攻击者得求Na和和Nb，就是，就是P?G中的中的?Copyright by 王鲲鹏 用用EC的加解密的加解密准备准备曲线参数曲线参数p、a、b、G，y2x3axb mod p A有自己的私钥有自己的私钥Na，并产生公钥，并产生公钥PaNaGB有自己的私钥有自己的私钥Nb，并产生公钥，并产生公钥PbNbG加密加密 （A要给要给B发送消息）发送消息）对明文对明文m的编码点的编码点Pm，选择随机数，选择随机数k，密文，密文CC1，C2 kG，PmkPb解密：解密：编码点编码点PmC2NbC1，因为，因为 (Pmk
12、Pb)NbkG PmkNbGNbkG PmCopyright by 王鲲鹏 用用EC的加解密的加解密原理原理先是通过先是通过kPb掩盖掩盖Pm (即即m)，又通过，又通过kG掩盖掩盖k知道陷门知道陷门Nb则可以轻松恢复之则可以轻松恢复之分析分析攻击者解攻击者解C1kG中的中的k困难性困难性Copyright by 王鲲鹏 关于速度关于速度速度速度在密钥长度相等的情况下，在密钥长度相等的情况下，RSA和和ECC的速度相当；的速度相当；但是在相同的安全强度要求下，但是在相同的安全强度要求下，ECC可以使用较少的位可以使用较少的位数就可以；数就可以；故故ECC较好较好适合嵌入式设备中适合嵌入式设备中Copyright by 王鲲鹏 ECC vs. RSA
