1) Le système R.S.A.

En 1978, l’algorithme à clé publique de Ron Rivest, Adi Shamir et Leonard Adelman (RSA) apparaît. Il servait encore à l’aube de l’an 2000 à protéger les codes nucléaires de l’armée américaine et soviétique. 

2) Fonctionnement de R.S.A.

Le fonctionnement du cryptosystème RSA est basé sur la difficulté de factoriser deux entiers. Pour commencer, il nous faut donc choisir deux nombres premiers p et q très grands (de l’ordre de 200 chiffres). Il y a des algorithmes de génération aléatoire de nombres premiers qui existent. Ensuite on trouve le nombre n facilement : n=p.q . Puis il nous faut trouver un entier e compris entre 2 et j(n). j(n) est la fonction indicatrice d’Euler, c’est en fait le nombre d’entiers inférieurs à n qui sont premiers avec lui, on a j(n)=(p-1)(q-1) . j(n) se calcule très facilement ici, puisque l’on a  p et q. Maintenant que l’on a n et e, nous sommes prêts à crypter. Les nombres n et e forment ici notre clé publique que l’on notera [n,e]. Il nous faut calculer le nombre d qui sera nécessaire au décryptage. Selon la théorie de RSA, nous devons avoir d tel que (e.d-1) soit divisible par j(n). Comme e et j(n) sont premiers entre eux, le théorème de Bezout prouve qu’il existe d et k dans Z tel que e.d+k.j(n)=1

On pourra résoudre l’équation grâce à l’algorithme d’Euclide. Après résolution, on arrivera à une classe de solution de la forme d=r.j(n)+d₀ (où r appartient à Z) puisque e a été choisi premier avec j(n). L’ensemble des solutions d à l’équation diophantienne e.d+k.j(n)=1 est une classe de congruence modulo j(n), il y a donc une unique solution d comprise entre 2 et j(n), donc d=d₀. Nous voilà prêts à décrypter. Le nombre d est notre clé privée.

Nous pouvons à présent rendre publique notre clé publique [n,e] et garder secrète notre clé privée. Quant aux nombres p, q, et j(n), on doit, soit les conserver secrets, soit les détruire car ils ne serviront plus.

3) L’algorithme R.S.A.

a) Histoire de R.S.A.

Le brevet de cet algorithme appartient à la société américaine RSA Data Security, qui fait maintenant partie de Security Dynamics et aux Public Key Parteners, (PKP à Sunnyvale, Californie, Etats-Unis) qui possèdent les droits en général sur les algorithmes à clé publique. RSA est un algorithme à clé publique qui sert aussi bien à la cryptographie de documents, qu’à l’authentification. Grâce au fait qu’il était à clé publique, et au fait qu’il était très sûr, l’algorithme RSA est devenu un standard de facto dans le monde.

b) Le cryptage avec l’algorithme R.S.A.

Pour crypter un document que l’on aura auparavant transformé en un nombre m inférieur à n il nous faut effectuer l’opération c=m^e mod n . c est ici notre nombre n une fois crypté. La première opération peut être très longue à effectuer à la main, l’utilisation d’un ordinateur et d’un programme spécial est fortement conseillée.

c) Le décryptage avec l’algorithme R.S.A.

Pour décrypter un document c, il nous faut effectuer l’opération m=c^d mod n . m sera bel et bien notre nombre décrypté, qu’il ne restera plus qu’à retransformer en texte ou en autre chose. La preuve de cette algorithme de chiffrement est faite avec le théorème de Fermat et le théorème chinois des restes connus depuis quelques siècles !

4) L’authentification de documents

L’authentification d’un document, c’est le fait d’être sûr de l’identité de l’auteur d’un document. Cette authentification peut s’avérer indispensable pour la justice lors d’un litige sur un contrat par exemple. L’authentification se fait toujours sur un contrat papier par une signature manuscrite, à priori infalsifiable. Le problème de l’authentification d’un document « informatique », est l’impossibilité physique d’y apposer une signature manuscrite à sa fin. On va donc y apposer une signature « digitale ». Pour ne pas être falsifiable, on va crypter cette signature par exemple avec l’algorithme RSA.

Les signatures digitales avec R.S.A.

Pour bien prouver qu’un document a été composé par nous, il nous suffira de crypter par exemple notre Nom, Prénom et fonction ou n’importe quoi d’autre, avec notre clé privée (en théorie connue de nous seul). Ainsi, quiconque qui voudra vérifier l’auteur de ce document, n’aura qu’à utiliser notre clé publique pour le décryptage. Et si le décryptage fonctionne, cela veut bien dire que la signature a été « forgée » avec notre clé privée.

5) L’attaque d’un document crypté avec R.S.A.

Comme on l’a vu précédemment, la résistance d’un document crypté avec l’algorithme RSA s’appuie sur le fait qu’il est extrêmement difficile de factoriser en deux facteurs premiers un très grand nombre. L’attaque va donc consister à utiliser des algorithmes de factorisation les plus rapides, et les plus puissants possibles, pour factoriser le nombre n extrêmement grand de la clé publique visée. L’attaque d’un tel document et encore beaucoup plus long (pour une taille du nombre n raisonnable) que l’attaque d’un document crypté avec DES. C’est pourquoi, de grandes recherches en mathématiques sur des algorithmes de factorisation de plus en plus rapides sont effectuées partout dans le monde. La méthode RSA, réputée pour sa quasi-invulnérabilité (quand elle est utilisée avec une très grande clé) pourrait s’écrouler si quelqu’un parvenait un jour à écrire un tel algorithme. Car RSA repose sur un principe qui a l’air évident mais qui n’a jamais été prouvé ! Actuellement, il n’y a aucun algorithme/méthode connu, capable de factoriser dans un temps convenable une très grande clé. Avec les algorithmes de factorisation actuels, il faudrait au briseur de code une puissance beaucoup plus importante pour arriver à ses fins. Mais avec une puissance de calcul plus importante, l’utilisateur peut aussi agrandir la taille de la clé de un bit ou deux, par exemple. Or l’augmentation de la taille de la clé de un/deux bits signifie une multiplication par deux/quatre le nombre maximum que peut être la clé ! Par exemple RSA Labs a mis sur le marché il y a quelques mois un processeur dédié à la méthode RSA comportant des instructions dites « de haut niveau » directement implémentées sur le processeur, comme une instruction permettant de calculer le modulo d’un grand nombre avec un autre grand nombre rapidement, et une instruction permettant de factoriser un grand nombre. Ce processeur factorise en effet beaucoup plus vite qu’un ordinateur normal, puisque sur l’un, l’algorithme de factorisation est implémenté en hardware alors que sur l’autre, il est implémenté en software. On peut remarquer que ce processeur avantage plus ou moins également le crypteur que le briseur de code.

Tableau récapitulatif de la gestion des clés avec R.S.A. :