Malbolge

Malbolge
Date de première version	1998
Influencé par	Brainfuck Befunge
modifier

Malbolge est un langage de programmation dans le domaine public inventé par Ben Olmstead en 1998, nommé d'après le huitième cercle de l'Enfer dans la Divine Comédie de Dante, le Malebolge.

La particularité de Malbolge est qu'il a été conçu pour être le langage de programmation le plus difficile et le plus exotique possible. Toutefois, certaines des astuces utilisées pour rendre la compréhension difficile peuvent être simplifiées.

Programmer en Malbolge

Malbolge était si difficile à comprendre quand il est arrivé qu'il a fallu deux ans au premier programme Malbolge pour apparaître. Le programme lui-même n'a pas été écrit par un être humain : il a été généré par un algorithme de recherche par faisceaux conçu par Andrew Cooke et implémenté en Lisp.

Le 24 août 2000, Anthony Youhas annonça sur son blog qu'il a « battu Malbolge avec un bâton et maîtrisé ses secrets », fournissant des preuves sous forme de trois programmes Malbolge qui affichent diverses phrases. il ne révéla toutefois pas ses techniques.

Plus tard, Lou Scheffer posta une cryptanalyse de Malbolge et fournit un programme pour copier son entrée vers sa sortie.

Olmstead croyait Malbolge Turing-complet, sauf pour de la mémoire infinie. Une discussion a visé à déterminer si l'on pouvait implémenter des boucles en Malbolge ; il a fallu de nombreuses années avant de trouver un programme qui ne termine pas.

Le 17 août 2004, Tomasz Wegrzanowski écrivit un générateur de programmes Malbolge affichant diverses chaînes de caractères. D'après lui, l'astuce est d'oublier les sauts, de garder le registre D à des endroits bas de la mémoire, et d'effectuer aléatoirement des opérations NOP, ROT et Crazy jusqu'à ce que le registre A contienne ce dont on a besoin. Les programmes produits avec cette technique sont bien plus grands que ceux de Youhas.

Hello world en Malbolge

(=<`#9]~6ZY32Vx/4Rs+0No-&Jk)"Fh}|Bcy?`=*z]Kw%oG4UUS0/@-ejc(:'8dc

Programmes simples en Malbolge

Malbolge est un langage machine pour une machine virtuelle trinaire, l'interpréteur Malbolge. Pour vous aider à écrire des programmes Malbolge qui tournent correctement, le mode de fonctionnement de l'interpréteur standard est décrit plus bas.

Notes

• L'interpréteur standard et la spécification officielle ne correspondent pas parfaitement (ce qui n'est d'ailleurs pas une exception dans les implémentations des langages de programmation. Exemple : le compilateur PL/1 de Bull pour GCOS 7, qui n'était pas conforme à sa propre documentation, divers compilateurs Ada ou Cobol, qui sont pourtant des langages normalisés).
• C'est une explication simplifiée du code source de l'interpréteur : elle évite le chiffrement inutile et les étapes de soustraction et introduit un langage assembleur.

Registres

Malbolge possède trois registres, a, c, et d, qui sont comme des variables dans d'autres langages. Quand un programme démarre, la valeur de ces trois registres est zéro. c est spécial : c'est le compteur ordinal (i.e. il pointe sur l'instruction courante).

Notation des pointeurs

d signifie que la valeur de d est une adresse mémoire; [d] est la valeur stockée à cette adresse. [c] est similaire.

Mémoire

La machine virtuelle a 59049 (3^10) emplacements mémoire qui peuvent chacun contenir un nombre trinaire à dix chiffres. Chaque emplacement mémoire a une adresse de 0 à 59048 et peut contenir une valeur de 0 à 59048. Une valeur qui atteint 59049 est remplacée par 0.

Avant qu'un programme Malbolge commence, la première partie de la mémoire est remplie avec le programme. Tous les blancs dans le programme sont ignorés et, pour rendre la programmation plus difficile, tout le reste dans le programme doit commencer en tant qu'une des instructions suivantes.

Le reste de la mémoire est rempli en utilisant l'opération Crazy (voir plus bas) sur les deux adresses précédentes ([m] = crz [m - 2], [m - 1]). La mémoire remplie ainsi se répète toutes les douze adresses (les chiffres ternaires individuels se répètent toutes les trois ou quatre adresses, donc un groupe de chiffres trinaires est garanti de se répéter toutes les douze adresses).

Instructions

Malbolge possède huit instructions. Malbolge trouve quelle instruction exécuter en prenant la valeur à [c], en lui ajoutant la valeur de c et en gardant le reste de la division par 94 :

Instructions

Valeur de ([c] + c) % 94	Instruction représentée	Explication
4	jmp [d] + 1	La valeur à [d], plus un, est là où Malbolge va sauter et commencer à exécuter des instructions.
5	out a	Affiche la valeur de a, en tant que caractère ASCII, à l'écran.
23	in a	Entre un caractère, en tant que code ASCII, dans a. Les retours à la ligne sont le code 10. Une condition de fin de fichier est le code 59048.
39	rotr [d] mov a, [d]	Fait tourner la valeur à [d] d'un nombre trinaire (0002111112 devient 2000211111). Stocke le résultat à la fois dans [d] et dans a.
40	mov d, [d]	Copie la valeur à [d] dans d.
62	crz [d], a mov a, [d]	Effectue l'opération Crazy (voir plus bas) avec la valeur à [d] et la valeur de a. Stocke le résultat à la fois dans [d] et a.
68	nop	Ne fait rien.
81	end	Termine le programme.
Toute autre valeur fait comme 68: rien. Ces valeurs ne sont pas permises dans un programme pendant qu'il est chargé, mais sont permises plus tard.

Après l'exécution d'une instruction, celle-ci est chiffrée (voir plus bas) afin qu'elle ne fasse pas la même chose la prochaine fois, sauf si c'est un saut. Après un saut, Malbolge chiffre l'instruction précédant celle sur laquelle il a sauté. Enfin, les valeurs de c et d sont incrémentées de 1 et l'instruction suivante est exécutée.

L'opération Crazy

Pour chaque chiffre trinaire des deux entrées, utilisez la table suivante pour obtenir le résultat de l'opération Crazy. Par exemple, crz 0001112220, 0120120120 donne 1001022211.

opération Crazy

crz		Entrée 2
		0	1	2
Entrée 1	0	1	0	0
	1	1	0	2
	2	2	2	1

Chiffrement

Après qu'une instruction est exécutée, la valeur [c] (sans rien ajouter) se verra devenir [c] modulo 94. Puis, le résultat est chiffré avec l'une des deux méthodes équivalentes suivantes.

Méthode 1

Trouver le résultat ci-dessous. Stocker le code ASCII du caractère en dessous de la valeur de [c].

0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999
0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123
----------------------------------------------------------------------------------------------
9m<.TVac`uY*MK'X~xDl}REokN:#?G"i@5z]&gqtyfr$(we4{WP)H-Zn,[%\3dL+Q;>U!pJS72FhOA1CB6v^=I_0/8|jsb

Méthode 2

Trouver le résultat ci-dessous. Stocker la version chiffrée de [c].

Table de chiffrement

Résultat	Chiffré	Résultat	Chiffré	Résultat	Chiffré	Résultat	Chiffré	Résultat	Chiffré
0	57	19	108	38	113	57	91	76	79
1	109	20	125	39	116	58	37	77	65
2	60	21	82	40	121	59	92	78	49
3	46	22	69	41	102	60	51	79	67
4	84	23	111	42	114	61	100	80	66
5	86	24	107	43	36	62	76	81	54
6	97	25	78	44	40	63	43	82	118
7	99	26	58	45	119	64	81	83	94
8	96	27	35	46	101	65	59	84	61
9	117	28	63	47	52	66	62	85	73
10	89	29	71	48	123	67	85	86	95
11	42	30	34	49	87	68	33	87	48
12	77	31	105	50	80	69	112	88	47
13	75	32	64	51	41	70	74	89	56
14	39	33	53	52	72	71	83	90	124
15	88	34	122	53	45	72	55	91	106
16	126	35	93	54	90	73	50	92	115
17	120	36	38	55	110	74	70	93	98
18	68	37	103	56	44	75	104

Cycles dans le chiffrement

La cryptanalyse de Malbolge par Lou Scheffer mentionne six cycles différents dans le chiffrement. Ils sont listés ici :

• 33 ⇒ 53 ⇒ 45 ⇒ 119 ⇒ 78 ⇒ 49 ⇒ 87 ⇒ 48 ⇒ 123 ⇒ 71 ⇒ 83 ⇒ 94 ⇒ 57 ⇒ 91 ⇒ 106 ⇒ 77 ⇒ 65 ⇒ 59 ⇒ 92 ⇒ 115 ⇒ 82 ⇒ 118 ⇒ 107 ⇒ 75 ⇒ 104 ⇒ 89 ⇒ 56 ⇒ 44 ⇒ 40 ⇒ 121 ⇒ 35 ⇒ 93 ⇒ 98 ⇒ 84 ⇒ 61 ⇒ 100 ⇒ 97 ⇒ 46 ⇒ 101 ⇒ 99 ⇒ 86 ⇒ 95 ⇒ 109 ⇒ 88 ⇒ 47 ⇒ 52 ⇒ 72 ⇒ 55 ⇒ 110 ⇒ 126 ⇒ 64 ⇒ 81 ⇒ 54 ⇒ 90 ⇒ 124 ⇒ 34 ⇒ 122 ⇒ 63 ⇒ 43 ⇒ 36 ⇒ 38 ⇒ 113 ⇒ 108 ⇒ 39 ⇒ 116 ⇒ 69 ⇒ 112 ⇒ 68 ⇒ 33 ...
• 37 ⇒ 103 ⇒ 117 ⇒ 111 ⇒ 120 ⇒ 58 ⇒ 37 ...
• 41 ⇒ 102 ⇒ 96 ⇒ 60 ⇒ 51 ⇒ 41 ...
• 42 ⇒ 114 ⇒ 125 ⇒ 105 ⇒ 42 ...
• 50 ⇒ 80 ⇒ 66 ⇒ 62 ⇒ 76 ⇒ 79 ⇒ 67 ⇒ 85 ⇒ 73 ⇒ 50 ...
• 70 ⇒ 74 ⇒ 70 ...

Ces cycles peuvent être utilisés pour créer des boucles qui font des choses différentes à chaque fois et qui deviennent finalement répétitives. Lou Scheffer a utilisé cette idée pour créer un programme Malbolge (inclus dans sa cryptanalyse sur laquelle un lien ci-dessous pointe) qui répète tout ce que l'utilisateur donne en entrée.

Référence dans la culture populaire

Dans la série TV "Elementary", dans l'épisode "Léviathan" (saison 1, épisode 10), un élément clé de l'intrigue est un code informatique rédigé en Malbolge.

Voir aussi

Article connexe

• Code impénétrable

Liens externes

• Site officiel de Malbolge (archivé)
• interpréteur Malbolge (code source C)
• description de l'algorithme d'Andrew Cooke pour créer le premier programme Malbolge
• cryptanalyse de Malbolge par Lou Scheffer
• papier sur la manière d'écrire des programmes Malbolge ; pousse l'analyse de Scheffer un peu plus loin
• version simpliste de "99 bottles" en Malbolge