Fonction de multiplication de courbe elliptique

Question

J'essaie de créer ma propre bibliothèque pour la courbe elliptique. Certaines choses fonctionnent, mais d'autres ne fonctionnent pas.

Pour calculer une clé publique à partir d'une clé privée, vous devez multiplier le point de générateur par la clé privée et vous obtenez un autre point: la clé publique Point (ECPoint = BigInteger * ECPoint).

Maintenant, j'ai une clé privée, et je la multiplie avec le point de générateur de la courbe Secp256k1. Je reçois une clé, mais ce n'est pas la clé que je devrais avoir.

Ceci est mon code JAVA:

import java.math.BigInteger; 

public class Point{ 

    public static final Point INFINITY = new Point(); 

    private final BigInteger x; 
    private final BigInteger y; 

    private Point(){ 
     this.x = null; 
     this.y = null; 
    } 

    public Point(BigInteger x,BigInteger y){ 
     if(x==null || y==null){ 
      throw new NullPointerException("x or y is null"); 
     } 
     this.x = x; 
     this.y = y; 
    } 

    public BigInteger getX(){ 
     return this.x; 
    } 

    public BigInteger getY(){ 
     return this.y; 
    } 

    public boolean isInfinite(){ 
     return this.x==null || this.y==null; 
    } 

    public Point add(Curve ec,Point Q){ 
     Point P = this; 

     if(P.isInfinite()){ 
      return Q; 
     } 
     if(Q.isInfinite()){ 
      return P; 
     } 
     if(P.getX().equals(Q.getX()) && P.getY().equals(Q.getY())){ 
      return this.twice(ec); 
     } 

     BigInteger lambda = Q.getY().subtract(P.getY()).divide(Q.getX().subtract(P.getX())); 

     BigInteger xR = lambda.pow(2).subtract(P.getX()).subtract(Q.getX()); 
     BigInteger yR = lambda.multiply(P.getX().subtract(xR)).subtract(P.getY()); 

     Point R = new Point(xR,yR); 

     return R; 
    } 

    public Point twice(Curve ec){ 
     if(this.isInfinite()){ 
      return this; 
     } 

     BigInteger lambda = BigInteger.valueOf(3).multiply(this.getX().pow(2)).add(ec.getA()).divide(BigInteger.valueOf(2).multiply(this.getY())); 

     BigInteger xR = lambda.pow(2).subtract(this.getX()).subtract(this.getX()); 
     BigInteger yR = lambda.multiply(this.getX().subtract(xR)).subtract(this.getY()); 

     Point R = new Point(xR,yR); 

     return R; 
    } 

    public Point multiply(Curve ec,BigInteger k){ 
     //Point P = this; 
     //Point R = Point.INFINITY; 

     if(this.isInfinite()){ 
      return this; 
     } 

     if(k.signum()==0){ 
      return Point.INFINITY; 
     } 

     BigInteger h = k.multiply(BigInteger.valueOf(3)); 
     Point neg = this.negate(); 
     Point R = this; 

     for(int i=h.bitLength()-2;i>0;i--){ 
      R = R.twice(ec); 

      boolean hBit = h.testBit(i); 
      boolean eBit = k.testBit(i); 

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

     return R; 
    } 

    public Point negate(){ 
     if(this.isInfinite()){ 
      return this; 
     } 

     return new Point(this.x,this.y.negate()); 
    } 

} 

Y at-il quelque chose avec mon code? Existe-t-il un algorithme de multiplicateur spécifique pour secp256k1?

Answer 1

Oui, il y a un problème avec votre code; vous essayez de diviser en Z (en utilisant BigInteger) quand vous devez diviser en Zp (alias Z/pZ) où p est le paramètre de courbe définissant le champ sous-jacent (pour secp256k1 voir SEC2). La division modulaire est implémentée en Java en prenant l'inverse modulaire et la multiplication modulaire; voir Scalar Multiplication of Point over elliptic Curve. Aussi, vous devez prendre au moins les résultats finaux mod p, et il est généralement plus efficace de faire les résultats par étapes aussi bien.