Cours 10.

La Signature Numérique

O.R. Merad Boudia

Université d’Oran 1, Ahmed Ben Bella
L3 : 2023/2024

08/04/2024 Sécurité Informatique 1

 Introduction (1/2)
 Les signatures numériques sont l’un des outils cryptographiques les plus importants et sont
largement utilisées aujourd’hui.

 Les applications des signatures numériques vont des certificats numériques pour un
commerce électronique sécurisé à la signature légale de contrats pour sécuriser les mises à
jour logicielles.

 Les signatures numériques partagent certaines fonctionnalités avec les signatures

manuscrites.

 En particulier, ils fournissent une méthode pour garantir qu'un message est authentique
pour un utilisateur, c'est-à-dire qu'il provient bien de la personne qui prétend avoir généré le
message.

 Les systèmes de chiffrement que nous avons rencontrés jusqu'à présent avaient deux
objectifs principaux : soit chiffrer des données (par exemple, avec le chiffrement AES, 3DES
ou RSA), soit établir une clé partagée (par exemple, avec l'échange de clés Diffie-Hellman ou
à courbe elliptique).

O. R. Merad Boudia Sécurité Informatique 2

 Introduction (2/2)
 On pourrait être tenté de penser que nous sommes désormais en mesure de satisfaire les
besoins de sécurité qui se présentent dans la pratique.

 Cependant, outre le chiffrement et l'échange de clés, il existe de nombreux autres besoins

en matière de sécurité, voir cours 1 (page 17).

 Comme pour les signatures manuscrites conventionnelles, seule la personne qui crée un
message numérique doit être capable de générer une signature valide.

 Pour y parvenir avec les primitives cryptographiques, nous devons appliquer la

cryptographie à clé publique.

 L’idée de base est que la personne qui signe le message utilise une clé privée et que le
destinataire utilise la clé publique correspondante.

O. R. Merad Boudia Sécurité Informatique 3

 Principe

Chacune des trois familles populaires d'algorithmes à clé publique, à savoir la factorisation,
les logarithmes discrets et les courbes elliptiques, nous permet de construire des signatures
numériques. Dans la suite de ce cours, nous découvrirons la plupart des systèmes de
signature présentant un intérêt pratique.

O. R. Merad Boudia Sécurité Informatique 4

 Signature RSA
 Le schéma de signature RSA est basé sur le chiffrement RSA introduit dans le cours 8.

 Sa sécurité repose sur la difficulté de factoriser un produit de deux grands nombres premiers
(le problème de la factorisation des nombres entiers).

 Depuis sa première description en 1978, le schéma de signature RSA est apparu comme le
schéma de signature numérique le plus largement utilisé en pratique.

O. R. Merad Boudia Sécurité Informatique 5

 Signature RSA : Exemple
 Supposons que Bob veuille envoyer un message signé (x = 4) à Alice. Les premières étapes
sont exactement les mêmes que pour un cryptage RSA : Bob calcule ses paramètres RSA et
envoie la clé publique à Alice. Contrairement au système de chiffrement, la clé privée est
désormais utilisée pour la signature, tandis que la clé publique est nécessaire pour vérifier la
signature.

O. R. Merad Boudia Sécurité Informatique 6

 Remarques
 Tout d’abord, on remarque que la signature est aussi longue que le module n, c’est-à-dire à
peu près log2n bit.

 Comme indiqué précédemment, n est généralement compris entre 1 024 et 3 072 bits.

 Même si une telle longueur de signature ne pose pas de problème dans la plupart des
applications Internet, elle peut s'avérer indésirable dans les systèmes dont la bande
passante et/ou l'énergie sont limitées, par exemple les téléphones mobiles.

 Le processus de génération de clé est identique à celui que nous avons utilisé pour le
cryptage RSA.

 Les techniques d'accélération pour RSA sont également applicables au système de signature
numérique.

 Les clés publiques courtes e sont particulièrement intéressantes, par exemple le choix e =
216 + 1. Cela fait de la vérification une opération très rapide.

 Étant donné que dans de nombreux scénarios pratiques, un message n’est signé qu’une
seule fois mais vérifié plusieurs fois, le fait que la vérification soit très rapide est utile.

O. R. Merad Boudia Sécurité Informatique 7

 Signature Elgamal
 Le schéma de signature Elgamal, publié en 1985, repose sur la difficulté de calculer
des logarithmes discrets.

 Contrairement à RSA, où le cryptage et la signature numérique sont des opérations

presque identiques, la signature numérique Elgamal est assez différente du schéma
de cryptage du même nom.

O. R. Merad Boudia Sécurité Informatique 8

 Génération des clés
 Comme pour tout système à clé publique, il existe une phase de configuration au
cours de laquelle les clés sont calculées.

 Nous commençons par trouver un grand p premier et construisons un problème de

logarithme discret comme suit :

O. R. Merad Boudia Sécurité Informatique 9

 Signature
 À l'aide de la clé privée et des paramètres de la clé publique, la signature :

pour un message x est calculée pendant le processus de signature.

 Notez que la signature est constituée de deux entiers r et s.

O. R. Merad Boudia Sécurité Informatique 10

 Vérification
 Du côté de la réception, la signature est vérifiée à l'aide de la clé publique, de la
signature et du message.

O. R. Merad Boudia Sécurité Informatique 11

 Exemple


O. R. Merad Boudia Sécurité Informatique 12

 Remarques
 La phase de génération de clé est identique à celle du chiffrement Elgamal.

 La sécurité du schéma de signature repose sur le problème du logarithme discret.

 En particulier, le nombre premier p doit avoir une longueur d'au moins 1024 bits.

 La clé privée doit être générée par un CSPRNG.

 La clé publique nécessite une exponentiation utilisant l'algorithme Square &

Multiply.

 La signature est constituée de la paire (r,s). Les deux ont à peu près la même
longueur de bits que p, de sorte que la longueur totale du paquet (x,(r,s)) est
environ trois fois plus longue que le message x.

O. R. Merad Boudia Sécurité Informatique 13

 Signature DSA
 L’algorithme de signature Elgamal décrit précédemment est rarement utilisé en
pratique.

 Au lieu de cela, une variante beaucoup plus populaire est utilisée, connue sous le
nom d’algorithme de signature numérique (DSA).

 Il s'agit d'un standard proposé par le NIST (National Institute of Standards and
Technology).

 Ses principaux avantages par rapport au schéma de signature Elgamal sont que la
signature ne fait que 320 bits et que certaines des attaques pouvant menacer le
schéma Elgamal ne sont pas applicables sur DSA.

O. R. Merad Boudia Sécurité Informatique 14

 Génération des clés
 Les clés du DSA sont calculées comme suit :

 Notez que des longueurs de bits plus longues sont également possibles.

O. R. Merad Boudia Sécurité Informatique 15

 Signature
 Comme dans le schéma de signature Elgamal, la signature DSA est constituée d'une
paire d'entiers (r,s).

 Étant donné que chacun des deux paramètres ne fait que 160 bits, la longueur
totale de la signature est de 320 bits.

 À l'aide des clés publique et privée, la signature d'un message x est calculée
comme suit :

 Selon le standard, le message x doit être haché à l'aide de la fonction de hachage

SHA-1 afin de calculer s.

O. R. Merad Boudia Sécurité Informatique 16

 Vérification

 Le vérificateur n'accepte une signature (r,s) que si v ≡ r mod q est satisfaite. Sinon,
la vérification échoue.
 Dans ce cas, le message ou la signature peut avoir été modifié ou le vérificateur
n'est pas en possession de la bonne clé publique. Dans tous les cas, la signature
doit être considérée comme invalide.

O. R. Merad Boudia Sécurité Informatique 17

 Exemple
 Bob veut envoyer un message x à Alice qui doit être signé avec l'algorithme DSA.
Supposons que la valeur de hachage de x soit h(x) = 26. Le processus de signature
et de vérification est alors le suivant :

O. R. Merad Boudia Sécurité Informatique 18

 Remarques
 Lors de la signature, nous calculons les paramètres r et s. Le calcul de r implique
d'abord l'évaluation de gkE mod p à l'aide de l'algorithme square & multiply.
 Le résultat, qui a une longueur de 1024 bits, est ensuite réduit à 160 bits par
l'opération « mod q ». Le calcul de s implique uniquement des nombres de 160
bits. L’étape la plus coûteuse est l’inversion de kE.
 Le calcul des paramètres auxiliaires w, u1 et u2 ne fait intervenir que des
opérandes de 160 bits, ce qui les rend relativement rapides.
 La sécurité de DSA est basée sur le logarithme discret.
 Il convient de souligner que le record des calculs de logarithmes discrets est de 795
bits en 2019. Lien.
 Par conséquent, la variante DSA à 1 024 bits est actuellement sécurisée, et les
variantes à 2 048 bits et 3 072 bits semblent offrir une bonne sécurité à long
terme.

O. R. Merad Boudia Sécurité Informatique 19

 La signature ECDSA
 Comme discuté dans le cours précèdent, les courbes elliptiques présentent
plusieurs avantages par rapport aux schémas RSA et DL comme Elgamal ou DSA.

 En particulier, en l'absence d'attaques puissantes contre les cryptosystèmes à

courbe elliptique (ECC), des longueurs de bits comprises entre 160 et 256 bits
peuvent être choisies, ce qui offre une sécurité équivalente aux schémas RSA et DL
de 1 024 à 3 072 bits.

 La longueur de bit plus courte de l'ECC entraîne souvent un temps de traitement

plus court et des signatures plus courtes.

 Pour ces raisons, l’algorithme de signature numérique à courbe elliptique (ECDSA)

a été standardisé par l’American National Standards Institute (ANSI) en 1998.

O. R. Merad Boudia Sécurité Informatique 20

 Génération des clés
 Les clés de l'ECDSA sont calculées comme suit :

Notez que nous avons mis en place un problème de logarithme discret où l'entier d est la clé
privée et le résultat de la multiplication scalaire, le point B, est la clé publique. Semblable au DSA,
le groupe cyclique a un ordre q qui doit avoir une taille d'au moins 160 bits ou plus pour des
niveaux de sécurité plus élevés.
O. R. Merad Boudia Sécurité Informatique 21
 Signature
 Comme DSA, une signature ECDSA se compose d'une paire d'entiers (r,s). Chaque valeur a la
même longueur de bits que q, ce qui donne des signatures assez compactes. À l'aide des
clés publique et privée, la signature d'un message x est calculée comme suit :

 Dans l'étape 3, la coordonnée x du point R est affectée à la variable r.

 Le message x doit être haché à l'aide de la fonction h afin de calculer s.

 La longueur de sortie de la fonction de hachage doit être au moins aussi longue que q.

O. R. Merad Boudia Sécurité Informatique 22

 Vérification
 Le processus de vérification de la signature est le suivant :

 Dans la dernière étape, la notation xP indique la coordonnée x du point P.

 Le vérificateur n'accepte une signature (r,s) que si le xP a la même valeur que le paramètre
de signature r modulo q.

 Dans le cas contraire, la signature devrait être considérée comme invalide.

O. R. Merad Boudia Sécurité Informatique 23

 Exemple

O. R. Merad Boudia Sécurité Informatique 24

 Remarques
 La multiplication par un scalaire est l’opération la plus couteuse.

 Dans la vérification, la charge de calcul principale se produit lors de l’évaluation de

P = u1A + u2B. Ceci peut être accompli par deux multiplications de points distinctes.
Cependant, il existe des méthodes spécialisées d'exponentiation simultanée qui
sont plus rapides que les multiplications de deux points individuels. (Lien)

 La sécurité de ECDSA est basée sur l’ECDLP.

 Le niveau de sécurité de la fonction de hachage doit également correspondre à

celui du problème du logarithme discret.

 La force cryptographique d’une fonction de hachage est principalement

déterminée par la longueur de sa sortie.

O. R. Merad Boudia Sécurité Informatique 25

 Exercice
 Étant donné un schéma de signature RSA avec la clé publique (n = 9797,e = 131),
Parmi les signatures suivantes, lesquelles sont valides ?

O. R. Merad Boudia Sécurité Informatique 26

 Bibliographie
 Livre : cybersécurité ; analyser les risques, mettre en œuvre les solutions. S.
Ghernaouti, DUNOD, 2019.

 Livre : Tout sur la sécurité informatique. J-F. Pillou et J-P. Bay, DUNOD, 2013.

 Livre : Sécurité informatique et Réseaux. S. Ghernaouti, DUNOD, 2013.

 Livre : Tableaux de bord de la sécurité réseau. C. Llorens, L. Levier et D. Valois,

Eyrolles, 2011

 Livre : Understanding cryptography: a textbook for students and practitioners.

Paar, Christof, and Jan Pelzl. Springer Science & Business Media, 2009.

O. R. Merad Boudia Sécurité Informatique 27