Annexe A. Exemples

A.1. Exemple détaillé

Nous détaillons ici les valeurs intermédiaires obtenues lors de la génération de k sur un exemple de message et de clé. Nous utilisons une courbe binaire car cette courbe spécifique est standard et a une longueur d'ordre de groupe (qlen) qui n'est pas un multiple de 8; cela illustre les détails fins de la façon dont les conversions sont effectuées entre les entiers et les séquences de bits.

A.1.1. Paire de clés

Nous considérons ECDSA sur la courbe K-163 décrite dans [FIPS-186-4] (également connue sous le nom "ansix9t163k1" dans [X9.62]). La courbe est définie sur un corps GF(2^163): les éléments de corps sont encodés en chaînes de 163 bits. L'ordre du point de base conventionnel est la valeur première:

q = 0x4000000000000000000020108A2E0CC0D99F8A5EF

qui a une longueur qlen = 163 bits.

Notre clé privée est:

x = 0x09A4D6792295A7F730FC3F2B49CBC0F62E862272F

La clé publique correspondante est le point de courbe U = xG. Ce point a deux coordonnées, qui sont des éléments du corps GF(2^163). Ces éléments peuvent être convertis en entiers en utilisant la procédure décrite dans la section A.5.6 de [X9.62], produisant les deux coordonnées de point public:

Ux = 0x79AEE090DB05EC252D5CB4452F356BE198A4FF96F

Uy = 0x782E29634DDC9A31EF40386E896BAA18B53AFA5A3

A.1.2. Génération de k

Dans cet exemple, nous utilisons la fonction de hachage SHA-256 [FIPS-180-4]. Le message d'entrée est l'encodage UTF-8 de la chaîne "sample" (6 octets, c'est-à-dire 48 bits).

Le message d'entrée haché h1 = SHA-256(m) est:

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; chaque valeur d'octet est listée en notation hexadécimale).

Nous convertissons la clé privée x en une séquence d'octets en utilisant la transformation int2octets:

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

Note: Bien que la valeur spécifique de x tiendrait numériquement dans 160 bits, c'est-à-dire 20 octets, nous encodons toujours x en 21 octets, car la longueur d'encodage est déterminée par la longueur de q, qui est de 163 bits.

Nous tronquons et/ou étendons également le message haché en utilisant bits2octets:

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

Les étapes b à g (voir la section 3.2) calculent ensuite les valeurs pour les variables K et V. Ces variables sont des séquences de 256 bits (la longueur de sortie de la fonction de hachage, arrondie au multiple suivant de 8). Nous reproduisons ici les valeurs successives:

V après l'étape 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 après l'étape 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 après l'étape 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 après l'étape 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 après l'étape 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 après l'étape 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

Dans l'étape h, nous effectuons la boucle finale. Puisque nous utilisons HMAC avec SHA-256, qui produit 256 bits de sortie, et nous n'avons besoin que de 163 bits pour T, une seule invocation HMAC produit le T suivant:

T (première tentative):

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

qui, lorsqu'il est converti en un entier avec bits2int, donne un premier candidat pour k:

k1 = 0x4982D236F3FFC758838CA6F5E9FEA455106AF3B2B

Puisque cette valeur est supérieure à q-1, nous devons boucler. Cela implique d'abord de calculer de nouvelles valeurs pour K et V:

nouveau 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

nouveau 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

puis un nouveau T:

T (deuxième tentative):

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

et un nouveau candidat pour k:

k2 = 0x63863C30451DADF4944DF4877B740D4F160A8B6AB

Puisque k2 est également supérieur à q-1, nous bouclons à nouveau:

nouveau 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

nouveau 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 (troisième tentative):

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

et nous obtenons finalement une valeur acceptable pour k:

k = 0x23AF4074C90A02B3FE61D286D5C87F425E6BDD81B

A.1.3. Signature

Avec notre clé privée et la valeur de k que nous venons de générer, nous pouvons maintenant calculer la signature en utilisant les mécanismes ECDSA standard. D'abord, le point kG est calculé, et la coordonnée X de ce point est convertie en un entier puis réduite modulo q, produisant la première moitié de signature:

r = 0x113A63990598A3828C407C0F4D2438D990DF99A7F

que nous utilisons, avec x (la clé privée), k (que nous avons calculé ci-dessus), et h = bits2int(h1), pour calculer la seconde moitié de signature:

s = 0x1313A2E03F5412DDB296A22E2C455335545672D9F

Une signature ECDSA est une paire d'entiers. Dans de nombreux protocoles qui nécessitent qu'une signature soit une séquence de bits (ou d'octets), il est d'usage d'encoder la signature comme une SEQUENCE ASN.1 de deux valeurs INTEGER, avec les règles DER. Cela résulte en la signature de 48 octets suivante:

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.2. Vecteurs de test

Dans les sections suivantes, nous donnons des vecteurs de test pour diverses tailles de clé et fonctions de hachage, à la fois pour DSA et ECDSA.

Tous les nombres sont donnés en notation hexadécimale. Chaque signature consiste en deux entiers, nommés r et s; de nombreuses implémentations encoderont ces entiers en une seule structure ASN.1 ou avec une autre convention d'encodage, ce qui est en dehors du cadre de ce document. Nous montrons également la valeur k utilisée en interne.

Pour chaque clé, nous listons dix signatures, correspondant à deux messages d'entrée distincts, et cinq des fonctions SHA [FIPS-180-4]: SHA-1, SHA-224, SHA-256, SHA-384 et SHA-512. Les deux messages d'entrée sont l'encodage UTF-8 des chaînes "sample" et "test" (sans les guillemets), de longueur 48 et 32 bits, respectivement.

Les exemples ECDSA utilisent les courbes standard décrites dans [FIPS-186-4].

A.3. Code exemple

Des exemples de code implémentant cette spécification sont disponibles sur le site Web de l'auteur.