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

《现代密码学08---椭圆曲线与IBC.pptx》由会员分享，可在线阅读，更多相关《现代密码学08---椭圆曲线与IBC.pptx（47页珍藏版）》请在三一办公上搜索。

1、,现代密码学,椭圆曲线与基于身份的密码学,2,3,8.1 椭圆曲线概述8.2 基于身份的密码学(IBC),4,5,1985年，N.Koblitz(华盛顿大学)和 V.Miller(IBM)分别独立提出了椭圆曲线密码体制(ECC)的思想,Neal Koblitz,6,同等安全强度下，ECC要求的密钥长度较短，故而具有以下优势存储量要求低带宽要求低计算速度快实现高度安全性,7,ECC是公钥密码的主流，是设计大多数计算能力和存储空间有限、带宽受限又要求高速实现的安全产品的首选。智能卡无线网络手持设备,8,一般来讲，椭圆曲线的曲线方程是以下形式的三次方程：,其中，a1,a2,a3,a4,a5,a6R满

2、足该方程的(x,y)称为椭圆曲线E上的点，通常用大写字母P、Q或R表示。,9,非奇异椭圆曲线 设a,bR，且，方程 的所有解(x,y)，连同一个无穷远点O组成集合E称为非奇异椭圆曲线。是保证方程有三个不同解(实数或复数)的充要条件如果，则对应的椭圆曲线称为奇异椭圆曲线,10,非奇异椭圆曲线的两个例子,11,若E是非奇异椭圆曲线，可在该集合上定义一个二元运算，通常用加法表示，使之成为交换群(E,+)。加法交换群(E,+)的特性单位元：无穷远点O对于任意PE，有P+O=O+P=P逆元：设P=(x,y)E，则P的逆元定义为-P=(x,-y)于是，P+(-P)=(x,y)+(x,-y)=O对任意P,Q

3、E，设P=(x1,y1),Q=(x2,y2)，计算P+Q时考虑以下三种情况：,12,x1x2 时画一条通过P、Q的直线与椭圆曲线交于R，R的逆元便是P+Q的结果,R,P+Q,Q,P,13,x1=x2 且 y1=-y2 时，P与Q互为逆元 此时，P+Q=O,P,Q,14,x1=x2 且 y1=y2 时，则P=Q(点P与自己相加)画一条通过P的切线，与椭圆曲线交于R，R的逆元便是P+P的结果,R,P+P,P,15,令P为椭圆曲线E上一点。对正整数n，若点P自加n次，即P+P+P，可简写成 nPP的阶：满足 nP=O 的最小正整数 n,16,密码学中使用的是有限域上的椭圆曲线，是由方程 E:y2x3

4、+ax+b(mod p)定义的曲线(包括无穷远点O)其中 a,bFp，且满足4a3+27b2 0(mod p)E上点的坐标 x 和 y 都是Fp中的元素，即属于0,1,p-1(小于p的整数)注意：前面介绍的椭圆曲线方程的系数是实数(连续的)，而有限域上的椭圆曲线方程的系数属于Fp(离散的，整数),17,有限域Fp上的椭圆曲线，通常记为E(Fp)，简记为EE(Fp)在加法定义下形成交换群，简记为(E,+)单位元：无穷远点O加法运算与实数上的曲线加法相同，只是所有的坐标运算都是模p的,18,y2=x3+x mod 23,19,椭圆曲线密码体制(ECC)建立在椭圆曲线上的困难问题之上基于离散对数、D

5、iffie-Hellman问题的密码方案均可用椭圆曲线实现Diffie-Hellman密钥交换协议（椭圆曲线版）ElGamal密码体制（椭圆曲线版）,20,设PE(Fp),P的阶是一个非常大的素数，则有如下两个困难问题：椭圆曲线上的离散对数问题(DL)令Q=kP，则给定P、Q，求k是计算上困难的椭圆曲线上的计算Diffie-Hellman问题(CDH)给定aP、bP，求abP是计算上困难的,21,系统建立：选择椭圆曲线E(Fp)，及其上一点P，设P的阶是一个非常大的素数E(Fp)和P是公开的系统参数密钥交换如下图：,xYB=K yYA=K,YB=yP,YA=xP,(xyP=K)(xyP=K),

6、22,安全性高比基于传统离散对数问题的公钥体制更安全灵活性好Fp上的椭圆曲线可通过改变参数得到不同的曲线密钥长度更短使用更短的密钥长度提供相同的安全强度,23,国外已有用ECC进行加解密的产品出现在市场上美国NeXT Computer公司开发快速椭圆曲线加密(FEE)算法加拿大Certicom公司开发出实用的ECC集成电路3COM/Palm Computing、Motorala、日本Mitsushita及NTT实验室、法国Thompson、德国Siemens、加拿大Waterloo大学等也都实现这一体制(包括软件和硬件实现)目前，ECC标准化正在进行中。虽然还没有统一的标准方案，但已有一些较为

7、成熟的标准出现IEEE（P1363）ANSI X9F1工作组（X9.42，X9.62和X9.63）ISO/IEC,24,超奇异椭圆曲线是有限域上一种特殊的椭圆曲线在该类曲线上，存在一种被称为双线性映射(bilinear pairing)的有效算法，可以将曲线上两个点映射到基域上的一个元素如今，基于超奇异椭圆曲线和双线性映射的密码体制变得炙手可热，成为当今密码学研究的热点。,25,设p是大素数，加法群G1和乘法群G2都是p阶群。双线性映射e:G1G1G2满足以下条件：双线性：对任意 P,Q,RG1 和 a,bZ*p 有 e(P,Q+R)=e(P,Q)e(P,R)e(P+Q,R)=e(P,R)e(

8、Q,R)e(aP,bQ)=e(P,Q)ab非退化性：存在P,QG1,有e(P,Q)1可计算性：对于所有P,QG1,e(P,Q)可有效计算通常，取G1为有限域上超奇异椭圆曲线，G2为G1的基域(椭圆曲线所基于的有限域),26,离散对数问题(DL)计算Diffie-Hellman问题(CDH)双线性Diffie-Hellman问题(BDH)设 a,b,cZ*p，给定 P,aP,bP,cPG1 求e(P,P)abc 是计算上不可行的,27,三方Diffie-Hellman密钥交换协议系统建立随机选择大素数p，生成p阶加法群G1和乘法群G2随机选择阶足够大的元素PG1e:G1G1G2是双线性映射,28

9、,随机选择aZ*p,随机选择bZ*p,随机选择cZ*p,aP,cP,bP,Internet,密钥交换,29,计算共享密钥Alice 计算 K=e(bP,cP)a=e(P,P)abcBob 计算 K=e(aP,cP)b=e(P,P)abcCarol计算 K=e(aP,bP)c=e(P,P)abc于是，三人获得相同的密钥K,bP:来自Bob,cP:来自Carol,a:Alice自己的选择,30,安全性分析攻击者能获得哪些信息？获得系统参数P窃听到aP,bP,cP但无法计算出 e(P,P)abc原理：BDH问题是计算上困难的当然，为防止中间人攻击，需要加入认证功能，以保证接收到数据的来源的可靠性。,

10、PBC-library开发者：Ben Lynn注：需要另一个软件包GMP的支持,31,32,优点 提供了丰富的运算性质，可以满足以前难以满足的安全需求 缺点 目前广泛应用的算法(Weil pairing,Tate pairing)计算速度相对较慢,33,34,传统公钥密码体制存在的问题：公钥杂乱无章，随机的，不可识别如何确保公钥的真实性？需要将所有者的身份和公钥绑定公钥证书，PKI但PKI的运行和维护代价很大,35,36,IBC 的提出 Adi Shamir 1984年 相关文献：Identity-Based Cryptosystems and Signature Scheme,37,传统公钥

11、密码中公钥的产生先选择私钥，再计算公钥，公钥必然显得“一片混乱”IBC 产生公钥的原理先选择公钥，再计算私钥公钥可选择email地址、身份证号等，称之为用户的身份，记为ID(注意：公钥就是ID，或从ID直接推导而来)私钥看起来杂乱无章，没关系，反而有利,身份ID,38,IBC下的秘密通信模型,加密 E(),解密 D(),明文M,密文C,私钥SK,破译,公开信道,B,13%df#ef5&g,身份ID,明文M,Trusted Agency(TA),39,ID必须是每个用户唯一确定的信息，比如身份证号、电子邮箱等。需要注意的是ID并没有任何特殊的数学意义，它所具有的是特殊的社会意义。因为，数学上可以

12、用任何串做公钥，于是我们选择了具有特殊社会意义的串作为ID。,40,我们依然需要一个可信第三方，用以帮助用户产生私钥，称之为 Trusted Agency(TA)也即，用户选择自己的ID作为公钥 TA根据ID产生相应的私钥（用户的私钥从TA那里获得）注意IBC中的TA 与 PKI中的CA 职能不同TA的任务简单很多,Trusted Agency(TA),41,CA的任务绑定ID和公钥(ID不是公钥)TA的任务由ID计算出私钥(公钥就是ID，或从ID直接推导而来),42,43,优点避免使用复杂的PKI系统缺点私钥泄露以后，相应的ID也就无法使用密钥撤销问题是影响IBC发展的主要桎梏密钥托管问题（

13、Key-escrow）私钥由TA产生，一旦TA被攻破，所有用户信息将受到严重威胁,私钥泄露了怎么办,44,掌握ECC的优势掌握椭圆曲线加法群的几何性质掌握双线性映射技术的描述掌握IBC的基本概念、优缺点、TA和CA的区别了解椭圆曲线版Diffie-Hellman密钥交换协议,45,与传统公钥密码相比，ECC的优点是()A.安全性高 B.灵活性好 C.密钥长度更短 D.以上都对不属于双线性映射特性的是()A.双线性 B.非退化性 C.可计算性 D.差分性3.TA的主要任务是()A.签发证书 B.产生用户私钥 C.作废过期证书 D.以上都不对,D,D,B,45,46,IBC中的密钥托管问题是指()A.ID如果发生泄露，其安全性会受到威胁 B.私钥泄露以后，相应的ID也就无法使用 C.私钥由TA产生，一旦TA被攻破，所有用户信息将受到严重威胁 D.以上都不对,C,46,47,双线性映射技术作用于()A.奇异椭圆曲线 B.非奇异椭圆曲线 C.超奇异椭圆曲线 D.以上都不对双线性映射技术可以()A.将曲线上一个点映射到其基域的一个元素 B.将曲线上两个点映射到其基域的一个元素 C.将基域的一个元素映射到曲线上的一个点 D.以上都不对,C,47,B,