1

I was wondering if there was a quick way to check that the group underlying the elliptic curve secp256k1 was indeed cyclic with the usual point G a generator. I am given the prime number underlying the field Fp, I am given the point G, I am given the integer orderwhich is presented as the order of the curve. I can check that the scalar multiplication order.G yields the infinity point. So I know that the order of G (i.e. the cardinal of its generated subgroup) divides order. I can check that order is a probable prime. So I reach the conclusion that the order of G is indeed order. But how do I know its generated subgroup is the whole elliptic curve?

import java.math.BigInteger;
import org.bitcoinj.core.ECKey;
import org.spongycastle.math.ec.ECCurve;
import org.spongycastle.math.ec.ECPoint;


public class Test {
  public static void main(String[] args){

  // secp256k1 elliptic curve
  ECCurve curve = ECKey.CURVE.getCurve();

  // the order of the curve
  BigInteger order = curve.getOrder();

  // fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
  System.out.println(order.toString(16));

  // The generator of the curve
  ECPoint G = ECKey.CURVE.getG();
  BigInteger X = G.getAffineXCoord().toBigInteger();
  BigInteger Y = G.getAffineYCoord().toBigInteger();

  // 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  System.out.println(X.toString(16));

  // 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
  System.out.println(Y.toString(16));


  // Computing scalar multiplication order.G
  ECPoint test = G.multiply(order);

  System.out.println(test.isInfinity());  // true

  // so we know the order of G (i.e. the cardinal of its
  // generated subgroup) divides 'order'. However:

  System.out.println(order.isProbablePrime(128)); // true

  // and G is not infinity. So the order of G is precisely order.
  // How do I check that the subgroup generated by G is actually 
  // the whole elliptic curve group, i.e. that the cofactor is 1?
  }
}
  • The generated subgroup is a set of size order, contained in the curve group which is also of size order. So they must be equal. ...? – Nate Eldredge Aug 25 '16 at 20:01
  • I was trying to justify the fact the curve group was of the same size (i.e. not bigger) – Sven Williamson Aug 25 '16 at 20:04
  • Wasn't order defined to be the size of the curve group? – Nate Eldredge Aug 25 '16 at 20:06
  • The library says it is. It is spitting out a number and a point G. I can check that this number is indeed the order of G. But I wanted also to check that it had to be the size of the whole curve. – Sven Williamson Aug 25 '16 at 20:10
  • 2
    Given that the curve order is prime, the only possibilities for the cofactor (which must be a divisor of the curve order) are 1 and the order itself. – Pieter Wuille Aug 25 '16 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.