Contenu | Rechercher | Menus

Annonce

Ubuntu 16.04 LTS
Commandez vos DVD et clés USB Ubuntu-fr !

Appel à contributeurs. Réunion pour la refonte du wiki lundi 26 juin

Si vous avez des soucis pour rester connecté, déconnectez-vous puis reconnectez-vous depuis ce lien en cochant la case
Me connecter automatiquement lors de mes prochaines visites.

#1 Le 24/11/2016, à 19:36

ublender

[Résolu] chiffre de Vigenère: longueur de la clé

Bonjour,

Je me suis lancé dans le codage d'un programme en c++ pour casser le chiffre de Vigenère. La partie décodage/codage en connaissant la clé est faite, ça fonctionne. Pour décoder sans la clé, on peut commencer par chercher des redondances dans le chiffré puis en déduire des longueurs de clé probables. Le problème c'est que je ne vois pas comment faire pour trouver les redondances: je sais qu'il existe des algorithmes de recherche de motifs mais là, je n'ai pas de motif... Pouvez vous m'expliquer une méthode pour résoudre ce problème?
En vous remerciant par avance

Dernière modification par ublender (Le 25/11/2016, à 22:56)

Hors ligne

#2 Le 24/11/2016, à 21:21

claudius01

Re : [Résolu] chiffre de Vigenère: longueur de la clé

Bonsoir,

Sujet très intéressant ... j'imagine que tu as lu et relu l'article Wikipedia avec notamment l'Indice de coïncidence...

A suivre, suis abonné à ce fil de discussion...

Hors ligne

#3 Le 24/11/2016, à 23:01

ublender

Re : [Résolu] chiffre de Vigenère: longueur de la clé

Merci de ta réponse.
C'est particulièrement la première partie de https://fr.wikipedia.org/wiki/Cryptanal … en%C3%A8re que j'ai regardé. Je n'avais pas vu la suite de cette page (et pourtant j'y ai passé beaucoup de temps sur cette page...), apparemment on peut réduire ce problème à calculer l'indice de coincidence et à comparer avec des valeurs normales. J'ai compris les fonction calculerIC et recoller, les deux autres me paraissent moins claires. Je vois pas comment l'indice de coincidence peut donner la longueur de la clé avec un chiffrement polyalphabétique: la formule sur wikipédia n'est pas démontrée et je ne vois pas d'où elle vient. Je vais chercher une explication à cette formule. m, "le nombre d'alphabets" c'est la longueur de la clé? Si c'est le cas, c'est juste équation à résoudre.

Dernière modification par ublender (Le 24/11/2016, à 23:04)

Hors ligne

#4 Le 25/11/2016, à 00:07

Nasman

Re : [Résolu] chiffre de Vigenère: longueur de la clé

L'indice de coïncidence est propre à chaque langue - pour le français il est voisin de 0.07
Le truc est de calculer les indices de coïncidence avec des clés de longueur différentes.

Supposons que la taille de la clé est de 5
Si on calcule l'indice avec une longueur de clé de 1 on aura quelque chose proche d'une iso répartition des lettres et un indice voisin de 0.038 (de mémoire)
Avec une clé de longueur 2, on aura deux indices, disons 0.035 et 0.04
Avec une clé de longueur 3 on aura 3 indices, par exemple 0.042, 0.04 et 0.041
Avec une clé de longueur 4 on aura 4 indices, par exemple 0.041, 0.05, 0.046 et 0.045
Avec une clé de longueur 5 on aura 5 indices, par exemple 0.065, 0.064, 0.072, 0.075 et 0.080
Avec une clé de longueur 6 on aura 6 indices, par exemple 0.039, 0.042, 0.040, 0.05, 0.044 et 0.035

On voit que c'est avec une clé de longueur 5 que les indices sont les plus proches de ceux de la langue

Si on fait une statistique des lettres tous les 5 caractères, on aura la statistique de la langue employée, avec un décalage correspond à un code de César (décalage de x lettres). En supposant que le E est la lettre la plus fréquence en français on en déduit le décalage. Il suffit de faire cette statistique en décalant d'un caractère.
n, n+5, n+10, n+15, n+20...
n+1, n+6, n+11, n+16, n+21...
n+2, n+7, n+12, n+17, n+22...
n+3, n+8, n+13, n+18, n+23...
n+4, n+9, n+14, n+19, n+24...

Regarde sur ce site.

Dernière modification par Nasman (Le 25/11/2016, à 00:08)


PC fixe et portable avec Precise 64 bits

Hors ligne

#5 Le 25/11/2016, à 22:55

ublender

Re : [Résolu] chiffre de Vigenère: longueur de la clé

C'est super pratique en fait l'indice de coincidence! Ça permet de savoir si on a un cryptage mono ou poly alphabétique, j'adore smile . J'ai compris le fonctionnement, je peux donc commencer à coder ça!
Merci beaucoup de ton explication, je passe le sujet en résolu et je mettrai les sources de mon programme dès que j'aurai fini.

Dernière modification par ublender (Le 25/11/2016, à 22:56)

Hors ligne

#6 Le 09/12/2016, à 12:11

Nasman

Re : [Résolu] chiffre de Vigenère: longueur de la clé

Je me suis attaqué à ce problème en m'initiant au langage C.

J'ai réussi à faire un programme qui teste différentes longueurs de clés et calcule les indices de coïncidence pour chaque décalage pour une longueur de clé fixée. La moyenne de ces indices permet d'apprécier la meilleure longueur vis à vis de l'indice de coïncidence du français.

Une fois la longueur de clé déterminée, je teste les différents décalages des lettres et apprécie la solution en calculant l'écart des histogrammes des lettres entre le français (décalé) et ceux du message chiffré (pour chaque position à l'intérieur du mot clé). Quand la lettre de la clé correspond, alors l'écart est minimal.
En définitive un mot clé est proposé.

J'ai fait un test et la clé trouvée est bien la bonne.

il me reste plus qu'à déchiffrer le message automatiquement une fois le clé trouvée.


PC fixe et portable avec Precise 64 bits

Hors ligne

#7 Le 09/12/2016, à 18:53

ublender

Re : [Résolu] chiffre de Vigenère: longueur de la clé

Bravo, de mémoire la dernière fois que j'ai essayé j'avais des problèmes d'indice de tableau (en gros j'ai des erreurs de segmentations), j'attends que mes examens soient passés et je propose ma solution smile

Hors ligne

#8 Le 09/12/2016, à 19:04

Nasman

Re : [Résolu] chiffre de Vigenère: longueur de la clé

Le programme décrypte automatiquement le fichier chiffré. J'ai juste un petit problème avec le dernier caractère du fichier en clair, sans doute à cause d'une mauvaise gestion de la fin de fichier.
La cause semble en être le caractère EOF retourné par la fonction fgetc qui, malgré un test sur le caractère retourné se retrouve déchiffré et dans le fichier de sortie.
Il faut aussi que je clarifie et remette le programme au "propre".


PC fixe et portable avec Precise 64 bits

Hors ligne

#9 Le 14/12/2016, à 09:50

Nasman

Re : [Résolu] chiffre de Vigenère: longueur de la clé

Je viens de faire un test de décryptage avec mon programme, comme texte de départ j'ai pris un extrait de "la disparition" (qui n'est pas un texte représentatif du français).
Avec un mot clé de 10 caractères, le programme décrypte sans erreur le texte chiffré. Avec une clé de 17 caractères, un des caractères de la clé est erroné mais avec une faute tous les 17 caractères, le texte décrypté est tout à fait lisible (il est très facile de corriger la clé).

Avec une longueur de clé de 17, l'IC moyen du texte chiffré est de 0.081965.
Ce même texte chiffré avec une clé de 1 caractère (chiffre de César) donne un IC de 0.081175. Le programme trouve une longueur de clé de 2 caractères (IC=0.08106) - ce qui serait incorrect mais trouve les deux mêmes caractères dans la clé ce qui revient à un chiffre de César (qui est le cas particulier d'un Vigenere avec une clé d'un caractère).
Nota: avec une clé courte (donc statistique des lettres plus fiable), le texte est décrypté sans erreur.

Dernière modification par Nasman (Le 14/12/2016, à 10:00)


PC fixe et portable avec Precise 64 bits

Hors ligne