Discussion :

[Bill Fassinou]

Un programmeur belge résout le casse-tête cryptographique du MIT vieux de 20 ans
émis par un professeur de l’université en 1999

Le laboratoire d’informatique et d’intelligence artificielle du MIT (CSAIL) a annoncé cette semaine qu’un programmeur belge a résolu un puzzle cryptographique émis par un professeur de l’université en 1999 lors du 35e anniversaire du laboratoire du MIT. Selon les chercheurs du MIT, au départ, il n’avait pas été prévu que l’énigme soit résolue avant 35 ans, mais il faut dire que les ordinateurs et les semi-conducteurs ont évolué très rapidement, ce qui a permis au Belge Bernard Fabrot de parvenir à proposer une solution pour le puzzle 15 années plus tôt.

L’énigme a été proposée en avril 1999 par des professeurs de l’université du MIT. Les estimations faites par les scientifiques à l’époque ne prévoyaient pas une solution pour le puzzle, du moins pas avant 2034 et il faudra passer des étapes successives pour atteindre cette solution. Cependant, Bernard Fabrot a pu s’en sortir cette année après avoir passé trois mois et demi à calculer la solution. Selon les explications des chercheurs du MIT, l’énigme consistait essentiellement à effectuer environ 80 000 milliards de squarings successifs d’un numéro de départ. Elle a été spécialement conçue pour déjouer quiconque tente de le résoudre plus rapidement en utilisant le calcul parallèle.

« Le puzzle est conçu pour déjouer les tentatives du solveur d’exploiter une technique informatique parallèle ou distribuée pour accélérer le calcul. Le calcul nécessaire pour résoudre le puzzle est “intrinsèquement séquentiel”. Le problème est de calculer 2^(2^t) (mod n) pour les valeurs spécifiées de t et n. Ici, n est le produit de deux grands nombres premiers et t est choisi pour définir le niveau de difficulté souhaité du puzzle. Nous estimons qu’il faudra 35 ans de calcul continu pour résoudre le casse-tête, l’ordinateur étant remplacé chaque année par le prochain modèle le plus rapide disponible. La plupart des travaux seront toutefois effectués au cours des dernières années », peut-on lire dans la note de description du cryptopuzzle LCS35 annoncé par le professeur Ronald L. Rivest le 4 avril de l’année 1999.

Le casse-tête est un exemple de « fonction de retard vérifiable » (VDF), ce qui signifie que sa réponse ne peut être résolue qu’après un certain nombre d’étapes. Étant donné que les VDF peuvent également être utilisés pour créer un caractère aléatoire non biaisé, ils ont été proposés comme approches potentielles pour améliorer la sécurité et l'évolutivité de systèmes blockchain tels que Ethereum et Filecoin, ont expliqué les chercheurs du LCS (laboratory of computer science). Ainsi, pour parvenir à son résultat, Fabrot a utilisé un simple ordinateur personnel avec un processeur Intel Core i7-6700 et a calculé la solution à l'aide de la bibliothèque arithmétique de précision multiple GNU (GMP).

La bibliothèque arithmétique de précision multiple GNU (GMP) du projet GNU est une bibliothèque libre pour l’arithmétique de précision arbitraire fonctionnant sur des entiers signés, des nombres rationnels et des nombres à virgule flottante. Il n'y a pas de limite pratique à la précision, à l'exception de celles impliquées par la mémoire disponible dans la machine sur laquelle GMP s'exécute (la taille de l'opérande est limitée à 232-1 bits sur les machines 32 bits et à 237 bits sur les machines 64 bits). GMP dispose d’un riche ensemble de fonctions, dont l’interface est régulière. L'interface de base est pour C, mais les wrappers existent pour d'autres langages notamment Ada, C++, C #, Julia, .NET, OCaml, Perl , PHP, Python, R, Ruby et le langage Wolfram.

En parallèle à cette annonce, le MIT a également annoncé qu’une autre équipe dirigée par Simon Peffers de Supranational, une société technologique spécialisée dans l'optimisation algorithmique, le développement de logiciels, la conception de semi-conducteurs et le développement de systèmes, appliquant une approche différente de celle de Fabrot, est sur le point de finaliser elle aussi le traitement d’une solution. L’équipe de Peffers a utilisé un nouvel algorithme de quadrature (conçu par Erdinç Öztürk de l'Université Sabanci) pour s'exécuter sur un accélérateur matériel programmable appelé FPGA. L'équipe, qui travaille dans le cadre d'une collaboration appelée Cryptophage, est en passe de terminer le puzzle le 11 mai, après seulement deux mois de calculs.

La résolution du puzzle donnera lieu très prochainement à l’ouverture d’une capsule temporelle conçue par l'architecte Frank Gehry et contenant des artefacts historiques de l'inventeur du Web, Tim Berners-Lee, le co-inventeur d'Ethernet, Bob Metcalfe et le fondateur de Microsoft, Bill Gates (Gates a fait don de l’Altair BASIC d’origine qui représentait le tout premier produit de Microsoft , développé par MITS en 1975). Selon les explications données par les chercheurs du MIT, la cérémonie devrait avoir lieu le mercredi 15 mai.

Source : CSAIL

Et vous ?

Qu'en pensez-vous ?

Voir aussi

Google vient de battre le record du monde pour le calcul des chiffres de Pi qui sont désormais de 31,4 milliards de chiffres et célèbre le Pi Day

Le MIT coupe les liens avec les entreprises technologiques chinoises Huawei et ZTE à cause des poursuites engagées contre elles par les USA

Des puces mémoire à très basse consommation d'énergie électrique pourraient être bientôt fabriquées grâce à une étude des chercheurs du MIT

[JeanMorlet]

Argh ! C'est quoi le fameux message caché ? Va-t'il falloir se taper le calcul ou ils vont le dévoiler maintenant qu'il a été découvert ?

[Invité]

Il ne faisait donc pas qu'écrire des livres pour Marabout (excellent soit dit en passant).

Bravo Bernard Fabrot !

C'est fou, parce qu'il a l'air drôlement jeune, alors que j'ai appris Unix grâce à lui il y a plus de 25 ans. Encore un enfant HP !

[Thorna]

Selon les explications des chercheurs du MIT, l’énigme consistait essentiellement à effectuer environ 80 000 milliards de squarings successifs d’un numéro de départ.

Aaahhh, le squaring, cette fameuse opération mathématique si mystérieuse qu'elle n'a même pas de nom en français ! Pas étonnant qu'il ait fallu si longtemps pour résoudre ce puzzle, quand on sait combien il est dangereux de se promener seul dans un square le soir après le nuit tombée...

[jean12]

C'est, comme l'a dit Neil Armstrong, un petit pas pour l'homme un grand bond pour l'humanité. Les réalisations qui vont en découler sont encore impensables ...

[Christian_B]

le squaring, cette fameuse opération mathématique si mystérieuse qu'elle n'a même pas de nom en français ! [...] on sait combien il est dangereux de se promener seul dans un square le soir après le nuit tombée...

En principe, squaring signifie quadrature (transformation en carré), ce qui il est vrai ne nous avance guère, faute d'autres précisions. Par ailleurs il n'est pas indiqué si la cérémonie (un tantinet publicitaire) aura lieu dans un square.
.

un petit pas pour l'homme un grand bond pour l'humanité. Les réalisations qui vont en découler sont encore impensables ...

Je suppose qu'il ne faut pas prendre cette proposition enthousiaste au 1er degré. Des défis mathématiques impliquant l'utilisation les ordinateurs il y en a eu bien d'autres. Et il ne s'agit pas ici d'un progrès fondamental en mathématiques (imprévisible par nature) mais d'un problème d'optimisation et de puissance de calcul, visiblement très cadré puisqu'une estimation approximative des moyens à mettre en œuvre était possible dès le départ.
.

C'est quoi le fameux message caché ?

A mon avis le message (pas très bien caché) est "Achetez Microsoft, Bill Gates est sympa, il fait cadeau d'un logiciel" (qui ne sert plus à rien depuis longtemps).