使用此椭圆曲线点乘法计算的点不在曲线上，并且此类带来算术异常 [英] Points calculated using this elliptic curve point multiplication do not lie on the curve and this class brings Arithmetic exception
本文介绍了使用此椭圆曲线点乘法计算的点不在曲线上，并且此类带来算术异常的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我使用标准投影坐标叠加我的点乘法误差。我不知道我错过了什么，但是增加的点不在曲线上，有些时候它输出像算术异常：整数不可逆。
I get stack on my error of point multiplication using standard projective coordinates. I don't know what i missed but the multiplied points do not lie on the curve and some times it outputs something like Arithmetic Exception: integer is not invertible.
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 = b.y.multiply(this.z).
subtract(this.y.multiply(b.z)).mod(this.ec.getP());
// v = X2 * Z1 - X1 * Z2
BigInteger v = b.x.multiply(this.z).
subtract(this.x.multiply(b.z)).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 = 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.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(b.z).add(u.multiply(v3)).mod(this.ec.getP());
// z3 = v^3 * z1 * z2
BigInteger z3 = v3.multiply(this.z).multiply(b.z).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函数，所以使用它来测试异常。
Elliptic curve digital signature Algorithm implementation is here. In this code there is main function so use this to test 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 || r.compareTo(param.getOrder()) >= 0) {
return false;
}
// s in the range [1,n-1]
if (s.compareTo(one) < 0 || s.compareTo(param.getOrder()) >= 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类
Here PrivateKey class
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类
PublicKey class
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;
}
}
Rand类
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和顺序是基数10，而不是基本16。此外，当您构造EllipticCurve对象时，您以错误的顺序提供参数。你的方法需要（a，b，p），但你用（p，a，b）所以我的猜测 p 不是正确的）。
The most important errors are in NISTCurves.P192: p and the order are in base-10, not in base-16. Also, when you construct the EllipticCurve-object, you provide the parameters in the wrong order. Your method requires (a, b, p), but you call it with (p, a, b) (so my guess about p not being prime was correct).
另一个问题是在您的验证方法，您打开 r 和 s 。由于它们是无符号格式，因此您应该使用 new BigInteger（1，rArr）而不是普通构造函数。
Another problem is in your verify-method, when you unwrap r and s. Since they are in unsigned format, you should use new BigInteger(1, rArr) instead of the normal constructor.
对于这些更改，您的代码适用于我（我可以验证签名 - 我没有验证实施的正确性）。
With those changes your code works for me (I can validate the signatures - I have not verified the correctness of the implementation).
（旧答案如下：
因为你没有给我们匹配stacktrace的代码，这只是一个猜测：
Since you have not given us the code that matches the stacktrace, this will merely be a guess:
在椭圆曲线加法期间（使用在主要领域的曲线），您应该只调用 BigInteger.modInverse（） code> p （素数字段的顺序）作为模数。
During elliptic curve addition (with a curve over a prime field), you should only be calling BigInteger.modInverse() with the prime p (the order of the prime field) as the modulus.
最有可能的方法是偶尔失败BigInteger not invertible是 p 实际上不是素数。
The most probable way for this to fail sporadically with "BigInteger not invertible" is if p is not actually a prime.
你在哪里得到 p from？尝试插入
Where are you getting p from? Try inserting
if(!ec.getP().isProbablePrime(100)) throw new RuntimeException("P is not a prime");
某处。
这篇关于使用此椭圆曲线点乘法计算的点不在曲线上，并且此类带来算术异常的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
