java - 椭圆曲线中的点乘

Question

我在 Stack Overflow 上找到了以下算术代码，即:椭圆曲线点的加法、加倍和乘法。我尝试运行它并使用以下 NIST 例程文档中给出的测试用例，[NSA 提供了 NIST 椭圆曲线例程] (http://www.nsa.gov/ia/_files/nist-routines.pdf/)。

代码编译并运行，但输出与给定的预测值不匹配。请帮忙。

import java.lang.*;
import java.math.*;
import java.security.spec.*;
import java.util.*;

class ECPointArthimetic{

EllipticCurve ec;
ECFieldFp ef;
private BigInteger x;
private BigInteger y;
private BigInteger z;
private BigInteger zinv;
private BigInteger one = BigInteger.ONE;
private BigInteger zero = BigInteger.ZERO;
private boolean infinity;

public ECPointArthimetic(EllipticCurve ec, BigInteger x, BigInteger y, BigInteger z) {
    this.ec = ec;
    this.x = x;
    this.y = y;
    this.ef=(ECFieldFp)ec.getField();

    // Projective coordinates: either zinv == null or z * zinv == 1
    // z and zinv are just BigIntegers, not fieldElements
    if (z == null) 
    {
        this.z = BigInteger.ONE;
    } 
    else 
    {
        this.z = z;
    }
    this.zinv = null;
    infinity = false;
    //TODO: compression flag
}

public BigInteger getX() 
{
    if (this.zinv == null) 
    {
        this.zinv = this.z.modInverse(this.ef.getP());
    }
    return this.x.multiply(this.zinv).mod(this.ef.getP());
}

public BigInteger getY() 
{
    if (this.zinv == null) 
    {
        this.zinv = this.z.modInverse(this.ef.getP());
    }
    return this.y.multiply(this.zinv).mod(this.ef.getP());
}

public boolean pointEquals(ECPointArthimetic other) 
{
    if (other == this) 
    {
        return true;
    }
    if (this.isInfinity()) 
    {
        return other.isInfinity();
    }
    if (other.isInfinity()) 
    {
        return this.isInfinity();
    }
    BigInteger u, v;
    // u = Y2 * Z1 - Y1 * Z2
    u = other.y.multiply(this.z).subtract(this.y.multiply(other.z)).mod(this.ef.getP());
    if (!u.equals(BigInteger.ZERO)) 
    {
        return false;
    }
    // v = X2 * Z1 - X1 * Z2
    v = other.x.multiply(this.z).subtract(this.x.multiply(other.z)).mod(this.ef.getP());
    return v.equals(BigInteger.ZERO);
}

public boolean isInfinity() 
{

    if ((this.x == zero) && (this.y == zero)) 
    {
        return true;
    }
    return this.z.equals(BigInteger.ZERO) && !this.y.equals(BigInteger.ZERO);

}

public ECPointArthimetic negate() 
{
    return new ECPointArthimetic(this.ec, this.x, this.y.negate(), this.z);
}

public ECPointArthimetic add(ECPointArthimetic b) 
{
    if (this.isInfinity()) 
    {
        return b;
    }
    if (b.isInfinity()) 
    {
        return this;
    }
    ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
    // u = Y2 * Z1 - Y1 * Z2
    BigInteger u = b.y.multiply(this.z).subtract(this.y.multiply(b.z)).mod(this.ef.getP());
    // v = X2 * Z1 - X1 * Z2
    BigInteger v = b.x.multiply(this.z).subtract(this.x.multiply(b.z)).mod(this.ef.getP());

    if (BigInteger.ZERO.equals(v)) 
    {
        if (BigInteger.ZERO.equals(u)) 
        {
            return this.twice(); // this == b, so double
        }

        infinity = true; // this = -b, so infinity
        return R;
    }

    BigInteger THREE = new BigInteger("3");
    BigInteger x1 = this.x;
    BigInteger y1 = this.y;
    BigInteger x2 = b.x;
    BigInteger y2 = b.y;

    BigInteger v2 = v.pow(2);
    BigInteger v3 = v2.multiply(v);
    BigInteger x1v2 = x1.multiply(v2);
    BigInteger zu2 = u.pow(2).multiply(this.z);

    // x3 = v * (z2 * (z1 * u^2 - 2 * x1 * v^2) - v^3)
    BigInteger x3 = zu2.subtract(x1v2.shiftLeft(1)).multiply(b.z).subtract(v3).multiply(v).mod(this.ef.getP());

    // y3 = z2 * (3 * x1 * u * v^2 - y1 * v^3 - z1 * u^3) + u * v^3
    BigInteger y3 = x1v2.multiply(THREE).multiply(u).subtract(y1.multiply(v3)).subtract(zu2.multiply(u)).multiply(b.z).add(u.multiply(v3)).mod(this.ef.getP());

    // z3 = v^3 * z1 * z2
    BigInteger z3 = v3.multiply(this.z).multiply(b.z).mod(this.ef.getP());

    return new ECPointArthimetic(this.ec, x3, y3, z3);
}

public ECPointArthimetic twice() 
{
    if (this.isInfinity()) 
    {
        return this;
    }
    ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
    if (this.y.signum() == 0) 
    {
        infinity = true;
        return R;
    }

    BigInteger THREE = new BigInteger("3");
    BigInteger x1 = this.x;
    BigInteger y1 = this.y;

    BigInteger y1z1 = y1.multiply(this.z);
    BigInteger y1sqz1 = y1z1.multiply(y1).mod(this.ef.getP());
    BigInteger a = this.ec.getA();

    // w = 3 * x1^2 + a * z1^2
    BigInteger w = x1.pow(2).multiply(THREE);

    if (!BigInteger.ZERO.equals(a)) 
    {
        w = w.add(this.z.pow(2).multiply(a));
    }

    w = w.mod(this.ef.getP());

    // x3 = 2 * y1 * z1 * (w^2 - 8 * x1 * y1^2 * z1)
    BigInteger x3 = w.pow(2).subtract(x1.shiftLeft(3).multiply(y1sqz1)).shiftLeft(1).multiply(y1z1).mod(this.ef.getP());

    // y3 = 4 * y1^2 * z1 * (3 * w * x1 - 2 * y1^2 * z1) - w^3
    BigInteger y3 = (w.multiply(THREE).multiply(x1).subtract(y1sqz1.shiftLeft(1))).shiftLeft(2).multiply(y1sqz1).subtract(w.pow(2).multiply(w)).mod(this.ef.getP());

    // z3 = 8 * (y1 * z1)^3
    BigInteger z3 = y1z1.pow(2).multiply(y1z1).shiftLeft(3).mod(this.ef.getP());

    return new ECPointArthimetic(this.ec, x3, y3, z3);
}

public ECPointArthimetic multiply(BigInteger k) 
{
    if (this.isInfinity()) 
    {
        return this;
    }

    ECPointArthimetic R = new ECPointArthimetic(this.ec, zero, zero, null);
    if (k.signum() == 0) 
    {
        infinity = true;
        return R;
    }

    BigInteger e = k;
    BigInteger h = e.multiply(new BigInteger("3"));

    ECPointArthimetic neg = this.negate();
    R = this;

    int i;
    for (i = h.bitLength() - 2; i > 0; --i) 
    {
        R = R.twice();
        boolean hBit = h.testBit(i);
        boolean eBit = e.testBit(i);

        if (hBit != eBit) {
            R = R.add(hBit ? this : neg);
        }
    }

    return R;
}


}

class ECMath{
public static void main(String args[])
{
    //sx,sy,tx,ty are provided coordinates, and so is d which is a random integer, to be used later as a private key
    BigInteger sx = new BigInteger("d458e7d127ae671b0c330266d246769353a012073e97acf8",16);
    BigInteger sy = new BigInteger("325930500d851f336bddc050cf7fb11b5673a1645086df3b",16);
    BigInteger tx = new BigInteger("f22c4395213e9ebe67ddecdd87fdbd01be16fb059b9753a4",16);
    BigInteger ty = new BigInteger("264424096af2b3597796db48f8dfb41fa9cecc97691a9c79",16);
    BigInteger d = new BigInteger("2854434767935089551580740784991073913165554873467591589150");

    String p192X = "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012";
    String p192Y = "07192b95ffc8da78631011ed6b24cdd573f977a11e794811";
    String p192B = "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1";
    String p192P = "6277101735386680763835789423207666416083908700390324961279";
    String p192Order = "6277101735386680763835789423176059013767194773182842284081";
    String p192A = "-3";

    BigInteger p = new BigInteger(p192P, 16);
    BigInteger gx = new BigInteger(p192X, 16);
    BigInteger gy = new BigInteger(p192Y, 16);
    ECFieldFp ef= new ECFieldFp(p);
    EllipticCurve ec =  new EllipticCurve(ef,new BigInteger(p192A).mod(p),new BigInteger(p192B, 16));
    ECPointArthimetic G = new ECPointArthimetic(ec, new BigInteger(p192X,16), new BigInteger(p192Y,16),null);
    BigInteger order = new BigInteger(p192Order, 16);

    ECPointArthimetic ga = new ECPointArthimetic(ec,gx,gy,null);
    ECPointArthimetic sa = new ECPointArthimetic(ec,sx,sy,null);
    ECPointArthimetic ta = new ECPointArthimetic(ec,tx,ty,null);

    ECPointArthimetic resAdd = sa.add(ta);
    ECPointArthimetic resMul = ga.multiply(d);

    System.out.println(resAdd.getX().toString(16));
    System.out.println(resAdd.getY().toString(16));

    System.out.println(resMul.getX().toString(16));
    System.out.println(resMul.getY().toString(16));

}
}

Answer 1

您有exactly the same problem如Clickmit Wg :p192P 和 p192Order 以 10 为基数给出，而不是以 16 为基数。因此您应该使用 new BigInteger(value) 而不是 new BigInteger(value, 16 code>) 构造质数和顺序实例。