Cryptanalyse de chiffres classiques¶

Dans ce TP, on va effectuer des cryptanalyses simples de chiffres historiques. Le but est également de se familiariser avec le langage [Par19] qui servira pour la suite du cours.

Une référence pour la cryptanalyse : l’article de Shannon [Sha49].

Codage modulo 26¶

On pose:

s = "une chaine de caracteres"

convertir s en liste de codes ASCII (utiliser Vec(Vecsmall(s)) sous gp).
solution ⇲ ⇱ solution
l = Vec(Vecsmall(s))
transformer cette liste en liste d’entier modulo 26, en éliminant les codes de caractères non alphabétiques.
solution ⇲ ⇱ solution
alpha(l) = 0 <= l && l < 26; m = select(alpha,vector(#l,k,l[k]-97))

Ecrire une fonction str2vec(s) qui fasse le travail ci-dessus, et la fonction vec2str(v) codant l’opération inverse.

On aura donc:

? str2vec("une chaine")
[20, 13, 4, 2, 7, 0, 8, 13, 4]

? vec2str([20, 13, 4, 2, 7, 0, 8, 13, 4])
"unechaine"

solution ⇲ ⇱ solution

str2vec(s) = {
  s = Vec(Vecsmall(s));
  s = vector(#s, i, s[i]-97);
  s = select(l -> 0 <= l && l < 26, s);
  s;
}

vec2str(v) = Strchr(vector(#v,i,v[i]+97));

Chiffre de Vigenere¶

Ecrire une fonction vigenere(m,k) qui effectue un chiffrement de Vigenere de clef k. Cette fonction prend en argument des listes d’entiers.
solution ⇲ ⇱ solution
vigenere(m,k) = vector(#m,i,(m[i] + k[(i-1) % #k + 1]) % 26);
Ecrire une fonction Vigenere(M,K) qui effectue le chiffrement sur des chaînes de caractères.
solution ⇲ ⇱ solution
Vigenere(m,k) = vec2str(vigenere(str2vec(m),str2vec(k)));
Le texte suivant est un chiffré de Vigenère de clef "haricot", le déchiffrer:
```
zejioshbvimvcb
```
solution ⇲ ⇱ solution
m = vec2str(vigenere(str2vec("zejioshbvimvcb"),-str2vec("haricot")))

Analyse fréquentielle¶

Récupérer et enregistrer ce texte (disponible aussi sur Didel). Pour le lire sous gp on pose:

? s = concat(readstr("texte.txt"))

Pour le lire sous sage on pose:

with open("texte.txt","r") as f:
  s = f.read()
s = ' '.join(s.split('\n'))

On travaille dans l’espace \(\Z/26\Z\).

Ecrire une fonction count(m) qui renvoie le nombre d’occurrences de chaque caractère de m.
Écrire aussi le calcul des fréquences, et rendre un résultat ordonné par fréquence décroissante.
Examiner ces fréquences, quelles sont les cinq lettres les plus utilisées ?

Une cryptanalyse simple¶

On rappelle que l’entropie d’une source dont les symboles apparaissent avec probabilité \(p_i\) vaut

\[H = -\sum p_i\log(p_i)\]

Calculer l’entropie du texte s.
Calculer l’entropie d’un texte aléatoire (probabilité uniforme sur chacune des lettres).
Choisir une clef k de longueur comprise entre 3 et 8 caractères, et chiffrer le texte m par la méthode de Vigenère.
Calculer l’entropie du chiffré c obtenu.

Dans la suite, on va analyser et décrypter ce chiffré. Si possible, échangez votre chiffré avec celui de votre voisin.

Former le message obtenu en prenant un caractère sur deux, et calculer son entropie.
De même, calculer les entropies des sous-messages obtenus en ne prenant que les premières lettres de blocs de longueur l, pour l allant de 1 à 8.
Quelle est la longueur de la clef ?
Quel est le décalage effectué sur la première lettre de chaque bloc ?
Retrouver la clef utilisée pour le chiffrement : à chaque fois, on prendra le décalage le plus probable.
Ecrire une fonction decrypt(c,lmax) qui décrypte automatiquement un chiffre suffisamment long, de longueur de clef inférieure à lmax.

Mesures statistiques¶

Soient \(C\) et \(T\) deux textes, pour lesquels les caractères ont fréquences respectives \(p_i(C)\) et \(p_i(T)\). La mesure «somme des carrés» est un bon indicateur de la proximité fréquentielle entre \(C\) et \(T\).

\[S(C,T) = \sum_i (p_i(C) - p_i(T))^2\]

On l’utilise en particulier dans le cas où \(T\) est un texte de référence.

Ecrire une fonction test_carre(c,t) qui mesure cette quantité.
Faire une cryptanalyse par force brute du chiffré obtenu plus haut, en ne conservant que la clef qui permet d’obtenir le meilleur score.
Quelles tailles de clefs peut-on traiter de cette manière ?

Chiffre de Hill¶

On va réaliser une attaque par mot probable sur le chiffre de Hill.

Définir une matrice \(A\in\Gl_3(\Z/26\Z)\) aléatoire comme suit:
```
until(gcd(matdet(A),26)==1,A=matrix(3,3,i,j,random(26)))
```
Ecrire une fonction hill(m, A) qui effectue le chiffrement de m par A, et calculer le chiffré c obtenu.
Connaissant la clef A, déchiffrer c.

Technique du mot probable¶

Sachant la provenance du texte, on fait l’hypothèse que le message m contient le mot ordinateur, et même que ce mot commence au début d’un bloc. Quelles sont les matrices de chiffrement possibles ?
À l’aide d’un test statistique, retrouver la matrice de chiffrement A.
Généraliser au cas où le mot ne se trouve pas nécessairement en début de bloc.

Analyse d’une attaque par force brute¶

Quel est le cardinal de \(\Gl_2(\Z/26\Z)\) ?
Faire une boucle qui parcourt toutes les matrices \(A\) de \(\Gl_2(\Z/26\Z)\).
Faire une attaque par force brute pour un chiffre de longueur 2. Quel est le temps de calcul ?
Ecrire une formule donnant le cardinal de \(\Gl_l(\Z/26\Z)\). Quel est le temps de calcul estimé pour \(l=3\) ? \(l=4\) ?

Références¶

tot11: Amount of single operations reachable. 2011. URL: https://security.stackexchange.com/questions/6141/amount-of-simple-operations-that-is-safely-out-of-reach-for-all-humanity/6149#6149.
blo18: Online blockchain demo. 2018. URL: https://anders.com/blockchain/blockchain.html.
Par19: PARI/GP version 2.12. Univ. Bordeaux, 2019. URL: http://pari.math.u-bordeaux.fr/.
HVDH20: David Harvey and Joris Van Der Hoeven. Integer multiplication in time O(n log n). Annals of Mathematics, 2020. URL: https://hal.archives-ouvertes.fr/hal-02070778.
LHA+12: Arjen K. Lenstra, James P. Hughes, Maxime Augier, Joppe W. Bos, Thorsten Kleinjung, and Christophe Wachter. Ron was wrong, whit is right. IACR Cryptology ePrint Archive, 2012:64, 2012. URL: https://eprint.iacr.org/2012/064.pdf.
Sha49: C. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, Vol 28, pp. 656–715, October 1949. URL: http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf.