《密钥管理及其他公钥体制.ppt》由会员分享,可在线阅读,更多相关《密钥管理及其他公钥体制.ppt(22页珍藏版)》请在三一文库上搜索。
1、2012年3月18日,计算机安全技术与实践 密钥管理和其他公钥密码体制,10.1 Diffie-Hellman密钥交换,离散对数问题 ygx mod p,其中g是生成元 求x的困难性 目前没有有效的方法 实际使用时常用Zp*和ECC上的点加法群 Pohlig-Hellman algorithm 如果p-1是小素数的乘积,则易求 因此,p-1应含有大素因子,Diffie-Hellman密钥交换协议,DH76,Diffie-Hellman 步骤 选取大素数q和它的一个生成元g,这些参数公开 A选择随机数Xa,B选择随机数Xb A计算YagXa mod q,B计算YbgXb mod q 交换Ya,Y
2、b A计算KYbXa mod q,B计算KYaXb mod q 事实上,KK,证明、分析和例子,证明KK KYbXa mod q KYaXb mod q (gXb)Xa mod q (gXa)Xb mod q g(XbXa) mod q g(XaXb) mod q 举例 q97,g5 A选Xa36,B选Xb58,则 Ya5369750,Yb5589744 交换50,44 A算K44369775,B算K50589775 分析(别人怎么计算K?) 别人看到了Ya和Yb,但需要计算Xa或Xb,即要算离散对数 YagXa mod q,或YbgXb mod q,中间人攻击,交换Y的过程中,Y有可能被替换
3、假冒,而且不能发现 形式上,可以理解为一个中间人在跟双方同时通信,当然通信内容在中间人那里是可见的 * 一个现实的例子就是:可以同时开两盘QQx棋,一个后手,一个先手,,Man-in-the-middle,A E B Xa Xb Xa Xb Ya Yb Ya Yb K=YbXa K=YaXb,相关结论,maurer94towards Towards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms http:/ 结论 破译D-H密钥协商协议等价于计算离散对数 RSA
4、算法的安全性是否等价于大数的因子分解?,10.1a PKCS#3,PKCS#3 Diffie-Hellman Key-Agreement Standard 进一步参阅 pkcs#3,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 p,ElGamal etc,基于离散对数难题 缺点 需要随机数 密文长度加倍 ElGamal可以迁移
5、到ECDLP上 ElGamal签名和DSS,10.3 椭圆曲线,背景 RSA中用到了因子分解的困难性,而为了增加困难得加大数的位数,从而导致计算速度变慢。 ECC可以用较小的密钥长度达到较高的计算难度 Elliptic Curve y2axybyx3cx2dxe 其中a、b、c、d、e是满足某个简单条件的实数 另有O点被定义为无穷点/零点 点加法PQR定义为 过P、Q和椭圆曲线相交的第三点的X轴对称点R,EC:PQR,素域上的EC,在有限域Zp上的简化EC y2x3axb mod p 其中4a327b2 mod p 0 (这是一个离散点的集合) 举例 y2x318x15 mod 23 y2x3
6、17x15 mod 23,EC (1),EC (2),EC上的离散对数问题(ECDLP),QkP中的k计算也是极其困难的 kP表示k个P相加:P + P + + P 在DH密钥交换中 使用了ygx mod p中x的计算困难性 同样在ECC中 将使用QkP中计算k的困难性 有两个应用 密钥交换 加密解密,10.4 椭圆曲线密码学ECC,ECC利用EC上的离散对数难题(ECDLP),这和利用Zp*上的离散对数难题(DLP)是一样的方法。 在一般数域上的离散对数问题(以及大数分解问题)存在亚指数级时间复杂度求解算法,而ECDLP只有纯指数算法。,使用EC的密钥交换(D-H),步骤 y2x3axb m
7、od p 选择素数p(得约160比特)和参数a、b 选择一个生成点G(x1,y1) p、a、b和点G是公开的 A:选取秘密的数Na,计算PaNaG B:选取秘密的数Nb,计算PbNbG 交换Pa,Pb A:计算KNaPbNaNbG B:计算KNbPaNbNaG 分析 攻击者得求Na和Nb,就是P?G中的?,用EC的加解密,准备 曲线参数p、a、b、G,y2x3axb mod p A有自己的私钥Na,并产生公钥PaNaG B有自己的私钥Nb,并产生公钥PbNbG 加密 (A要给B发送消息) 对明文m的编码点Pm,选择随机数k,密文 CC1,C2 kG,PmkPb 解密: 编码点PmC2NbC1,因为 (PmkPb)NbkG PmkNbGNbkG Pm,用EC的加解密,原理 先是通过kPb掩盖Pm (即m),又通过kG掩盖k 知道陷门Nb则可以轻松恢复之 分析 攻击者解C1kG中的k困难性,关于速度,速度 在密钥长度相等的情况下,RSA和ECC的速度相当; 但是在相同的安全强度要求下,ECC可以使用较少的位数就可以; 故 ECC较好 适合嵌入式设备中,ECC vs. RSA,
链接地址:https://www.31doc.com/p-2363338.html