1、1.椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似，一般来计，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e （1）其中a,b,c,d,e是满足某些简单条件的实数。其中包括称为无穷远点的元素。密码中普遍采用的是有限域上的椭圆曲线，有限域上的椭圆曲线是指曲线方程定义式（1）中，所有系数都是某一有限域GF（p）中的元素（其中p为一大素数）。其中最为常用的是由方程y2x3+ax+b （mod p）定义的曲线。（a,bGF（p）, 4a2+27b30 mod p）椭圆曲线上的加法运算定义如下：（1）设L是通过P和Q的直线。L交
2、E于P和Q，容易看出，L还交E于第三点，记作R。对x轴反射R，得到一点R,定义P+Q=R。见图1和图2. 图2中的P点和Q点重合。（2） o为加法单位元（无穷远点），即对椭圆曲线上任一点P，有P+o=o+P=P.（3）P=（x,y）是椭圆曲线上的一点，它的加法逆元定义为-P=（x,-y）P+（-P）=o下面给出一个计算R的代数公式。椭圆曲线E上的两点P=（x1,y1）和Q=（x2,y2）可以按照下面的规则相加：（1） 如果x2=x1 ,y2=-y1,则P+Q=o;否则P+Q=（x3,y3）,其中x32-x1-x2 （mod p）y3（x1-x3）-y1 （mod p）其中是直线L的斜率，（y2
3、-y1）（x2-x1）-1 mod p 当PQ时（3x12+a）（2y1）-1 mod p 当P=Q时举例：设E是Z11上的椭圆曲线y2x3+x+6。请确定E上的点。解：从y2x3+x+6看出，a=1,b=6,则4a3+27b280 mod 11 所以该椭圆曲线可用于密码体制。（1） 当x=0时y26 mod 11 （2）现在求解方程（2），首先根据legendre符号来判断方程（2）有没有解：而可见方程（2）无解。（2） 当x=1时，方程变为y28 mod 11 （3）现判断方程（3）有没有解。所以方程（3）也无解。（3） 当x=2时，方程变为y25 mod 11 （4）方程（4）有解，其解
4、为y5（11+1）/4534 （mod 11）即有两个点（2，4），（2，-4）（4）当x=3时，y23 mod 11 （5）因为所以方程（5）有解，其解为：3（11+1）/4335 （mod 11）即有两个点（3，5），（3，-5）同理可以算出：当x=4,5,6,7,8,9,10时各方程解。结果如下表所示：xX3+x+6 mod 11是否为二次剩余y6否1825是4，735，642，9793，810可见E有13点（包括无穷远点o）.假设取p=（2，7）,计算2P:2P=P+P（3x12+a）（2y1）-1 mod p（322+1）（27）-1 mod 1123-1 mod 118 mod 1
5、1x32-x1-x2 （mod p） 82-2-25 mod 11y3（x1-x3）-y1 （mod p） 8（2-5）-72 mod 11所以 2P=（5，2）下面计算3P3P=2P+P=（5,2）+（2,7）（y2-y1）（x2-x1）-1 mod p （7-2）（2-5）-1 mod p5（-3）-1 mod p58-12 mod 11x32-x1-x2 （mod p） 22-5-28 mod 11y3（x1-x3）-y1 （mod p） 2（5-8）-23 mod 11可见3P=（8，3）如此继续下去，其余的乘积计算结果如下：P=（2，7） 2P=（5，2） 3P=（8，3）4P=（1
6、0，2） 5P=（3，6） 6P=（7，9）7P=（7，2） 8P=（3，5） 9P=（10，9）10P=（8，8） 11P=（5，9） 12P=（2，4）2.椭圆曲线上的密码体制（1） ElGamal密码体制设p是一个素数，g是Zp*的一个生成元（也叫原根）。明文空间P=Zp*，密文空间C= Zp*Zp*，选定0ap，计算bga mod p。私钥：a 公钥： b加密算法：设明文为m，0mp，随机地选择一个正整数k，0kp，计算：y1gk mod p, y2mbk mod p密文c=（ y1,y2 ）解密算法： my2 y1-a mod p（2）基于椭圆曲线的ElGamal密码体制首先选取一条
7、满足4a3+27b20 mod p的椭圆曲线Ep（a,b），将明文消息通过编码嵌入到曲线上得点Pm，再对点Pm 做加密变换。 取Ep（a,b）上的一个点, Ep（a,b）和G作为公开参数用户选nA作为秘密钥，并以PA=nAG作为公开密钥。任一用：1）加密：用户B若想向A发送消息Pm，可选取一随机正整数k ，产生以下密文对：Cm=kG，Pm+kPA=C1,C22）解密： C2- nAC1= Pm+kPA- nA kG = Pm+k nA G - nA kG= Pm利用上例的椭圆曲线y2x3+x+6。取G=（2，7）,私钥nA=7,则公钥为PA=nAG=7（2，7）=（7，2）若明文Pm=（10，
8、9），取随机数k=3,加密：C1= kG=3（2，7）=（8，3）C2= Pm+kPA=（10,9）+3（7，2）=（10,2）解密： Pm= C2- nAC1=（10,2）-7（8，3）=（10,2）-（3，5）=（10,2）+（3，6）=（10，9）3.椭圆曲线密码算法的优点ECC与RSA比较，有很多技术优点：（1）安全性能更高安全性能占绝对优势，ECC在计算复杂度上目前是完全指数级的，而RSA是亚指数级。（2）计算量小和处理速度快。（3）存储空间小。160bit的ECC与1024bit的RSA具有相同的安全强度210bit的ECC与2048bit的RSA具有相同的安全强度。意味着它所占的存储空间要小得多。这对于加密算法在资源受限环境上（如智能卡等）的应用具有特别重要的意义。（4）带宽要求低。习题：求出椭圆曲线E：y2x3-2 mod 7上的点，并：（1） 在E上找到（3，2）+（6，5）的和。（2） 在E上找到（3，2）+（3，2）的和。
