News :: Erreur :: Visiteurs :: ClearType :: Imprimer ::

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

Dernière mise à jour de ce chapitre: 2015-09-06 16:35:36 | {oUUID 1.789}
Version: 3.0 Révision 8 | Rédacteur: Vincent ISOZ  | Avancement: ~50%
vues depuis le 2012-01-01: 4'580

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.

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é , nous cherchons une fonction de chiffrement:

  (61.1)

et une fonction de déchiffrement (decryption):

  (61.2)

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

  (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".

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

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.).

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:

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".

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:

  (61.4)

où  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  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  de (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:

  (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  et   et qu'une personne malveillante arrive à intercepter les deux messages correspondants cryptés  et . À partir de  et l'intercepteur peut facilement obtenir des informations sur  et   du fait des particularités des langues. En effet, puisque:

 et   (61.6)

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

  (61.7)

car:

    (61.8)

(au besoin faire la table de vérité pour s'en convaincre). Or, si  et   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 , 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:

  (61.9)

et donc:

  (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  qui associe à G et D les nombres S et T telle que:

 et   (61.11)

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

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

 et   (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  est bijective, on peut réitérer le processus. Un schéma de Feistel où l'on applique n fois la fonction  est nommé "schéma à n étapes".

Exemple:

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 de deux bits vers deux bits. Les fonctions 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:

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

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  sont indiscernables de fonctions réellement aléatoires. En pratique, plutôt que d'utiliser quatre étapes et des fonctions  qui ont l'air aléatoires, on préfère en général utiliser plus d'étapes et des fonctions  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).

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.

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.

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.

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:

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:

  (61.13)

où 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 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 à 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 , de p et de , 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:

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: et un nombre aléatoire commun inférieur à p: . On suppose que ces deux valeurs sont secrètes.
Alice choisit un nombre aléatoire secret:		Bernard choisit un nombre aléatoire secret:
Avec le nombre a Alice génère l'élément public:		Avec le nombre b Bernard génère l'élément public:
Envoi du résultat à Bernard:
		Envoi du résultat à Alice:
Le secret partagé est alors:		Le secret partagé est alors:
Les échanges sont alors chiffrés avec la clé secrète K

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 .

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:

  (61.14)

Exemple:

, alors qu'avec nous avons alors que .

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

  (61.15)

de même:

  (61.16)

et donc:

  (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:

  (61.18)

Autrement dit, la fonction  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  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:

(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

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:

  (61.19)

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):

  (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  (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:

  (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:

  (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  qui satisfont les trois propriétés:

P1. 

P2.   n'est pas congru  modulo m lorsque

P3. Chaque entier x relativement premier avec m est congru à un certain  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   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 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 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:

et par hypothèse:

  (61.23)

alors nous voulons démontrer que:

    (61.24)

est aussi satisfait.

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

  (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  du système réduit modulo m, nous aurons un résidu  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.

Exemple:

Prenons:

    (61.26)

effectivement:

    (61.27)

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

    (61.28)

alors nous avons également:

    (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:

  (61.30)

Exemple:

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:

  (61.31)

Nous avons alors:

  (61.32)

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

    (61.33)

car . 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:

  (61.34)

Puisque:

  (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:

    (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:

  (61.37)

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

C.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 , où , alors:

  (61.38)

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

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 avec .

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

  (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'à selon la méthode du crible d'Ératosthène qui est la plus connue dans les petites écoles.

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

Tout nombre naturel  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:

  (61.42)

Alors,  et , puisque n est supposé composé, nous avons que , 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  qui est premier, sans quoi le choix minimal de  serait contredit. Nous pouvons donc écrire . Si  est premier, alors la preuve est terminée. Si  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  et d'un entier  tels que . En poursuivant ainsi, nous arrivons forcément à la conclusion que  sera premier.

C.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.

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.

Exemple:

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 . 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:

  (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:

  (61.44)

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

Et comme:

  (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:

  (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:

  (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  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: 

  (61.48)

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

  (61.49)

et on travaille successivement avec chaque morceau  du message.

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

  (61.50)

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

  (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): 

  (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 ,  ce qui implique, d'après le théorème de Bézout (cf. chapitre de Théorie Des Nombres), que si a et 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 , auquel cas ):

  (61.53)

ou autrement écrit:

  (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 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

Effectivement, car:

  (61.55)

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

  (61.56)

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

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

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

  (61.57)

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

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

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

  (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:

  (61.59)

Explications:

Nous avions déjà montré que:

  (61.60)

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

  (61.61)

Effectivement:

  (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:

  (61.63)

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

  (61.64)

donc que:

  (61.65)

Reste à démontrer que:

  (61.66)

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

    (61.67)

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

  (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:

  (61.69)

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

  (61.70)

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

  (61.71)

Puisque les deux membres de gauche sont bien modulos n.

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

  (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 , 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.

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:

  (61.73)

nous avons alors:

  (61.74)

2) Nous calculons l'indicatrice d'Euler:

  (61.75)

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

  (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:

  (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 à 2⁶⁴, 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 ().

É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 |
K[t] =89ABCDEF |
K[t] =FEDCBA98  |
K[t] =76543210 |

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) |
F[t] (X,Y,Z) = (X XOR Y) XOR D |
F[t] (X,Y,Z) = (X AND Y) OR (X AND Z) OR (Y AND Z) |
F[t] (X,Y,Z) = X XOR Y XOR Z |

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 Sⁿ le décalage circulaire de n bits vers la gauche

Voici l'algorithme SHA-1:

Pour t = 16 à 79 faire
     M[t] = S¹(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 = S⁵(A) + F[t](B,C,D) + E + M[t] + K[t]
     E = D; D = C; C = S³⁰(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

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é). 

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:

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 . Nous pouvons décider d'attribuer par convention la valeur 1 à la polarisation et la valeur 0 à la polarisation : 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:

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":

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°!

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.

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.

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 !

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:

  (61.78)

nous noterons les états correspondants (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 alors comme nous l'avons vu en informatique quantique, nous aurons:

  (61.79)

C2. Soit un photon dans l'état:

  (61.80)

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

  (61.81)

et:

  (61.82)

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...

4   0

Notée par 12 visiteur(s) 12345 PageRater 0.5.0 Commentaires: [0]