Rappels
Chiffrement à clé publique
Cryptosystème RSA
Anca Nitulescu
[email protected]
Ecole Normale Supérieure, Paris
Cours 3
1/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Rappels mathématiques
Outils mathématiques
Algorithme d’Euclide étendu
Nombres premiers grands
Exponentiation modulaire
Inversion modulaire
Calcul des restes chinois
2/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Arithmétique modulaire
(Zn , +) forme un groupe additif commutatif d’ordre n.
(Zn , +, ·) forme un anneau commutatif.
Inverse modulaire de a dans Zn : entier b = a−1 tel que
a×b =1 mod n
Z?n = l’ensemble des éléments inversibles modulo n.
(Z?n , ·) forme un groupe multiplicatif.
(Zp , +, ·) forme un corps commutatif.
Attention !
Z?n 6= Zn \ {0} pour n composé
Z?p = Zp \ {0} pour p prime
3/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Critère d’inversibilité
Les entiers inversibles modulo n
x ∈ Z?n est inversibles modulo n si et seulement si pgcd(x, n) = 1.
Preuve : T. Bézout.
Calcul de l’inverse modulaire
Trouver x −1 mod n
Il existe u et v tels que xu + nv = pgcd(x, n) = 1
Trouver l’inverse d’un élément revient à calculer u.
L’algorithme d’Euclid étendu calcule des coeficients (u, v )
4/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Fonction d’Euler
Définition
ϕ(n) est le nombre d’entiers de [1, n] qui sont premiers avec n.
ϕ(n) désigne l’ordre du groupe multiplicatif Z?n
Propriétés
si p est premier et q premier :
ϕ(p) = p − 1
ϕ(pq) = ϕ(p)ϕ(q)
5/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Exponentiation modulaire
Théorème de Lagrange
Si G est un groupe multiplicatif d’ordre n, alors :
∀g ∈ G g n = e
Théorème d’Euler
Pour tout entier n et tout a ∈ Z?n , on a
aϕ(n) = 1 mod n
Petit théorème de Fermat
Pour p premier et tout entier a on a
ap = a mod p
6/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Exponentiation modulaire
Ordre du groupe Z?n
ordre |Z?n | = ϕ(n) ⇒ aϕ(n) = 1 (mod n)
ordre |Z?p | = ϕ(p) = p − 1 ⇒ ap−1 = 1 (mod n)
Règles
Dans une exponentiation modulaire (modulo un entier M), les
exposants doivent être pris modulo ϕ(M).
Effectuer les réduction modulaires au fur et à mesure.
7/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Fonctions à sens unique
8/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Fonctions à sens unique
Principe
Pour une relation y = f (x), calculer y est facile, et retrouver x à
partir de y est difficile sans une "trappe".
Question
Comment construire telles fonctions ?
9/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Factorisation des entiers
Factorisation
(p, q) → p · q facile
n = p · q → (p, q) difficile
10/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Arithmétique modulaire
Rappels
• Exponentiation modulaire
Chiffrement à clé publique
• Factorisation des entiers
Méthodes connues = exponentielles
Algorithmes de factorisation
√
Divisions successives → O( n)
Algorithme de Fermat : trouver n = a2 − b 2 → O(n1/3 )
cas facil : p − q petit
Méthode de Gauss : trouver des résidus quadratiques mod n
cas facil : ϕ(n) connu
Algorithme p − 1 de Pollard → O(p log(p))
cas facil : p − 1 et q − 1 ont des petits facteurs premiers
Algorithme Williams
cas facil : p + 1 et q + 1 ont des petits facteurs premiers
Algorithmes sous-exponentiels
crible quadratique, courbes elliptiques, crible algébrique
11/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Chiffrement à clé publique
12/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Chiffrement à clé publique
Protocole
• Algorithme de génération des clés KG(`) = (pk, sk)
à partir d’un paramètre de sécurité, il produit une paire de clés
• Algorithme de chiffrement E(pk, m) = c
produit le chiffré d’un message m, par la clé publique
• Algorithme de déchiffrement D(sk, c) = m
utilise la clé sécrete/privée sk pour retrouver m à partir de c
13/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Protocole RSA
RSA - Génération des clés
KG(`) = (pk, sk)
Soit n = p · q (p et q premiers)
L’ordre du groupe multiplicatif Z?n = ϕ(n) = (p − 1)(q − 1)
Soit e un entier premier avec ϕ(n) = (p − 1)(q − 1)
Soit d un entier qui satisfait d · e = 1 (mod ϕ(n))
d · e + uϕ(n) = 1 (Bézout)
clé publique clé secrète
n = pq : module public d = e−1 (mod ϕ(n))
e : exposant public les premiers p et q
14/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Protocole RSA
RSA - Chiffrement
E(pk = (e, n), M) = M e (mod n)
RSA - Déchiffrement
D(sk = d, C ) = C d (mod n)
Vérification
(M e )d = M ed = M 1−uϕ(n) = M · 1 = M (mod n)
(Théorème d’Euler)
15/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
RSA - Exemple simplifié
Deux petits premiers : p = 5 et q = 7
• n = 5 · 7 = 35, ϕ(n) = (5 − 1) · (7 − 1) = 24
• e et d : ed = 1 mod 24
• ed = 1 : Non, trop petit
• ed = 25 : Ok, mais e = d = 5 et alors clé privé = clé publique
• ed = 49 : Pareil, e = d
• ed = 73 : 73 est premier, raté
• ed = 97 : 97 est premier, raté
• ed = 121 : 11 au caré, encore raté
• ed = 165 : 165 = 5 * 33, et 5 est premier : Ok
• Clé publique = (RSA, 35, 5) • Clé privée = (RSA, 33).
16/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Conseils d’utilisation du RSA
RSA - Précautions
Il y a de nombreuses manières de mal utiliser RSA et d’ouvrir des
failles de sécurité !
Ne jamais utiliser de valeur n trop petite
Ne jamais utiliser d’exposant e trop petit
N’utiliser que des clés fortes
(p − 1 et q − 1 ont un grand facteur premier)
Ne pas chiffrer de blocs trop courts
Ne pas utiliser de n communs à plusieurs clés
17/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Attaques RSA
RSA - Attaques mathématiques
factoriser n = pq et par conséquent trouver ϕ(n)
et puis d
déterminer ϕ(n) directement et trouver d
trouver d directement (si petit)
attaques "broadcast"
attaques sur modulo n commun
attaques de synchronisation
(sur le fonctionnement du déchiffrement)
18/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Efficacité de RSA
RSA - coût
Le coût est celui d’une exponentiation modulaire :
Chiffrement : E(pk = (e, n), M) = M e (mod n)
3|e|/2 multiplications
si |n| = |e| coût total 1.5 log3 n
Déchiffrement : D(sk = d, C ) = C d (mod n)
3|p|/2 multiplications mod p + 3|q|/2 multiplications mod q
≈ 3|p| multiplications mod p
≈ 3|n|/8 multiplications mod p
19/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Propriétés du chiffrement
RSA = Homomorphisme
Le chiffré d’un produit M1 M2 est égal au produit des chiffrés
C1 = M1e (mod n) C1 C2 = M1e M2e = (M1 M2 )e
C2 = M2e (mod n)
Intéressant pour certains scénarios
Mais aussi nuisible à la sécurité ...
Attaque à chiffré choisi
1 Soit C = M e un message chiffré
2 On fabrique C 0 = Ae M e le chiffré du message A · M
3 Le déchiffrement de C 0 fournit celui de C
20/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Propriétés du chiffrement
RSA = Déterministe
Chiffrement déterministe = si l’on chiffre plusieurs fois le même
message, on obtient le même chiffré
Méthodes pour éviter le chiffrement par substitution :
couper le message en grands blocs
modifier la taille de blocs à chaque fois
randomiser le chiffrement RSA
21/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Sécurité de RSA
RSA - Sécurité
RSA est considéré sécure :
impossible à déchiffrer sans connaitre l’exposant d de la clé
secrète
trouver la clé secrète d est equivalent à factoriser n = pq
pas d’algorithme polynomial en temps en fonction de la taille
des données (la taille des nombres n et e) pour factoriser n
meilleur algorithme connu est sous-exponentiel (crible
algébrique) : 1/3 2/3
O e 1.92(ln n) (ln ln n)
22/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Sécurité de RSA
RSA - Sécurité
Pour évaluer et tester la sécurité du RSA :
évaluer la rapidité des algorithmes de factorisations de grands
nombres entiers
démontrer que la clef secrète de déchiffrement d ne peut pas
être obtenue sans factoriser n = pq
montrer que on ne peut pas déchiffrer un message sans la clé
secrète d
23/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Problèmes difficiles
Factorisation
(p, q) → p · q facile
n = p · q → (p, q) difficile
1/3 2/3
Meilleur algorithme (crible algébrique) : O e 1.92(ln n) (ln ln n)
Fonction RSA
Extraction de racine e-ième
x → xe mod n facile
y= xe → x mod n difficile
avec la trappe d = e−1 (mod ϕ(n)) :
24/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Problèmes difficiles
Factorisation
(p, q) → p · q facile
n = p · q → (p, q) difficile
1/3 2/3
Meilleur algorithme (crible algébrique) : O e 1.92(ln n) (ln ln n)
Fonction RSA
Extraction de racine e-ième
x → xe mod n facile
y= xe → x mod n difficile
avec la trappe d = e−1 (mod ϕ(n)) : x = y d = x ed = x mod n
24/25 Anca Nitulescu [email protected] Introduction à la cryptographie
• Protocole RSA
Rappels
• Attaques sur RSA
Chiffrement à clé publique
• Sécurité
Difficulté de RSA
Réduction
Si on connaît la factorisation, on casse RSA :
RSA se réduit à la factorisation !
Le contraire est peut-être faux !
calculer des racines e-ièmes sans factoriser ? ? ?
En pratique
La factorisation est la seule méthode connue pour casser RSA.
25/25 Anca Nitulescu [email protected] Introduction à la cryptographie
