3
$\begingroup$

I'm a complete newbie to ECC.. but I was trying to get my feet wet with (what I thought would be) a TRIVIAL/EXTREMELY SIMPLE example of ECDSA signing and verification (that I could check by hand).

I'd appreciate any advice as to what I'm missing.. or have done wrong.

And if this is NOT an appropriate venue for this kind of question, I appologize, and would welcome any advice as to what group/forum would be a better choice.

E := y^2 = x^3 + 2 x + 2 mod 17

(this elliptic curve has 18 points, and any of the points on the curve can be the generator (G).. so I chose G = (5,1))

I chose an "ephemeral" key

k = 3

then

k G
= 3 (5,1)
= (10,6)

I chose

dA = 5

then

QA = dA G
= 5 (5,1)
= (9,16)

so A's private/public keys are

dA (= 5) and QA (= (9,16))

And finally, I chose an value for "e" (the hash of the message) of 8.

e = 8

SIGNING:

R = (rX,rY) = k G
= (10,6)

(r =) rx = 10

s = (e + dA r) k^-1 mon n
= (8 + 5 10) 3^15 mod 17
= (8 + 5 10) 6 mod 17
= 8

so the "signature" (for any message that hashes to e = 8) is

(r,s) = (10,8)

VERIFICATION:

w = s^-1 mod n
= 8^15 mod 17
= 15

u1 = e w mod n
= 8 15 mod 17
= 1

u2 = r w mod n
= 10 15 mod 17
= 14

P = (pX,pY) = u1 G + u2 QA
= 1 (5,1) + 14 (9,16)
= (5,1) + (16,4)
= (9,1)

And pX (9) SHOULD be equal to r (10).. but, clearly, it's NOT.

What am I missing or doing wrong?

$\endgroup$

closed as off-topic by e-sushi Jan 6 '18 at 4:51

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ The modular inverse in the signature process is modulo the order of the group, not of the base field. By the way, the order of your group is 19, not 18 as you have stated. $\endgroup$ – fkraiem Dec 6 '16 at 16:00
  • $\begingroup$ Bingo! Thanks 1e6. And maybe my wording is not technically correct (which is to say it's wrong).. but when I said that there are 18 points.. I meant there are 18 points ON THE CURVE.. which, when you throw in the point at infinity, makes 19. $\endgroup$ – Tom Dec 6 '16 at 18:36
  • 1
    $\begingroup$ The point at infinity is a point. Really. $\endgroup$ – fkraiem Dec 6 '16 at 19:15