Principe de fonctionnement du cryptage RSA

50 %
50 %
Information about Principe de fonctionnement du cryptage RSA
Technology

Published on February 5, 2014

Author: KristenLeLiboux

Source: slideshare.net

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.

« 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 Transport avec espions ?

L’échange sécurisé symétrique Emetteur Destinataire

L’échange sécurisé symétrique Emetteur E E Destinataire

L’échange sécurisé symétrique Emetteur Destinataire E E E

L’échange sécurisé symétrique Emetteur Destinataire E E E D D

L’échange sécurisé symétrique Emetteur Destinataire E E E E D D D

L’échange sécurisé symétrique Emetteur Destinataire E E E D D D

L’échange sécurisé symétrique Emetteur Destinataire E E E D D D D

L’échange sécurisé symétrique Emetteur Destinataire E E E D D D

L’échange sécurisé asymétrique Emetteur Destinataire D

L’échange sécurisé asymétrique Emetteur Destinataire D D

L’échange sécurisé asymétrique Emetteur D Destinataire D D

L’échange sécurisé asymétrique Emetteur Destinataire D D D D

L’échange sécurisé asymétrique Emetteur Destinataire D D D D D

L’échange sécurisé asymétrique Emetteur Destinataire D D D D

La cryptographie Message à crypter Encodage en nombre Stopper tous les réacteurs ! 192015161605180020... Message M Objectif : transformer M, et pouvoir revenir à M par deux opérations mathématiques

Quelle opération ? Message à crypter Encodage en nombre Stopper tous les réacteurs ! 192015161605180020... M x 13 24961957665925534150... M / 13 192015161605180020...

Quelle opération ? Message secret M 192015161605180020... M x 13 24961957665925534150... M / 13 192015161605180020... Problème : clé identique pour cryptage et décryptage la clé doit voyager avec le message...

Puissance modulo Une nouvelle opération mathématique simple. Puissance : M5 = M x M x M x M x M

Puissance modulo Une nouvelle opération mathématique simple. Puissance : M5 = M x M x M x M x M 32 chiffres

Puissance modulo Une nouvelle opération mathématique simple. Puissance : Problème : M5 = M x M x M x M x M 32 chiffres 160 chiffres La multiplication est une opération qui provoque des débordements

Puissance modulo Une 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 : 0 35 70 82 105 140 ... infini Les nombres modulo 35 (par exemple) se représentent sur une « échelle » : ... 0 12 34

Puissance modulo Une 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 : 34 M5 [35] = la réduction de M5 modulo 35

Exemple Une nouvelle opération mathématique simple. Un exemple : 85 [35] = 32768 [35] = 29 0 ... 29 34

Crypter le message M =12871 Calcul des puissances du message modulo N M2 Très rapide sur un PC M3 Prenons N=89077 par exemple, et M=12871 (le message secret), et calculons les puissances de M modulo N. M4 0 ... 89077

Retomber sur ses pieds M =12871 Calcul des puissances du message modulo N Il existe des puissances particulières, complémentaires, qui permettent de retomber sur ses pieds M17 = C C193 ... 0 12871 68018 89077

Retomber sur ses pieds M =12871 Message original Message crypté M17 = C Message décrypté Paramètres fixes (clés) C193 ... 0 12871 68018 89077

Retomber sur ses pieds M =12871 Sur les paramètres : • Nécessaire pour crypter M17 = C • Nécessaire pour décrypter • Nécessaire pour les deux C193 ... 0 12871 68018 89077

Contraintes mathématiques M =12871 Cela marche bien avec les paramètres 17, 193, 89077. M17 = C Mais pas avec n’importe quels autres. Comment trouver des paramètres qui marchent ? C193 ... 0 12871 68018 89077

Contraintes mathématiques Cela marche bien avec les paramètres 17, 193, 89077. Il y a des liens entre ces valeurs.

Contraintes mathématiques Cela marche bien avec les paramètres 17, 193, 89077. Il y a des liens entre ces valeurs. 89077 = 41 x 83

Contraintes mathématiques Cela marche bien avec les paramètres 17, 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ètres 17, 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ètres 17, 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ètres 17, 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ètres 17, 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ètres 17, 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ètres 17, 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 : La démonstration repose sur le petit théorème de Fermat (1640) et le théorème d’Euler (1761) 17 x 193 = 3281 Différence de 1 => OK

Contraintes mathématiques Rappel : 89077 = 41 x 83 • Nécessaire pour On enlève 1 : crypter • Nécessaire pour décrypter : SECRET! • Nécessaire pour les deux 40 x 82 = 3280 Or : 17 x 193 = 3281 Différence de 1 => OK

Point fondamental Si on est capable d’écrire ce nombre sous la forme d’un produit, alors on peut en déduire la clé privée. 89077 = 41 x 83

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ?

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 =

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 99 =

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 99 = 11 x 9

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 99 = 11 x 9 247 =

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 99 = 11 x 9 247 = 13 x 19

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 99 = 11 x 9 247 = 13 x 19 89077 =

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 99 = 11 x 9 247 = 13 x 19 89077 = 41 x 83

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 89077 = 41 x 83 99 = 11 x 9 437669 = 247 = 13 x 19

Point fondamental Est-ce facile d’écrire un nombre comme produit de deux autres nombres ? 35 = 7x5 89077 = 41 x 83 99 = 11 x 9 437669 = 541 x 809 247 = 13 x 19

Point fondamental 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 35 = 7x5 89077 = 41 x 83 99 = 11 x 9 437669 = 541 x 809 247 = 13 x 19

Point fondamental

Point fondamental 1230186684530117755130494958384962720772853 56959533479219732245215172640050726 3657518745202199786469389956474942774063845 92519255732630345373154826850791702 6122142913461670429214311602221240479274737 794080665351419597459856902143413

Point fondamental 1230186684530117755130494958384962720772853 56959533479219732245215172640050726 3657518745202199786469389956474942774063845 92519255732630345373154826850791702 6122142913461670429214311602221240479274737 794080665351419597459856902143413 =

Point fondamental 1230186684530117755130494958384962720772853 56959533479219732245215172640050726 3657518745202199786469389956474942774063845 92519255732630345373154826850791702 6122142913461670429214311602221240479274737 794080665351419597459856902143413 = ?

Point fondamental 1230186684530117755130494958384962720772853 56959533479219732245215172640050726 3657518745202199786469389956474942774063845 92519255732630345373154826850791702 6122142913461670429214311602221240479274737 794080665351419597459856902143413 = ? 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 pas intrinsè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 RSA Adi 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 :-)

Add a comment

Related presentations

Presentación que realice en el Evento Nacional de Gobierno Abierto, realizado los ...

In this presentation we will describe our experience developing with a highly dyna...

Presentation to the LITA Forum 7th November 2014 Albuquerque, NM

Un recorrido por los cambios que nos generará el wearabletech en el futuro

Um paralelo entre as novidades & mercado em Wearable Computing e Tecnologias Assis...

Microsoft finally joins the smartwatch and fitness tracker game by introducing the...

Related pages

Algorithme de chiffrement RSA - Comment Ça Marche

RSA, du nom de ces inventeurs, ... cet article énonce le principe de base de l'algorithme publié en 1978. Pour une implémentation rigoureuse, ...
Read more

Chiffrement RSA — Wikipédia

Fonctionnement détaillé. Ronald ... ce qui fait le succès du RSA est qu'il n'existe ... tous les algorithmes de chiffrement fondés sur ce principe ...
Read more

La cryptographie à clé publique - Principe de fonctionnement

... Principe de fonctionnement ... tout du moins en comparaison des moyens que l'on peut déployer à cette date pour les vaincre. ... (RSA, …) et la ...
Read more

Cryptographie asymétrique — Wikipédia

Fonctionnement Principe général La cryptographie asymétrique, ou cryptographie à clef ... par exemple dans le cas du RSA, ...
Read more

Système RSA - cryptage.org

Le RSA Le principe. Le premier système à clé publique solide à avoir été inventé, et le plus utilisé actuellement, ... la mise en oeuvre du RSA.
Read more

Cryptage RSA en C++ - linor.fr

Utilisation de la biblioth?que de cryptage RSA en ... Principe de fonctionnement. ... Limitations en taille du message L'algorithme de cryptage RSA n'est ...
Read more

cryptographie RSA : principe de fonctionnement, exercice ...

cryptographie RSA : principe de fonctionnement, ... c'est la deuxieme partie que j'ai du mal : ... cryptage : x est crypté par C ...
Read more

Principe du Cryptage PGP - laurent.flaum.free.fr

Fonctionnement du cryptage PGP. ... qu'il soit RSA, ... PGP part du principe que si vous possédez la clé privée, ...
Read more

CryptAGE, tout sur la cryptographie

Accueil. Bienvenue sur CryptAGE, l'âge de la crypte ...ographie Contenu. Ce site contient à la base mon travail de fin d'études sur la cryptographie.
Read more