Le monde est mathématique

Codage et cryptographie

4 avril 2013  - Ecrit par  Joan Gómez Voir les commentaires (9)

Cet article a été écrit en partenariat avec L’Institut Henri Poincaré

Cet article a été écrit en partenariat avec RBA

L’Institut Henri Poincaré et Images des Mathématiques ont uni leurs efforts pour superviser la réédition de la collection Le monde est mathématique,
publiée par RBA en partenariat avec Le Monde. En 40 ouvrages, cette collection de qualité, issue
d’un projet collectif de mathématiciens espagnols, vise à présenter,
à travers une grande variété de points de vue, de multiples facettes
des sciences mathématiques, sous un aspect historique, humain, social,
technique, culturel ...

Reprise et améliorée au niveau de la forme, cette nouvelle édition a été
entièrement lue et corrigée par l’équipe d’Images des Mathématiques ;
des préfaces et listes bibliographiques ont été ajoutées. Le Monde consacre un cahier spécial au lancement de cette collection présentée par Cédric Villani, qui en a écrit la préface générale.

Chaque semaine, à l’occasion de la sortie d’un nouveau numéro de la série, un extrait sélectionné sera présenté sur Images des Mathématiques. Il sera également accompagné d’une invitation à prolonger votre lecture.

Extrait du Chapitre 5. Un secret de polichinelle : la cryptographie à clé publique

La cryptographie n’a pas échappé à l’irruption du traitement informatique et à son développement postérieur. Employer un ordinateur pour le chiffrement d’un message est une opération en grande partie identique au chiffrement sans lui, à trois différences près... La première, c’est qu’un ordinateur peut être programmé pour simuler le travail d’une machine conventionnelle de chiffrement de, par exemple, mille rotors, sans avoir besoin de la fabriquer physiquement. Deuxièmement, un ordinateur ne travaille qu’avec des chiffres binaires, et, par conséquent, tout chiffrement se fait à ce niveau (même si par la suite les informations numériques sont de nouveau décodées en informations textuelles). Enfin, les ordinateurs se caractérisent par une vitesse de calcul et de traitement extraordinaire.
Dans les années 1970, les premiers chiffrements ont été conçus pour tirer parti du potentiel des ordinateurs, comme Lucifer, un chiffrement qui divisait le texte en blocs de 64 bits et en cryptait une partie par un remplacement complexe, avant de les réunir dans un nouveau bloc chiffré de bits et de répéter l’opération. Le système exigeait un ordinateur équipé d’un programme de cryptage ainsi qu’une clé numérique à la fois pour l’émetteur et le récepteur. Une version de 56 bits de Lucifer, dénommée DES, fut lancée en 1976 aux États-Unis et constituait toujours, en 2009, l’un des standards de chiffrement dans ce pays.
Le chiffrement a indubitablement tiré parti de la capacité de traitement des ordinateurs, mais, tout comme leurs prédécesseurs millénaires, ceux-ci continuaient d’être exposés au risque qu’un récepteur indésirable parvienne à obtenir les clés et, connaissant l’algorithme de chiffrement, à déchiffrer le message. Cette faiblesse élémentaire de tout système « classique » de cryptographie est connue comme le problème de la distribution de clé.

Le problème de la distribution de clé

Depuis que la communauté cryptographique s’est mise d’accord sur le fait que la protection des clés, davantage que celle de l’algorithme, était l’élément fondamental qu’il fallait garantir pour assurer la sécurité des cryptosystèmes, leur implantation a dû
s’attaquer au problème de la distribution des clés en toute sécurité. Dans le meilleur des cas, cela occasionnait de véritables problèmes logistiques : par exemple, au moment de distribuer les milliers de livres de clés générés par une armée importante ou de le faire à des centres de communication mobiles opérant dans des circonstances extrêmes, comme l’équipage des sous-marins ou les unités sur le front de bataille. La sophistication d’un système de cryptage « classique » n’a pas d’importance : ils sont tous vulnérables à l’interception de leurs clés respectives.

L’algorithme de Diffie-Hellman

La notion d’« échange sûr de clés » peut sembler une contradiction : la transmission même de la clé est en soi un message, si bien qu’elle doit aussi être cryptée et avec une clé qui a préalablement dû être échangée. Cependant, si l’échange est envisagé comme un processus de communication en plusieurs phases, il est possible d’imaginer une solution au problème, du moins en théorie.
Supposons qu’un émetteur quelconque dénommé Alice crypte un message avec une clé propre et l’envoie à un récepteur, Bob. Ce dernier crypte de nouveau le message chiffré avec une autre clé propre et le renvoie à l’émetteur. Alice déchiffre le message avec sa clé et envoie ce nouveau message, qui n’est alors plus chiffré qu’avec la clé de Bob, lequel commence à le déchiffrer. Le problème millénaire d’échange sûr de clés vient d’être résolu. Mais cela se passe-t-il vraiment comme cela ? La réponse est non. D’ailleurs, dans tout algorithme de chiffrement complexe, l’ordre d’application de la clé est fondamental, et nous avons vu dans notre exemple théorique que Alice doit déchiffrer un message déjà chiffré avec une autre clé. L’inversion de l’ordre des chiffrements aboutirait à un galimatias. La théorie ne sert à rien dans ce cas, mais elle a tracé la voie à suivre.

LES HOMMES À L’ORIGINE DE L’ALGORITHME

Bailey Whitfield Diffie (ci-dessous) est né en 1944 aux Etats-Unis. Mathématicien formé au Massachusetts institute of technology (MIT), il est depuis 2002 le directeur de la sécurité et vice-président de Sun Microsystems, dont le siège est en Californie.

JPEG - 20.7 ko

Quant à Monte Hellman, ingénieur, il est né en 1945 et a effectué sa carrière professionnelle chez IBM et au MIT, où il fit la connaissance de Diffie.

En 1976, deux jeunes scientifiques américains, Whitfield Diffie et Monte Hellman, ont trouvé un moyen pour que deux personnes échangent des messages chiffrés sans avoir pour cela à échanger de clé. Cette méthode repose sur l’arithmétique modulaire, ainsi que sur les propriétés des nombres premiers des opérations où ils interviennent.

L’idée est la suivante :

1) Alice choisit un nombre quelconque, qu’il maintient secret. Nous appellerons ce nombre $N_{j1}$.

2) Bob choisit un autre nombre quelconque, qu’il maintient aussi secret. Nous appellerons ce nombre $N_{p1}$.

3) Ensuite, Alice et Bob appliquent tous deux sur leur nombre respectif une fonction du type $f(x) = a^x$ mod $p$, où $p$ est un nombre premier connu.

  • Alice obtient comme résultat un nouveau nombre, $N_{j2}$, qu’il envoie cette fois à Bob.
  • Bob obtient comme résultat un nouveau nombre, $N_{P2}$, qu’il envoie à Alice.

4) Alice résout une équation du type $N_{P2}^{N_{j1}}$(mod $p$) et obtient comme résultat un nouveau nombre : $C_J$.

5) Bob résout une équation du type $N_{J2}^{N_{P1}}$ (mod $p$) et obtient comme résultat un nouveau nombre : $C_P$.

Bien que cela semble étonnant, $C_J$ et $C_P$ seront égaux. Et voici donc la clé. Notez que le seul moment où Alice et Bob ont échangé des informations, c’est lorsqu’ils
ont convenu de la fonction $ f(x) = a^x$ mod $p$ et qu’ils se sont envoyé $N{_J2}$ et $N_{P2}$ , qui ne constituent pas la clé et dont l’éventuelle interception, par conséquent, ne compromet pas la sécurité du cryptosystème. La clé de ce système aura la forme générale
\[ a^{N_{J1}⋅N_{P1}} \text{(mod} \, p).\]

Par ailleurs, il est important de tenir compte du fait que la fonction originale a la particularité de ne pas être réversible. Autrement dit, si l’on connaît la fonction ainsi que le résultat de son application à une variable $x$, il est impossible (ou du moins très difficile) d’obtenir la variable $x$ originale.



Pour que tout soit bien clair, répétons l’opération avec des fonctions et des chiffres concrets. La fonction choisie est, par exemple,
\[f(x) = 7^x \text{(mod} \,11)\]

1) Alice choisit un nombre $N_{j1}$ , par exemple 3, et calcule $f(x) = 7^x $(mod 11)

  • ce qui donne $f(3) = 7^3 ≡ 2$ (mod 11).

2) Bob choisit un nombre $N_{P1}$ , par exemple 6, et calcule $f(x) = 7^x$ (mod 11)

  • ce qui donne $f(6) = 7^6 ≡ 4$ (mod11).

3) Alice envoie à Bob son résultat, 2, et Bob fait de même avec le sien, 4.

4) Alice calcule $4^3 ≡ 9$ (mod 11).

5) Bob calcule $2^6 ≡ 9$ (mod 11).

Cette valeur, 9, sera la clé du système.

Alice et Bob ont échangé la fonction $f(x)$ ainsi que les chiffres 2 et 4. Quelles informations apportent réellement ces deux données à un éventuel espion ? Supposons que notre récepteur inattendu connaisse la fonction ainsi que les chiffres. Il est maintenant confronté au problème de la résolution de  $7^{N_{J1}} ≡ 2$ (mod 11) et $ 7^{N_{P1}} ≡ 4$ (mod 11) modulo 11, où $N_{J1}$ et $N_{P1}$ sont les nombres que Alice et Bob maintiennent secrets. S’il arrive à les obtenir, il lui suffira pour obtenir la clé de résoudre $a^{N_{J1}⋅N_{P1}}$ modulo $p$. La solution à ce problème, au fait, s’appelle en mathématiques un logarithme discret.

Par exemple, dans le cas de

\[f(x) = 3^x \text{(mod 17)},\]

on observe que $3^x ≡ 15$ (mod 17), et, en essayant avec différentes valeurs de $x$, on obtient que, si $x = 6$, la relation $3^x ≡15$ (mod 17) est vérifiée.
Les algorithmes de ce type et le problème du logarithme discret n’ont reçu aucune attention particulière avant le début des années 1990, et ce n’est que ces dernières années qu’ils ont été réellement développés. Dans cet exemple, on dit que 6 est le logarithme discret de 15 en base 3 modulo 17.
La particularité des équations de ce type, comme mentionné ci-dessus, c’est qu’elles sont difficilement réversibles (elles sont dites asymétriques). Pour des valeurs de $p$ de plus de 300 chiffres et de $a$ de plus de 100, la solution, et donc la rupture de la clé, devient extrêmement difficile.




VIRUS ET « PORTES DÉROBÉES »

Même le plus sûr des chiffrements à clé publique dépend du fait que la clé privée soit maintenue secrète. En conséquence, un virus qui s’installerait dans le système d’un émetteur, localiserait et transmettrait cette clé privée ferait tomber à l’eau tout le cryptosystème.
En 1998 s’est fait jour l’histoire d’une entreprise suisse leader en matière d’élaboration et de vente de produits cryptographiques, qui avait inclus dans ces produits des « portes dérobées » qui détectaient les clés privées des utilisateurs et les renvoyaient à l’entreprise. Une partie de ces informations fut remise au gouvernement américain, qui pouvait de cette façon, à tous les effets, surveiller les communications entre les ordinateurs infectés.

Cet algorithme est l’un des piliers de la cryptographie moderne. Diffie et Hellman ont exposé leur idée lors d’un Congrès national de l’informatique, à l’occasion d’un séminaire qu’il convient de qualifier d’historique. Ce travail peut être consulté dans sa totalité à l’adresse www.cs.berkeley.edu/ christos/classics/diffiehellman.pdf, sous le titre New Directions in Cryptography (« Nouvelles directions en cryptographie »).
L’algorithme de Diffie-Hellman a démontré, en théorie, la possibilité de créer une méthode cryptographique qui n’aurait besoin d’aucun échange de clés, mais, paradoxalement, qui reposerait sur la communication publique d’une partie du processus (les deux nombres initiaux qui servent à déterminer la clé).
Autrement dit, cet algorithme a démontré la viabilité d’un cryptosystème dont les émetteurs et les récepteurs n’ont pas besoin de se retrouver pour établir les clés. Mais il reste toutefois certains inconvénients : si Alice souhaite envoyer un message à Bob alors que celui-ci dort, par exemple, elle devra attendre qu’il se réveille pour pouvoir générer la clé.
Dans la quête de découvrir de nouveaux algorithmes plus efficaces, Diffie a théorisé sur un cryptosystème dont la clé de chiffrement serait distincte de celle de déchiffrement, aucune des deux ne pouvant évidemment être obtenue à partir de l’autre. Dans ce cryptosystème théorique, l’émetteur disposerait de deux clés : celle de cryptage et celle de décryptage. Des deux, seule la première serait rendue publique, pour que quiconque souhaitant envoyer un message puisse le crypter. Une fois le message reçu, l’émetteur procéderait à son déchiffrement à l’aide de la clé de décryptage, qui serait évidemment restée secrète. Cela dit, comment réussir à mettre en œuvre ce système ?



Les nombres premiers au secours : l’algorithme RSA

En août 1977, Martin Gardner, divulgateur scientifique américain de renom, a publié dans sa colonne de récréations mathématiques de la revue Scientific American un article intitulé « Un nouveau type de chiffrement qui prendrait des millions d’années pour être déchiffré ». Après avoir expliqué en détail à ses lecteurs les fondements du système à clé publique, il fit observer le message chiffré ainsi que la clé publique N utilisée pour cela :
\[N=114.381.625.757.888.867.669.235.779.976.146.\]\[612.010.218.296.721.242.362.562.561.842.935.706.935.245.733.\]\[897.830.597.123.563.958.705.058.989.075.147.599.290.026.879.\]\[543.541.\]

Gardner mit ses lecteurs au défi de déchiffrer le message à partir des informations données, en précisant que la solution exigeait de factoriser $N$ en ses composants premiers $p$ et $q$. Pour finir, Gardner promit une récompense de 100 dollars (montant important à l’époque) à celle ou celui qui trouverait la bonne réponse en premier. Toute personne souhaitant davantage d’informations sur le chiffrement en question, précisa Gardner,devait envoyer une demande au Laboratoire d’informatique du MIT à l’attention de ses créateurs Ron Rivest, Adi Shamir et Len Adelman.
La bonne réponse ne fut reçue que 17 ans plus tard, et la collaboration de plus de 600 personnes fut nécessaire pour la trouver. Les clés étaient
\[p = 32.769.132.993.266.709 .549.961.988.190.834.461.413.177.642.967.992.942.539. 798.288.533\]
et
\[q = 3.490.529.510.847.650.949.147.849.619.903.898.133.417.764. 638.493.387.843.990.820.577,\]
et le message chiffré : « The magic words are squeamish ossifrage » (« Les mots magiques sont délicats et cruels »).

L’algorithme présenté par Gardner est connu sous la dénomination RSA, sigle des noms de famille Rivest, Shamir et Adelman. Il s’agit de la première mise en œuvre pratique du modèle à clé publique imaginé par Diffie, et il est aujourd’hui assidûment employé. Il offre une sécurité extrême, car le processus de déchiffrement est incroyablement laborieux bien que, comme nous le verrons plus tard, pas impossible. Nous présentons ci-après les fondements du système de manière élémentaire, sans trop entrer dans la technique.




L’algorithme RSA en détail

L’algorithme RSA repose sur certaines propriétés des nombres premiers, que vous pourrez consulter dans les annexes du présent volume si vous souhaitez plus d’informations. Nous nous limiterons ici à exposer les règles de base qui en sont à l’origine.

  • L’ensemble des nombres inférieurs à $n$ et premiers avec n est dénommé fonction d’Euler et est exprimé sous la forme  $\varphi(n)$.
  • Si $n = pq$, $p$ et $q$ étant deux nombres premiers, alors  $\varphi(n) = (p – 1)(q – 1).$
  • D’après le petit théorème de Fermat, on sait que si $p$ est un nombre premier entier positif et $a$ un entier premier avec $p$ (ce qui signifie pgcd $(a, p) = 1$), l’équation $a^{p−1} ≡1$(mod p) doit être
    vérifiée.
  • D’après le théorème d’Euler, si pgcd$(n,a) = 1$, alors $a^{\varphi(n)} ≡ 1$ (mod 1).

Comme nous l’avons mentionné précédemment, le système est dit à « clé publique » car la clé de cryptage est portée à la connaissance des émetteurs qui souhaitent envoyer des messages. Chaque récepteur possède une clé publique propre. On part du principe que les messages seront transmis convertis en nombres, à l’aide d’un code ASCII ou de tout autre moyen souhaité.
En premier lieu, Alice génère une valeur $n$ qui est le produit de deux nombres premiers $p$ et $q$ $(n = p·q)$, puis choisit une valeur $e$ de telle sorte que le pgcd$(\varphi (n), e) = 1$. Rappelons que $\varphi(n) = (p – 1)(q – 1)$. Les valeurs rendues publiques sont $n$ et $e$ (en aucun cas les valeurs $p$ et $q$ ne sont fournies). Le couple $(n,e)$ est la clé publique du système, et les valeurs $p$ et $q$ sont dénommées nombres RSA. Parallèlement, Alice calcule la valeur unique $d$ modulo $\varphi (n)$ qui vérifie $d·e = 1$, à savoir l’inverse de $e$ modulo $\varphi (n)$. On sait que cet inverse existe parce que pgcd $(\varphi(n),e)=1$. Cette valeur $d$ est la clé privée du système. Pour sa part, Bob emploie la clé publique $(n,e)$ pour crypter le message $m$ à l’aide de la fonction $M ≡m^e$ (mod $n$). À la réception du message chiffré, Alice réalise l’opération $M^d ≡{ (m^e)}^d$ (mod $n$), équivalent à $M^d ≡ (m^e)^d ≡ m$ (mod $n$), ce qui démontre que le message peut être déchiffré.

Nous allons maintenant appliquer le procédé exposé avec des valeurs numériques concrètes.

  • Soit $p=3$ et $q=11$, d’où $ n=33. \varphi(33)=(3–1)·(11–1)=20$. Alice choisit $e$ de manière à n’avoir aucun diviseur commun avec $20$, par exemple, $e = 7$. La clé publique de Alice est $(33,7)$.



  • Entretemps, Alice a calculé une clé privée $d$ qui sera l’inverse de 7 modulo 20, à savoir $7·3 ≡ 1$ (mod.20), d’où $d = 3$.
  • Bob obtient la clé publique et souhaite envoyer le message « 9 » ou bien, $m=9$. Pour le chiffrer, il utilise la clé publique de Alice et résout l’équation suivante :
    \[9^7 = 4.782.969 ≡ 15 \text{(mod 33)}.\]

Le message chiffré est « 15 ». Bob envoie le message.
Alice reçoit le message « M = 15 » et le déchiffre comme suit :

\[15^3=3.375 ≡ 9 \text {(mod 33)}. \]

Le message a bien été déchiffré.

Au fur et à mesure que sont choisis des nombres premiers $p$ et $q$ plus élevés, la difficulté de mise en œuvre de l’algorithme RSA augmente, au point que l’emploi de l’ordinateur devient nécessaire pour le calcul des congruences. Par exemple, soit $p = 23$ et $q = 17$, d’où $n = 391$. La clé publique qui en résulte pour $e = 3$ est (391,3). En conséquence, $d = 235$. Pour un message simple comme « 34 », l’opération de déchiffrement est la suivante :
\[204^{235} = 34 \text{(mod 391)}.\]

Observez le degré de la puissance et pensez à la gigantesque capacité de calcul nécessaire pour trouver la congruence.

[...]

PDF - 2.1 Mo
Sommaire du livre

Pour aller plus loin

Post-scriptum :

L’extrait proposé est choisi par le préfacier du livre : Vincent Beffara. Celui-ci répondra aux commentaires éventuels.

Partager cet article

Pour citer cet article :

Joan Gómez — «Codage et cryptographie» — Images des Mathématiques, CNRS, 2013

Crédits image :

Image à la une - Manon Bucciarelli
img_9751 - Archives RBA

Commentaire sur l'article

  • Codage et cryptographie

    le 5 avril 2013 à 23:13, par Christophe Boilley

    Je suis intrigué par la dernière phrase.

    204235 = 34 (mod 391).

    Observez le degré de la puissance et pensez à la gigantesque capacité de calcul nécessaire pour trouver la congruence.

    L’algorithme d’exponentiation rapide et l’utilisation des congruences permettent de calculer ce résultat avec 12 multiplications à trois chiffres et autant de divisions euclidiennes. À la main, c’est donc probablement faisable en une demi-heure environ. J’ai peine à croire que l’auteur d’un article sur la cryptographie puisse penser sincèrement que ce calcul donné en exemple nécessite des capacités gigantesques.

    Bien sûr que la cryptographie telle qu’elle est utilisée aujourd’hui est gourmande en ressources. Mais les ordres de grandeurs ne sont pas du tout les mêmes que dans cet exemple.

    Répondre à ce message
    • Codage et cryptographie

      le 18 avril 2013 à 15:44, par Vincent Beffara

      Merci pour votre message,

      Bien sûr que ce calcul est faisable à la main si on sait s’y prendre, écrire 235 en base 2 etc. Je pense que ce que voulait l’auteur c’est de faire sentir ce qui se passe dans l’algorithme en prenant des nombres traitables à la main, pas forcément de donner une idée des capacités de calcul des processeurs actuels. Après tout, avec des modulos de cette taille, une recherche en « force brute » se fait en un temps dérisoire même sans raccourci de calcul ...

      Répondre à ce message
      • Codage et cryptographie

        le 18 avril 2013 à 19:02, par Christophe Boilley

        Mais qu’on me détrompe si « ce qui se passe dans l’algorithme » n’est pas précisément ce que j’indique (et qui n’implique pas de savoir décomposer 235 en base 2, même si c’est bien une interprétation mathématique de ce qui se passe).

        Pour le lecteur curieux de passage, on construit une suite d’exposants décroissante de 235 à 1 en divisant par 2 les exposants pairs et en retirant 1 aux exposants impairs : 235, 234, 117, 116, 58, 29, 28, 14, 7, 6, 3, 2, 1. Puis on calcule successivement les résidus des puissances correspondantes en commençant par la fin : 235, 2352, 2353 = 235×2352, 2356 = (2353)2… À chaque étape, on calcule donc un produit ou un carré, suivi d’une division euclidienne.
        (Dans le cas présent, c’est encore plus rapide parce qu’on se rend compte que 20429 est congru à 2047, mais je suppose qu’on ne peut compter sur ce genre de collision en général).

        Mais on ne peut faire croire aux lecteurs qu’en cryptographie, on calcule complètement la puissance avant de passer aux congruences : la plupart du temps, les puissances en jeu ont tellement de chiffres qu’il n’est pas matériellement possible de les représenter avec toutes les particules de l’univers.

        Répondre à ce message
  • Codage et cryptographie

    le 6 avril 2013 à 01:08, par Cronos

    Page 96. Le tableau de vérification du code de contrôle d’un code barre EAN-13 comporte une erreur. À la ligne « somme des chiffres de rang pair » il faut lire « somme des chiffres de rang impair »

    Répondre à ce message
  • Codage et cryptographie

    le 9 avril 2013 à 02:00, par Cronos

    Page 135, pour la fonction indicatrice d’Euler, un « - » a été remplacé par un « + ».

    Répondre à ce message
  • Codage et cryptographie

    le 13 avril 2013 à 11:04, par Jacques Jousset

    Je viens de découvrir la collection ’’Le monde est mathématique’’, j’ai lu avec beaucoup d’intérêt les deux premiers numéros.

    J’aimerais toutefois vous faire part d’une remarque personnelle.
    Elle concerne le chapitre le Chapitre 6 du numéro ’’Codage et cryptographie’’.
    Il me semble que l’explication avancée p.115 concernant la superposition d’état quantiques ne soit pas la plus satisfaisante, et laisse planer un léger air de mystère sur le comportement quantique.
    Le comportement quantique est seulement (si j’ose dire) contre-intuitif, il n’est pas mystérieux, simplement il ne s’accorde pas avec notre représentation du monde macroscopique.

    A votre avis ne vaudrait-il pas mieux souligner que le principe de superposition des états est un des principes fondamentaux de la mécanique quantique.
    Si cette superposition d’états ne se retrouve pas dans monde macroscopique l’explication la plus satisfaisante actuellement est la décohérence :
    Un système quantique ne doit pas être considéré comme isolé mais en interaction avec un environnement macroscopique possédant un grand nombre de degré de liberté.
    Ce sont ces interactions qui provoquent la disparition rapide des états superposés.

    Avancer cette explication, qui tant à s’imposer de plus en plus, grâce, en particulier, aux travaux expérimentaux d’Alain Aspect et de Serge Haroche, permettrait également de souligner qu’une des principales difficultés dans la réalisation des qbit est justement d’obtenir des temps de décohérence suffisamment élevés pour que ceux-ci soit utilisables.
    Qu’en pensez-vous ?

    Quand au chat de Schrödinger….
    Si, comme il est supposé, le chat est vivant au début de l’expérience il interagit avec un nombre énorme de molécules de son environnement (air qu’il respire, chaleur sous forme de rayonnement thermique, processus biologiques divers…). Cette interaction avec l’environnement efface le comportement quantique du système chat+atome qui se comporte alors de façon classique et se trouve dans un état et un seul (vivant ou mort) bien avant qu’on ouvre la boîte. (Notes prises à partir d’un exposé de Serge Haroche).
    Donc rien de mystérieux !
    Cordialement

    Jacques Jousset

    Répondre à ce message
  • Codage et cryptographie

    le 18 avril 2013 à 16:00, par Vincent Beffara

    Merci pour votre commentaire !

    Je ne suis pas du tout spécialiste de mécanique quantique, et l’auteur du volume non plus je pense ... Même si le comportement de systèmes microscopiques est bien compris, le passage à l’échelle « classique » reste lui malgré tout mystérieux (ce que vous soulignez vous-même - la décohérence est une explication satisfaisante mais je ne sais pas à quelle point elle fait l’unanimité). Au point que des chercheurs reconnus comme Shallit (le ’S’ de RSA) doutent de la possibilité même théorique de réaliser des ordinateurs quantiques vraiment utilisables alors que d’autres considèrent les obstacles comme purement pratiques. Tout sera tranché par l’expérience ...

    Quant au chat de Schrödinger, dans mon idée il s’agit d’une expérience de pensée, qui sert à mettre le doigt sur le comportement contre-intuitifs des systèmes quantiques en les décrivant de manière absurde avec des mots de tout les jours, et non d’une description d’une expérience réelle. Un vrai chat aura bien sûr un comportement classique, mais cela n’empêche pas l’image du chat en superposition dans deux états d’être pertinente !

    Répondre à ce message
  • Truffé d’erreurs

    le 10 juin 2013 à 12:05, par Jérôme ^

    Bonjour,

    je suis mathématicien dans un laboratoire de cryptographie. Cet opuscule a fait le tour du laboratoire il y a quelques semaines, d’abord en nous amusant par la taille du bêtisier, puis en nous consternant par les ravages produits en termes de vulgarisation.

    Pour bien situer le contexte, il s’agit d’une traduction récente d’un ouvrage espagnol d’une trentaine d’années, « remis à jour » récemment. Ladite remise à jour n’a consisté qu’à ajouter « En 2009, » au début de
    quelques phrases, sans en changer le contenu, qui est largement obsolète.

    À côté de ces problèmes d’obsolescence se manifestent également de vraies et profondes erreurs mathématiques, dont le gag sur l’exponentiation rapide cité ci-dessus par Christophe Boilley. Les preuves n’ont apparemment pas été relues par un mathématicien : elles ont pour résultat de perdre le lecteur néophyte plus que de le convaincre.

    Le plus grave est tout de même que ce livre n’a été ni écrit, ni relu, par un cryptographe compétent. Le tableau qu’il dresse de la cryptographie est complètement partiel et bancal, et pas d’une façon qui s’expliquerait par son contexte mathématique plus qu’informatique. Parmi les absences remarquables :

     - le masque jetable est un concept absolument central et très simple, qui est à peine évoqué ici, et pas au bon endroit ;

     - le successeur de DES, AES, n’est même pas cité : même s’il est moins mathématique que les algorithmes symétriques, il permet toutefois de parler de permutations ou d’algèbre linéaire modulo 2 ;

     - courbes elliptiques ? ;

     - il existe d’autres familles asymétriques particulièrement faciles à vulgariser, comme les algorithmes basés sur les réseaux de ℝⁿ.

    Enfin, le chapitre sur la cryptographie quantique est peut-être le pire de tous. Il présente le sujet comme la seule branche vraiment active de la cryptographie, ce qui est absolument faux (c’est une branche assez mineure en volume), et reprend le mantra connu (et archi-faux) « ce que la cryptographie quantique prend, la cryptographie quantique le rend ».

    J’ajoute que j’ai également eu l’occasion de feuilleter le premier opus de la série (le nombre d’or) et que je ne l’ai pas trouvé plus satisfaisant (même si le style des erreurs est différent). Je n’achèterai ni ne recommanderai aucun de ces ouvrages, au contraire.

    Ci-dessous, des extraits du bêtisier. (Ce ne sont que des extraits...)

    I. Contenu obsolète depuis 30 ans :


    p. 99 : « [DES] constituait toujours, en 2009, l’un des standards de chiffrement ». DES est considéré cryptanalysé depuis 1997 (cf. infra). Certaines variantes (triple-DES) existent encore dans la nature mais sont déconseillées pour les nouveaux produits de sécurité. Ce paragraphe a visiblement été écrit avant l’apparition de nouveaux algorithmes tels qu’AES (standard depuis 2001), puis révisé en 2009 par un deuxième auteur qui en ignore tout.

    p. 106–107 : « si n est suffisamment grand (de l’ordre de plus de 100 chiffres), il n’existe aucun moyen connu de trouver p et q en un temps raisonnable. Actuellement, les nombres premiers employés pour le chiffrement des messages les plus confidentiels dépassent 200 chiffres ».
    Cette phrase aurait besoin d’une mise à jour... le dernier record en date est RSA-768, soit 232 chiffres décimaux. Le standard le plus fort actuellement utilisé (2013) pour le chiffrement RSA est de 4096 bits, soit environ 1200 chiffres décimaux.

    p. 113 : « comme nous l’avons déjà mentionné [!], essayer de casser par la force brute les algorithmes de cryptage tels que le RSA ou le DES [...] dépasse la capacité de traitement du plus rapide des ordinateurs actuels. » En fait, la cryptanalyse brutale de DES a été effectuée dès 1997 (par calcul distribué sur Internet) et 1998 (sur une seule machine).

    II - Erreurs mathématiques :


    p. 12, encadré : le codage binaire BCD (binary-coded decimal) existe mais est d’usage très restreint (essentiellement des implémentations très anciennes dans le domaine de la comptabilité) et n’est absolument jamais employé en cryptographie (il y a de bonnes raisons à cela, qui viennent de la théorie de l’information). Dans un ouvrage de vulgarisation, donner une construction erronée du code binaire est un peu dommage ; d’autant que les codes binaires sont fournis pour les chiffres décimaux sans aucune explication. Par ailleurs, le texte et le tableau se contredisent : le chiffre 4 est codé par 100 dans le tableau et par 0100 dans le texte (la différence est significative si on code la chaîne 44 : 100100 ou 01000100 ?).

    p. 101 : « 4) Alice résout une équation du type » Elle ne résout pas d’équation, elle calcule une puissance, ce qui est beaucoup plus facile (= faisable en pratique).

    p. 105 : la « preuve » de RSA est étrange. Elle cite le petit théorème de Fermat (qui n’est pas utilisé dans la preuve) et le théorème d’Euler (qui est utilisé, mais la preuve cache bien son utilisation).

    p. 135 : le premier paragraphe est extrêmement confus et les notations sont un peu mélangées. L’entier b est en fait égal à n.

    p. 137 : la preuve de correction de RSA est très étrange. Il est question d’un premier et d’un deuxième cas, qui ne désignent pas des alternatives, mais des étapes qui s’enchaînent. Par ailleurs, quitte à utiliser le petit théorème de Fermat pour prouver RSA, il est possible de produire une preuve nettement plus claire (c’est ce que font R., S. et A. dans leur article).

    Plus généralement dans l’annexe : le traducteur commençait à fatiguer et les tournures bizarres (hispanismes ?) abondent :

    - « le dit petit théorème de Fermat », « la dite identité de Bezout » (134),

    - « le nombre de nombres [...] premiers de n » (135),

    - « une correspondance numérique m d’un message » (136),

    - « le pgcd(a,n) = 1 » (135),

    - « des expressions (1) et (2) on peut affirmer que » (137)
    (noter d’ailleurs qu’il manque l’argument p, q premiers entre eux).

    III - Méconnaissance complète de la cryptographie :


    p. 16 : « aujourd’hui, les algorithmes de chiffrement utilisés, pour la plupart des communications, emploient au moins deux clés : une première privée [...] et une seconde publique ». En fait, la cryptographie symétrique est toujours vivante et se porte très bien ! Il est vrai que la cryptographie asymétrique joue un rôle essentiel dans les
    communications électroniques, mais le gros du volume est toujours chiffré symétriquement.

    p. 89, encadré : il est très étonnant de voir apparaître le chiffrement RC4 dans le chapitre sur la représentation de l’information, mais surtout : contrairement à ce qui est affirmé, RC4 n’est pas un algorithme à clé publique ! Il s’agit bien d’un type de chiffrement particulier (chiffrement par flot) mais qui est un algorithme symétrique tout ce qu’il y a de plus classique.

    p. 112 : « un espion ne devra pas pénétrer un, mais deux cryptosystèmes ». En fait, il suffit d’en pénétrer un des deux. (Le chiffrement asymétrique sert à chiffrer la clé symétrique. Pénétrer le premier donne la clé symétrique. Pénétrer le second donne directement le message).

    p. 118 : « ce qu’enlève la mécanique quantique, la mécanique quantique le donne ». C’est faux : elle casse une classe de problèmes asymétriques et fournit une famille de mécanismes symétriques, qui ne les remplace donc pas.

    p. 121 : il est enfin question du masque jetable (dans le chapitre sur la cryptographie quantique !), alors que c’est l’algorithme de chiffrement symétrique le plus basique qui soit.

    Répondre à ce message
  • Codage et cryptographie

    le 20 août 2013 à 12:29, par Audibert

    A propos du livre N°2 ,dans la présentation de Images des Math, le sommaire du livre N°2 , en pdf , a été oublié. G.A.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

L'auteur

Joan Gómez

Dossiers

Cet article fait partie du dossier «Le monde est mathématique» voir le dossier

Suivre IDM