Cryptographie à clé publique

Cours 5

Julien Lavauzelle
Université Paris 8
Master 1 mathématiques et applications – parcours ACC
26/02/2024
 Aujourd’hui

1. Signatures numériques

2. Quelques schémas de signature

Signature RSA
Signature RSA avec full domain hash
Signature ElGamal

1/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Plan

1. Signatures numériques

2. Quelques schémas de signature

Signature RSA
Signature RSA avec full domain hash
Signature ElGamal

1/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Contexte et motivations

On souhaite imiter (voire améliorer) certaines propriétés des signatures manuscrites.

Exemples de ce qu’on souhaite signer numériquement :
– des emails – de la communication publique (sites web)
– du code (mise à jour de logiciels)
– des transactions bancaires (ecommerce) – des clés de chiffrement, des certificats

Objectifs :
– Intégrité : on peut vérifier si le message a été modifié ou non.
– Authenticité : on peut associer un message à un émetteur.
– Non-répudiation : on ne peut pas nier avoir émis une signature valide.
– Infalsifiabilité : une autre personne ne peut pas prétendre avoir émis la signature.
– Non-réutilisation : on ne peut pas utiliser une même signature sur deux messages différents.

Remarque. Ces propriétés ne sont pas toutes vérifiées par la signature « physique ».

2/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Contexte et motivations

Remarque. Une signature d’un message m n’est pas :

1. du chiffrement (on ne cache pas la valeur du message),
2. « l’inverse du chiffrement asymétrique » (même si parfois ça y ressemble),
3. un MAC (message authentication code) : les signatures sont publiquement vérifiables.

La signature va s’apposer au message, et devra dépendre explicitement de lui.

Par conséquent, les propriétés additionnelles désirables d’une signature sont :
– des signatures courtes,
– des algorithmes de signature et vérification rapides,
– des clés courtes.

3/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Un dessin récapitulatif

Phase de vérification
→ opérée par quiconque
Phase de signature
→ opérée par Alice

message
message

+
+ clé publique pk
clé secrète sk +
signature ?

signature
signature acceptée ou non-acceptée

4/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Définition

Définition. Un schéma de signature numérique (à clé publique) est constitué de deux ensembles
1. M un ensemble de messages,
2. S un ensemble de signatures,
et de trois algorithmes :
1. KeyGen l’algorithme de génération de clés. Il renvoie un couple (pk, sk) de clé publique/clé privée.
2. Sign un algorithme de signature, qui prend en entrée un message m ∈ M, la clé privée sk, et retourne une
signature s = Sign(m, sk) ∈ S .
3. Verif un algorithme de vérification, qui renvoie une valeur booléenne true/false. L’algorithme Verif prend en
entrée la clé publique pk, le message m et la signature s.

Le schéma de signature est valide si

∀(m, s) ∈ M × S , Verif (m, s, pk) = true ⇐⇒ s = Sign(m, sk)

5/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Modèle d’attaquant (moyens)

Pour la sécurité du schéma, il faut définir un modèle d’attaquant (moyens) et un modèle d’attaque (objectifs).

On distingue différents moyens d’attaques, notamment :

1. Attaque à clé seule (key-only attack, KOA) : l’attaquant ne dispose que de la clé publique
2. Attaque à message connu (known-message attack, KMA) : l’attaquant dispose d’une liste de messages déjà
signés (m1 , s1 ), . . . , (mℓ , sℓ ). Les signatures sont valides et réalisées avec la même clé.
3. Attaque à message choisi (chosen-message attack, CMA) : l’attaquant choisit des messages m1 , . . . , mℓ et
demande les signatures s1 , . . . , sℓ associées. Les signatures sont valides et réalisées avec la même clé.

6/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Modèle d’attaquant (objectifs)

Les modèles d’attaque principaux sont les suivants :

1. Cassage total : l’attaquant détermine une clé privée équivalente à celle d’Alice.
2. Falsification universelle : avec probabilité non-négligeable, l’attaquant peut falsifier une signature d’un
message choisi par quelqu’un d’autre. Ce message n’aura pas été signé précédemment.
3. Falsification existentielle : avec probabilité non-négligeable, l’attaquant peut créer un couple (m, s) où s est
une signature valide de m. Ce message n’aura pas été signé précédemment.

Le fait qu’un schéma de signature ne permette pas d’effectuer une falsification existentielle sera noté EUF (Existential
UnForgeability).
De même, le fait qu’un schéma de signature ne permette pas d’effectuer une falsification universelle sera noté UUF
(Universal UnForgeability).

7/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Sécurité d’une signature

Comme pour le chiffrement, on combine les définitions précédentes pour définir la sécurité d’un schéma de
signature.
Par exemple :

Définition (exemple). On dit qu’un schéma satisfait la propriété d’infalsification existentielle sous une attaque à
message choisi (EUF-CMA,  Existential UnForgeability under Chosen Message Attack) si :
 la clé publique pk,
tout attaquant ayant accès à une liste de messages m1 , . . . , mℓ qu’il a choisis,
et les signatures associées s1 , . . . , sℓ ,

a une probabilité négligeable de retourner un message m′ ∈ / {mi } et une signature s′ tels que

Verif (m′ , s′ , pk) = true

Remarque. EUF-CMA est le standard de sécurité usuellement requis.

8/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Plan

1. Signatures numériques

2. Quelques schémas de signature

Signature RSA
Signature RSA avec full domain hash
Signature ElGamal

8/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Plan

1. Signatures numériques

2. Quelques schémas de signature

Signature RSA
Signature RSA avec full domain hash
Signature ElGamal

8/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Première idée
Phase de vérification
Phase de signature opérée par quiconque
opérée par Alice

message
message

+
+ clé publique pk
clé secrète sk +
signature ?
signature
vrai ou faux

Idée informelle : admettons que l’on ait à disposition une fonction à sens unique f , dont Alice connaît une trappe
(par exemple, dans RSA, f : x 7→ xe mod n). Tout le monde sait calculer f , seule Alice sait l’inverser.
Alors, pour signer un message m :
▶ Alice serait la seule à pouvoir émettre la signature s = f −1 (m)
▶ tout le monde pourrait vérifier que f (s) = m.

9/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Signature RSA

Signature RSA : génération de clés KeyGen

1. Calculer n = pq et ϕ(n) = (p − 1)(q − 1), où p et q sont deux grands nombres premiers aléatoires
2. Choisir e et d tels que ed ≡ 1 mod ϕ(n)
3. La clé publique est pk = (e, n), la clé privée est sk = (d, ϕ(n)).

L’espace des messages est M = Z/nZ et celui des signatures est S = Z/nZ.

Signature RSA : signature Sign(m, sk)

1. Calculer s = md mod n.
2. Retourner s.

Signature RSA : vérification Verif (m, s, pk)

1. Calculer m′ = se mod n.
2. Faire le test m′ = m et retourner le booléen associé.

Validité. m′ ≡ se ≡ med ≡ m mod n.

10/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Sécurité

Résumé (signature RSA).

?
Clés : pk = (n, e), sk = d, Vérification : se mod n ≡ m mod n
Signature : s = md mod n

Que dire de la sécurité de ce schéma ?

Proposition. La signature RSA « brute » n’est pas EUF-KOA. Autrement dit, il existe une attaque de falsification
existentielle sur la signature RSA « brute » avec la clé publique seule.

Preuve. À partir de la clé publique pk = (n, e), on peut forger un message m′ et une signature s′ valide pour la clé
privée sk = d d’Alice.
1. Choisir s′ aléatoirement dans S = Z/nZ,
2. Calculer m′ = (s′ )e mod n.

Proposition. Il existe également une attaque de falsification sélective sur la signature RSA « brute », avec des mes-
sages choisis.

Preuve. Au prochain TD. Indication : 2 messages préliminaires suffisent.

11/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Inconvénients

La signature RSA « brute » admet donc plusieurs inconvénients :

1. La sécurité (voir slide précédente).
2. D’un point de vue pratique, on ne peut pas signer un fichier de taille quelconque (M = Z/nZ).

Solution : fonction de hachage !

12/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Plan

1. Signatures numériques

2. Quelques schémas de signature

Signature RSA
Signature RSA avec full domain hash
Signature ElGamal

12/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Rappels sur les fonctions de hachage

Définition. Une famille de fonctions de hachage cryptographiques est un ensemble de fonctions Hκ : {0, 1}∗ → H,
où H est un ensemble de taille fixe, et κ est un paramètre de la famille. L’élément Hκ (m) est appelé haché de m.

Une fonction de hachage H = Hκ est résistante aux collisions si pour tout algorithme polynomial probabiliste A, la
probabilité
P m ̸= m′ et Hκ (m) = Hκ (m′ ) | (m, m′ ) ← A
 

est négligeable devant un paramètre de sécurité donné.

Exemple majeur : les fonctions SHA-3 (pour secure hash algorithm, 3ème version), dont les sorties sont de taille 224,
256, 384 ou 512 bits (au choix).

Important. Les « anciennes » fonctions MD5 et SHA-1 ne sont pas résistantes aux collisions, mais restent utilisées
pour des applications non-cryptographiques (à éviter néanmoins).

Dans toute la suite, on prend H = Hκ : {0, 1}∗ → H une fonction de hachage résistante aux collisions.

13/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 RSA-FDH : full domain hash

Idée : au lieu de signer directement le message m, on signe H (m) avec l’algorithme de signature RSA « brut » vu
précédemment.

La génération de clés est identique : pk = (n, e), sk = d.

L’espace des messages est maintenant M = {0, 1}∗ et celui des signatures reste S = Z/nZ.

Signature RSA-FDH : Sign(m, sk)

On suppose que m ∈ {0, 1}∗ et que H est à valeurs dans S = Z/nZ.
1. Hacher m, c’est-à-dire calculer h := H (m).
2. Calculer et retourner s = hd mod n.

Signature RSA-FDH : Verif (m, s, pk)

1. Calculer h′ = se mod n.
2. Hacher m, c’est-à-dire calculer h := H (m)
3. Faire le test h′ = h et retourner le booléen associé.

Validité. h′ ≡ se ≡ hed ≡ h mod n.

14/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Sécurité

Théorème. Dans le modèle de l’oracle aléatoire, si le problème RSA est difficile, alors la signature RSA-FDH est
EUF-CMA (résistante à toute falsification existentielle par une attaque à message choisi) .

Remarque. Le modèle de l’oracle aléatoire permet d’idéaliser les fonctions de hachage. C’est une hypothèse plus
forte que le modèle standard.
En pratique, on peut utiliser la fonction de hachage SHA-3, de sortie 224 ou 256 bits par exemple.
Pour s’appuyer le résultat (théorique) de sécurité ci-dessus, il faut que l’espace de définition de la fonction RSA soit
le même que l’espace des hachés : c’est la notion de « full domain hash ».

Problème : pour RSA, il faut choisir un module n de 2048 bits minimum, alors que les fonctions de hachage usuelles
forment des hachés de moins de 512 bits.

Plusieurs solutions :
– faire du remplissage aléatoire (padding),
– concaténer des hachés successifs du message H (i) (m) ou des hachés avec incrément H (i) (m || ctr).
Exemple :



FDH (m, IV) = H m || n || IV + 0 || H m || n || IV + 1 || H m || n || IV + 2 || · · ·
où IV est un vecteur d’initialisation public apposé au message.
15/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications
 Performance

La signature RSA-FDH est une brique de base du standard RSA PKCS#1 v2.1.
Performances :
▶ Calcul efficace ? Un haché + O(1) exponentiations modulaires (les clés sont de taille indépendante de celle du
fichier).
▶ Taille de clés ?
clé publique : 2 log2 n ≃ 4096 bits minimum
clé privée : log2 n ≃ 2048 bits minimum
▶ Taille de signature ? log2 n = 2048 bits minimum

16/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Plan

1. Signatures numériques

2. Quelques schémas de signature

Signature RSA
Signature RSA avec full domain hash
Signature ElGamal

16/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Description

On se place dans le groupe multiplicatif d’un corps fini Fp , où p est premier. On note g un générateur de Fp× .
Signature ElGamal : KeyGen
1. Choisir aléatoirement a ∈ Z/(p − 1)Z.
2. Calculer α = ga mod p.
3. La clé publique est pk = α, la clé privée est sk = a.

L’espace des messages est M = Fp× et celui des signatures est S = Fp× × Z/(p − 1)Z.

Signature ElGamal : Sign(m, sk)

1. Choisir aléatoirement k ∈ (Z/(p − 1)Z)× (c’est-à-dire, inversible modulo p − 1).
2. Calculer b = gk mod p.
3. Calculer c = (m − ab)k−1 mod (p − 1).
4. Retourner s = (b, c).

Signature ElGamal : Verif (m, s, pk)

1. Calculer x = αb · bc mod p et y = gm mod p.
2. Faire le test x = y et retourner le booléen associé.

17/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Validité

Résumé (signature ElGamal dans Fp ).

Clés : pk = α = ga , sk = a,
Signature : s = (b, c) où
b = gk mod p
c = (m − ab)k−1 mod (p − 1)
?
Vérification : αb · bc ≡ gm mod p

Remarque. Le premier élément b de la signature s ne dépend pas du message.

Validité. On vérifie que
−1 mod (p−1)
αb · bc = gab+k(m−ab)k ≡ gm mod p

18/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Exemple

Paramètres. On prend de petites tailles pour l’exemple : p = 467, g = 2.

Génération de clés. Alice engendre la clé privée a = 127 ; la clé publique est donc α = ga = 2127 mod 467 ≡ 132.
Signature. Supposons qu’Alice veuille signer le message m = 100.
Elle choisit la valeur aléatoire k = 213. On vérifie bien que
pgcd(k, p − 1) = pgcd(213, 466) = 1, et
k−1 mod (p − 1) vaut alors 431.
Alice calcule alors
b = gk = 2213 ≡ 29 mod 467
−1
c = (m − ab)k = (100 − 127 × 29) × 431 ≡ 51 mod 466

Vérification. On peut alors publiquement vérifier la signature (29, 51) d’Alice pour le message m = 100 :
d’une part, αb · bc = 13229 · 2951 ≡ 189 mod 467,
d’autre part, gm = 2100 ≡ 189 mod 467.

19/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Sécurité

On va montrer que la signature ElGamal "brute" n’est pas EUF-KOA.

But. À partir de la clé publique uniquement, calculer m et s = (b, c) tel que Verif (m, s, pk) = true.

Idée : on va écrire b = gi αj pour i, j ∈ {0, . . . , p − 2}. Cette écriture n’est pas unique.
Dans ce cas la condition de vérification est :

αb (gi αj )c = gm ⇐⇒ αb+jc = gm−ic

Cette condition est vérifiée en particulier si on a :

b + jc ≡ 0 mod (p − 1) et m − ic ≡ 0 mod (p − 1)

L’idée est alors de construire d’abord i quelconque et j inversible modulo p − 1 quelconque, puis de définir b, c et m en
fonction :
 b = gi αj

mod p
c = −bj−1 mod (p − 1)
m = ic mod (p − 1)


Important. Par l’utilisation d’une fonction de hachage, ces menaces peuvent être levées (voir cours suivant).

20/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications

 Fin du cours

Questions ?

21/21 J. Lavauzelle – Clé Publique 5 – M1 mathématiques et applications