A.1. Detailed Example

We detail here the intermediate values obtained during the generation of k on an example message and key. We use a binary curve because that specific curve is standard and has a group order length (qlen) that is not a multiple of 8; this illustrates the fine details of how conversions are performed between integers and bit sequences.

A.1.1. Key Pair

We consider ECDSA on the curve K-163 described in [FIPS-186-4] (also known as "ansix9t163k1" in [X9.62]). The curve is defined over a field GF(2^163): field elements are encoded into 163-bit strings. The order of the conventional base point is the prime value:

q = 0x4000000000000000000020108A2E0CC0D99F8A5EF

which has length qlen = 163 bits.

Our private key is:

x = 0x09A4D6792295A7F730FC3F2B49CBC0F62E862272F

The corresponding public key is the curve point U = xG. This point has two coordinates, which are elements of the field GF(2^163). These elements can be converted to integers using the procedure described in Section A.5.6 of [X9.62], yielding the two public point coordinates:

Ux = 0x79AEE090DB05EC252D5CB4452F356BE198A4FF96F
Uy = 0x782E29634DDC9A31EF40386E896BAA18B53AFA5A3

A.1.2. Generation of k

In this example, we use the hash function SHA-256 [FIPS-180-4]. The input message is the UTF-8 encoding of the string "sample" (6 octets, i.e., 48 bits).

The hashed input message h1 = SHA-256(m) is:

h1
   AF 2B DB E1 AA 9B 6E C1 E2 AD E1 D6 94 F4 1F C7
   1A 83 1D 02 68 E9 89 15 62 11 3D 8A 62 AD D1 BF

(32 octets; each octet value is listed in hexadecimal notation).

We convert the private key x to a sequence of octets using the int2octets transform:

int2octets(x)
   00 9A 4D 67 92 29 5A 7F 73 0F C3 F2 B4 9C BC 0F
   62 E8 62 27 2F

Note: Although the specific value of x would numerically fit in 160 bits, i.e., 20 octets, we still encode x into 21 octets, because the encoding length is driven by the length of q, which is 163 bits.

We also truncate and/or expand the hashed message using bits2octets:

bits2octets(h1)
   01 79 5E DF 0D 54 DB 76 0F 15 6D 0D AC 04 C0 32
   2B 3A 20 42 24

The steps b to g (see Section 3.2) then compute the values for the K and V variables. These variables are sequences of 256 bits (the hash function output length, rounded up to a multiple of 8). We reproduce here the successive values:

V after step b:
   01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
   01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
K after step c:
   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
   00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
K after step d:
   09 99 9A 9B FE F9 72 D3 34 69 11 88 3F AD 79 51
   D2 3F 2C 8B 47 F4 20 22 2D 11 71 EE EE AC 5A B8
V after step e:
   D5 F4 03 0F 75 5E E8 6A A1 0B BA 8C 09 DF 11 4F
   F6 B6 11 1C 23 85 00 D1 3C 73 43 A8 C0 1B EC F7
K after step f:
   0C F2 FE 96 D5 61 9C 9E F5 3C B7 41 7D 49 D3 7E
   A6 8A 4F FE D0 D7 E6 23 E3 86 89 28 99 11 BD 57
V after step g:
   78 34 57 C1 CF 31 48 A8 F2 A9 AE 73 ED 47 2F A9
   8E D9 CD 92 5D 8E 96 4C E0 76 4D EF 3F 84 2B 9A

In step h, we perform the final loop. Since we use HMAC with SHA-256, which produces 256 bits worth of output, and we need only 163 bits for T, a single HMAC invocation yields the following T:

T (first try)
   93 05 A4 6D E7 FF 8E B1 07 19 4D EB D3 FD 48 AA
   20 D5 E7 65 6C BE 0E A6 9D 2A 8D 4E 7C 67 31 4A

which, when converted to an integer with bits2int, yields a first candidate for k:

k1 = 0x4982D236F3FFC758838CA6F5E9FEA455106AF3B2B

Since that value is greater than q-1, we have to loop. This first entails computing new values for K and V:

new K
   75 CB 5C 05 B2 A7 8C 3D 81 DF 12 D7 4D 7B E0 A0
   E9 4A B1 98 15 78 1D 4D 8E 29 02 A7 9D 0A 66 99
new V
   DC B9 CA 12 61 07 A9 C2 7C E7 7B A5 8E A8 71 C8
   C9 12 D8 35 EA DD C3 05 F2 44 5D 88 F6 6C 4C 43

then a new T:

T (second try)
   C7 0C 78 60 8A 3B 5B E9 28 9B E9 0E F6 E8 1A 9E
   2C 15 16 D5 75 1D 2F 75 F5 00 33 E4 5F 73 BD EB

and a new candidate for k:

k2 = 0x63863C30451DADF4944DF4877B740D4F160A8B6AB

Since k2 is also greater than q-1, we loop again:

new K (2)
   0A 5A 64 B9 9C 05 95 20 10 36 86 CB 6F 36 BC FC
   A7 88 EB 3B CF 69 BA 66 A5 BB 08 0B 05 93 BA 53
new V (2)
   0B 3B 19 68 11 B1 9F 6C 6F 72 9C 43 F3 5B CF 0D
   FD 72 5F 17 CA 34 30 E8 72 14 53 E5 55 50 A1 8F
T (third try)
   47 5E 80 E9 92 14 05 67 FC C3 A5 0D AB 90 FE 84
   BC D7 BB 03 63 8E 9C 46 56 A0 6F 37 F6 50 8A 7C

and we finally get an acceptable value for k:

k = 0x23AF4074C90A02B3FE61D286D5C87F425E6BDD81B

A.1.3. Signature

With our private key and the value of k that we just generated, we can now compute the signature using the standard ECDSA mechanisms. First, the point kG is computed, and the X coordinate of that point is converted to an integer and then reduced modulo q, yielding the first signature half:

r = 0x113A63990598A3828C407C0F4D2438D990DF99A7F

which we use, together with x (the private key), k (which we computed above), and h = bits2int(h1), to compute the second signature half:

s = 0x1313A2E03F5412DDB296A22E2C455335545672D9F

An ECDSA signature is a pair of integers. In many protocols that require a signature to be a sequence of bits (or octets), it is customary to encode the signature as an ASN.1 SEQUENCE of two INTEGER values, with DER rules. This results in the following 48-octet signature:

30 2E 02 15 01 13 A6 39 90 59 8A 38 28 C4 07 C0
F4 D2 43 8D 99 0D F9 9A 7F 02 15 01 31 3A 2E 03
F5 41 2D DB 29 6A 22 E2 C4 55 33 55 45 67 2D 9F

A.1.1. Key Pair​

A.1.2. Generation of k​

A.1.3. Signature​

A.1.1. Key Pair

A.1.2. Generation of k

A.1.3. Signature