Inverse modulo doesn't give the same result as in Java (with BigInteger)

[PeterMacGonagan]

Hello,

I'm trying to compute the inverse modulo with your function but I don't get the "correct" result. There is something I don't understand.

To illustrate, I made a simple example in java to compare:
inverse of 7 mod prime
with prime = 115792089237316195423570985008687907853269984665640564039457584007908834671663

Java (with BigInteger.modInverse) :
ModInv(7) = 0x db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6da9249214d
With you lib (secp256k1_scalar_inverse):
ModInv(7) = 0x 49249249249249249249249249249248c79facd43214c011123c1b03a93412a5

In each case, I test: a * inva = 1
and it works in Java and in cpp with your lib but it's weird because the number are not the same (I know that it's %prime).

I tried to multiply in java the inverse obtained in cpp by the number:
7 * 0xdb6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6da9249214d
= 0xfffffffffffffffffffffffffffffffd755db9cd5e9140777fa4bd1aa06c8654
And it's not equal to 1.

I don't understand... How to get the same result as Java, please? I don't see the trick.

Here is my code with your lib:

    secp256k1_scalar a = SECP256K1_SCALAR_CONST(0, 0, 0, 0, 0, 0, 0, 7);
    secp256k1_scalar inva;
    secp256k1_scalar r;

    secp256k1_scalar_inverse(&inva, &a);
    secp256k1_scalar_mul(&r, &a, &inva);

    printfscalar(a);
    printfscalar(inva);
    printfscalar(r); //r=1 ok it works

Thank you in advance.

[elichai]

The prime you've put is the field's order, not the scalar's order.
The scalar's order is 115792089237316195423570985008687907852837564279074904382605163141518161494337
And you can see with quick python that:

>>> hex(pow(7, -1, 115792089237316195423570985008687907852837564279074904382605163141518161494337))
0x49249249249249249249249249249248c79facd43214c011123c1b03a93412a5

And if you use the secp256k1_fe type you get:

  static const secp256k1_fe secp256k1_fe_seven = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 7);
  unsigned char sever_inv_bytes[32];
  secp256k1_fe inv_7;
  secp256k1_fe_inv(&inv_7, &secp256k1_fe_seven);
  secp256k1_fe_get_b32(sever_inv_bytes, &inv_7);
  printf("inv_7 = 0x");
  for (int i = 0; i < 32; i++)
      printf("%02x", sever_inv_bytes[i]);
  printf("\n");
  return 0;

Which prints the same as this python:

>>> hex(pow(7, -1, 115792089237316195423570985008687907853269984665640564039457584007908834671663))
'0xdb6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6db6da9249214d'

[PeterMacGonagan]

Ok, thank you. I'm not sure I understand completely.

scalar order: 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
 field order: 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f

I would like to code an elliptic addition only with add, mul, inverse, etc. But I don't get the correct results.

Maybe you could help me?

Here is my code:

inline void AddPoint(
    secp256k1_scalar* Rx, secp256k1_scalar* Ry, //the result: elliptic point: R = P + Q
    secp256k1_scalar* Px, secp256k1_scalar* Py, //elliptic point P
    secp256k1_scalar* Qx, secp256k1_scalar* Qy) //elliptic point Q
{
    //
    secp256k1_scalar a, m, m2;
    secp256k1_scalar tmp1, tmp2, tmp3, tmp4, tmp5, tmp6;

    //m=(Py-Qy)/(Px-Qx) % P = (Py-Qy) * a   %P
    
    //a = P.X.subtract(Q.X).modInverse(prime);      //a=inv(Px-Qx)  % P
    secp256k1_scalar_subtract(&tmp1, Px, Qx); //tmp1 = Px-Qx
    secp256k1_scalar_inverse(&a, &tmp1); //a = inv(tmp1) % P = inv(Px-Qx) % P

    printfscalar(*Px);
    printfscalar(*Qx);

    printfscalar(tmp1);
    printfscalar(a);

    //m = P.Y.subtract(Q.Y).multiply(a).mod(prime); //m=(Py-Qy)/(Px-Qx)  % P = (Py-Qy) * a  % P
    secp256k1_scalar_subtract(&tmp2, Py, Qy); //tmp2 = Py-Qy
    secp256k1_scalar_mul(&m, &tmp2, &a); // mod P ?

    printfscalar(m);
    printfscalar(tmp2);

    ...

I don't get the correct answer for a and m (may be the invmod?).

[sipa]

The X and Y coordinates on the elliptic curves are numbers modulo p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f. They are referred to as field elements in the libsecp256k1 source code, with type secp256k1_fe.

Points on the curve are referred to as group elements (secp256k1_ge and secp256k1_gej).

Scalars (secp256k1_scalar) are integers modulo the number of points on the curve, n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141. They're used for private keys, nonces, ...

You can't use scalars for field operations; the modulus will be wrong.