Alphabets réversibles

Chapitre: VIII. Chiffres monoalphabétiques Prérequis: -

Un alphabet réversible (ou réciproque) est un alphabet désordonné qui, quand on l'applique deux fois à un message clair, redonne le message clair. Comme exemples, on peut mentionner les chiffres Atbash, Albam, Atbah, et l'escargot de Wolseley.
En français, un alphabet réversible s'obtient en prenant les 13 couples de 2 des 26 lettres utilisées et en considérant les lettres de chaque couple comme chiffrées et déchiffrées l'une de l'autre. Ainsi, par exemple, le couple A-F signifie que A est chiffrée par F et F est déchiffrée par A, et vice-versa.
Appelons invariant une lettre chiffrée par elle-même. Dans un alphabet réversible comptant un nombre impair de lettres, on est sûr qu'il y a un nombre impair d'invariants. Si l'alphabet réversible compte un nombre pair de lettres, alors il y aura un nombre pair d'invariants (éventuellement zéro).

Un alphabet réversible sans invariants peut s'écrire sur deux lignes d'un tableau, comme celui ci-dessous. Chaque lettre est remplacée par celle qui est dans la même colonne.

A B C D E G K L N O P Q R
F S W Z M Y X U J I V T H

Le petit programme javascript ci-dessous vous permettra de chiffrer/déchiffrer un message non accentué (au besoin prétraitez le texte) avec un alphabet réversible sans invariants, construit grâce à un mot-clef (sans caractères spéciaux).

 

Message clair

Mot-clef
Grille

Message chiffré



Exercice

En français, combien y a-t-il d'alphabets réversibles sans invariants ?

Solution


Il faut maintenant compter (et c'est nettement plus difficile) le nombre d'alphabets réversibles avec invariants. La formule (trouvée après quelques heures d'effort) est:

où n est le nombre (pair) de lettres de l'alphabet. Avec n=26, on obtient le nombre de 525'079'354'619'951. On constate que le nombre d'alphabets réversibles avec invariants est beaucoup plus élevé que sans invariants.

Le tableau ci-dessous donne le nombre total d'alphabets réversibles pour des alphabets de différentes tailles. Les cinq premiers résultats ont été vérifiés par énumération à l'aide d'un petit programme Mathematica (on s'est arrêté à une taille de 10 car au-delà on fait face à ce qu'on appelle en informatique l'explosion combinatoire).

Lettres (n) Alphabets réversibles* Alphabets désordonnés*
2 2 2
4 10 24
6 76 720
8 764 40'320
10 9'496 3'628'800
... ... ...
26 532'985'208'200'576 4.033·1026

*l'alphabet normalement ordonné est compté dans ce nombre.


Didier Müller, 3.1.03