Точки, рассчитанные с использованием этого умножения точек эллиптической кривой, не лежат на кривой, и этот класс приносит арифметическое исключение

Question

Я получаю стек от ошибки умножения точки с использованием стандартных проективных координат. Я не знаю, что я пропустил, но умноженные точки не лежат на кривой, а иногда выдает что-то вроде Арифметическое исключение: целое число не обратимо.

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(); 
} 

Эллиптическая кривая здесь. В этом коде есть основная функция, поэтому используйте это для проверки Исключения.

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 класс

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; 
    } 
} 

класс ОткрытыйКлюч

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; 
    }  
} 

Рэнд класс

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); 
} 

Answer 1

Наиболее важные ошибки приведены в NISTCurves.P192: p и порядок находятся в базе-10, а не в базе-16. Кроме того, когда вы создаете объект EllipticCurve, вы указываете параметры в неправильном порядке. Ваш метод требует (a, b, p), но вы называете его (p, a, b) (так что моя догадка о p не была правильной).

Другая проблема заключается в вашем методе проверки, когда вы разворачиваете r и s. Поскольку они находятся в неподписанном формате, вы должны использовать new BigInteger(1, rArr) вместо обычного конструктора.

С этими изменениями ваш код работает для меня (я могу проверить подписи - я не проверял правильность реализации).

---

(Старый ответ ниже :)

Поскольку вы не дали нам код, который соответствует StackTrace, это будет лишь предположение:

При эллиптической кривой сложения (с кривой над простое поле), вы должны только называть BigInteger.modInverse() с простым p (порядком простого поля) в качестве модуля.

Самый вероятный путь для этого, чтобы с ошибкой «BigInteger не обратимый», если p на самом деле не является простым.

Где вы принимаете? p? Попробуйте ввести

if(!ec.getP().isProbablePrime(100)) throw new RuntimeException("P is not a prime"); 

где-то.

Answer 2

Из кода Java JDK для BigInteger:

// Base and modulus are even, throw exception 
if (isEven()) 
    throw new ArithmeticException("BigInteger not invertible."); 

Кажется, что для метода modInverse(), то BigInteger не может быть четным числом.