Algorithme de signature numérique

L' algorithme de signature numérique ( DSA ) est un système de cryptographie à clé publique et une norme fédérale de traitement de l'information pour les signatures numériques , basé sur le concept mathématique d' exponentiation modulaire et le problème du logarithme discret . Dans un système de signature numérique, une paire de clés est utilisée : une clé privée et une clé publique. Dans ce système, une entité signataire ayant déclaré sa clé publique peut générer une signature à l'aide de sa clé privée, et un vérificateur peut authentifier la source s'il vérifie correctement la signature à l'aide de la clé publique déclarée. Le DSA est une variante des schémas de signature de Schnorr et d'ElGamal .

L' Institut national des normes et de la technologie (NIST) a proposé l'utilisation de DSA dans sa norme de signature numérique (DSS) en 1991 et l'a adoptée sous la référence FIPS 186 en 1994. Cinq révisions de la spécification initiale ont été publiées. La plus récente est la FIPS 186-5, datant de février 2023. DSA est brevetée, mais le NIST a mis ce brevet à disposition gratuitement dans le monde entier. La spécification FIPS 186-5 indique que DSA ne sera plus approuvée pour la génération de signatures numériques, mais pourra être utilisée pour vérifier les signatures générées avant la date d'entrée en vigueur de cette norme.

Aperçu

L'algorithme DSA fonctionne dans le cadre des systèmes de cryptographie à clé publique et repose sur les propriétés algébriques de l'exponentiation modulaire , ainsi que sur le problème du logarithme discret , considéré comme difficile à résoudre en pratique. L'algorithme utilise une paire de clés composée d'une clé publique et d'une clé privée. La clé privée sert à générer une signature numérique pour un message, et cette signature peut être vérifiée à l'aide de la clé publique correspondante du signataire. La signature numérique garantit l'authentification du message (le destinataire peut vérifier son origine), son intégrité (le destinataire peut vérifier que le message n'a pas été modifié depuis sa signature) et sa non-répudiation (l'expéditeur ne peut pas nier avoir signé le message).

Histoire

En 1982, le gouvernement américain a lancé un appel d'offres pour une norme de signature à clé publique. En août 1991, le National Institute of Standards and Technology (NIST) a proposé DSA pour sa norme de signature numérique (DSS). Cette proposition a initialement suscité de vives critiques, notamment de la part des éditeurs de logiciels qui avaient déjà investi dans le développement de logiciels de signature numérique basés sur le système de chiffrement RSA . Néanmoins, le NIST a adopté DSA comme norme fédérale (FIPS 186) en 1994. Cinq révisions de la spécification initiale ont été publiées : FIPS 186-1 en 1998, FIPS 186-2 en 2000, FIPS 186-3 en 2009, FIPS 186-4 en 2013, et FIPS 186-5 en 2023. La norme FIPS 186-5 interdit la signature avec DSA, tout en autorisant la vérification des signatures générées avant la date de mise en œuvre de la norme en tant que document. Elle doit être remplacée par des schémas de signature plus récents tels que EdDSA .

La technologie DSA est couverte par le brevet américain n° 5 231 668 , déposé le 26 juillet 1991 et désormais expiré, attribué à David W. Kravitz , ancien employé de la NSA . Ce brevet a été accordé aux « États-Unis d’Amérique, représentés par le secrétaire au Commerce , à Washington, D.C. », et le NIST l’a mis à disposition gratuitement dans le monde entier . Claus P. Schnorr affirme que son brevet américain n° 4 995 082 (également expiré) couvrait la technologie DSA ; cette affirmation est contestée

En 1993, Dave Banisar a réussi à obtenir la confirmation, via une demande FOIA , que l'algorithme DSA n'a pas été conçu par le NIST, mais par la NSA .

OpenSSH a annoncé que DSA serait supprimé en 2025. La prise en charge a été entièrement abandonnée dans la version 10.0.

Opération

L'algorithme DSA comprend quatre opérations : la génération de clés (qui crée la paire de clés), la distribution des clés, la signature et la vérification de la signature.

1. Génération de clés

La génération de clés comporte deux phases. La première phase consiste à choisir les paramètres de l'algorithme , qui peuvent être partagés entre différents utilisateurs du système, tandis que la seconde phase calcule une paire de clés unique pour chaque utilisateur.

Génération de paramètres

Choisissez une fonction de hachage cryptographique approuvée dont la longueur de sortie est de bits. Dans la version originale du DSS, il s'agissait toujours de SHA-1 , mais les fonctions de hachage SHA-2, plus robustes , sont approuvées pour une utilisation dans la version actuelle du DSS. Si la longueur de sortie est supérieure à la longueur du module , seuls les bits les plus à gauche du résultat du hachage sont utilisés. ${\displaystyle H <semantics><mrow><mstyle><mi>H</mi></mstyle></mrow><annotation>{\displaystyle H}</annotation></semantics></math><img src=$ ${\displaystyle |H| <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><mi>H</mi><mrow><mo>|</mo></mrow></mstyle></mrow><annotation>{\displaystyle |H|}</annotation></semantics></math><img src=$ ${\displaystyle H <semantics><mrow><mstyle><mi>H</mi></mstyle></mrow><annotation>{\displaystyle H}</annotation></semantics></math><img src=$ ${\displaystyle |H| <semantics><mrow><mstyle><mrow><mo>|</mo></mrow><mi>H</mi><mrow><mo>|</mo></mrow></mstyle></mrow><annotation>{\displaystyle |H|}</annotation></semantics></math><img src=$ ${\displaystyle N <semantics><mrow><mstyle><mi>N</mi></mstyle></mrow><annotation>{\displaystyle N}</annotation></semantics></math><img src=$ ${\displaystyle N <semantics><mrow><mstyle><mi>N</mi></mstyle></mrow><annotation>{\displaystyle N}</annotation></semantics></math><img src=$
Choisissez une longueur de clé . La norme DSS originale imposait une longueur multiple de 64, comprise entre 512 et 1024 inclus. La norme NIST 800-57 recommande des longueurs de 2048 (ou 3072) pour les clés dont la durée de vie de sécurité s'étend au-delà de 2010 (ou 2030). ${\displaystyle L <semantics><mrow><mstyle><mi>L</mi></mstyle></mrow><annotation>{\displaystyle L}</annotation></semantics></math><img src=$ ${\displaystyle L <semantics><mrow><mstyle><mi>L</mi></mstyle></mrow><annotation>{\displaystyle L}</annotation></semantics></math><img src=$
Choisissez la longueur du module telle que et . La norme FIPS 186-4 spécifie que et doivent avoir l'une des valeurs suivantes : (1024, 160), (2048, 224), (2048, 256) ou (3072, 256). ${\displaystyle N <semantics><mrow><mstyle><mi>N</mi></mstyle></mrow><annotation>{\displaystyle N}</annotation></semantics></math><img src=$ ${\displaystyle N<L <semantics><mrow><mstyle><mi>N</mi><mo><</mo><mi>L</mi></mstyle></mrow><annotation>{\displaystyle N<L}</annotation></semantics></math><img src=$ ${\displaystyle N\leq |H| <semantics><mrow><mstyle><mi>N</mi><mo>≤</mo><mrow><mo>|</mo></mrow><mi>H</mi><mrow><mo>|</mo></mrow></mstyle></mrow><annotation>{\displaystyle N\leq |H|}</annotation></semantics></math><img src=$ ${\displaystyle L <semantics><mrow><mstyle><mi>L</mi></mstyle></mrow><annotation>{\displaystyle L}</annotation></semantics></math><img src=$ ${\displaystyle N <semantics><mrow><mstyle><mi>N</mi></mstyle></mrow><annotation>{\displaystyle N}</annotation></semantics></math><img src=$
Choisissez un nombre premier de bits . ${\displaystyle N <semantics><mrow><mstyle><mi>N</mi></mstyle></mrow><annotation>{\displaystyle N}</annotation></semantics></math><img src=$ ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$
Choisissez un nombre premier de bits tel que soit un multiple de . ${\displaystyle L <semantics><mrow><mstyle><mi>L</mi></mstyle></mrow><annotation>{\displaystyle L}</annotation></semantics></math><img src=$ ${\displaystyle p <semantics><mrow><mstyle><mi>p</mi></mstyle></mrow><annotation>{\displaystyle p}</annotation></semantics></math><img src=$ ${\displaystyle p-1 <semantics><mrow><mstyle><mi>p</mi><mo>−</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle p-1}</annotation></semantics></math><img src=$ ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$
Choisissez un entier au hasard parmi . ${\displaystyle h <semantics><mrow><mstyle><mi>h</mi></mstyle></mrow><annotation>{\displaystyle h}</annotation></semantics></math><img src=$ ${\displaystyle \{2\ldots p-2\ <semantics><mrow><mstyle><mo>{</mo><mn>2</mn><mo>…</mo><mi>p</mi><mo>−</mo><mn>2</mn><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{2\ldots p-2\}}</annotation></semantics></math><img src=$
Calculer . Dans le rare cas où cela se produit, réessayer avec une valeur différente . On utilise généralement. Cette exponentiation modulaire peut être calculée efficacement même si les valeurs sont grandes. ${\displaystyle g:=h^{(p-1)/q}\mod p <semantics><mrow><mstyle><mi>g</mi><mo>:=</mo><msup><mi>h</mi><mrow><mo>(</mo><mi>p</mi><mo>−</mo><mn>1</mn><mo>)</mo><mrow><mo>/</mo></mrow><mi>q</mi></mrow></msup><mspace></mspace><mi>mod</mi><mspace></mspace><mspace></mspace><mi>p</mi></mstyle></mrow><annotation>{\displaystyle g:=h^{(p-1)/q}\mod p}</annotation></semantics></math><img src=$ ${\displaystyle g=1 <semantics><mrow><mstyle><mi>g</mi><mo>=</mo><mn>1</mn></mstyle></mrow><annotation>{\displaystyle g=1}</annotation></semantics></math><img src=$ ${\displaystyle h <semantics><mrow><mstyle><mi>h</mi></mstyle></mrow><annotation>{\displaystyle h}</annotation></semantics></math><img src=$ ${\displaystyle h=2 <semantics><mrow><mstyle><mi>h</mi><mo>=</mo><mn>2</mn></mstyle></mrow><annotation>{\displaystyle h=2}</annotation></semantics></math><img src=$

Les paramètres de l'algorithme sont ( , , ). Ceux-ci peuvent être partagés entre différents utilisateurs du système. ${\displaystyle p <semantics><mrow><mstyle><mi>p</mi></mstyle></mrow><annotation>{\displaystyle p}</annotation></semantics></math><img src=$ ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$ ${\displaystyle g <semantics><mrow><mstyle><mi>g</mi></mstyle></mrow><annotation>{\displaystyle g}</annotation></semantics></math><img src=$

Clés par utilisateur

À partir d'un ensemble de paramètres, la deuxième phase calcule la paire de clés pour un utilisateur unique :

Choisissez un entier au hasard parmi . ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$ ${\displaystyle \{1\ldots q-1\ <semantics><mrow><mstyle><mo>{</mo><mn>1</mn><mo>…</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{1\ldots q-1\}}</annotation></semantics></math><img src=$
Calculer . ${\displaystyle y:=g^{x}\mod p <semantics><mrow><mstyle><mi>y</mi><mo>:=</mo><msup><mi>g</mi><mrow><mi>x</mi></mrow></msup><mspace></mspace><mi>mod</mi><mspace></mspace><mspace></mspace><mi>p</mi></mstyle></mrow><annotation>{\displaystyle y:=g^{x}\mod p}</annotation></semantics></math><img src=$

${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$ ${\displaystyle y <semantics><mrow><mstyle><mi>y</mi></mstyle></mrow><annotation>{\displaystyle y}</annotation></semantics></math><img src=$

2. Répartition des clés

Le signataire doit publier la clé publique . Autrement dit, il doit transmettre la clé au destinataire par un mécanisme fiable, mais pas nécessairement secret. Le signataire doit garder sa clé privée secrète. ${\displaystyle y <semantics><mrow><mstyle><mi>y</mi></mstyle></mrow><annotation>{\displaystyle y}</annotation></semantics></math><img src=$ ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$

3. Signature

Un message est signé comme suit : ${\displaystyle m <semantics><mrow><mstyle><mi>m</mi></mstyle></mrow><annotation>{\displaystyle m}</annotation></semantics></math><img src=$

Choisissez un entier au hasard parmi ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle \{1\ldots q-1\ <semantics><mrow><mstyle><mo>{</mo><mn>1</mn><mo>…</mo><mi>q</mi><mo>−</mo><mn>1</mn><mo>}</mo></mstyle></mrow><annotation>{\displaystyle \{1\ldots q-1\}}</annotation></semantics></math><img src=$
Calculer . Dans le cas improbable où , recommencer avec un nombre aléatoire différent . ${\displaystyle r:=\left(g^{k}{\bmod {\,}}p ight){\bmod {\,}}q <semantics><mrow><mstyle><mi>r</mi><mo>:=</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mrow><mi>k</mi></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>p</mi></mrow><mo>)</mo></mrow><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle r:=\left(g^{k}{\bmod {\,}}p ight){\bmod {\,}}q}</annotation></semantics></math><img src=$ ${\displaystyle r=0 <semantics><mrow><mstyle><mi>r</mi><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle r=0}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$
Calculer . Dans le cas improbable où , recommencer avec un nombre aléatoire différent . ${\displaystyle s:=\left(k^{-1}\left(H(m)+xr ight) ight){\bmod {\,}}q <semantics><mrow><mstyle><mi>s</mi><mo>:=</mo><mrow><mo>(</mo><mrow><msup><mi>k</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mrow><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><mo>+</mo><mi>x</mi><mi>r</mi></mrow><mo>)</mo></mrow></mrow><mo>)</mo></mrow><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle s:=\left(k^{-1}\left(H(m)+xr ight) ight){\bmod {\,}}q}</annotation></semantics></math><img src=$ ${\displaystyle s=0 <semantics><mrow><mstyle><mi>s</mi><mo>=</mo><mn>0</mn></mstyle></mrow><annotation>{\displaystyle s=0}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$

La signature est ${\displaystyle \left(r,s ight) <semantics><mrow><mstyle><mrow><mo>(</mo><mrow><mi>r</mi><mo>,</mo><mi>s</mi></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle \left(r,s ight)}</annotation></semantics></math><img src=$

Le calcul de et revient à créer une nouvelle clé par message. L'exponentiation modulaire, dans le calcul, est l'étape la plus coûteuse de l'opération de signature, mais elle peut être effectuée avant que le message ne soit connu. Le calcul de l'inverse modulaire est la deuxième étape la plus coûteuse et peut également être effectué avant que le message ne soit connu. Il peut être calculé à l'aide de l' algorithme d'Euclide étendu ou du petit théorème de Fermat . ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle r <semantics><mrow><mstyle><mi>r</mi></mstyle></mrow><annotation>{\displaystyle r}</annotation></semantics></math><img src=$ ${\displaystyle r <semantics><mrow><mstyle><mi>r</mi></mstyle></mrow><annotation>{\displaystyle r}</annotation></semantics></math><img src=$ ${\displaystyle k^{-1}{\bmod {\,}}q <semantics><mrow><mstyle><msup><mi>k</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle k^{-1}{\bmod {\,}}q}</annotation></semantics></math><img src=$ ${\displaystyle k^{q-2}{\bmod {\,}}q <semantics><mrow><mstyle><msup><mi>k</mi><mrow><mi>q</mi><mo>−</mo><mn>2</mn></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle k^{q-2}{\bmod {\,}}q}</annotation></semantics></math><img src=$

4. Vérification de la signature

On peut vérifier qu'une signature est valide pour un message de la manière suivante : ${\displaystyle \left(r,s ight) <semantics><mrow><mstyle><mrow><mo>(</mo><mrow><mi>r</mi><mo>,</mo><mi>s</mi></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle \left(r,s ight)}</annotation></semantics></math><img src=$ ${\displaystyle m <semantics><mrow><mstyle><mi>m</mi></mstyle></mrow><annotation>{\displaystyle m}</annotation></semantics></math><img src=$

Vérifiez cela et . ${\displaystyle 0<r<q <semantics><mrow><mstyle><mn>0</mn><mo><</mo><mi>r</mi><mo><</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle 0<r<q}</annotation></semantics></math><img src=$ ${\displaystyle 0<s<q <semantics><mrow><mstyle><mn>0</mn><mo><</mo><mi>s</mi><mo><</mo><mi>q</mi></mstyle></mrow><annotation>{\displaystyle 0<s<q}</annotation></semantics></math><img src=$
Calculer . ${\displaystyle w:=s^{-1}{\bmod {\,}}q <semantics><mrow><mstyle><mi>w</mi><mo>:=</mo><msup><mi>s</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle w:=s^{-1}{\bmod {\,}}q}</annotation></semantics></math><img src=$
Calculer . ${\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q <semantics><mrow><mstyle><msub><mi>vous</mi><mrow><mn>1</mn></mrow></msub><mo>:=</mo><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><mo>⋅</mo><mi>w</mi><mspace></mspace><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}</annotation></semantics></math><img src=$
Calculer . ${\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q <semantics><mrow><mstyle><msub><mi>vous</mi><mrow><mn>2</mn></mrow></msub><mo>:=</mo><mi>r</mi><mo>⋅</mo><mi>w</mi><mspace></mspace><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}</annotation></semantics></math><img src=$
Calculer . ${\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p ight){\bmod {\,}}q <semantics><mrow><mstyle><mi>v</mi><mo>:=</mo><mrow><mo>(</mo><mrow><msup><mi>g</mi><mrow><msub><mi>vous</mi><mrow><mn>1</mn></mrow></msub></mrow></msup><msup><mi>y</mi><mrow><msub><mi>vous</mi><mrow><mn>2</mn></mrow></msub></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>p</mi></mrow><mo>)</mo></mrow><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p ight){\bmod {\,}}q}</annotation></semantics></math><img src=$
La signature est valide si et seulement si . ${\displaystyle v=r <semantics><mrow><mstyle><mi>v</mi><mo>=</mo><mi>r</mi></mstyle></mrow><annotation>{\displaystyle v=r}</annotation></semantics></math><img src=$

Exactitude de l'algorithme

Le schéma de signature est correct dans la mesure où le vérificateur acceptera toujours les signatures authentiques. Cela peut être démontré comme suit :

Premièrement, puisque , il s'ensuit, d' après le petit théorème de Fermat , que . Puisque et est premier, doit être d'ordre . ${ extstyle g=h^{(p-1)/q}~{ ext{mod}}~p <semantics><mrow><mstyle><mi>g</mi><mo>=</mo><msup><mi>h</mi><mrow><mo>(</mo><mi>p</mi><mo>−</mo><mn>1</mn><mo>)</mo><mrow><mo>/</mo></mrow><mi>q</mi></mrow></msup><mtext> </mtext><mrow><mtext>mod</mtext></mrow><mtext> </mtext><mi>p</mi></mstyle></mrow><annotation>{ extstyle g=h^{(p-1)/q}~{ ext{mod}}~p}</annotation></semantics></math><img src=$ ${ extstyle g^{q}\equiv h^{p-1}\equiv 1\mod p <semantics><mrow><mstyle><msup><mi>g</mi><mrow><mi>q</mi></mrow></msup><mo>≡</mo><msup><mi>h</mi><mrow><mi>p</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>≡</mo><mn>1</mn><mspace></mspace><mi>mod</mi><mspace></mspace><mspace></mspace><mi>p</mi></mstyle></mrow><annotation>{ extstyle g^{q}\equiv h^{p-1}\equiv 1\mod p}</annotation></semantics></math><img src=$ $0 g > 0$ 0 ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$ ${\displaystyle g <semantics><mrow><mstyle><mi>g</mi></mstyle></mrow><annotation>{\displaystyle g}</annotation></semantics></math><img src=$ ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$

Le signataire calcule

{\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q <semantics><mrow><mstyle><mi>s</mi><mo>=</mo><msup><mi>k</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>(</mo><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><mo>+</mo><mi>x</mi><mi>r</mi><mo>)</mo><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mstyle></mrow><annotation>{\displaystyle s=k^{-1}(H(m)+xr){\bmod {\,}}q}</annotation></semantics></math></span><img src=

Ainsi

{\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>k</mi></mtd><mtd><mi></mi><mo>≡</mo><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><msup><mi>s</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><mi>x</mi><mi>r</mi><msup><mi>s</mi><mrow><mo>−</mo><mn>1</mn></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>≡</mo><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><mi>w</mi><mo>+</mo><mi>x</mi><mi>r</mi><mi>w</mi><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mi>q</mi><mo>)</mo></mrow></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}k&\equiv H(m)s^{-1}+xrs^{-1}\\&\equiv H(m)w+xrw{\pmod {q}}\end{aligned}}}</annotation></semantics></math></span><img src=

Puisque nous avons l'ordre, nous avons ${\displaystyle g <semantics><mrow><mstyle><mi>g</mi></mstyle></mrow><annotation>{\displaystyle g}</annotation></semantics></math><img src=$ ${\displaystyle q <semantics><mrow><mstyle><mi>q</mi></mstyle></mrow><annotation>{\displaystyle q}</annotation></semantics></math><img src=$

{\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msup><mi>g</mi><mrow><mi>k</mi></mrow></msup></mtd><mtd><mi></mi><mo>≡</mo><msup><mi>g</mi><mrow><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><mi>w</mi></mrow></msup><msup><mi>g</mi><mrow><mi>x</mi><mi>r</mi><mi>w</mi></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>≡</mo><msup><mi>g</mi><mrow><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo><mi>w</mi></mrow></msup><msup><mi>y</mi><mrow><mi>r</mi><mi>w</mi></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>≡</mo><msup><mi>g</mi><mrow><msub><mi>vous</mi><mrow><mn>1</mn></mrow></msub></mrow></msup><msup><mi>y</mi><mrow><msub><mi>vous</mi><mrow><mn>2</mn></mrow></msub></mrow></msup><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mi>p</mi><mo>)</mo></mrow></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}g^{k}&\equiv g^{H(m)w}g^{xrw}\\&\equiv g^{H(m)w}y^{rw}\\&\equiv g^{u_{1}}y^{u_{2}}{\pmod {p}}\end{aligned}}}</annotation></semantics></math></span><img src=

Enfin, la validité de DSA découle de

{\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>r</mi></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><msup><mi>g</mi><mrow><mi>k</mi></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>p</mi><mo>)</mo><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><msup><mi>g</mi><mrow><msub><mi>vous</mi><mrow><mn>1</mn></mrow></msub></mrow></msup><msup><mi>y</mi><mrow><msub><mi>vous</mi><mrow><mn>2</mn></mrow></msub></mrow></msup><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>p</mi><mo>)</mo><mrow><mo>mod</mo><mrow><mspace></mspace></mrow></mrow><mi>q</mi></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mi>v</mi></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}r&=(g^{k}{\bmod {\,}}p){\bmod {\,}}q\\&=(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p){\bmod {\,}}q\\&=v\end{aligned}}}</annotation></semantics></math></span><img src=

Sensibilité

Avec DSA, l'entropie, la confidentialité et l'unicité de la valeur de signature aléatoire sont essentielles. Leur importance est telle que la violation de l'une de ces trois conditions peut révéler la totalité de la clé privée à un attaquant. Utiliser deux fois la même valeur (même en la gardant secrète), utiliser une valeur prévisible, ou divulguer ne serait-ce que quelques bits dans plusieurs signatures, suffit à révéler la clé privée . ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$

Ce problème affecte à la fois DSA et l'algorithme de signature numérique à courbe elliptique ( ECDSA ). En décembre 2010, le groupe fail0verflow a annoncé la récupération de la clé privée ECDSA utilisée par Sony pour signer les logiciels de la console de jeux PlayStation 3. L'attaque a été rendue possible par le fait que Sony n'a pas généré de nouvelle valeur aléatoire pour chaque signature. ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$

Ce problème peut être évité en dérivant de manière déterministe le hachage à partir de la clé privée et du hachage du message, comme décrit dans la RFC 6979. Cela garantit que le hachage est différent pour chaque attaquant et imprévisible pour ceux qui ne connaissent pas la clé privée . ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$ ${\displaystyle H(m) <semantics><mrow><mstyle><mi>H</mi><mo>(</mo><mi>m</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle H(m)}</annotation></semantics></math><img src=$ ${\displaystyle x <semantics><mrow><mstyle><mi>x</mi></mstyle></mrow><annotation>{\displaystyle x}</annotation></semantics></math><img src=$

De plus, des implémentations malveillantes de DSA et d'ECDSA peuvent être créées, où le choix de la méthode permet de divulguer des informations de manière subliminale via les signatures. Par exemple, une clé privée hors ligne pourrait être divulguée à partir d'un dispositif hors ligne parfaitement sécurisé qui ne publierait que des signatures d'apparence innocente. ${\displaystyle k <semantics><mrow><mstyle><mi>k</mi></mstyle></mrow><annotation>{\displaystyle k}</annotation></semantics></math><img src=$

Mises en œuvre

Vous trouverez ci-dessous une liste non exhaustive de bibliothèques cryptographiques prenant en charge DSA :