椭圆曲线ECC倍点运算forJava

前段时间写一个审计系统时，用到了椭圆曲线的数字签名技术。 在计算其倍点时，一开始我使用点与点相加的基本算式进行迭代运算。 但发现效率很低。最后想了想，进行了如下的改进（其实也是参考《密码编码学与网络安全》第6版一书中的一个思路，进行了如下的书写）。

package com.pathfinder.function;

import java.io.FileInputStream;

import java.math.BigInteger;

import java.util.ArrayList;

import java.util.List;

public class Algorithm {

private int a;

private int b;

private int q; 

public Algorithm(int a, int b, int q) {

this.a = a;

this.b = b;

this.q = q;

}

public int getA() {

return a;

}

public void setA(int a) {

this.a = a;

}

public int getB() {

return b;

}

public void setB(int b) {

this.b = b;

}

public int getQ() {

return q;

}

public void setQ(int q) {

this.q = q;

}

public String OutsAlgorithm(long n,String s)

{

List<Byte> er=new ArrayList<Byte>();//存放转化为二进制的数

List<String> dian=new ArrayList<String>();

if(n!=0)

{

//把要计算的值，转为二进制数，然后在二进制的每位上做相应的二倍运算，最后再把所有的相加

while(n!=0)

{

byte i=(byte)(n%2);

er.add(i);

n=n/2;

}

for(int i=0;i<er.size();i++)

{

if(er.get(i)==1)

dian.add(s);

s=multiple2Operation(s);//二倍  倍点运算算法 计算一个点的n倍的算法

}

s=dian.get(0);

for(int i=1;i<dian.size();i++)

{

s=addOperation(s, dian.get(i));//计算两个不同点相加的运算

}

return s;

}

else

{

return "0v0";

}

}

public String multiple2Operation(String g)

{

int x=2;

String[] vp=g.split("v");

int xp=Integer.parseInt(vp[0]);

int yp=Integer.parseInt(vp[1]);

if(yp==0)

{

return  "0v0"; //TODO y为0的时候怎么办？

}

else

{

long Numerator=3*xp*xp+a;//分子

    long denominator=2*yp;//分母

    denominator=niyuan(denominator,q,1,0);// 计算分母的逆元

    while(denominator<0)

    {

    denominator=denominator+q;

    }

    long ratio=(long)(Numerator*denominator)%q;//计算  入  的值  及斜率

long xrr=(long)(ratio*ratio-2*xp);

while(xrr<0)

{

xrr=xrr+q;

}

int Xr=(int)(xrr%q);//横坐标

long Yrr=(long)(ratio*(xp-Xr)-yp);

while(Yrr<0)

{

Yrr=Yrr+q;

}

int Yr=(int)(Yrr%q);

return Xr+"v"+Yr;//返回2倍点的坐标

}

}

public String addOperation(String V,String v1)

{

if(v1.equals(V))

{

return multiple2Operation(V);//如果两个点相等，直接调用倍点运算

}

else

{

String[] vp=V.split("v");

String[] vq=v1.split("v");

if(vp[0].equals(vq[0]))//两个的x值相等

{

return "0v0";

}

else

{

//排错

if(v1.equals("0v0"))

return V;

else if(V.equals("0v0"))

return v1;

//运算

else

{

//第一个点的x y坐标

int xp=Integer.parseInt(vp[0]);

int yp=Integer.parseInt(vp[1]);

//第二个点的x y坐标

int xq=Integer.parseInt(vq[0]);

int yq=Integer.parseInt(vq[1]);

long DValueY=(long)yq-yp;//y的差值

while(DValueY<0)

{

DValueY=DValueY+q;

}

long DValueX=(long)xq-xp;//x的差值

while(DValueX<0)

{

DValueX=DValueX+q;

}

DValueX=niyuan(DValueX,q,1,0);

    while(DValueX<0)

    {

    DValueX=DValueX+q;

    }

    long ratio=(long)(DValueY*DValueX)%q;

long xrr=(long)(ratio*ratio-xp-xq);

while(xrr<0)

{

xrr=xrr+q;

}

int xr=(int)(xrr%q);

long yrr=(long)(ratio*(xp-xr)-yp);

while(yrr<0)

{

yrr=yrr+q;

}

int yr=(int)(yrr%q);

//返回值

return xr+"v"+yr;

}

}

}

}

public long niyuan(long r1,long r2,long x1,long x2)

{

long qr=r1/r2;

long r=r1%r2;

long x=x1-qr*x2;

if(r==1)

{

return x;

}

else

return niyuan(r2,r,x2,x);

}

//END

}

欢迎各位大侠提出意见。相互学习