Proof that user public key corresponds the curve equation (secp256r1)

Question

I'm currently stuck at a problem, where I'm supposed to proove that the user public key of a returned u2f token corresponds to an elliptic curve equation (secp256r1). The token looks as follows:

05047d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef8cc6dd01e747ccb8bedaae6e7fb875d036ce7e4e6231b75b93993b15202829ac40d77b03735f1bc7716bd0df99790010495850502ebaf991c73f981a6f325db75869d98a03ca00c8471cab95832c0531cf3987238d0329dc5f780a0e4ca3eb419b3082021c30820106a003020102020424dbab40300b06092a864886f70d01010b302e312c302a0603550403132359756269636f2055324620526f6f742043412053657269616c203435373230303633313020170d3134303830313030303030305a180f32303530303930343030303030305a302b3129302706035504030c2059756269636f205532462045452053657269616c2031333530333237373838383059301306072a8648ce3d020106082a8648ce3d0301070342000402b094be347d477941c4778ebec5ca4ded2a479faa1e6fec39afebde0c2070cb5bd4bd69c96a78e3bf8751feb5791b8dfacac29401751cb157b97c09e4391a36a3123010300e060a2b0601040182c40a01010400300b06092a864886f70d01010b0382010100a363ae0e983af30bbaf12c8b2df35a59bf1cbb4a1b0fcb68c484558490f687345865b8db0269c346e553884c2c5607af0ea27b90ac8cf1ef431f72ac189db21c824914bf1788a5511a33d07b4c8e34647ce9f61e1516a9a9b36e900a402061f69aa46e12c532b993f9423efaaa4cf9a3b654b4dddef2924a548fd59995510dd4f7f4d9a4d52193873c71c9b87e86853e9e2da75e8f0c6d28305374d4efdd5e1496f8c33906107bd68bd6350daad2c37811eca3ca43bc930b734097def69d688d94550c4cfb18a9e24b86a2e5d88f499899a09bce5b810c536caf390dc8bdde960df330cacabc0521a18323957ffebca59ca90b20b10d09b5231c58c27eba6783304402206309fe66e6aa42c58ab156ed45efc120efb63abcac9d1d35a6237f99fbe1182102201462192f84f0fe1b6d2e4ce828f886264f249bafb585aa2c55f454e19e53a81a

At first I extracted the X and Y coordinates
x=56689369228784262545363082847328735491157691224156776757613891264163121815791
y=63675159857742677907627179845718530654249452333416428677953468052023208847788
and then SEC2v1 says that the elliptic curve looks like $y^2=x^3+a\,x+b$ and the $a$ and $b$ parameters are given there as well. So my thought was I just paste in $x$ into this equation to get $y^2$ and then take the square root of it. Unfortunately I keep getting wrong results.

What's wrong with my approach?

Answer 1

It is on the curve. Used the sageMath code supplied here for the NIST P-256 curve ( aka secp256r1). Test it online here

# Finite field prime
p256 = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF

# Curve parameters for the curve equation: y^2 = x^3 + a256*x +b256
a256 = p256 - 3
b256 = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B


px = 0x7d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef
py = 0x8cc6dd01e747ccb8bedaae6e7fb875d036ce7e4e6231b75b93993b15202829ac

print("The x-coordinate =", px)
print("The y-coordinate =", py)
print(py^2 % p256 )
print((px^3 + a256*px + b256) % p256)

outputs:

79438795822128695252942075663504569320626776578533931102248002205388342529032
79438795822128695252942075663504569320626776578533931102248002205388342529032

Note 1: The u2f standard can be found FIDO U2F Raw Message Formats

Note 2: there is no need to take the square root. Just compare both sides in the modulus of the curve. This eliminates extra square root calculations on the field.

A little elliptic curve;

In the finite field based Elliptic Curve, we take a finite field $F$ (prime field or finite field extension) and define a curve equation by $$y^2 + a_1xy + a_3y = x^3 + a_2x^2 + a_4x + a_6$$ This is Weierstrass equation.

If the field $F$ has characteristics different from 2 or 3 then the Weierstrass equation can be turned into the short form.

$$y^2 = x^3 + Ax +B$$

The equation is the standard short Weierstrass form. We don't want a singular curve so we check that the curve discriminant is non zero by $$2A^3-27B^2 \neq 0.$$

The points of the curve form an abelian group under the geometric interpretation with an identity element call $\mathcal{O}$, it can be the point at infinity like in secp256r1 or $(0,1)$ as the Edwards curves. The geometric interpretation of point addition turned into arithmetic over the field $F$.