Verifying multiplicative inverse on a prime field in NIST's ECDSA_Prime.pdf

Question

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 K and 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 K and 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:

44876559229634927483363577082941808653359045812660811236387870057706848524951

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 Kinv?

Answer 1

You are using the wrong value as the modulus; you ought to be using the value $r$ (which is also listed in the document).

$p$ is the characteristic of the field that the elliptic curve you're using is defined on. In this case, we're not interested in that; instead what we're interested in is the order of the curve, that is, that value $r$ such that $rP = 0$ for all points $P$ on the curve (note: strictly speaking, we're interested in the order of the generator point, however in this case, that's the same). That value $r$ is as listed.

$K$ and $K_{inv}$ are not inverses modulo $p$; instead, $K \times K_{inv} = 1 \ (\bmod \ r)$