Forum de mathématiques - Bibm@th.net

Est-ce que votre crypto est (ou est censé être) militaire ?
Il provient d'un jeu, d'une énigme ?
Vous n'avez qu'un seul message ?
Vous connaissez la langue utilisée ?
Vous avez une idée du contenu du message (mots probables) ?

En règle générale, on ne peut pas déterminer la méthode de chiffrement de la forme du crypto.

Pour les cryptos de type militaire, le problème de Zendia est un bon exemple.

Le message donné en échantillon sur la page Wikipédia est constitué d'un en-tête et du corps du message formé de 68 groupes.
On voit facilement que le nombre de groupes est dans l'en-tête et que les deux premiers groupes sont identiques aux deux derniers (on peut vérifier ces hypothèses sur les 375 messages du problème).
Le "vrai" crypto est compris entre ces deux groupes répétés.

La méthode de chiffrement est indiquée par le premier des groupes redoublés (mais on ne le sait pas au début du problème).
Les 375 messages ont la même forme bien que les méthodes de chiffrement soient diverses et variées.

Si on fait l'hypothèse que votre message a une structure du même genre, il faudrait faire les tests classiques (indice de coïncidence, présence, fréquences... etc.) sur la partie comprise entre les deux groupes répétés.

Si ça ne donne rien, il faut essayer les différentes méthodes de chiffrement connues une à une ... :-)

Bin alors,

KJNO YYXX IJNM QSLCBI SS WDDOQHXO ?

:-)

Bonjour à tous,

Il s'agit, si je ne m'abuse, d'une question d'algèbre linéaire dans l'anneau (non intègre !) $\mathbb{Z}/26 \mathbb{Z}$.

En posant A=1, B=2, ... Z=0 modulo 26, on peut écrire le codage sous forme matricielle :

$
\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
B \\
O \\
N \\
J \\
O \\
U \\
R
\end{pmatrix}
\equiv
\begin{pmatrix}
1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
2 \\
15 \\
14 \\
10 \\
15 \\
21 \\
18
\end{pmatrix}
\equiv
\begin{pmatrix}
17 \\
3 \\
24 \\
25 \\
10 \\
13 \\
20
\end{pmatrix}
\equiv
\begin{pmatrix}
Q \\
C \\
X \\
Y \\
J \\
M \\
T
\end{pmatrix}
$

Ce système de codage est donc lié aux matrices $K_n$ ($n\geqslant 2$) :

$$K_{n}\equiv \begin{pmatrix}
1 & 1 & 0 & 0 & \cdots  & 0 \\
0 & 1 & 1 & 0 & \cdots  & 0 \\
0 & 0 & \ddots  & \ddots  &  & \vdots  \\
\vdots  & \vdots  &  & \ddots  & \ddots  & \vdots  \\
0 & 0 &  &  & 1 & 1 \\
1 & 0 &  &  & 0 & 1
\end{pmatrix}$$

Ces matrices sont singulières. On peut vérifier (démonstration laissée au lecteur) :

$$\det (K_n)\equiv \left\{
\begin{array}{l}
0\text{ si }n \text{ pair} \\
2\text{ si }n \text{ impair}
\end{array}
\right. $$

Puisque ni $0$ ni $2$ ne sont inversibles dans $\mathbb{Z}/26 \mathbb{Z}$ (les éléments inversibles sont les entiers premiers avec 26), les matrices $K_n$ n'ont pas d'inverses.

Le codage n'est donc pas bijectif, ni injectif, ni surjectif puisque ces trois propriétés sont équivalentes pour un endomorphisme d'un espace vectoriel module libre de dimension finie.

C'est curieux, mais en codant un mot par ce procédé on perd de l'information et l'on ne peut pas retrouver avec certitude le mot dont on est parti.

[Je complète... :-) ]

Le rang de $K_n$ est $n-1$, autrement dit le noyau de $K_n$ est un sous-module de $(\mathbb{Z}/26\mathbb{Z})^n$ de dimension $1$.

Si $n$ est pair, $ker(K_n)$ est le sous-module engendré par le vecteur $\begin{pmatrix}
1 \\
25 \\
1 \\
25 \\
\vdots\\
1 \\
25
\end{pmatrix}$

Par exemple, tous les mots qui se codent comme 'BONJOU' sont $\begin{pmatrix}
B+k \\
O+25k \\
N+k \\
J+25k \\
O+k \\
U+25k
\end{pmatrix}$ pour $k \in \mathbb{Z}/26\mathbb{Z}$

Ce qui donne les 26 mots :
BONJOU, CNOIPT, DMPHQS, ELQGRR, FKRFSQ, GJSETP, HITDUO, IHUCVN,
JGVBWM, KFWAXL, LEXZYK, MDYYZJ, NCZXAI, OBAWBH, PABVCG, QZCUDF,
RYDTEE, SXESFD, TWFRGC, UVGQHB, VUHPIA, WTIOJZ, XSJNKY, YRKMLX
ZQLLMW, APMKNV

Si $n$ est impair, $ker(K_n)$ est le sous-module engendré par le vecteur $\begin{pmatrix}
13 \\
13 \\
\vdots\\
13
\end{pmatrix}$
Ce qui est amusant, c'est que ce sous-module ne comprend que deux vecteurs : $\begin{pmatrix}
13 \\
13 \\
\vdots\\
13
\end{pmatrix}$ et $\begin{pmatrix}
0 \\
0 \\
\vdots\\
0
\end{pmatrix}$

Il n'y a que deux mots qui se codent comme 'BONJOUR' : $\begin{pmatrix}
B+0 \\
O+0 \\
N+0 \\
J+0 \\
O+0 \\
U+0 \\
R+0
\end{pmatrix} \equiv
\begin{pmatrix}
B \\
O \\
N \\
J \\
O \\
U \\
R
\end{pmatrix}$ et $\begin{pmatrix}
B+13 \\
O+13 \\
N+13 \\
J+13 \\
O+13 \\
U+13 \\
R+13
\end{pmatrix} \equiv
\begin{pmatrix}
O \\
B \\
A \\
W \\
B \\
H \\
E
\end{pmatrix}$

Tout serait bien plus simple avec des matrices inversibles :-)) Voir le chiffrement de Hill

Bonjour à tous, bonjour meublat,

Votre message illustre parfaitement ce que je disais plus haut.
Avec les indications que vous donnez, on ne va pas très loin.

On se doute que le crypto est chiffré en Vigenère.

En 1853, un chirurgien dentiste du nom de John Hall Brock Thwaites a proposé à la Society of Arts un appareil cryptographique (semblable à se qu'on appelle en France une réglette de Saint-Cyr) qui permettait d'obtenir, prétendait-il, des cryptogrammes absolument indéchiffrables.
Charles Babbage, à qui on avait demandé son avis, a affirmé que le système était équivalent à un chiffrement de Vigenère et n'était pas indéchiffrable.
Thwaites a alors lancé un défi à Babbage : un cryptogramme chiffré avec son système.
Babbage a décrypté le message (un poeme de Tennyson, “The Vision of Sin”).
C'est la première trace que l'on ait du décryptement d'un message chiffré en Vigenère.
On ne sait pas comment Babbage s'y est pris.
On suppose qu'il a utilisé une technique semblable à celle décrite plus tard par Fridrich Wilhelm Kasiski, en 1863.

Si notre message est chiffré en Vigenère, la première chose à faire est de trouver la longueur de la clé. Curieusement, le test des indices de coïncidence ne donne rien : pas de résultat saillant. J'ai cherché par force brute toutes les clés de tailles 2 à 28, sans succès. J'ai cherché si le crypto n'était pas un autoclave sur le clair ou sur le crypto : négatif.

J'ai alors cherché la page d'où venait ce crypto : Geocaching

Et là, ça m'a sauté aux yeux :

Vous êtes sur les traces de Charles mais inutile de relever le défi de Thwaites puique vous possédez la clé...

Autrement dit, on a la clé sous les yeux ! La clé est, en supprimant les accents et les espaces :

'VOUSETESSURLESTRACESDECHARLESMAISINUTILEDERELEVERLEDEFIDETHWAITESPUIQUEVOUSPOSSEDEZLACLE'

Le programme Python suivant donne la solution :

Je vous laisse crapahuter dans les montagnes pour trouver la cache.

Quant à moi, je vais faire la sieste dans mon hamac, à l'ombre.

Bon courage :-)

Bonjour Dynastato,

Si vous voulez mon avis, la méthode que vous utilisez est vouée à l'échec. On peut contourner le problème d'espace mémoire en utilisant un itérateur qui va retourner un alphabet à chaque appel, mais le problème de temps d'exécution va persister.

Il y a $26! = 403291461126605635584000000$ alphabets possibles. En supposant un test toutes les nanosecondes, le temps nécessaire pour tester tous les alphabets est $\frac{26! \times 10^{-9}} {3600\times 24\times 365}\approx 12788288341$ années. 
Même en étant patient ...

Puisqu'il semble que les espaces entre les mots soient conservés dans le crypto, vous pouvez utiliser les motifs des mots. 
La fonction Python suivante renvoie le motif d'un mot :

Par exemple :

Le motif d'un mot est invariant par une substitution mono-alphabétique.
Par exemple, le mot 'ALPHABETIQUE' a pour motif 'ABCDAEFGHIJF'. Si on décale toutes ses lettres d'un rang (chiffre de César) on obtient 'BMQIBCFUJRVF' qui a le même motif :

Donc, si dans un crypto on a le mot 'BMQIBCFUJRVF', on peut chercher les mots du dictionnaire qui ont le même motif que lui. Il n'y en a que quatre pour mon dico :  'ORTHOPEDIQUE', 'ALPHABETIQUE', 'ALPHABETISME', 'ASPHALTERONT'.

On a donc quatre possibilités d'alphabet déchiffrant. En croisant les résultats obtenus pour d'autres mots du crypto, on obtient en général le texte clair rapidement.

Je ne peux pas être plus précis, car je ne connais pas MATLAB.

Note : j'utilise les dictionnaires de l'ACA.

---
It is not necessary to be crazy to be a cryptanalyst. But it always helps.
Joseph Rochefort

Bonjour Martin,

* Alice chiffre le message avec la clé publique de Bob et le signe avec sa clé privée (d'Alice).
* Après réception du message, Bob vérifie la signature avec la clé publique d'Alice puis il déchiffre le message avec sa clé privée (de Bob).

Là on ne connaît pas trop le contexte. Il manque le début du problème.

Si Alice, Bob, ..., Xavier partage une même clé K d'un chiffre symétrique, alors Alice chiffre le message avec K et le signe avec sa clé privée.
Chaque récipiendaire vérifie la signature avec la clé publique d'Alice, puis déchiffre le message avec la clé commune K.

S'ils n'ont pas de clé en commun, alors Alice choisit une clé aléatoire K et elle chiffre le message avec K.
Puis elle signe la clé K avec sa clé privée.
Ensuite, elle chiffre cette clé signée avec la clé publique de chacun de ses 25 correspondants.
Elle diffuse ensuite le message chiffré avec les 25 clés signées et chiffrées.

Chacun des récipiendaires applique sa clé privée à chacune des clés signées et chiffrées jointes au message puis applique la clé publique d'Alice pour retrouver K qui permet de déchiffrer le message.
Au maximum 25 essais sont nécessaires (Alice peut aussi écrire à chaque fois le nom du correspondant, mais alors la liste des correspondants est divulguée).

Pour d'autres protocoles, voir B. Schneier - Applied Cryptography (2d ed)
p.523 - 22.7 Conference Key Distribution and Secret Broadcasting

Bonsoir Fred, bonsoir à tous,

Juste un lien pour les radins qui ne veulent pas s'abonner à Quadrature :

Des mathématiciens polonais au coeur du décryptement de la machine Enigma

En fouillant dans le répertoire de Philippe Guillot, je suis tombé sur un article de La Science et La Vie N° 69 – mars 1923

La cryptographie et les machines à cryptographier – Lieutenant-Colonel Givierge

Bonne lecture.

Bonjour Oliv,

Le crypto que vous donnez n'est pas facile à manipuler. Si je fais un coupé-collé de votre crypto dans une cellule d'un IPython Notebook, les caractères 189 et 209 ne sont pas des espaces, mais 'ª' et 'o' respectivement.

Le crypto fait 581 caractères et le clair fait 560 caractères; comme dans le crypto il y a 7 quadruples espaces, je peux supposer qu'un quadruple espace correspond à un caractère tabulation \t : on retrouve les 3*7 = 21 caractères supplémentaires. Est-ce que cette expansion de \t en quatre espaces est dû au procédé de chiffrement ou est une interprétation du terminal ?

Si on remplace les quadruples espaces par des \t on a bien un crypto de 560 caractères et les caractères 189 et 209 sont des espaces chr(32).

D'autre part le caractère chr(206) ne s'affiche pas. On pourrait croire à première vue que la chaîne de test que vous donnez ÷&&zÔέ?S| fait 9 caractères. Erreur! elle en fait 10 car il y a un chr(206) invisible entre le 'Î' et le '?'.

Tout ça est embêtant, car on ne sait pas trop si on travaille sur le bon crypto.

Puisque vous proposez de donner les cryptos correspondants à des messages quelconques, je voudrais bien avoir les chiffrés des chaînes :

  'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' (64 a)

et

  'bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb' (64 b)

évidemment sans les guillemets et avec la même clé que précédemment, juste pour voir si ça mélange bien les lettres.

Finalement, connaissant l'optimisme inoxydable des créateurs de code, je propose comme traduction de ÷&&zÔέ?S| le mot de 10 lettres le plus probable : Incassable

J'ai bon ? ;-))

Bonjour à tous,

Hélas ! mon cher yoshi, j'ai cassé ma boule de cristal :-)

L'énoncé est visiblement incomplet : on ne connaît pas la "machine précédente". Une machine Enigma ???

La description donnée fait penser à un cadran d'Alberti : le grand disque avec un alphabet normalement ordonné, le petit disque avec un alphabet dans le désordre.
On initialise le dispositif en mettant le A en face du K (donc A -> K).
On code chaque lettre du texte clair et l'on fait tourner à chaque fois le petit disque d'un cran.

Comme on ne connaît ni l'alphabet désordonné, ni le sens de rotation, on ne peut rien dire de plus.

Ça serait sympa de donner l'énoncé complet !

Bonjour Baptiste,

C'est un gag ? un rébus ?
En me basant (vaguement) sur les formes, je dirais :

54|_(_)7

Bonjour Jeremy,

En fait de technique, j'ai utilisé un script Perl pour décrypter ce message en cinq minutes.
J'ai converti ce script en Python dans un IPython-NoteBook pour expliquer l'algorithme utilisé.
(Je trouve le concept de IPython-Notebook vraiment épatant !)

On le trouve ici : substitution_mono

A vous de jouer.