Courbes elliptiques et cryptographie multivariable

Durant cet article, nous allons vous parler de courbes elliptiques et de cryptographie multivariable, deux méthodes de cryptographie moderne.

Utilisation des courbes elliptiques dans la cryptographie

Comme nous l’avons vu dans notre précédent article, la cryptographie moderne fait appel à des procédés mathématiques toujours plus complexes afin de rendre les systèmes inviolables, mais également plus efficaces en assurant une meilleure protection avec des clés de poids plus faible.
Parmi les nouveaux procédés cryptographiques à clé publique, est apparue la cryptographie à base de courbes elliptiques.
La cryptographie à base de courbes elliptiques est très adaptée pour les nouveaux systèmes, notamment les systèmes embarqués, ou encore les cartes à puce, où les coûts et l’efficacité sont des contraintes importantes.
Pour vous donner un aperçu, la cryptographie à base de courbes elliptiques permet de réduire considérablement la taille des clés, notamment si on compare avec l’algorithme RSA, où quand celui-ci utilise des clés de 1024 bits, la cryptographie elliptique utilise des clés de 200 bits avec une sécurité plus élevée.

Petit rappel sur les courbes elliptiques

On appelle courbe elliptique, toute courbe d’équation :

y2 = x3 +ax + b

Et où le discriminant du membre de droite est non nul.
Une courbe elliptique est définie sur un corps K et se note E(K).

Considérons la figure suivant :

Courbe elliptique

On considère 3 points P(x1,y1), Q(x2,y2) et R(x3,y3) trois points de la courbe (E) et un point O situé à l’infini, tel que R = P + Q.
L’opération mathématique “+” définit une loi de groupe sur la courbe, on peut alors définir :
Opération

Nous avons ici fait un bref rappel sur les courbes elliptiques et défini ce dont nous allons avoir besoin afin de mieux comprendre son utilisation dans la cryptographie.

La mise en oeuvre dans la cryptographie

Les courbes elliptiques pour l’échange de clés

Comme nous l’avons dit en introduction, la cryptographie sur les courbes elliptiques est basée sur un échange de clés à la manière de Diffie et Hellman, c’est-à-dire sans se les communiquer directement.

Afin de communiquer, nos deux interlocuteurs vont devoir définir ensemble quelques paramètres.
Le premier paramètre, à définir publiquement, est un corps fini K, puis la courbe elliptique qui va servir.
Enfin le dernier paramètre à choisir publiquement est un point P.
La seconde étape pour nos deux interlocuteurs va être de choisir, cette fois-ci secrètement, un entier chacun (par exemple l’émetteur choisit un entier a et le récepteur un entier b).
Pendant la troisième étape, l’émetteur envoie au récepteur le point aP et le récepteur envoie le point bP.
Enfin, la dernière étape consiste à calculer, chacun de leur côté, a(bP) = b(aP) = (ab)P, qui est la clé voulue.

Lors de l’échange de clés par les courbes elliptiques, on peut remarquer qu’il y a beaucoup de dialogue entre émetteur et récepteur, se pose alors la question de la sécurité du procédé.
En effet, bien que beaucoup d’informations soient échangées, le secret reste intacte, et cela grâce à la notion mathématique de logarithme discret.
En effet, si une personne a écoutée l’échange entre nos deux interlocuteurs, elle va connaître la courbe, le corps fini, le point P, et les points aP et bP.
Cependant, pour pouvoir calculer la clé, ‘l’espion” va avoir besoin des entier a ou b.
Connaissant aP, bP et P, cela revient à résoudre le problème du logarithme discret, mais ce problème est extrêmement difficile à résoudre sur des courbes elliptiques.

Les courbes elliptiques pour la transmission de messages

Nous allons maintenant nous intéresser à l’envoi d’un message en utilisant la cryptographie à base de courbes elliptiques.
La première étape concerne le récepteur qui va fabriquer une clé publique à l’aide d’une clé privée b, d’une courbe elliptique E(A,B,K) et d’un point P de cette courbe.
La seconde étape concerne cette fois l’émetteur qui reçoit la clé publique constituée de la courbe, du point P et de bP.
Lors de la troisième étape, l’émetteur va choisir un entier n, calculer nP et M + nbP (M étant le message), et envoyer ces deux nouveaux points au récepteur.
Grâce à sa clé secrète b, le récepteur peut calculer nbP à partir de nP puis il lui suffit de calculer (M + nbP) – nbP pour trouver le message souhaité.

Nous avons donc vu la mise en oeuvre des courbes elliptiques dans la cryptographie pour l’envoi de messages et l’échange de clés.
Nous allons maintenant présenter les avantages et inconvénients de cette méthode.

Avantages et inconvénients de la cryptographie par courbes elliptiques

Comme nous l’avons vu, le principe de cryptographie par courbes elliptiques fait appel au procédé mathématique du logarithme discret.
C’est cet algorithme sur les logarithmes discrets qui fait la force d’un tel chiffrement car le problème mathématique à résoudre n’est plus sur de simples entiers, mais sur tout le groupe d’une courbe elliptique.
Le principal avantage de cela est que l’on va pouvoir générer des clés plus petites mais avec un niveau de sécurité plus élevé par rapport aux algorithmes plus classique de chiffrement.
Le second avantage d’un telle méthode est que les calculs sur les courbes elliptiques sont assez faciles à réaliser, ce qui est particulièrement intéressant pour des systèmes comme les cartes à puces, où la taille des clé est un facteur déterminant sur les performances, car leur puissance est limité.

Les principaux inconvénients du procédé subsistent du fait que la théorie des courbes elliptiques est complexe et encore assez récente, ce qui ne nous met pas à l’abri de solutions permettant de contourner le problème du logarithme discret.
Aussi, lors d’un échange de texte, il faut pouvoir transformer celui-ci en une suite de point d’une courbe elliptique ce qui est loin d’être facile !
Enfin, malgré son jeune âge, la cryptographie par courbes elliptiques a déjà fait l’objet de beaucoup de brevets, ce qui rend son utilisation assez chère.

Sources :
http://fr.scribd.com/doc/16760820/Exemple-de-cryptographie-elliptique

http://tel.archives-ouvertes.fr/docs/00/73/30/04/PDF/vverneuil_these.pdf

Cryptographie multivariable: une nouvelle “branche”

Présentation

De nos jours, la cryptographie à clef publique la plus utilisée peut être qualifiée de univariable (parfois bivariable). En effet, les équations qu’elle utilise sont le plus souvent univariables dans les anneaux ou corps finis. Quant aux cryptosystèmes basés sur les courbes elliptiques (EC), ils utilisent une équation bivariable. Cependant, dans la cryptographie multivariable, on utilise plusieurs équations avec plusieurs variables sur un corps ou anneau fini d’où le nom multivariable.

Prenons un exemple simple constitué de trois variables et de trois équations du second degré quadratiques:

y1 = x1 x1 + x1 x3 + x2 x3 + x3 x3
y2 = x1 x2 + x2 x2 + x3 x3
y3 = x1 x1 + x1 x2 + x2 x3 + x3 x3

Ici, le message à chiffrer est symbolisé par les xi. On peut donc facilement calculer les yi, mais il est nettement plus difficile de retrouver les xi en connaissant uniquement les yi. Il s’agit ici d’un exemple simple à valeur explicative mais en pratique, on utilise des centaines d’équations souvent quadratiques et des centaines de variables.

Par ailleurs, cette théorie repose sur les problème dits NP-complet. En d’autres termes, il s’agit de problèmes réputés les plus coriaces parmi un groupe de problèmes. Mais pour être plus précis, on définit les problèmes NP-complets comme suit:

  • c’est un problème pour lequel il est possible de vérifier une solution efficacement (en temps polynomial); cela correspond à la notation NP.
  • le problème est au moins aussi difficile que tous les autres problèmes de la classe NP puisque tout problème de la classe NP peut se ramener à ce problème par réduction polynomiale.

Cette branche de la cryptographie possède également une spécificité particulière qui est que les ensembles considérés ne possèdent plus de structure de groupe, ni aucune autre structure algébrique apparente. De fait on peut concevoir des cryptosystèmes que l’on ne pourra pas casser même en disposant d’une puissance de calcul exponentielle.

Pour situer un peu mieux la place des schémas multivariables parmi tous les autres, on peut faire une petite classification.

Classification des schémas multivariables et principe directeur

La cryptographie multivariable est une branche de la cryptographie à clef publique mais elle est basée sur des systèmes d’équations polynomiales sur des petits corps ou anneaux finis. On peut même aller jusqu’à distinguer trois styles:

  • Des cryptosystèmes multivariable linéaires sur des petits corps finis
  • Des schémas multivariables quadratique sur des petits corps finis
  • Les variantes combinatoires des schémas précédents

La dernière variante permet de modifier les schémas précédents en retirant un certain nombre d’équations par exemple. De cette manière, il est possible d’obtenir des schémas pour lesquels on ne connaît aucune attaque même théorique.

Pour élaborer le design des schémas multivariables, on cherche d’abord à trouver des schémas algébriques basiques liés voire même directement basés sur des problèmes algébriques difficiles à résoudre. Et pour compliquer un peu les choses, on rajoute une voire plusieurs couches combinatoires afin d’introduire des perturbations pour mettre à mal les attaques qui existent.

Solution classiques contre multivariables

Continuons à comparer les schémas multivariables comme le schéma HFE aux autres schémas bien connus – les schémas à clef publique tels que RSA, McEliece ou Courbes Elliptiques.

Pour commencer, pourquoi ces “nouveaux” schémas multivariables? Pour une raison simple et alarmante: le RSA arrive à son terme. En effet, on se rappelle tous du problème posé par le pirate Français Serge Humpich. Il avait désassemblé un terminal de paiement pour trouver la clef publique RSA utilisée par les banques pour signer les cartes bancaires. Et grâce à ça, il a pu fabriquer de fausses cartes capables de se faire passer pour des vraies dans certains terminaux simplifiés. Pour se faire, il a cassé RSA en réussissant à factoriser un entier de 320 bits qui avait été jugé largement suffisant dans les années 80. Petit échec auquel vient s’ajouter un autre en août 1999. Cette “attaque” résultait d’un effort conjoint de chercheurs issus de nombreux pays et de l’équipe de l’école Polytechnique et avait permis de casser le RSA avec une clé de 512 bits. De fait, à cause de ces quelques problèmes, le désir de trouver un successeur à RSA est devenu une priorité. Mais en attendant, on utilise des tailles de paramètres plus importantes – 1024 bits par exemple – pour assurer la sécurité de RSA. Mais de telles tailles commencent à être assez encombrantes.

Évidemment, d’autre solutions ont été proposées pour remplacer RSA, il n’y a pas eu que les schémas multivariables. On peut citer les schémas HFE (Hidden Field Equations) et les courbes elliptiques qui ont été proposées pour remplacer RSA. En fait, ces deux idées sont des voies de généralisation de l’idée RSA:

  • Les courbes elliptiques (EC) reposent sur des groupes mathématiques plus complexes
  • HFE reposent sur des polynômes plus complexes

Ce qui a justifié l’évolution aussi rapide de la cryptanalyse de RSA fut la structure algébrique Z/NZ qui est trop riche. De fait, le problème d’extraction des racines dans cette anneau, qui constitue le problème RSA n’est pas un problème exponentiel. Donc, pourquoi ne pas remplacer RSA par des cryptosystèmes exponentiels?

On peut citer les deux cryptosystèmes exponentiels bien établis qui permettent d’effectuer à la fois une signature et du chiffrement:

  • McEl, il s’agit du système de McEliece connu depuis 1978
  • Courbes elliptiques, connues depuis 1985 pour leur application cryptographique

Mais même dans ces deux cas, il existe des attaques de complexité égale à la racine carrée de la complexité d’une recherche en force brute. Ainsi, même si de nombreuses alternatives existent, aucun successeur ne semble se détacher du lot au vu des problèmes sur lesquels ils sont basés. Mais qu’en est-il de la sécurité de ces schémas?

Sécurité théorique et pratique

Commençons par quelques rappels sur les cryptosystèmes considérés:

RSA:

  • cryptosystème basé sur un problème algébrique, à savoir la factorisation.
  • problème RSA = problème d’inversion (ce problème semble aussi dur que la factorisation).

McEl:

  • ces systèmes reposent sur l’observation suivante, à savoir que les codes de Goppa sont assez nombreux et assez optimaux pour ne pas pouvoir les distinguer d’un code aléatoire.
  • le problème de Syndrome Decoding pour un code aléatoire est supposé être pleinement exponentiel à résoudre.

Pour en savoir plus sur le Syndrome Decoding et les codes de Goppa, vous pouvez vous référez aux liens suivants:
http://fr.wikipedia.org/wiki/D%C3%A9codage_par_syndrome
http://fr.wikipedia.org/wiki/Code_de_Goppa

EC:

  • il s’agit d’une généralisation des problèmes tels que RSA sur quelque chose de très compliqué. Ces cryptosystèmes sont uniquement basés sur l’opacité de la représentation du code sous-jacent.

HFE:

  • pour ce système, la sécurité se décline en deux niveaux emboîtés, la sécurité issue des problèmes algébriques et celle provenant de l’opacité de la représentation.

Maintenant que ces quelques rappels sur la sécurité théorique ont été faits, voyons ce qu’ils ont donné en pratique:

RSA:

  • ce système avec un bloc (ou clé) de taille 512 bits fut cassé en août 1999 et l’attaque avait même été exposées au Eurocrypt de la même année. Cette attaque nécessitait environ 258 opérations CPU

McEl:

  • ce système avec les paramètre d’origine qui étaient 1025, 524 et 101 a été cassé en 1998 à l’aide d’environ 260 opérations CPU

EC:

  • ce système avec un bloc de taille 97 bits fut cassé en septembre 1999 au cours d’un challenge posé par Certicom et l’attaque nécessitait environ 259 opérations CPU

HFE:

  • ce système avec un bloc de taille 80 bits a été cassé avec une attaque en 262 opérations CPU

La constatation est donc la suivante: à difficulté comparable, les cryptosystèmes multivariables semblent atteindre des tailles de blocs plus courts.

La cryptographie multivariable et son importance

Cette nouvelle cryptographie apporte de nouvelles choses à la cryptographie à clé publique de manière générale et ce sur plusieurs plans.

Pour commencer, elle utilise des schémas qui sont souvent beaucoup plus rapides, plus intuitifs et qui donnent des signatures beaucoup plus courtes que d’autres schémas. De fait, elle est plus efficace. De plus les coûts sont également plus faibles puisqu’à complexité égale, les tailles des blocs sont plus petites comme nous l’avons vu juste avant.

Ensuite, en sécurité, tout baser sur le même problème difficile comme la factorisation n’est pas forcément la meilleur stratégie à adopter. On a besoin de varier les types de problèmes, il s’agit de biodiversité, un terme créé par François Morain. Et c’est ce que fait la cryptographie multivariable car elle repose sur les problèmes dits NP-complets qui sont plus coriaces (complexité exponentielle) et plus variés que le “simple” problème de factorisation.

De plus, la cryptographie multivariable possède des propriétés uniques permettant des choses que les autres branches de la cryptographie ne peuvent pas faire. On peut citer par exemple la possibilité de créer des signatures très courtes, un attrait non négligeable. On rappelle d’ailleurs qu’une signature a pour but de permettre au destinataire de vérifier que tel message provient bien de l’émetteur indiqué. Et cet attrait est très recherché puisque pour les télévisions cryptées, les transmissions militaires, les cartes à puce, la sécurisation des transactions sur Internet, la protection des mots de passe sur un disque dur et bien d’autres applications, il est nécessaire d’avoir des clés compactes, ou des temps de calcul infimes, voire même les deux.

Quid de son histoire?

D’après les propriétés et avantages vus plus haut, on a constaté que la cryptographie multivariable était adaptée aux situations où la puissance de calcul était limitée (en raison de la faible taille des blocs), elle sert aussi pour le chiffrement et la vérification de signature en particulier. Mais parlons quand même de son histoire pour voir ce qu’elle est devenue.

En 1988, lors du congrès européen de cryptographie Eurocrypt, deux Japonais, Tsutomu Matsumoto et Hideki Imai ont proposé un premier schéma connu sous le nom “Matsumoto-Imai”, MI ou encore C* mettant à profit le principe de cryptographie multivariable. Dans ce schéma, les équations étaient de degré deux, comme dans notre exemple, limité à deux d’où le terme cryptographie multivariable quadratique MQ.

Ce schéma va rester invaincu pendant sept ans jusqu’à ce qu’une équipe française décide de s’attaquer à ce schéma. Elle finit par le casser en 1995 avec l’aide de Jacques Patarin. Première déconvenue pour cette branche de la cryptographie. Mais juste après cette cryptanalyse, Jacques Patarin propose de nouveaux schémas. C’est en 1996 à Eurocrypt qu’il va présenter un algorithme s’éloignant de la proposition de Matsumoto et d’Imai : HFE (Hidden Field Equations) basé sur des polynômes au lieu de monômes. Son approche est de plus très économe en temps de calcul. Il va poursuivre ses travaux en proposant un algorithme de signature en 1997nommé Oil and Vinegar (OV) assez similaire au MI. Le nom vient du fait que les variables du système d’équation sont séparées en deux catégories: les hi pour huile et les vi pour vinaigre. Les équations de ce système comportent tous les produits à l’exception du produit hi-hi.

Mais ce système OV va être démonté durant le congrès Crypto en 1998 par deux Israéliens. J. Patarin va donc le réparer donnant naissance au schéma Unbalanced Oil and Vinegar qui comportent beaucoup plus de variables  vi que hi publié en 1999 avec l’aide d’un des israéliens qui avaient démonté son schéma précédent.

Deux ans plus tard, J. Patarin publie SFLASH en se basant sur HFE, avec l’aide de Nicolas Courtois et Louis Goubin, deux membres de l’université de Versailles. Cet algorithme de signature numérique va s’avérer très convaincant du fait de son économie en puissance de calcul à la fois pour calculer et pour vérifier la signature. Cet algorithme va même finir par être homologué en 2003.

Donc, malgré quelques déboires la cryptographie multivariable a fini par s’imposer dans le milieu de la signature spartiate.

Mais c’était sans compter l’attaque proposée par Henri Gilbert lors de l’Eurocrypt de 2002. Car même si celle-ci n’a pas remis en question les fondements du schéma, elle a fini par engendrer des corrections au niveau des paramètres – au niveau de la taille des clés en fait. Suite à ce manque de sécurité, deux nouvelles versions de SFLASH vont voir le jour (avec des tailles de clé plus grandes même si la taille finale commençait à être un peu lourde pour les cartes à puce de 2008).

Il y a même eu des attaques sur HFE avec celle du congrès Crypto de 2003 menée par deux Français: Jean-Charles Faugère et Antoine Joux.

Puis, l’équipe constituée de Vivien Dubois, P.-A. Fouque et J. Stern de l’ENS va s’attaquer à une version dégradée de SFLASH et va réussir à casser cette version. Ainsi, SFLASH commence à être mis à mal. Puis c’est l’ensemble des versions normales de SFLASH (même la v3) qui va être détruit avec une petit coup de main d’un des fondateurs du RSA.

Somme toute, seul HFE semble encore tenir la route. La cryptographie multivariable a donc connu son heure de gloire avec SFLASH mais à l’heure actuelle, avec les nombreuses attaques subies, son âge d’or semble bel et bien fini.

Sources :
http://www.larecherche.fr/savoirs/dossier/gloire-deboires-cryptographie-multivariable-01-06-2008-74888
La sécurité des primitives cryptographiques basées sur des problèmes algébriques multivariables: MQ, IP, MinRank, HFE (thèse)

“Nouveaux” types de cryptographie

Introduction

Comme chacun sait, il y a eu une augmentation considérable des débits des télécommunications de ces dernières années que ce soit dans les transmissions numériques ou analogiques. Augmentation qui va naturellement de paire avec la montée en puissance des calculateurs ce qui conduit à se demander pendant combien de temps les algorithmes de calcul seront encore sûrs. Ces craintes sont d’autant plus importantes que les promesses faites sur les capacités de calcul de l’ordinateur quantique sont très prometteuses et surtout colossales.

C’est ainsi que deux alternatives ou plutôt deux nouvelles techniques ont fait leur apparition durant les dernières années : la cryptographie quantique et la cryptographie chaotique. Deux alternatives que nous allons expliciter un peu plus au cours de cet article.

La cryptographie quantique

Un des procédés cryptographiques qui a révolutionné la fin du XXe siècle est la cryptographie quantique se basant sur des propriétés de la physique quantique. Longtemps considérée comme une méthode quasiment invulnérable, nous verrons que des expériences lui ont démontrées quelques limites.

La cryptographie quantique est donc un moyen cryptographique qui utilise des propriétés de la physique quantique afin d’atteindre des niveaux de sécurité qu’un procédé classique ne pourrait pas atteindre. Ce procédé est surtout utilisé pour chiffrer les clés lors d’une communication entre deux personnes distantes. La sécurité de ce procédé se base essentiellement sur les lois de la physique quantique et la théorie de l’information. Jusqu’à maintenant le moyen de transmettre des clés secrètes entre deux personnes distantes afin que celles-ci puissent communiquer, était la valise diplomatique. Nous allons voir en quoi la cryptographie quantique a sonnée au coup de tonnerre en terme de sécurité.

Afin de vous faire comprendre comment marche ce procédé, il est temps de vous mettre en situation. Pour cela nous vous présentons 3 personnages : Alice et Bob qui communiquent entre eux, et Eve qui les espionne. Ces 3 prénoms sont couramment utilisés pour expliquer les procédés cryptographiques, notamment Eve signifie “eavesdropper”, oreille indiscrète en anglais. Voici ce dont disposent nos deux interlocuteurs :

  • des objets quantiques, comme des impulsions lumineuses : des photons.
  • un canal quantiques qui va permettre au objets quantiques de se déplacer d’un point à un autre, comme la fibre optique.
  • un canal classique de communication, comme Internet.
Chacun des photons peuvent être polarisés sur des angles qui vont varier de 0° à 180°. Les protocoles de cryptographie quantique les plus connus sont le BB84 et le E90 mis au point par les canadiens CH.Bennett et G.Brassard. Dans ces protocoles les champs magnétiques des photons prennent des directions de 0°, 45°, 90° et 135° soit 4 positions possibles.

Champs magnétiques

Pour les polarisations de 0 et 90° on parle de polarisation rectiligne et pour 45 et 135°, de polarisation diagonale.

Afin de détecter l’orientation du photon, le receveur va utiliser un filtre, qui comme les photons peut être orienté. Dans le cas d’un filtre orienté à 0°, si un photon orienté à 0° est transmis, il va traverser le filtre et donc être enregistré par le receveur qui dispose d’un détecteur. Maintenant si l’émetteur transmet un photon orienté à 45 ou 135°, le photon va traverser le filtre une fois sur deux. Il est donc possible de distinguer une polarisation de 0° contre une polarisation de 90° mais les polarisations 45 et 135° sont in-différentiables. C’est le protocole de sécurité qui nous allons expliquer par la suite qui va permettre de les différencier. Il faut noter que dans le cas d’un filtre orienté à 45°, il laissera passer les photons orientés à 45°, stoppera ceux à 135° et reviendra le même problème pour les photons à 0 et 90°.

Après ces explications, nos deux personnages Alice et Bob peuvent commencer à s’échanger la clé secrète via le canal quantique. Alice va émettre une série de photons où les 0° et 45° représentent 0, et 90° et 135° vont représenter 1. De l’autre côté, Bob va recevoir les photons et mesurer leur polarité avec un filtre rectiligne ou diagonal, et considérera 0 si le photon traverse le filtre, 1 sinon.

Lors de la mesure avec par exemple un filtre rectiligne, si un photon est orienté diagonalement, il passera une fois sur deux et donc la mesure de Bob pourra être fausse. C’est là qu’intervient le canal classique de communication entre les deux interlocuteur. Bob va pouvoir indiquer à Alice le filtre qu’il a utilisé et Alice va alors pouvoir confirmer ou non la mesure de Bob. Les bits qui seront connus d’Alice et Bob constitueront la clé secrète.

Le canal classique va être primordial pour la sécurité du système. En effet, si Eve était en train d’écouter la transmission d’Alice vers Bob, elle effectuait en fait le même travail que Bob. Eve intercepte donc le photon, et afin que son action reste invisible, il renvoie immédiatement un photon vers Bob en essayant de transmettre le même qu’Alice. Cependant elle a une chance sur deux de renvoyer le même photon, donc Bob a maintenant une chance sur quatre d’avoir une mesure fausse. Alice est Bob vont donc sacrifier quelques uns des bits communs afin de vérifier la sécurité :

  1. Alice émet un photon à 45° de valeur en bit 0
  2. Eve intercepte avec un filtre rectiligne, lit 1 et transmet un photon à 90°
  3. Bob reçoit le photon avec un filtre diagonal, le photon passe, Bob note 1
  4. Alice et Bob sacrifient la mesure, Bob annonce un filtre diagonal

Alice et Bob peuvent donc en conclurent qu’Eve les a espionnée

La cryptographie quantique commence t-elle à montrer ses limites ?

Grâce à ce procédé, la cryptographie quantique demeure très sûre, bien que quelques expériences commencent à démontrer le contraire, notamment des travaux au sein de l’université des sciences et technologies de Norvège, ou des chercheurs sont parvenus à trouver un moyen d’écouter une communication sans utiliser le canal direct de communication afin de le pas laisser de trace. Les chercheurs sont allés directement aveugler la machine émettrice grâce à des flashs laser. Grâce à ce procédé, les chercheurs ont intercepté 4% des communications sécurisées.

Comme tout procédé élaboré par l’Homme, la cryptographie quantique commence peut-être à montrer ses limites, ce qui devrait qui continuer dans le futur avec l’apparition des ordinateurs quantiques. Comme toujours l’Homme va devoir encore rechercher une méthode plus performante afin de répondre à l’évolution des technologies et l’évolution des travaux de chercheurs mal intentionnés ou non.

La cryptographie chaotique

Avant toute chose, il faut savoir que la cryptographie par chaos a déjà donné la preuve de sa faisabilité et de sa puissance de chiffrage qui excède 1 Gbits/s.

Principe du cryptage par chaos

Dans certain cas, en cryptanalyse, il est possible d’utiliser la répétabilité du signal transmis. En effet, les algorithmes “actuels” de cryptage sont des suites de nombres pseudo aléatoires. De fait, on peut, à l’aide du signal crypté si celui-ci est suffisamment long, retrouver la clé. On peut résoudre ce type de faille en choisissant un clé d’une dimension relativement importante et suffisamment complexe afin d’éviter que, même sur le long terme, on ne puisse pas remonter à la clé à l’aide du texte crypté. Une bonne idée pourrait donc reposer sur l’utilisation d’un bruit aléatoire, fonction du temps, comme clé.

Pour en revenir au chiffrement d’un message par le chaos, la méthode est la suivante. Ce chiffrement est basé sur la superposition d’un signal chaotique à l’information initiale que l’on veut chiffrer. C’est cette superposition que l’on va envoyer à un récepteur connaissant les caractéristiques du générateur de chaos. Le destinataire n’a plus qu’à soustraire la superposition chaotique du message qu’il a reçu afin de récupérer le message clair. Tout cela semble parfait à l’exception du fait que le décryptage est une étape pour le moins critique notamment en ce qui concerne la recréation de la composante chaotique à soustraire.

Petit rappel succinct sur le chaos

Comment savoir qu’un phénomène peut être qualifié de chaotique ? C’est le cas lorsque le phénomène présente un comportement désordonné et ceci peut se constater sans recherche particulièrement poussée. C’est le cas du jeu de billard puisque l’on peut aisément concevoir que l’on ne pourra pas renvoyer une boule exactement d’où elle vient, sauf en utilisant exactement la même force et le même angle. Et même en remplissant ces conditions, le comportement des bandes du billard ne sera pas forcément le même non plus. Ainsi, on comprend aisément l’importance des conditions initiales pour un tel système. Cette sensibilité aux conditions initiales est la caractéristique propre de tout système chaotique.

Et pour plus d’informations sur la théorie du chaos et ses principes fondamentaux comme le déterminisme :
http://just.loic.free.fr/

La synchronisation des signaux chaotiques

Comme nous l’avons fait remarquer juste avant, le vrai problème que pose un système de cryptographie chaotique provient du phénomène présenté avec l’exemple de la boule de billard : un joueur de billard est incapable de renvoyer sa boule d’où elle vient du moins volontairement. Ainsi, faire le chemin inverse – consistant à reproduire exactement un signal chaotique dans notre cas – va devenir une opération très complexe voir irréalisable. Et donc décrypter un message risque d’être assez difficile. De fait, même si cette méthode semble sure, s’il est impossible de déchiffrer le message transmis, l’intérêt d’un tel chiffrement diminue significativement.

C’est en 1996 que Thomas Caroll et Louis Pecora vont faire une découverte surprenante dans ce domaine en parvenant à reproduire à l’identique un signal électrique chaotique et à le mettre en phase avec le signal original, phénomène connu sous le nom de synchronisation des signaux chaotiques. Un phénomène indispensable sans lequel cette méthode de cryptographie ne serait pas valide.

Générateur optique de chaos

Pour ne citer q’un exemple de générateur de chaos, on peut parler des générateurs optiques de chaos utilisant des dynamiques engendrées par des oscillateurs non linéaires à retard. L’une des principales études réalisées dans ce domaine l’a été par par le physicien japonais Kensuke Ikeda qui a choisi d’analysé les variations de la puissance optique en sortie d’une cavité optique non linéaire en forme d’anneau aussi appelée boucle à retard ou encore anneau d’Ikeda. On injecte un faisceau laser dont la puissance est constante dans cet anneau optique en matériau non linéaire (ce qui signifie, entre autres choses, que son indice de réfraction varie avec l’intensité optique). Après un tour dans ladite cavité, le faisceau va interférer avec lui-même créant ainsi une interférence induisant une variation de l’intensité lumineuse dans la cavité qui va elle-même provoquer une modification de l’indice de réfraction de la boucle. Cet enchaînement va entraîner un chaos d’intensité lumineuse au fur et à mesure que le rayon tournera dans l’anneau.

Ce comportement est décrit par des équations différentielles à retard ou équations d’Ikeda qui sont de la forme :
équation différentielle à retardDans ces équations, T correspond au retard du faisceau dû aux interférences, entraînant un chaos de plus en plus complexe à mesure que T grandira.

Composantes d’un système de chiffrement par chaos

Un système de cryptage par chaos comme bien d’autres systèmes de chiffrement se compose de deux parties : le brouilleur et le décrypteur. Dans notre cas, ces deux éléments sont strictement identiques compte tenu de la sensibilité d’un système chaotique aux conditions initiales : pour obtenir le même résultat (signal chaotique) les conditions initiales doivent être scrupuleusement identiques. Pour mettre en place La synchronisation des dispositifs, on amorce le chaos dans le système récepteur en injectant dans sa boucle à retard l’ensemble “information + dynamique chaotique superposée” puis on attend que les générateurs de chaos soient synchronisés via un signal de synchronisation provenant du générateur de chaos de l’émetteur. On remarque que cette méthode nécessite généralement deux canaux de transmission : l’un pour le signal crypté et l’autre pour la synchronisation. Comme mentionné plus haut, c’est cette étape qui constitue la phase critique de l’opération de déchiffrement. En effet, le moindre écart lors du processus de chiffrement va entraîner un parasite sur l’information aussi appelé bruit de déchiffrement, ce qui rendra illisible l’information.

Limite de complexité

Pour limiter les bruits de déchiffrement on peut choisir un chaos moins complexe au détriment de la qualité du chiffrement. Ainsi, tous les phénomènes chaotiques ne peuvent pas servir à chiffrer un message car même si le degré de complexité assure la sûreté du message, si le phénomène chaotique n’est pas reproductible, on ne pourra pas obtenir une restitution suffisamment claire de l’information.

C’est ainsi que s’achève notre article sur ces deux nouvelle méthodes de chiffrement toutes deux prometteuses. Mais soyez rassurés, si vous avez apprécier ce survol, vous allez pouvoir approfondir le sujet en consultant les liens suivants :

http://www.google.com/patents/EP0963064B1?cl=fr
http://blog.4j4x.net/?p=27

http://www.bibmath.net/crypto/index.php?action=affiche&quoi=moderne/quantique

http://www.lemonde.fr/technologies/article/2009/06/19/le-secret-etait-presque-parfait-la-cryptographie-quantique-n-est-pas-invulnerable_1209092_651865.html

http://fr.wikipedia.org/wiki/Cryptographie_quantique

http://www.femto-st.fr/~laurent.larger/Homepage_ll_fichiers/pdf_files/HDR_ll.pdf (mémoire assez complet et complexe)

Cryptographie symétrique et asymétrique

Après le précédent article où nous avons abordé la cryptographie à travers l’histoire avec quelques exemples connus ou à connaître, nous allons maintenant voir ce que la cryptographie est devenue en parlant de deux axes majeurs de ce domaine. Commençons d’abord par la cryptographie symétrique.

Cryptographie symétrique

En cryptographie, on peut trouver deux approches différentes pour protéger les données. On trouve la cryptographie symétrique aussi nommée à clé secrète et la cryptographie asymétrique ou à clé publique. Dans les deux cas, les objectifs fonctionnels visés sont similaires. De fait, le choix de la méthode est plus une affaire de contexte d’utilisation.

Parlons maintenant de la cryptographie symétrique. Elle regroupe tous les mécanismes cryptographiques qui font appel à des opérations de protection et de recouvrement qui peuvent facilement se déduire l’une de l’autre. Ainsi, ces opérations doivent rester secrètes. C’est pour cette raison que l’usage des mécanismes reposant sur la cryptographie symétrique implique l’établissement d’un secret préalablement partagé entre toutes les entités voulant communiquer de manière sécurisée naturellement.

Les premiers mécanismes de cryptographie symétrique

Ces premiers mécanismes étaient utilisé dans le domaine militaire (encore une avancée grâce à la guerre). Ils servaient à protéger la confidentialité des messages entre leurs émetteurs et leurs destinataires. Dans un premier temps, la transformation d’un message clair en un message crypté (message incompréhensible toute personne autre que le ou les destinataires)  passait par des procédures secrètes. C’est donc cette opération que l’on partageait entre les différents participants.

Un des premiers exemples de cette cryptographie symétrique est le chiffrement de César dont nous avons déjà parlé dans notre précédent article.

Le principe de Kerckhoffs

Cependant, avec la croissance du besoin de transmettre des messages protégés en confidentialité, les limites des premières méthodes de cryptage ont vite été atteintes. Et pour cause, devoir créer de nouvelles opérations pour chaque couple émetteur-destinataire est vite devenue compliqué voire irréaliste en raison du très grand nombre de couples. Par ailleurs, quantifier la notion de secret utilisée dans un algorithme n’est pas aisée et même si une méthode est inventée par un cryptologue cela ne signifie pas pour autant qu’un attaquant ne peut pas imaginer le fonctionnement d’une telle opération. Et enfin, conserver ces procédés secrets peut s’avérer difficile. C’est alors que les cryptographes ont mis en place le concept de clé. Il s’agit en fait d’un paramètre qui est choisi aléatoirement. Ce paramètre est utilisé dans la fonction de chiffrement évitant ainsi de devoir créer un nouvel algorithme à chaque fois que l’on veut le réutiliser pour un nouveau couple émetteur-destinataire. Il suffit de modifier la clé. Une clé possible pour le chiffre de César pourrait être le nombre de positions par lequel on décale chaque lettre dans l’alphabet.

Ce concept, même si assez « simple », fut une véritable révolution qui a permis une large réutilisation d’un même algorithme. Mais cela a contribué à rendre publiques les algorithmes très réutilisés conduisant ainsi Auguste Kerckhoffs, un cryptologue néerlandais du XIXe siècle, à énoncer un principe fondamental :

« La sécurité d’un cryptosystème doit résider dans le secret de la clé. Les algorithmes utilisés doivent pouvoir être rendus publics »

Ainsi, même si un algorithme de chiffrement est publié, si le constat précédent est vérifié, l’impact d’une telle publication s’en trouvera réduit.

Description sommaire d’une fonction de chiffrement symétrique

Pour résumer tout ce qui a été dit précédemment : la confidentialité des données, en cryptographie symétrique, repose sur l’utilisation d’une fonction avec un paramètre correspondant à la clé secrète qui sera partagée entre l’émetteur et le destinataire d’un message.

Figure illustrant le fonctionnement du chiffrement symétriqueLe chiffre de Vernam : fonctionnement et limites

C’est en 1926 que le chiffre de Vernam, un cryptosystème, a été inventé. Sa sécurité est inconditionnelle. En d’autres termes, même en interceptant le message chiffré via ce système, la seule chose que l’on pourra apprendre à propos du message clair sera sa longueur quelle que soit la puissance de calcul utilisée par l’attaquant.

De plus, suivant la façon dont est représenté le texte clair (suite de 0 et de 1 en informatique par exemple), on peut trouver plusieurs versions de ce cryptosystème. On va prendre ici le cas d’une représentation « normale » c’est-à-dire utilisant les 26 lettres de l’alphabet latin.

Pour cette méthode, la clé est une suite de nombres de même taille que le message. Par ailleurs, il vaut mieux choisir ces nombres (modulo 26) de manière aléatoire pour qu’ils soient deux à deux indépendants. On a donc pour chaque lettre du message clair un nombre correspondant et on décale la lettre de ce message dans l’alphabet conformément au nombre de la clé. Pour déchiffrer le message, on applique le décalage dans l’autre sens.

En théorie, le chiffrement de Vernam pourrait être une méthode idéale mais on peut pointer deux gros inconvénients :

  • La clé doit être de même longueur que le message à transmettre.
  • Les clés ne peuvent pas être réutilisées

En effet, supposons que l’on utilise deux fois la même clé et qu’un pirate intercepte deux messages chiffrés avec cette clé. Il serait alors en mesure d’en extraire des informations. Il pourrait même déchiffrer partiellement ou totalement les messages interceptés. Et pour cause, le décalage serait le même pour chaque lettre des deux messages interceptés. La preuve de l’efficacité d’une telle attaque a été démontrée par les services secrets américains et britanniques qui ont, de cette façon, réussi à déchiffrer des messages soviétiques, durant la guerre froide.

De fait, l’organisation nécessaire à la bonne mise en place et à l’utilisation d’un tel système serait bien trop lourde voire impossible à assurer en pratique. Par ailleurs, en 1949, Shannon a démontré que l’on pouvait obtenir une sécurité inconditionnelle à condition d’avoir un coût au moins égal à celui du chiffrement de Vernam. Encore une fois, la réalité est différente. Ainsi, les systèmes actuellement utilisés n’atteignent pas ce niveau de sécurité. On se contente d’assurer une sécurité calculatoire même si celle-ci est fortement dépendante de la puissance des ordinateurs qui est multipliée par deux tous les 18 mois.

Le chiffrement par flot

Les inconvénients du chiffrement de Vernam qui ont été mis en évidence ont toutefois conduit à l’élaboration de nouveaux algorithmes de chiffrement par pallier ces problèmes. C’est ainsi qu’est né le chiffrement par flot qui utilise des clés courtes et réutilisables. Il fonctionne de la façon suivante :

  • On choisit une clé secrète K partagée entre un émetteur (Emil) et le récepteur (Remi) du message
  • Emil choisit une valeur aléatoire IV. Et à l’aide de ces deux valeurs (IV et K) et d’un algorithme public (appelé générateur de pseudo-aléa cryptographique), il va créer une suite S de nombres de longueur prédéfinie. Les nombres de cette suite sont ainsi générés de manière pseudo-aléatoire : ils doivent donner l’illusion d’être choisis totalement au hasard et sans la clé, on ne doit pas pouvoir retrouver cette suite même si une personne en possède une partie.
  • Emil utilise cette suite de nombres comme clé pour le chiffrement de Vernam.
  • Il envoie ensuite IV et le message chiffré.
  • Remi reçoit le tout et en déduit S pour faire le processus dans le sens inverse.

Le chiffrement par blocs

Les primitives (« combinaison d’algorithmes ou pratiques ») de chiffrement par flot permettent d’effectuer un chiffrement rapide  en traitant les données bit par bit mais cela n’a conduit à aucun cryptosystème avec des garanties suffisantes en termes de sécurité à ce jour. A la place, c’est le principe de chiffrement par blocs qui a permis l’élaboration de la plupart des primitives utilisées de nos jours.

Le principe est simple : Emil découpe le message à traiter en blocs de longueur fixe, et on traite ces blocs de manière successive. On va donc transformer les messages clairs de taille fixe N en des messages chiffrés de taille N via une clé de longueur K. De plus, cette opération doit être inversible.

Il existe de nos jours quatre modes de chiffrement par blocs. Le cryptage par blocs (block-cipher) est beaucoup plus utilisé et assure une meilleure sécurité. De plus, plusieurs normes existent : le DES datant de 1977, le triple-DES qui en découle directement, et pour finir l’AES datant de 2001. Pour plus d’informations sur ce domaine, vous pouvez suivre les deux liens suivant :

http://www.securiteinfo.com/cryptographie/symetrique.shtml
http://iml.univ-mrs.fr/~rodier/Cours/Blocs.pdf

Parlons maintenant de quelques notions importantes à respecter pour la cryptographie de la façon dont cela est assuré dans le cas de la cryptographie symétrique.

Confidentialité, intégrité et authentification

En cryptographie, la protection en confidentialité d’un message a pour but de restreindre la lecture de son contenu à un petit nombre d’entités en transformant ce message pour qu’il soit incompréhensible. Etant donné qu’en cryptographie symétrique, tout repose sur la connaissance de d’une clé privée comme nous allons le voir après, il faut donc avoir partagé de manière sécurisée autant de clés secrètes différentes que d’interlocuteurs potentiels ce qui est avantageux dans le cas où il y en a peu (communications point à point, chiffrement d’archives, architectures en étoile…) Dans l’autre cas (de nombreux interlocuteur potentiels), cela nécessite une couche de gestion des clés souvent réalisée à l’aide de la cryptographie asymétrique.

Il existe également le mécanisme d’authentification qui est doit permettre à une entité de s’assurer de l’identité de l’origine des messages reçus.

Enfin, on peut parler de la protection en intégrité d’une donnée. Il s’agit de prouver au destinataire du message que celui-ci n’a pas été modifié depuis qu’il a été envoyé. Dans le cas de la cryptographie symétrique, ceci est assuré par la transmission d’un MAC ou Message Authentication Code qui est spécifique à un message donné. Le MAC fonctionne grâce à la clé secrète partagée. De plus, si la clé partagée est symétrique, la validité du MAC implique l’authenticité de son origine puisque les seuls détenteurs de la clé secrète sont l’émetteur et le récepteur.

Point essentiel à retenir

Rappelons donc le point le plus important de la cryptographie symétrique qui se trouve dans le principe de Kerckhoffs :

« la sécurité d’un système cryptographique doit résider dans le secret de la clé ».

Toutes ces méthodes reposaient sur la connaissance préalable d’une clé partagée entre les personnes voulant communiquer, chose assez contraignante, ce qui va conduire à l’élaboration de la cryptographie asymétrique dont nous allons maintenant parler.

Cryptographie Asymétrique

Comme nous avons pu le voir, la notion de cryptographie symétrique repose sur la connaissance d’un secret par plusieurs entités. Nous allons donc maintenant pouvoir introduire le concept de cryptographie asymétrique ou également appelée cryptographie à clé publique.

La cryptographie asymétrique est basée sur le même principe mathématique d’asymétrie. En effet, certaines fonctions mathématiques peuvent être calculées facilement par ordinateur, mais l’opération inverse reste difficile à réaliser. Grâce à cette notion mathématique, on peut alors définir des couples d’opérations inverses l’une de l’autre, l’une étant publique et l’autre reposant alors sur la connaissance d’un secret. En se basant sur ces notions mathématiques, on peut alors donner une définition de la cryptographie asymétrique :

« Ensemble de mécanismes reposant sur des fonctions mathématiques asymétriques, qui sont faciles à calculer mais dont l’inverse est difficile à calculer pour quiconque sauf celui qui connaît la clé privée. »

Naissance de la cryptographie asymétrique

La notion d’asymétrie dans la cryptographie est apparue en 1976 lorsque deux cryptologues américains Whitfield Diffie et Martin Hellman ont publié un article mettant en œuvre le principe d’asymétrie en cryptologie.

Leur principe repose sur le fait qu’il n’y pas nécessité, pour que tout se passe bien, que la clé de chiffrement soit la même que pour le déchiffrement.

De plus, les deux cryptologues ont constaté que, pour la protection de données en confidentialité par exemple, le chiffrement d’un message pourrait être effectué par tous alors que le déchiffrement devrait être effectué seulement par le destinataire du message.

L’intérêt de l’asymétrie serait alors que la clé de chiffrement pourrait être rendue publique, donc utilisable par tous ceux qui voudraient chiffrer un message, on parle alors de clé publique, alors que la clé de déchiffrement serait propre au destinataire, on parle de clé privée.

L’idée de Diffie et Hellman est alors apparue comme une petite révolution dans le monde de la cryptographie et il restait maintenant à trouver les outils mathématiques adéquats, des problèmes mathématiques dont la solution serait extrêmement difficile à trouver, et ce, par les ordinateurs les plus puissants au monde.

Nous allons exposer le problème de la factorisation des grands nombres entiers, c’est un problème utilisé aujourd’hui dans la cryptographie asymétrique.

Petits rappels d’arithmétique :

  • Si a et b sont deux nombre entiers, a est dit divisible par b si le reste de la division de a par b et 0. b est alors un diviseur de a.
  • Un nombre entier a est dit premier s’il admet exactement deux diviseurs distincts : 1 et a.

Petits exemples :

  • 7 = 7 * 1 donc 7 est premier.
  • 6 = 1 * 6 = 2 * 3 donc 6 n’est pas premier.

Définition : Factorisation.

Trouver deux grands nombres premiers p et q et calculer leur produit N = p*q et assez simple, en revanche, le problème consistant à retrouver p et q connaissant N est difficile quand p et q sont grands. C’est ce problème que l’on appelle factorisation.

On peut illustrer le problème de cette façon :

Illustration du problème de factorisation

La première primitive de chiffrement asymétrique est publiée en 1978 par Rivest, Shamir et Adleman.

Elle est alors basée sur le problème de factorisation ci-dessus, c’est la primitive RSA.

Le principe de fonctionnement est le suivant :

  1. Génération de la clé publique.
    Le destinataire choisit deux grands nombres premiers p et q et calcule leur produit N. Il choisit également un exposant e qui ne doit avoir aucun diviseur premier commun avec (p – 1)(q – 1). Il publie ensuite N et e.
  2. Calcul de la clé privée.
    Seule la connaissance de p, q et e permet de calculer l’exposant privé d.
  3. Chiffrement.
    Pour chiffrer un message m, l’émetteur calcule c = me [N].
  4. Déchiffrement.
    Le déchiffrement s’obtient en calculant m = cd [N].

Ce qu’il faut retenir pour la primitive RSA :

La primitive RSA repose sur le principe de la factorisation. La clé publique contient un entier N, produit de deux grands nombres premiers p et q. La connaissance de p et q permet d’effectuer des opérations de déchiffrement.

Application de la cryptographie asymétrique

Notion de chiffrement hybride

Comme on l’a vu, lors d’un chiffrement asymétrique, chaque utilisateur génère une clé privée, et sa clé publique est diffusée. Cela permet de résoudre les problèmes de gestion des clés dans les réseaux de taille importante. Le principal problème de l’asymétrie par rapport à la symétrie va être le problème du débit, en effet les mécanismes mis en œuvre sont moins performants. C’est donc à partir de ce constat qu’est né le chiffrement hybride. Le principe fait appel à de la cryptographie symétrique et à de la cryptographie asymétrique.

Définition : Chiffrement hybride.

Le chiffrement d’un message M se déroule en deux étapes. Dans un premier temps, l’émetteur choisit une clé symétrique K aléatoire. Il utilise ensuite cette clé K pour chiffrer de manière symétrique le message M. Ensuite il chiffre de manière asymétrique cette fois, la clé K avec la clé publique du destinataire. Il envoie à son destinataire les chiffrés de M et de K. Le destinataire déchiffre d’abord la clé K, puis l’utilise pour retrouver M.

Le chiffrement asymétrique possède donc un grand avantage lorsque le nombre d’interlocuteurs est grand.

Le chiffrement hybride étant composé des chiffrements symétrique et asymétrique, il possède les avantages des deux procédés.

Autres applications : signature électronique et certificat

La signature électronique est l’équivalent de la signature manuscrite. Cette donnée doit garantir l’intégrité du message et authentifier celui qui l’envoie. Ici, l’opération privée va correspondre à la signature du message qui sera effectuée par l’envoyeur à l’aide de la clé privée. La vérification de la signature repose uniquement sur l’utilisation de la clé publique et peut être effectuée par tous.

Nous avons ainsi passé en revue les deux axes majeurs autour desquels la cryptographie d’aujourd’hui s’est développée. C’est donc tout pour cette fois.

Aperçu des méthodes de cryptographie du passé

Fidèles à notre poste, nous allons cette semaine vous parler de quelques méthodes de cryptographie du passé. Nous parlerons de la cryptographie par substitution mono-alphabétique avec le célèbre chiffre de César, entre autres et nous parlerons pour finir d’une méthode qui a fait loi pendant près de 3 siècles.

Principe de la cryptographie par substitution mono-alphabétique

Le cryptage par substitution mono-alphabétique est un des codages les plus anciens, et également certainement le codage le plus simple à réaliser. Cette méthode va simplement consister à remplacer une lettre donnée par une autre lettre de l’alphabet ou un signe quelconque. On parle de substitution mono-alphabétique car une même lettre n’est remplacée que par une seule et même lettre.
Voici un premier exemple :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
W X E H Y Z T K C P J I U A D G L Q M N R S F V B O

Le message « Un petit roseau » va alors donner « MT JCGLG UZVCNM ». Le déchiffrement du message s’obtient simplement avec la même clé de chiffrement. L’un des problèmes de ce chiffrement est qu’il faut se souvenir de la clé utilisée, c’est-à-dire de la permutation de l’alphabet utilisée.

Pour cela il existe plusieurs techniques dont la première est de se baser sur un mot-clé et ensuite de compléter la clé par la suite alphabétique du mot. Par exemple, choisissons comme mot-clé : SRETI, la clé de chiffrement sera :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
S R E T I J K L M N O P Q U V W X Y Z A B C D F G H

Deux autres techniques sont, ou ont été, utilisées pour se souvenir de la clé, le chiffrement AtBash qui consiste à simplement inverser l’alphabet, ou encore le code de César fondé sur un simple décalage de lettres.

Principe du Code de César

Le chiffrement par substitution mono-alphabétique remonte maintenant à de nombreux siècles. En effet, les premières traces d’un tel codage remontent à l’époque de Jules César. On sait que, pour transmettre des messages secrets, César s’est essayé à des méthodes toutes plus originales les unes que les autres.

Par exemple, une méthode consistait à raser la tête d’un esclave sur laquelle on inscrivait ensuite le message puis, une fois que les cheveux avaient repoussé, on envoyait l’esclave délivrer le message. Cependant à cause de l’attente que cette méthode engendrait, César a dû recourir à des moyens plus ingénieux dont le plus célèbre reste le Code de César qui constitue la méthode de cryptographie la plus ancienne connue à ce jour.

Il va consister à décaler les lettres de l’alphabet d’un ou plusieurs rangs. Il faut noter que César lui ne décalait les lettres que de 3 rangs, c’est pour cela qu’officiellement, le chiffre de César ne correspond qu’au chiffrement par un décalage de 3 lettres.

Par exemple, pour un décalage de 3 lettres :

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Ainsi la phrase « Je levai les yeux » devint « MH OHYDL OHV BHXA ».

La sécurité d’un tel chiffrement est assez limitée puisqu’il n’existe que 26 façons différentes de crypter un message avec ce code. Cependant on trouve encore quelques traces d’utilisation des siècles plus tard, par exemple l’armée russe l’aurait utilisée en 1915, ainsi que des sudistes pendant la guerre de Sécession.

Le carré de Polybe

Voici une méthode de chiffrement qui remonte également à l’antiquité. Polybe, un historien grec est capturé par les Romains parmi 1000 otages à la suite de la bataille de Pydna en Macédoine et à la victoire de Paul-Émile sur les Grecs.

Le carré de Polybe est un carré comportant 25 cases (pour notre alphabet), ce qui signifie que l’on place le I et le J dans la même case et donc ils auront le même codage. Chaque lettre va alors être codée par ses coordonnées dans le tableau, en commençant par la ligne puis la colonne. Par exemple, on va coder A par 11 et B par 12.

Le carré de PolybeProcédons à un exemple : le mot SRETI va ici être codé par : 4342154424.

Plusieurs variantes du carré de Polybe consistent notamment à remplir le tableau de manière différente et en commençant, pourquoi pas, par un mot-clé et la suite de l’alphabet.

Une des dernières grandes utilisations connues de l’utilisation du carré de Polybe remonte aux XIXème et XXème siècle. En effet, il fut utilisé par les nihilistes russes (terroristes russes souhaitant la chute du Tsar) enfermés dans des prisons du Tsars. Afin de faire parvenir les messages entre les cellules, ils tapaient sur les murs ou la tuyauterie afin de pratiquer une transmission de message très proche du morse, la différence est qu’ici, on peut modifier la clé. S’ils avaient voulus transférer le mot SRETI, les prisonniers auraient tapés comme suit : 4.3 – 4.2 – 1.5 – 4.4 – 2.4, les . désignant des silences brefs et les – des silences prolongés.

Le chiffre des templiers

On a vu que dans les codes précédents, pour crypter un message, on se contentait de remplacer une lettre par une autre selon une clé bien définie. Et si, au lieu de ça, on décidait de remplacer chaque lettre par des symboles… C’est là ce que certains ont préféré. En fait, ce sont surtout les membres de société plus ou moins secrète qui ont utilisé ce procédé comme les francs-maçons au XIXè s. avec le chiffre de PigPen.

Mais pourquoi les templiers ont-ils eu besoin de coder les lettres qu’ils s’échangeaient ? Pour le savoir faisons un rapide rappel d’histoire : le Temple, un ordre de moines fondé au XIIème siècle, avait pour mission d’assurer la sécurité des pèlerins en Terre Sainte. Mais assez rapidement, les templiers se sont détournés du droit chemin pour chercher richesse et pouvoir. Et ils se sont tellement enrichis qu’ils ont fini par devenir les trésoriers du roi et du Pape. Et de fait, par souci de sécurité, ils ont dû coder les lettres de crédit qu’ils s’échangeaient. Cet alphabet de substitution provient de la croix « des huit béatitudes » qui étaient l’emblème de leur ordre.

Emblème des templierscode des templiers

Si on fait abstraction de la petite difficulté provenant de l’utilisation de symboles peu courants ce système de chiffrement n’est pas plus sûr que n’importe quel autre système de substitution.

Les faiblesses de la méthode de substitution mono-alphabétique

Pour toutes les méthodes de cryptographie par substitution mono-alphabétique que nous avons vues, les clés possibles sont au nombre de 26! soit un peu plus de 4×1026, ce qui en soi est assez énorme. Pas de souci donc, les méchants ne trouveront jamais la clé… Eh bien, en fait, il y a un très gros bémol : ce nombre de clés ne tient pas compte de la faiblesse structurelle de la cryptographie par substitution. En effet, dans les différentes langues, les lettres n’apparaissent pas toutes à la même fréquence. Dans le cas de la langue française, il y a presque toujours beaucoup plus de E que de Y dans un texte, enfin presque… dans le cas de la Disparition de Georges Pérec, où la lettre E a totalement disparu, ce postulat n’est plus vrai. Mais sinon, comme le E est toujours remplacé par la même lettre et le Y aussi on peut en déduire que la lettre qui apparait le plus dans un texte français correspond sûrement à un E crypté. Et inversement, s’il n’y a presque aucun F par exemple, il s’agit sûrement d’un Y crypté.

Histogramme illustrant l’analyse de fréquence d’apparition des lettres dans l’acte 1 du Malade Imaginaire de Molière (soit 13334 caractères utiles après conversion des caractères accentués en leurs équivalents sans accent et en supprimant les autres caractères (espaces, ponctuations, etc.).

Grâce à cet histogramme, on note l’apparition de groupes de lettres avec des fréquences assez similaires :

  • le E est de loin le plus fréquent
  • Puis, on trouve les S et U
  • Ensuite, les A,I,N,O,T
  • Et on continue…

En plus des fréquences d’apparition, on peut également utiliser la position des lettres dans le texte pour en identifier d’autres. On trouve par exemple les S en fin de mots quand ils sont au pluriel. Le A est, quant à lui, fait souvent parti des lettres qui apparaissent isolées. Puis on continue avec la fréquence d’apparition des groupes de 2 lettres voire de 3.

Cette démarche comporte tout de même quelques failles. Tout d’abord, le texte doit être relativement long pour réaliser des statistiques correctes et fiables et il vaut mieux qu’il soit écrit en français standard pas comme la Disparition de Georges Pérec.

Le chiffre de Vigenère

Malgré quelques faiblesses, aucune amélioration n’est survenue entre César et le XVIème siècle en matière de procédé cryptographique, à la fois sûr et facile à utiliser ! C’est alors que naquit en 1523 Blaise de Vigenère qui allait devenir l’inventeur d’une « nouvelle » façon de crypter les messages, une méthode mettant en scène une substitution polyalphabétique. Et cette méthode va dominer 3 siècles durant. Elle est expliquée dans son Traicté des chiffres ou Secrètes manières d’écrire publié en 1586.

Son idée, que l’on peut qualifier de révolutionnaire pour l’époque, à propos de cette nouvelle substitution consistait à utiliser un chiffre de César différent pour chaque lettre. On modifie donc le décalage pour chaque lettre. Pour ce faire, on utilise la table suivante :

La méthodologie pour coder un message est la suivante : on commence par choisir une clé, i.e. un mot de longueur arbitraire. On reproduit ensuite ce mot sous la totalité du texte à coder autant que nécessaire de façon à ce que toutes les lettres du texte soit associée à une lettre de la clé. Enfin, on regarde dans le tableau la lettre qui se trouve à l’intersection de la lettre du texte et de celle de la clé.

Un petit exemple pour rendre tout ça plus compréhensible. On va coder le texte « Vous aurez une surprise lors du prochain cours de SRETI » avec la clé « SRETI ». On commence donc par écrire la clé sous le texte à coder :

V

O

U

S

A

U

R

E

Z

U

N

E

S

U

R

P

R

I

S

E

S

R

E

T

I

S

R

E

T

I

S

R

E

T

I

S

R

E

T

I

Pour coder la lettre V, on regarde l’intersection de la colonne issue de V avec la ligne issue de S et l’intersection donne la lettre N. Puis on continue et on obtient au final : NFYL IMIIS CFV WNZHIMLM DFVL LM GVHKZRMG KGLVL LW JVXBA.

Par rapport à tous les algorithmes précédents, celui-là possède nettement plus de points forts. Le cryptage et le décryptage en connaissant la clé sont tous deux faciles d’utilisation.

Ce code n’est certes pas infaillible mais résout l’un des problèmes qui se posait précédemment. Le E a été codé en E, R, I et X. Ainsi, une analyse statistique simple ne peut pas permettre de découvrir où se trouvent les E. Par ailleurs, on peut produire une infinité de clés qui peuvent être des mots voire des phrases. Pour toutes ces raisons, cette méthode s’est imposée durant plus de 3 siècles.

C’est donc sur cette dernière méthode que l’on va refermer le bref historique sur les méthodes de cryptographie du passé. Nous espérons que cette lecture vous aura plu et nous espérons que vous serez également là pour notre prochaine publication.

Panorama des algorithmes de cryptage de l’information

   La cryptologie est une science mathématique qui peut se décomposer en deux branches : la cryptographie et la cryptanalyse. Durant notre étude nous allons exclusivement nous concentrer sur la cryptographie.

Qu’est ce que la cryptographie ?

La cryptographie consiste en l’étude des techniques permettant de transmettre des données de façon confidentielle, afin de protéger une information, qui serait envoyée entre deux entités, dans le cas où celle-ci serait interceptée par une personne mal intentionnée.

Le cadenas informatique

Comme ça marche ?

Une brève explication de la cryptographie pourra se résumer comme ceci : lorsque l’on souhaite protéger un message, on va lui appliquer une transformation mathématique qui va le rendre illisible, cette transformation s’appelle le chiffrement.
Enfin, si on souhaite lire le message après réception et en général, c’est le cas : on va effectuer un déchiffrement, i.e. l’action inverse.

Le plan

Durant cette étude, nous commencerons par étudier et effectuer un historique des méthodes de cryptographie, un historique assez riche puisque les premières découvertes de cryptographie remontent à MXOHV FHVDU (la personne qui a inventé le code César… je vous laisse deviner).

Ensuite nous présenterons les méthodes de cryptographie modernes :
- Cryptographie symétrique
- Cryptographie asymétrique
- Cryptographie hybride

Ces méthodes pourront être illustrées par des exemples de systèmes connus.

Puis, afin de finir l’étude, nous effectuerons des recherches concernant l’évolution de ces méthodes ainsi que des recherches sur de futures méthodes.

Et pour commencer à vous mettre dans le bain, voici un petit lien intéressant au cas où vous auriez du mal à dormir le soir :
http://www.bibmath.net/crypto/index.php3

Licence Creative Commons

Licence Creative Commons
Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution – Partage dans les Mêmes Conditions 3.0 non transposé.