II] Système RSA

Origine

Le système RSA a été créé en 1977 par trois mathématiciens : Ron Rivest, Adi Shamir et Len Adleman. On retrouve leur initiales dans RSA.

Les créateurs du système RSA
Ron Rivest, Adi Shamir et Len Adleman

Ce système de chiffrement est un des plus utilisé de nos jours. On le retrouve dans le commerce sur internet, dans les cartes de crédit et dans certains logiciels.
(Pour en savoir plus, voir la partie III)

Fonctionnement

Un système asymétrique

Avant de commencer nous vous présentons Alice et Bob, qui servirons de cobaye pour les communications cryptés.

On distingue deux systèmes de cryptages : Le cryptage symétrique et le cryptage asymétrique. Chacun ont leur avantages et inconvéniants. Ceux deux systèmes peuvent être associés afin d'avoir un système plus rapide et plus sur par exemple avec le SSH.
Dans le système symétrique, dit à clé secrète, il existe une seule clé que Alice et Bob sont les seuls à connaitre. Les messages sont chiffrés grâce à cette clé. Tout repose sur le secret de cette clé. Le code de Cesar est un système symétrique. Ce système est rapide car il ne cessite pas de calculs compliqués. Le seul problème est de pouvoir se communiquer la clé.
Le système asymétrique utilise 2 clés pour chaque personne. Une clé publique que tout le monde peut voir et utiliser. Et une clé privé que seul le propriétaire de la clé peut voir et utiliser. De cette façon il n'y a pas besoin de contacts entre Bob et Alice. Nous verrons comment fonctionne ce système avec le RSA.

Récapitulatif :

Système symétrique :
Chiffrage
+ =
Déchiffrage
+ =

Sytème asymétrique :
Chiffrage
+ Clé publique =
Déchiffrage
+ Clé privé =

Théorie

L'efficacité de l'algorithme repose sur le fait que Bob et Alice peuvent s'envoyer des messages sans jamais avoir communiqué de clé auparavent.

Chaque personne dispose de 2 clés.

Pour que Bob envoit un message à Alice, il doit utiliser sa clé publique, disponible sur un annuaire de clés. N'importe qui peut voir cette clé. Remarquons que Bob peut tout simplement demander sa clé publique à Alice par email ou dans la cour de récréation.
Après avoir écrit son message, Bob chiffre le message avec la clé publique d'Alice. Quand il envoit le message il est sur que personne ne peut le lire.
Quand Alice le reçoit, elle le déchiffre avec sa clé privé.
En résumé, la clé publique sert à chiffrer et la clé privé sert à déchiffrer.

Algorithme

Créations des clés

La clé publique

La clé publique est composé de deux nombres. On l'écrit (N, C). Voyons comment déterminer N et C.

Pour créé notre clé publique, il faut d'abord choisir deux nombres, P et Q, qui doivent être des nombres premiers. Ils admettent donc deux et uniquement deux diviseurs positifs distincts. 1 et eux même. Nous avons donc un choix infini pour les rééls P et Q.

On choisis par exemple P = 53 et Q = 97.

Ensuite, on va prendre un autre nombre, N, tel que : N = P x Q. Dans notre cas, nous avons N = 53 x 97 = 5141.

On pose M = (P-1) x (Q-1).

Ce nombre "M" est appelé indicatrice d'Euler, il correspond au nombre d'entiers naturels qui sont premiers avec N.

Dans notre cas on obtient, M = (53 - 1) x (97 - 1) = 4992.

Pour créer notre clé publique, il ne nous reste plus qu'à choisir un nombre C, qui soit premier avec M. (Il en existe, là aussi, une infinité.) Prenons C = 7.

Deux nombres sont premiers entre eux si et seulement s'ils n'ont aucun facteur commun (à l'exception de 1 et -1)

Pour savoir si C et M sont premier entre eux, on calcule leur pgcd. Il doit être égal à 1.

Au final, notre clé publique est composée de (N, C). Dans notre cas, nous avons (N = 5141, C = 7) comme clé publique.

La clé privé

Composition

La clé privé est, tout comme la clé publique, composé de deux nombres. Le premier est N, le même que dans la clé publique. Le second est U, qui est le seul nombre qui doit rester secret, si l'espion connait U, il peut déchiffrer les messages envoyés par Bob à Alice.

U permet d'inverser la fonction de chiffrement très facilement.

Nous aurons donc une clé privé (U, N) avec N = 5141.

Quand nous avons créé notre clé publique, nous avons utilisé les nombres C et M. Il vous nous servir à nouveau pour la clé privé, pour calculer U. Nous avions choisis C premier avec M.

D'après le théorème de Bézout deux nombres a et b sont premiers entre eux si et seulement s'il existe des solutions u et v (u et v sont des entiers) telles que au + bv = 1

Nous avons donc les nombres premiers C et M que nous allons utiliser pour remplacer les variables a et b.
Nous devons donc chercher CU + MV = 1 (notons que V ne nous servira pas).

Calcul de U

Pour calculer U, la technique consiste à utiliser l'algorithme d'Euclide étendu. Cet algorithme permet tout simplement de calculer un couple (u, v) des coefficients de Bézout.
En raison de possibilités technologiques de nos jours, nous allons utiliser un programme tout fait pour le RSA qui nous calculera u et v et vérifiera si C et M sont premiers entre eux.

Pour télécharger le logiciel pour Windows cliquez là.

Pour Linux il faut compiler la source et je ne sais pas le faire, au lycée nous travaillons sur Windows xp, donc nous utiliserons le programme windows si besoin.

En console, pour utiliser ce programme on utilise la commande bezout.
Pour Windows : bezout.exe -rsa C M
Pour Linux : ./bezout -rsa C M

Nous entrons obtenons :

>./bezout -rsa 7 4992
4279

Nous avons maintenant notre U = 4279.
La clé privé est composée de (U, N) soit (U = 4279 et N = 5141) dans notre cas.

Remarque : Ici nous avons de petits nombres, il n'y a donc aucune sécurité. Pour avoir un système sécurisé, il faut prendre des nombres avec plusieurs centaines de chiffres.

Cryptage

Nous allons maintenant procéder au chiffrage d'un texte à l'aide de la clé publique que nous venons de créer. Pour manipuler des chiffres, nous allons remplacer chaque caractère à chiffrer par son nombre correspondant dans la table ASCII

Pour calculer de grands nombre on doit utiliser la librairie GMP téléchargeable ici pour Windows.

On reprend toutes les valeurs des clés vu précédement.
Bob demande donc à Alice sa clé publique, elle lui donne (N = 5141, C= 7).

Bob veut envoyer le message Bonjour ! à Alice. On se réfère tout d'abord à la table ASCII pour remplacer chaque caractère par le nombre qui lui correspond dans la table.

On commence par calculer la puissance de chaque nombre. On mets le C en exposant. Pour nous C = 7 donc

Pour windows, tapez calcul_RSA 66 7 pour calculer le premier block et ainsi de suite.

Nous allons maintenant nous servir de N. Il va servir pour calculer X modulo N, soit le reste de la division euclidienne de X par N.

On obtient avec le programme précédement installé calculs_RSA 66 7 5141 :

Voilà, c'est fait, on a chiffré notre message. Ainsi avec la clé publique d'Alice (N = 5141, C = 7), le message Bonjour ! devient 386 1858 2127 2809 1858 1774 737 3675 244. À partir du moment où le message est chiffré, on ne peut plus le déchiffrer sans l'aide de la clé privée. Même Bob, qui est l'auteur du message, ne peut pas le déchiffrer.

Decryptage

Bob a renvoyé à Alice son message crypté : 386 1858 2127 2809 1858 1774 737 3675 244. Alice doit maintenant déchiffrer le message de Bob à l'aide de sa clé privé (U = 4279, N = 5141).

On commence avec le nombre nombre secret, U. On s'en sert pour élever chaque block à la puissance U. On a donc :

Maintenant comme on peut s'en douter, nous allons utiliser N. On calcule le modulo par N du résultat précédant. (Rappel : N = 5141)

On remplace les nombres obtenus par leur caractère correspondant dans la table ASCII

Alice lit donc Bonjour !, tout simplement. Pour chaque message chiffré ou déchiffré avec le RSA, on utilisera toujours le même algorythme qu'au dessus.

Le message envoyé par Bob n'était pas vraiment sécurisé. On aurai pu avoir un message sécurisé avec des nombres beaucoup plus grands. Ici les petits nombres étaient pratique pour faire un exemple.

Copyright "Purgateur Corporation" 2007-2009, tous droits réservés
Si vous reproduisez le contenu de ce site en le modifiant ou non, merci de citer l'auteur ainsi qu'un lien vers ce site

------> Voir le CSS

Code XHTML valide Code CSS valide

Mesure d'audience ROI statistique webanalytics par WebAnalytics