Rappels mathématiques
Protocole RSA
Cryptosystème RSA
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Primalité
Définition
Un nombre p est premier si ses seuls diviseurs positifs sont p et 1.
Liste : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . .
23/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Primalité
Définition
Un nombre p est premier si ses seuls diviseurs positifs sont p et 1.
Liste : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, . . .
Propriétés
Entre n et 2n, il y a toujours un nombre premier.
Un nombre pair est toujours la somme de 2 premiers.
Un nombre impair (>5) est la somme de 3 premiers.
Théorème d’Euclide
Il existe une infinité de nombres premiers.
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Décomposition en facteurs prémiers
Théorème fondamental de l’arithmétique
Tout entier n s’écrit de façon unique comme produit de puissances
de nombres premiers : k
Y
n= piαi
i=1
PGCD
piαi et b = piβi , alors :
Q Q
Si a = i i
Y min(α ,β )
i i
pgcd(a, b) = pi
i
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Distribution des nombres premiers
Question
Il existe une infinité de
nombres premiers.
(Euclide)
Comment sont-ils
répartis ? ? ?
25/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Fonction d’Euler
Définition
ϕ(n) est le nombre d’entiers de [1, n] qui sont premiers avec n.
44/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Fonction d’Euler
Définition
ϕ(n) est le nombre d’entiers de [1, n] qui sont premiers avec n.
Propriétés
si p est premier et q premier :
ϕ(p) = p − 1
ϕ(p e ) = p e−1 (p − 1) = p e − p e−1
ϕ(pq) = ϕ(p)ϕ(q) si pgcd(p , q ) = 1
44/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Fonction d’Euler
Calcul de ϕ(n)
k
piαi :
Q
Formule générale pour n =
i
k k
piαi −1 αi −1
Y Y
ϕ(n) = piαi − = pi pi− 1
i=1 i=1
45/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Théorème des restes chinois
Problème
Pour p et q premiers et a et b entiers on cherche x tel que :
x =a mod p et x =b mod q
49/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Primalité
Algorithmes pour la crypto • Arithmétique modulaire
Rappels mathématiques • Exponentiation modulaire
Protocole RSA • Théorème des restes chinois
Théorème des restes chinois
Problème
Pour p et q premiers et a et b entiers on cherche x tel que :
x =a mod p et x =b mod q
Théorème CRT (Chinese Remainder Theorem)
La solution x est unique modulo pq et se calcule par l’algorithme
de Gauss :
x = aq(q −1 mod p) + bp(p −1 mod q) mod pq
Resoudre
x = 9 mod 17 et x = 3 mod 5
49/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
Fonctions à sens unique
multiplication ↔ factorisation
(p, q) → p · q facile ↔ n = p · q → (p, q) difficile
Meilleur algorithme connu (crible algébrique) :
1/3 2/3
O e 1.92(ln n) (ln ln n)
51/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
Chiffrement à clé publique
52/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
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
53/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
Protocole RSA
RSA - Génération des clés
KG(`) = (pk, sk)
Soit n = p · q (p et q premiers)
ϕ(n) = (p − 1)(q − 1)
Soit e un entier premier avec ϕ(n)
Soit d un entier qui satisfait d · e = 1 (mod ϕ(n))
54/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
Protocole RSA
RSA - Génération des clés
KG(`) = (pk, sk)
Soit n = p · q (p et q premiers)
ϕ(n) = (p − 1)(q − 1)
Soit e un entier premier avec ϕ(n)
Soit d un entier qui satisfait d · e = 1 (mod ϕ(n))
clé publique clé secrète
n = pq : module public d = e−1 (mod ϕ(n))
e : exposant public les premiers p et q
54/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
RSA - Exemple simplifié
Deux petits premiers : p = 5 et q = 7
56/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
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é
• eed = 121 : 11 au caré, encore raté
• ed = 165: 165 = 5 * 33, et 5 est premier : Ok
• Clé publique = ( n , 5 ) • Clé privée = ( 33, p , q ).
56/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
RSA-Chiffrement-Dechiffrement
Configuration
1 On choisit deux entiers premiers assez grands p et q, calculer
n = pq et φ(n) = (p − 1)(q − 1)
2 choisir e (clé de cryptage) tel que pgcd(e, φ(n)) = 1
3 calculer d (clé de déchiffrement) tel que e.d ≡ 1(modφ(n))
4 rendre n et e publique, et garde d,p,q secrets
Chiffrement -Dechifrement
1 récupérer n et e de destinataire
2 chiffre un message m en calculant c ≡ me (mod n)
3 à la reception on déchiffre en calculant m ≡ c d (mod n)
56/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA • Exemple
RSA-Chiffrement-Dechiffrement
56/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA
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
57/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
Algorithmique • Fonctions à sens unique
Algorithmes pour la crypto • Chiffrement à clé publique
Rappels mathématiques • Protocole RSA
Protocole RSA
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
.....
58/58 Anca Nitulescu [Link]@[Link] Introduction à la cryptographie
