《crypto4c-ch10-密钥管理及其他公钥体制剖析》由会员分享,可在线阅读,更多相关《crypto4c-ch10-密钥管理及其他公钥体制剖析(49页珍藏版)》请在金锄头文库上搜索。
1、B密码编码学与网络安全密码编码学与网络安全电子工业出版社2006 - 2007B第10章 公钥密钥管理及其他公钥体制10.1 密钥管理10.2 Diffie-Hellman密钥交换* 10.a PKCS#3 & RFC* 10.b ElGamal10.3 椭圆曲线10.4 椭圆曲线密码学ECCB“公开”密钥?这太简单了!错!错!曾经使用对称密码体制时,一个非常烦人的问题是如何协商会话密钥。公钥体制中只需公开发布公钥(且保守私钥) ,因此通常被认为是减轻了密钥管理的负担。但当认真考虑如何发布公钥时,你会发现:原来可靠地发布公钥其实也很难原来可靠地发布公钥其实也很难。公钥的发布体制-证书体系(CA
2、),是PKI的核心和基础。事实上,证书体系的过于复杂阻碍了PKI的普及。B10.1 密钥管理公钥的分配公钥体制用于传统密码体制的密钥分配B公钥的分配方法1. 临时索要公钥/自由的扩散/PGP的公钥环2. 公开的目录服务(在线方式)3. 公钥授权(在线中心方式)4. 通过证书中心CA(离线中心方式)B1. 自由方式当要通信时向对方索要其公钥没有先验知识,不能确定对方的身份,不能提供鉴别特性只能用在不究身份时的加密,如萍水相逢的两人之间的防偷听聊天扩散通过可信的朋友之间的辗转交换PGP中即有此种公钥交换机制朋友并不总可信问题:相信阁下的人品,但是不相信阁下的智商B2. 公开目录公开的目录服务目录的
3、维护得由信得过的机构执行每个用户在目录里有一项 身份信息,其公钥 面对面的审核和注册可以更新或废止提供网络的访问手段,可公开查询目录中心的安全负担太重,也是性能瓶颈B3. 公钥授权:在线中心有在线中心帮助的公钥交换A请求中心给B的公钥,带时间戳中心用私钥签署的消息,包括:原始请求和时间戳,B的公钥,A用B的公钥加密:自己的身份IDa和会话标识号N1B也如法取得A的公钥B用A的公钥加密:N1和N2A用B的公钥加密N2,以最后确认会话在线中心容易成为单点故障和性能瓶颈B公钥授权:在线中心 B4. 证书:离线中心Certificate Authentication CA是受信任的权威机构,有一对公钥
4、私钥。每个用户自己产生一对公钥和私钥,并把公钥提交给CA申请证书。CA以某种可靠的方式核对申请人的身份及其公钥,并用自己的私钥“签发”证书。证书主要内容:用户公钥,持有人和签发人的信息,用途,有效期间,签名等。证书在需要通信时临时交换,并用CA的公钥验证。有了经CA签名保证的用户公钥,则可进行下一步的身份验证和交换会话密钥等。BCA B使用公钥传递会话密钥 公钥算法太慢对称算法一般几十兆字节/秒1024位RSA解密约100多次/秒(加密快10倍以上)100*128B = 10KB/s只用来传递会话密钥(假设B已经有A的公钥KeA)A发起和B的通信B产生会话密钥Ks,并用KeA加密后传给AA能用
5、自己的私钥KdA解开他人不会知道KsBMerkle方案 因为B临时获取A的公钥,所以存在“中间人攻击”的问题BNEED78方案(事先拥有对方公钥)B10.2 Diffie-Hellman密钥交换离散对数问题ygx mod p,其中g是生成元求x的困难性目前没有有效的方法实际使用时常用Zp*和ECC上的点加法群 Pohlig-Hellman algorithm如果p-1是小素数的乘积,则易求因此,p-1应含有大素因子BDiffie-Hellman密钥交换协议 DH76,Diffie-Hellman步骤选取大素数q和它的一个生成元g,这些参数公开A选择随机数Xa,B选择随机数Xb A计算YagXa
6、 mod q,B计算YbgXb mod q 交换Ya,YbA计算KYbXa mod q,B计算KYaXb mod q 事实上,KKB证明、分析和例子证明KKKYbXa mod qKYaXb mod q (gXb)Xa mod q (gXa)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 qB中间人攻击
7、交换Y的过程中,Y有可能被替换假冒,而且不能发现形式上,可以理解为一个中间人在跟双方同时通信,当然通信内容在中间人那里是可见的* 一个现实的例子就是:可以同时开两盘QQx棋,一个后手,一个先手,BMan-in-the-middleAEBXaXb XaXbYaYb YaYbK=YbXaK=YaXbB相关结论maurer94towardsTowards the Equivalence of Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithmshttp:/ PKCS#3PKCS#3 Diffie-Hellman
8、Key-Agreement Standard进一步参阅 pkcs#3PVpublic valuep primePVothers public valuex private valueSKsecret keyx others private valueg basey integer public valuek length of prime in octetsy others integer public valuellength of private value in bits z integer secret keymod n modulo nBRFC 2631Diffie-Hellman
9、Key Agreement MethodBRFC 2409The Internet Key Exchange (IKE)BRFC 3526More Modular Exponential (MODP) Diffie-Hellman groups for Internet Key Exchange (IKE)Brfc35261. Introduction One of the important protocol parameters negotiated by Internet Key Exchange (IKE) RFC-2409 is the Diffie-Hellman group th
10、at will be used for certain cryptographic operations. IKE currently defines 4 groups. These groups are approximately as strong as a symmetric key of 70-80 bits. The new Advanced Encryption Standard (AES) cipher AES, which has more strength, needs stronger groups. For the 128-bit AES we need about a
11、3200-bit group Orman01. The 192 and 256-bit keys would need groups that are about 8000 and 15400 bits respectively. Another source RSA13 Rousseau00 estimates that the security equivalent key size for the 192-bit symmetric cipher is 2500 bits instead of 8000 bits, and the equivalent key size 256-bit
12、symmetric cipher is 4200 bits instead of 15400 bits. Because of this disagreement, we just specify different groups without specifying which group should be used with 128, 192 or 256- bit AES. With current hardware groups bigger than 8192-bits being too slow for practical use, this document does not
13、 provide any groups bigger than 8192-bits.BRFC 5114B10.b 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 pBElGamal etc基于离散对数难题缺点需要随机数密文长度加倍背景循环群: 从Zp*到EC点加群ElGamal可以迁移到ECDLP上ElGamal签名和DSSB10.3 椭圆曲线 Ellipti
14、c Curve背景RSA安全依赖因子分解的难度,为了增加安全性就得增加位数,从而导致计算速度变慢。Zp*上的DLP问题有亚指数复杂度的算法。至今未发现解决ECDLP的普适性亚指数算法ECC可以用较小的密钥长度达到较高的计算难度,即安全性B椭圆曲线ECElliptic Curvey2axybyx3cx2dxe其中a、b、c、d、e是满足某个简单条件的实数Any elliptic curve can be written as a plane algebraic curve defined by an equation of the form:y2x3axbBEC上点加法定义为无穷点/零点为O点点
15、加法PQR定义为过P、Q和椭圆曲线相交的第三点的X轴对称点RBEC:PQR B动画演示加法B素域上的EC 在有限域Zp上的简化ECy2x3axb mod p 其中4a327b2 mod p 0(这是一个离散点的集合)举例y2x318x15 mod 23 y2x317x15 mod 23BEC (1) BEC (2)B动画演示加法(离散点)BEC上的离散对数问题(ECDLP)QkP中的k计算也是极其困难的kP表示k个P相加:P + P + + P在DH密钥交换中使用了ygx mod p中x的计算困难性同样在ECC中将使用QkP中计算k的困难性有两个应用密钥交换加密解密B10.4 椭圆曲线密码学E
16、CCECC利用EC上的离散对数难题(ECDLP),这和利用Zp*上的离散对数难题(DLP)是一样的方法。在一般数域上的离散对数问题(以及大数分解问题)存在亚指数级时间复杂度求解算法,而ECDLP只有纯指数算法。B使用EC的密钥交换(D-H)步骤y2x3axb mod p 选择素数p(得约160比特)和参数a、b选择一个生成点G(x1,y1)p、a、b和点G是公开的A:选取秘密的数Na,计算PaNaGB:选取秘密的数Nb,计算PbNbG交换Pa,PbA:计算KNaPbNaNbGB:计算KNbPaNbNaG分析攻击者得求Na和Nb,就是P?G中的?B用EC的加解密准备曲线参数p、a、b、G,y2x
17、3axb mod p A有自己的私钥Na,并产生公钥PaNaGB有自己的私钥Nb,并产生公钥PbNbG加密 (A要给B发送消息)对明文m的编码点Pm,选择随机数k,密文CC1,C2 kG,PmkPb解密:编码点PmC2NbC1,因为 (PmkPb)NbkG PmkNbGNbkG PmB用EC的加解密原理先是通过kPb掩盖Pm (即m),又通过kG掩盖k知道陷门Nb则可以轻松恢复之分析攻击者解C1kG中的k困难性B关于速度速度在密钥长度相等的情况下,RSA和ECC的速度相当;但是在相同的安全强度要求下,ECC可以使用较少的位数就可以;故ECC较好适合嵌入式设备中BECC vs. RSA BRFC
18、 4050Using the ECDSA for XML Digital SignaturesBECC STDPKCS#13 proposalECC Cryptography Tutorialhttp:/ ANSI X9.42($100)ANSI X9.62/FIPS 186-2IEEE P1363: Standard Specifications For Public Key Cryptographyhttp:/grouper.ieee.org/groups/1363/ ECC - Elliptic Curve C http:/ http:/ ISO/IEC 15946B关键词 Key Te
19、rmsabelian groupbinary curvecubic equationDiffie-Hellman key exchangediscrete logarithmelliptic curveelliptic curve arithmeticelliptic curve cryptographyfinite fieldkey distributionkey managementman-the-middle attackprime curveprimitive rootpublic-key certificate public-key directoryzero pointB小结公钥算法没有对称算法那样多,但是对称算法都是基于替代和置换的组合应用技巧,而公钥算法各自使用不同的背景难题。目前常用有三个背景难题:大数分解(IFP),离散对数问题(DLP),椭圆曲线上的DLP(ECDLP)。随着计算能力的日益增长,公钥算法的密钥宽度也需要与时俱进。公钥算法仍需要和对称算法结合使用,各自发挥优点,避免缺点。BQ & A