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

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?

-

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)$
Ah, you are right. I forgot that k is not really a member of the field, it is just a number that represents a point $p*G$ on the curve. My calculations work if I use $r$ instead of $p$. Thanks! –  David Grayson Mar 15 '14 at 22:49