Introduction

Pour exposer le principe du cryptage asymétrique sans nous perdre dans les détails mathématiques, nous allons utiliser une analogie très simple. Considérons la méthode de cryptage qui consiste à remplacer tous les caractères d'un texte par celui qui se trouve p positions plus loin dans l'alphabet. Nous choisissons préalablement une valeur de décalage, mettons 2, puis nous remplaçons tous les a par des c, tous les b par des d, etc…

Un programme pourra le faire très simplement en ajoutant le décalage au code ASCII du caractère modulo 256.

Le décryptage le plus évident consiste à appliquer la méthode inverse: au lieu de décaler vers la fin de l'alphabet, on décale vers le début en utilisant la même valeur (clef). On utilisera donc une soustraction au lieu d'une addition. Mais il existe une autre méthode équivalente qui consiste à décaler à nouveau vers la fin de l'alphabet en utilisant cette fois la valeur 256-clef. Au lieu de revenir en arrière, on exécute un "tour complet". L'opération utilisée est alors une addition et non une soustraction.

Quelle est la différence ? Lorsqu'on utilise addition/soustraction, il n'y en a aucune car les deux opérations sont à peu près aussi faciles à exécuter. Supposons maintenant qu'on utilise comme fonction de décalage une exponentiation: s'il est relativement facile d'élever un nombre à une puissance quelconque, il est beaucoup plus difficile d'en extraire la racine nième. Songez au cas 2: le carré d'un nombre se calcule en quelques instants avec un papier et un crayon, la racine carrée est nettement plus longue à extraire (Quelqu'un dans la salle sait-il encore extraire une racine carrée à la main ?) . A condition d'utiliser des nombres suffisemment grands, cette extraction devient pratiquement impossible car elle réclame des temps d'exécution trop élevés, même pour des machines très puissantes.

Dans notre analogie, ceci revient à dire que la méthode de décryptage évidente qui consiste à revenir en arrière en utilisant la clef qui a servi à encrypter est inutilisable et qu'on doit donc se rabattre sur la seconde méthode qui met en jeu une deuxième clef qui dépend de la première et du modulo utilisé. Dans notre analogie, la seconde clef se déduit facilement de la première et du modulo par soustraction. Ce qui implique que dans le second cas, il faudrait de nouveau extraire une racine nième pour déduire la seconde clef de la première, et qu'une fois encore, ce calcul est impraticable.

L'algorithme RSA (du nom de ses inventeurs Rivest, Shamir et Adleman), est donc fondamentalement une fonction dont l'inverse n'est pas calculable en pratique et dont l'application répétée avec deux clefs convenablement choisies redonne le message original. Dans les techniques classiques, l'émetteur et le récepteur du message codé doivent tous les deux possèder la même clef, donc trouver un moyen sûr de se la communiquer. D'autre part, un tiers en possession d'un exemplaire du message codé et du message en clair peut assez facilement en déduire la clef s'il connaît l'algorithme utilisé. Avec un algorithme asymétrique, l'émetteur n'a pas besoin des deux clefs: la première suffit. La seconde pourra donc n'être connue que de son propriétaire. Comme il est impossible de déduire la deuxième clef de la première, il n'y a aucun inconvénient à rendre la première publique. De la même manière, disposer du même message sous forme codée et en clair n'apporte rien, sinon des resnseignements sur le première clef qui sont connus de tous.

L'algorithme consiste en gros à découper le message en chaînes de caractères de même longueur, les convertir en nombres (hashage), puis de les élever à la puissance p (clef publique du destinataire) modulo n. Le récepteur élève de nouveau chacun de ces nombres à la puissance q (sa clef privée) modulo n puis exécute le hashage inverse pour rétablir le message. Pour définir un jeu de clefs, on choisit arbitrairement deux grands nombres premiers et un calcul simple permet d'en déduire deux clefs et le modulo associé.

Pour ceux qui souhaitent se pencher sur les détails mathématico-informatiques de l'algorithme on peut consulter:

Le site RSA Laboratories est consacré à ce thème. Une présentation détaillée de l'algorithme proprement dit peut être téléchargée au format Word.(cliquez ici)

Le site du NIST pour SHA1 qui est la méthode de hashage la plus recommandée.

Propriétés de l'algorithme RSA et protocoles

Quittons maintenant les mathématiques pour explorer les multiples possibilités offertes par la technique de codage asymétrique. Dans la suite nous appellerons P(M) le résultat de la fonction de cryptage appliquée au message M en utilisant la clef publique et p(M) le résultat de la même fonction en utilisant la clef privée. La propriété fondamentale de l'algorithme est donc que p(P(M)) = M

Echange de messages cryptés

Chaque utilisateur se fabrique donc une paire de clefs (c'est naturellement le travail de certains programmes comme PGP alias Pretty Good Privacy, le plus connu des utilitaires de ce genre, qui assure également l'encryptage des e-mails. Linux contient également une fonction de ce genre). Il transmet ensuite à qui le désire sa clef publique, et toute personne souhaitant lui envoyer un message l'encryptera à l'aide de cette clef. Pour la réponse, il faudra naturellement employer la clef publique du premier émetteur. Une suite de messages pourrait donc se représenter comme suit:

On voit donc que chacun n'a besoin de disposer que de la clef publique de l'autre et que les messages voyagent sur le réseau de manière parfaitement sûre.

Signatures

Mais l'algorithme (car il est basé sur des opérations mathématiques commutatives) a également la propriété suivante: P(p(M)) = M. Autrement dit, l'ordre dans lequel on utilise les clefs n'importe pas. Il est assez évident qu'un message encrypté avec la clef privée d'un utilisateur n'a plus rien de confidentiel, puisque n'importe qui, disposant de sa clef publique, peut le décrypter. Par contre, seul l'émetteur est en mesure de créer un message codé qui sera correctement décodé à l'aide de sa clef publique. Ce qui permet de créer des signatures électroniques infalsifiables. Une signature de ce type sera par exemple constituée du message:

La vérification de la signature consiste à comparer M passé en clair avec le résultat du décryptage P(p(M)) (la deuxième partie du message complet). En effet, seul le détenteur de la clef privée p est en mesure d'encoder correctement M de telle manière que les deux parties du message concordent. Par conséquent, tout un chacun peut s'assurer qu'il est bien l'auteur du message. (Cet exemple rudimentaire et didactique ne résoud pas tous les problèmes de sécurité et les implémentations réelles sont en fait plus complexes).

Autres possibilités

Il existe encore d'autres possibilités basées sur la commutativité de l'algorithme: on peut en effet mélanger l'application des paires de clefs comme dans l'exemple suivant: imaginons que deux machines souhaitent communiquer sans connaître leurs clefs publiques respectives. Elles peuvent procéder ainsi pour se transmettre un message M:

A envoie PA(M)
B reçoit ce message qu'il ne peut décrypter (il lui faudrait la clef privée de A), il répond en encryptant le paquet avec sa propre clef publique soit PB(PA(M))
A applique au paquet sa clef privée pA(PB(PA(M))) ce qui donne PB(M) (ne me demandez pas pourquoi ça marche) et renvoie ce nouveau paquet que B décryptera facilement en lui appliquant sa clef privée.

Et le tour est joué. Il existe pas mal de variations possibles sur ce thème, répondant toutes à un besoin différent. Cet échange particulier a la propriété de ne pas être vulnérable à l'attaque connue sous le nom de "man in the middle" (décrite plus loin), mais elle ne résoud pas le problème de l'identification du destinataire.

Il existe aussi des applications à trois partenaires et plus, en particulier pour le paiement sécurisé, où un organisme intermédiaire délivre à un acheteur un jeton utilisable par lui seul et une fois seulement pour règler un achat ou un service effectué en ligne. On utilise alors des composés complexes de signatures et de messages utilisant les clefs des trois partenaires.

Man in the middle et autres certificats

Les messages ont beau être cryptés de manière parfaitement sûre, il existe un trou énorme dans la sécurité. Supposons qu'un tiers X soit placé sur la route des échanges entre A et B. Il peut naturellement se créer une paire de clefs et tenter de faire croire à A et B que sa propre clef publique est celle de son correspondant.

A envoie sa clef publique PA vers B
X intercepte le message et communique à B sa propre clef publique PX
B envoie sa clef publique PB vers A
X intercepte de nouveau et communique à A sa propre clef publique PX

Si la transaction se poursuit par l'émission d'un message M en provenance de A. A l'encodera avec PX, ce qui permet à X de le décoder, ET de le réencoder en utilisant la clef publique de B qui le recevra normalement. Au lieu de:

On a:

La présence du tiers est donc parfaitement transparente. Cette attaque, connue sous le nom de "man in the middle", ne peut être contrée que si A peut s'assurer qu'il utilise la clef publique de son destinataire final B et non une autre qui lui aurait été substituée. Pour cette raison, on a recours à un "tiers de confiance" ou organisme certificateur. Celui-ci est un site capable de fournir sous une forme infalsifiable la clef publique de l'utilisateur qu'il certifie. Un certificat est donc fondamentalement un message qui contient une clef publique et une identification d'utilisateur, signée (électroniquement) par l'organisme en question. On pourrait imaginer qu'un pirate puisse également créer de faux certificats en essayant de se substituer à l'organisme certificateur. Mais pour cela, il faudrait qu'il puisse s'installer sur la route entre le demandeur et l'organisme, qu'il établisse une corrélation entre deux transactions qui n'ont rien à voir entre elles (la requête de A vers l'organisme pour obtenir la clef publique de B, puis le message de A vers B), et enfin, qu'il puisse se substituer avec succès à l'organisme certificateur. Comme la plupart des navigateurs sont livrés avec le certificat d'un certain nombre de ces organismes, il faudrait donc que le pirate ait également accès à ces certificats sur la machine de A.

Conclusion

Comme on l'a vu dans ce bref exposé, le cryptage asymétrique est une technique très souple qui permet d'implémenter un grand nombre de protocoles d'usages variés. Il se trouve également dans les protocoles de communication sécurisés comme https/SSL (secure socket layer) et les réseaux vrituels privés VPN. Dans un certain nombre de cas, il s'appuie sur l'existence permanente d'une paire de clefs propre à un utilisateur ou une machine, mais il existe aussi d'autres cas où ces clefs sont calculées au vol et pour le temps d'une transaction. Rien n'oblige à ce que cette paire de clefs soit permanente et unique comme une adresse IP.

Nous n'avons naturellement pu qu'effleurer le sujet, à la fois pour rester dans le cadre d'un article et... par ignorance d'une bonne partie de ces questions.

On m'excusera de n'avoir pu proposer une bibliographie même sommaire, mais le journal des réseaux n'a-t-il pas cette ambition en lui-même ?

L. Sebilleau -- Informatique Service Angers -- e-mail