3
$\begingroup$

I need to verify that the point in this public key

04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca

is in secp256r1. I already know the parameters $a$ and $b$ of the curve, but they are pretty big and they are hexadecimal. I've been trying to pass it to decimal, but I'm not getting it. Should I compute it in hexadecimal? I do also don't understand what are the coordinates of the public key. I mean, the public key is supposed to be a point with x-coordinate and the least important part of the y-coordinate, as the public key begins by 04, isn't it? I'm really sorry, but I'm confused about how to approach this.

Note: I saw some questions that were basically the same as mine, but the numbers were much smaller. I do also have PARI/GP to use.

EDIT: I tried with SageMath, and the result was

y = 98344895439910594971593461997930184197459096557735598026509132013917697767882
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

Then, I tried y^2 == x^3 + a*x + b, and it gave False, but I know beforehand that the point belongs to the curve. Can you tell me what I am doing wrong?.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

An Elliptic curve defined over the finite Field $\mathbb F_p$ means that all of the coordinates are elements of $\mathbb F_p$, i.e. in affine coordinates, let $P=(x,y)$ be a point then $x,y \in \mathbb F_p$. Actually, all of the arithmetic is done over $\mathbb F_p$

In the encoding

04 11 95 23 03 f0 f1 f1 45 67 14 98 e4 39 80 ce 25 39 02 6e 72 34 fe 02 38 8a ea cc fb 3a 3d 4d dc d9 6d 3c fe 8b 55 bf ea c3 3a a1 59 13 54 b3 91 79 45 b7 3b 49 d9 0e 96 2a de 79 d3 49 dc 79 ca

The first byte defines the compression and 04 means there is no compression. So, after removing the 04, the first half belongs to $x$ and the second half belongs to $y$ coordinate of the point.

You forgot to take $\bmod p$.

With testing equality of both sides

#Sagemath
x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

print(y^2 % p)
print( (x^3 + a * x + b) % p )
#or test with assert
assert(y^2 % p == (x^3 + a * x + b) % p)

outputs

107039974491263683037557989129009082794410266580376414531485756411379666775575
107039974491263683037557989129009082794410266580376414531485756411379666775575

Therefore it is a valid point on the curve.

Using Curves on SageMath

There is another way, and maybe easier on the SageMath. This method uses the Elliptic Curve construction and defining point on the curve.

#secp256r1
a = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = Integer("0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
p = Integer("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")

K = GF(p)
E = EllipticCurve(K,[a,b])

x = Integer("0x11952303f0f1f145671498e43980ce2539026e7234fe02388aeaccfb3a3d4ddc")
y = Integer("0xd96d3cfe8b55bfeac33aa1591354b3917945b73b49d90e962ade79d349dc79ca")

P = E(x,y) ### try to set the point with the coordinates.

If the $P$ is not a point on the curve, you will get many errors

Further notes

In the next steps, you may want to add/double points. The elliptic curve uses special formulas for point addition. You may find them here, or use directly Sagemath, you can just use addition for point additions P+Q and 5*P for scalar multiplication where it is usually written as $[5]P = P + P + P + P +P$

Representation of the point on infinity

Points on the elliptic curve together with the point at infinity $\mathcal{O}$ form an abelian group under point addition law. For secp256r1;

$$E(\mathbb{F_p}) := \{ (x, y) \in \mathbb{F}^2_p \mid y^2= x^3 + a\cdot x + b\} \cup \{\mathcal O\}$$

As we can see, the $\mathcal O$ has no representation on the affine coordinates, we magically add it to the group definition. While mathematically we can handle this, programmatically we need to represent it. If $b \neq 0 \bmod p$ then coordinate $(0,0)$ doesn't satisfy the curve equation therefore it is not on the curve, therefore it is a good choice for representation of $\mathcal O$ and usually selected this way. While working with the libraries always check that how the $\mathcal O$ is represented.

$\endgroup$
2
  • $\begingroup$ I had forgotten to take mod p. Thanks so much @kelalaka for all the help!!! $\endgroup$
    – Anonymous
    Commented May 23, 2021 at 20:38
  • 2
    $\begingroup$ Now you can upvote, too. have fun. $\endgroup$
    – kelalaka
    Commented May 23, 2021 at 20:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.