(Février 2016) Décryptez les secrets les mieux gardés !

Pour ce Défi de Clem de février, on revient vers de la cryptographie, mais promis, ce sera plus simple que la dernière fois. Le but de ce défi va être de réaliser un programme capable de décrypter¹ automatiquement un texte rendu illisible par l’utilisation de certains chiffrements simples. Semi-automatiquement serait plus exact : un tel programme peut se tromper, et il faut toujours un œil humain pour vérifier le résultat obtenu et, éventuellement, remettre la recherche sur les rails.

Nous allons procéder en trois étapes, permettant d’introduire des outils de décryptage au fur et à mesure, et de présenter trois systèmes de chiffrement, pour ceux qui ne les connaissent pas encore.

Étape 0 : pré-traiter un message

Il est d’usage, dans les systèmes de chiffrement les plus basiques, de simplifier le message à chiffrer en enlevant toutes les espaces et les ponctuations, en remplaçant les caractères spéciaux par leurs versions sans diacritiques (p. ex. ç > c, œ > oe, ê > e, etc.) et en mettant toutes les lettres en majuscule, ou en minuscule, selon ce que vous préférez.

Cette étape 0 consiste donc à écrire une fonction qui prenne un message écrit en français courant (on n’utilisera que du français dans ce défi) et en fasse un message traitable par les fonctions de chiffrement. Dans l’idéal la fonction sera paramétrable, permettant de choisir une sortie en minuscules ou majuscules, de conserver les espaces d’origine ou de les enlever totalement, ou de redécouper le message toutes les $n$ lettres.

Étape 1 : chiffre de César

Le chiffre de César est ce que l’on appelle un chiffrement par substitution simple : chaque lettre du message en clair (c’est-à-dire, le message que l’on va chiffrer) sera remplacée par une et une seule autre lettre ; en outre, deux lettres de l’alphabet de départ ne peuvent pas être remplacées par la même lettre de l’alphabet d’arrivée.

Plus précisément, le chiffre de César se contente de décaler les lettres du message en clair d’un certain nombre de rangs dans l’alphabet. Par exemple, le chiffre de César « classique » décale de trois lettres : A devient D, B devient E, C devient F, etc. Et pour déchiffrer, on procède simplement dans l’autre sens : on décale chaque lettre du même nombre de rangs dans l’autre sens.

Commencez donc par écrire une fonction qui prend un texte et un décalage, et permet de chiffrer / déchiffrer le texte avec le chiffre de César utilisant ce décalage.

Comment l’attaquer ?

L’avantage du chiffre de César (du point de vue de l’attaquant, bien sûr), c’est qu’il n’y a que 25 décalages possibles à essayer et à vérifier, ce qui est donc très rapide. Et c’est précisément ainsi que va fonctionner votre première fonction de décryptage : il s’agira de décaler le message de un rang, puis de deux, puis de trois, etc. et de laisser l’utilisateur trouver lui-même quelle combinaison est la bonne.

Cette méthode a l’avantage de fonctionner quelle que soit la longueur du message, mais elle demande encore une trop grande participation de l’utilisateur. Pour mieux automatiser le processus, on va utiliser une forme simplifiée d’analyse des fréquences.

Vous l’avez sans doute déjà remarqué, toutes les lettres n’apparaissent pas aussi souvent dans un texte : on trouve beaucoup plus de T que de J, par exemple. Eh bien, en français, c’est le E qui truste la première place, et de très loin : en moyenne, 17,26 % des lettres d’un texte en français sont des E. En deuxième et troisième places arrivent le A avec 8,4 % et le S avec 8,08 % : une domination incontestable, vous disais-je.

Ce que vous devez faire, c’est compter combien de fois apparaît chaque lettre du message à décrypter : celle qui apparaît en première position a de très fortes chances d’être un E dans le texte en clair, ce qui vous permet de déduire le décalage qui a été utilisé. Allez ! Au travail !

Étape 2 : substitution simple

Je vais répéter ici la définition d’un chiffrement par substitution simple : chaque lettre du message en clair sera remplacée par une et une seule autre lettre ; en outre, deux lettres de l’alphabet de départ ne peuvent pas être remplacées par la même lettre de l’alphabet d’arrivée.

La différence avec le chiffre de César, c’est qu’il n’y a aucune espèce de logique dans la manière d’échanger les lettres. On peut décider, par exemple, que A devient K, B devient W, C reste C, D devient A, E devient J, etc. On constitue ainsi un alphabet désordonné qui devient la clé de notre message : ici, il s’agirait de KWCAJ…

Pour chiffrer un message, on prend chaque lettre du message en clair et on la remplace par son équivalent dans l’alphabet desordonné. Pour déchiffrer le message, on procède dans l’autre sens. Vous pouvez dès à présent coder ces deux fonctions.

Il n’est cependant pas très pratique de générer (et surtout, de retenir !) un alphabet désordonné parfaitement aléatoire. Il existe donc deux techniques pour générer un alphabet désordonné à partir d’une clé.

• L’alphabet désordonné commence par la clé, nettoyée bien sûr de ses doublons, puis les autres lettres de l’alphabet suivent leur ordre habituel.
• On procède de même, mais en répartissant les lettres sur cinq ou six colonnes, puis on prend les lettres colonne par colonne.

Vous pouvez donc ajouter à votre code la possibilité de générer des alphabets désordonnés à partir d’une clé.

Comment l’attaquer ?

La seule technique viable consiste à généraliser l’analyse des fréquences. Il faut compter combien de fois apparaît chaque lettre dans le cryptogramme, et donc quel pourcentage de l’ensemble des lettres elle représente, et comparer avec la répartition fréquentielle des lettres en français pour tenter une correspondance entre alphabet désordonné et alphabet ordinaire.

Pour cela, vous aurez besoin de ladite répartition fréquentielle du français, que je vous donne directement sous une forme utilisable informatiquement, parce que je suis gentil.

1
2
3
4
5

(0.084,0.0106,0.0303,0.0418,0.1726,
0.0112,0.0127,0.0092,0.0734,0.0031,
0.0005,0.0601,0.0296,0.0713,0.0526,
0.0301,0.0099,0.0655,0.0808,0.0707,
0.0574,0.0132,0.0004,0.0045,0.0030,0.0012)

Cependant, si vous testez votre fonction de décryptage, vous verrez que même avec un texte de plus de huit mille caractères, le résultat obtenu par cette seule méthode est assez illisible. Il vous faudra donc ajouter deux possibilités de post-traitement, afin de rendre la fonction plus utilisable.

Tout d’abord, il faudra que l’utilisateur puisse signaler au programme où il s’est trompé. Supposez par exemple que le programme aboutisse au résultat « JEIUSITOUJOURILA » : il faudrait pouvoir lui dire « En fait, tu as inversé le S et le I dans ton décryptage, essaye encore. ». Je vous laisse décider quelle forme cela peut prendre.

Ensuite, il serait même encore mieux que le programme propose de lui-même ce genre de corrections. En effet, si vous regardez attentivement les fréquences, à part le E qui est tout seul en première place, les autres sont assez susceptibles de changer de place si le texte en clair ne respecte pas strictement la répartition fréquentielle.

Par exemple, C (3,03 %), P (3,01 %) et M (2,96 %) qui ont un score très proche, et assez nettement séparé de leurs plus proches voisins D (4,18 %) et V (1,32 %), ont de fortes chances de se retrouver mélangés. Il pourrait être assez intéressant que le programme propose plusieurs versions alternatives du décryptage, où ces trois lettres arriveraient dans un ordre différent. Et bien évidemment, faire de même avec d’autres lettres susceptibles d’être inversées. À vous de voir comment rendre cette amélioration progressive du rendu la plus ergonomique possible.

Étape 3 : chiffre de Vigenère

Le chiffre de Vigenère est une variante subtile du chiffre de César. On commence par choisir une clé, puis la première lettre de la clé détermine le décalage à appliquer à la première lettre du message, la deuxième lettre de la clé détermine le décalage à appliquer à la deuxième lettre du message, etc. Évidemment, quand on arrive au bout de la clé, on recommence au début de celle-ci, et ainsi de suite jusqu’à ce que le message soit entièrement chiffré.

Pour déchiffrer, on procède bien évidemment en sens inverse. Avec cela, vous avez toutes les informations en main pour écrire les fonctions de chiffrement et déchiffrement pour Vigenère. Vous pouvez bien sûr réutiliser la fonction du chiffre de César déjà codée, puisque le chiffre de Vigenère se sert explicitement de ce dernier.

Comment l’attaquer ?

La différence avec le chiffre de César est subtile, et pourtant, elle fait une grande différence : la méthode de l’analyse de fréquences ne fonctionne plus ! Ou plus exactement, plus toute seule. En effet, avant de pouvoir procéder à une analyse fréquentielle, il faut déterminer la longueur de la clé utilisée. Pour cela, deux méthodes existent.

La première consiste à chercher des suites de trois lettres ou plus (plus c’est long, plus c’est bon) qui apparaissent plusieurs fois dans le cryptogramme. Il y a de très fortes chances que ces lettres correspondent aux mêmes lettres du texte en clair, chiffrées par les mêmes lettres de la clé. Par conséquent, la distance (en lettres) entre la première lettre de la première occurrence et la première lettre de la seconde occurrence est très vraisemblablement un multiple de la longueur de la clé.

En relevant toutes les occurrences de suites de lettres qui apparaissent plusieurs fois, et en calculant la distance entre ces occurrences d’une même suite de lettres, on peut alors rechercher le diviseur commun à toutes ces distances : il s’agit de la longueur de la clé, avec une très forte probabilité.

La seconde méthode est plus mathématique. Elle utilise ce que l’on appelle l’indice de coïncidence des lettres du cryptogramme. Pour calculer l’indice de coïncidence, il faut compter le nombre de A que renferme le cryptogramme (qu’on appelle $n_1$), le nombre de B ($n_2$), le nombre de C ($n_3$), etc. jusqu’à Z ($n_{26}$), et on appelle $n$ le nombre total de lettres que compte le cryptogramme. L’indice de coïncidence $IC$ est alors obtenu par la formule suivante.

Dans un texte parfaitement aléatoire, cet indice de coïncidence est aux alentours de $0,038$. Pour un texte en français, en revanche, il est censé être aux alentours de $0,074$. En pratique, cependant, même avec un texte de plus de 1500 caractères, on peut encore avoir des indices assez nettement différents, comme $0,08$.

Pour obtenir la longueur de la clé par cette méthode, vous allez commencer par calculer l’indice de coïncidence de l’ensemble du cryptogramme (on va l’appeler $IC_1$). Puis vous allez diviser le cryptogramme en deux sous-textes, le premier contenant la 1^re, la 3^e, la 5^e, etc. lettre, et le second contenant la 2^e, la 4^e, la 6^e, etc. lettre ; vous calculez alors l’indice de coïncidence de chacun de ces sous-textes, et vous en faites la moyenne ($IC_2$). Vous répétez le procédé avec trois sous-textes, contenant chacun une lettre toutes les trois lettres, puis avec quatre sous-textes, etc.

Lorsque vous atteignez un indice de coïncidence moyen très proche de celui du français ($0,074$), vous avez trouvé la longueur de votre clé ! Du moins, ça, c’est la théorie. Comme je l’ai dit, dans la pratique, l’indice de coïncidence peut être assez éloigné de $0,074$, même avec la bonne longueur de clé. En outre, les longueurs de clé ayant un diviseur commun avec la longueur réelle (par exemple, 6 pour une longueur réelle de 8) peuvent faire de bons scores, et les diviseurs de la longueur réelle des scores encore meilleurs (par exemple, 4 pour 8).

Comment être sûr de trouver la bonne, alors ? Sauf mauvaise surprise, la bonne longueur de clé aura un indice de coïncidence supérieur à l’indice théorique, tandis que les autres « bons scores » s’en approcheront plutôt par le bas.

Une fois que vous avez déterminé la longueur de la clé, vous divisez le cryptogramme en autant de sous-textes, comme on l’a fait précédemment pour calculer l’indice de coïncidence, et vous appliquez à chacun la même méthode de décryptage que pour le chiffre de César. Finalement, une fois qu’on a la bonne longueur de clé, c’est pas si difficile ! 

En guise de conclusion

Voilà, c’est tout pour ce défi. Comme vous le voyez, il y a plein de petites étapes, que vous pouvez réaliser séparément : par exemple, rien ne vous oblige à coder les fonctions de chiffrement / déchiffrement pour coder les fonctions de décryptage, et vice-versa.

J’ai donné quelques exemples pour tester vos fonctions de décryptage. Je vous invite chaleureusement à proposer vos propres cryptogrammes sur lesquels les autres pourront plancher. Et maintenant, amusez-vous bien !

@nohar si jamais tu passes par là… Pas taper stp.

Python 2 :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

#!/usr/bin/python
# -*- coding: utf-8 -*-
import math
import sys
import urllib2

def get_probable_key(cipher, key_len):
    i = 0
    vigenere_key = ''
    while i < key_len:
        subcipher = sub_string(cipher, i, key_len)
        vigenere_key += frequency_cryptanalysis(subcipher)
        i += 1
    return vigenere_key


def vigenere_uncipher(ciphered, key):
    out_string = ''
    if ciphered != '' and key != '':
        a = ord('a')
        z = ord('z')
        A = ord('A')
        Z = ord('Z')

        ord_key = []
        i = 0
        len_key = len(key)
        while i < len_key:
            ord_key.append(ord(key[i]) - A)
            i += 1

        i = 0
        l = len(ciphered)

        j = 0
        while i < l:
            ch_cipher = ord(ciphered[i])
            if ch_cipher >= a and ch_cipher <= z:  # lowercase
                ch_cipher -= ord_key[j % len_key]
                if ch_cipher < a:
                    ch_cipher += 26
                j += 1
            elif ch_cipher >= A and ch_cipher <= Z: # uppercase
                ch_cipher -= ord_key[j % len_key]
                if ch_cipher < A:
                    ch_cipher += 26
                j += 1
            out_string += chr(ch_cipher)

            i += 1

    return out_string


def get_probable_key_length(cipher):
    french_ic = 0.074
    min_diff = 1
    gap = 0.01
    key_len = 2

    keys_lengthes = []

    number_of_acceptable_ic = 0
    max_number_of_acceptable_ic = 0
    i = 2
    while i <= 10:
        ics = coincident_index_with_step(cipher, i)
        number_of_acceptable_ic = 0
        for ic in ics:
            if math.fabs(float(ic) - french_ic) < gap:
                number_of_acceptable_ic += 1

        if math.fabs(float(ic) - french_ic) < gap:
            max_number_of_acceptable_ic = number_of_acceptable_ic
            key_len = i

            addit = 1

            if addit:
                keys_lengthes.append(key_len)
                key_len = i

        i += 1
    return key_len


def coincident_index(cipher):
    tot_ic = 0.0

    ch = ord('A')
    i = 0
    n = len(cipher)
    while i < 26:
        ni = cipher.count(chr(ch))
        ic = float(ni * (ni - 1)) / (n * (n - 1))
        tot_ic += ic

        i += 1
        ch += 1
    return tot_ic


def coincident_index_count(
    cipher,
    letter,
    start,
    step,
    ):
    c = 0
    d = 0
    i = start
    l = len(cipher)

    while i < l:
        if cipher[i] == letter:
            c += 1
        d += 1
        i += step
    return (c, d)


def frequency_cryptanalysis(cipher):
    occs = {}
    i = 0
    l = len(cipher)
    while i < l:
        if occs.has_key(cipher[i]):
            occs[cipher[i]] += 1
        else:
            occs[cipher[i]] = 1
        i += 1
    letter = ''
    max = -1
    for key in occs.keys():
        if occs[key] > max:
            max = occs[key]
            letter = key

    E = ord('E')
    ciphered_letter = ord(letter)

    diff = ciphered_letter - E
    if diff < 0:
        diff += 26
    return chr(ord('A') + diff)


def sub_string(cipher, start, step):
    out = ''
    i = start
    l = len(cipher)
    while i < l:
        out += cipher[i]
        i += step
    return out


def coincident_index_with_step(cipher, step):
    indexes = []
    start = 0
    while start < step:

        ch = ord('A')
        i = 0
        tot_ic = 0.0
        while i < 26:
            (ni, n) = coincident_index_count(cipher, chr(ch), start,
                    step)
            if n != 0 and n - 1 != 0:
                ic = float(ni * (ni - 1)) / (n * (n - 1))
                tot_ic += ic

            i += 1
            ch += 1
        indexes.append(tot_ic)
        start += 1
    return indexes


def avg(l):
    sum = 0
    for i in l:
        sum += i
    return sum / len(l)


cipher = 'YOUR CIPHER'  # TODO: Fill this var with relevant data
cipher_tmp = cipher.replace(' ', '')
key_len = get_probable_key_length(cipher_tmp)
probable_key = get_probable_key(cipher_tmp, key_len)
txt_plain = vigenere_uncipher(cipher, probable_key)
print txt_plain

Ton code marche foutrement bien. Je crois bien qu’il fait un sans faute sur l’exemple donné.

Tu l'as testé ?

Quelqu'un fera plus propre (et plus optimisé) que moi, je ne me fais pas de souci là-dessus.

@nohar si jamais tu passes par là… Pas taper stp.

1
2
3
4

         This is Bill.
 o       Bill respects the PEP-08 and doesn't name his variables 'l'.
/|\      Bill is smart.
/ \      Be like Bill.

Pour ceux que ça intéresse, j'ai lu Histoire des codes secrets de Simon Singh il y a quelques années, j'ai beaucoup aimé. Je recommande chaudement, d'autant plus que l'ouvrage présente d'autres chiffrements comme Enigma, ADFGVX, RSA, l'échange de clés Diffie-Hellman…

C'était pas très relevant comme intervention, même si ça fait sens.

Déchiffrement de Vigenère (donc de César)

Un petit test en Java, qui déchiffre du Vigenère (donc du César) :

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

package info.kisai.vigenere;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Locale;
import java.util.Map;

/**
 * Déchiffrement d'un code de Vigenère. Code sous WTFPL - http://www.wtfpl.net
 * Created by spacefox on 01/02/16.
 */
public class Vigenere {

    private static final char[] ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toCharArray();
    private static final int ALPHABET_SIZE = ALPHABET.length;
    private static final char MOST_FREQUENT_LETTER = 'E';

    // Je suppose que l'index de coïncidence va dépasser cette valeur. Si non, le cas n'est pas géré…
    private static final double INDEX_THRESHOLD = 0.070;


    public String unCypher(String in) {
        String cleanIn = in.replace(" ", "").toUpperCase(Locale.FRANCE);

        int step = 0;
        List<String> subCyphers;    // On garde la liste des sous-chaînes, elle re-sert ensuite
        do {
            step++;
            subCyphers = splitCypher(cleanIn, step);
        } while (computeMeanIndexOfCoincidence(subCyphers) < INDEX_THRESHOLD);

        List<String> subUnCyphered = new ArrayList<>(step);
        for (String subCypher : subCyphers) {
            Character mostFrequent = mostFrequent(computeFrequencies(subCypher));
            Character keyLetter = toLetter(mostFrequent - MOST_FREQUENT_LETTER);
            subUnCyphered.add(unCaesar(subCypher, keyLetter));
        }

        return concatenate(subUnCyphered, cleanIn.length());
    }

    private List<String> splitCypher(String cleanIn, final int step) {
        List<String> subCyphers = new ArrayList<String>(step) {{
            for (int i = 0; i < step; i++) {
                add("");
            }
        }};
        for (int i = 0; i < cleanIn.length(); i++) {
            subCyphers.set(i % step, subCyphers.get(i % step) + cleanIn.charAt(i));
        }
        return subCyphers;
    }

    private float computeMeanIndexOfCoincidence(List<String> subCyphers) {
        float sumIndexes = 0;
        for (String subCypher : subCyphers) {
            sumIndexes += computeIndexOfCoincidence(subCypher);
        }
        return sumIndexes / subCyphers.size();
    }

    private float computeIndexOfCoincidence(String s) {
        final Map<Character, Float> frequencies = computeFrequencies(s);
        float ic = 0;
        float n = s.length();
        for (Float nq : frequencies.values()) {
            ic += (nq * (nq - 1)) / (n * (n - 1));
        }
        return ic;
    }

    private Map<Character, Float> computeFrequencies(String s) {
        final Map<Character, Float> frequencies = new HashMap<Character, Float>() {{
            for (char c = 'A'; c <= 'Z'; c++) {
                put(c, 0f);
            }
        }};
        for (char c : s.toCharArray()) {
            if ('A' <= c && c <= 'Z') {
                frequencies.put(c, frequencies.get(c) + 1);
            }
        }
        return frequencies;
    }

    private Character mostFrequent(Map<Character, Float> frequencies) {
        float maxFrequency = Float.MIN_VALUE;
        Character out = null;
        for (Map.Entry<Character, Float> entry : frequencies.entrySet()) {
            if (entry.getValue() > maxFrequency) {
                out = entry.getKey();
                maxFrequency = entry.getValue();
            }
        }
        return out;
    }

    private Character toLetter(int i) {
        return ALPHABET[i % ALPHABET_SIZE];
    }

    private String unCaesar(String subCypher, Character key) {
        StringBuilder sb = new StringBuilder();
        for (char c : subCypher.toCharArray()) {
            // On ajoute ALPHABET_SIZE pour éviter de se prendre le chou avec les nombres négatifs
            sb.append(toLetter(c - key + ALPHABET_SIZE));
        }
        return sb.toString();
    }

    private String concatenate(List<String> subUnCyphered, int length) {
        char[] out = new char[length];
        int steps = subUnCyphered.size();
        for (int step = 0; step < steps; step++) {
            char[] chars = subUnCyphered.get(step).toCharArray();
            for (int i = 0; i < chars.length; i++) {
                out[i * steps + step] = chars[i];
            }
        }
        return new String(out);
    }
}

Bon, que peut-on en dire :

1. Il n'y a aucun contrôle d'entrée : on donne de la merde au programme, il plante. En même temps, j'ai grave la flemme de m'occuper de ça.
2. La combine avec le seuil de l'index de coïncidence fonctionne, elle permet de trouver des clés arbitrairement longues, mais :
   • S'il est trop bas, le programme peut s'arrêter sur une mauvaise clé.
   • S'il est trop haut, le programme ne trouvera jamais la clé.
   • Une solution serait de limiter la boucle à une longueur « raisonnable » (quelques pourcents de la longueur du message) et de prendre la valeur d'index de coïncidence la plus élevée.
   • Une autre solution serait sans doute de calculer toutes longueurs, et de tenter la plus proche de la fréquence théorique. Sur un texte de cette longueur, ce programme fait ça en moins de 2 secondes.
   • On pourrait aussi prendre plusieurs valeurs crédibles et faire des essais avec un dictionnaire.
3. C'est clairement pas optimisé, que ce soit en temps CPU, en mémoire ou en lisibilité. Mais ça fait le job dans un temps raisonnable (instantané sur l'exemple), donc bon…
4. Le programme ne donne pas la clé de décodage. Parce qu'on s'en fout en fait, on en a jamais besoin. On peut la récupérer en concaténant les différentes keyLetter ligne 36.

Quant au reste je n'ai pas testé les cas aux limites, mais ça devrait faire le boulot, modulo les points ci-dessus.

Je pense que le code reste clair, s'il ne l'est pas, n'hésitez pas à poser des questions !

La question niveau expert

En fait c'est une question piège. En considérant qu'on a une clé de la longueur du texte :

1. La clé n'est jamais réutilisée (un seul message chiffré avec cette clé). On se retrouve dans le cas du chiffre de Vernam, aussi appelé « Masque jetable », et qui est mathématiquement sûr… tant qu'on arrive à respecter les moult conditions d'utilisations.
2. Soit on a plusieurs messages chiffrés par la même clé. On a alors diverses solutions pour retrouver la clé et donc le message d'origine, détaillées dans les articles ci-dessus.

PS : je note que mon code est plus court que celui en Python proposé ci-dessus

Pour l'étape 2 (substitution simple), voici une solution inspirée par ce papier.

La méthode s'apparente à un recuit simulé, les solutions ne sont donc pas forcément les mêmes à chaque fois, et le texte décrypté n'est généralement pas parfait (mais il est possible de finir manuellement).

Mon code (j'ai pris "les misérables" comme corpus d'apprentissage) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

import random
from string import ascii_uppercase as charset
from collections import defaultdict, Counter
from math import fsum, log, exp
import unicodedata


msg = "IMGPB MUMBB RRIRG APBMB SGRIR ONHAP PMGQR RQDMS IAQRB SAQLM AEBRD RGQQM ABBMG QIRPR PJHAG QRPUM OABBM GQRPS GJMPP MVRMP MBSDA RNRMQ NMURN PBRLR SABBM VRDHN QRBIS GVNMG ISJMP IMGPB RPJNH LHGIR SNPIR BMUMB BRRHS BMBSD ARNRG RJMNU ARGQJ MPPRD RSURG QIRPL HNDRP KSAGR PHGQJ MPIRP QAGRR PMRQN RUSRP LHAPH GGMGQ RBMUR VRQMQ AHGNR OHSUN ROCMK SRURN PMGQH SBMUA VGRUA RNVRD MBRLA KSRRQ BRPJB MGQRP VNADJ MGQRP NMDJR GQJMN DABRP JARNN RPIRP JMBMA PRGNS AGRPR GBMOM GQRQN HAQRD RGQIR POHBH GGRPE NAPRR PRQIR QNMGV RPDHG HBAQC RPPHS BRUMG QBRPI MBBRP IRDMN ENRJH PRRPJ MNIRP DMAGP HSEBA RRPRQ IMGPB RPMNE NRPKS AJHSP PRGQV AVMGQ RPKSR PIMGP IRPOH SNPIR BMENR RPEHG IAPPR GQIRJ RQAQP PAGVR PQMGI APKSM BBMGQ RQURG MGQJM NBRPO NYJQR PJNHL HGIRP PRGQH NQABB RGQIR PPRNJ RGQPU RGADR SXRQI RPRQN RPPKS MDRSX PMGPG HDADD RGPRP PHGQB RPJAR NNRPK SAIHN DRGQP HSPBR POHSU NRBAQ PIRDH SPPRL NHAIR RQCSD AIRRQ JSAPP MGQPP HGQBR PDSNP IHGQR BBRPP HGQQH DERRP JHSNB RQRNG AQRBR SNPEM QAPPR SNPBR PMUMA RGQRN AVRPR QMBMU RNAQR ABPPR NURGQ RGOHN RGHEB RDRGQ OMNOR PQMSI RPPHS PIRSX KSRBR ONMJM SIVNA PMLMA QPMIR DRSNR QHSQM SLHGI IRBMU MBBRR PRQNH SURBM NAUAR NRQCH DIHGQ BRPRM SXPHG QUAPK SRSPR PRQNR DJBAR PIRLR SABBR PIRPH SNORP OMOCR RPRBB RFMAB BAQRQ URNPI RPVNH QQRPP HSQRN NMAGR PRBBR PROHS BRPAE ARGKS RBRIR DHGIR BMUMB BRRGR PMAQJ MPJHS NKSHA PRPRM SXPHG QNHSV RPGAM KSRBP BARSX RBBRP PHGQB ARRPB RVRGA RKSAC MGQRB RPNMY HGPIR BMBSG RJMNB MMSIR DHGIR BMUMB BRRIA PMGQF RPSAP UARSX RQQNR PHSEB ARSXI APDHA BRPMO QRPBM JJMNR GORRQ BRGHD IRORS XKSAH GQOHG PQNSA QORPO CHPRP IRJAR NNRRQ BRIRD HGNRJ HGIAQ FRPSA PDRDH ANRRQ FRPSA PURNP RIMGP BRPQN MIAQA HGPIS JMPPR DMAPD HAMSP PAFRP SAPUA RSXOR PRQNR PRQMA RGQOH DDRBR PRMSX IRBMN AUARN RQCHD HGGRJ HSUMA QBRPO HDJNR GINRI RBRSN PMOQR PFRGR DRPHS UARGP JMPOM NABPG RXAPQ RNRGQ KSRIM GPBAG PQMGQ IRBRS NMJJM NRGOR FRDRP HSUAR GPUMV SRDRG QRBBR RQMAQ JMNRA BBRMO RBBRI RPJRQ AQPPA GVRPI MGPBR PMNEN RPIRB RSNGH DFRDR PHSUA RGPOB MANRD RGQOM NABNA DRMUR OORBS AIRBM NAUAR NRORP RQNRP ICARN PMJJR BMARG QCHDD RMBHN PBRVR GARPR GUHBM IRGHS URMSU RNPBR DAGOR ONHAP PMGQI RBMBS GRRQB RIRDH GNRVM NIMMQ QRGQA URDRG QSGJR QAQPA GVRIM GPSGM NENRK SAJHS PPMAQ IMGPS GROHS NIRBM ENRR"
s = msg.replace(' ', '')

with open('les-miserables', 'r', encoding='utf8') as fp:
    txt = fp.read()

txt = unicodedata.normalize('NFKD', txt).upper()
#.encode('ASCII', 'ignore').decode()

counter = Counter((txt[i], txt[i+1]) for i in range(len(txt) - 1))
counter = {(a,b): v for (a, b), v in counter.items() if a in charset and b in charset}

X = defaultdict(dict)
for (a,b), v in counter.items():
    X[a][b] = v

M = defaultdict(lambda: 1e-8)
for a, d in X.items():
    total = sum(d.values())
    for b, v in d.items():
        M[a,b] = float(v) / total

def make_code():
    cipher = list(charset)
    random.shuffle(cipher)
    return dict(zip(charset, cipher))

def decode(s, code):
    return ''.join(code.get(c, c) for c in s)

def plausibility(f, s):
    s2 = decode(s, f)
    return fsum(log(M[s2[i], s2[i+1]]) for i in range(len(s2)-1))

def transform(f):
    _f = f.copy()
    (k1, v1), (k2, v2) = random.sample(_f.items(), 2)
    _f[k1] = v2
    _f[k2] = v1
    return _f


if __name__ == '__main__':
    f = make_code()
    pl = plausibility(f, s)
    i = 0
    while True:
        _f = transform(f)
        _pl = plausibility(_f, s)
        if _pl > pl or random.random() < exp(_pl - pl):
            f, pl = _f, _pl
        if i % 250 == 0:
            print(pl, _pl)
            print(i, decode(s, f))
            inp = input('continuer ?')
            if inp and inp[0].upper() != 'Y':
                break
        i += 1

Le texte décrypté :

Salut,

Une petite version en C pour l'étape 1.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210

#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <locale.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <wchar.h>
#include <wctype.h>

#define NORM_KEEP_SPACE   1
#define NORM_LOWER    2

static void chomp(wchar_t *);
static void ws_replace_special(wchar_t *);
static int cesar(char *, unsigned);
static char *normalize(wchar_t *, int, unsigned);


static void
chomp(wchar_t *ws)
{
  while (*ws != L'\n' && *ws != L'\0')
      ++ws;

  *ws = L'\0';
}


static void
ws_replace_special(wchar_t *ws)
{
  size_t i;

  for (i = 0; ws[i] != L'\0'; ++i) {
      switch (ws[i]) {
      case L'à':
      case L'â':
      case L'À':
          ws[i] = 'a';
          break;
      case L'é':
      case L'ê':
      case L'è':
      case L'ë':
      case L'É':
      case L'Ê':
      case L'È':
          ws[i] = 'e';
          break;
      case L'î':
      case L'ï':
          ws[i] = 'i';
          break;
      case L'ô':
          ws[i] = 'o';
          break;
      case L'û':
      case L'ù':
          ws[i] = 'u';
          break;
      case L'ç':
      case L'Ç':
          ws[i] = 'c';
          break;
      default:
          if (iswpunct(ws[i]))
              ws[i] = L' ';
          break;
      }
  }
}


static int
cesar(char *s, unsigned n)
{
  static char lo[] = "abcdefghijklmnopqrstuvwxyz";
  static char up[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  char *ch;

  assert(s != NULL);

  if (islower(*s))
      ch = lo;
  else
      ch = up;

  for (; *s != '\0'; ++s) {
      char *t;

      if (*s == ' ')
          continue;

      t = strchr(ch, *s);

      if (t == NULL) {
          fprintf(stderr, "Mauvais format d'entrée (%c)\n", *s);
          return -1;
      }

      *s = ch[((unsigned)(t - ch) + n) % sizeof lo];
  }

  return 0;
}


static char *
normalize(wchar_t *ws, int mode, unsigned word_size)
{
  char *ret;
  char *dst;
  wchar_t *src;
  size_t len;
  size_t i;

  assert(ws != NULL);
  ws_replace_special(ws);
  len = wcslen(ws);

  if (!(mode & NORM_KEEP_SPACE)) {
      assert(word_size != 0);
      ret = malloc(len + (len / word_size + 1) + 1);
  } else
      ret = malloc(len + 1);

  if (ret == NULL) {
      fprintf(stderr, "malloc: %s\n", strerror(errno));
      return NULL;
  }

  dst = ret;
  src = ws;
  i = 0;

  while (*src != L'\0') {
      if (mode & NORM_KEEP_SPACE) {
          if (*src == L' ' && *(src + 1) == L' ') {
              ++src;
              continue;
          }
      } else if (*src == L' ') {
          ++src;
          continue;
      } else if (i == word_size) {
          *dst++ = ' ';
          i = 0;
          continue;
      }

      if (mode & NORM_LOWER)
          *dst++ = tolower(*src++);
      else
          *dst++ = toupper(*src++);

      ++i;    
  }

  *dst = '\0';
  return ret;
}


int
main(void)
{
  char *s;
  wchar_t ws[255];
  unsigned n;
  int ret = EXIT_FAILURE;

  setlocale(LC_CTYPE, "");

  wprintf(L"Veuillez entrer une phrase à chiffrer : ");
  fflush(stdin);

  if (fgetws(ws, 255, stdin) == NULL) {
      fprintf(stderr, "fgetws: %s\n", strerror(errno));
      goto end;
  }

  chomp(ws);
  s = normalize(ws, 0, 5);

  if (s == NULL) {
      fprintf(stderr, "Impossible de normaliser le texte\n");
      goto end;
  }

  wprintf(L"Veuillez entrer le décalage à appliquer : ");
  fflush(stdin);

  if (wscanf(L"%u", &n) != 1) {
      fprintf(stderr, "Veuillez entrer un nombre\n");
      goto free_s;
  }

  if (cesar(s, n) != 0) {
      fprintf(stderr, "Impossible de chiffrer la phrase entrée\n");
      goto free_s;
  }

  wprintf(L"%s\n", s);
  ret = EXIT_SUCCESS;
free_s:
  free(s);
end:
  return ret;
}

Bon je me suis un peu amusé aujourd'hui à faire l'étape 0 et 1.

Pas de difficulté particulière pour l'étape 0 (que j'ai fait plus sérieusement que les autres à ce que je vois, j'aime perdre mon temps…)

Du coup j'ai fait tout un bidule avec un découpage en plusieurs classes, possibilité de charger un fichier de de phrases à crypter, gestion d'un fichier de langue pour l'affichage etc etc… je me suis senti un peu tout con en voyant que tout le monde s'était concentré sur la partie algo. Déformation professionnel je pense. Je vais donc pas le copier coller ici, il est un peu trop long.

Ensuite pour déchiffrer un code crypté en césar, j'ai fait une analyse de fréquence par lettre et une analyse de fréquence par digrammes (j'ai récupéré les fréquences ici : wiki : analyse fréquentielle

Pour chaque décalage du message d'origine, je génère les tableaux de fréquence de lettre et de digramme, et à la fin je calcule le classement pour chaque analyse. Le gagnant sera le décalage dont la somme des classements est la plus faible. Pour mon algo, je dois forcer un pré-traitement du texte :

• suppression des espace et des caractères spéciaux

• tout en minuscule

Sinon ça fonctionne pas

Pour mon programme je propose un traitement à la main (on donne le texte à décrypter et on choisit le paramétrage de pré-traitement), ce qui, pour l'exemple du sujet, donne la sortie console suivante:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

|----------------------------------------|
|------------CHOIX D'EXECUTION-----------|
|----------------------------------------|
- A la main : 0
- Automatique : 1
0
|----------------------------------------|
|---------EXECUTION MANUELLE-------------|
|----------------------------------------|
Entrer la phrase à déchiffrer :
SYKMA OTTGB GOZPG SGOYK AJKHU TNKAX GBKIY KYINB XKYOR RKYVK XJGOZ ZUAZK YJKRG SS
KLG UTATH KGASG ZOTKR RKYIG YYGOK TZRKA XIUXJ KYKTG RRGOK TZJGT YRGSU TZGMT KKZR
N GAZRK RUAVR KYSGT MKGOZ TORKY IGXKY YKYJK RKAXS GZXKT ORGVK AXJAR UAVXO KTTKR
KYXKZ KTGOZ IZ
|----------------------------------------|
|---------------PARAMETRAGE--------------|
|----------------------------------------|
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Suppression des espaces : 2
- Suppression de la ponctuation : 3
- Gestion de la casse : 4
- Recouper le message : 5
2
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Suppression de la ponctuation : 3
- Gestion de la casse : 4
- Recouper le message : 5
3
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Gestion de la casse : 4
- Recouper le message : 5
4
Choisissez un paramétrage à appliquer
- Fin du paramétrage : 1
- Recouper le message : 5
1
Entrer votre choix pour la casse :
- sortie du message en majuscule : 0
- sortie du message en minuscule : 1
1

|----------------------------------------|
|-------RESULTAT POST TRAITEMENT---------|
|----------------------------------------|
Votre phrase :
SYKMA OTTGB GOZPG SGOYK AJKHU TNKAX GBKIY KYINB XKYOR RKYVK XJGOZ ZUAZK YJKRG SS
KLG UTATH KGASG ZOTKR RKYIG YYGOK TZRKA XIUXJ KYKTG RRGOK TZJGT YRGSU TZGMT KKZR
N GAZRK RUAVR KYSGT MKGOZ TORKY IGXKY YKYJK RKAXS GZXKT ORGVK AXJAR UAVXO KTTKR
KYXKZ KTGOZ IZ
Avec les paramètrages suivants:
1 - Suppression des espaces
2 - Suppression de la ponctuation
3 - Gestion de la casse
Donne le résultat post traitement suivant :
sykmaottgbgozpgsgoykajkhutnkaxgbkiykyinbxkyorrkyvkxjgozzuazkyjkrgssklgutathkgasg
zotkrrkyigyygoktzrkaxiuxjkyktgrrgoktzjgtyrgsutzgmtkkzrngazrkruavrkysgtmkgoztorky
igxkyykyjkrkaxsgzxktorgvkaxjaruavxokttkrkyxkzktgoziz

|----------------------------------------|
|--------------DECHIFFRAGE---------------|
|----------------------------------------|
Message décrypté :
mseguinnavaitjamaiseudebonheuravecseschvresillesperdaittoutesdelammefaonunbeauma
tinellescassaientleurcordesenallaientdanslamontagneetlhautlelouplesmangeaitniles
caressesdeleurmatrenilapeurduloupriennelesretenaitct
Décalage pour le décryptage:
20
Fin de l'éxécution

Ensuite j'ai fait une partie plus automatique, avec un fichier de phrase en entrée: chaque phrase est chiffrée puis l'algo de déchiffrage tente de retrouver le décalage. Les statistiques de réussite et d'échec s'affichent en sortie.

Du coup j'ai analysé deux fichiers :

• l'un avec la partie "Origine" de la fiche wiki de césar : lien

• l'autre avec une dizaine de phrases sans lettre E.

Résultat pour le 1er fichier:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

|----------------------------------------|
|------------CHOIX D'EXECUTION-----------|
|----------------------------------------|
- A la main : 0
- Automatique : 1
1
|----------------------------------------|
|---------EXECUTION AUTOMATIQUE----------|
|----------------------------------------|
Nombre de ligne : 17
Nombre de succès: 17
Nombre d'échec : 0
Fin de l'éxécution

Et les résultats pour le deuxième fichier:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

|----------------------------------------|
|------------CHOIX D'EXECUTION-----------|
|----------------------------------------|
- A la main : 0
- Automatique : 1
1
|----------------------------------------|
|---------EXECUTION AUTOMATIQUE----------|
|----------------------------------------|
Nombre de ligne : 11
Nombre de succès: 1
Nombre d'échec : 10
Fin de l'éxécution

Donc pour le premier autant ça se passe très bien (la phrase la plus courte doit faire 25 caractères sans espace), autant pour le second c'est la débandade. Bon évidemment des phrases sans E, ça a pas été évident à trouver, et c'est des phrases assez courtes en générale (ça varie de 15 à 90 caractères). C'était vraiment pour tester à fond l'algo et clairement il est pas assez solide.

Il faudrait que je rajoute du coup l'analyse avec un dictionnaire. Si j'ai la motivation je m'attaquerais à ca.

premier script avec python, j'en ai profiter pour test. Je vous prie donc de ne pas m'assassiner si vous voyez une horreur !

étape 0 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# cipher ==> string chiffré
# decipher ==> string déchiffré
# myString ==> string chiffré ou déchiffré


def goToCrypt(myCrypt):
    return "lol"

def etapeZero(deCipher, startPos, pas):
    i = startPos
    z = 0
    tabString = []
    myResult = ''


    deCipher = deCipher.replace(' ', '')
    deCipher = deCipher.replace('ê', 'e')
    deCipher = deCipher.replace("'", '')
    deCipher = deCipher.replace('é', 'e')
    deCipher = deCipher.replace('«', '')
    deCipher = deCipher.replace('»', '')
    deCipher = deCipher.replace(',', '')
    deCipher = deCipher.replace('.', '')

    deCipher = deCipher.upper()




    myLength = len(deCipher)

    print("longueur de chaine", myLength)

    if myLength == 0:
            print('erreur longeur String ==> 0')


    while i < myLength:

        tabString.append(deCipher[i:i + 5])

        myResult += tabString[z]
        myResult += ' '


        i += pas
        z += 1

    return myResult



deCipher = input("Entrez la phrase à chiffrer : ")
cipher = etapeZero(deCipher, 0, 5)
print(cipher)

Étape 1

J'avais un petit peu de temps ce soir, je me suis dit que c'était l'occasion pour participer (enfin) aux défis de Clem'. Voici donc ma version (sans doute pas ultra-optimisée) du décodage du chiffrage César en Python 3, en jouant sur les minuscules et les majuscules pour faciliter le décodage :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

alphabet = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ') #utile pour la suite

#Fonction qui cherche la lettre la plus présente (sans doute E)
def search_e (cryptogram) :
    max = 0
    for letter in alphabet :
        count = cryptogram.count(letter)
        if count > max :
            max = count
            probably_e = letter
    return probably_e

#Fonction de décodage (qui joue sur MAJ/minuscules).
def decode (cryptogram, gap) :
    cryptogram = cryptogram.upper().replace(' ', '')
    translation = cryptogram
    for rank in range(26) :
        new_rank = rank - gap
        if new_rank > 25 :
            new_rank = new_rank - 26
        translation = translation.replace(alphabet[rank], alphabet[new_rank].lower())
    return translation.upper()



cryptogram = input()
probably_e = search_e(cryptogram)

#Cas le plus probable
gap = alphabet.index(probably_e) - 4
print ('\nSi ', probably_e, ' vaut E :')
translation = decode(cryptogram, gap)
print(translation)

#Cas moins probable
gap = alphabet.index(probably_e)
print ('\nSi ', probably_e, ' vaut A :')
translation = decode(cryptogram, gap)
print(translation)

Ce qui donne :

Voici un petit script un Perl (j'utilise le nouveau Perl, Perl 6). Malheureusement, je n'ai pas eu le temps de plus m'amuser avec, il n'est donc absolument pas complet. J'essaierais de l'améliorer/le compléter à l'occasion. Il s'utilise de la sorte :

1

$ script [mode] [indice] [nom du fichier]

Par exemple, pour chiffrer grâce à décalage de 16 lettres le contenu d'un fichier message.txt :

1

$ script enc 16 message.txt

Avec un fichier texte contenant le message suivant, j'obtiens le résultat ci-dessous.

1

Zeste de Savoir, un petit pas pour l'homme, un grand pas pour la connaissance !

1
2

$ perl6 script.p6 enc 16 message.txt
PUIJUTUIQLEYHKDFUJYJFQIFEKHBXECCUKDWHQDTFQIFEKHBQSEDDQYIIQDSU

Bien évidemment, ça fonctionne dans l'autre sens avec le mode pour déchiffrement, dec. Ci-dessous, vous pourrez retrouver mon code. Encore une fois, je compte bien l'améliorer dès que possible.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

use v6;

my @alphabet = 'A' .. 'Z';

multi sub MAIN(Str $mode, Int $n, Str $filename) {
  given $mode {
    when 'enc' {
      my $message = prepare(slurp($filename));
      my $encrypt = encrypt($n, $message);
      say $encrypt;
    }
    when 'dec' {
      my $message = slurp($filename);
      my $decrypt = decrypt($n, $message);
      say $decrypt;
    }
    default {
      die 'Invalid !';
    }
  }
}

multi sub prepare(Str $message) {
  return $message.subst(/<-:L>+/,'',:g).uc;
}

multi sub encrypt($key where 1..25, $message) {
  $message.trans(@alphabet Z=> @alphabet.rotate($key));
}

multi sub decrypt($key where 1..25, $message) {
  $message.trans(@alphabet.rotate($key) Z=> @alphabet);
}

Le code est ultra basqiue. Les erreurs ne sont absolument pas gérées : par exemple, si l'indice de décalage \$n est supérieur à 25, ça plante. Si le nom du fichier \$filename est incorrect, ça plante. Bref, plein d'améliorations à apporter !

J'ai fini d'implémenter l'étape 1 en C++, l'étape 0 n'est pas fonctionnel, mais je pense quand même continuer sur l'étape 2. Le code est sur github avec un CMakeLists si certains veulent l'essayer

Voici mon code en Objective-c

Etape 0:

1
2
3
4
5
6

#import <Foundation/Foundation.h>

@interface NSString (Crypt)
- (NSString *)prepareCrypt;

@end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#import "NSString+Crypt.h"

@implementation NSString (Crypt)
- (NSString *)prepareCrypt{
    NSString *res;
    //Enlève les accentes et autres conneries
    res = [[self componentsSeparatedByCharactersInSet:[[NSCharacterSet letterCharacterSet] invertedSet]] componentsJoinedByString:@""];
    //Met en masjuscule
    res = [res uppercaseString];
    
    //Enlève les espaces
    res = [res stringByReplacingOccurrencesOfString:@" " withString:@""];
    
    NSMutableString *mutableString = [res mutableCopy];
    
    for (int i = 0; i < mutableString.length; i++){
        if (i % 6 == 0 && i > 0){
            [mutableString insertString:@" " atIndex:i];
        }
    }
    
    return [mutableString copy];
    
}
@end

Etape 1:

1
2
3
4
5
6

import <Foundation/Foundation.h>

@interface CorrectTextFrench : NSObject
- (BOOL)correctTextFrench:(NSString *)text;
- (int)frequencesOfNSString:(NSString *)c in:(NSString *)s;
@end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#import "CorrectTextFrench.h"

@implementation CorrectTextFrench
- (BOOL)correctTextFrench:(NSString *)text{
    text = [text lowercaseString];
    
    NSString *bestCharFrequences;
    int bestFrequences = 0;
    int currentFrequent = 0;
    
    for (int i = 0; i < 26; i++){
        NSString *search = [NSString stringWithFormat:@"%c", 97 + i];
        currentFrequent = [self frequencesOfNSString:search in:text];
        
        if (currentFrequent > bestFrequences){
            bestCharFrequences = search;
            bestFrequences = currentFrequent;
        }
    }
    
    if ([bestCharFrequences isEqualToString:@"e"] || [bestCharFrequences isEqualToString:@"s"] || [bestCharFrequences isEqualToString:@"a"]){
        return YES;
    }else{
        return NO;
    }
     

}

- (int)frequencesOfNSString:(NSString *)c in:(NSString *)s{
    int f = 0;
    for (int i = 0; i < s.length; i++){
        if ([[NSString stringWithFormat:@"%c", [s characterAtIndex:i]] isEqualToString:c]){
            f++;
        }
    }
    return f;
}
@end

1
2
3
4
5
6
7
8

#import <Foundation/Foundation.h>
#import "NSString+Crypt.h"
#import "CorrectTextFrench.h"
@interface CaesarCrypt : NSObject
- (NSString *)cryptString:(NSString *)text withRotation:(int)r;
- (NSString *)decryptString:(NSString *)decrypt withRotation:(int)r;
- (NSArray *)decryptString:(NSString *)decryptText;
@end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#import "CaesarCrypt.h"

@implementation CaesarCrypt
- (NSString *)cryptString:(NSString *)text withRotation:(int)r{
    text = [text prepareCrypt];
    
    const char *utf8 = [text cStringUsingEncoding:NSUTF8StringEncoding];
    size_t len = strlen(utf8) + 1;
    
    char t[len];
    memcpy(t, utf8, len);
    
    for (int i = 0; i  < text.length; i++){
        if (t[i] == ' '){
            continue;
        }
        if ((t[i] + r) > 'Z'){
            t[i] = 64 + ((t[i] + r) - 'Z');
        }else if ((t[i] + r) < 'A'){
            t[i] = 91 - ('A' - (t[i] + r));
        }else{
           t[i] += r;
        }
        
    }
    
    return [NSString stringWithFormat:@"%s", t];
}

- (NSString *)decryptString:(NSString *)decrypt withRotation:(int)r{
    return [self cryptString:decrypt withRotation:r];
}
- (NSArray *)decryptString:(NSString *)decryptText{
    CorrectTextFrench *c = [[CorrectTextFrench alloc] init];
    NSMutableArray *pos = [NSMutableArray array];
    for (int i = 0; i <= 25; i++){
        NSString *string = [self cryptString:decryptText withRotation:i];
        if ([c correctTextFrench:string]){
            [pos addObject:[self cryptString:decryptText withRotation:i]];
        }
        
    }
    
    return [pos copy];
}
@end

Et pour le test :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

    NSString *s = @"J'aimes les poules";
    CaesarCrypt *crytp = [[CaesarCrypt alloc] init];
    NSString *sd = [crytp cryptString:s withRotation:8];
    NSArray *p = [crytp decryptString:sd];
    NSLog(@"Crypt : %@", sd); // RIQUMA TMAXW CTMA
    NSLog(@"Decrypt : %@", [crytp decryptString:sd withRotation:-8]); //JAIMES LESPO ULES
    NSLog(@"Decrypt sans clé : %@", p); //"RIQUMA TMAXW CTMA"
                                        //"VMUYQE XQEBA GXQE"
                                        //"FWEIAO HAOLK QHAO"
                                        //"JAIMES LESPO ULES" <-- C'est le bon message ;)