1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ The curve's equation is not in the integers $\mathbb Z$ or the reals $\mathbb R$. Its in a finite field. It's specified which is the spec you linked. Also, to test an equality, the most natural method goes: compute both sides and compare. Your method with a square root will sometime reach a wrong conclusion (if we where in the field $\mathbb R$: when $y$ is negative; and there are analogs in other fields). $\endgroup$
    – fgrieu
    Oct 26 '20 at 7:34
  • $\begingroup$ Your token might not be uncompressed there is 02 in the front of the public key. This simply explains why they need 65-bytes in the standard, too. But still conflict since why did they need extra 32. $\endgroup$
    – kelalaka
    Oct 26 '20 at 7:54
  • $\begingroup$ @kelalaka Is there? I figured out the public key was 047d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef8cc6dd01e747ccb8bedaae6e7fb875d036ce7e4e6231b75b93993b15202829ac or am I wrong with that? Thanks a lot for your response though. :) $\endgroup$
    – Steven
    Oct 26 '20 at 8:27
  • $\begingroup$ @fgriue Thanks for your response, but isn't the eliptic curve inside of the field? Maybe I missunderstand something, but I thought that the eliptic curve lays inside of the finite field and if that's the case shouldnt my calculation lead to a true statement? I'm reallly sorry if i messed something up. $\endgroup$
    – Steven
    Oct 26 '20 at 8:43
  • $\begingroup$ The arithmetic of the equation is in the field $\mathbb F_p$ (that is, the integers modulo $p$) with $p$ the prime in the spec. Your task is to harness the right tools to compute both sides of the equation in that field (then compare). $\endgroup$
    – fgrieu
    Oct 26 '20 at 9:12
2
$\begingroup$

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$.

$\endgroup$
7
  • $\begingroup$ Wow, thanks a lot for the effort! :) Unfortunately I'm supposed to figure it out "by hand". Do you know if the approach I've taken up there is wrong? All my research so far showed that this seems to be the most common method to check it out. But due to your confirmation I do atleast know that my calculation is wrong and I can be sure that my trial and error is not for nothing. :'D P.S: Thanks for the hint with the square root, I didn't think about it properly. $\endgroup$
    – Steven
    Oct 26 '20 at 8:53
  • $\begingroup$ Well, I don't know what do you mean by hand, however, the last 3 lines you need with $a$,$b$, and $p$. For the, you need a big number library where SageMath is helpful. $\endgroup$
    – kelalaka
    Oct 26 '20 at 8:56
  • $\begingroup$ I've simplified the code. now, it just calculates the arithmetic, $\endgroup$
    – kelalaka
    Oct 26 '20 at 9:02
  • $\begingroup$ Thank you, it became way more clear now! :) I still missunderstand something. Why do you calculate modulo the field? I've tested the online IDE aswell and tried if px^3+a256*px+b256 equals to py^2 but it doesn't, so I think my whole understanding is wrong... I'm really sorry for being so slow, but even with researching a lot I don't seem to understand it and that's really frustrating. $\endgroup$
    – Steven
    Oct 26 '20 at 9:15
  • 1
    $\begingroup$ Alright, thank you very much for your time and help. Things became much clearer! :) $\endgroup$
    – Steven
    Oct 26 '20 at 9:50

Your Answer

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

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