les dossiers de l’ afis44

DOSSIER : MATHEMATIQUES

document : la cryptographie sur Internet ( l’algorithme R S A )

la cryptographie sur internet ( système RSA )

introduction

Que de chemin parcouru depuis que le centre d’études et de recherches nucléaires a permis l’usage au public de son logiciel world wide web. Ce n’était qu’en 1993 … L’usage de la toile s’est répandu et les administrations ou les entreprises, tout comme les particuliers ont vite mesuré le côté pratique de pouvoir réaliser des opérations (achats de biens ou de services, paiements, virement bancaires, consultations de comptes, déclarations administratives diverses, etc.) « en ligne ».

L’opération « en ligne » elle-même n’est pas bien difficile ; la difficulté réside dans la sécurité de la transaction. En effet on se trouve ainsi face au problème classique de la transmission d’information que l’on veut confidentielle par un canal qui est peu sûr. C’est ce que nous évoquions dans l’introduction à la cryptographie que nous présentons sur ce site :

« La confidentialité du message proprement dite sera obtenue par l'opération de chiffrement à l'aide d'une "clef", chiffrement rendant le message a priori incompréhensible par quiconque aurait accès à ce message chiffré. Pour pouvoir restaurer le texte clair il faut utiliser la "clef" de déchiffrement.

Message	chiffrement		déchiffrement	Message
Clair	du message		du message	Clair
	Clef chiffrante	Transmission par canal peu sûr	Clef déchiffrante

Le tiers intéressé, le plus souvent avec des intentions inamicales, s'investira dans l'interception de la communication puis le décryptage ( c'est là l'objet des cryptanalystes ) du message. »

Ainsi, suivant le mode « classique », l’émetteur et le receveur conviennent d’une seule et même clef, servant à la fois de clef chiffrante et de clef déchiffrante. C’est ce qu’on appelle une « cryptographie à clef privée ».

D’un point de vue cryptographie il n’y a aucune difficulté. Par contre la transmission sûre par le destinataire de la clef à l’émetteur n’est pas chose aisée, surtout à grande échelle.

D’où l’idée d’utiliser plusieurs clefs : une ultra confidentielle qui ne quittera pas la banque (pour rester dans cet exemple) ; et une autre qui peut voyager sans difficulté car ne servirait en pratique à rien pour celui qui n’a pas la première. Cette deuxième clef peut être « publique ».

Evidemment, si ça marche, on imagine facilement que c’est plus pratique mais l’idée semble farfelue et présenter un vice logique : comment un chiffrement avec une clef publique pourrait-il assurer la confidentialité des informations ?

En 1977, trois mathématiciens (Ronald Rivest, Adi Shamir et Léonard Adleman) décidèrent de travailler ensemble pour prouver que la nouvelle technologie de cryptographie à clé publique est une impossibilité logique.

Ils ne réussirent pas …

et, au contraire, mirent au point un nouvel algorithme de cryptographie à clef publique qui supplanta le seul existant auparavant : c’est le RSA.

Ne restaient plus qu’à attendre que quelques améliorations de la technologie des ordinateurs et leur large diffusion dans le public pour que 25 ans après l’algorithme RSA devienne utilisé dans plus de 300 millions de programmes, dont le noyau de Windows, de Mac OS, les logiciels de messagerie électronique et de carte de crédit en France etc.

RSA : la succession des opérations

Cette présentation se veut une présentation de vulgarisation scientifique. Nous essaierons donc de ne poser que des assertions vraies (en glissant sur les démonstrations). Nous rencontrerons néanmoins des notions plus ou moins compliquées d’arithmétique. Quelques éclairages ou approfondissements seront disponibles au fil du texte si vous cliquez sur les liens jaunes. Pour revenir au texte il suffit d’utiliser le retour du navigateur. Néanmoins le texte devrait pouvoir se lire sans faire appel à (l’essentiel de) ces éléments additionnels. Des sites désormais multiples et souvent plus excellents les uns que les autres permettront d’approfondir pour ceux qui le souhaiteraient. quelques liens seront donnés.

Bob veut qu’Alice lui adresse un message confidentiel

Il y a deux clés: une de codage et une de décodage, dont l’une ne se déduit qu’extrêmement difficilement l’une de l’autre.

Appelons Bob celui qui souhaite recevoir un message, et Alice celle qui va le lui envoyer.

Bob crée les deux clefs: celle de codage et celle de décodage. Il garde pour lui la clef de décodage, et envoie la clef de codage à Alice. Alice code le message avec la clef publique et envoie le message codé à Bob, qui seul a la clef de décodage, et donc peut décoder.

Bob crée les deux clefs

Résumé : Bob va choisir deux nombres premiers qu’il gardera bien sûr secrets. A partir de ces deux nombres il va faire certaines opérations (que nous allons voir) qui vont lui donner trois nombres, deux qu’il va communiquer à Alice (ce sera la clef publique) et un qu’il gardera pour déchiffrer le message d’Alice (ce sera sa clef privée). Le degré de protection donné par le système proviendra de la difficulté pour un tiers malveillant de retrouver les deux nombres choisis initialement par Bob.

		Exemple chiffré
1	Bob choisit deux nombres premiers p et q distincts	Dans la pratique il est fait usage de grands nombres (au moins 100 chiffres chacun) mais le principe marche aussi avec des petits nombres et c’est plus facile à manipuler; choisissons donc p = 13 et q = 17
2	Il les multiplie entre eux ; cela donne le nombre n ( n = p x q). Ce nombre n fait partie des deux nombres constituant la clef publique.	n = 13 x 17 = 221
3	Il multiplie ensuite le prédécesseur de p par le prédécesseur de q. Nous appellerons ce nombre m m = (p-1) x (q-1) Ce nombre est en réalité j(n) qui est la valeur de l’indicateur PHI d’EULER pour le nombre n.	m = 12 x 16 = 192
4	Il choisit un nombre entier, que l’on appellera e, plus grand que 2, plus petit que m et premier avec lui.	choisissons par exemple e = 5 (dans l’exemple, tout nombre compris entre 2 et 192 qui n’aurait pas été divisible ni par 2 ni par 3 aurait fait l’affaire ; il y en a beaucoup)
5	Il choisit alors la clef de décodage d. Cette clef doit être telle que si on la multiplie par le nombre e que l’on vient de choisir et qu’on divise le résultat de cette multiplication par le nombre m, le reste de la division soit égal à 1 (en langage mathématique, le produit e x d doit être congru à 1 modulo m). On utilise, pour trouver d une technique dénommée « algorithme d’Euclide étendu »	Dans le cas présent la clef de déchiffrage est le nombre 77 (en effet : 77 x 5 = 385 ; 385 divisé par 192 égale 2 et il reste 1 )
6	Bob a donc ses deux clefs. Il communique à Alice qu’il utilisera l’algorithme RSA et lui donne les deux nombres de la clef publique n et e. Il conserve précieusement pour lui les nombres p et q, bien sûr, et le nombre d qui lui servira au déchiffrement	Clef publique : (RSA, 221, 5) Clef privée : 77

Alice chiffre puis crypte le message

Page en cours de création

afis, Science et pseudo-sciences, 14 rue de l'école polytechnique, 75005 PARIS.