4 avril 2013

10 messages - Retourner à 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
  • Algo minimal d’échange de clé

    le 24 mai à 09:50, par Yann Coudert

    Bonjour,

    Il existe à ce jour une méthode beaucoup plus simple et moins coûteuse que Diffie-Hellman pour échanger une clé entre A et B. Ne vous basez pas sur mon dernier envoi (bidon). C’était pour vous montrer le look de la méthode. Je ne peux évidemment pas publier le bon algo sans avoir de garantie. Si cela vous intéresse, dites-le moi, sinon on restera avec l’ancienne méthode (c’est très bien aussi mais plus lourd).

    Cordialement,

    Yann Coudert

    PS : non je ne suis pas mégalo (si vous pensez cela).

    Répondre à ce message
Pour participer à la discussion merci de vous identifier : Si vous n'avez pas d'identifiant, vous pouvez vous inscrire.