Je n'y arrive pas (je m'en suis jamais servi) -- mais je veux juste envoyer un fichier

Bonsoir mvc, tu peux me joindre via le serveur Discord du Club Alkindi si tu le souhaites (pseudo jaudi) ! ;-)

Bonjour,

Je veux bien envoyer a jaudi le zip de mon programme et des données (il faut éviter qu'une erreur de copie se glisse quelque part) -- d'ailleurs cela serait bien quand il y a de grandes quantités de données d'avoir un fichier externe qui les contient-- Mais comment faire pour envoyer ce fichier

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 !

Oui, depuis la modification de Hme en avril, elle est à nouveau à jour ! J'ai juste mis ce message pour rassurer les cryptanalystes qui ont tenté de nombreuses réponses récemment. ;-)

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. ;-)