Embed Size (px)
DESCRIPTION
Le cryptage RSA est-il intrinsèquement inviolable ? Pour le savoir, nous essayons de comprendre comment il fonctionne et sur quelles mathématiques il s'appuie.
Citation preview
« Le pédant tient plus à nous instruire de ce qu'il sait que de ce que nous ignorons. »
JOHN PETIT-SENN
DOIT-ON FAIRE CONFIANCE AU
CRYPTAGE ?
Introduction
Cryptage RSA
• Rivest Shamir Adleman 1977, 1983, 2000
• A la base des communications sécurisées
• Système de « clés » (nombres secrets)
• Logiciel PGP (Zimmermann, 1991)(Pretty Good Privacy)
Fiable, vraiment ?
Si personne ne connaît votre clé à part vous, vos informations sont-elles à l’abri ?
• NSA : poursuites abandonnées contre PGP (1996), sans donner de raison !
• Algorithme de Shor (1994) :RSA cassé sur ordinateur quantique !
Comment est-ce possible ?
L’échange sécurisé
Emetteur Destinataire
Transportavec espions
?
L’échange sécurisé symétrique
Emetteur Destinataire
L’échange sécurisé symétrique
Emetteur Destinataire
E
E
L’échange sécurisé symétrique
Emetteur Destinataire
E
E
E
L’échange sécurisé symétrique
Emetteur Destinataire
E
DD
E
E
L’échange sécurisé symétrique
Emetteur Destinataire
E
DD
E
E
D
E
L’échange sécurisé symétrique
Emetteur Destinataire
E
DD
E
E
D
L’échange sécurisé symétrique
Emetteur Destinataire
E
DD
E
E
D
D
L’échange sécurisé symétrique
Emetteur Destinataire
E
DD
E
E
D
L’échange sécurisé asymétrique
Emetteur Destinataire
D
L’échange sécurisé asymétrique
Emetteur Destinataire
DD
L’échange sécurisé asymétrique
Emetteur Destinataire
DD
D
L’échange sécurisé asymétrique
Emetteur Destinataire
DD
D
D
L’échange sécurisé asymétrique
Emetteur Destinataire
DD
D
D
D
L’échange sécurisé asymétrique
Emetteur Destinataire
DD
D
D
La cryptographie
Message à crypter
Encodage en nombre
Stopper tous les réacteurs !
192015161605180020...
Message M
Objectif : transformer M, et pouvoir revenir à Mpar deux opérations mathématiques
Quelle opération ?
Message à crypter
Encodage en nombre
Stopper tous les réacteurs !
192015161605180020...
M x 13
M / 13
24961957665925534150...
192015161605180020...
Quelle opération ?
Message secret M 192015161605180020...
M x 13
M / 13
24961957665925534150...
192015161605180020...
Problème : clé identique pour cryptage et décryptagela clé doit voyager avec le message...
Puissance moduloUne nouvelle opération mathématique simple.
Puissance : M5 = M x M x M x M x M
Puissance modulo
32 chiffres
Une nouvelle opération mathématique simple.
Puissance : M5 = M x M x M x M x M
Puissance modulo
32 chiffres 160 chiffres
La multiplication est une opérationqui provoque des débordements
Une nouvelle opération mathématique simple.
Puissance :
Problème :
M5 = M x M x M x M x M
Puissance moduloUne nouvelle opération mathématique simple.
Puissance : M5 = M x M x M x M x M
Les nombres classiques se représentent sur une ligne :
Les nombres modulo 35 (par exemple)se représentent sur une « échelle » :
0 35 70 105 140 ... infini
0...
82
12 34
Puissance moduloUne nouvelle opération mathématique simple.
Puissance : M5 = M x M x M x M x M
Les nombres modulo 35 :
0...
12
Puissance modulo 35 : M5 [35] = la réduction de M5
modulo 35
34
ExempleUne nouvelle opération mathématique simple.
Un exemple : 85 [35] = 32768 [35] = 29
0...29 34
Crypter le message
Calcul des puissances du message modulo N
Très rapide sur un PC
Prenons N=89077 par exemple, et M=12871 (le message secret), et calculons les puissances de M modulo N.
...
0 89077
M =12871
M2
M3
M4
Retomber sur ses pieds
Calcul des puissances du message modulo N
Il existe des puissances particulières, complémentaires,qui permettent de retomber sur ses pieds
...
0 89077
M =12871
M17 = C
C193
12871 68018
Retomber sur ses pieds
Message original
Message crypté
Message décrypté
Paramètres fixes (clés)
...
0 89077
M =12871
M17 = C
C193
12871 68018
Retomber sur ses pieds
Sur les paramètres :
• Nécessaire pour crypter
• Nécessaire pour décrypter
• Nécessaire pour les deux
...
0 89077
M =12871
M17 = C
C193
12871 68018
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Mais pas avec n’importe quels autres.
Comment trouver des paramètres qui marchent ? ...
0 89077
M =12871
M17 = C
C193
12871 68018
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
On enlève 1 :
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
On enlève 1 :
40 x 82 = 3280
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
On enlève 1 :
40 x 82 = 3280
Or :
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
On enlève 1 :
40 x 82 = 3280
Or :
17 x 193 = 3281
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
On enlève 1 :
40 x 82 = 3280
Or :
17 x 193 = 3281
Différence de 1 => OK
Contraintes mathématiques
Cela marche bien avec les paramètres17, 193, 89077.
Il y a des liens entre ces valeurs.
89077 = 41 x 83
41 et 83 sont des nombres premiers.
On enlève 1 :
40 x 82 = 3280
Or :
17 x 193 = 3281
Différence de 1 => OKLa démonstration repose sur le petit théorème de Fermat (1640) et le théorème d’Euler (1761)
Contraintes mathématiques
89077 = 41 x 83
On enlève 1 :
40 x 82 = 3280
Or :
17 x 193 = 3281
Différence de 1 => OK
Rappel :
• Nécessaire pour crypter
• Nécessaire pour décrypter : SECRET!
• Nécessaire pour les deux
Point fondamental
89077 = 41 x 83Si on est capable d’écrire ce nombre sous la forme d’un produit, alors on peut en déduire la clé privée.
Point fondamental
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =13 x 19
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =13 x 19
89077 = Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =13 x 19
89077 = 41 x 83
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =13 x 19
89077 = 41 x 83
437669 =
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =13 x 19
89077 = 41 x 83
437669 =541 x 809
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
Point fondamental
35 = 7 x 5
99 =11 x 9
247 =13 x 19
89077 = 41 x 83
437669 =541 x 809
Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?
On peut le faire par « force brute », mais on ne connait quasiment pas d’autre méthode
Point fondamental
Point fondamental
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
Point fondamental
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
=
Point fondamental
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
= ?
Point fondamental
123018668453011775513049495838496272077285356959533479219732245215172640050726
365751874520219978646938995647494277406384592519255732630345373154826850791702
6122142913461670429214311602221240479274737794080665351419597459856902143413
= ?
Une clé de 232 chiffres cassée en 2010 [Kleinjung & al.]après 2 ans et demi de travail
Point fondamental
• Cette clé de 768 bits (232 chiffres) a été cassée en 2010 [Kleinjung & al.]
• En pratique les clés actuelles font 1024 bits (308 chiffres)
• Aucun algorithme connu efficace sur des clés aussi longues, temps de calcul estimé à plusieurs décennies
Conclusion
Conclusion
La sécurité du web repose sur une incapacité mathématique humaine (et une incapacité machine).
Conclusion
La sécurité du web repose sur une incapacité mathématique humaine (et une incapacité machine).
Ou plutôt, sur la croyance en cette incapacité.
Conclusion
La sécurité du web repose sur une incapacité mathématique humaine (et une incapacité machine).
Ou plutôt, sur la croyance en cette incapacité.
On sait ainsi pourquoi elle n’est pasintrinsèquement inviolable.
Points additionnels
Points additionnels
Un autre problème est lié à l’implémentation de l’algorithme : les bugs ou les insuffisances des logiciels qui utilisent cet algorithme peuvent être aisément exploitées.
Points additionnels
Un autre problème est lié à l’implémentation de l’algorithme : les bugs ou les insuffisances des logiciels qui utilisent cet algorithme peuvent être aisément exploitées.
Un exemple : en mesurant le temps de calcul pris par un ordinateur pour chiffrer un message, on peut en déduire les clés de chiffrement !
Points additionnels
Un autre problème est lié à l’implémentation de l’algorithme : les bugs ou les insuffisances des logiciels qui utilisent cet algorithme peuvent être aisément exploitées.
Un exemple : en mesurant le temps de calcul pris par un ordinateur pour chiffrer un message, on peut en déduire les clés de chiffrement !
Beaucoup d’autres attaques possibles...
En savoir plus
Sur l’histoire de la cryptographie :http://fr.wikipedia.org/wiki/Histoire_de_la_cryptographie
Sur RSA :http://fr.wikipedia.org/wiki/Chiffrement_RSA
Sur Adi Shamir et l’avenir de RSAAdi Shamir, sa majesté des codes (les Echos, 15/10/2012)
Avez-vous compris ?
Feedback apprécié :
• Kristen Le Liboux sur SlideShare
• @novlangue sur Twitter
MERCI :-)
