第6章-椭圆曲线密码体制

公钥密码一、椭圆曲线公钥密码ECC(EllipticCurveCryptography)二、McEliece公钥密码椭圆曲线公钥密码ECC1.简要历史椭圆曲线(Ellipticcurve)作为代数几何中的重要问题已有100多年的研究历史1985年，N.Koblitz和V.Miller独立将其引入密码学中，成为构造双钥密码体制的一个有力工具。利用有限域GF(2n)上的椭圆曲线上点集所构成的群上定义的离散对数系统，可以构造出基于有限域上离散对数的一些双钥体制--椭圆曲线离散对数密码体制(ECDLC)，如Diffie-Hellman，ElGamal，Schnorr，DSA等。10余年的研究，尚未发现明显的弱点。研究现状椭圆曲线密码是除RSA算法以外最重要的公钥密码之一。与RSA算法相比它也有很多独特的优点。出于国家安全战略考虑，国内学术界和管理部门一直希望能够在国内一些应用场合使用椭圆曲线密码。在推广和使用椭圆曲线密码的过程中，相应的芯片是必不可少的。然而，由于椭圆曲线密码算法是一种很复杂的数学算法，如何将椭圆曲线密码算法芯片化，国内外没有成熟技术。椭圆曲线加密算法背景–RSA中用到了因子分解的困难性，而为了增加困难得加大数的位数，从而导致计算速度变慢。–ECC可以用较小的密钥长度达到较高的计算难度获得同样的安全性，密钥长度较RSA短得多被IEEE公钥密码标准P1363采用椭圆曲线公钥密码ECC椭圆曲线上一个点P的k倍表示表示P+P+…（k个点P“相加”），记为kP。椭圆曲线上一个点P的所有倍数点组成了椭圆曲线的子集，该子集是该椭圆曲线关于该“加法”的循环子群。给定“椭圆曲线”上的点P，给定整数k，计算“kP=？”是容易的。（折半相加）给定“椭圆曲线”上的两个点P和Q，求整数“？P=Q”是困难的。这个问题称为椭圆曲线上的离散对数问题。椭圆曲线方程EllipticCurvey2＋axy＋by＝x3＋cx2＋dx＋e其中a、b、c、d、e是满足某个简单条件的实数另有O点被定义为无穷点/零点椭圆曲线的定义1.1椭圆曲线的定义设F是域，F-是F的代数闭包。椭圆曲线的一般定义为F-上亏格为1的光滑的代数曲线。这个定义涉及很多代数几何中的概念。实际上，定义在F上的椭圆曲线可等价地看作由方程y2+a1xy+a3xy=x3+a2x2+a4x+a6(1)刻划的F-上曲线再添加上一点O，其中ai∈F且满足判别式不为零。椭圆曲线的有理点即为点O及坐标在F中的点(x，y)。方程(1)称为该椭圆曲线的Weierstrass方程。当F的特征不是2或3时，这个方程可化为特别简单的形式y2=x3+ax+b并要求判别式Δ=4a3+27b2≠0椭圆曲线密码示意图椭圆曲线密码介绍运算定义：–若曲线三点在一条直线上,则其和为O–O用作加法的单位：O=-O;P+O=P–一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1=-P2–如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P1–2倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S椭圆曲线加法的定义–Q,R是ECC上x坐标不同的两点，Q+R定义为：画一条通过Q,R的直线与ECC交于P1(交点是唯一的，除非做的Q,R点的切线，此时分别取P1=Q或P1=R)。由Q+R+P1=O,得Q+R=-P1–点Q的倍数定义如下：在Q点做ECC的一条切线，设切线与ECC交于S,定义2Q=Q+Q=-S。类似可定义3Q=Q+Q+Q,…,–上述加法满足加法的一般性质，如交换律、结合律等椭圆曲线上不同坐标点相加椭圆曲线上相同坐标点相加椭圆曲线上一坐标点与无穷远点相加椭圆曲线上两对称点相加A＋B=A+(-A)=OBEC：P＋Q＝R素域上的EC在有限域Zp上的简化ECy2≡x3＋ax＋bmodp其中4a3＋27b2modp≠0（这是一个离散点的集合）举例y2≡x3＋18x＋15mod23y2≡x3＋17x＋15mod23－1EC－2有限域上的椭圆曲线曲线方程中的所有系数都是某一有限域GF(p)中的元素(p为一大素数)，最为常用的曲线方程为y2=x3+ax+bmod(p)(a,b∈GF(p),4a3+27b2≠0modp)例：p=23,a=b=1,4a3+27b2=8≠0(mod23),方程为y2=x3+x+1mod(p)，图形为连续图形。我们感兴趣的是在第一象限的整数点。设Ep(a,b)表示ECC上点集{(x,y)|0≤xp,0≤yp,且x,y均为整数}并上O.有限域上的椭圆曲线点集产生方法对每一x(0≤xp且x为整数），计算x3+ax+bmodp决定求出的值在模p下是否有平方根，如果没有则椭圆曲线上没有与这一x对应的点；如果有，则求出两个平方根。Ep(a,b)上加法如果P,Q∈Ep(a,b)–P+O=P–如果P＝(x,y),则(x,y)+(x,-y)＝O–P＝(x1,y1),Q=(x2,y2),P≠-Q,P+Q=(x3,y3)x3=l2-x1-x2（modp）y3=l(x1-x3)-y1(modp)QPyaxQPxxyy121121223l例：E23(1,1)P=(3,10),Q(=9,7))12,7(223mod123410)73(623mod73033623mod641205102133:2)1,1()20,17(23mod2016410)173(1123mod17109931123mod11222216339107323223323PyxPEQPyxllEC上的离散对数问题Q＝k×P中的k计算也是极其困难的k×P表示k个P相加：P+P+…+P在DH密钥交换中使用了y＝gxmodp中x的计算困难性同样在ECC中将使用Q＝k×P中计算k的困难性有两个应用密钥交换加密解密在有限域上的椭圆曲线运算•在此椭圆曲线上可以能出现的点有(0,1)、(0,4)、(2,1)、(2,4)、(3,1)、(3,4)、(4,2)、(4,3)、(∞,∞)•任取椭圆曲线上两点，无论作加法、減法或乘法，其結果永远为上述坐标点中的一点.•椭圆曲线中的离散对数难题：给定一参数K及一点A，要求得另一点B，使得B=KA是很容易的。例如：5A=A+A+A+A+A但若給定A及B要求得K則很困難ECC上的密码ECC上的离散对数问题–在ECC构成的交换群Ep(a,b)上考虑方程Q＝kP，P,Q∈Ep(a,b),kp.由k和P求Q容易，由P,Q求k则是困难的。由ECC上离散对数问题可以构造Diffie-Hellman密钥交换和ElGamal密码体制椭圆曲线用于加密找到一个难题：–考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp–已知k和P，计算Q，是容易的–已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数–G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=kG，然后–公开(p,a,b,G,P)，P为公钥–保密k用EC的加解密准备–曲线参数p、a、b、G，y2≡x3＋ax＋bmodp–A有自己的私钥Na，并产生公钥Pa＝Na×G–B有自己的私钥Nb，并产生公钥Pb＝Nb×G加密（A要给B发送消息）–对明文m的编码点Pm，选择随机数k，密文C＝{C1，C2}＝{k×G，Pm＋k×Pb}解密：–编码点Pm＝C2－Nb×C1，因为＝(Pm＋k×Pb)－Nb×k×G＝Pm＋k×Nb×G－Nb×k×G＝Pm类ElGamal用EC的加解密原理–先是通过k×Pb掩盖Pm(即m)，又通过k×G掩盖k–知道陷门Nb则可以轻松恢复之分析–攻击者解C1＝k×G中的k困难性橢圓曲線的公開金鑰加密機制11111))(()()())(()()()(MGKBBrBrMGrRGrKBrMRKCMxxxxXxxxx椭圆曲线的数字签名Diffie-Hellman密钥交换取一素数p≈2180,两个参数a,b,得到Ep(a,b).取Ep(a,b)的一个生成元G(x1,y1),要求G的阶是一个非常大的素数。(阶是满足nG=O的最小正整数n).Ep(a,b)和G公开，A和B密钥交换过程如下–A选小于n的整数nA作为秘密钥，并有PA=nAG作为公钥–B类似选取自己的秘密钥nB和公开钥PB–A和B分别由K=nAPB和K＝nBPA产生共享的秘密钥攻击者如想获得K，必须由PA和G求出nA或PB和G求出nBElGamal密码体制密钥产生过程–选择一个素数p，以及g(gp),xp,计算公钥ygxmodp,(y,g,p)为公钥，x为秘密钥加密过程–M是发送明文组，选择随机数k，且(k,p－1)=1，计算：C1=gkmodp(随机数k被加密)C2=Mykmodp(明文被随机数k和公钥加密)–密文由C1、C2级连构成，即密文C=C1||C2。解密过程–M=C2/C1x=Myk/gkx=Mgxk/gkxmodpECC实现ElGamal密码体制选取一条椭圆曲线，得到Ep(a,b)。将明文消息通过编码嵌入曲线上得到点pm取Ep(a,b)的生成元G，Ep(a,b)和G为公开参数用户选取nA为秘密钥，PA=nAG为公开钥。加密：选随机正整数k，密文为Cm=(kG,Pm+kPA)解密：Pm+kPA-nAkG=Pm椭圆曲线公钥密码ECC根据这个数学难题，可以构造丰富的公钥密码体制，称为椭圆曲线公钥密码（ECC，略）。Certicom公司对ECC和RSA进行了对比，在实现相同的安全性下，ECC所需的密钥量比RSA少得多，如下表所示。其中MIPS表示用每秒完成100万条指令的计算机所需工作的年数，m表示ECC的密钥由2m点构成。以40MHz的钟频实现155bits的ECC，每秒可完成40,000次椭园曲线运算，其速度比1024bits的DSA和RSA快10倍。关于速度速度–在密钥长度相等的情况下，RSA和ECC的速度相当；–但是在相同的安全强度要求下，ECC可以使用较少的位数就可以；故–ECC较好–适合嵌入式设备中椭圆曲线公钥密码ECC因此ECC与RSA相比，更加简洁快速。具体地说，实现具有相同安全性的同类体制，ECC具有更小规模的软、硬件。ECC的密钥长度mRSA的密钥长度MIPS-年1601024101232051201036600210001078120012000010168椭圆曲线密码的安全性难点:从P和kP获得k对椭圆曲线研究的时间短椭圆曲线要求密钥长度短,速度快对比:ECCRSA*Pollardrho分析方法KeysizeMIPS-Yrs1503.810102057.110182341.6102851231047682108102431011128011014153631016204831020椭圆曲线算法与RSA算法的比较椭圆曲线公钥系统是代替RSA的强有力的竞争者。椭圆曲线加密方法与RSA方法相比，有以下的优点：（1）安全性能更高如160位ECC与1024位RSA、DSA有相同的安全强度。（2）计算量小，处理速度快在私钥的处理速度上（解密和签名），ECC远比RSA、DSA快得多。（3）存储空间占用小ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多，所以占用的存储空间小得多。（4）带宽要求低使得ECC具有广泛得应用前景。椭圆曲线密码体制的优点密钥量小–实现相同安全性条件下，ECC所需密钥量远下雨有限域上离散对数问题的公钥体制的密钥量灵活性好–通过改变参数可以获得不同的曲线，具有丰富的群结构和多选择性ECC的这些特点使它必将取代RSA，成为通用的公钥加密算法。比如SET协议的制定者已把它作为下一代SET协议中缺省的公