现代密码学椭圆曲线与基于身份的密码学第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:yxaxb324a27b0324a27b0324a27b=010非奇异椭圆曲线的两个例子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...
