Utilisateur:Thilp/Brouillons/Salle d'attente

Toute la cryptologie sur Vikidia : Qu’est-ce que… la cryptographie ? la cryptologie ? la cryptanalyse ? chiffrer, déchiffrer, décrypter ? le principe des clefs de chiffrement ? les cryptographies symétrique et asymétrique ?

Rivest Shamir Adleman (RSA) est un algorithme de chiffrement.

Créé en 1977, il est encore aujourd’hui très utilisé à travers le monde. Il fait partie de la famille des chiffrements à clef publique, qui permettent d’échanger de l’information entre deux personnes sans que d’autres puissent savoir ce dont il s’agit. Ses principaux champs d’application sont les communications secrètes et les échanges bancaires.

Il est basé sur les mathématiques, et plus précisément sur le problème dit « du logarithme discret ».

Historique

RSA est un sigle qui rassemble les initiales de ses trois concepteurs :

• Ronald Rivest ;
• Adi Shamir ;
• Leonard Adleman ;

qui sont cryptologues et mathématiciens.

Ils ont décrit le principe de RSA en 1977, et l’algorithme a été breveté par le MIT  en 1983. Ce brevet a expiré en l’an 2000 : cela signifie qu'aujourd'hui, tout le monde peut utiliser RSA en toute liberté.

Le principe de la cryptographie asymétrique a été inventé en 1976 par Whitfield Diffie et Martin Hellman ; il existait donc avant RSA. Cependant, aucun algorithme n'était conçu pour l'utiliser !

La légende raconte que Ronald Rivest a imaginé les bases de RSA lors d'une fête chez ses étudiants.

Principales utilisations

• Commerce :

  C’est majoritairement RSA qui sécurise les transferts d’argent lors d’un achat sur Internet. Cela empêche le vol des coordonnées bancaires (comme le code de la carte bancaire), qui donnent accès au compte.

• Communication secrètes :

  RSA permet de communiquer des informations à une autre personne sans lui avoir transmis une clef (un « mot de passe ») avant. De cette façon, on peut échanger des messages sans craindre qu’un espion les intercepte.

  Ce principe est notamment utilisé par les militaires et les entreprises, pour partager leurs informations avec leurs collaborateurs sans que leurs adversaires puissent les lire.

• Authentification :

  C’est ainsi qu’on appelle la vérification de l’identité de la personne avec qui l’on correspond. Par exemple, RSA est utilisé par certains sites Internet pour prouver qu’ils ne sont pas des contrefaçons, des faux. Les sites de messagerie électronique, de banques et les vendeurs de logiciels s’authentifient généralement (le navigateur Internet le signale alors, par un cadenas par exemple) : cela indique qu’on communique bien avec le site web prévu, et non avec un pirate informatique.

• Autres chiffrements :

  Depuis sa création, RSA a inspiré de nombreux autres algorithmes. On peut citer PGP , GPG  et DSA .

Fonctionnement

Note : cette section explique le principe général de RSA ; elle n’emploie pas les mathématiques. Pour une description complète, voir la section Description, plus bas.

Introduction

Imaginons que deux personnes, Alice et Bob, veuillent s’envoyer un message secret sans qu’un troisième personnage, Ève, puisse découvrir ce dont il s’agit.

Alice et Bob pourraient décider d’une clef et l’utiliser pour chiffrer leurs messages (c’est la cryptographie symétrique : les deux parties partagent la même clef). Cependant, ils ne peuvent peut-être pas le faire sans qu’Ève les espionne et découvre leur clef.

RSA (et les autres algorithmes de cryptographie asymétrique) permettent donc d’éviter cette situation : Alice a ses propres clefs, Bob a les siennes et ils ne les partagent pas comme ça.

Alice possède deux clefs de chiffrement :

• K_P,A : sa « clef publique » ;
• K_S,A : sa « clef privée » (secrète).

Alice peut donner sa clef publique à tout le monde, même à Ève. Par contre, sa clef privée doit vraiment rester secrète ! Pour communiquer avec Alice, Bob a besoin de connaître K_P,A, mais pas K_S,A.

Chiffrement, transfert et déchiffrement

On note M le message que Bob veut envoyer à Alice. Ève ne doit pas pouvoir découvrir M pendant cet envoi.

1. Bob chiffre M avec K_P,A, la clef publique d’Alice, qu’il connaît (comme Ève) puisqu’Alice l’a donnée à tout le monde. Il obtient C, le message chiffré avec K_P,A.
2. On suppose qu’Ève intercepte le courrier. Elle connaît donc C et K_P,A, mais ni K_S,A, ni le message clair M. Par les propriétés mathématiques de RSA, elle ne peut pas retrouver M, même en connaissant le résultat (C) et le chiffrement (K_P,A) : on appelle la transformation de M par K_P,A une transformation à sens unique, car il est impossible de « revenir en arrière », de l’inverser… sans connaître K_S,A !
3. Alice reçoit le message codé C. En appliquant sa clef privée K_S,A à C, elle retrouve M.

Avantages et inconvénients

• Alice et Bob n’ont pas eu à convenir d’une clef secrète entre eux, ils peuvent même ne pas se connaître ! Sur Internet, il existe de grands « annuaires » qui répertorient les clefs publiques de beaucoup de gens, ce qui permet à n’importe qui de les contacter de manière sécurisée.
• Il est inutile de protéger le message pendant son trajet : on a vu qu’Ève, qui avait intercepté C, ne pouvait rien en faire pour retrouver M.
• Par contre, le chiffrement RSA nécessite de gros calculs, contrairement aux chiffrements symétriques.

Ce sont les raisons pour lesquelles on a inventé la cryptographie hybride, qui allie la puissance des chiffrements asymétriques pour communiquer (comme RSA) à la rapidité des chiffrements symétriques (comme AES ).

Description

Cette section décrit les détails de l’algorithme RSA.

De nombreux liens bleus y expliquent les notions mathématiques utilisées : il ne faut pas hésiter à les suivre !

Pour chiffrer un message, on le transforme d’abord en nombre (ou en suite de nombres). Les algorithmes de chiffrement utilisent des opérations mathématiques sur ces nombres, en se servant d’une clef, pour rendre le message illisible.

Dans les sous-sections suivantes, on découvrira pas à pas :

• les groupes cycliques : le cadre dans lequel RSA fait ses calculs ;
• le logarithme discret : ce qui empêche d’inverser le chiffrement avec la clef publique ;
• la trappe : c’est l’astuce permettant de retrouver le message original grâce à la clef privée.

Enfin, la sous-section Protocole complet résume ces notions et décrit les étapes de l’algorithme.

Les groupes cycliques

La plupart des calculs que nous faisons tous les jours, comme par exemple :

• le coût total de l’achat de plusieurs objets ;
• le temps qu’il nous reste avant un rendez-vous ;
• la quantité d’ingrédients nécessaire pour faire la cuisine ;

Une horloge à aiguilles, exemple d’un groupe cyclique.

nous sont habituels. Ils se déroulent dans une certaine structure mathématique qu’on appelle un corps (dans ces exemples, c’est celui des nombres réels). On peut y ajouter autant de farine ou d’euros qu’on veut, on trouve toujours le résultat auquel on s’attend : leur somme.

Les calculs de RSA, eux, se font dans une structure différente ; mais pas de panique ! Nous avons aussi l’habitude de l’utiliser.

Cette structure est celle des groupes cycliques. Nous connaissons en fait bien cette notion, avec la mesure du temps. Ainsi, sur une horloge avec aiguilles,

• 9 heures + 1 heure = 10 heures ;
• 10 heures + 1 heure = 11 heures ;
• 11 heures + 1 heure = 12 heures ;
• mais : 12 heures + 1 heure = 1 heure ! (et non 13 heures, sur une horloge)

Pourtant, si cela avait été de l’argent, 12 € + 1 € = 13 €. C’est parce que les calculs d’argent se font dans le corps des réels (comme les exemples plus haut), tandis que les calculs horaires, eux, se font dans un groupe cyclique. Quel est ce groupe ?

Pour les heures sur l’horloge, c’est $\mathbb {N} /12\mathbb {N}$, c’est à dire : les nombres entiers positifs, modulo 12. Cela signifie qu’en comptant 0, 1, 2, 3… on ne dépasse jamais 12 ; quand on arrive à 12, on repart à 0. C’est bien ce que font les heures :

• 0 heure (minuit),
• 1 heure (du matin),
• 2 heures (du matin),
• …
• 11 heures (du matin),
• 0 heure (midi),
• 1 heure (de l’après-midi),
• …
• 11 heures (du soir),
• 0 heure (minuit) !

On comprend pourquoi ces groupes s’appellent « cycliques » : ils décrivent un cycle (ils « tournent »), comme les heures, l’eau ou les saisons, et reviennent toujours aux mêmes valeurs, régulièrement.

Un groupe cyclique, finalement, n’est pas bien compliqué :

1. c’est un ensemble de nombres ;
2. tous ces nombres sont compris entre deux bornes (pour l’horloge, ce sont 0 et 12) ;
3. par conséquent, le résultat de toute opération dans un groupe cyclique est aussi compris entre ces bornes.

   Exemple : si on parle d’heures, 11 + 3 × 6 ne vaut pas « 29 » (« il est 29 heures » n’a aucun sens), mais « 29 modulo 12 », c’est-à-dire « 29 moins 12, et encore moins 12, et encore, tant que le résultat n’est pas inférieur à 12 » ; le résultat vaut donc 5.

Pour en savoir plus, lis l’article : Modulus.

Le logarithme discret

Un peu de théorie

La courbe de la fonction logarithme naturel près de zéro.

Le logarithme discret est une fonction mathématique très connue, le logarithme, appliquée à des nombres entiers positifs (c’est ici le sens de « discret »). On la note ln pour faire plus court (logarithme naturel).

La fonction qui fait l’inverse de ce que fait le logarithme s’appelle l’exponentielle. Si on la note exp, cela signifie que, si y = exp(x), alors x = ln(y). L’exponentielle est la réciproque du logarithme.

Pour en savoir plus, lis l’article : Fonction réciproque.

On peut créer autant de fonctions exponentielles et logarithmes que l’on veut. Les plus communes, celles que l’on note habituellement ln et exp, sont dites « naturelles » car elles sont « de base e » (c’est juste une convention). Il existe par exemple d’autres logarithmes :

• le logarithme « de base 10 », noté log₁₀ et utilisé en physique ;
• le logarithme « de base 2 », noté log₂ et utilisé en informatique.

On peut donc choisir un nombre a et décider d’utiliser les fonctions « exponentielle de base a » (notée exp_a ou $x\mapsto a^{x}$) et « logarithme de base a » (notée log_a). On aura toujours la relation de réciprocité de tout à l’heure : si y = a^x, alors x = log_a(y).

Dans la pratique de RSA

Une des transformations les plus importantes du RSA est celle-ci :

$M^{e}=C_{1}$

où M est le message à chiffrer, e et m deux nombres (qui constituent la clef) et C₁ le résultat de l’opération.

Cela signifie que nous calculons « M puissance e ».

Grâce à l’écriture, nous savons maintenant que « M puissance e » est en fait… une exponentielle de base M ! Pour décrypter un message en ne connaissant que la clef publique, c’est-à-dire pour retrouver M à partir de C₁, il faut donc faire l’opération inverse. Nous avons vu juste avant que, pour cela, il nous faut utiliser un logarithme de même base, donc un logarithme de base M.

Liens, sources et références

Liens pour compléter

• Sur Vikidia :
  • Cryptographie ;
  • Clef publique ;
  • Pretty Good Privacy.
• Ailleurs sur Internet :
  • Qu’est-ce que la cryptographie à clef publique ? sur [email protected] ;
  • RSA et sa mise en pratique sur le Site du Zéro.

Sources de cet article

Les ouvrages et sites suivants ont permis d’assurer les fondements théoriques de cet article :

• Applied Cryptography (seconde édition) de Bruce Schneier ;
• [pdf] Théorie du RSA par le département de mathématiques et applications (DMA) de l'École Normale Supérieure de Paris ;
• La cryptographie à clé publique - le RSA sur [email protected] ;
• Anneau Z/nZ et RSA sur Wikipédia.

Références

Catégorie:Cryptologie Catégorie:Communication