News :: Erreur :: Statistiques :: ClearType :: Imprimer ::

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

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. Nous rapportons son utilisation en Egypte 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.

A 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és. Ainsi, les ingénieurs ont du 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 à 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 informatique standards ou performants (en puissance de calcul donc). Les ingénieurs et chercheurs se sont alors plongés dans les mathématiques pour chercher les outils satisfaisant ce cahier des charges et pour les systèmes les plus connus, les théories mathématiques qui furent optées avaient plus de 200 ans (cryptographie quantique mise à part) d'ancienneté.

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:

  (1)

et une fonction de déchiffrement (decryption) :

  (2)

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

  (3)

autrement dit, ces deux fonctions doivent être injectives!

Pour arriver à ce résultat, deux types de techniques cryptograhpiques 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ème de chiffrement "aysmétriques à clé publique". 

Par nature, ces deux types de clés sont très différentes. 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étrique 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.).

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 Kerchoffs 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 le clés publiques et secrètes. Ceci est du 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é. A 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 constructions 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 appellé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ée après la transmission de cette clé, A va encoder son message en C en effectuant l'opération:

  (5)

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:

  (6)

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 futures 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 possible source d'erreur. 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 les 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 servit à chiffrer les messages de langue française  et   et qu'une personne malveillante arrive à intercepter les deux message correspondants cryptés  et . A partir de  et l'intercepteur peut facilement obtenir des informations sur  et   du fait des particularités des langues. En effet, puisque :

 et   (7)

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

  (8)

car :

    (9)

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

et donc:

Evidemment dans ce genre de petites situations on peut deviner sans trop de difficultés M rien qu'en ayant C si il n'y a comme ici qu'une seule étape de chiffrement. Raisons pour laquelle 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 palier à 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

Dans les années 1950, un mathématicien (Feistel) a montré qu'une fonction pseudo aléatoire se transforme, par une méthode 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 à 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 tel que:

 et   (10)

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

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ée "schéma à n étapes".

Exemple:

Nous allons chiffrer par la méthode de Feistel à deux étapes un message constituté 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 bijection (). A titre d'exemple, chiffrons le message 1101. G désigne la moitié gauche du message à chiffrer, D la moitié droite :

  (12)

Le résultat est 0010. Nous calculerons l'image des 15 autres messages possible 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ésultat 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 droit (D). A 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.

  (13)

La fonction de confusion (f), qui agit sur les blocs de 32 bits, mélange les bits selon les processus suivant (à 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.

  (14)

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

Avant d'exposer dans le détail le protocole de Diffie-Hellmann, 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 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!) fréquemment les clés. 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. Echanger une clé secrète utilisant une fonction mathématique non-inversible ou très difficilement inversible (c'est le protocole de Diffie-Hellmann que nous verrons également dans une figure plus bas).

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

  (15)

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 sont 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 transactions de la figure ci-dessus). En recevant le coffre, Bernard peut ouvrir le coffre, puisque lui seul détient le 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. La clé privée et publique sont construites à parti d'une fonction mathématique supposée comme "à sens unique".

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

PROTOCOLE DE DIFFIE-HELLMANN

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

  (16)

Les mathématiciens appellant ce genre d'opérations une "exponentation modulaire".

Pour un tel calcul, 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.

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 un 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 :		Bob choisit un nombre aléatoire secret :
échange données chiffrées avec K

Alice et Bernard on calculé le même secret commu n: 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 :

  (17)

Exemple:

, alors qu'avec nous avons alors que .

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

  (18)

de même :

  (19)

et donc :

  (20)

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 (environs 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-Hellmann 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'en suit 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).

Le protocole de Diffie-Hellmann a ouvert la voie à toute une série d'algorithmes, celui du chiffrement a 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 a 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éments dasn les navigateurs Web, comme Netscape Navigator, Microsoft Internet Explorer ou encore dans certaines cartes à puces 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 en géométrie ou théorie des graphes). Voyons de quoi il s'agit (attention c'est relativement long!).

THÉORÈME D'EULER

Avant de voir en quoi consiste ce théorème, 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 dite appelée "indicatrice d'Euler" et définie par:

  (21)

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

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

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:

  (22)

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

  (23)

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 :

  (24)

dans laquelle nous voyons apparaître l'indicatrice d'Euler définie juste avant haut..

Démonstration:

Rappelons d'abord (cf. chapitre de Théorie Des Nombres) qu'un système de résidus modulo m est un ensemble d'entiers  tel que:

1. 

2.   n'est pas congru  modulo m lorsque

3. 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 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, 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 fonction d'Euler. Nous parlons alors de "conjecture", c'est-à-dire une supposition fondée sur des probabilités (car non démontrée parait-il!).

Pour cela, rappelons-nous que:

 et   (25)

alors nous voulons démontrer que:

    (26)

est aussi satisfait.

Posons pour cela (par tradition...). Nous avons alors puisque  que  et  et identiquement pour  puisque  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:

  (27)

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 :

    (28)

effectivement :

    (29)

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

    (30)

alors nous avons également  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 au moins un élément dans l'ensemble d'arrivée (s'il y avait pour chaque homme sur Terre un 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:

  (31)

Exemple:

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

  (32)

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

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

  (34)

Puisque :

  (35) 

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

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

  (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é de l'indicateur d'Euler, que si N est un nombre premier et si , où , alors :

  (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 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 a également:

  (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'Eratosthè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  (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  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:

  (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 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 utilise 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 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 où p et q sont de l'ordre de  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.

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 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 deux nombres premiers, nous calculons l'expression :

  (43)

appelée "modulus".

Ensuite, Alice qui souhaite recevoir les information 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 .

Et comme :

  (44)

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êment difficile de retrouver les facteurs premiers de n.

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

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

  (45)

à 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'aborde le message en chiffres en utilisant la convention que chaque lettre est remplacée par sa position correspondant dans l'alphabet en commencent à compter à partir de 01 (le caractère "espace" sera chiffré "27").

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

  (46)

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

  (47)

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

  (48)

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 tel que :

  (49)

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

  (50)

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

  (51)

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 choisi  a de telle que sorte que ,  ce qui implique, d'après 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) qu'il existe des entiers x et y tels que (on peut supposer que , auquel cas ):

  (52)

ou autrement écrit :

  (53)

Ce qui signifie :

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

2. Que a est inversible modulo

Effectivement, car :

  (54)

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

  (55)

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

Seul 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 indicatrie 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:

  (56)

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 que ê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 :

  (57)

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:

  (58)

Explications:

Nous avions déjà montré que :

  (59)

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

  (60)

Effectivement :

  (61)

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.

Effectivement :

  (62)

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

  (63)

donc que :

  (64)

Reste à démontrer que :

  (65)

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

    (66)

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

  (67)

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

  (68)

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

  (69)

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

  (70)

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:

  (71)

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.

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 communication d'ordre militaire. Cette surveillance a d'ailleurs soulevé aux Etats-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.

FONCTONS 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'elles sont très utilisées 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 sont fonctionnement:

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

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

Etape 3 : Calcul itératif

La boucle principale a 4 rondes qui utilise chaque fois 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.

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.

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

Le MD5 n'état 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 :

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". A 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 identiques pour deux message d'origine différents.

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

Etape 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 hexadecimal ().

Etape 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[1] , F[2], ..., F[79]  qui prennent des arguments codés sur 32 bits, et renvoie 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.

Etape 3 : Calcul Itératif

L'itération, utilise deux buffers, chacun consistant en l'utilisation de 5 variable 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 variable 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é. Le certificat est en quelque sorte la carte d'identité de la clé ou la "signature numérique", délivré 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 vise essentiellement 4 points importants:

1. l'authentification (le destinataire de votre e-mail 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 des 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'UIT, qui définit les informations contenues dans le certificat :

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

- Le nom du propriétaire du certificat (UBS)

- 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 venant d'un confrère (T. Taglicht - www.taglicht.com):

Pour signer le message que vous expédiez (point (5) sur le schéma), il suffit en effet de lui appliquer une fonction de hachage (point (1) sur le schéma) qui produit un résumé (code haché) du message (les algorithmes de hachage les plus connus sont MD5 (128 bits (Message Digest 5)) et 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) sur le schéma). C'est ce code qui constitue la signature numérique. Le destinataire du message peut ensuite vérifier que vous en êtes bien l'expéditeur en déchiffrant la signature numérique, au moyen de votre clé publique (que vous lui avez transmis automatiquement avec le mail (point (4) sur le schéma), pour obtenir le code haché (point (9) sur le schéma). 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é). 

  (72)

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.

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. A 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 lui permettent de décider si le photon était polarisé horizontalement ou verticalement :

  (73)

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

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. La polarisation est mesurée par un angle qui varie de 0° à 180°. Dans le protocole que nous décrivons, dû aux canadiens CH.Bennett et G.Brassard, la polarisation peut prendre 4 valeurs : 0°, 45°, 90°, 135°. Pour les photons polarisés de 0° à 90°, nous parlons de "polarisation rectiligne", pour ceux polarisés de 45° à 135°, de "polarisation diagonale" :

  (74)

Il nous faut pouvoir détecter la polarisation des photos. 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°!

  (75)

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é, où 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°. A 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 tout 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, quelle 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.

  (76)

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

  (77)

Puis... Bob : j'ai peur que nous ayons été espionné, 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 :

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

  (79)

C2. Soit un photon dans l'état :

  (80)

Alors (nous appliquons comme nous l'avons vu en informatique quantique, le test à l'état :

  (81)

et :

  (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 dont attention aux confusions!

CRYPTOGRAPHIE ALTERNATIVE

Les mathématiciens s'aventurent parfois hors de 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 ce 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'impliquation 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...