recevoir les news :: signaler une erreur :: statistiques visiteurs :: imprimer

ALGORITHMES | FRACTALS | ALGEBRE DE BOOLE | CRYPTOGRAPHIE | INFORMATIQUE QUANTIQUE

Avec la prolifération des ordinateurs et des moyens électroniques de communication, il devient de plus en plus important d'utiliser des codes secrets pour la transmission des données entre les organismes à caractère militaire ou

1. Les premières (celles de 128 bits aujourd'hui) concernent les systèmes de chiffrement à clé secrète ou symétrique. Rigoureusement parlant, les mathématiques de ces clés sont plus complexes que celles des systèmes à clés publiques et font souvent référence au protocole DES: Data Encryption System (en 1998, les Etats-Unis ont décidé de changer de protocole et de passer au AES – Advanced Encryption Standard – qui reste un algorithme de chiffrement par bloc).

2. Les secondes (celles de 320 bits aujourd'hui) sont la partie publique d'une clé d'un système de chiffrement à clé publique ou asymétrique. Ce type de clé fait souvent référence au protocole RSA, du nom des personnes à qui on en a attribué le développement: Rivest, Shamir et Adi. Elles sont beaucoup utilisées de par la rapidité du temps de cryptage et de décryptage ainsi que de leur grande entropie. Commes elles sont utilisées en masse sur des serveurs uniques, il était important de trouver un système simple et sûre.

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

Un système de chiffrement est dit symétrique si 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". De tels systèmes sont aussi nommés "systèmes de chiffrement à clés secrètes ".

Les protocoles asymétriques, ou à clé publique, désignent les systèmes 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 une clé nommée "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 est le RSA.

Si l'on considère que la loi de Moore s'applique indéfiniment, une "clé secrète" de 218 bits (39 chiffres) serait cassable en ~2100 et une "clé publique" de 2048 bits en ~2080. Mais rappelons que la première bien que plus sécurisée n'est pas adéquate du tout à une utilisation de masse. Quant à la publique, le dernier record de factorisation d'un entier a été établi durant l'été 1999 par une équipe de mathématiciens qui a factorisé un entier de 512 bits (155 chiffres)  après plusieurs mois de calculs distribués sur des centaines d'ordinateurs du réseau Internet et terminée sur un supercalculateur: des moyens hors de portée du particulier moyen. Pour obtenir une sécurité satisfaisante aujourd'hui, il est estimé que les clés RSA doivent avoir une taille de 1024 bits (Internet Explorer fonctionne avec un système asynchrone de 1024 bits certifié par un système synchrone)

Au cours de l'histoire, on s'est servi de différents codes pour transmettre des messages secrets (surtout de nature militaire). Les messages qui étaient codés avec des méthodes relativement simples pouvaient, avec peu d'effort, être finalement déchiffrés. De leur côté, les messages qui recouraient à des codes très sophistiqués, et donc presque indéchiffrables souffraient du désavantage d'être très compliqués à transmettre ou très longs à décoder. D'ailleurs, la plupart des codes employés au cours de l'histoire pourraient facilement être décodés par un intercepteur muni d'un ordinateur moyen contemporain. De tout manière, ces codes demeurent toujours déchiffrables, à condition que l'intercepteur possède "assez de temps et de papier" (sauf exception si l'on aborde le cryptage quantique).

Pour aborder les fondements de la théorie de la cryptographie, j'avais le choix:

1. De renvoyer fréquemment le lecteur à des théories qui ont été vues dans d'autres sections de ce site comme on le fait dans de trop nombreux ouvrages (qui font toujours référence à d'autres ouvrages ou à d'autres pages ou encore qui supposent que le lecteur sait déjà beaucoup de choses)

2. De reporter toutes les théories dans un même cadre.

Par expérience, j'ai choisi la seconde option.

PRINCIPE DE KERCHOFFS

La première fonction de la cryptographie consiste à assurer la confidentialité d'un échange d'information. 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 peut 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 Kerchoffs", 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.

SYSTEMES SYMETRIQUES ET ASYMETRIQUES

Il existe deux types fondamentales de clés:chrone de 128 bits).

TRAPPES

Il existe parfois ce que l'on nomme 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 a 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é, directement liée à l'entropie du générateur aléatoire. On définit 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'entropie d'un générateur de clés de n bits n'excédera donc jamais n mais pourra cependant y être inférieure.

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. Si le générateur aléatoire qui engendre ces nombres est biaisé (voir la définition de ce terme dans la section probabilités du site), ce biais facilitera la recherche des nombres premiers ayant servi à l'élaboration de la clé qu'un attaquent tente de casser.

RAPPELS SUR LA LOI DE GROUPE

Remarque : pour les détails, voir le chapitre traitant de la théorie des ensembles dans la section d'arithmétique.

Soit pour simplifier les écritures,  une loi de composition (comme l'addition, la multiplication, la division par exemples) interne dans E (un ensemble quelconque comme ). On écrit que:

 est une loi de composition interne dans E  vers E implique (bijection)

 est une loi de composition interne dans E  implique que  est une application de

Définitions:

Soit  et  des symboles de lois de composition internes dans un ensemble E :

-  est commutative: 

-  est associative:

- n est élément neutre pour :

-  est le symétrique de  pour :

-   est distributive par rapport à :

On définit un ensemble par le terme "Groupe", noté G, si les composants le constituant satisfont aux 3 conditions de ce que l'on nomme la "Loi de Groupe", définie ci-dessous:

 est un groupe si

Il y a des groupes particuliers tels que si:

-  est également commutative on dit alors que le groupe est "abélien" (ou commutatif)

On ne verra pas les autres groupes particuliers qui sortent du contexte de la base mathématique de la cryptographie. Tant pis donc pour l'étude de l'AES (Advanced Encryption System).

RAPPELS SUR LA DIVISIBILITE

Soit  avec . On dit que A divise B s'il existe un entier q tel que , auquel cas on écrit . Dans le cas contraire, on écrit  et on lit "A ne divise pas B".

Exemple: 3 divise 15 et l'entier q vaut donc 5

RAPPELS SUR LA DIVISION EUCLIDIENNE

Soit  avec ; alors, il existe des entiers q et r  tels que , où . De plus, si , alors .

Démonstrations: Considérons l'ensemble:

Il est facile de voir  et donc que , d'où, d'après le principe du bon ordre, on conclut que S contient un plus petit élément . Soit q l'entier satisfaisant à . Il reste à montrer que . Supposons le contraire à nouveau (démonstration par l'absurde), c'est-à-dire que . Alors, dans ce cas, on a , ce qui est équivalent à ; mais  et , ce qui contredit le fait que  est le plus petit élément de S. Donc, . Enfin, il est clair que si , on a , d'où la seconde affirmation du théorème.

RAPPELS SUR LE P.G.C.D.

Soit  tels que . Le "plus grand commun diviseur" (noté p.g.c.d par la suite) de , noté , est l'entier positif d qui satisfait aux deux conditions suivantes:

1.  et

2. si  et  alors  (par définition)

Exemple: Le p.g.c.d de 9 et 15 est 3

Remarque: notons que 1 est un diviseur commun de deux entiers arbitraires. Cependant, il n'est pas évident que le p.g.c.d de deux entiers  existe toujours; ce fait est démontré dans le théorème suivant (cependant, si le p.g.c.d existe, il est de par sa définition unique):

Soit  tels que . Alors, il existe des entiers  tels que:

Exemple: pour

Démonstration:

Considérons l'ensemble . Comme  et , on peut utiliser le principe du bon ordre et conclure que S possède un plus petit élément d. On peut alors écrire  pour un certain choix . Il suffit de montrer que . Pour cela, il faut montrer que d satisfait aux conditions 1. et 2. de la définition du p.g.c.d. 

Commençons par la première:

Supposons que . Alors, d'après la division euclidienne, il existe  tels que , où . Mais alors:

et donc  et , ce qui contredit le fait que d est le plus petit élément possible de S. Donc,  et, de la même façon, on démontre que .

FONCTION PHI D'EULER

Soit la fonction d'Euler définie par:

Il faut lire: la fonction  du nombre m a pour résultat un nombre n inférieur ou égal à m et tel que le plus grand commun diviseur de n et m soit 1.

On remarque la propriété remarquable de cette fonction lorsque si l'on note un nombre premier quelconque par la lettre p alors:

Cette fonction à également la propriété remarquable de compter le nombre d'entiers positifs plus petits que m et "relativement premiers" (attention, nous reviendrons sur cette terminologie) à m, c'est-à-dire:

C'est pourquoi on trouve parfois dans la littérature le terme "indicateur d'Euler" au lieu de "fonction phi d'Euler".

RAPPELS SUR LA CONGRUENCE

Définition: Soit . On dit que " est congru à b modulo m", et on écrit:

si ; dans le cas contraire, on dit que " est non congru à b modulo m".

D'autre part, on peut tendre la signification du mot "reste" en disant que: "deux nombres congrus pour le module M sont résidus l'un de l'autre pour ce module". 

On a les propriétés principales suivantes pour la congruence:

- On peut multiplier les deux membres d'une congruence par un même nombre entier et il restera congru modulo m et multiplié par ce nombre entier.

- On peut élever à une même puissance les deux membres d'une congruence.

- Si

Exemple:  car  et  et idem pour les autres propriétés de la congruence.

Revenons à notre théorème d'Euler (qui soit dit en passant, est une généralisation du "petit théorème de Fermat" que nous verrons plus loin):

Soit  (le plus grand diviseur commun de  et ), alors:

Démonstration:

Définition préalable: 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  relativement premier avec m est congru à un certain  modulo m.

Exemple: L'ensemble est un système réduit de résidus modulo 6 ou autre exemple,  est un système réduit de résidus modulo 7. On vérifie é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.

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: Vous pouvez observer que le nombre de résidus correspondent, pour un modulo m premier donné, au résultat défini par la fonction d'Euler. On parle alors de "conjecture", c'est-à-dire une supposition fondée sur des probabilités.

Démonstration sous-jacente:

Puisque  et , alors nous voulons démontrer que  est aussi satisfait:

Posons . On a donc puisque  que  et  et identiquement pour  puisque  et que . Maintenant si  divise bien  ou  dans ce cas on a que  ou autrement . Donc  et  ce qui nous permet d'écrire:

Revenons à notre théorème d'Euler. 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, on aura un résidu  du système réduit modulo m selon la propriété fondamentale de la congruence qui rappelons-le dit que:

"On peut 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  effectivement  car le reste de la division de 30 par 6 est bien nul. Si l'on prend par exemple  alors également  et le reste est aussi nul…

Petit rappel sur la bijection: On dit que l'on a 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, on peut écrire:

Exemple: L'ensemble est un système réduit de résidus modulo 6 comme nous l'avons déjà vu. On a donc . Si l'on prend un  tel que , par exemple  car effectivement . Alors  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:

Puisque  (vous pouvez vérifier!), on est bien obligé de conclure que:

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:

comme nous l'autorise une des propriétés intrinséque de la congruence.

SYSTEME DE CHIFFREMENT A CLE SECRETE D.E.S

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. On l'emploie pour cette raison dans des cas sensibles, par exemple, pour sécuriser le "téléphone rouge" entre Moscou et Washington.

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 (le destinataire). On engendre une grande quantité de bits "réellement aléatoires" qui forment une clé secrète K (les programmes informatiques, déterministes par essence, ne peuvent engendrer des bits vraiment aléatoires).

Cette clé sera transmise à B par un canal sûr (à nouveau la physique quantique intervient au moment inopportun). 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:

où  est un opérateur qui doit satisfaire à une "loi de groupe" 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.

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). Ainsi B va effectuer l'opération suivante:

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 si il intercepte C (hormis la taille de M). 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 , alors l'intercepteur connaît un résultat simple qui fait intervenir   et  , sans la clé K:

car  (qui est élément neutre du OU EXCLUSIF). Or, si  et   sont dans la même langue, on saura en général, grâce aux redondances des langues, retrouver à partir de , chacun des deux messages (le travail est quand même laborieux).

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 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 fait correspondre un élément de départ et inversement).

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

où le signe  représente désigne 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

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. Dont voici un exemple pratique tiré du mensuel "Dossiers pour la Science":

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 passer 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 DES (Data Encryption System) qui est un schéma de Feistel à 16 étapes comme représenté dans la figure ci-dessous, l'algorithme Triple DES (TDES) qui est un schéma de Feistal à 48 étapes et l'algorithme Blowfish.

Il y a, par exemple, dans chaque carte bancaire, une clé DES (ou TDES depuis octobre 2001).

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. La fonction de confusion, 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.

PRATIQUE DU SYSTEME DE CHIFFREMENT A CLE PUBLIQUE R.S.A

En 1975,  W. Diffie et M.E. Hellman, deux professeurs du département de Standford University (une des deux meilleure école au monde), révolutionnaient la science de la cryptographie en démontrant l'existence d'un code (voir "New Directions in Cryptrography", IEEE Transactions on Information Theory, novembre 1976) qui ne pouvait être déchiffré par un intercepteur à moins que ce dernier ne disposât de millions d'années de temps d'ordinateur.  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 que l'on verra plus tard). Toutefois, ce sont trois mathématiciens du M.I.T, R.L. Rivest, A. Shamir et L. Adleman (RSA) qui eurent d'appliquer les nombres premiers au schéma de principe du système de Diffie-Hellman.

Posons à plat les mathématiques de ce système de cryptage:

Soit étant donné un nombre N, décider si N est premier ou non.

On sait d'après le théorème d'Euler, que si N est un nombre premier et si , où , alors (c'est l'expression du "petit théoèrme de Fermat"):

Effectivement si vous vous rappelez du théorème d'Euler  et de la propriété de la fonction  pour un nombre m premier.

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

On peut appliquer ce dernier théorème sur un nombre N à propos duquel on aimerait 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 écoles.

En fait, avec l'aide d'un ordinateur assez puissant, on peut 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 on a 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:

Alors,  et , puisque n est composé, on a 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. On peut donc écrire . Si  est premier, alors la preuve est terminée. Si  est composé, alors on répète le même argument que précédemment et on en déduit l'existence d'un nombre premier  et d'un entier  tels que . En poursuivant ainsi on arrive forcément à la conclusion que  sera premier.

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 l'on utilise en cryptographie.

On ne connaît 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.

On cherche donc un système simple, où le codage et le décodage seront presque instantanés, avec "clé publique" presque "incassable".

Soit donc 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 information cryptées, se trouve deux nombres premier p et q très grands de l'ordre de . 

Pour trouver de si grands nombres premiers on choisit au hasard un nombre de 100 chiffres et on vérifie par un des algorithmes connus s'il est premier ou non et on répète l'expérience jusqu'à ce que l'on obtienne ainsi un nombre premier. Une fois ceci fait avec deux nombres, on calcule l'expression appelée "modulus".

Ensuite, le membre qui souhaite recevoir les information cryptées (qui est le seul en possession du nombre n pour l'instant) choisit un entier positif  tel que .

 Notons que:

par conséquent, par essais répétés, il est facile de trouver un tel nombre . Le membre principal, trouve donc un n et un  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.

Exemple:

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

L'agence choisit un p et un q et détermine ainsi les nombres n et . Ces deux nombres nous l'avons déjà vu, doivent satisfaires aux conditions suivantes:

1.-  où p et q sont premiers

2.- p et q sont connus que par le destinataire

3.-

L'agence enovoie la clé publique, définit par le couple:

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

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: 

.

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

et on travaille successivement avec chaque morceau  du message.

On considère la puissance de : . 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 .

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

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

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   de telle que sorte que ,  ce qui implique, d'après une des propriétés du p.g.c.d, qu'il existe des entiers x et y tels que (on peut supposer que , auquel cas ):

 ou encore

Effectivement car  et d'après la définition de la congruence () on a effectivement  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 d'Euler et donc connaître p et q.

Si  est le message d'origine et  est le message reçu, alors nous avons la propriété suivante:

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

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:

Explications:

1. Nous avions déjà montré que  et selon la troisième principale propriété de la congruence, nous pouvons écrire

2. Effectivement,  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.

3. Effectivement,  puisque nous avons démontré précédemment que  donc que .

4. Reste à démontrer que  où l'on peut écrire  sous la forme:

Or, rappelez-vous que nous avons démontré le théorème d'Euler: et que la deuxième principale propriété de la congruence nous donne le droite d'élever à une puissance quelconque les deux membres de la congruence tel que:

Mais comme 1 élevé à n'importe quelle puissance fait 1, on a: . Cette dernière relation nous permet donc de vérifier que l'on peut s'autoriser à écrire:

Puisque les deux membres de gauche sont bien modulos n.

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

Pour trouver , la relation précédente revient à calculer:

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 visiblement ont dans ce pays des problèmes à se concentrer sur leurs feuilles), qui voient ainsi brimer leur liberté professionnelle (cf. Notices of Amercian Mathematical Society, janvier 1983).

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

FONCTION DE CONDENSATION MESSAGE DIGEST MD5

Une fonction de condensation (ou de hachage) calcule le résumé d'un texte, et ce résumé est très sensible au texte initial (une petite modification du texte provoque une grande modification du résumé). 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". Cet algorithme est utilisé pour les signatures numériques (notion utilisée, lors de la validation de certificats d'authenticité).

Voici les différentes étapes de cet algorithme:

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.

FONCTION DE CONDENSATION SECURE HASH ALGORITHM SHA-1

Le SHA-1 est utilize 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é. 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

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

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 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 nœuds 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 ains que la transmission instantanée d'un message sans liaison physique…