使用此椭圆曲线点乘法计算的点不在曲线上，并且此类带来算术exception
我使用标准投影坐标得到了我的点乘法误差。 我不知道我错过了什么，但是乘法点不在曲线上，有时它会输出类似算术exception的东西：整数不可逆。
public class ECPointArthimetic { EllipticCurve ec; 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; // 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.ec.getP()); } return this.x.multiply(this.zinv).mod(this.ec.getP()); } public BigInteger getY() { if (this.zinv == null) { this.zinv = this.z.modInverse(this.ec.getP()); } return this.y.multiply(this.zinv).mod(this.ec.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.ec.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.ec.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 = bymultiply(this.z). subtract(this.y.multiply(bz)).mod(this.ec.getP()); // v = X2 * Z1 - X1 * Z2 BigInteger v = bxmultiply(this.z). subtract(this.x.multiply(bz)).mod(this.ec.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 = bx; BigInteger y2 = by; 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(bz). subtract(v3).multiply(v).mod(this.ec.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(bz).add(u.multiply(v3)).mod(this.ec.getP()); // z3 = v^3 * z1 * z2 BigInteger z3 = v3.multiply(this.z).multiply(bz).mod(this.ec.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.ec.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.ec.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.ec.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.ec.getP()); // z3 = 8 * (y1 * z1)^3 BigInteger z3 = y1z1.pow(2).multiply(y1z1).shiftLeft(3).mod(this.ec.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; } public ECPointArthimetic implShamirsTrick( BigInteger k, ECPointArthimetic Q, BigInteger l){ int m = Math.max(k.bitLength(), l.bitLength()); ECPointArthimetic Z = this.add(Q); ECPointArthimetic R = new ECPointArthimetic(ec,zero,zero,null); for (int i = m - 1; i >= 0; --i){ R = R.twice(); if (k.testBit(i)){ if (l.testBit(i)){ R = R.add(Z); }else{ R = R.add(this); } }else{ if (l.testBit(i)){ R = R.add(Q); } } } return R; } } 这是我使用的曲线：
package NISTCurves; import ecc.*; import java.math.BigInteger; public class P192 implements ECDomainParameters { String p192X = "188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012"; String p192Y = "07192b95ffc8da78631011ed6b24cdd573f977a11e794811"; String p192B = "64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1"; String p192P = "6277101735386680763835789423207666416083908700390324961279"; String p192Order = "6277101735386680763835789423176059013767194773182842284081"; String p192A = "-3"; BigInteger p = new BigInteger(p192P, 16); EllipticCurve ec = new EllipticCurve(p, 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); @Override public BigInteger getP() { return p; } @Override public EllipticCurve getECCurve() { return ec; } @Override public BigInteger getOrder() { return order; } @Override public ECPointArthimetic getGenerator() { return G; } }
椭圆曲线域参数的规范
package NISTCurves; import ecc.ECPointArthimetic; import ecc.EllipticCurve; import java.math.BigInteger; public interface ECDomainParameters { public BigInteger getP(); public ECPointArthimetic getGenerator(); public EllipticCurve getECCurve(); public BigInteger getOrder(); }
椭圆曲线数字签名算法实现在这里。 在这段代码中有main函数，所以用它来测试Exception。
package ecc; import NISTCurves.ECDomainParameters; import NISTCurves.P192; import java.io.FileNotFoundException; import java.io.IOException; import java.math.BigInteger; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; /** * * @author Gere */ public class ECDSA { private BigInteger r, s; ECDomainParameters param; private PrivateKey prvKey; private PublicKey pubKey; BigInteger zero = BigInteger.ZERO; private BigInteger one = BigInteger.ONE; private MessageDigest sha; public ECDSA() { try { sha = MessageDigest.getInstance("SHA-512"); } catch (NoSuchAlgorithmException ex) { ex.printStackTrace(); } } public void initSign(PrivateKey prvKey) { this.prvKey = prvKey; param = prvKey.getParam(); } public void initVerify(PublicKey pubKey) { this.pubKey = pubKey; param = pubKey.getParam(); } public void update(byte[] byteMsg) { sha.update(byteMsg); } public byte[] sign() throws FileNotFoundException, IOException { BigInteger c = new BigInteger( param.getP().bitLength() + 64, Rand.sr); BigInteger k = c.mod(param.getOrder().subtract(one)).add(one); while (!(k.gcd(param.getOrder()).compareTo(one) == 0)) { c = new BigInteger(param.getP().bitLength() + 64, Rand.sr); k = c.mod(param.getOrder().subtract(one)).add(one); } BigInteger kinv = k.modInverse(param.getOrder()); ECPointArthimetic p = param.getGenerator().multiply(k); if (p.getX().equals(zero)) { return sign(); } BigInteger hash = new BigInteger(sha.digest()); BigInteger r = p.getX().mod(param.getOrder()); BigInteger s = (kinv.multiply((hash.add((prvKey.getPrivateKey() .multiply(r)))))).mod(param.getOrder()); if (s.compareTo(zero) == 0) { return sign(); } System.out.println("r at sign: " + r); System.out.println("s at sign: " + s); byte[] rArr = toUnsignedByteArray(r); byte[] sArr = toUnsignedByteArray(s); int nLength = (param.getOrder().bitLength() + 7) / 8; byte[] res = new byte[2 * nLength]; System.arraycopy(rArr, 0, res, nLength - rArr.length, rArr.length); System.arraycopy(sArr, 0, res, 2 * nLength - sArr.length, sArr.length); return res; } public boolean verify(byte[] res) { int nLength = (param.getOrder().bitLength() + 7) / 8; byte[] rArr = new byte[nLength]; System.arraycopy(res, 0, rArr, 0, nLength); r = new BigInteger(rArr); byte[] sArr = new byte[nLength]; System.arraycopy(res, nLength, sArr, 0, nLength); s = new BigInteger(sArr); System.out.println("r at verify: " + r); System.out.println("s at verify: " + s); BigInteger w, u1, u2, v; // r in the range [1,n-1] if (r.compareTo(one) = 0) { return false; } // s in the range [1,n-1] if (s.compareTo(one) = 0) { return false; } w = s.modInverse(param.getOrder()); BigInteger hash = new BigInteger(sha.digest()); u1 = hash.multiply(w); u2 = r.multiply(w); ECPointArthimetic G = param.getGenerator(); ECPointArthimetic Q = pubKey.getPublicKey(); // u1G + u2Q ECPointArthimetic temp = G.implShamirsTrick(u1, Q, u2); v = temp.getX(); v = v.mod(param.getOrder()); return v.equals(r); } byte[] toUnsignedByteArray(BigInteger bi) { byte[] ba = bi.toByteArray(); if (ba[0] != 0) { return ba; } else { byte[] ba2 = new byte[ba.length - 1]; System.arraycopy(ba, 1, ba2, 0, ba.length - 1); return ba2; } } public static void main(String[] args) { byte[] msg = "Hello".getBytes(); byte[] sig = null; ECDomainParameters param = new P192(); PrivateKey prvObj = new PrivateKey(param); PublicKey pubObj = new PublicKey(prvObj); ECDSA ecdsa = new ECDSA(); ecdsa.initSign(prvObj); ecdsa.update(msg); try { sig = ecdsa.sign(); } catch (FileNotFoundException ex) { System.out.println(ex.getMessage()); } catch (IOException ex) { System.out.println(ex.getMessage()); } ecdsa.initVerify(pubObj); ecdsa.update(msg); if (ecdsa.verify(sig)) { System.out.println("valid"); } else { System.out.println("invalid"); } } }
这里是PrivateKey类
package ecc; import NISTCurves.ECDomainParameters; import java.math.BigInteger; import java.security.SecureRandom; /** * * @author Gere */ public class PrivateKey { private BigInteger d; private ECDomainParameters param; private BigInteger one = BigInteger.ONE; private BigInteger zero; private PublicKey pubKey; public PrivateKey(ECDomainParameters param) { this.param = param; BigInteger c = new BigInteger(param.getOrder().bitLength() + 64, new SecureRandom()); BigInteger n1 = param.getOrder().subtract(one); d = c.mod(n1).add(one); pubKey = new PublicKey(this); } public BigInteger getPrivateKey() { return d; } public ECDomainParameters getParam() { return param; } }
PublicKey类
package ecc; import NISTCurves.ECDomainParameters; /** * * @author Gere */ public class PublicKey { private ECDomainParameters param; private ECPointArthimetic Q; public PublicKey(PrivateKey privObj) { param = privObj.getParam(); Q = param.getGenerator().multiply(privObj.getPrivateKey()); } public ECDomainParameters getParam() { return param; } public ECPointArthimetic getPublicKey() { return Q; } }
椭圆曲线
package ecc; import java.math.BigInteger; /** * * @author Gere */ public class EllipticCurve { private BigInteger a; private BigInteger b; private BigInteger p; public EllipticCurve(BigInteger a, BigInteger b, BigInteger p) { this.a = a; this.b = b; this.p = p; } public BigInteger getA() { return a; } public BigInteger getB() { return b; } public BigInteger getP() { return p; } }
兰德class
package ecc; import java.security.SecureRandom; /** * * @author Gere */ public class Rand { public static final SecureRandom sr = new SecureRandom(); }
椭圆曲线界面
package ecc; import java.math.BigInteger; public interface ECConstants{ public static final BigInteger zero = BigInteger.valueOf(0); public static final BigInteger one = BigInteger.valueOf(1); public static final BigInteger two = BigInteger.valueOf(2); public static final BigInteger three = BigInteger.valueOf(3); public static final BigInteger four= BigInteger.valueOf(4); }
最重要的错误在NISTCurves.P192：p中，顺序在base-10中，而不在base-16中。 此外，在构造EllipticCurve对象时，以错误的顺序提供参数。 你的方法需要(a, b, p) ，但你用(p, a, b)调用它（所以我猜p不是素数是正确的）。
另一个问题是你的validation方法，当你解开r和s 。 由于它们是无符号格式，因此应使用new BigInteger(1, rArr)而不是普通的构造函数。
通过这些更改，您的代码适用于我（我可以validation签名 – 我还没有validation实现的正确性）。
（旧答案:)
既然你还没有给我们提供与堆栈跟踪相匹配的代码，那么这只是一个猜测：
在椭圆曲线加法期间（在素数场上有一条曲线），你应该只用素数p （素数场的阶数）作为模数调用BigInteger.modInverse() 。
如果p实际上不是一个素数，那么偶然失败的最可能的方法是“BigInteger不可逆”。
你从哪里得到p ？ 尝试插入
if(!ec.getP().isProbablePrime(100)) throw new RuntimeException("P is not a prime");
某处。
从BigInteger的JDK java代码：
// Base and modulus are even, throw exception if (isEven()) throw new ArithmeticException("BigInteger not invertible.");
似乎对于modInverse()方法， BigInteger可能不是偶数。