2. Notations DSA et ECDSA

2. Notations DSA et ECDSA

Dans cette section, nous décrivons succinctement DSA et ECDSA et définissons nos notations. Les spécifications complètes pour DSA et ECDSA peuvent être trouvées dans [FIPS-186-4] et [X9.62], respectivement.

2.1. Paramètres de clé

DSA et ECDSA fonctionnent sur un grand groupe de taille première, dans lequel l'opération de groupe est facile à calculer, mais le logarithme discret est computationnellement infaisable avec la technologie existante et prévisible. La définition du groupe est appelée les "paramètres de clé". Les paramètres de clé peuvent être partagés entre différentes paires de clés sans effet néfaste sur la sécurité; c'est le cas habituel avec ECDSA en particulier.

DSA utilise les paramètres de clé suivants:

p : un grand nombre premier (au moins 1024 bits)

q : un nombre premier suffisamment grand (au moins 160 bits) qui est également un diviseur de p-1

g : un générateur pour le sous-groupe multiplicatif d'ordre q des entiers modulo p

Le groupe sur lequel DSA sera calculé se compose des valeurs 'g^j mod p', où '^' désigne l'exponentiation et j varie de 0 à q-1 (inclus). La taille du groupe est q.

ECDSA utilise les paramètres de clé suivants:

E : une courbe elliptique, définie sur un corps fini donné

q : un nombre premier suffisamment grand (au moins 160 bits) qui est un diviseur de l'ordre de la courbe

G : un point de E, d'ordre q

Le groupe sur lequel ECDSA sera calculé se compose des points de courbe jG (multiplication du point G par l'entier j) où j varie de 0 à q-1. G est tel que qG = 0 (le "point à l'infini" sur la courbe E). La taille du groupe est q. Notez que ces notations diffèrent légèrement de celles décrites dans [X9.62]; nous les utilisons afin de correspondre à celles utilisées pour DSA.

2.2. Paires de clés

Une clé privée DSA ou ECDSA est un entier x pris modulo q. Les normes pertinentes prescrivent que x ne doit pas être 0; par conséquent, x est un entier dans la plage [1, q-1].

Une clé publique DSA ou ECDSA est calculée à partir de la clé privée x et des paramètres de clé:

• Pour DSA, la clé publique est l'entier: y = g^x mod p

• Pour ECDSA, la clé publique est le point de courbe: U = xG

2.3. Conversions d'entiers

Soit qlen la longueur binaire de q. qlen est le plus petit entier tel que q est inférieur à 2^qlen. C'est la taille de la représentation binaire de q sans bit de signe (notez que q, étant un grand nombre premier, est impair, évitant ainsi toute ambiguïté sur la longueur de tout entier égal à une puissance de 2). Nous définissons cinq fonctions de conversion, qui fonctionnent sur des chaînes de bits, d'octets et des entiers modulo q. qlen est le paramètre principal pour ces conversions.

Dans les sous-sections suivantes, nous utilisons deux autres longueurs, appelées blen et rlen. rlen est égal à qlen, arrondi au multiple suivant de 8 (si qlen est déjà un multiple de 8, alors rlen est égal à qlen; sinon, rlen est légèrement plus grand, jusqu'à qlen+7). Notez que rlen n'est pas lié à la valeur r, la première moitié d'une signature générée. blen est la longueur (en bits) d'une séquence d'entrée de bits et peut varier entre les appels. blen peut être inférieur, égal ou supérieur à qlen.

2.3.1. Bits et octets

Formellement, toutes les opérations sont définies sur des séquences de bits. Une séquence est ordonnée; le premier bit est dit le plus à gauche, tandis que le dernier bit est le plus à droite.

Sur la plupart des systèmes logiciels, les bits sont regroupés en octets (séquences de huit bits). Les données binaires, par exemple la sortie d'une fonction de hachage, sont disponibles sous forme de séquence d'octets. Lorsque cela est applicable, nous considérons que les bits dans un octet sont ordonnés du plus significatif au moins significatif: le premier bit (le plus à gauche) dans un octet a une valeur numérique de 128, tandis que le dernier (le plus à droite) a une valeur numérique de 1.

2.3.2. Chaîne de bits vers entier

La transformation bits2int prend en entrée une séquence de blen bits et produit un entier non négatif qui est inférieur à 2^qlen. Elle consiste en les étapes suivantes:

1. La séquence est d'abord tronquée ou étendue à la longueur qlen:

   • si qlen < blen, alors les qlen bits les plus à gauche sont conservés, et les bits suivants sont écartés;

   • sinon, qlen-blen bits (de valeur zéro) sont ajoutés à gauche de la séquence (c'est-à-dire avant les bits d'entrée dans l'ordre de séquence).

2. La séquence résultante est ensuite convertie en une valeur entière en utilisant la convention big-endian: si les bits d'entrée sont appelés b_0 (le plus à gauche) à b_(qlen-1) (le plus à droite), alors la valeur résultante est:

   b_02^(qlen-1) + b_12^(qlen-2) + ... + b_(qlen-1)*2^0

La transformation bits2int peut également être décrite de la manière suivante: la séquence de bits d'entrée (de longueur blen) est transformée en un entier en utilisant la convention big-endian. Ensuite, si blen est supérieur à qlen, l'entier résultant est divisé par deux à la puissance blen-qlen (division euclidienne: le reste est écarté); dans de nombreuses implémentations logicielles d'arithmétique sur de grands entiers, cette division équivaut à un "décalage à droite" de blen-qlen bits.

2.3.3. Entier vers chaîne d'octets

Une valeur entière x inférieure à q (et, en particulier, une valeur qui a été prise modulo q) peut être convertie en une séquence de rlen bits, où rlen = 8*ceil(qlen/8). C'est la séquence de bits obtenue par encodage big-endian. En d'autres termes, les bits de séquence x_i (pour i allant de 0 à rlen-1) sont tels que:

x = x_02^(rlen-1) + x_12^(rlen-2) + ... + x_(rlen-1)

Nous appelons cette transformation int2octets. Puisque rlen est un multiple de 8 (le plus petit multiple de 8 qui n'est pas inférieur à qlen), alors la séquence de bits résultante est également une séquence d'octets, d'où le nom.

2.3.4. Chaîne de bits vers chaîne d'octets

La transformation bits2octets prend en entrée une séquence de blen bits et produit une séquence de rlen bits. Elle consiste en les étapes suivantes:

1. La séquence d'entrée b est convertie en une valeur entière z1 par la transformation bits2int:

   z1 = bits2int(b)

2. z1 est réduit modulo q, donnant z2 (un entier entre 0 et q-1, inclus):

   z2 = z1 mod q

   Notez que puisque z1 est inférieur à 2^qlen, cette réduction modulaire peut être implémentée avec une simple soustraction conditionnelle: z2 = z1-q si cette valeur est non négative; sinon, z2 = z1.

3. z2 est transformé en une séquence d'octets (une séquence de rlen bits) en appliquant int2octets.

2.3.5. Utilisation

Il convient de noter que int2octets n'est pas l'inverse de bits2int, même pour les séquences d'entrée de longueur qlen: int2octets ajoutera quelques bits à gauche, tandis que bits2int écartera quelques bits à droite. int2octets est l'inverse de bits2int uniquement lorsque qlen est un multiple de 8 et que les séquences de bits ont déjà la longueur qlen.

bits2int est utilisé pendant la génération et la vérification de signature dans DSA et ECDSA standard pour transformer une valeur de hachage (calculée sur le message d'entrée) en un entier modulo q. C'est-à-dire que l'entier obtenu par bits2int est ensuite réduit modulo q; puisque cet entier est inférieur à 2^qlen, cette réduction peut être effectuée avec au plus une soustraction.

int2octets est défini sous le nom "Integer-to-OctetString" dans la section 2.3.7 de SEC 1 [SEC1]. Il est utilisé dans la spécification de l'encodage d'une clé privée ECDSA (x) dans une structure basée sur ASN.1.

bits2octets n'est pas utilisé dans DSA ou ECDSA standard. Nous l'utiliserons dans la spécification de (EC)DSA déterministe.

2.4. Génération de signature

La génération de signature utilise une fonction de hachage cryptographique H et un message d'entrée m. Le message est d'abord traité par H, produisant la valeur H(m), qui est une séquence de bits de longueur hlen. Normalement, H est choisi de sorte que sa longueur de sortie hlen soit à peu près égale à qlen, puisque la sécurité globale du schéma de signature dépendra du plus petit de hlen et qlen; cependant, les normes pertinentes prennent en charge toutes les combinaisons de hlen et qlen.

Les étapes suivantes sont ensuite appliquées:

1. H(m) est transformé en un entier modulo q en utilisant la transformation bits2int et une réduction modulaire supplémentaire:

   h = bits2int(H(m)) mod q

   Comme cela a été noté dans la description de bits2octets, la réduction modulaire supplémentaire n'est pas plus qu'une soustraction conditionnelle.

2. Une valeur aléatoire modulo q, appelée k, est générée. Cette valeur ne doit pas être 0; par conséquent, elle se situe dans la plage [1, q-1]. La plus grande partie du reste de ce document tournera autour du processus utilisé pour générer k. Dans DSA ou ECDSA ordinaire, k DEVRAIT être sélectionné par une sélection aléatoire qui choisit une valeur parmi les q-1 valeurs possibles avec une probabilité uniforme.

3. Une valeur r (modulo q) est calculée à partir de k et des paramètres de clé:

   • Pour DSA:

     r = g^k mod p mod q

     (L'exponentiation est effectuée modulo p, produisant un nombre entre 0 et p-1, qui est ensuite réduit davantage modulo q.)

   • Pour ECDSA: le point kG est calculé; sa coordonnée X (un membre du corps sur lequel E est défini) est convertie en un entier, qui est réduit modulo q, donnant r.

   Si r s'avère être zéro, un nouveau k DEVRAIT être sélectionné et r calculé à nouveau (c'est une occurrence extrêmement improbable).

4. La valeur s (modulo q) est calculée:

   s = (h+x*r)/k mod q

   La paire (r, s) est la signature. La façon dont une signature doit être encodée n'est pas couverte par les normes DSA et ECDSA elles-mêmes; une façon courante est d'utiliser une structure ASN.1 encodée en DER (une SEQUENCE de deux INTEGER, pour r et s, dans cet ordre).