[Cryptanalyse] Détecter le chiffrement par transposition

Quel indice utiliser ?

a marqué ce sujet comme résolu.
Auteur du sujet

Bonsoir à tous !

Je suis en train d’examiner un texte possiblement chiffré, et je suis en train de le passer au crible de plusieurs tests, afin d’en savoir plus à son sujet. J’ai donc, par exemple, utilisé l’indice de coïncidence, qui est assez efficace pour savoir si l’on a affaire ou non à un chiffrement poly-alphabétique. Je suis maintenant à la recherche d’un indice permettant de discerner si l’on a ou non affaire à un chiffrement par transposition, quel qu’il soit. En existe-il un ?

Je me suis un peu creusé la tête et, en l’absence d’indice existant, je vous proposerais le raisonnement suivant : dites-moi ce que vous en pensez.

Dans une langue naturelle, il est ce qu’on appelle des règles phonotactiques : en bref, ce sont les probabilités que la lettre y suive la lettre x (px(y)p_x(y)). On aboutit donc, pour une langue donnée, à un tableau phonotactique, qui montre les probabilités de consécutivité (par exemple, chez nous, le Q est quasi-systématiquement suivi par un U, etc.).
Je fais l’hypothèse qu’un chiffrement par transposition va tendre à rendre les probabilités de consécutivité assez uniformes. Ainsi, par exemple, le Q pourra être suivi de n’importe quelle lettre (A, Z, D, F, etc.). En d’autres termes, le chiffrement par transposition tend à diminuer l’hétérogénéité phonotactique.
Comme indices de l’hétérogénéité phonotactique, j’identifie la variance de tous les px(y)p_x(y) du tableau phonotactique (ainsi que le nombre de cases où px(y)p_x(y) vaut 0, que je n’utilise pas ici).
Cependant, bien sûr, le fonctionnement décrit plus haut n’est qu’une tendance : il faut donc la moduler en fonction de la longueur du texte et du nombre de caractères utilisables dans le texte (moins il y en a, moins il peut y avoir de variabilité phonotactique).

Ainsi, j’aboutis à l’indice suivant :

I=V(x,ypx(y))taillealphabet×tailletexteI = \frac{V(\sum_{x,y}p_x(y))}{taille_{alphabet} \times taille_{texte}}

Il est plus que probable que j’ai fait des erreurs dans mon raisonnement : qu’en pensez-vous ? Même partiels, vos avis peuvent beaucoup m’aider !

La moindre remarque est la bienvenue ;) ,
Dwayn

Très occupé ces temps-ci. Laissez un MP si besoin

+0 -0

Cette réponse a aidé l’auteur du sujet

L’idée me semble pertinente, mais ce n’est pas dit que les probabilités de consécutivité deviennent uniforme. Si par exemple on fait de la transposition de couples de lettres, on tend certes vers plus d’uniformité, mais il reste qu’environ la moitié des Q seront toujours suivis d’un U.

Sinon, une idée serait peut-être de vérifier que la distribution des lettres suit celles de la langue du texte, chose qui tend à disparaître pour de la substitution.

+2 -0
Auteur du sujet

Merci de ta réponse !

L’idée me semble pertinente, mais ce n’est pas dit que les probabilités de consécutivité deviennent uniforme. Si par exemple on fait de la transposition de couples de lettres, on tend certes vers plus d’uniformité, mais il reste qu’environ la moitié des Q seront toujours suivis d’un U.

Sinon, une idée serait peut-être de vérifier que la distribution des lettres suit celles de la langue du texte, chose qui tend à disparaître pour de la substitution.

Ryx

La difficulté apparaît lorsqu’on ne connaît pas la langue du texte :) … Éventuellement, on pourrait voir si la variance des probabilités phonotactiques dans diverses langues peut être contenue dans un intervalle, auquel cas on pourrait essayer de voir si la variance du texte s’y trouve ?

Très occupé ces temps-ci. Laissez un MP si besoin

+0 -0

Cette réponse a aidé l’auteur du sujet

Je passe en rase motte pour rappeler qu’il y a d’excellents articles et un tutoriel à ce sujet :

Et la série C’est toute une histoire : la cryptographie d'@Arius et de @Bermudes, notamment la partie 1 qui aborde les inversions de lettre :

+1 -0

Cette réponse a aidé l’auteur du sujet

La difficulté apparaît lorsqu’on ne connaît pas la langue du texte

Ca m’étonnerais que tu n’aies absolument aucune idée de la langue du texte. Tu en as forcément une, au moins un choix parmi 2, 3 ou au pire 4 non ?

Ton raisonnement me parait fondamentalement correct mais de toute manière tu as besoin de la langue pour calculer ton indice phonotactique, le comparer, et pour moduler le résultat par rapport à la distribution des lettres (il va falloir le faire, les deux ne sont pas indépendants). Donc, la langue, c’est la première question à te poser.

Pour déterminer la langue du message, outre les analyses purement mathématiques comme la distribution des symboles, les méta-informations sont extrêmement importantes, et souvent implicites. D’où vient le message ? Que connais-tu de son émetteur ?

Si réellement tu n’as aucune idée de la langue, alors tu ne sais pas ce que tu cherches; tu n’as aucune chance de décrypter le message, toutes les possibilités étant dès lors parfaitement équiprobables.

Édité par QuentinC

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Auteur du sujet

Merci A-312, je les ai tous lu, mais j’avais oublié l’existence du premier (désolé, Ryx :D ).

Ca m’étonnerais que tu n’aies absolument aucune idée de la langue du texte. Tu en as forcément une, au moins un choix parmi 2, 3 ou au pire 4 non ?

Ton raisonnement me parait fondamentalement correct mais de toute manière tu as besoin de la langue pour calculer ton indice phonotactique, le comparer, et pour moduler le résultat par rapport à la distribution des lettres (il va falloir le faire, les deux ne sont pas indépendants). Donc, la langue, c’est la première question à te poser.

Pour déterminer la langue du message, outre les analyses purement mathématiques comme la distribution des symboles, les méta-informations sont extrêmement importantes, et souvent implicites. D’où vient le message ? Que connais-tu de son émetteur ?

Si réellement tu n’as aucune idée de la langue, alors tu ne sais pas ce que tu cherches; tu n’as aucune chance de décrypter le message, toutes les possibilités étant dès lors parfaitement équiprobables.

QuentinC

Je comprends ce que tu dis, mais je cherche la méthode la plus "universelle" possible, pour éviter de simplement comparer les tableaux phonotactiques à la main…

Très occupé ces temps-ci. Laissez un MP si besoin

+0 -0

Cette réponse a aidé l’auteur du sujet

Je ne comprend pas pourquoi dans ton indice tu divises pas la taille du texte.

Tu peux m’expliquer ?

Pour déterminer la langue d’un texte inconnu, généralement on en essaye simplement plusieurs, celle qui colle le mieux et de manière claire (avec une différence notable avec les autres) est choisie. Au final, c’est le sens du message décrypté qui détermine la langue (logique mais pas automatique malheureusement).

Édité par ache

ache.one                 🦹         👾                                🦊

+0 -0
Auteur du sujet

Plus le texte est long, plus la distribution phonotactique va avoir tendance à s’homogénéiser. Mais si, par exemple, on n’a qu’une occurrence de la lettre A (qui précède un T, disons), il est normal que la probabilité qu’un T succède à A vaille 1. De fait, on a hétérogénéité, mais ça reste un artéfact peu représentatif de la méthode de chiffrement.

Très occupé ces temps-ci. Laissez un MP si besoin

+1 -0

Plus le texte est long, plus la distribution phonotactique va avoir tendance à s’homogénéiser.

Dwayn

Pourquoi ? Ça ne me semble pas logique.

Supposons un texte en Français. La distribution phonotactique suis à peu près celle du français. Si on étudie ce texte mais en le répétant. Le nombre de lettre a doublé mais la distribution phonotactique elle n’a que très peu changée. Non ?


Bref, toujours est-il que j’ai du mal à comprendre l’idée. Le chiffrement par transposition va violemment homogénéisé la distribution phonotactique. Pour peu que la longueur du texte soit de l’ordre du carré de l’alphabet, on est censé obtenir une distribution à peu près homogène. La variance va tendre vers 0 donc. Pas besoin donc de diviser encore par la taille du texte.

Édité par ache

ache.one                 🦹         👾                                🦊

+0 -0
Auteur du sujet

Plus le texte est long, plus la distribution phonotactique va avoir tendance à s’homogénéiser.

Dwayn

Pourquoi ? Ça ne me semble pas logique.

Supposons un texte en Français. La distribution phonotactique suis à peu près celle du français. Si on étudie ce texte mais en le répétant. Le nombre de lettre a doublé mais la distribution phonotactique elle n’a que très peu changée. Non ?

ache

Oui mais ça c’est dans le cas où il n’y a pas de chiffrement par transposition. Dans le cas du chiffrement par transposition, les lettres vont être mélangées et donc la phonotactique sera homogénéisée (ce que dis ton deuxième paragraphe). Simplement, dans le cas d’un texte chiffré par transposition, on n’aura connaissance de l’homogénéisation du texte seulement si on a beaucoup d’occurrences de la lettre. Dans un texte court, on aura peu d’occurrences, donc une certaine homogénéité.

Je vais prendre un exemple pour être plus parlant :

Le texte en clair est : je veux que Clem soit contente. Le texte chiffré par transposition (je prends un caractère sur deux du texte clair) : j exqeCe otcnet.evu u lmsi otne.

Comme le texte est court, on a une seule occurrence phonotactique pour Q (suivi de E à 100% des cas) : on a là une belle hétérogénéité phonotactique. Tu comprends bien que, plus le texte est court, moins on a d’occurrences, donc moins on observe l’homogénéisation phonotactique d’un texte transposé. Au contraire, dans un texte français, peu importe à peu près la longueur, les règles phonotactiques seront toujours hétérogènes.

Édité par Dwayn

Très occupé ces temps-ci. Laissez un MP si besoin

+0 -0

Cette réponse a aidé l’auteur du sujet

Oui mais ça, ça vient du fait que le cryptogramme soit de petite taille (25 caractères seulement). Ici, on a ot et ne qui sont représentés 2fois sinon, tout couple de lettre n’est présent qu’une seule fois.

Dans le texte original, on a seulement le couple te qui est répété.

On remarque que j, s, x, q ne sont présent qu’une seule fois dans le message original et donc forcément empêcheront une homogénéité correcte.

aabacadaeafagahaiajakalamanaoapaqarasatauavawaxayazbbcbdbebfbgbhbibjbkblbmbnbobpbqbrbsbtbubvbwbxbybzccdcecfcgchcicjckclcmcncocpcqcrcsctcucvcwcxcyczddedfdgdhdidjdkdldmdndodpdqdrdsdtdudvdwdxdydzeefegeheiejekelemeneoepeqereseteuevewexeyezffgfhfifjfkflfmfnfofpfqfrfsftfufvfwfxfyfzgghgigjgkglgmgngogpgqgrgsgtgugvgwgxgygzhhihjhkhlhmhnhohphqhrhshthuhvhwhxhyhziijikiliminioipiqirisitiuiviwixiyizjjkjljmjnjojpjqjrjsjtjujvjwjxjyjzkklkmknkokpkqkrksktkukvkwkxkykzllmlnlolplqlrlsltlulvlwlxlylzmmnmompmqmrmsmtmumvmwmxmymznnonpnqnrnsntnunvnwnxnynzoopoqorosotouovowoxoyozppqprpsptpupvpwpxpypzqqrqsqtquqvqwqxqyqzrrsrtrurvrwrxryrzsstsusvswsxsyszttutvtwtxtytzuuvuwuxuyuzvvwvxvyvzwwxwywzxxyxzyyzza Outch c’est long !

Édité par ache

ache.one                 🦹         👾                                🦊

+0 -0

Cette réponse a aidé l’auteur du sujet

Je comprends ce que tu dis, mais je cherche la méthode la plus "universelle" possible, pour éviter de simplement comparer les tableaux phonotactiques à la main…

Tout n’est pas automatisable à 100%.

En y réfléchissant un peu plus, je ne suis pas sûr que ton indice phonotactique soit réellement utile pour savoir si oui ou non tu as à faire à un chiffrement par transposition. J’ai l’impression que ça sera trop dépendant de la distribution. En revanche il pourrait être utile pour découvrir la taille des blocs, et, de proche en proche, trouver quoi est adjaçant à quoi, si tu n’as pas d’autre indice plus évident.

En fait, si la distribution et l’indice de coïncidence correspondent à la langue du texte clair, tu n’as pas de substitution, et donc par déduction, tu as forcément de la transposition. Peut-on faire autre chose que de la substitution ou de la transposition ? je ne crois pas, si on considère un texte chiffré qui possède autant de symboles que le texte clair (si ce n’était pas le cas, on aurait pu faire autrement).

Ca suffit et à partir de là, le meilleur moyen est une attaque à texte clair connu. Je ne pense pas que ce soit faisable de manière entièrement automatique par contre. Avec un texte et une taille de bloc suffisament longues, on peut retrouver n’importe quel mot du dictionnaire, et donc impossible sans intervention humaine de vraiment savoir si on progresse vers la solution ou non.

Édité par QuentinC

Ma plateforme avec 23 jeux de société classiques en 6 langues et 13000 joueurs: http://qcsalon.net/ | Apprenez à faire des sites web accessibles http://www.openweb.eu.org/

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte