3. EdDSA Algorithm

EdDSA est un système de signature numérique avec 11 paramètres.

Le système de signature numérique EdDSA générique avec ses 11 paramètres d'entrée n'est pas destiné à être implémenté directement. Le choix des paramètres est critique pour une opération sécurisée et efficace. Au lieu de cela, vous implémenteriez un choix de paramètres particulier pour EdDSA (tel qu'Ed25519 ou Ed448), parfois légèrement généralisé pour obtenir une réutilisation du code couvrant Ed25519 et Ed448.

Par conséquent, une explication précise de l'EdDSA générique n'est donc pas particulièrement utile pour les implémenteurs. Pour le contexte et l'exhaustivité, une description succincte de l'algorithme EdDSA générique est donnée ici.

La définition de certains paramètres, tels que n et c, peut aider à expliquer certaines étapes de l'algorithme qui ne sont pas intuitives.

Cette description suit de près [EDDSA2].

EdDSA a 11 paramètres:

Une puissance première impaire p. EdDSA utilise une courbe elliptique sur le corps fini GF(p).
Un entier b avec 2^(b-1) > p. Les clés publiques EdDSA ont exactement b bits, et les signatures EdDSA ont exactement 2*b bits. Il est recommandé que b soit un multiple de 8, de sorte que les longueurs de clé publique et de signature soient un nombre entier d'octets.
Un encodage de (b-1) bits des éléments du corps fini GF(p).
Une fonction de hachage cryptographique H produisant une sortie de 2*b bits. Les fonctions de hachage conservatrices (c'est-à-dire les fonctions de hachage où il est infaisable de créer des collisions) sont recommandées et n'ont pas beaucoup d'impact sur le coût total d'EdDSA.
Un entier c qui est 2 ou 3. Les scalaires secrets EdDSA sont des multiples de 2^c. L'entier c est le logarithme en base 2 du soi-disant cofacteur.
Un entier n avec c <= n < b. Les scalaires secrets EdDSA ont exactement n + 1 bits, avec le bit supérieur (la position 2^n) toujours défini et les c bits inférieurs toujours effacés.
Un élément non carré d de GF(p). La recommandation habituelle est de le prendre comme la valeur la plus proche de zéro qui donne une courbe acceptable.
Un élément carré non nul a de GF(p). La recommandation habituelle pour les meilleures performances est a = -1 si p mod 4 = 1, et a = 1 si p mod 4 = 3.
Un élément B != (0,1) de l'ensemble E = { (x,y) est un membre de GF(p) x GF(p) tel que a * x^2 + y^2 = 1 + d * x^2 * y^2 }.
Un nombre premier impair L tel que [L]B = 0 et 2^c * L = #E. Le nombre #E (le nombre de points sur la courbe) fait partie des données standard fournies pour une courbe elliptique E, ou il peut être calculé comme cofacteur * ordre.
Une fonction "prehash" PH. PureEdDSA signifie EdDSA où PH est la fonction identité, c'est-à-dire PH(M) = M. HashEdDSA signifie EdDSA où PH génère une sortie courte, quelle que soit la longueur du message; par exemple, PH(M) = SHA-512(M).

Les points sur la courbe forment un groupe sous addition, (x3, y3) = (x1, y1) + (x2, y2), avec les formules

         x1 * y2 + x2 * y1                y1 * y2 - a * x1 * x2
x3 = --------------------------,   y3 = ---------------------------
     1 + d * x1 * x2 * y1 * y2          1 - d * x1 * x2 * y1 * y2

L'élément neutre du groupe est (0,1).

Contrairement à de nombreuses autres courbes utilisées pour les applications cryptographiques, ces formules sont "complètes"; elles sont valides pour tous les points de la courbe, sans exception. En particulier, les dénominateurs sont non nuls pour tous les points d'entrée.

Il existe des formules plus efficaces, qui sont toujours complètes, qui utilisent des coordonnées homogènes pour éviter les inversions modulo p coûteuses. Voir [Faster-ECC] et [Edwards-revisited].

3. EdDSA Algorithm​

3. EdDSA Algorithm