Le blog-notes mathématique du coyote

Échanger des informations secrètes sur Internet ? C’est possible. Mais il y a toujours un risque qu’elle soient interceptées. C’est là que les mathématiques viennent à la rescousse. Et la méthode des « réseaux euclidiens » promet d’être encore plus efficace que les méthodes standard. De plus, il se trouve qu’on peut la comprendre en jouant à un jeu vidéo aux allures de Tetris, qui s’appelle « Cryptris ».

Lire les articles sur Images des Maths : partie 1, partie 2

Voir tous les épisodes sur Youtube

Dans une étude récente, des chercheurs du CNRS ont réussi à déjouer le logarithme discret, l’un des systèmes de protection les plus difficiles à résoudre. Ce travail permet d'ores et déjà de rejeter plusieurs applications cryptographiques et devrait avoir des répercussions importantes sur les systèmes de sécurité.

La cryptographie est une science qui s’attache à protéger la confidentialité de l'information en utilisant des problèmes mathématiques difficiles à résoudre, même pour les machines les plus puissantes. La sécurité d'une variante du logarithme discret, réputé très complexe, vient cependant d’être battue en brèche par des chercheurs du CNRS. Leurs résultats, publiés dans la collection Lecture Notes in Computer Science, ont été présentés lors de la conférence internationale Eurocrypt 2014 à Copenhague entre le 11 et le 15 mai.
L'algorithme conçu par ces scientifiques se démarque de ceux connus jusqu'alors pour ce problème. D'une part, il est significativement plus simple à expliquer et d'autre part, sa complexité est bien meilleure : ceci signifie qu'il est à même de résoudre des problèmes de logarithmes discrets de plus en plus grands, en voyant son temps de calcul croître beaucoup plus modérément. Le calcul de logarithmes discrets associé aux problèmes voulus difficiles pour les applications cryptographiques s'en trouve donc grandement facilité.
Résoudre cette variante du logarithme discret étant désormais à la portée des calculateurs actuels, il devient inenvisageable de reposer sur sa difficulté dans les applications cryptographiques. Ces travaux sont encore à un stade théorique et l'algorithme doit encore être affiné avant de pouvoir fournir une démonstration pratique de la faiblesse de cette variante du logarithme discret. Néanmoins, ces résultats ouvrent une faille dans la sécurité cryptographique et la voie à d'autres recherches. Il pourrait par exemple être utilisé afin de tester la solidité d'autres solutions cryptographiques.

Source : Futura-Sciences

Vous pensiez que le code de lancement de l’arsenal nucléaire américain était incassable ? Que c’était le secret le mieux gardé de la planète ? Vous allez être déçus. Pendant près de 20 ans, le fameux « nuke code » (code nucléaire) à huit chiffres qui permet de libérer le feu de l’apocalypse se composait ainsi : 00000000.
Dans le bunker qui accueillait les silos « Minuteman » et leurs 50 missiles, huit zéros suffisaient donc à lancer les engins. Un ancien membre de l’équipe de tir raconte : « Notre manuel de lancement nous apprenait en fait, l’équipe de tir, à vérifier deux fois le panneau de déverrouillage dans notre bunker souterrain pour s’assurer qu’aucun autre chiffre que le zéro n’avait été appuyé. »
Ce qui revenait, en somme, à révéler le code à tout le personnel militaire du site. Les généraux étaient manifestement obsédés par l’idée que la réponse à une attaque soviétique ne soit pas suffisamment rapide ou que les instructions du Président ne leur parviennent pas.

Source : rue89.com

Le prix Gödel, qui récompense chaque année des travaux remarquables en informatique théorique, a été décerné le 3 juin 2013 à Dan Boneh, Matt Franklin et Antoine Joux pour leurs travaux en cryptologie, reposant sur l’utilisation d’un outil mathématique appelé couplage. Parallèlement, deux équipes de chercheurs se font la course depuis quelques mois et battent record sur record d’un problème difficile, le calcul de logarithmes discrets dans des corps finis, et ces résultats semblent justement menacer l’utilisation des couplages. Ces récents événements sont l’occasion de parler un peu de cryptologie sur Images des Mathématiques.

Le message codé d'un pigeon voyageur vieux de 70 ans a été retrouvé dans une cheminée en Angleterre lors d'un banal ramonage. Les employés ont découvert le squelette et un petit étui rouge. Ce dernier renferme un secret datant de la Seconde Guerre mondiale.

Le message codé cache peut-être des informations très intéressantes concernant la Seconde Guerre mondiale. Les spécialistes se sont donc empressés d'essayer les méthodes actuelles pour le déchiffrer. L'informatique n'a absolument rien donné, alors les historiens estiment qu'il y a deux possibilités. Soit, le code a été inscrit dans un livre mettant en avant une opération spécifique en 39-45, dans ce cas de figure, il sera impossible de trouver la clé puisque le précieux livre a dû être détruit. Deuxième solution, il existe un code qu'il faut trouver. Dans tous les cas cette cheminée de la maison de Surrey en Angleterre a mobilisé tous les spécialistes du GCHQ, ils essayent de découvrir à quoi correspondent les blocs de lettres. Certains estiment que le message pourrait avoir un lien avec le Débarquement.

Le message sera-t-il déchiffré ?

Depuis quelques jours, les experts se multiplient et personne n'a encore réussi à le déchiffrer. Le code pourrait reposer sur le One Time Pad, cela mettrait un terme à la recherche, car il serait impossible à déchiffrer. Deux numéros d'identification sont également présents dans ce message, les experts tentent de trouver un lien. Cette découverte a mobilisé toute la toile puisque sur de nombreux forums de spécialistes de cryptographie tentent de trouver la clé, celle qui permettra au monde entier de connaître le fameux texte envoyé par le pigeon voyageur.
Il y a de grandes chances pour que le message reste à jamais codé et le secret est mort avec le pigeon et la personne qui est à l'origine du texte. Il faut savoir que cette méthode était largement utilisée pendant la Seconde Guerre mondiale, près de 250 000 pigeons ont transmis des messages.

Article original : Begeek.fr

State-of-the-art image scrambling algorithm uses a new type of matrix mathematics based on Sudoku puzzles.

Lire l'article en anglais sur technologyreview.com

Lire aussi l'article original sur arXiv.org : Sudoku Associated Two Dimensional Bijections for Image Scrambling

Le si réputé algorithme de génération de clés de chiffrement RSA ne laisse pas une part assez grande au hasard pour être totalement fiable. Des chercheurs viennent ainsi de démontrer qu’il offre au mieux une sécurité de 99,8 % et, au pire, une sécurité nulle.

L’algorithme utilisé pour générer des certificats X.509 ou encore des clés de chiffrement PHP n’est pas aussi sûr que l’on pouvait l’imaginer jusqu’ici. La découverte en a été faite par des chercheurs en cryptographie de l'EFFL et publiée dans un article Ron was wrong, Whit is right. Ceux-ci indiquent avoir procédé à une «vérification de l’état sanitaire de clés publiques trouvées sur Internet», avec pour objectif de «tester la validité de l’assertion selon laquelle un choix aléatoire différent est fait à chaque fois que des clés sont générées ». Une opération qui a échoué : «la vaste majorité des clés publiques fonctionne comme prévu» mais «deux modulos RSA pour mille n’offrent aucune sécurité ». Pourquoi ? Notamment parce qu’il y a des duplicatas, bien involontaires, certes, mais dont l’existence même pose problème.
Concrètement, les chercheurs aboutissent à la conclusion «qu’il y a plus de duplicatas» que ce que les études précédentes avaient pu laisser penser : «sur 6,4 millions de modulos RSA distincts, 71504 (1,1 %) apparaissent plus d’une fois, et même des milliers de fois pour certains.» Pire, ils assurent avoir trouvé 12934 modulos RSA n’offrant aucune sécurité : «les clés privées [correspondantes] sont accessibles à n’importe qui prendrait la peine de reproduire notre travail », assurent-ils. Et d’estimer ainsi que, au mieux, l’algorithme RSA 1024 bits offre une sécurité de 99,8 %. Pour ces chercheurs, le chiffrement basé sur un secret unique - et non pas sur un couple clé privé/clé publique - et sur l’algorithme Diffie-Hellman serait finalement plus sûr. Pour l’expert Bruce Schneier, c’est un «excellent travail» qu’on fait là les chercheurs. Mais pour lui, l’algorithme RSA ou le principe du chiffrement asymétrique ne sont pas remis en cause par cette étude : le problème vient «presque certainement du générateur de nombres aléatoires» utilisé pour la création de ces clés publiques. Et «cela ne devrait surprendre personne. L’un des points les plus difficiles de la cryptographie est la génération de nombres aléatoires ». Et d’ajouter que «la capacité à produire quelque chose d’aléatoire n’est pas une exigence fonctionnelle et à moins que vous ne la testiez spécifiquement - et que vous sachiez comment la tester - vous penserez probablement que votre système cryptographique fonctionne correctement ».
En fait, pour les chercheurs, c’est environ 0,003 % des clés RSA publiques qui est potentiellement vulnérable, « ce qui ne semble pas inacceptable ». Pour Bruce Schneier, il y a effectivement un risque mais il est difficile à quantifier. Et la nature aléatoire - encore - de la menace fait «qu’il est difficile de savoir comment monétiser» la faille. Ce qui tend à réduire la menace concrète. Toutefois, il s’interroge sur l’éventualité de générateurs de nombres aléatoires «volontairement affaiblis. Les suspects les plus évidents sont les services de renseignement nationaux comme la NSA. Je n’ai aucune preuve mais si je devais affaiblir des systèmes de chiffrement, je commencerais par les générateurs de nombres aléatoires.»

Source : lemagIT.fr

Le GCHQ (Government Communications Headquarters), le service de renseignements électronique du gouvernement britannique, publie un cryptogramme sur le site www.canyoucrackit.co.uk. Si vous le résolvez, vous pourrez être recruté par le GCHQ.

A lire l'article du Guardian GCHQ aims to recruit computer hackers with code-cracking website

Les œuvres de Platon sont analysées et débattues depuis plus de 2000 ans. Mais il s'avère que l’immense philosophe grec Platon pratiquait également la stéganographie (art de la dissimulation; faire passer inaperçu un message dans un autre message) : ses textes portent des messages que personne n'avait décelé jusqu'ici... Un universitaire britannique affirme en effet avoir découvert une série de messages secrets cachés dans certains des textes les plus influents de notre civilisation.
« J'ai montré rigoureusement que les livres contiennent des codes et des symboles et celui qui les décryptera sera en mesure de révéler la véritable philosophie de Platon », explique le Dr Jay Kennedy, professeur à l’Université de Manchester.
Ce code de Platon laisse penser que le philosophe avait prévu (anticipé, prophétisé ?) la révolution scientifique 2000 ans avant Isaac Newton : le livre de la nature est écrit en langage mathématique.

Une symbolique musicale

Dr Jay Kennedy a découvert un modèle intégré de symboles ainsi qu'une structure musicale. Ce code révèle la « philosophie cachée de Platon. Le résultat est stupéfiant. Imaginez que vous trouviez de nouveaux évangiles... écrits par Jésus-Christ lui-même ! »
Selon le professeur, le texte est rythmé par des multiples de 12, rythme qui correspond à une la gamme musicale grecque
Mathématique et musique sont ici étroitement liées , Platon les combinait pour truffer son texte de passages cryptés,que l'on se doit donc de débusquer, dans son œuvre. Certains passages sont marqués par des notes harmoniques, d'autres par des dissonantes. Les notes harmoniques sont à associer à l'amour ou au rire, les notes dissonantes à la guerre ou la mort. Ce code musical constituerait la clé de l'ensemble du système symbolique de Platon.
Si la structure musicale des symboles a été mise au jour, il reste toutefois à en découvrir le sens.
Alors que d'autres savants modernes avaient rejeté l’hypothèse d’une écriture codée, Kennedy semble avoir apporté la preuve du contraire, et explique: « Ceci est le début de quelque chose de grand. Il faudra une génération à travailler sur le décryptage complet et les implications de ce code ».
« Découvrir l'ordre scientifique de la nature nous rapproche de Dieu ». Platon
Si l’on réussit donc à « cracker » le code de Platon, nul doute que les schémas de pensées occidentaux (notamment ceux qui opposent science et religion) seront révolutionnés…

Sources : besoindesavoir.com, Université de Manchester

Le manuscrit dit de Copiale, entièrement crypté, vient d’être « cassé » par un logiciel utilisant des méthodes… de traduction. Verdict : ce long texte est une description de rites étranges organisés par une société secrète du XVIIIe siècle.

Baptisé Copiale (un de ses rares mots écrits en clair), ce livret de 105 pages retrouvé dans des archives de l’ex-Allemagne de l’Est défiait les spécialistes de la cryptographie. Il faut dire que l’on y trouve pêle-mêle des caractères latins, grecs et symboliques. On repère par exemple le signe désignant le sexe femelle ou celui qui, en mathématique, indique l’infini, ou encore des formes géométriques variées.
L’équipe réunie autour du « code Copiale » est composée de linguistes. Kevin Knight est Américain, Beáta Megyesi et Christiane Schaefer sont Suédois. Ils n’ont pas utilisé les armes de la cryptographie mais celles de la traduction. En somme, il s’agit de considérer un texte codé comme s’il était écrit dans une langue étrangère. L’idée n’est pas nouvelle et a été émise par Warren Weaver, un théoricien de la traduction, qui a proposé de rapprocher les méthodes de la cryptographie et de la traduction (on peut remarquer que Kevin Knight travaille à la SDL Weaver, née de la fusion de SDL et Language Weaver Inc.).

Cryptographie subtile

Les outils de l’équipe sont ceux de la traduction statistique. Alors que la méthode linguistique analyse la syntaxe des phrases, la traduction statistique puise dans des bases de données les plus vastes possibles pour dénicher des traductions déjà faites. Google s’est fait le champion de cette voie en utilisant sans limite le travail déjà réalisé par des traducteurs humains ou informatiques.
Pour l’appliquer au texte de Copiale, l’équipe a d’abord fait l’hypothèse que seuls les caractères latins avaient une signification. Devant l’échec, les linguistes ont postulé l’inverse, considérant qu’ils n’étaient là que pour embrouiller le problème (ces caractères sont des « nulles » dans le jargon de la cryptographie). Il a ensuite semblé que le code était « homophonique », c’est-à-dire qu’un caractère originel peut être codé par plusieurs signes, dont le nombre est proportionnel à la fréquence habituelle de ce caractère dans la langue originelle.
En considérant que le texte était en allemand et en comprenant que le signe « : » doublait la consonne précédente, les linguistes ont finalement abouti à un texte en clair. Sur son site Web, l’équipe donne toutes les indications et on y trouve également les versions en allemand et en anglais du code Copiale. On comprend que ce document décrit les étranges pratiques d’une secte secrète inconnue particulièrement intéressée par l’ophtalmologie. On y apprend dans le détail le déroulement de cérémonies d’intronisations de nouveaux membres.
Le décryptage de ce genre de textes est donc davantage qu’un jeu. Il apporte aussi du grain à moudre pour les historiens. Kevin Knight s’est attaqué cette année à un autre document, encore plus célèbre, le manuscrit de Voynich. Ce long texte écrit avec des caractères inconnus, qui daterait du XIVe siècle, défie à ce point les tentatives de décryptage que certains concluent à une supercherie. D’après Kevin Knight, c’est bien un texte réel mais son code résiste encore. Les méthodes de traduction statistiques en viendront-elles à bout ?

Source : Futura-Sciences

Le FBI demande la collaboration du public dans la résolution d'une énigme relative au meurtre de Ricky Mc Cormick âgé de 41 ans, commis en 1999. Deux courts messages retrouvés dans la poche de la victime de ce crime demeurent indéchiffrables puisque écrits dans un langage codé. S'étant d'abord référés à une équipe travaillant en analyse cryptographique ainsi qu'à l'Association américaine des cryptogrammes, cette agence fédérale des Etats-Unis constate qu'après l'écoulement de dix années, ce mystère n'a pu être résolu.
Selon la famille de la personne assassinée, cet homme rédigeait depuis l'enfance des textes sous forme codée mais personne ne connaît le sens de ces écrits. Les agents du FBI espèrent que quelqu'un quelque part pourra interpréter ces lignes ou que jaillira de cette recherche une idée novatrice. Ils tentent présentement de retracer des textes semblablement codés ou dont l'écriture se rapproche de celle du message diffusé en ligne afin d'établir des comparaisons ou des liens révélant la signification de cette série de lettres et de signes actuellement indéchiffrables.
Le FBI les a donc mis en ligne, expliquant: «Cette trentaine de lignes de matériau codé utilisent une variété exaspérante de lettres, nombres, tirets, et parenthèses. McCormick n'avait pas son bac, mais il pouvait lire, écrire, et on disait de lui qu'il était débrouillard. D'après des membres de sa famille, McCormick utilisait de telles notes encryptées depuis l'enfance, mais apparemment personne de sa famille ne sait comment déchiffrer les codes, et on ne sait pas si quiconque en dehors de McCormick pouvait traduire son langage secret.»
Toutes les techniques traditionnelles d'analyses cryptographiques ont échoué, et le chef du bureau concerné du FBI espère désormais que le grand public pourrait éclaircir le mystère McCormick, continue le communiqué de presse de l'agence. Les agents recherchent un autre exemple du système codé de McCormick, ou d'un code qui s'en approche, espérant pouvoir contextualiser les mots retrouvés, ou bien en tirer des comparaisons.

Sources : Sur-la-Toile, Yahoo Actualités, FBI

Nouvel exploit en matière de décryptage: une équipe internationale, basée notamment à l'EPFL, a réussi à extraire les nombres premiers d'un nombre totalisant 307 chiffres. Ce tour de force pourrait remettre en cause un standard de sécurité informatique.
Cette percée est l'oeuvre de trois institutions: l'Ecole polytechnique fédérale de Lausanne (EPFL), l'Université de Bonn et la compagnie japonaise NTT. Il aurait été impensable il y a encore quelques années et s'explique en partie par la montée en puissance des ordinateurs, relève lundi l'EPFL.
«C'est le plus grand nombre de cette forme que l'on factorise à ce jour», note le professeur de cryptologie Arjen Lenstra. Le nouveau nombre à 307 chiffres est tout prêt des 308 du fameux cryptage standard RSA de 1024 bits considéré comme sûr et couramment utilisé sur Internet pour naviguer en toute sécurité.
Plus la clé de cryptage est complexe, plus le nombre de bits est élevé, plus il est difficile de «casser» cette sécurité, explique Pascal Vermot, attaché de presse de l'EPFL. Factoriser signifie réduire le nombre dans les plus petits éléments possibles, soit en nombres premiers.
L'opération a nécessité onze mois de calculs. L'équipe internationale n'a pas voulu s'attaquer au standard 308 mais «montrer les limites actuelles de la cryptographie», selon Pascal Vermot. Le nouveau record à 307 chiffres, même s'il n'est pas un nombre RSA n'en représente pas moins un saut considérable.
Les nombres RSA se définissent par leur propriété quasi incassable: ils sont immenses et ne sont divisibles que par deux nombres premiers. Ces facteurs sont tellement difficiles à trouver que cela leur donne une vertu particulière pour de nombreuses applications de sécurité.
Malgré ces découvertes, le mode de cryptage à 1024 bits reste sûr pour l'instant, estime le professeur Arjen Lenstra. Le record de factorisation pour les nombres RSA, détenu par l'Université de Bonn, demeure à 200. Mais cela pourrait rapidement changer.

Source : 20 minutes

Exploit pour la factorisation de RSA-640, par Salvatore Tummarello, Futura-Sciences, le 06/12/2005

L'équipe allemande qui s'était déjà illustrée en mai dernier en "cassant" une clé de 200 chiffres a annoncé la factorisation de RSA-640. Pour cet exploit, l'équipe de la "Bundesamt für Sicherheit in der Informationstechnik" (BSI, agence fédérale pour la sécurité des techniques de l'information) se voit remettre un prix de 20 000$.

La sécurité du système de cryptage RSA repose en effet sur la lenteur des algorithmes de factorisation connus et les laboratoires RSA Security soumettent depuis 1977 une liste de grands nombres assortie de récompenses pour les premières équipes capable de les factoriser (i.e. retrouver les diviseurs).
Baptisés RSA suivi de leurs nombres de chiffres en écriture décimale ou binaire, les nombres proposés sont extrêmement difficile à casser et on estimait il y a 25 ans qu'il faudrait des millions d'année pour y parvenir... RSA-640 comprend 193 chiffres (décimaux) et n'a pourtant résisté que quatre mois et demi au crible mis en oeuvre par l'équipe allemande sur un réseau de 80 micro-processeurs Opteron cadencés à 2.2 GHz.
Les prochains défis? RSA-704 (212 chiffres) pour 30 000$ ... ou bien RSA-2048 (617 chiffres) pour 200 000$ !

La factorisation de RSA-640:

310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
=
1634733 6458092538 4844313388 3865090859 8417836700 3309231218 1110852389 3331001045 0815121211 8167511579
x
1900871 2816648221 1312685157 3935413975 4718967899 6851549366 6638539088 0271038021 0449895719 1261465571