I am trying to learn about the Elliptic Curve Digital Signature Algorithm (ECDSA) by verifying the results in some example calculations. I found a PDF of example ECDSA calculations from NIST here: http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ECDSA_Prime.pdf
In the section "Example of ECDSA with P-256", NIST gives two large hex numbers
Kinv, which I presume are multiplicative inverses of eachother in the prime field of the P-256 curve. I tried to verify that
K * Kinv is equal to 1 (in modulo arithmetic) but I was unable to; I got a really large number instead of 1.
Could someone check my relatively simple work and tell me what I am doing wrong? Or could someone verify it in their own way and tell me how they verified it?
Here is the excerpt from ECDSA_Prime.pdf I am looking at:
============================================================== Signature Generation msg is "Example of ECDSA with P-256" Hash length = 256 ... K is 7A1A7E52 797FC8CA AA435D2A 4DACE391 58504BF2 04FBE19F 14DBB427 FAEE50AE ... Kinv is 62159E5B A9E712FB 098CCE8F E20F1BED 8346554E 98EF3C7C 1FC3332B A67D87EF
I found the prime value $p$ that defines the field for curve P-256 in NISTReCur.pdf. I multiplied
Kinv together in Ruby, taking advantage of that language's automatic handling of very large integers. Here is my Ruby code:
# From http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf # in the section entitled "P-256" nist_p = 11579208921035624876269744694940757353008614_3415290314195533631308867097853951 # From http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/ECDSA_Prime.pdf # in the section entitled "Example of ECDSA with P-256" nist_k = 0x7A1A7E52_797FC8CA_AA435D2A_4DACE391_58504BF2_04FBE19F_14DBB427_FAEE50AE nist_kinv = 0x62159E5B_A9E712FB_098CCE8F_E20F1BED_8346554E_98EF3C7C_1FC3332B_A67D87EF puts (nist_k * nist_kinv) % nist_p # expect to get 1, but did not
Note that the underscores are just spacers between the digits to make these long numbers more readable; they can be removed without affecting the program.
This code outputs the following number, even though I would expect it to output 1:
I tried reversing the order of bytes in the NIST hex numbers and I also tried reversing the order of the 32-bit chunks, but neither yielded the correct result.
What am I doing wrong here? Am I using the wrong value of $p$ for the P-256 curve? Is my understanding of
Kinv incorrect? Did NIST miscalculate