Confirmé de mon côté : mon implémentation du pseudo-code dynamique de la V10 déchiffre l'intégralité des 5385 bits du cryptogramme sans accroc, jusqu'au mot manquant annoncé par l'énoncé. :-)

Il n'y a plus besoin de mode "devinette" en aval du bit 96 qui me bloquait, comme visiblement Jericho aussi, contrairement à mvc ;-)

Merci d'avoir assumé et documenté que c'est une variante personnelle (une sorte de FGK à priorité Vitter : échanges simples à la FGK, critère de choix branche/feuille de Vitter, le départage à poids égal restant ta convention propre) plutôt qu'un Vitter canonique.

Les suivants ne devraient pas avoir d'indigestion ! ;-)

Bravo jaudi !

Un test rapide ce matin de cette V10, déchiffre désormais le crypto correctement en suivant scrupuleusement le pseudo-code donné. Dommage que celui-ci ne soit pas donné sous forme de texte dans le pdf.

Allez, je retourne sur mon transat pour finir ma grille de mots-croisés en espérant ne pas y trouver de "Huffman" ni de "Vitter" ;-))

Bonsoir à tous,
L'énoncé de cette énigme a été changé car je n'étais pas tout à fait satisfait avec l'ancienne version.

Après quelques heures de recherche sur le système, je me suis rendu compte que j'avais fait une variante très peu intuitive pour le codage Vitter, à savoir que je mettais à jour les poids statiquement en ne changeant pas les poids des noeuds même lorsque leurs enfants changeaient. Ce problème de "priorité en cache non actualisée" a causé la sortie de route au bit 96 pour ceux qui réalisaient une mise à jour dynamique qui est bien plus logique pour rester dans la veine du chiffrement Huffman-Vitter.

J'ai donc corrigé ce bug en mettant à présent une mise à jour dynamique pour les poids, et j'ai complété le cours avec un nouvel exemple, des explications détaillées et même un pseudo-code pour illustrer toutes les subtilités de cette variante personnelle du codage Huffman, utilisant la méthode d'échange du FGK mais avec les idées de Vitter pour élargir l'arbre au lieu de l'allonger !

J'espère que cette nouvelle version vous conviendra mieux et sera un bon remède aux indigestions dues à une exposition trop prolongée en forêt huffmanienne (hâte d'avoir le retour des cadors du site à ce sujet s'il vous plaît) ! Bonne semaine ! ;-)

Désolé pour l’ajout : plus précisément, je voulais dire que même s’il y avait maintenant un oracle de chiffrement sur cette énigme, l’indigestion chronique est désormais bien installée !

Elle avait commencé ailleurs, avec le premier défi Huffman et son implémentation dCode.fr… mais heureusement, celle-là était finalement bien guérie. ;-)

Disons que cette épreuve a quelque peu provoqué une rechute. ;-)

Bonjour mvc, et bravo pour le décodage intégral ! \(^_^)/

En fait, ton retour illustre assez bien mon propos : si tu as dû faire de nombreux allers-retours avec l’IA pour "adapter" ton code, c’est bien que les règles ne semblaient pas complètement explicitées dans le cours.

Du coup, pour la science :-) : pourrais-tu nous partager la portion de code de ton IA qui permet de départager deux nœuds de même poids ? Ou, encore mieux, la partager avec jaudi pour qu’elle puisse éventuellement servir à compléter le cours ?

C’est justement l’un des points qui me semble manquer dans le cours, et c’est précisément là que mes scripts divergent et cassent au 96ᵉ bit. Je serais super curieux de voir comment toi et ton IA avez tranché ça !

Parce que même avec un oracle de chiffrement sur cette épreuve, je pense que j’aurais fini par jeter l’éponge : ça fait une semaine que je m’interdisais de passer en mode devinette sur la réponse… et j’ai fini par craquer. ;-)

Merci @Cogite pour ce retour détaillé, et désolé si la documentation n'était pas suffisamment claire !
Comme tu l'as justement remarqué, il s'agit d'une variante personnelle de l'algorithme Vitter, comme détaillé dans mon cours. Elle correspond au principe de l'algorithme FGK (avec des échanges de branches), dans lequel on a intégré les améliorations de l'algorithme Vitter (pour élargir l'arbre au lieu de l'allonger).
Je vais essayer de modifier le cours (et éventuellement l'énoncé) dans les jours qui suivent pour rendre plus clair le chiffrement de cette énigme, car @Jericho m'a également signalé que son programme décryptait bien l'exemple mais bloquait à complètement décrypter le cryptogramme, mais pourtant je n'ai pas réussi à comprendre de manière claire d'où venait la différence de convention entre nos deux scripts.
Encore désolé si la documentation fournie ne permette pas d'être certain de la pertinence de son script Python !

suite... a partir de l'exemple du cours. En fait j'ai fait le programme a partir de ce que j'ai compris de Vitter et je l'ai adapté pour que l'exemple marche. Pour être clair c'est l'IA qui fait mes programmes, mais je lui explique comment corriger -- et dans ce cas précis il y a eu vraiment beaucoup d'aller et retour

Bonjour,

Je ne comprends pas, mon programme ne s'arrête pas au bit 96 et il décode le message en entier et pourtant je l'ai mis au point a parir de l'exemple

Maintenant que l'énigme est pliée, je tiens à poser ici mon REX.

L'idée de départ était vraiment séduisante, mais je ne vais pas cacher une frustration certaine et un vrai mécontentement quant à la réalisation globale du défi.

Pour le dire sans détour : "J'SUIS PAS CONTENT !", comme dirait un certain vidéaste.

1. "Vitter", vraiment ? Ou une variante maison dont on aurait égaré la notice ?

L'énoncé nous présente ça comme du Vitter. Or l'algorithme de Vitter décrit dans la littérature repose sur une propriété fondamentale non négociable : la propriété de fratrie.

A tout instant, on doit pouvoir ranger les nœuds par poids croissant, chacun avant son parent. C'est la colonne vertébrale de l'algorithme.

Or ici, elle semble casser. Et pas besoin d'aller loin pour le voir : l'exemple du cours lui-même produit, au bout de quelques lettres, des configurations où un nœud léger est mieux placé qu'un nœud plus lourd. Un Vitter conforme rééquilibrerait, celui-ci hausse les épaules et continue.

Le souci, c'est que le cryptanalyste consciencieux, lui, code du vrai Vitter. Celui des livres. Et il obtient un flux qui ne colle pas au cryptogramme. On se retrouve donc avec un petit problème de contrat : l'énoncé annonce Vitter, mais la mécanique qu'il faut réellement retrouver est une variante maison dont les règles ne sont pas données. Et là, forcément, le cryptanalyste se met à chercher la notice qui manque. ;-)

2. L'exemple valide gentiment des implémentations qui vont échouer

Le jeu d'essai, c'est l'encodage de ABBCDBAAAA en 50 bits. Dix caractères, quatre lettres distinctes. C'est mignon, mais c'est beaucoup trop maigre pour trancher les cas qui comptent : le départage entre nœuds de même profondeur, le classement exact entre branche et feuille à poids égal (bref, tout ce qui se joue quand deux nœuds se disputent la même place), et surtout le comportement une fois que l'arbre a grossi.

Je pèse mes mots, parce que j'ai vérifié ce point précis, et il est, sauf erreur de ma part, assez révélateur : on peut écrire une implémentation qui reproduit l'exemple décrit dans le cours, et qui déraille quand même sur le cryptogramme, très exactement au bit 96. C'est-à-dire très tôt dans le décodage, sur une mise à jour de l'arbre. Autrement dit : l'exemple vous tape sur l'épaule en disant "c'est bon, ton code est juste", puis votre code s'écroule au premier virage.

Pour donner une idée du gouffre : j'ai passé au crible plus de 16 000 variantes de règle déterministe, tous les ordres de qualité, tous les comparateurs de poids, saut contre glissement, départ de la remontée à la feuille ou au parent. Aucune ne franchit ce point de rupture.

J'en tire une conclusion prudente mais nette : la règle réellement employée ne semble pas déductible des seuls éléments fournis. Et c'est précisément là que le petit exemple est trompeur : il est tout à fait possible de reproduire parfaitement les dix caractères du cours (mvc, Jericho et moi y sommes parvenus). Le problème est que cette validation s'arrête exactement là où commence le véritable test. Le programme passe donc brillamment son examen... mais uniquement sur le sujet d'entraînement. ;-)

J'aurais donc tendance à supposer que la règle recherchée correspond à une subtilité particulière de l'implémentation de l'auteur. ;-) Mais je garde volontairement une réserve : peut-être que l'algorithme est parfaitement cohérent et que je passe simplement à côté d'une subtilité. Sans jeu de données plus conséquent, cela reste pour moi une hypothèse, pas une certitude.

3. Et donc, la cryptanalyse vous dépose devant la porte... et vous laisse deviner

C'est la suite logique. Puisque la mécanique exacte devient incertaine très tôt dans le décodage, il ne semble plus possible, avec les seules règles explicitées dans le cours, de poursuivre proprement le décodage sans commencer par reconstituer la règle manquante.

C'est probablement faisable, mais au prix d'un travail de rétro-ingénierie assez conséquent que je n'ai franchement pas envie de refaire après ma presque indigestion de Huffman ailleurs. ;-)

Le solveur se retrouve donc, au choix, à :
1. passer encore beaucoup de temps à reconstruire la mécanique exacte
2. ou identifier le texte source à partir des rares mots décodables, puis retrouver le texte complet et tirer au jugé lequel de ses mots s'est fait la malle.

Pour une énigme cryptographique, ça pique un peu : la partie code ne livre pas la réponse, elle vous amène poliment jusqu'au seuil et vous glisse "à toi de jouer", mode devinette, sur un mot à faible entropie.

J'ai fini par trouver, mais par intuition "méta" sur le thème du texte, pas par cryptanalyse. Et, en ce qui me concerne, c'était même du méta-méta-égarement. ;-) Un pari heureux, aussi satisfaisant soit-il sur le moment, ce n'est pas tout à fait ce que je venais chercher.

Le vrai sujet : difficulté maligne, ou difficulté par sous-spécification ?

Qu'on soit bien d'accord : une énigme crypto a le droit d'être dure. C'est même tout l'intérêt. Mais la difficulté devrait être analytique : plus je comprends, plus j'avance, et le raisonnement seul finit par livrer la solution complète. Ici, une bonne part de la difficulté est informationnelle (il manque une pièce du puzzle) : la règle de rééquilibrage exacte, qu'aucune dose de réflexion raisonnable ne semble permettre de reconstituer directement à partir des éléments fournis. Ce n'est pas mon analyse qui est éprouvée, c'est l'écart entre ce qui est écrit et le code resté dans le tiroir de l'auteur. Nuance, mais nuance qui fait toute la différence entre "redoutable" et "injuste".

Comment rendre cette énigme imprenable sur la forme (parce que l'idée mérite une v2)

Trois retouches, et elle devient irréprochable :

- Dire ce qu'on fait. Si la variante ne respecte pas la propriété de fratrie, l'assumer et la décrire : ordre de qualité des positions, condition d'échange branche/feuille et feuille/feuille, saut ou glissement, point de départ de la remontée. Dix lignes de pseudo-code et l'ambiguïté disparaît.

- Donner un exemple qui tranche vraiment. Une trace d'au moins 25 caractères sur un alphabet plus fourni (une dizaine de symboles), ou, le rêve du solveur, l'état complet de l'arbre à un point pivot : les codes de chaque symbole après, disons, une vingtaine de caractères. C'est le seul filet qui permette de valider son implémentation avant de la lâcher sur le cryptogramme.

- S'assurer que le chiffre rend la réponse. Mécanisme bien spécifié = message entièrement décodable = mot égaré lu par comparaison directe, sans deviner. C'est le test qualité le plus simple qui soit : la solution doit tomber du décodage, pas surgir d'une intuition heureuse.

Voilà. Merci quand même pour la conception et pour le choix du texte.

Et si jamais j'ai mal lu quelque part et qu'il existait un chemin propre, je serai le premier ravi qu'on me montre la notice. Il m'arrive de me tromper, hein, mais pas trop souvent. ;-)

Bon alors celle-là je ne l'ai pas tout à fait méritée...

Je fais court :
- j'ai un script qui fonctionne pour l'exemple du cours
- il plante sur le crypto en me sortant un message illisible sauf... les deux premiers mots.
- je trouve le texte de référence et je teste des mots du clair qui pourraient convenir comme réponse attendue en mode "guessing"
- Bingo ! après quelques essais et quelques "IP Banned"

Pour l'instant je n'ai plus le courage ni l'envie de chercher le bug dans mon/ton algo.
Bon c'est fini maintenant Huffman hein !?

Merci pour ce retour détaillé qui me conforte dans ma vérification de cette nouvelle version. En effet, je n'ai pas utilisé tous les caractères ASCII, notamment pour ne pas avoir un arbre trop complexe à construire car je trouvais que le système était déjà assez complexe comme cela avec des variations multiples de l'arbre qui, à mon sens, méritent bien le niveau "expert" (même si initialement je pensais la mettre en "difficile", le fait qu'un raté de changement de codage désynchronise tout m'a fait changer le niveau de difficulté ;-) ! )

en fait je me suis trompé : pour les 4 a finaux ils se codent de manières différentes tous les 4 :
A : 000
A : 01
A : 00
A : 1

Bonjour,
L'énigme ne comporte pas d'erreurs, mais c'est dommage de pas utiliser les majuscules/minuscules, les accents et la ponctuation car on travaille en ASCII.
En ce qui concerne le cours, je n'ai travaillé que sur l'exemple donné et maintenant il est juste. J'ai mis environ quatre heures pour mettre au point le programme (encoder cette petite séquence de 10 lettres). C'est assez difficile : dans l'exemple pour les 4 A finaux : les deux premiers se codent d'un manière, puis le troisième d'une seconde manière et enfin le dernier d'une troisième manière.

@mvc Maintenant que tu l'as validée, peux-tu me confirmer que l'énigme ne comporte pas d'erreurs (que ce soit le cryptogramme lui-même ou la partie du cours correspondante) s'il te plaît (afin d'avoir une vérification extérieure sur ce système complexe où la moindre erreur peut tout désynchroniser) ?

Bravo @mvc pour le décryptage et la médaille !

L'indigestion est confirmée ! :-/