Cryptographie à clé révélée: RSA

Précisons que l'on parle aussi de clé publique .

L'objectif de la cryptographie est de permettre de communiquer par des messages codés, qui ne pourront être lus que par leur destinataire.

Pour cela, un "superviseur" donne à chaque receveur potentiel un "décodeur" et une "clé". La clé, comme son nom ne l'indique peut-être pas, est quelque chose qui peut être diffusé à tout le monde.

Pour envoyer un message crypté à un individu , il suffit de passer le message par la moulinette de la clé correspondante à . Cela n'est pas difficile, puisque diffuse abondamment sa clé, à tous ses correspondants éventuels. Lorsque reçoit un message, il peut alors utiliser son décodeur, qu'il est seul à posséder, pour transformer le message crypté en le message original.

La difficulté est que, formellement, il est toujours possible de reconstruire le message initial à partir du message crypté, pourvu que vous ayez la clé. Pour cela, il suffit de tester tous les messages possibles, l'un après l'autre (ils sont bien en bijection avec , comme on peut s'en convaincre facilement en considérant l'ordre lexicographique sur les messages possibles), et de les passer par la moulinette de la clé jusqu'à ce que l'on retrouve le message crypté. Mais il reste un espoir de fabriquer une cryptographie efficace, car bien sûr, cette méthode prendrait un temps énorme. La cryptographie est ainsi basée sur l'hypothèse de base que certaines tâches, faciles à faire dans un sens (le sens du cryptage par une clé), est difficile à faire dans l'autre (décryptage à l'aide d'une clé).

On note bien que la difficulté réside dans le fait que la fonction "clé" est publique. Si on cache la clé, il est très facile de réaliser des cryptographies parfaites. Par exemple, on peut utiliser le protocole suivant pour que envoie un message à :

- signale à qu'il veut lui envoyer un message, que l'on supposera constitué uniquement de 0 et de (par un codage quelconque on peut facilement se ramener à cela), et de longueur .

- fournit à une liste de chiffres 0 ou , 0 et étant équiprobables.

- le protocole recommence à l'étape précédente jusqu'à ce que la liste de chiffres soit passée sans être interceptée; on tire au sort une nouvelle liste de chiffres à chaque nouvel essai.

- transforme le message en un message , par dans .

- envoit à ; si est intercepté, il ne sera pas décodable, puisque n'est pas connu.

- décode par dans .

Aucune interception ne permet de décoder le message; mais les étapes et peuvent prendre du temps ou n'être pas réalisables. Il est indispensable de changer de liste à chaque nouveau message, ou du moins régulièrement - sinon, en considérant les fréquences des 0 et des , un observateur des différents pourrait finir par reconstituer .

L'algorithme RSA, du nom de ses inventeurs, Rivest, Shamir et Adleman, est basé sur la difficulté de la factorisation d'un nombre entier en nombres premiers.

Supposons que souhaite envoyer des messages cryptés RSA à . Alors se donne deux grands nombres premiers et . Maple permet aisément de construire de tels nombres, par exemple; il suffit par exemple de tirer des nombres au sort et de recommencer jusqu'à ce qu'ils soient premiers, grâce à un algorithme permettant de dire si oui ou non un nombre est premier. En fait les algorithmes utilisés pour cela sont généralement probabilistes, c'est-à-dire qu'ils ont une probabilité non nulle de se tromper; mais les erreurs sont extrêmement rares. La fonction Maple "isprime" permet de tester la primalité d'un nombre; par exemple, "isprime(123456789012345678901234567)" renvoit "false", donc "123456789012345678901234567" n'est pas premier.
"nextprime(123456789012345678901234567)" renvoit
"123456789012345678901234651", qui est donc le nombre premier le plus petit plus grand que celui-ci. On constate donc que Maple permet très rapidement de trouver de grands nombres premiers; les exemples ici fournis ne sont pas du tout à la limite du faisable, on peut aller largement au delà.

Ces deux nombres premiers seront notés et . La première partie de la clé publique, notée , sera le produit de et . choisit alors un nombre , premier avec , avec la fonction d'Euler, c'est-à-dire le nombre de nombres premiers plus petits que , donc . Il est facile de choisir un nombre qui soit premier avec un autre: il suffit d'en piocher un au hasard, et de recommencer jusqu'à ce que l'algorithme de Bezout confirme que ces nombres sont premiers entre eux. On peut aussi déterminer facilement , inverse de dans (il y a isomorphisme car par le corollaire et isomorphisme entre et (resp. et ) par le lemme ): il suffit d'utiliser l'algorithme de Bezout.

Cryptage:

- On suppose le message suffisamment court pour être codable par un élément inversible de , ce qui est possible en remplaçant le message par des tranches successives suffisamment petites (si on a un alphabet de taille , il suffit de prendre des tranches de longueur avec ). Cette méthode de codage n'a pas à être compliquée ni à être cachée. Il suffit donc d'avoir une injection de dans .

- chaque message de est donc remplacé (par ) par un élément inversible dans .

- envoie alors à le nombre dans .

Décryptage:

- , qui dispose de et de , effectue simplement le calcul de , qui lui donne , et donc le message initial.

D'autres systèmes de cryptographie à clé publique font intervenir des structures plus complexes que , comme par exemple les courbes elliptiques.