loadingPage en cours de chargement
    ACCUEIL | TÉLÉCHARGER | QCM | DON | ANNONCES | CHAT | FORUM | LIVRE D'OR | PARTENAIRES | CONTACT | BLOG
 
  Rechercher
  separation
  Introduction
  Arithmétique
  Algèbre
  Analyse
  Géométrie
  Mécanique
  Électrodynamique
  Atomistique
  Cosmologie
  Chimie
  Informatique Théorique
  Maths. Sociales
  Ingénierie
  separation
  Biographies
  Références
  Liens
  separation
  Humour
  Serveur d'exercices
  separation
  Parrains
15 connectés
News News :: Erreur Erreur :: Statistiques Visiteurs :: ClearType ClearType :: Imprimer Imprimer :: Bookmark and Share

Informatique Théorique

MÉTHODES NUMÉRIQUES | FRACTALES | SYSTÈMES LOGIQUES | CODES CORRECTEURS CRYPTOGRAPHIE | AUTOMATES | INFORMATIQUE QUANTIQUE

61. CRYPTOGRAPHIE

Dernière mise à jour de ce chapitre: 2017-04-14 17:21:02 | {oUUID 1.789}
Version: 3.1 Révision 9 | Avancement: ~50%
viewsvues depuis le 2012-01-01: 5'401

Table des matières LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité et/ou authenticité) que deux personnes souhaitent s'échanger à travers un canal peu sûr en s'aidant souvent de secrets ou clés.

L'histoire de la cryptographie est déjà longue et passionnante (puisque c'est en quelque sorte un "jeu"). Nous rapportons son utilisation en Égypte il y a 4'000 ans. Toutefois, pendant des siècles, les méthodes utilisées étaient restées souvent très primitives. D'autre part, sa mise en oeuvre était limitée aux besoins de l'armée et de la diplomatie. Ainsi, les méthodes de chiffrement et de cryptanalyse (le casse de code) ont connu un développement très important au cours de la seconde guerre mondiale et ont eu une profonde influence sur le cours de celle-ci.

À la fin du 20ème siècle (en particulier !), avec la prolifération des ordinateurs et des moyens électroniques de communication, il était devenu de plus en plus important d'utiliser des codes secrets pour la transmission des données entre les organismes à caractère militaire ou privé. Ainsi, les ingénieurs ont dû chercher à cette même époque des méthodes numériques solides et dont la mise en oeuvre et l'usage était à portée de presque tout un chacun (nation, entreprise et individu) tout en faisant en sorte que les attaques extérieures nécessitent des outils hors d'atteinte d'un individu ou groupe d'individus équipé d'outils informatiques standards ou performants (en puissance de calcul donc). Les ingénieurs et chercheurs se sont alors plongés dans la mathématique pour chercher les outils satisfaisant ce cahier des charges et pour les systèmes les plus connus, les théories mathématiques qui furent adoptées avaient plus de 200 ans (cryptographie quantique mise à part) d'ancienneté.

Les techniques de stéganographie (art de dissimuler un message dans un autre, ou dans une image) doivent toutefois être préservées car rien ne nous dit que la puissance de calcul de l'informatique sera toujours disponible en temps de guerre. Il convient de souligner aussi que la stéganographie déploie des trésors d'imagination. Signalons par exemple: les permutations de lettres, les formatages spéciaux et subtiles de caractères, l'utilisation de synonymes, les messages cachés dans la virgule d'un texte ou derrière un timbre-poste, dans des coups de jeux d'échecs (d'où le fait que ces jeux aient été interdits par les américains pendant quelques années après l'attaque de Pearl Harbor), dans des images/dessins, dans des partitions musicales, etc. Toutes ces techniques font que pendant la deuxième guerre mondiale, l'office de censure aux États-Unis occupait 10'000 employés à plein temps qui analysaient le courrier des citoyens, les petites annonces, les textes radios, etc.

Remarques:

R1. Pour aborder les fondements de la théorie de la cryptographie, nous conseillons au lecteur d'avoir parcouru au préalable les chapitres de Théorie des Nombres, Théorie des Ensembles, de Méthodes Numériques (surtout la partie traitant de la complexité algorithmique), des Systèmes Numériques Formels, de la Mécanique Statistique (où se trouve la théorie de l'information) et pour la partie de la cryptographie quantique: le chapitre d'Informatique Quantique du site.

R2. Il faut rester conscient à nouveau que la cryptographie étant plus une science de l'ingénieur qu'une science du physicien (mis à part en ce qui concerne la cryptographie quantique) il ne faut pas s'étonner alors de voir apparaître des algorithmes tombés un peu de nulle part et adoptés par l'industrie parce qu'ils marchent bien... par ailleurs il est certain que seulement quelques années après avoir écrit ce texte il soit déjà considéré comme obsolète (c'est tout l'art de l'ingénierie... l'obsolescence programmée)

SYSTÈMES CRYPTOGRAPHIQUES

Définitions:

Un "système cryptographique" est composé de:

D1. Un ensemble fini P appelé "l'espace des textes clairs"

D2. Un ensemble fini C appelé "l'espace des textes chiffrés"

D3. Un ensemble fini K appelé "l'espace de clés"

Pour chaque clé equation, nous cherchons une fonction de chiffrement:

equation   (61.1)

et une fonction de déchiffrement (decryption):

equation   (61.2)

telles que (cf. chapitre de Théorie Des Ensembles):

equation   (61.3)

Autrement dit, ces deux fonctions doivent être injectives!

Pour arriver à ce résultat, deux types de techniques cryptographiques se distinguent , englobant toutes les méthodes de cryptage modernes connues (pour les détails voir plus loin):

1. Les premières concernent les systèmes de chiffrement "symétriques à clé secrète".

Remarque: Les clés publiques font souvent référence au protocole D.E.S. (voir plus loin): Data Encryption System.

2. Les secondes concernent les systèmes de chiffrement "asymétriques à clé publique". 

Remarque: Ce type de clé fait souvent référence par exemple au protocole R.S.A., du nom des personnes à qui on en a attribué le développement: Rivest, Shamir et Adleman. Elles sont beaucoup utilisées de par la rapidité du temps de cryptage et de décryptage ainsi que de leur grande entropie (voir définition plus loin).

Par nature, ces deux types de clés sont très différents. Essayons d'en comprendre les raisons:

Un chiffrement symétrique désigne un système où la clé utilisée dans l'opération de chiffrement est aussi celle utilisée dans l'opération de déchiffrement. Dans ce cas, lors d'un échange sécurisé (supposé), les deux parties de la correspondance doivent partager un secret: la clé utilisée ou "clé de session".

Un chiffrement asymétrique désigne un système de chiffrement où la clé utilisée pour le chiffrement (clé privée de l'expéditeur) diffère de celle utilisée pour le déchiffrement (clé privée du destinataire). Le seul échange qu'il y a entre les membres du groupe est la clé publique, qui permet à chacun des membres d'adapter son chiffrement (ou cryptage) en fonction de la clé privée des autres membres (parmi les nombreux systèmes asymétriques qui ont été proposés, l'un des plus répandu en ce début de 21ème siècle est le R.S.A.).

Remarques:

R1. En 2001, MS Internet Explorer (navigateur internet de Microsoft) fonctionnait avec un système asynchrone de 1024 bits certifié par un système synchrone et Adobe Acrobat (PDF) en 2004 avec un système A.E.S. (Advanced Encryption System) de 128 bits pour les protections basses de même que pour l'iPhone 4S et 5.

R2. MS Windows et son système E.F.S. (Encryption File System) utilise une clé symétrique (pour chiffrer le fichier) appelée "File Encryption Key" et la cryptographie asymétrique pour coder la clé symétrique dans l'en-tête du fichier selon le schéma suivant (les clés étant mises à jour régulièrement via les certificats racines de Windows Update):

equation
Figure: 61.1 - Principe de l'E.F.S. dans l'O.S. Microsoft Windows (source: Wikipédia)

Ces méthodes demeurent toujours déchiffrables, à condition que l'intercepteur possède "assez de temps et de papier" (exception à ce jour pour le cryptage quantique).

Voici un petit tableau résumé des clés cassées et de leur taille respective pour chacun des deux systèmes classiques:

Clé secrète (système symétrique)
Recherche exhaustive

Nombre de bits

Année

40

Cassée en 1995

56

Cassée en 1998

64

Cassable

128

Cassable en ~2100

256

?

Clé publique RSA (système asymétrique)
Factorisation

Nombre de bits

Année

256

Cassée en 1985

512

Cassée en 1999

1024

Cassée 2010

2048

Cassable en ~2100

4096

?

Tableau: 61.1 - Systèmes de clés et cassages récents

PRINCIPE DE KERCKHOFFS

La première fonction de la cryptographie consiste donc à assurer la confidentialité d'un échange d'informations. Deux parties d'un échange confidentiel s'accordent d'abord sur une convention secrète pour rédiger leurs messages, et si elles l'ont soigneusement choisie, personne d'autre ne devrait pouvoir saisir leur échange.

Si le caractère secret de telles conventions est envisageable entre quelques personnes isolées pour une période limitée, il est inconcevable à grande échelle et pour une durée assez longue. C'est ce qu'avait compris Auguste Kerckhoffs lorsqu'il établit les principes de base de la cryptographie pratique dont un principe fondamental exige un système de chiffrement: "qui n'exige pas le secret, et qui puisse sans inconvénient tomber entre les mains de l'ennemi". 

Un autre principe précise que: "la clé doit pouvoir être changée ou modifiée au gré des correspondants".

Le premier de ces deux principes, connu aujourd'hui sous le nom de "principe de Kerckhoffs", stipule donc que la sécurité d'un système de chiffrement n'est pas fondée sur le secret de la procédure qu'il suit, mais uniquement sur un paramètre utilisé lors de sa mise en oeuvre: la clé. Cette clé est le seul secret de la convention d'échange.

Ce principe a cependant été reformulé par Claude Shannon: "l'adversaire connaît le système". Cette formulation est connue sous le nom de la "maxime de Shannon". C'est le principe le plus souvent adopté par les cryptologues, par opposition à la sécurité par l'obscurité.

TRAPPES

Il existe parfois ce que nous nommons des "trappes" dans les clés publiques et secrètes. Ceci est dû au fait que lors de la génération de la clé, qui doit se faire aléatoirement en respectant certaines contraintes théoriques prédéfinies, le générateur aléatoire peut avoir un défaut (parfois le défaut est volontaire de la part du fournisseur... espionnage oblige).

Dans les clés secrètes, les trappes se situent au niveau de "l'entropie de la clé" (cf. chapitre de Mécanique Statistique), directement liée à l'entropie du générateur aléatoire. Nous pouvons de manière simpliste définir l'entropie d'un générateur de clés par le nombre moyen optimal de questions binaires (c'est-à-dire donnant lieu à des réponses du type Oui/Non) qu'il faut poser à quelqu'un connaissant une clé produite par ce générateur, pour la déterminer. Plus l'entropie d'un générateur de clé est élevée, plus il faut de questions pour déterminer cette clé. À l'inverse, plus l'entropie est faible, moins il faut de questions, de sorte que la recherche d'une clé est facilitée.

L'introduction de trappes dans les clés de systèmes asymétriques est beaucoup plus difficile, puisque ce type de clé possède déjà une structure mathématique intrinsèque: leur construction n'est pas due au hasard, mais résulte de règles mathématiques. Le hasard est ici dans le choix des grands nombres premiers utilisés. Le fait que les systèmes asymétriques puissent être aisément calculés, mais difficiles à inverser font qu'ils sont parfois appelés "fonctions trappes à sens unique".

Remarque: Si le générateur aléatoire qui engendre ces nombres premiers est biaisé (cf. chapitre de Statistiques), ce biais facilitera la recherche des nombres premiers ayant servi à l'élaboration de la clé qu'un attaquant tente de casser.

SYSTÈME DE CHIFFREMENT A CLÉ SECRÈTE

Le "chiffre à usage unique" est un algorithme de chiffrement à clé secrète prouvé inconditionnellement sûr. Correctement utilisé (et c'est un point important), il fournit un chiffrement incassable en des temps raisonnables.

Les bases théoriques de ce système de cryptage sont les suivantes:

Soit un message M sous forme binaire à transmettre entre des personnes A (créateur et expéditeur du message M) et B ( lecteur et destinataire). Nous engendrons une grande quantité de bits "réellement aléatoires" qui forment une clé secrète K de même taille que le message à transmettre (les programmes informatiques, déterministes par essence, ne peuvent engendrer des bits vraiment aléatoires).

Cette clé sera transmise à B par un canal supposé sûr... Un laps de temps donné après la transmission de cette clé, A va encoder son message en C en effectuant l'opération:

equation   (61.4)

equation est un opérateur qui doit satisfaire à une loi de groupe (cf. chapitre de Théorie Des Ensembles) sur un ensemble fini (qui contient un nombre fini d'éléments).

L'intérêt en informatique est d'utiliser la loi de groupe XOR (aussi nommée OU EXCLUSIF) notée equation par la suite (cf. chapitre de Systèmes Logiques).

Finalement, l'expéditeur A transmet la version cryptée C de son message par une voie pas nécessairement sécurisée. B retrouve le message original M en utilisant l'opération inverse equation de equation(l'opérateur XOR est son propre inverse comme le montre sa table de vérité dans le chapitre de Systèmes numériques). Ainsi B va effectuer l'opération suivante:

equation   (61.5)

Sous réserve que la clé K ait bien été engendrée de façon totalement aléatoire et que chaque bit la composant n'ait été utilisé qu'une seule fois pour crypter le message, un intercepteur n'obtient aucune information sur le message clair M s'il intercepte C . En effet, dans ces conditions, on ne peut établir aucune corrélation entre M et C sans la connaissance de K.

Même avec de futurs ordinateurs quantiques ultra-puissants, le problème est insoluble, car rien ne relie les informations dont on dispose et le problème à résoudre. En conséquence, le "chiffre à usage unique" est un algorithme de chiffrement "inconditionnellement sûr". La preuve de sa sécurité ne fait pas appel à des conjectures mathématiques non démontrées et les tentatives de déchiffrement d'un intercepteur muni d'une puissance de calcul infinie sont vaines.

Cependant, chaque étape du chiffrement est source d'erreurs possibles. En effet, la clé K peut avoir été mal élaborée. La moindre déviation statistique sur K par rapport à du "vrai" aléatoire fourni des informations sur le message clair M à partir de sa version cryptée. C'est la raison pour laquelle les bits de K ne doivent servir qu'une seule fois.

Effectivement, supposons qu'une même clé ait servi à chiffrer les messages de langue française equation et  equation et qu'une personne malveillante arrive à intercepter les deux messages correspondants cryptés equation et equation. À partir de equation et equation l'intercepteur peut facilement obtenir des informations sur equation et  equation du fait des particularités des langues. En effet, puisque:

equation et equation   (61.6)

alors l'intercepteur connaît un résultat simple qui fait intervenir equation et  equation, sans la clé K:

equation   (61.7)

car:

equation    (61.8)

(au besoin faire la table de vérité pour s'en convaincre). Or, si equation et  equation sont dans la même langue, on saura en général, grâce aux redondances des langues (par exemple la lettre "e" apparaît très souvent dans la langue française), retrouver à partir de equation, chacun des deux messages (le travail est quand même laborieux).

Imaginons que nous souhaitons envoyer un tout petit message codé en binaire par 1101 et que nous avons généré une clé aléatoire qui a donné 0101.

Nous avons alors:

equation   (61.9)

et donc:

equation   (61.10)

Évidemment dans ce genre de petites situations on peut deviner sans trop de difficultés M rien qu'en ayant C s'il n'y a comme ici qu'une seule étape de chiffrement. Raisons pour lesquelles il existe des schémas comme nous allons le voir maintenant.

Le problème principal de cette technique est donc la création d'une clé aussi aléatoire que possible. Pour pallier à cela, les mathématiciens font passer la clé par une série de fonctions imbriquées, dont le résultat, après un grand nombre d'itérations, devient "pseudo-aléatoire".

Construire une itération pseudo-aléatoire est une chose, construire une bijection pseudo-aléatoire en est cependant une autre. En effet, il faut pouvoir décrypter le message par la suite, c'est pourquoi l'on a absolument besoin d'un système bijectif (qui a tout élément d'arrivée - message crypté - fait correspondre un unique élément de départ - message décrypté - et inversement).

SCHÉMA DE FEISTEL

Même si les algorithmes de chiffrement de fin du 20ème siècle et du début du 21ème siècle se contentent d'une clé à nombre de bits fini, l'objectif demeure l'élaboration à partir d'un message M d'une suite aléatoire de chiffres, ou, à défaut, qui paraisse aléatoire, que la détention de la clé K permet de déchiffrer. Concrètement, cet objectif demande de construire ou d'identifier une fonction qui, d'une part, fasse correspondre à chaque chiffre de M un chiffre de C qui semble tiré au hasard (mais dont la valeur dépend en réalité de la clé) et, d'autre part, qui autorise le cheminement inverse, c'est-à-dire qu'à partir d'un chiffre de C, on puisse remonter de façon univoque au chiffre correspondant de M (donc une fonction bijective!). Nous désirons ainsi trouver une bijection pseudo-aléatoire.

Dans les années 1950, un mathématicien (Horst Feistel) a montré qu'une fonction pseudo-aléatoire se transforme, par une méthode relativement simple, en bijection. Aujourd'hui, la "méthode de Feistel" est la plus utilisée dans les chiffrements à clé secrète et est aussi à la base du D.E.S. (Data Encryption System). Comment fonctionne-t-elle ?

En voici le principe:

Le message initial à chiffrer a une taille de 2n bits. On sépare le message M en deux blocs, G et D, de longueurs égales (G regroupe les n premiers bits et D les suivants) et on construit la transformation equation qui associe à G et D les nombres S et T telle que:

equation et equation   (61.11)

où le signe equation représente toujours l'opération XOR bit à bit et equation une fonction quelconque, pas nécessairement bijective, de n bits vers n bits qui utilise la clé secrète K.

La transformation equation est bien bijective, car on remonte de façon univoque (unique) à partir de S et de T à G et D par les opérations:

equation et equation   (61.12)

On ne doit évidemment pas s'arrêter-là puisque la partie droite du message, D, n'a pas été chiffrée, elle est simplement passée à gauche. Cependant, comme equation est bijective, on peut réitérer le processus. Un schéma de Feistel où l'on applique n fois la fonction equation est nommé "schéma à n étapes".

exempleExemple:

Nous allons chiffrer par la méthode de Feistel à deux étapes un message constitué de quatre bits (donc 16 possibilités de messages), ce qui vient à construire une bijection de quatre bits vers quatre bits à partir de deux fonctions equation de deux bits vers deux bits. Les fonctions equation possèdent en entrée à la fois le message à chiffrer et la clé secrète. Nous considérerons que pour une certaine clé entrée, ces fonctions sont les suivantes:

Entrée

equation

Sortie

Entrée

equation

Sortie

00

equation

01

00

equation

11

01

equation

11

01

equation

00

10

equation

10

10

equation

00

11

equation

01

11

equation

01

Tableau: 61.2  - Correspondances entrées/sorties de clés par fonctions

Notons que ni equation, ni equation ne sont des bijections (equation). À titre d'exemple, chiffrons le message 1101. G désigne la moitié gauche du message à chiffrer, D la moitié droite:

equation
Figure: 61.2 - Chiffrement de 1101 par la méthode de Feistel

Le résultat est 0010. Nous calculerons l'image des 15 autres messages possibles et nous vérifierions qu'il y ait une correspondance univoque entre chaque message et son image par le schéma de Feistel: nous avons construit une bijection à partir de deux fonctions qui n'en sont pas.

Des résultats théoriques complexes garantissent la sécurité cryptographique des schémas de Feistel à partir de quatre étapes lorsque n est assez grand et lorsque les fonctions equation sont indiscernables de fonctions réellement aléatoires. En pratique, plutôt que d'utiliser quatre étapes et des fonctions equation qui ont l'air aléatoires, on préfère en général utiliser plus d'étapes et des fonctions equation plus simples. Au bout de quelques étapes, la bijection obtenue devient souvent très difficile à distinguer des bijections aléatoires. Et pour des paramètres bien choisis, on ne sait plus du tout comment les distinguer de bijections réellement aléatoires !!!

La plupart des algorithmes à chiffrement à clé secrète utilisés actuellement dans le monde civil sont des schémas de Feistel. En particulier, l'algorithme D.E.S. (Data Encryption System) qui est un schéma de Feistel à 16 étapes comme représenté dans la figure ci-dessous et l'algorithme Triple DES (TDES) qui est un schéma de Feistal à 48 étapes et l'algorithme Blowfish (que nous n'aborderons pas ici).

Remarque: Il y a, par exemple, dans beaucoup de cartes bancaires, une clé DES (ou TDES depuis octobre 2001) qui apporte la preuve de la légitimité de la carte entre le centre de contrôle de la banque et le terminal du commerçant en plus de la partie publique d'une clé RSA pour s'assurer de la saisie du code utilisateur (contrôle fait par une puce interne à la carte dont la fabrication doit alors se faire dans des locaux très sécurisés).

Rigoureusement le schéma de Feistel est un peu autre car il fait intervenir des clés, ce que nous n'avons pas utilisé dans l'exemple cité précédemment. Voici au fait en un peu plus détaillé en quoi consiste ce schéma de Feistel (voir figures ci-dessous).

Principe du schéma: Un message à chiffrer est découpé en blocs de 64 bits, chacun d'eux étant séparé en deux sous-blocs de 32 bits, le bloc de gauche (G) et le bloc de droite (D). À chaque itération, l'ancien bloc droit devient le nouveau bloc gauche et le nouveau bloc droit résulte de la combinaison par l'opération XOR de l'ancien bloc droit, dont les bits sont mélangés par une fonction de confusion, et de l'ancien bloc gauche. On répète l'itération 16 fois.

equation
Figure: 61.3 - Schéma de Feistel un peu plus réaliste

La fonction de confusion (f), qui agit sur les blocs de 32 bits, mélange les bits selon les processus suivants (à droite sur la figure). D'abord, elle transforme le bloc de 32 bits en un bloc de 48 bits par duplication de certains bits (expansion). Ensuite, elle ajoute à ce bloc, une sous-clé de 48 bits (clé de tour) extraite de la clé secrète de 56 bits puis elle transforme chaque ensemble de 6 bits en 4 bits par des transformations locales (transformation S). On aboutit à un bloc de 32 bits que l'on mélange enfin suivant une permutation fixe.

equation
Figure: 61.4 - Schéma de la fonction de confusion

SYSTÈME DE CHIFFREMENT A CLÉ PUBLIQUE

En 1975,  W. Diffie et M.E. Hellman révolutionnaient la science de la cryptographie en démontrant l'existence d'un protocole qui ne pouvait être déchiffré par un intercepteur à moins que ce dernier ne disposât de conséquentes ressources informatiques.  Le plus fascinant dans leur méthode - dont le principe est encore en usage aujourd'hui - c'est que le code utilisé ne nécessite pas le camouflage de la méthode employée et qu'il peut servir à maintes reprises sans aucune modification (principe de Kerckhoffs). Ils ont à l'époque tout simplement créé le concept de cryptographie à clé publique, ou cryptographie asymétrique (dont nous avons déjà fait mention au tout début de ce chapitre), invention qui suscita l'émergence d'une communauté universitaire et industrielle dynamique.

Remarque: Contrairement à ce que l'on pourrait croire, la cryptographie à clé publique n'a pas relégué la cryptographie à clé secrète aux oubliettes, bien au contraire: ces deux types de cryptographie s'utilisent le plus souvent conjointement dans des cryptosystèmes hybrides où l'authentification des clés publiées est assurée par une "autorité de certification".

Avant d'exposer dans le détail le protocole de Diffie-Hellman, rappelons que le protocole d'échange des "clés secrètes" n'était fiable à l'époque (et ne l'est toujours pas aujourd'hui ) puisqu'il voyage/transite entre les interlocuteurs, l'élément permettant de crypter et donc décrypter les messages. De plus, même si rien qu'une seule clé venait à voyager, toute personne ayant une puissance de calculs suffisante pourrait briser le code. D'où la nécessité qu'il y avait de changer (malheur de plus!) périodiquement les clés (cryptopériode). Deux solutions s'offrent alors:

S1. Ne pas échanger de clé (c'est possible mais c'est long comme nous allons le voir dans la figure ci-dessous)

S2. Échanger une clé secrète utilisant une fonction mathématique non inversible ou très difficilement inversible (c'est le protocole de Diffie-Hellman que nous verrons également dans une figure plus bas).

Voyons en quoi consiste la première solution et son désavantage flagrant:

equation
Figure: 61.5 - Principe du chiffrement à clé publique

Explication: Alice et Bernard veulent transmettre un message sur une ligne non sécurisée et sans échanger de clé. Pour cela, Alice met sa lettre dans un coffre qu'elle ferme avec sa clé et l'envoie à Bernard. Ce dernier renvoie le coffre à Alice où il a ajouté son propre cadenas qu'il a fermé avec sa propre clé. Quand Alice reçoit le coffre, elle ôte son cadenas et renvoie à Bernard un coffre qui ne comprend plus que le cadenas de Bernard fermé avec la clé de Bernard. Celui-ci n'a donc plus qu'à ouvrir le coffre pour lire la lettre. Cette opération est sûre et ne nécessite pas d'échange de clé. En revanche, elle requiert plusieurs trajets (l'ensemble est représenté par les 4 premières transactions de la figure ci-dessus).

Le principe de la clé publique doit autoriser des échanges sécurisés, sans clé secrète, en un seul trajet. Bernard distribue largement des exemplaires de son cadenas public. Alice s'en procure un, mais n'importe qui pourrait faire de même. Alice place le message dans le coffre et le ferme avec le cadenas code de Bernard, puis elle lui envoie le coffre (représenté par la cinquième transaction de la figure ci-dessus). En recevant le coffre, Bernard peut ouvrir le coffre, puisque lui seul détient la clé qui ouvre ce cadenas. Le transfert est sûr en un seul voyage. En cryptographie, la clé publique équivaut au cadenas code, qui est disponible par exemple dans des annuaires, tandis que la clé qui ouvre ce cadenas est la clé privée, détenue uniquement par leur propriétaire et qui n'est jamais divulguée. Les clés privée et publique (le "trousseau de clé" comme on dit...) sont construites à partir d'une fonction mathématique supposée "à sens unique".

Voyons donc maintenant la deuxième solution faisant usage de clé publique selon le protocole de Diffie-Hellman:

PROTOCOLE DE DIFFIE-HELLMAN

Comme son nom l'indique, une fonction à sens unique donne un résultat facilement, mais l'opération inverse est très difficile. Trouver de telles fonctions dans le monde mathématique semblait fort ardu aux mathématiciens. Comment imaginer une fonction qui soit à sens unique pour tout le monde, excepté pour son créateur qui peut l'inverser grâce à la connaissance d'une information particulière. Ainsi, W. Diffie et M. Hellman ont été les premiers à proposer publiquement une fonction à sens unique pour résoudre le problème de la mise en accord sur un secret commun. L'idée de base consiste à calculer des valeurs du type:

equation   (61.13)

equation et a sont imposés comme étant des entiers et p un nombre premier.

Les mathématiciens appelant ce genre d'opérations une "exponentiation modulaire" ou "exponentielle discrète" et il est d'usage de noter le corps fini des entiers modulo p (où p est un nombre premier) par equation en l'honneur d'Évariste Galois.

Pour expliciter un tel calcul (pour rappel de ce qui a été vu dans le chapitre de Théorie Des Nombres...), nous élevons un nombre equation à la puissance a, puis nous divisons le résultat par un grand nombre premier p et nous conservons finalement le reste de cette division (opération modulo p).

L'opération inverse est un problème redoutable: même si nous connaissons les valeurs numériques de equation, de p et de equation, il est extrêmement difficile en pratique de retrouver le bon nombre a. Les fonctions à sens unique telles que celle ci-dessus provenant de l'arithmétique modulaire se comportent de manière très irrégulière comme l'atteste le tableau avec l'exemple particulier ci-dessous:

a

equation

equation

0

1
1

1

3
3

2

9
2

3

27
6

4

81
4
5
243
5
6
729
1
7
2187
3
8
6561
2
Tableau: 61.3 - Exemple d'application de l'exponentiation modulaire

Donc même s'il est facile de calculer une exponentielle discrète, il est presque impossible de retrouver le nombre de départ a à partir du résultat et ce particulièrement quand cette fonction modulaire s'applique à des nombres premiers p très grands.

La sécurité de ce protocole est calculatoire. Elle se fonde sur l'hypothèse qu'avec une puissance de calcul et un temps limités, un adversaire ne peut inverser la fonction exponentielle modulaire (en faisant usage des propriétés des logarithmes avec les fonctions exponentielles comme nous l'avons vu dans le chapitre d'analyse fonctionnelle) et donc ne peut trouver le secret a à partir des éléments échangés. Cette difficulté calculatoire est due au fait que le temps de calcul nécessaire à l'inversion d'une fonction à sens unique n'a pas une complexité algorithmique (cf. chapitre de Méthodes Numériques) polynomiale mais exponentielle avec p.

Voyons un exemple schématique:

ALICE Publique (Internet) BERNARD

On choisit un nombre arbitraire commun: equation et un nombre aléatoire commun inférieur à p: equation. On suppose que ces deux valeurs sont secrètes.

Alice choisit un nombre aléatoire secret: equation   Bernard choisit un nombre aléatoire secret: equation

Avec le nombre a Alice génère l'élément public:equation

  Avec le nombre b Bernard génère l'élément public:equation
Envoi du résultat à Bernard:equation equationequation

equation

equation equationequation

Envoi du résultat à Alice:equation

Le secret partagé est alors:
equation

  Le secret partagé est alors:
equation

equationequation Les échanges sont alors chiffrés avec la clé secrète K equationequation

Tableau: 61.4  - Exemple d'échange de clé entre Alice et Bernard

Alice et Bernard ont calculé le même secret commun: 493. On se sert de 493 pour chiffrer les données échangées (dans la pratique, on utilise des nombres beaucoup plus grands). L'espion n'est supposé pouvoir intervenir qu'après l'échange du choix commun de p et equation.

Rappel: La clé K est obtenue par le fait que l'opération puissance est compatible avec la relation d'équivalence modulo p (cf. chapitre de Théorie Des Nombres) telle que:

equation   (61.14)

exempleExemple:

equation, alors qu'avec equation nous avons equation alors que equation.

Ainsi, puisque equation, le second modulo n'a plus de sens donc nous pouvons écrire:

equation   (61.15)

de même:

equation   (61.16)

et donc:

equation   (61.17)

Malgré ces précautions, des experts ont établi au début du 21ème siècle un record en utilisant un nouvel algorithme, ils ont réussi à inverser la fonction exponentielle modulaire pour un nombre p de 120 chiffres (environ 400 bits), à l'aide d'un ordinateur intégrant quatre processeurs de 525 MHz. Ce record montre que la sécurité du protocole dépend grandement des progrès constants réalisés dans le domaine de la complexité algorithmique.

L'astucieux schéma de Diffie-Hellman reste un schéma de principe. Son principal inconvénient est qu'il ne permet pas d'assurer les services de sécurité classiques: authentification des deux intervenants, contrôle de l'intégrité de la clé et anti-rejeu ( vérification qu'une information déjà transmise ne le soit pas à nouveau). Il s'ensuit qu'un attaquant peut, par exemple, usurper l'identité d'Alice en remplaçant l'élément public d'Alice par son propre élément public. Pour pallier à cet inconvénient, des versions sécurisées de ce protocole générique ont été publiées, par exemple un protocole nommé "STS" (Station To Station) qui utilise notamment la signature électronique pour assurer l'authentification des intervenants (voir plus loin). Cette stratégie est à la base de la connexion Internet sécurisée (IPSec).

Le protocole de Diffie-Hellman a ouvert la voie à toute une série d'algorithmes, celui du chiffrement à clé publique étant le premier. L'idée était de rompre la symétrie du chiffrement et du déchiffrement en utilisant les fonctions à sens unique.

SYSTÈME R.S.A.

Curieusement, le système de chiffrement R.S.A. le premier apparu dans la littérature est conceptuellement assez éloigné du protocole de Diffie-Hellman: il n'utilise pas l'exponentielle discrète, mais la factorisation des grands nombres. Ce système à clé publique a été inventé en 1977 par Ron Rivest, Adi Shamir et Leonard Adleman. Vite devenu un standard international, la technique R.S.A. a été commercialisée par plus de 400 entreprises et nous estimons que plus de 400 millions de logiciels l'utilisent. Elle est implémentée dans les navigateurs Web, comme Netscape Navigator, Microsoft Internet Explorer ou encore dans certaines cartes à puce bancaires, comme les cartes VISA.

Le système RSA est fondé sur la difficulté de factoriser des grands nombres et la fonction à sens unique utilisée est une fonction "puissance". Le protocole de chiffrement R.S.A. se décompose en trois phases:

1. Création des clés (publiques et privées)

2. Chiffrement à l'aide de la clé publique du destinataire

3. Déchiffrement à l'aide de la clé privée

Ce concept repose sur un théorème fameux appelé "théorème d'Euler" (rien à voir avec le théorème du même nom vu dans les chapitres de Théorie Des Graphes ou Formes Géométriques). Voyons de quoi il s'agit (attention c'est relativement long!).

THÉORÈME D'EULER

Avant de voir en quoi consiste le théorème d'Euler, il nous faut définir deux éléments qui y sont inclus. Outre le concept de congruence que nous avons déjà étudié dans le chapitre de Théorie des Nombres, il reste une fonction spéciale appelée "indicatrice d'Euler" et définie en toute généralité par:

equation   (61.18)

Autrement dit, la fonction equation du nombre entier m a pour résultat un nombre n strictement inférieur à m, donné par le nombre d'éléments compris entre 1 et m dont le p.g.c.d. (cf. chapitre de Théorie Des Ensembles) avec m est 1. Nous avons déjà donné un exemple pratique de l'utilité de cette fonction indicatrice dans le chapitre de Théorie Des Nombres dans le cadre des systèmes réduits de résidus et qui sont au centre de la démonstration du théorème d'Euler.

Ce qui peut encore se formuler sous la forme suivante: l'indicateur equation du nombre entier m est défini comme le nombre d'entiers positifs inférieurs ou égaux à m et premiers avec m.

Cette fonction a donc la propriété remarquable de compter le nombre d'entiers positifs plus petits que m et "relativement premiers" (c'est-à-dire qui ont le p.g.c.d. égal à 1) avec m.

Voici quelques valeurs de 0 à 19:

equation(m) 0 1 2 3 4 5 6 7 8 9
0+   1 1 2 2 4 2 6 4 6
10+
4
10
4
12
6
8
8
16
6
18
Tableau: 61.5  - Valeurs de l'indicatrice d'Euler

P1. Nous remarquons la propriété (triviale) de cette fonction lorsque nous notons un nombre premier (se rappeler que 1 n'est pas un nombre premier!) quelconque par la lettre p alors:

equation   (61.19)

Remarque: Cette fonction se trouve parfois dans la littérature sous la dénomination "indicateur d'Euler" au lieu de "fonction phi d'Euler".

P2. L'indicatrice d'Euler peut s'écrire aussi sous la forme suivante si p et q sont premiers (il s'agit du cadenas du système R.S.A qui est plus compliqué que la simple multiplication de p et q):

equation   (61.20)

cette dernière relation peut se vérifier aisément (sans démonstration) en prenant quelques valeurs du tableau précédent.

Ceci fait, soit equation (le p.g.c.d. de a et m), le "théorème d'Euler" dit que si m est un entier naturel et a est relativement premier avec m alors nous avons:

equation   (61.21)

dans laquelle nous voyons apparaître l'indicatrice d'Euler définie juste plus haut. C'est une relation assez surprenante. Voyons si elle marche avec 7 et 2 qui sont premiers entre eux:

equation   (61.22)

le reste étant donc bien 1 quand on fait 64 modulo 7.

Démonstration:

Rappelons d'abord (cf. chapitre de Théorie Des Nombres) qu'un système réduit de résidus modulo m est un ensemble d'entiers equation qui satisfont les trois propriétés:

P1.  equation

P2.  equation n'est pas congru equation modulo m lorsque equation

P3. Chaque entier x relativement premier avec m est congru à un certain equation modulo m.

Par exemple, l'ensemble {1,5} est un système réduit de résidus modulo 6 ou autre exemple; {1,2,3,4,5,6} est un système réduit de résidus modulo 7. Nous vérifions également pour le premier exemple, que 1 n'est pas congru 5 modulo 6 (effectivement, 6 ne divise pas (5-1)) et que 5 qui est relativement premier à 6 est congru à lui-même.

Pour le deuxième, exemple, nous remarquons que le cardinal de l'ensemble de résidus correspond à la valeur de l'indicateur d'Euler pour le nombre 7.

Ainsi, soit  equation un système réduit de résidus modulo m. Nous avons besoin pour la démonstration du théorème d'Euler, de démontrer au préalable que equation est aussi un système réduit de résidus modulo m.

Remarque: Comme nous en avons déjà fait mention dans l'exemple précédent, vous pouvez observer que le cardinal de l'ensemble des résidus correspond, pour un modulo m premier donné, au résultat défini par la propriété P1 de la fonction equation d'Euler. Cette propriété n'est à ce jour qu'une "conjecture", c'est-à-dire une supposition fondée sur des probabilités (car non démontrée paraît-il!).

Pour cela, rappelons-nous que par la propriété d'un système réduit:

equation 

et par hypothèse:

equation   (61.23)

alors nous voulons démontrer que:

equation    (61.24)

est aussi satisfait.

Posons pour cela equation (par tradition...). Nous avons alors puisque equation que equation et equation et identiquement pour equation  que equation et que equation. Maintenant si d divise bien a ou equation dans ce cas nous avons que equation ou autrement equation. Donc equation et equation ce qui nous permet d'écrire:

equation   (61.25)

Revenons à notre théorème d'Euler... si vous suivez toujours... Nous venons de démontrer qu'il y a bijection entre les deux ensembles de résidus. C'est-à-dire que pour chaque résidu equation du système réduit modulo m, nous aurons un résidu equation du système réduit modulo m selon la propriété fondamentale de la congruence qui rappelons-le dit que: nous pouvons multiplier les deux membres d'une congruence par un même nombre entier et il restera congru modulo m et modulo m multiplié par ce nombre entier.

exempleExemple:

Prenons:

equation    (61.26)

effectivement:

equation    (61.27)

car le reste de la division de 30 par 6 est bien nul. Si nous prenons par exemple:

equation    (61.28)

alors nous avons également:

equation    (61.29)

et le reste est aussi nul...

Petit rappel sur la bijection (cf. chapitre de Théorie Des Ensembles): nous disons que nous avons une bijection, si à chaque élément d'un ensemble de départ correspond un et un seul élément dans l'ensemble d'arrivée (s'il y avait pour chaque homme sur Terre une femme - à proportions égales donc - il y aurait bijection entre l'ensemble des Hommes et des Femmes).

Bref, comme il y a bijection entre les deux ensembles de résidus, nous pouvons écrire:

equation   (61.30)

exempleExemple:

L'ensemble {1,5} est un système réduit de résidus modulo 6 comme nous l'avons déjà vu. Nous avons donc:

equation   (61.31)

Nous avons alors:

equation   (61.32)

Si nous prenons un a tel que equation, par exemple equation car effectivement equation, alors:

equation    (61.33)

car equation. Effectivement 6 divise bien 30 avec un reste nul.

Donc revenons à notre bijection qui peut s'écrire par les règles élémentaires de l'algèbre:

equation   (61.34)

Puisque:

equation   (61.35) 

(vous pouvez vérifier mais cela découle de la définition même d'un ensemble de résidus!), nous sommes bien obligés de conclure que:

 equation   (61.36)

et de toute façon, même si cela ne vous semble pas évident, vous n'avez qu'à multiplier chacun des membres de l'égalité de la congruence par:

equation   (61.37)

comme nous l'autorise une des propriétés intrinsèque de la congruence démontrée précédemment.

equationC.Q.F.D.

Cet interlude théorie étant fait, considérons un nombre N dont nous souhaitons décider s'il est premier ou non.

Nous savons d'après le théorème d'Euler et de la propriété P1 de l'indicateur d'Euler, que si N est un nombre premier et si equation, où equation, alors:

equation   (61.38)

qui est appelé le "petit théorème de Fermat".

Remarque: Cette relation découle des propriétés que nous avons exposées lors de notre démonstration du théorème d'Euler:

equation   (61.39)

et de la propriété P1 de la fonction equation pour un nombre p premier:

equation   (61.40)

Le petit théorème de Fermat est cependant également valable pour quelques nombres N qui ne sont pas premiers. Mais les nombres qui vérifient ça sans être premiers sont rares, et du coup ça vaut la peine de déclencher un algorithme plus sophistiqué pour savoir si N est réellement premier ou non (disons que dans ce cas, N est un bon candidat à la primalité et est alors appelé "nombre pseudo-premier"). Pour tester si le nombre, le cas échéant N non-premier est "suffisamment premier", on essaie avec un algorithme de tester le petit théorème de Fermat pour un nombre maximal de equation avec equation.

D'après la propriété de la congruence (voir plus haut), nous avons également:

equation   (61.41)

Nous pouvons appliquer ce dernier théorème sur un nombre N à propos duquel nous aimerions savoir au mieux s'il est premier ou non.

Il existe une grande quantité d'autres méthodes non optimales pour déterminer si N est premier; dont les essais préliminaires de division par 2, 3, 5, 7, 11 et des nombres premiers petits jusqu'à equationselon la méthode du crible d'Ératosthène qui est la plus connue dans les petites écoles.

Remarque: En fait, avec l'aide d'un ordinateur assez puissant, nous pouvons décider si un nombre naturel de l'ordre de equation (10 suivi 300 zéros) est premier ou non en l'espace de quelques minutes voir secondes. Ce qu'il est important de savoir, c'est que, étant donné un nombre naturel N, on peut décider en relativement peu de temps s'il est premier ou non, sans pour autant connaître ses facteurs premiers. 

Cependant, selon le théorème fondamental de l'arithmétique nous avons que:

Tout nombre naturel equation peut s'écrire comme un produit de nombres premiers, et cette représentation est unique, à part l'ordre dans lequel les facteurs premiers sont disposés.

Démonstration:

Si n est premier, alors la preuve est terminée. Supposons que n n'est pas premier et considérons l'ensemble:

equation   (61.42)

Alors, equation et , puisque n est supposé composé, nous avons que equation, D'après le principe du bon ordre (tout ensemble non vide contient un plus petit élément), D possède un plus petit élément equation qui est premier, sans quoi le choix minimal de equation serait contredit. Nous pouvons donc écrire equation. Si equation est premier, alors la preuve est terminée. Si equation est composé, alors nous répétons le même argument que précédemment et nous en déduisons l'existence d'un nombre premier equation et d'un entier equation tels que equation. En poursuivant ainsi, nous arrivons forcément à la conclusion que equation sera premier.

equationC.Q.F.D.

Donc finalement nous avons bien démontré qu'un nombre quelconque est décomposable en facteurs de nombres premiers à l'aide du principe du bon ordre. Il existe dans l'ensemble des nombres naturels, certains qui peuvent s'exprimer, ou qui s'expriment tout court, uniquement par 2 facteurs premiers notés traditionnellement p et q. Ce sont ces nombres que nous utilisons en cryptographie à clé publique selon le protocole R.S.A.

Remarque: Nous ne connaissons pas à ce jour de loi qui permette de calculer facilement et rapidement le n-ième facteur premier equation d'un nombre. En fait, même avec les ordinateurs les plus puissants d'aujourd'hui, il faudrait plusieurs années pour arriver à trouver les deux facteurs premiers p et q d'un nombre equationp et q sont de l'ordre de equation chacun. Et il semble peu probable que l'on découvre dans un avenir proche un algorithme assez efficace pour améliorer de façon appréciable ce temps de calcul. Notons qu'il est possible de déterminer en moins de 5 minutes (en 2002) si un nombre de 200 chiffres est premier ou non. Cependant, pour factoriser un nombre de 200 chiffres en deux nombres premiers, il faudrait au moins 100 ans. Chose merveilleuse: les théories qui permettent ces exploits sont très profondes et ont été élaborées en partie il y a longtemps dans un cadre très différent.

Le fait qu'il soit beaucoup plus difficile de trouver les facteurs premiers d'un nombre N que de découvrir si N est premier ou composé, est précisément ce qui a permis d'élaborer cette méthode très ingénieuse de codage et décodage de messages selon le protocole R.S.A.

exempleExemple:

Considérons maintenant un groupe d'individus qui se transmettent régulièrement des messages par courrier électronique et pour lequel il est important que les messages ne soient connus que de l'expéditeur et du destinataire. Alors, le membre du groupe (ici Alice) qui souhaite recevoir des informations cryptées, se trouve deux nombres premiers p et q très grands de l'ordre de equation. Pour trouver de si grands nombres premiers, nous choisissons au hasard un nombre de 100 chiffres et nous vérifions par un des algorithmes connus s'il est premier ou non et nous répétons l'expérience jusqu'à ce que nous obtenions ainsi un nombre premier. Une fois ceci fait avec ces deux nombres premiers, nous calculons l'expression:

equation   (61.43)

appelée "modulus".

Ensuite, Alice qui souhaite recevoir les informations cryptées (qui est la seule en possession du nombre n pour l'instant) choisit un entier positif a tel (p.g.c.d.) que:

equation   (61.44)

Donc a (souvent noté e dans la littérature) est un entier premier avec equation appelé parfois le "générateur".

Et comme:

equation   (61.45)

par conséquent, par essais répétés, il est facile de trouver un tel nombre a. Le membre principal, trouve donc un n et un a pour son contact, qu'il lui envoie sans aucune protection. Car, même dans le cas où il y aurait d'éventuels intercepteurs à l'affût sur la ligne, il leur sera extrêmement difficile de retrouver les facteurs premiers de n dans un laps de temps relativement bref.

Supposons qu'une agence secrète souhaite recevoir un message d'un de ses agents. 

L'agence envoie la clé publique, définie donc par le couple:

equationequation   (61.46)

à l'agent.

L'agent reçoit la clé publique et souhaite envoyer le message "déclencher l'opération rouge". Pour ce faire, l'agent transforme d'abord le message en chiffres en utilisant la convention que chaque lettre est remplacée par sa position correspondante dans l'alphabet en commençant à compter à partir de 01 (le caractère "espace" sera chiffré "27").

Ainsi le message clair noté M par la suite devient:

equation   (61.47)

Point technique: il faut que M et n n'aient pas de diviseur commun autre que 1 (sinon quoi, un éventuel espion pourrait réduire le problème de deux très grands nombres difficilement manipulables à celui de plus petits nombres, plus facilement manipulables). Sinon quoi, on ajoute à la fin de M des chiffres sans valeur, comme 01 (par exemple), pour finalement avoir M et n sans diviseur commun autre que 1. On peut aussi briser M en morceaux equation dont le nombre de chiffres n'excède pas 99 (rappelez-vous que nous avions fixé une limite inférieure d'une puissance de 100 pour p et q et qu'il suffirait donc qu'un des deux nombres premiers soit 1 et l'autre exactement un nombre avec un exposant 100 pour être à limite du nombre n comportant alors au pire 100 chiffres), auquel cas on aura toujours: 

equation  (61.48)

On découpe M en morceaux, chacun étant plus petit que n:

equation  (61.49)

et on travaille successivement avec chaque morceau equation du message.

On considère la puissance a de equation, c'est-à-dire equation. On remplace equation par le nombre equation, qui est le reste de la division par n du nombre equation. On procède de même pour tous les autres morceaux equation tels que:

equation   (61.50)

L'agent envoie alors le message codé à l'agence:

equation  (61.51)

Un intercepteur (non-mathématicien) du message codé et de la clé publique, connaissant l'algorithme de chiffrement, aurait donc à résoudre le problème d'une équation à deux inconnues (équation obtenue simplement à partir de l'expression mathématique du chiffrement): 

equation   (61.52)

Problème évidemment indéterminé !

Pour voir comment l'agence décrypte le message, on a besoin d'un outil mathématique supplémentaire.

Rappelons que l'agence choisit  a de telle que sorte que equation,  ce qui implique, d'après le théorème de Bézout (cf. chapitre de Théorie Des Nombres), que si a et equation sont premiers entre eux (que leur plus grand diviseur commun est 1) il existe des entiers x et y tels que (on peut supposer que equation, auquel cas equation):

equation  (61.53)

ou autrement écrit:

equation   (61.54)

C'est ainsi que nous allons déterminer la valeur de x (il faut utiliser des algorithmes pour trouver la solution x à cette équation).

Ce qui signifie:

1. Que si a est premier avec equation alors par les propriétés de la congruence il l'est également avec p-1 et q-1.

2. Que a est inversible modulo equation

Effectivement, car:

equation  (61.55)

et d'après la définition de la congruence (equation) nous avons effectivement:

equation   (61.56)

puisque equation divise le membre de droite de equation et donc de par l'égalité, le membre de gauche.

Seule l'agence, qui reçoit le message, peut facilement calculer le nombre equation utilisé ci-dessus. Car pour cela, il faut pouvoir calculer la valeur de la fonction equation indicatrice d'Euler et donc connaître p et q.

Si equation est le message (valeur numérique) d'origine et equation est le message (valeur numérique) codé reçu, alors nous avons la relation suivante:

equation   (61.57)

Ce qui est complètement logique puisque la différence equation, où rappelons-le, equation est le reste de la division de equation par n, ne peut donc qu'être divisible par n.

L'agence reçoit donc le message codé equation et élève à la puissance x les nombres equation et obtient ainsi le message initial.

En effet, elle va appliquer pour chaque equation la propriété mathématique suivante de la congruence:

equation   (61.58)

La clé privée (permettant de décrypter le message et qui peut être connue facilement uniquement par l'agence) est donc définie par le couple:

equationequation   (61.59)

Explications:

Nous avions déjà montré que:

equation  (61.60)

et selon la propriété de symétrie de la congruence (cf. chapitre de Théorie Des Nombres), nous pouvons écrire:

equation   (61.61)

Effectivement:

equation  (61.62)

selon la deuxième principale propriété de la congruence qui dit que l'on peut élever à une même puissance les deux membres d'une congruence. Ce qui nous donne aussi directement:

equation   (61.63)

puisque nous avons démontré précédemment que:

equation  (61.64)

donc que:

equation   (61.65)

Reste à démontrer que:

equation   (61.66)

où l'on peut écrire equation sous la forme:

 equation   (61.67)

Or, rappelez-vous que nous avons démontré le théorème d'Euler:

equation   (61.68)

et qu'une des propriétés de la congruence nous donne le droit d'élever à une puissance quelconque les deux membres de la congruence tel que:

equation   (61.69)

Mais comme 1 élevé à n'importe quelle puissance fait 1, nous avons:

equation   (61.70)

Cette dernière relation nous permet donc de vérifier que l'on peut s'autoriser à écrire:

equation   (61.71)

Puisque les deux membres de gauche sont bien modulos n.

Donc si on reprend tout ça, l'agence reçoit un morceau equation et l'élève par automatisme à la puissance x pour obtenir un nombre qui selon elle devrait être le equation véritable. Pour en être sûr, elle applique la vérification imparable:

equation   (61.72)

Il est facile de voir que tout intercepteur ne peut décoder et en plus vérifier si le décodage est bien le bon, car pour cela il devrait connaître la valeur de x, laquelle à son tour dépend de equation, qu'il ne connaît pas non plus, parce qu'il ne connaît pas les facteurs premiers de n.

Il est d'usage de dire que le système RSA utilise les nombres p, q (secrets), n (publique), a (publique) et x (secret). Le tout se résumant au triplet n, a, x noté parfois dans la littérature n, e, d.

equation
Figure: 61.6 - Principe du chiffrement à clé publique RSA

Et une petite application pratique avec Maple 4.00b:

> #initialisation du générateur aléatoire de Maple 4.00b
> randomize():
> #définition de la taille souhaitée du modulus (c'est un nombre pair)
> t:=30:
> #génération de deux entiers de t/2 bits
> x:=rand(2^(t/2-1)..2^(t/2))();
> y:=rand(2^(t/2-1)..2^(t/2))();
> #calcul des nombres premiers qui suivent
> p:=nextprime(x);
>q:=nextprime(y);
> #modulus public de la clé RSA
> n:=p*q;
> phi:=(p-1)*(q-1);
> #on choisit a empiriquement
> a:=65537;
> #on vérifie qu'il est premier avec phi
> igcd(a,phi);
> #on calcule l'inverse de a modulo phi
> x:=1/a mod phi;
> #on choisit un message comme étant 1234
> m:=1234;
> # on code
> c:=m&^a mod n;
> # on décode
> c&^x mod n;

Suite à la demande d'un lecteur voici un résumé littéral de ce que nous avons vu jusqu'à maintenant pour les premières étapes de l'algorithme ci-dessus:

1) Nous choisissons p et q premiers suffisamment grands:

equation   (61.73)

nous avons alors:

equation   (61.74)

2) Nous calculons l'indicatrice d'Euler:

equation   (61.75)

3) Nous choisissons le générateur a tel que:

equation   (61.76)

et pour cela nous prendrons a = 5. Le couple (n, a) est la clé publique (peut être distribuée à tout le monde pendant un temps déterminé).

4) Ensuite, nous calculons:

equation   (61.77)

Donc le couple (x, a) est la clé privée (à garder secrète).

Pour des raisons de sécurité, la cryptographie à clé publique est utilisée conjointement avec la cryptographie à clé secrète. Par exemple, au jour de l'écriture de ces lignes, le protocole SSL pour les pages Internet utilise le RSA pour échanger une clé secrète (système symétrique) et crypte ensuite les données grâce à un algorithme symétrique classique.

Signalons en terminant cette brève présentation du codage des messages, que le gouvernement américain surveille de très près les activités des mathématiciens qui travaillent sur la factorisation des grands nombres. En effet, si un de ceux-ci arrivait à trouver un algorithme permettant de factoriser en peu de temps un nombre de deux cents chiffres (supérieur à 524 bits non signé), cela mettrait en péril le caractère secret de plusieurs communications d'ordre militaire. Cette surveillance a d'ailleurs soulevé aux États-Unis un mouvement de protestation de la part des hommes de sciences, qui voient ainsi brimer leur liberté professionnelle (Notices of American Mathematical Society, janvier 1983).

Pour information technique, le logiciel PGP (Pretty Good Privacy) du MIT, utilise un système de chiffrement RSA.

FONCTIONS DE HACHAGE

Une fonction de hash (anglicisme) ou fonction de hachage est une fonction qui associe à un grand ensemble de données un ensemble beaucoup plus petit (de l'ordre de quelques centaines de bits) qui est caractéristique de l'ensemble de départ . Cette propriété fait qu'elle est très utilisée en informatique, en particulier pour accéder rapidement à des données grâce à des "tables de hachage". En effet, une fonction de hachage permet d'associer à une chaîne de caractères un entier particulier. Ainsi, si nous connaissons l'empreinte des chaînes de caractères stockées, nous pouvons rapidement vérifier si une chaîne se trouve ou non dans cette table (en O(1) si la fonction de hachage est suffisamment bonne). Les fonctions de hachage sont aussi extrêmement utiles en cryptographie pour accélérer le cryptage.

Les 2 algorithmes de condensation les plus utilisés sont le "SHA" (Secure Hash Algorithm) qui calcule un résumé de 160 bits, et le MD5 (Message Digest 5 - Run Rivest 1992), qui calcule un résumé de 128 bits nommé "Message Digest".

FONCTION DE CONDENSATION MESSAGE DIGEST MD5

Cet algorithme est (était) surtout utilisé pour les signatures numériques (notion utilisée, lors de la validation de certificats d'authenticité comme nous le verrons plus loin).

Voici les différentes étapes de son fonctionnement:

Étape 1: Complétion

Le message est constitué de b bits. On complète le message par un 1, et suffisamment de 0 pour que le message étendu ait une longueur multiple de 512 bits. Après ce traitement initial, on manipule le texte d'entrée par blocs de 512 bits divisés en 16 sous-blocs M[i] de 32 bits.

Étape 2: Initialisation

On définit les variables de chaînage de 32 bits A, B, C et D initialisées ainsi (les chiffres sont hexadécimaux):

A=01234567, B=89ABCDEF, C=FEDCBA98, D=76543210

On définit aussi 4 fonctions non linéaires F, G, H et I, qui prennent des arguments codés sur 32 bits, et renvoient une valeur sur 32 bits, les opérations se faisant bit à bit.

F(X,Y,Z) = (X AND Y) OR (NOT(X) AND Z)
G(X,Y,Z) = (X AND Z) OR (Y AND NOT(Z))
H(X,Y,Z) = X XOR Y XOR Z
I(X,Y,Z) = Y XOR (X OR NOT(Z))

Ce qu'il y a d'important avec ces 4 fonctions est que si les bits de leurs arguments X,Y et Z sont indépendants, les bits du résultat le sont aussi.

Étape 3: Calcul itératif

La boucle principale a 4 rondes qui utilisent chacune une fonction non linéaire différente (d'où le fait qu'il y en ait 4...). Chaque ronde consiste donc en 16 exécutions d'une opération (car 16 sous-blocs).

Chaque opération calcule une fonction non linéaire de trois des variables A, B, C et D, y ajoute un sous-bloc M[i] du texte à chiffrer, une constante s prédéfinie (codée sur 32 bits) et effectue un décalage circulaire vers la gauche, d'un nombre variable n de bits. Voici l'exemple pour A:

- A = B + A + F(B,C,D) + M[i] + s | décalé circulairement de n vers la gauche

- A = B + A + G(B,C,D) + M[i] + s | décalé circulairement de n vers la gauche

- A = B + A + H(B,C,D) + M[i] + s | décalé circulairement de n vers la gauche

- A = B + A + I(B,C,D) + M[i] + s | décalé circulairement de n vers la gauche

Cette nouvelle valeur de A est ensuite sommée avec l'ancienne.

Étape 4: Ecriture du résumé

Le résumé sur 128 bits est obtenu en mettant bout à bout les 4 variables de chaînage A, B, C, D de 32 bits obtenues à la fin de l'itération.

La fonction MD5 n'est pas sûre et pas unique (deux entrées différentes peuvent donner la même signature: nous parlons alors de collision). Cependant, la fonction MD5 reste encore largement utilisée comme outil de vérification lors des téléchargements et l'utilisateur peut valider l'intégrité de la version téléchargée grâce à l'empreinte. Ceci peut se faire avec un programme comme md5sum pour MD5 et sha1sum pour SHA-1. (cf. chapitre de Codes Correcteurs).

Voici l'empreinte (appelée abusivement "signature") obtenue sur une phrase (que nous avons pris sans accents):

MD5("Wikipedia, l'encyclopedie libre et gratuite") = d6aa97d33d459ea3670056e737c99a3d

En modifiant un caractère, cette empreinte change radicalement:

MD5("Wikipedia, l'encyclopedie libre et gratuitE") = 5da8aa7126701c9840f99f8e9fa54976

Très concrètement, la vérification de l'empreinte ou somme de contrôle MD5 peut être réalisée de la façon suivante: lors du téléchargement d'un programme, nous notons la série de caractères indiquée sur la page de téléchargement. Quand ce téléchargement est terminé, nous lançons un des utilitaires susmentionné.

FONCTION DE CONDENSATION SECURE HASH ALGORITHM SHA-1

Le SHA-1 est (était) utilisé en concurrence du MD5 pour les signatures numériques (Digital Signature Algorithm) comme spécifié par le Digital Signature Standard (DSS). Pour un message de longueur inférieure à 264, le SHA-1 génère un condensé de 160 bits du message appelé "hash". À nouveau, à l'identique du MD5, une modification infime du message d'origine doit avoir une grosse répercussion sur le message condensé et il ne doit pas exister de Message Digest identique pour deux messages d'origine différente.

Comme pour le MD5, on travaille sur des messages dont la longueur est un multiple de 512 bits.

Étape 1: Complétion

Si le message n'a pas une longueur de 512 bits, on rajoute autant de 1 que nécessaire à la fin de ce dernier. Les derniers 64 bits du bloc de 512 bits sont utilisés pour définir la longueur d'origine du message. On transforme ensuite le bloc de 512 bits en sous-blocs M[ i ]  de 32 bits chacun exprimés en hexadécimal (equation).

Étape 2: Initialisation

Comme pour le MD5, on définit cette fois 80 variables de chaînage de 32 bits K[i] initialisées ainsi (les chiffres sont hexadécimaux):

K[t] =01234567 |equation
K[t] =89ABCDEF | equation
K[t] =FEDCBA98  | equation
K[t] =76543210 | equation

On définit aussi 80 fonctions non linéaires F[0],F[1] , F[2], ..., F[79]  qui prennent des arguments codés sur 32 bits, et renvoient une valeur sur 32 bits, les opérations se faisant bit à bit.

F[t](X,Y,Z) = (X AND Y) OR (NOT(X) AND Z) | equation
F[t] (X,Y,Z) = (X XOR Y) XOR D | equation
F[t] (X,Y,Z) = (X AND Y) OR (X AND Z) OR (Y AND Z) | equation
F[t] (X,Y,Z) = X XOR Y XOR Z | equation

Ce qu'il y a d'important avec ces 80 fonctions est que si les bits de leurs arguments X,Y et Z sont indépendants, les bits du résultat le sont aussi.

Étape 3: Calcul Itératif

L'itération utilise deux buffers, chacun consistant en l'utilisation de 5 variables de chaînage. Les variables de chaînage du premier buffer sont notées A, B, C, D, E. Le second paquet de 5 contient les variables de chaînage notées H[0], H[1], H[2], H[3], H[4].

Par ailleurs, notons Sn le décalage circulaire de n bits vers la gauche

Voici l'algorithme SHA-1:

Pour t = 16 à 79 faire
     M[t] = S1(M[t-16] XOR M[t-15] XOR M [t-14] XOR M [t-13])
Fin Pour
A = H[0]; B = H[1]; C = H[2]; D = H[3]; E = H[4]
Pour t = 0 à 79 faire
     TEMP = S5(A) + F[t](B,C,D) + E + M[t] + K[t]
     E = D; D = C; C = S30(B); B = A; A = TEMP
Fin Pour
H[0] = H[0] + A; H[1] = H[1] + B; H[2] = H[2]  + C, H[3] = H[3]  + D, H[4] = H[4]  + E

Après l'exécution de cet algorithme, on obtient un message 160 bits (5x32) représentés par les 5 variables de chaînage H[0], H[1], H[2], H[3], H[4].

CERTIFICATS D'AUTHENTIFICATION

Nous avons vu lors de la cryptographie à clé publique et à clé secrète, qu'il subsistait une faille dans le système de transmission des clés au début de la communication.

Ainsi dans les deux systèmes, la faille réside dans le fait que quelqu'un de malveillant puisse se substituer à l'interlocuteur réel et envoyer ainsi soit une fausse clé secrète, soit une fausse clé publique (en fonction des cas).

Ainsi, un certificat d'authenticité permet d'associer une clé à une entité (une personne, une machine, ...) afin d'en assurer la validité (l'association à la "vraie personne"). Le certificat est en quelque sorte la carte d'identité de la clé ou la "signature numérique", délivrée par un organisme appelé "autorité de certification".

La technologie faisant usage des signatures numériques fait partie d'un ensemble plus vaste connu sous l'acronyme "PKI" (Public Key Infrastructure). L'ensemble se déroule moyennant des certificats que vous pouvez obtenir auprès d'une Autorité de certification (voir exemple plus bas). Lorsque vous demandez votre certificat, votre ordinateur crée la paire de clefs composées d'une clé privée (la jaune sur le schéma) et une clé publique (la noire). Votre clé privée est secrète et c'est seulement vous qui y avez accès alors que la clé publique est librement disponible pour tout le monde. Votre clef publique sera attachée à votre certificat que vous obtiendrez de la part de l'autorité de certification à qui vous avez remis votre demande de certificat.

Le PKI (sur lequel est basée la connexion IPSec) vise essentiellement 4 points importants:

1. l'authentification (le destinataire de votre courriel doit pouvoir vérifier que c'est bien vous qui avez envoyé l'objet et pas un autre). Une personne peut intercepter votre mail, extraire votre mot de passe, etc.

2. l'intégrité (s'assurer que le contenu n'a pas été changé en chemin).

3. la confidentialité (s'assurer que le contenu n'est lisible que par le destinataire).

4. la non-répudiation (découlant des 3 premiers points)

L'autorité de certification est chargée de délivrer les certificats, de leur assigner une date de validité (1 jour), ainsi que de révoquer éventuellement des certificats avant cette date en cas de compromission de la clé.

Les certificats sont de petits fichiers divisés en deux parties:

- La partie contenant les informations

- La partie contenant la signature de l'autorité de certification (voir Internet Explorer)

La structure des certificats est normalisée par le standard X.509 de l'Unition Internation des Télécommunication (UIT), qui définit les informations contenues dans le certificat:

- Le nom de l'autorité de certification (VeriSign par exemple)

- Le nom du propriétaire du certificat (la banque UBS par exemple)

- La date de validité du certificat (1 jour à partir de la date courante)

- L'algorithme de chiffrement utilisé (MD5RSA)

- La clé publique du propriétaire

Voici un très bon exemple:

Pour signer le message que vous expédiez (point (5) sur le schéma ci-dessous), il suffit en effet de lui appliquer une fonction de hachage (point (1)) qui produit un résumé (code haché) du message (les algorithmes de hachage les plus connus sont le MD5 (128 bits (Message Digest 5)) et le SHA-1 (160 bits (Secure Hash Algorithm 1)). Le résumé obtenu est propre à chaque message, à l'image d'une empreinte digitale. Cet algorithme assure que si un seul bit du texte original est modifié et si l'on refaisait un nouveau hachage (empreinte), ce dernier serait radicalement différent du premier. Le code haché peut ensuite être chiffré à l'aide de votre clé privée et annexé à votre message (points (2) et (3)). C'est ce code qui constitue la signature numérique. Le destinataire du message (point (6)) peut ensuite vérifier que vous en êtes bien l'expéditeur en déchiffrant la signature numérique (point (7)), au moyen de votre clé publique (point (8)), que vous lui avez transmis automatiquement avec le mail (point (4)), pour obtenir le code haché (point (9)). Le destinataire applique ensuite la même fonction de hachage au message reçu (point (10) sur le schéma); si les deux codes (points 11 et 12 sur le schéma) sont identiques, vous êtes bien l'expéditeur du message (authentification) et le message n'a pas été altéré (intégrité). 

equation
Figure: 61.7 - Principe des certificats d'authentification 1/2

Tout cela a l'air bien compliqué, mais en pratique, vous n'avez qu'à cliquer sur une icône à l'écran pour lancer tout le processus.

Sinon voyons un autre schéma peut-être un peu plus clair:

equation
Figure: 61.8 - Principe des certificats d'authentification 2/2 (source: Dossier Pour La Science)

1. Alice utilise une clé secrète (a) ainsi qu'une clé publique (b) reçue d'une autorité de certification qui a transmis par courrier classique les clés privée et publique à Alice dans une carte à puce contenant un certificat numérique (c). Sur ce certificat, se trouve aussi la signature de l'autorité de certification, laquelle peut être vérifiée par toute personne (ou logiciel) connaissant ou pouvant accéder à la clé publique de cet organisme.

2. Le clé publique (d) de l'autorité de certification est fournie à ceux qui en ont besoin, Bernard par exemple. Cette clé peut être incluse dans les programmes de navigation sur le réseau Internet et dans d'autres logiciels utilisés pour les communications informatiques sécurisées.

3. Alice signe numériquement le message qu'elle envoie à Bernard. Tout d'abord, elle crée un condensé du message en lui appliquant une fonction de hachage. Le condensé ainsi créé est ensuite chiffré à l'aide de la clé secrète d'Alice ce qui donne la signature numérique du message (e). Cette signature est envoyée à Bernard en même temps que le message crypté ( f ) et la clé publique.

4. Bernard utilise la clé publique de l'autorité de certification pour vérifier si la signature numérique officielle apposée sur le certificat est authentique et que la clé publique qui l'accompagne est celle d'Alice. Il utilise alors cette clé pour déchiffrer la signature numérique d'Alice et obtient le condensé du message. Enfin, Bernard applique la fonction de hachage au message envoyé par Alice et obtient ainsi un condensé du message. Si ce condensé est identique à celui qui est obtenu par le chiffrage numérique d'Alice, Bernard est certain que le message provient bien d'Alice et qu'il n'a pas été altéré par une tierce personne.

CRYPTOGRAPHIE QUANTIQUE

La "cryptographie quantique" est une expression médiatique, mais quelque peu trompeuse: en effet, il ne s'agit pas de chiffrer un message à l'aide de la physique quantique, mais d'utiliser celle-ci pour s'assurer que la transmission de la clé n'a pas été espionnée. Comme nous l'avons déjà expliqué en informatique quantique, la transmission d'un message, chiffré ou non, peut se faire en utilisant les deux états de polarisation linéaire orthogonaux d'un photon, par exemple equation. Nous pouvons décider d'attribuer par convention la valeur 1 à la polarisation equation et la valeur 0 à la polarisation equation: chaque photon transporte donc un bit d'information. Tout message chiffré ou non peut être alors écrit en langage binaire, comme une suite de 0 et 1, et le message 1001110 sera codé par Alice grâce à la séquence de photons xyyxxxy, qu'elle expédiera à Bob par exemple par une fibre optique. À l'aide d'une lame biréfringente, Bob sépare les photons de polarisation verticale et horizontale et deux détecteurs placés derrière la lame lui permettent de décider si le photon était polarisé horizontalement ou verticalement:

equation
Figure: 61.9 - Expérience de pensée pour la cryptographie quantique

il peut donc reconstituer le message. S'il s'agissait d'un message ordinaire, il y aurait bien sûr des façons bien plus simples et efficaces de le transmettre! Remarquons simplement que si Ève s'installe sur la fibre, détecte les photons et renvoie à Bob des photons de polarisation identique à ceux expédiés par Alice, Bob ne peut pas savoir que la ligne a été espionnée. Il en serait de même pour tout dispositif fonctionnant de façon classique (c'est-à-dire sans utiliser le principe de superposition): si l'espion prend suffisamment de précautions, il est indétectable.

C'est ici que la physique quantique et le principe de superposition viennent au secours d'Alice et de Bob, en leur permettant de s'assurer que leur message n'a pas été intercepté. Ce message n'a pas besoin d'être long (le système de transmission par la polarisation est à ce jour très peu performant). Il s'agira en général de transmettre une clé permettant de chiffrer un message ultérieur, clé qui pourra être remplacée à la demande. Tout ceci satisfaisant le principe de Kerckhoffs.

Avant de passer à la partie très formelle, voyons le principe (vulgarisé) de fonctionnement de ce système:

Dans le transport de "clé quantique", l'information est donc transportée par les photons. Chaque photon peut être polarisé, c'est-à-dire que l'on impose une direction à son champ électrique (cf. chapitre d'Optique Ondulatoire).

La polarisation est mesurée par un angle qui varie de 0° à 180°. Dans le protocole que nous décrivons la polarisation peut prendre 4 valeurs: 0°, 45°, 90°, 135°. Pour les photons polarisés à 0° et à 90°, nous parlons de "polarisation rectiligne", pour ceux polarisés à 45° et à 135°, de "polarisation diagonale":

equation
Figure: 61.10 - Rappels de quelques polarisations classiques

Il nous faut pouvoir détecter la polarisation des photons. Pour cela, nous utilisons un filtre polarisant suivi d'un détecteur de photons. Si un photon polarisé à 0° rencontre un filtre polarisant orienté à 0°, il traverse ce filtre polarisant et est enregistré par le détecteur placé juste après. Si un photon polarisé à 90° rencontre le même filtre, il est immédiatement stoppé, et le détecteur n'enregistre rien. Maintenant, si le photon est polarisé diagonalement (45° ou 135°), une fois sur deux, il traverse le filtre (superposition de deux états polarisés de manière rectiligne), et une fois sur deux, il est stoppé. Si nous pouvons distinguer entre une polarisation à 0° et à 90°, il est impossible de distinguer en même temps entre une polarisation à 45° et à 135°! De la même façon, on peut utiliser un filtre polarisant orienté à 45°: il laisse passer les photons polarisés à 45°, stoppe ceux polarisés à 135°, et se comporte aléatoirement avec ceux à 0° et 90°!

equation
Figure: 61.11 - Passage à travers un filtre polarisant

Décrivons alors le protocole qu'Alice et Bob doivent respecter pour qu'Alice envoie à Bob une clé secrète constituée de 0 et de 1; ils disposent de 2 canaux d'échange: un "canal quantique", où ils peuvent s'échanger des photons polarisés, et un canal radio (non protégé) par lequel ils peuvent discuter. Ils conviennent avant que les photons polarisés à 0° ou 45° représentent 0, et ceux polarisés à 90° ou 135° représentent 1. Alice émet, sur le canal quantique, une suite de photons polarisés au hasard parmi 0°, 45°, 90° et 135°. À l'autre bout, Bob reçoit les photons et mesure aléatoirement ou leur polarisation rectiligne (filtre placé à 0°), ou leur polarisation diagonale (filtre placé à 45°). Si le photon traverse le filtre, Bob note 0, sinon il note 1.

Bien sûr, certaines mesures de Bob (en moyenne, une sur deux) n'ont pas d'intérêt (c'est là que toute l'astuce réside !!!): il a pu essayer de mesurer la polarisation rectiligne d'un photon polarisé à 45°, ce qui n'a pas de sens et donne un résultat aléatoire (par exemple, le photon a été bloqué par le filtre, Bob note donc 1 alors qu'Alice avait envoyé 0). Pour éliminer ces bits sans sens, il indique à Alice, par le canal radio, quel type de mesure (rectiligne ou diagonale) il a faite pour chaque photon. Par le même canal radio, Alice lui indique quelles sont les mesures correctes (photon polarisé à 0° ou 90° avec filtre rectiligne, photon à 45° ou 135° avec filtre diagonal), dans l'exemple ci-dessous la 1, la 3, la 4, et la 7. Les bits 1,3,4,7 sont désormais connus à la fois de Bob et d'Alice, et constituent leur clé secrète commune.

Dans la figure ci-dessous qui représente donc de façon schématique le concept, il ne faut pas oublier que la valeur peut être correcte mais non fiable. Ainsi, l'arbre de décision est le suivant (afin que les choses soient bien claires!):

- soit la valeur fournie par Bob est incorrecte et on élimine la colonne
- soit la valeur est correcte et le filtre est adéquat: cela devient une valeur de la clé
- soit la valeur est correcte mais le filtrage est aléatoire: pour toute sûreté on élimine la colonne.

equation
Figure: 61.12 - Principe général résumé

Il faut encore vérifier que ce protocole est sûr. Si Caroline écoute le canal quantique, elle peut faire la même chose que Bob: intercepter les photons en plaçant un filtre polarisant tantôt rectiligne, tantôt diagonal. Pour que Bob ne se doute de rien, elle doit réémettre un photon polarisé. Elle va essayer d'envoyer le même photon qu'Alice, mais comme elle a une chance sur deux d'avoir choisi le mauvais filtre, elle a une chance sur deux de se tromper. Quand Bob reçoit le photon, s'il est mal polarisé par Caroline, il a une chance sur deux d'avoir un résultat différent d'avec le photon original, et finalement, pour chaque photon intercepté par Caroline, il y a une chance sur 4 que Bob reçoive une information erronée.

Alice et Bob décident alors de "sacrifier" une partie de leur clé commune. Parmi tous les bits qu'ils ont en commun, ils en choisissent quelques-uns au hasard, et les compare publiquement par le canal radio: s'ils sont différents, ils ont une preuve qu'ils ont été écoutés, et ils oublient vite cette clé. En comparant suffisamment de bits, ils ont une garantie presque absolue de ne pas avoir été écoutés.

equation
Figure: 61.13 - En cas d'interception

Puis... Bob: j'ai peur que nous ayons été espionnés, sacrifions le premier bit de notre clé - j'obtiens 1. Alice: je t'avais envoyé 0, nous avons été espionnés...

Remarquons que même non repérée, Caroline n'avait pas la bonne clé, puisque le troisième bit de la clé qu'elle obtient (par rapport à la clé reconstituée d'Alice et Bob) est 0 alors qu'Alice avait envoyé 1 !

Remarque: Le protocole décrit ci-dessus est appelé BB84, du nom de ses inventeurs Bennett et Brassard.

Passons maintenant à la partie formelle (il faut si possible avoir parcouru le début du chapitre d'informatique quantique au préalable).

Les états du système quantique sont les états de polarisation d'un photon: les mesures (de l'observable) auront aussi pour valeur ses états de polarisation. Les mesures possibles seront du type:

equation   (61.78)

nous noterons les états correspondants equation (base orthonormée de l'espace des états (de polarisation): c'est la base H/V (Horizontale/Verticale).

Prenons plusieurs cas:

C1. Soit un photon dans l'état equation alors comme nous l'avons vu en informatique quantique, nous aurons:

equation   (61.79)

C2. Soit un photon dans l'état:

equation   (61.80)

Remarques:

R1. Cette (fameuse) valeur est choisie à des fins de normalisation telle que equation !!! Beaucoup de gens se posent la question d'où vient la racine carrée en informatique quantique. La réponse est simplement pour la normalisation.

R2. Notons que ce photon n'est pas polarisé dans la direction equation (c'est-à-dire dans la direction oblique) mais est dans une superposition quantique de ces deux polarisations.

Alors (nous appliquons comme nous l'avons vu dans le chapitre d'Informatique Quantique, le test equation à l'état equation:

equation   (61.81)

et:

equation   (61.82)

Remarque: Rappelons que sur ce site, nous notons en physique quantique le module d'un nombre complexe et la norme, indistinctement par le symbole equation donc attention aux confusions!

CRYPTOGRAPHIE ALTERNATIVE

Les mathématiciens s'aventurent parfois hors des sentiers battus de la théorie des nombres: ils inventent des cryptosystèmes fondés sur des tresses ou des réseaux (théorie des noeuds et des graphes). Les physiciens ne sont pas en reste et proposent des méthodes de chiffrement qui utilisent la théorie du chaos ou la physique quantique. Cette dernière apporterait une solution définitive au délicat problème de l'échange de clés et mettrait en péril les cryptosystèmes fondés sur la factorisation.

La plupart de ces méthodes sortent pour l'instant du contexte du contenu de ce site mais on peut citer cependant:

- l'algorithme LLL basé sur la structure en maille d'ensembles de nombres et se basant sur le théorème de Minkowski assurant que le contenu d'un disque de rayon donné en un point contient au moins un autre point du réseau

- la cryptographie ultravariable dans laquelle les données passent par des systèmes d'équations quadratiques superposées.

- l'hyperchaos optique, obtenu par le passage d'un LASER dans un anneau d'IKEDA dans lequel se présente un matériau non linéaire en longueur d'onde.

- la cryptographie quantique, basée sur le principe d'incertitude de Heisenberg et l'implication de l'annulation des transferts de données. Les scientifiques cherchent aujourd'hui des moyens de communication moins onéreux des clés quantiques en utilisant entre autres, les propriétés du condensat de Bose-Einstein qui permettrait de contrôler l'émission de photons ainsi que la transmission instantanée d'un message sans liaison physique...

L'avenir nous dira le reste!
Haut de page

CODES CORRECTEURSAUTOMATES


Like5   Dislike0
47.69% sur 100%
Notée par 13 visiteur(s)
12345
Commentaires: [0] 
 
 


W3C - HTMLW3C - CSS Firefox
Ce travail est dans le domaine public
2002-2017 Sciences.ch

Haut de page