Le chiffre de Vigenère ressemble au chiffre de César, si ce n'est que le décalage à effectuer n'est pas le même selon la position de la lettre dans le texte.

Imaginons que l'on souhaite chiffrer la phrase "la programmation, c'est vraiment bien !" (juste les lettres, on ne touche pas aux signes de ponctuation). On choisit tout d'abord un mot de passe que le destinataire du message doit aussi connaître : par exemple, choisissons "java" comme mot de passe. Le mot de passe doit alors être transformé en une série de nombres, chacun correspondant à la position de la lettre dans l'alphabet : ici, "java" devient 10-1-22-1.

Pour chiffrer le message, on décalera la première lettre de 10 places, la seconde d'une place, la troisième de 22 places, la quatrième de 1 place, puis on boucle : la cinquième lettre sera décalée de 10 places, la sixième lettre sera décalée d'une place, etc...

Notre message devient alors :

 l  a     p  r  o  g  r  a  m  m  a  t  i  o  n   ,   c '  e  s  t    v  r  a  i  m  e  n  t    b  i  e  n   !
10 01    22 01 10 01 22 01 10 01 22 01 10 01 22      01   10 01 22   01 10 01 22 01 10 01 22   01 10 01 22
----------------------------------------------------------------------------------------------------------------
 v  b     l  s  y  h  n  b  w  n  w  u  s  p  j   ,   d '  o  t  p    w  b  b  e  n  o  o  p    c  s  f  j   !

On voit dans le résultat que deux lettres différentes peuvent, au final, apparaître comme la même lettre dans le message crypté.

Voici deux fichiers contenant un message, en français, chiffré avec cette technique. A vous de les déchiffrer (dans les deux fichiers, seules les lettres ont été modifiées, les signes de ponctuation ainsi que les chiffres n'ont pas été touchés) : fichier1 et fichier2 (clic-droit, puis enregistrer-sous). Les deux messages sont chiffrés avec des mots de passe différents, qui consistent chacun en un mot de moins de 30 lettres.

Plus d'informations sur le chiffre de Vigenère sur le site de Wikipedia.

Imaginons que l'on connaisse la longueur du mot de passe (ici, pour notre exemple, quatre) utilisé pour crypter le message. On sait que, toutes les quatre lettres, le décalage est le même...

On peut construire un tableau de caractères contenant toutes les lettres du message. Si on créait un autre tableau de caractères où ne figuraient que les 1°, 5°, 9°, 13°, ... lettres du message (une lettre sur quatre), on se retrouverait avec le même problème qu'à la partie précédente : on devrait trouver la lettre qui apparait le plus souvent, considérer que cette lettre est l'équivalent du 'e' dans le message clair, et réaliser le décalage inverse.

Dans notre exemple, on créerait 4 tableaux de caractères : dans le premier ne figureraient que les lettres 1, 5, 9, 13... du message crypté, dans le second ne figureraient que les lettres 2, 6, 10, 14, ... du message crypté, dans le troisième ne figureraient que les lettres 3, 7, 11, 15, ... du message crypté, et dans le dernier ne figureraient que les lettres 4, 8, 12, 16, ... du message crypté :

1° tableau : v  y  w  s  o  b  o  s
2° tableau : b  h  n  p  t  b  o  f 
3° tableau : l  n  w  j  p  e  p  j
4° tableau : s  b  u  d  w  n  c

Sur les quatre tableaux, on utiliserait la technique expliquée précédemment pour trouver le décalage de chaque message, et on pourrait ainsi reconstituer le fichier d'origine. Par exemple (même si ici, le message est trop court pour que la méthode fonctionne de manière infaillible), on voit que dans le premier tableau, la lettre qui apparait le plus souvent est la lettre 'o' : cette lettre doit correspondre au 'e', on doit donc décaler toutes les lettres du premier tableau de -10 places dans l'alphabet (ou +16 places), ce qui donne :

1° fichier : l  o  m  i  e  r  e  i

On a ainsi déchiffré un quart du message, reste à recommencer sur les autres tableaux. Cette méthode ne fonctionne efficacement que si le message à chiffrer est long par rapport à la longueur du mot de passe (et qu'il existe donc des répétitions dans les décalages de lettres).

Si vous avez suivi mes conseils à la partie précédente, rappelez-vous que vous avez une fonction qui prend en paramètre un tableau de caractères et trouve le caractère qui y apparait le plus souvent...

Si le mot de passe faisait n caractères, on devrait créer n fichiers texte... Reste maintenant à trouver une méthode pour obtenir la longueur du mot de passe.

L'indice de coïncidence d'un texte est la probabilité, si on prend deux lettres au hasard dans un texte, que ces deux lettres soient les mêmes. Pour calculer l'indice de coïncidence d'un texte, c'est vraiment très simple.

Posons N le nombre de lettres du texte que l'on examine. Posons Na, le nombre de 'a' dans le texte, Nb, le nombre de 'b' dans le texte, etc...

Calculons d'abord Pa, la probabilité de choisir deux lettres au hasard dans un texte, et que ces lettres soient toutes les deux un 'a'. La probabilité de prendre une lettre au hasard dans le texte et que cette lettre soit un 'a' est égale à Na/N.

Une fois que l'on a pris le 'a' dans le texte, on le met de côté, on a (N-1) lettres dans le texte et (Na-1) caractères 'a' dans le texte. La probabilité de tirer une seconde fois un 'a' dans le texte est égale à (Na-1)/(N-1). Au final, la probabilité de tirer deux lettres au hasard dans le texte et que ces deux lettres soient 'a' est égale au produit des probabilités que l'on vient de calculer, c'est à dire Pa = Na/N * (Na-1)/(N-1).

De même, la probabilité Pb de choisir deux lettres au hasard et que ces lettres soient 'b' est égale à Nb/N * (Nb-1)/(N-1).

Au final, on trouve que l'indice de coïncidence du texte est égal à Pa + Pb + Pc + ... + Pz, c'est à dire

[ Na*(Na-1) + Nb*(Nb-1) + Nc*(Nc-1) + ... + Nz*(Nz-1) ] / [ N*(N-1) ]

Remarquez que le fait de décaler toutes les lettres d'un même cran dans le texte ne modifie pas l'indice de coïncidence du texte. Par contre, le fait de décaler les lettres d'un décalage différent (comme dans le code de Vigenère) modifie l'indice de coïncidence. De plus, le fait de ne prendre qu'une lettre sur deux, ou une lettre sur trois, ou une lettre sur quatre, ... dans le texte ne modifiera que très peu (si le texte est assez long) son indice de coïncidence.

En quoi l'indice de coïncidence peut nous aider ? Il se trouve que si l'on met des lettres au hasard dans un texte (le texte n'aura alors aucun sens), l'indice de coïncidence de ce dernier sera à peu près égal à 0,0385. Par-contre, si vous écrivez un texte en français (vous ne choisissez donc pas les lettres au hasard), l'indice de coïncidence sera à peu près égal à 0,0785.

Reprenons l'exemple d'un message chiffré en Vigenère avec le mot de passe "java". Si vous calculez l'indice de coïncidence de ce message, vous obtiendrez probablement un score aux alentours de 0,04 (car le message crypté ne ressemble en rien à du français). Si vous ne prenez qu'une lettre sur deux du message, l'indice de coïncidence du nouveau texte sera aussi assez proche de 0,04. Si vous ne prenez qu'une lettre sur trois du message, l'indice de coïncidence du nouveau texte sera aussi assez proche de 0,04. Par contre, si vous ne prenez qu'une lettre sur quatre du message (quatre étant la longueur du mot de passe), vous créez un message où toutes les lettres ont été décalées d'un même cran... Comme dit précédemment, l'indice de coïncidence ne varie pas si l'on décale toutes les lettres d'un même cran : vous constaterez alors que l'indice de coïncidence de ce nouveau texte sera très proche de 0,0785.

Pour résumer, voici comment trouver la longueur du mot de passe utilisé pour chiffrer un texte en Vigenère. Constituez un nouveau tableau de caractères où ne figurent qu'une lettre sur deux du message chiffré et calculez son indice de coïncidence. Tant que l'indice de coïncidence obtenu n'est pas proche de 0,0785, construisez de nouveaux tableaux de caractères où ne figurent qu'une lettre sur 3, 4, 5... du message chiffré. Dès qu'un tableau de caractères donne un indice de coïncidence proche de 0,0785, vous avez trouvé la longueur du mot de passe : si le texte qui donne un bon score est obtenu en ne gardant qu'une lettre sur k dans le message chiffré, alors le mot de passe utilisé dans le chiffrage fait k lettres.

Vous pouvez alors utiliser la méthode décrite dans la section précédente pour décrypter complètement le message.

Cette méthode ne fonctionne que si le texte est assez long par rapport au mot de passe utilisé. De plus, le français possédant un indice de coïncidence très élevé, cette méthode s'applique bien pour des textes en français.

Plus d'informations sur l'indice de coïncidence sur Wikipedia.

. Écrivez une fonction qui prend en paramètre tableau de caractères, un entier n et un entier k, et produit en sortie un tableau de caractères où ne sont conservés qu'un caractère sur n du fichier d'entrée, sélectionnés à partir du k° caractère du fichier d'entrée. Cette fonction devrait vous être utile pour résoudre cette partie.
Si par exemple, votre tableau contient les caractères b-o-n-j-o-u-r-c-a-v-a, que n vaut deux et k vaut trois, alors votre nouveau tableau devrait contenir n-o-r-a-a.

. Ecrivez une fonction qui prend en paramètre un tableau de caractères en entrée, et produit en sortie l'indice de coïncidence du texte contenu dans le tableau.

. N'oubliez pas que, si vous avez suivi mes conseils dans la partie précédente, vous possédez une fonction qui peut analyser un tableau de caractères, trouver la lettre qui y apparait le plus souvent, et proposer un décalage à appliquer au tableau.

. J'ai précisé, au début de cette page, que les mots de passe utilisés dans les deux textes cryptés font moins de 30 lettres... Vous pouvez donc tester tous les découpages possibles du texte entre 2 et 30, et conserver le découpage qui est le plus proche de l'indice de coïncidence du français.