Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
233 personne(s) sur le site en ce moment
E. Cartan

Les maths pour l'agreg

A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Cryptographie à clé révélée: RSA next up previous index
suivant: Index monter: Quelques résultats supplémentaires d'arithmétique précédent: Fractions continues   Index


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 $ M$ crypté à un individu $ I$, il suffit de passer le message $ M$ par la moulinette de la clé correspondante à $ I$. Cela n'est pas difficile, puisque $ I$ diffuse abondamment sa clé, à tous ses correspondants éventuels. Lorsque $ I$ 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 $ \mathbb{N}$, 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 $ A$ envoie un message à $ B$:

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

- $ B$ fournit à $ A$ une liste $ L$ de $ 1000$ chiffres 0 ou $ 1$, 0 et $ 1$ é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 $ 1000$ chiffres à chaque nouvel essai.

- $ A$ transforme le message $ M$ en un message $ M'$, par $ M'=M+L$ dans $ \mathbb{Z}/2\mathbb{Z}$.

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

- $ B$ décode $ M'$ par $ M=M'+L$ dans $ \mathbb{Z}/2\mathbb{Z}$.

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

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 $ A$ souhaite envoyer des messages cryptés RSA à $ B$. Alors $ B$ se donne deux grands nombres premiers $ p$ et $ q$. 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 $ p$ et $ q$. La première partie de la clé publique, notée $ c$, sera le produit de $ p$ et $ q$. $ A$ choisit alors un nombre $ d$, premier avec $ \phi(c)=(p-1)(q-1)$, avec $ \phi$ la fonction d'Euler, c'est-à-dire le nombre de nombres premiers plus petits que $ c$, donc $ (p-1)(q-1)$. 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 $ d^{-1}$, inverse de $ d$ dans $ (\mathbb{Z}/c\mathbb{Z})^*\simeq \mathbb{Z}/\phi(c)\mathbb{Z}$ (il y a isomorphisme car $ (\mathbb{Z}/c\mathbb{Z})^* \simeq (\mathbb{Z}/p\mathbb{Z})^* \times (\mathbb{Z}/q\mathbb{Z})^*$ par le corollaire [*] et isomorphisme entre $ (\mathbb{Z}/p\mathbb{Z})^*$ et $ \mathbb{Z}/(p-1)\mathbb{Z}$ (resp. $ (\mathbb{Z}/q\mathbb{Z})^*$ et $ \mathbb{Z}/(q-1)\mathbb{Z}$) 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 $ \mathbb{Z}/c\mathbb{Z}$, ce qui est possible en remplaçant le message par des tranches successives suffisamment petites (si on a un alphabet de taille $ \alpha$, il suffit de prendre des tranches de longueur $ l$ avec $ \alpha^l<\phi(c)$). Cette méthode de codage n'a pas à être compliquée ni à être cachée. Il suffit donc d'avoir une injection de $ [1,\alpha^l]$ dans $ (\mathbb{Z}/c\mathbb{Z})^*$.

- chaque message de $ A$ est donc remplacé (par $ A$) par un élément $ n$ inversible dans $ \mathbb{Z}/c\mathbb{Z}$.

- $ A$ envoie alors à $ B$ le nombre $ e=n^d$ dans $ \mathbb{Z}/c\mathbb{Z}$.

Décryptage:

- $ B$, qui dispose de $ d$ et de $ d^{-1}$, effectue simplement le calcul de $ e^{d^{-1}}$, qui lui donne $ n$, et donc le message initial.

D'autres systèmes de cryptographie à clé publique font intervenir des structures plus complexes que $ \mathbb{Z}/n\mathbb{Z}$, comme par exemple les courbes elliptiques.


next up previous index
suivant: Index monter: Quelques résultats supplémentaires d'arithmétique précédent: Fractions continues   Index
C_Antonini,J_F_Quint,P_Borgnat,J_Bérard,E_Lebeau,E_Souche,A_Chateau,O_Teytaud
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page