RSA

« L’algorithme RSA Maya Godon MPSI A Introduction R ivest S hamir A dleman Introduction Idée : Trouver deux fonctions f et g sur les entiers, telles que : • f ◦ g = Id • l’on ne puisse pas trouver f (fonction de décryptage) à partir de g (clé) Introduction Idée : Trouver deux fonctions f et g sur les entiers, telles que : • f ◦ g = Id • l’on ne puisse pas trouver f (fonction de décryptage) à partir de g (clé) ⇒ Cela permet de crypter le message sans savoir comment decrypter Introduction Idée : Trouver deux fonctions f et g sur les entiers, telles que : • f ◦ g = Id • l’on ne puisse pas trouver f (fonction de décryptage) à partir de g (clé) ⇒ Cela permet de crypter le message sans savoir comment decrypter But : Pouvoir transmettre un message codé a partir d’une clé publique, seulement décryptable par le récepteur officiel, donc impossible par quelqu’un d’autre que celui qui a la clé privée Protocole Alice – destinatrice du message Bernard – l’emetteur 1) Alice crée ses clés : une privée, qu’elle gardera pour elle-même, une publique, qu’elle transmettra à Bernard. Protocole Alice – destinatrice du message Bernard – l’emetteur 1) Alice crée ses clés : une privée, qu’elle gardera pour elle-même, une publique, qu’elle transmettra à Bernard. 2) Bernard crypte son message à partir de la clé publique fournie par Alice Protocole Alice – destinatrice du message Bernard – l’emetteur 1) Alice crée ses clés : une privée, qu’elle gardera pour elle-même, une publique, qu’elle transmettra à Bernard. 2) Bernard crypte son message à partir de la clé publique fournie par Alice 3) Alice décrypte le message secret de Bernard avec sa clé privée Protocole 1) Alice crée ses clés en suivant le protocole suivant : · · · · · générer deux gros nombres entiers p et q calculer w = (p - 1)(q - 1) générer d tel que d ∧ w = 1 calculer n = p × q calculer e tel que d × e ≡ 1 [w] Protocole 1) Alice crée ses clés en suivant le protocole suivant : · · · · · générer deux gros nombres entiers p et q calculer w = (p - 1)(q - 1) générer d tel que d ∧ w = 1 calculer n = p × q calculer e tel que d × e ≡ 1 [w] Clé privée d Clé publique n et e Protocole 1) Alice crée ses clés en suivant le protocole suivant : · · · · · générer deux gros nombres entiers p et q calculer w = (p - 1)(q - 1) générer d tel que d ∧ w = 1 calculer n = p × q calculer e tel que d × e ≡ 1 [w] Clé privée d · oublier w, p et q Clé publique n et e Protocole 2) Bernard crypte son message à partir de la clé publique fournie par Alice · crypter un message M par M ⟼ M e [n].... »