Le chiffrement par substitution consiste à remplacer, dans un message, chaque lettre par une autre lettre. Deux lettres égales dans le texte original doivent être chiffrées de la même manière, et deux lettres différentes doivent être chiffrées différemment.

Par exemple, considérons cette substitution :

lettre originale :  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
lettre chiffrée  :  w  q  a  x  s  z  c  d  e  v  f  r  b  g  t  n  h  y  j  u  k  i  l  o  m  p

Les 'a' du texte original deviendrons des 'w' dans le texte chiffré, les 'b' deviendrons des 'q', etc.. Notre message sur la programmation deviendra :

 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   !
----------------------------------------------------------------------------------------------------------------
 r  w     n  y  t  c  y  w  b  b  w  u  e  t  g   ,   a '  s  j  u    i  y  w  e  b  s  g  u    q  e  s  g   !

Remarquez que le chiffrement de César est un cas particulier de chiffrement par substitution.

Voici un fichier (clic-droit, puis enregistrer-sous) contenant un message, en français, chiffré avec cette technique. A vous de le déchiffrer (seules les lettres ont été modifiées, les signes de ponctuation ainsi que les chiffres n'ont pas été touchés).

Plus d'informations sur le chiffrement par substitution sur le site de Wikipedia.

Comme pour César, on peut rechercher la lettre la plus fréquente, ce qui permettra de trouver le 'e' du texte. Malheureusement, contrairement à César, trouver le 'e' ne permet pas de trouver toutes les autres lettres. L'indice de coïncidence du texte ne vas pas nous aider car, comme cet indice n'est pas sensible au décalage de lettres, on risque fort de trouver une valeur proche de 0,0785.

Cependant voici un petit tableau fort utile (donné sous forme Java) :

char[] tab_freq_francais = {'e', 'a', 'i', 's', 't', 'n', 'r', 'u', 'l', 'o', 'd', 'm', 'p', 'c', 'v', 'q', 'g', 'b', 'f', 'j', 'h', 'z', 'x', 'y', 'k', 'w'};

Ce tableau, extrait du site Wikipedia, donne la fréquence d'apparition des lettres en français, classée de la lettre la plus fréquente à la lettre la moins fréquente. En construisant un tableau où figureraient le nombre de chaque lettre du texte (par exemple, dans la case 0 figurerait le nombre de 'a' du texte, dans la case 1 figurerait le nombre de 'b' du texte, ...), et en triant ce tableau, vous devriez pouvoir déduire quelle lettre du message chiffré correspond à quelle lettre dans le message clair.

Malheureusement, beaucoup de lettres possèdent des fréquence d'apparition très proches, et vous devrez peut-être procéder à de petites permutations de lettres dans le tableau précédent avant de déchiffrer correctement le message.

Pour résumer, vous devrez compter dans un tableau de 26 cases chaque lettre du texte, trier le tableau, et reconstruire le message déchiffré en utilisant le tableau de fréquences donné précédemment. Le texte ainsi obtenu possèdera sûrement des erreurs : identifiez des lettres qui semblent inversées (à côté des apostrophes, on trouve souvent un l ou un c, les mots de deux lettres sont souvent "un", "le", "la" ou "de", ...), modifiez un peu le tableau de fréquences et relancez votre programme (après l'avoir recompilé).

. N'hésitez pas à découper votre programme en fonctions... Cela sera ainsi plus simple, pour vous, de trouver et corriger vos erreurs.

. Si vous n'êtes pas dégouté du décryptage, et une fois votre projet terminé, vous pouvez visiter ce site, où le FBI appelle à l'aide pour déchiffrer un message qui n'a, semble-t-il, pas été chiffré avec des moyens modernes (puisque l'auteur du message chiffrait ses textes à la main) et qui pourtant résiste aux analystes de l'agence...