现代密码学08---椭圆曲线与IBC

现代密码学林喜军中国海洋大学信息安全实验室椭圆曲线与基于身份的密码学第8章2本章内容38.1椭圆曲线概述8.2基于身份的密码学(IBC)8.1椭圆曲线概述45•1985年，N.Koblitz(华盛顿大学)和V.Miller(IBM)分别独立提出了椭圆曲线密码体制(ECC)的思想NealKoblitz6•同等安全强度下，ECC要求的密钥长度较短，故而具有以下优势–存储量要求低–带宽要求低–计算速度快–实现高度安全性ECC的优势7•ECC是公钥密码的主流，是设计大多数计算能力和存储空间有限、带宽受限又要求高速实现的安全产品的首选。–智能卡–无线网络–手持设备……8•一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：23213246E:yaxyayxaxaxa其中，a1,a2,a3,a4,a5,a6∈R•满足该方程的(x,y)称为椭圆曲线E上的点，通常用大写字母P、Q或R表示。椭圆曲线的曲线方程9•非奇异椭圆曲线设a,b∈R，且，方程的所有解(x,y)，连同一个无穷远点O组成集合E称为非奇异椭圆曲线。•是保证方程有三个不同解(实数或复数)的充要条件•如果，则对应的椭圆曲线称为奇异椭圆曲线23E:yxaxb324a27b0324a27b0324a27b=010非奇异椭圆曲线的两个例子11•若E是非奇异椭圆曲线，可在该集合上定义一个二元运算，通常用加法表示，使之成为交换群(E,+)。•加法交换群(E,+)的特性–单位元：无穷远点O•对于任意P∈E，有P+O=O+P=P–逆元：设P=(x,y)∈E，则P的逆元定义为-P=(x,-y)•于是，P+(-P)=(x,y)+(x,-y)=O–对任意P,Q∈E，设P=(x1,y1),Q=(x2,y2)，计算P+Q时考虑以下三种情况：非奇异椭圆曲线可构成加法交换群12①x1≠x2时–画一条通过P、Q的直线与椭圆曲线交于R，R的逆元便是P+Q的结果RP+QQP33221312313121(,),(),PQxyyyxxxyxxyxx设，则其中13②x1=x2且y1=-y2时，P与Q互为逆元此时，P+Q=OPQ14③x1=x2且y1=y2时，则P=Q(点P与自己相加)–画一条通过P的切线，与椭圆曲线交于R，R的逆元便是P+P的结果RP+PP332213131311(,)32,(),2PPxyxaxxyxxyy设，则其中15•令P为椭圆曲线E上一点。对正整数n，若点P自加n次，即P+P+…+P，可简写成nP•P的阶：满足nP=O的最小正整数n16•密码学中使用的是有限域上的椭圆曲线，是由方程E:y2≡x3+ax+b(modp)定义的曲线(包括无穷远点O)其中a,b∈Fp，且满足4a3+27b2≠0(modp)–E上点的坐标x和y都是Fp中的元素，即属于{0,1,…,p-1}(小于p的整数)–注意：前面介绍的椭圆曲线方程的系数是实数(连续的)，而有限域上的椭圆曲线方程的系数属于Fp(离散的，整数)有限域上的ECC17•有限域Fp上的椭圆曲线，通常记为E(Fp)，简记为E•E(Fp)在加法定义下形成交换群，简记为(E,+)–单位元：无穷远点O–加法运算与实数上的曲线加法相同，只是所有的坐标运算都是模p的Fp称为E的基域18•y2=x3+xmod23举例19•椭圆曲线密码体制(ECC)建立在椭圆曲线上的困难问题之上•基于离散对数、Diffie-Hellman问题的密码方案均可用椭圆曲线实现–Diffie-Hellman密钥交换协议（椭圆曲线版）–ElGamal密码体制（椭圆曲线版）……椭圆曲线上的困难问题20•设P∈E(Fp),P的阶是一个非常大的素数，则有如下两个困难问题：•椭圆曲线上的离散对数问题(DL)令Q=kP，则给定P、Q，求k是计算上困难的•椭圆曲线上的计算Diffie-Hellman问题(CDH)给定aP、bP，求abP是计算上困难的椭圆曲线上的困难问题21•系统建立：–选择椭圆曲线E(Fp)，及其上一点P，设P的阶是一个非常大的素数–E(Fp)和P是公开的系统参数•密钥交换如下图：xYB=KyYA=KYB=yPYA=xPYAYB(xyP=K)(xyP=K)椭圆曲线版Diffie-Hellman密钥交换协议（自己看）22①安全性高–比基于传统离散对数问题的公钥体制更安全②灵活性好–Fp上的椭圆曲线可通过改变参数得到不同的曲线③密钥长度更短–使用更短的密钥长度提供相同的安全强度椭圆曲线密码112bit161bit224bitRSA512bit1024bit2048bit密钥长度比5:16:19:1椭圆曲线概述ECC的优点小结23•国外已有用ECC进行加解密的产品出现在市场上–美国NeXTComputer公司开发快速椭圆曲线加密(FEE)算法–加拿大Certicom公司开发出实用的ECC集成电路–3COM/PalmComputing、Motorala、日本Mitsushita及NTT实验室、法国Thompson、德国Siemens、加拿大Waterloo大学等也都实现这一体制(包括软件和硬件实现)•目前，ECC标准化正在进行中。虽然还没有统一的标准方案，但已有一些较为成熟的标准出现–IEEE（P1363）–ANSIX9F1工作组（X9.42，X9.62和X9.63）–ISO/IEC……24•超奇异椭圆曲线是有限域上一种特殊的椭圆曲线•在该类曲线上，存在一种被称为双线性映射(bilinearpairing)的有效算法，可以将曲线上两个点映射到基域上的一个元素•如今，基于超奇异椭圆曲线和双线性映射的密码体制变得炙手可热，成为当今密码学研究的热点。双线性映射技术（BilinearPairing）25•设p是大素数，加法群G1和乘法群G2都是p阶群。双线性映射e:G1×G1→G2满足以下条件：①双线性：对任意P,Q,R∈G1和a,b∈Z*p有e(P,Q+R)=e(P,Q)e(P,R)e(P+Q,R)=e(P,R)e(Q,R)e(aP,bQ)=e(P,Q)ab②非退化性：存在P,Q∈G1,有e(P,Q)≠1③可计算性：对于所有P,Q∈G1,e(P,Q)可有效计算•通常，取G1为有限域上超奇异椭圆曲线，G2为G1的基域(椭圆曲线所基于的有限域)双线性映射技术描述26①离散对数问题(DL)②计算Diffie-Hellman问题(CDH)③双线性Diffie-Hellman问题(BDH)设a,b,c∈Z*p，给定P,aP,bP,cP∈G1求e(P,P)abc是计算上不可行的双线性映射技术超奇异椭圆曲线上的困难问题27•三方Diffie-Hellman密钥交换协议①系统建立•随机选择大素数p，生成p阶加法群G1和乘法群G2•随机选择阶足够大的元素P∈G1•e:G1×G1→G2是双线性映射双线性映射技术应用举例28随机选择a∈Z*p随机选择b∈Z*p随机选择c∈Z*paPcPbPInternet②密钥交换双线性映射技术应用举例29③计算共享密钥–Alice计算K=e(bP,cP)a=e(P,P)abc–Bob计算K=e(aP,cP)b=e(P,P)abc–Carol计算K=e(aP,bP)c=e(P,P)abc•于是，三人获得相同的密钥KbP:来自BobcP:来自Carola:Alice自己的选择双线性映射技术应用举例30•安全性分析–攻击者能获得哪些信息？•获得系统参数P•窃听到aP,bP,cP•但无法计算出e(P,P)abc–原理：BDH问题是计算上困难的•当然，为防止中间人攻击，需要加入认证功能，以保证接收到数据的来源的可靠性。双线性映射技术应用举例（不考）•双线性Diffie-Hellman问题(BDH)设a,b,c∈Z*p给定P,aP,bP,cP∈G1求e(P,P)abc是计算上不可行的•PBC-library–开发者：BenLynn–注：需要另一个软件包GMP的支持31双线性映射技术支持双线性映射的软件包32•优点提供了丰富的运算性质，可以满足以前难以满足的安全需求•缺点目前广泛应用的算法(Weilpairing,Tatepairing)计算速度相对较慢双线性映射技术优缺点8.2基于身份的密码学(IBC)3334•传统公钥密码体制存在的问题：公钥杂乱无章，随机的，不可识别•如何确保公钥的真实性？–需要将所有者的身份和公钥绑定•公钥证书，PKI•但PKI的运行和维护代价很大35Q:是否有另一种解决该问题的方法？基于身份的密码学(Identity-BasedCryptography)36•IBC的提出AdiShamir1984年相关文献：Identity-BasedCryptosystemsandSignatureScheme37•传统公钥密码中公钥的产生–先选择私钥，再计算公钥，公钥必然显得“一片混乱”•IBC产生公钥的原理–先选择公钥，再计算私钥–公钥可选择email地址、身份证号等，称之为用户的身份，记为ID(注意：公钥就是ID，或从ID直接推导而来)–私钥看起来杂乱无章，没关系，反而有利IBC的原理身份ID38IBC下的秘密通信模型加密E(·)解密D(·)明文M密文C私钥SK破译公开信道[e-mail]13%df#ef5&g身份ID明文MTrustedAgency(TA)由ID产生用户私钥39•ID必须是每个用户唯一确定的信息，比如身份证号、电子邮箱等。•需要注意的是–ID并没有任何特殊的数学意义，它所具有的是特殊的社会意义。–因为，数学上可以用任何串做公钥，于是我们选择了具有特殊社会意义的串作为ID。40•我们依然需要一个可信第三方，用以帮助用户产生私钥，称之为TrustedAgency(TA)也即，用户选择自己的ID作为公钥TA根据ID产生相应的私钥（用户的私钥从TA那里获得）˙注意–IBC中的TA与PKI中的CA职能不同–TA的任务简单很多TrustedAgency(TA)TrustedAgency(TA)41•CA的任务绑定ID和公钥(ID不是公钥)•TA的任务由ID计算出私钥(公钥就是ID，或从ID直接推导而来)CA公钥证书ID绑定公钥CA与TA的区别TAID产生私钥公钥42扩展阅读IBS基于身份的签名方案IBE基于身份的加密方案43•优点–避免使用复杂的PKI系统•缺点①私钥泄露以后，相应的ID也就无法使用•密钥撤销问题是影响IBC发展的主要桎梏②密钥托管问题（Key-escrow）•私钥由TA产生，一旦TA被攻破，所有用户信息将受到严重威胁私钥泄露了怎么办IBC的优缺点441.掌握ECC的优势2.掌握椭圆曲线加法群的几何性质3.掌握双线性映射技术的描述4.掌握IBC的基本概念、优缺点、TA和CA的区别5.了解椭圆曲线版Diffie-Hellman密钥交换协议本章小结45练习题1.与传统公钥密码相比，ECC的优点是()A.安全性高B.灵活性好C.密钥长度更短D.以上都对2.不属于双线性映射特性的是()A.双线性B.非退化性C.可计算性D.差分性3.TA的主要任务是()A.签发证书B.产生用户私钥C.作废过期证书D.以上都不对DDB•4546练习题4.IBC中的密钥托管问题是指()A.ID如果发生泄露，其安全性会受到威胁B.私钥泄露以后，相应的ID也就无法使用C.私钥由TA产生，一旦TA被攻破，所有用户信息将受到严重威胁D.以上都不对C•4647练习题5.双线性映射技术作用于()A.奇异椭圆曲线B.非奇异椭圆曲线C.超奇异椭圆曲线D.以上都不对6.双线性映射技术可以()A.将曲线上一个点映射到其基域的一个元素B.将曲线上两个点映射到其基域的一个元素C.将基域的一个元素映射到曲线上的一个点D.以上都不对C•47B