Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 28-01-2015 17:48:09

gielev
Membre
Inscription : 08-03-2007
Messages : 333

une alternative au test de Kasiski...

Bonsoir,
En complément à la discussion initiée par Hogdush voici une autre manière d'arriver à trouver (parfois*) la longueur de la clé.
On considère le texte recopié sur 2 lignes.
On décale la 2ème ligne d'un cran et on compte le nombre de caractères identiques qui se répètent, puis le pourcentage correspondant.
Lorsque ce pourcentage est, disons élevé, le décalage fait correspond à la longueur de clé.
A noter que tous les multiples de cette longueur donneront aussi un pourcentage élevé.
Prenons un exemple
GIJDAVTPJXJWOVTWYIJGIWYSIWUPLIHXJQEPBTRWNIEEMWAGJILCDCAIGEERUMHVHSEZTWAIOSLESCSJJGRYTMGFGIDPQCNRYWFYNMYLZYIPJMZINSLGIMAWYIJUOCEWVRTTEVFIONVALMHVZIKUEURRQEZDACIIIXDLUDNMNULTMMZTJVKPDMPEYICLPIEIDPRWANRYDPCPMWEXZ
Une petite procédure toute simple à écrire donne le graphique suivant
Exemple1
On voit clairement que la longueur de clé semble être 8.
J'ai pris dans le texte de Hogdush, les 970 premiers caractères.
Voici ce que cela donne
Exemple2
Même si les pourcentages sont plus lissés (et que le Vigenère n'est pas un Vigenère "pur") le 4 émerge...
Amusez-vous bien :).
@Yoshi : en VBA il m'a fallu 7 lignes pour les calculs proprement dits (en ne comptant pas les initialisations et l'affichage)

gielev

* texte pas trop court

Dernière modification par gielev (28-01-2015 17:54:27)

Hors ligne

#2 06-02-2015 11:57:55

gielev
Membre
Inscription : 08-03-2007
Messages : 333

Re : une alternative au test de Kasiski...

re!
*
je m'explique ;)
Début de mon crypto

décalage de 1

G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W
  G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W

décalage de 2

G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W
    G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W

décalage de 3

G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W
      G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W

décalage de 4

G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W
        G I J D A V T P J X J W O V T W Y I J G I W Y S I W U P L I H X J Q E P B T R W

Evidemment ça rend mal comme ça. Faudrait avoir un beau tableau avec jolies superpositions. En plus quand je valide le post apparaît un décalage parasite...
Facile à programmer non ? :)

gielev

Dernière modification par yoshi (06-02-2015 12:05:23)

Hors ligne

#3 06-02-2015 12:11:49

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 13 349

Re : une alternative au test de Kasiski...

Salut gielev,

Evidemment ça rend mal comme ça.

Plus maintenant, tu vois : ça a été une demande de feu ce cher nerosson qui pestait régulièrement contre le non alignement vertical.
Fred a corrigé en ajoutant une police à espacement fixe.
Tu sélectionnes tes lignes, tu cliques sur <> dans la barre d'outils de message, et tu rectifies la balise code en ajoutant = crypto : c'est ainsi que j'ai procédé.

Merci.
Je comprends maintenant ce que tu appelles décalage.
Par contre, je dois être particulièrement bouché : tes répétions de lettres sont à prendre verticalement ?
Parce que, sauf si je ne vois pas clair : là je n'en vois pas ? Il faudrait pousser jusqu'à 8 ?
Je vais voir ça...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#4 06-02-2015 14:03:48

LeSingeMalicieux
Membre
Inscription : 18-01-2015
Messages : 42

Re : une alternative au test de Kasiski...

Salut,

La méthode est effectivement intéressante !
Et si j'ai bien compris, je te confirme, yoshi, que les répétitions à prendre en compte sont effectivement verticalement parlant.

En fait cela vient du principe que si on chiffre le message clair avec une clef de longueur n (ici 8 dans le premier exemple de gielev), tous les 8 caractères du message clair seront chiffrés avec la même lettre de la clef, c'est à dire qu'il subiront le même décalage alphabétique.
Mais ceci est déjà parfaitement expliqué sur cette page : http://www.bibmath.net/crypto/index.php … viganalyse
(section L'essentiel : Trouver la longueur de la clé)

Et comme certaines lettres sont plus fréquentes en français que d'autres (le E notamment, mais pas que) on va les retrouver plus fréquemment dans le message clair, et du coup comme elles sont chiffrées de la même manière (avec le même décalage) elles se répéteront (leur correspondant chiffré) plus fréquemment toutes les 8 lettres.
Ainsi, les lettres identiques du message chiffré, repérées avec le test de gielev, correspondront en général à des lettres fréquentes en français (dans le message clair).

Et en effet, ce test est bien plus efficace que le test de Kasiski, ce dernier supposant la répétition de mots probables dans le message.


Pour être plus complet, je dirais que la méthode de gielev est similaire (dans le principe) à un test existant, appelé le test de Friedman.
Là aussi je ne vais pas en réexpliquer le principe, puisqu'il est brillamment exposé sur cette page (sans toutefois en préciser le nom ni son inventeur) : http://www.bibmath.net/crypto/index.php … viganalyse
(section Méthode moderne : l'indice de coïncidence)
Mais afin de rendre à César ce qui est à César (ou plutôt rendre à Friedman ce qui est à Friedman), je souhaitais juste préciser qu'on doit ce test au génial cryptologue William F. Friedman (1891-1969), qui est d'ailleurs l'inventeur de la notion d'Indice de Coïncidence. Au passage, c'est également à lui que l'on doit le terme de cryptanalyse.
Si l'Histoire vous intéresse, vous trouverez plus d'infos sur cette page : https://fr.wikipedia.org/wiki/William_F._Friedman


Si on applique le test de Friedman au crypto proposé par Gielev, on obtient les résultats suivants, pour des longueurs supposées de la clef allant de 1 à 9 (on pourrait aller plus loin que 9, c'est juste la longueur maximale supposée de la clef) :
- n=1 : IC=0,045
- n=2 : toutes les 2 lettres, IC=0,045 ; 0,065
- n=3 : toutes les 3 lettres, IC=0,043 ; 0,043 ; 0,050
- n=4 : toutes les 4 lettres, IC=0,045 ; 0,084 ; 0,049 ; 0,055
- n=5 : toutes les 5 lettres, IC=0,052 ; 0,059 ; 0,034 ; 0,052 ; 0,050
- n=6 : toutes les 6 lettres, IC=0,039 ; 0,052 ; 0,054 ; 0,059 ; 0,055 ; 0,071
- n=7 : toutes les 7 lettres, IC=0,048 ; 0,060 ; 0,028 ; 0,044 ; 0,032 ; 0,034 ; 0,052
- n=8 : toutes les 8 lettres, IC=0,080 ; 0,108 ; 0,068 ; 0,071 ; 0,040 ; 0,148 ; 0,058 ; 0,074
- n=9 : toutes les 9 lettres, IC= 0,029 ; 0,033 ; 0,028 ; 0,043 ; 0,047 ; 0,055 ; 0,036 ; 0,028 ; 0,059
etc.
(en gras les IC à partir de 0,065, valeur arbitraire)

On remarque que l'IC est quasiment toujours élevé (pour rappel l'IC moyen d'un texte écrit en français est de 0;078, et l'IC d'un texte formé de lettre aléatoires est de 0,0385) pour une longueur de clef n=8.

On peut d'ailleurs, pour chaque valeur de n, calculer la moyenne de tous les IC obtenus. On obtient les résultats suivants (j'ai ici été jusqu'à n=24) :
- n=1 : IC=0,045
- n=2 : IC=0,055
- n=3 : IC=0,045
- n=4 : IC=0,058
- n=5 : IC=0,049
- n=6 : IC=0,055
- n=7 : IC=0,043
- n=8 : IC=0,081
- n=9 : IC=0,040
- n=10 : IC=0,062
- n=11 : IC=0,036
- n=12 : IC=0,055
- n=13 : IC=0,039
- n=14 : IC=0,052
- n=15 : IC=0,052
- n=16 : IC=0,080
- n=17 : IC=0,040
- n=18 : IC=0,051
- n=19 : IC=0,035
- n=20 : IC=0,062
- etc.
- n=24 : IC=0,084

L'IC moyen pour n=8 est de 0,081, ce qui est très élevé. On remarquera d'ailleurs un résultat élevé tous les multiples de 8 (ce qui correspond à une répétition d'une clef de longueur 8).

On peut ainsi en conclure que la clef est de longueur 8 !



Pour parler de mon expérience personnelle, les trois premières étapes que je fais toujours devant un crypto lettré sont :
1 - L'analyse des fréquences
2 - l'IC du crypto
3 - Le test de Friedman

Si ces trois points donnent de bons résultats, on a alors affaire à une transposition.

Un test de Friedman (étape 3) avec un résultat concluant pour n=1 (et donc un IC correct du crypto (étape 2)), mais sans lettres fréquentes dans l'analyse des fréquences (étape 1) correspond à une substitution mono-alphabétique (César, chiffres hébreux, alphabet désordonné, Wolseley, etc.)

Si seule l'étape 3 (test de Friedman) donne un résultat concluant, alors il s'agit d'une substitution polyalphabétique (Vigenère, Beaufort, Porta, Gronsfeld, etc.).


Toujours pour parler de ma propre expérience, le test de Friedman s'est toujours avéré redoutable.
D'ailleurs, je peux te dire, gielev, que j'aime bien le choix de ton poème pour le crypto qui illustre ton propos ;)

Amicalement

Dernière modification par LeSingeMalicieux (06-02-2015 14:09:04)

Hors ligne

#5 06-02-2015 15:14:12

gielev
Membre
Inscription : 08-03-2007
Messages : 333

Re : une alternative au test de Kasiski...

Salut !

yoshi a écrit :

... tes répétions de lettres sont à prendre verticalement ?
Parce que, sauf si je ne vois pas clair : là je n'en vois pas ? Il faudrait pousser jusqu'à 8 ?

Comme l'a dit LeSingeMalicieux, oui c'est à prendre verticalement.
Pour ce qui est de savoir où s'arrêter en fait je me suis fixé 40 arbitrairement dans mes graphiques.
Par contre il est très important de prendre le texte en entier. Dans l'échantillon que j'ai mis évidemment il n'y a aucune coïncidence.
Pour un décalage de 2 sur le texte entier j'ai ainsi eu 4,5% de caractères identiques.
Les pointes autour de 8% (ou plus) sont des révélateurs de la longueur de clé et ce d'autant plus qu'elles se répètent pour les multiples de cette longueur.
Sur un texte avec du Vigenère "tordu" comme celui de Hogdush on arrive quand même à dégager la longueur de clé... c'est amusant...
gielev

Dernière modification par gielev (06-02-2015 15:14:47)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
cinquante plus soixante quinze
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums