Cryptographie

Introduction

Un texte est une suite de symboles (ou caractères) pris dans un alphabet de taille finie $N$. Chiffrer ce texte consiste à lui appliquer une transformation de façon à produire un autre texte, le texte chiffré. Déchiffrer le texte chiffré signifie appliquer la transformation inverse de façon à retrouver le texte en clair. Le texte qui est produit par l'algorithme de chiffrement dépend d'une donnée supplémentaire que l'on appelle la clé. L'algorithme de déchiffrement utilise également cette clé. Seuls ceux qui possèdent la clé peuvent a priori retrouver le texte en clair. Si la méthode de chiffrement n'est pas suffisamment robuste, il peut cependant être possible de décrypter le texte chiffré et retrouver ainsi le texte en clair sans connaître la clé par avance.

L'objet du TP est de programmer tout d'abord l'algorithme de chiffrement monoalphabétique. C'est un algorithme qui est très facile à casser en analysant la fréquence des symboles apparaissant dans le texte chiffré. Dans un deuxième temps vous programmerez l'algorithme de Vigenère qui permet a priori de se prémunir de l'attaque précédente. Nous verrons toutefois en fin de TP une méthode qui permet de le casser lui aussi.

Partie A — Chiffrement monoalphabétique

Les algorithmes de chiffrement/déchiffrement ne s'appliquent pas directement sur les caractères mais sur des nombres entiers. La norme Unicode a répertorié l'ensemble des caractères utilisés dans les diverses langues écrites actuelles. Chacun de ces symboles est identifié par un entier appelé point de code Unicode compris entre 0 et 0x110000.

Remarque : Le préfixe 0x signifie que l'entier est écrit en base 0x10, c'est-à-dire en base 16.

In [ ]:
0x2A
Out[ ]:
42
In [ ]:
0x110000
Out[ ]:
1114112

Les fonctions python chr et ord permettent d'obtenir le caractère à partir du point de code et réciproquement :

In [ ]:
print(chr(233))
print(ord('é'))
é
233

Nous allons appliquer nos algorithmes sur ces points de code en nous restreignant aux caractères dont le point de code est compris entre 0 et $N-1$ avec $N=$ 0x800.

In [ ]:
N = 0x800
print([chr(code) for code in range(N)])

Remarque : Les polices de ces caractères ne sont pas toutes présentes sur la machine. Dans ce cas, le caractère est représenté par un carré.

Le chiffrement monoalphabétique consiste à choisir une permutation sur l'ensemble des entiers entre 0 et $N-1$ et à appliquer cette permutation à chacun des symboles du texte en clair. La permutation inverse permet de retrouver le message d'origine.

Remarque sur les valeurs python de type function

En Python les fonctions sont des valeurs comme les autres (entiers, liste, etc.). Les valeurs de type function sont le plus souvent construites avec le mot-clé def.

Le mot-clé lambda permet de créer une valeur de type fonction sans nécessairement stocker cette valeur sous un nom :

In [ ]:
lambda x: (x + 1) % 20
Out[ ]:
<function __main__.<lambda>>

L'opération principale que l'on peut effectuer sur une valeur de type function est de la calculer sur une valeur donnée :

In [ ]:
(lambda x: (x + 1) % 20)(26)
Out[ ]:
7

Comme n'importe qu'elle type de valeurs, une valeur de type function peut être passée en argument d'une autre fonction :

In [ ]:
def apply(f, L):
    return [f(x) for x in L]

apply(lambda x: (x + 1) % 20, [3, 11, 18, 26, 42])
Out[ ]:
[4, 12, 19, 7, 3]

Question 1

Coder la fonction monoalphabetic_cipher.

  • Vous pouvez par exemple implémenter l'algorithme suivant :
algorithm
Fonction monoalphabetic_cipher(clear_text, permutation)
    Créer une liste vide ciphered_symbols
    Pour chaque clear_symbol de clear_text faire
        ciphered_symbol ⟵ chiffré de clear_symbol
        Ajouter ciphered_symbol à la liste ciphered_symbols
    finPour
    ciphered_text ⟵ concaténation des symboles
                      de la liste ciphered_symbols
    Retourner ciphered_text
  • Le second argument de la fonction monoalphabetic_cipher est lui-même une fonction qui prend comme argument un entier entre 0 et $N-1$ et qui retourne un entier entre 0 et $N-1$.

    Pour la concaténation, servez-vous de la méthode str.join. Évaluez l'instruction ''.join(['a', 'b', 'c']) pour comprendre l'effet de cette méthode.

In [ ]:
def monoalphabetic_cipher(clear_text, permutation):
    """ Chiffre le texte `clear_text` en appliquant la fonction
        `permutation` au code de chaque symbole .
    """
    ### À COMPLÉTER
    
monoalphabetic_cipher("La prépa est un long fleuve tranquille",
                      lambda x: (x + 1) % N)

Le chiffrement affine est une version particulière du chiffrement monoalphabétique. Il consiste à appliquer la transformation affine $x\longrightarrow (ax+b) \bmod N$ sur les codes des symboles du texte à chiffrer. Il est nécessaire de choisir $a$ premier avec $N$ pour garantir que la transformation soit bien bijective. La transformation réciproque est alors elle-même une transformation affine.

Question 2

Coder la fonction affine_cipher.

Puisque affine_cipher est un cas particulier, servez-vous de la fonction générale monoalphabetic_cipher.

In [ ]:
def affine_cipher(clear_text, a, b):
    """ Chiffre le texte `clear_text` par le chiffrement affine
        x -> ax + b mod N.
    """
    ### À COMPLÉTER
In [ ]:
print([ord(symbol) 
       for symbol in "La prépa est un long fleuve tranquille"])
[76, 97, 32, 112, 114, 233, 112, 97, 32, 101, 115, 116, 32, 117, 110, 32, 108, 111, 110, 103, 32, 102, 108, 101, 117, 118, 101, 32, 116, 114, 97, 110, 113, 117, 105, 108, 108, 101]
In [ ]:
affine_cipher("La prépa est un long fleuve tranquille", 3, 1)
Out[ ]:
'åĤaőŗʼőĤaİŚŝaŠŋaŅŎŋĶaijŅİŠţİaŝŗĤŋŔŠļŅŅİ'
In [ ]:
print([ord(symbol) 
       for symbol in "åĤaőŗʼőĤaİŚŝaŠŋaŅŎŋĶaijŅİŠţİaŝŗĤŋŔŠļŅŅİ"])
[229, 292, 97, 337, 343, 700, 337, 292, 97, 304, 346, 349, 97, 352, 331, 97, 325, 334, 331, 310, 97, 307, 325, 304, 352, 355, 304, 97, 349, 343, 292, 331, 340, 352, 316, 325, 325, 304]

Pour retrouver le texte original à partir du texte chiffré il suffit d'appliquer l'algorithme avec la permutation réciproque. Mais, quelle est la permutation réciproque de $x\longrightarrow (ax+b) \bmod N$ ?

Si $a$ est premier avec $N$, le théorème de Bézout nous dit qu'il existe deux entiers $a'$ et $v$ tels que $aa' + vN = 1$, autrement dit tels que $aa' \equiv 1 \bmod N$. On dit que $a$ et $a'$ sont inverses modulo $N$.

Trouver la permutation réciproque de $x\longrightarrow (ax+b) \bmod N$ consiste à résoudre par rapport à $x$ l'équation $y\equiv ax+b \bmod N$.

Question 3

On note $a'$ l'inverse de $a$ modulo $N$.

Quelle est la permutation réciproque de $x\longrightarrow (ax+b) \bmod N$ ?

Le calcul de la permutation réciproque nécessite donc de calculer un inverse modulo $N$. On peut utiliser pour cela l'algorithme d'Euclide étendu. Cet algorithme permet d'obtenir le pgcd de deux entiers $a$ et $b$, ainsi que les coefficients de Bézout $u$ et $v$ tels que

$$au+bv=\mbox{pgcd}(a, b).$$
In [ ]:
def euclide(a, b):
    """ Algorithme d'Euclide étendu
        Retourne le pgcd de `a` et `b`, ainsi que les coefficients de
        Bézout `u` et ` v` tels que au + bv = pgcd(a, b).
    """
    r0, u0, v0, r1, u1, v1 = a, 1, 0, b, 0, 1
    while r1 != 0:
        q = r0 // r1
        r0, u0, v0, r1, u1, v1 = (
        r1, u1, v1, r0 - q * r1, u0 - q * u1, v0 - q * v1)
    return r0, u0, v0

gcd, u, v = euclide(120, 23)
print(gcd, u, v)
120 * u + 23 * v
1 -9 47
Out[ ]:
1

Question 4

Coder la fonction inv_mod(x, n).

Utilisez pour cela la fonction euclide.

In [ ]:
def inv_mod(x, n):
    """ Retourne l'inverse de `x` modulo `n`.
    
        Rappel : `x` possède un inverse modulo `n` ssi
        `x` et `n` sont premiers entre eux.
    """
    ### À COMPLÉTER
In [ ]:
inv_mod(3, N)
Out[ ]:
683

Question 5

Coder la fonction affine_decipher.

In [ ]:
def affine_decipher(ciphered_text, a, b):
    """ Déchiffre le texte `ciphered_text` chiffré par chiffrement
        affine x -> ax + b mod N.
    """
    ### À COMPLÉTER
In [ ]:
affine_decipher("åĤaőŗʼőĤaİŚŝaŠŋaŅŎŋĶaijŅİŠţİaŝŗĤŋŔŠļŅŅİ", 3, 1)
Out[ ]:
'La prépa est un long fleuve tranquille'

Question 6

Le texte du fichier ciphered-1.txt a été obtenu par chiffrement affine. La clé est $(a, b) = (11, 8)$. Déchiffrer ce message et le sauvegarder sous le nom clear-1.txt.

Le fichier ciphered-1.txt est un fichier de texte : il contient une chaîne de caractères unicode encodée en utf-8. Cependant le caractère saut de ligne a été lui-même transformé en un autre caractère par l'algorithme de chiffrement. Cela n'a donc plus guère de sens de lire le fichier ciphered ligne par ligne. Pour cette raison, vous utiliserez la fonction fd.read() pour lire l'ensemble du texte et le stocker dans une unique chaîne de caractères python. Ceci ne pose pas de problème ici car il s'agit d'un petit fichier. Pour un très gros fichier, il faudrait le lire et le traiter par blocs, de 1024 caractères par exemple, en écrivant fd.read(1024).

In [ ]:
 

Partie B — Décryptage par analyse fréquentielle

Dans un texte en français les symboles ne sont pas distribués de façon uniforme. Parmi toutes les lettres le 'e' est a priori très majoritaire. Le caractère ESPACE est également très fréquent. Ces fréquences se retrouvent dans le message chiffré et ceci peut être utilisé pour décrypter le texte.

Question 7

Coder la fonction frequencies.

Créez une liste de taille $N$ initialisée avec des 0, puis mettez à jour cette liste en lisant un à un les symboles du texte. Retournez cette liste.

In [ ]:
def frequencies(text):
    """ Retourne une liste donnant le nombre d'occurrences dans `text`
        de chaque symbole de l'alphabet.
    """
    ### À COMPLÉTER
In [ ]:
freq = frequencies("La prépa est un long fleuve tranquille")
freq[ord('e')]
Out[ ]:
4

Dans la suite du TP nous allons utiliser la bibliothèque matplotlib. Pour cela exécuter la commande magique IPython suivante :

In [ ]:
%pylab inline
Populating the interactive namespace from numpy and matplotlib

Cette commande a exécutée pour nous :

import numpy as np
import matplotlib.pyplot as plt

Elle a également configurée matplotlib pour que les graphiques s'affichent dans le navigateur.

Question 8

Représenter les fréquences des symboles du texte clear-1.txt sous la forme d'un diagramme en bâtons. Faites de même pour le texte chiffré ciphered-1.txt.

Utilisez pour cela la fonction matplotlib.pyplot.bar.

La fonction plt.xlim permet si nécessaire de définir l'échelle sur l'axe des abscisses.

In [ ]:
 

Question 9

Le texte du fichier ciphered-2.txt a été obtenu par chiffrement affine mais vous ne connaissez pas la clé.

Décryptez ce texte.

Déchiffrer un message signifie appliquer l'algorithme de déchiffrement. Cela suppose donc de connaître la clé.

Décrypter un message signifie retrouver le texte en clair sans avoir connaissance de la clé.

Pour cette question la fonction python sorted pourra vous être utile. Elle permet de trier les éléments d'un itérable selon un certain critère.

In [ ]:
 

Partie C — Chiffrement de Vigenère

L'algorithme de Vigenère est un système de chiffrement polyalphabétique. C'est un chiffrement par substitution, mais, suivant sa position dans le texte en clair, un même symbole peut être remplacé par des symboles différents. Cette méthode résiste ainsi à l'analyse de fréquences, ce qui est un avantage décisif sur les chiffrements monoalphabétiques. Cependant le chiffre de Vigenère a été cassé par le major prussien Friedrich Kasiski qui a publié sa méthode en 1863. Depuis cette époque, il n'offre plus aucune sécurité.

Question 10

Lisez l'article de Wikipedia pour étudier l'algorithme de chiffrement et comprendre pourquoi il résiste à une analyse fréquentielle comme celle que vous avez effectuée précédemment.

Question 11

Coder la fonction vigenere_cipher :

In [ ]:
def vigenere_cipher(clear_text, key):
    """ Chiffre le texte `clear_text` par `chiffrement de Vigenère
        avec la clé `key`.
    """
    ### À COMPLÉTER

Question 12

Coder la fonction vigenere_decipher :

In [ ]:
def vigenere_decipher(ciphered_text, key):
    """ Chiffre le texte `clear_text` par `chiffrement de Vigenère
        avec la clé `key`.
    """
    ### À COMPLÉTER

Question 13

Le texte du fichier ciphered-3.txt a été chiffré par l'algorithme de Vigenère avec la clé : "La prépa est un long fleuve tranquille".

Déchiffrer ce texte.

In [ ]:
 

Question 14

Vérifier que vous retrouvez bien le texte chiffré de ciphered-3.txt à l'aide de votre fonction vigenere_decipher.

In [ ]:
 

Partie D - Cryptanalyse d'un texte chiffré par l'algorithme de Vigenère

L'objectif de cette partie est de décrypter le texte ciphered-4.txt.

La première étape pour décrypter un texte chiffré par l'algorithme de Vigenère consiste à déterminer la longueur de la clé. On recherche pour cela des répétitions de séquence de symboles dans le texte chiffré. L'explication la plus probable de ces répétitions est qu'elles préexistaient déjà dans le texte en clair et qu'elles ont été chiffrées par la même partie de la clé. Dans cette hypothèse la distance séparant les diverses occurrences de ces séquences identiques est un multiple de la longueur de la clé.

Question 15

Coder la fonction positions_occurrences.

Remarque : Par mot on entend ici une suite quelconque de caractères. Ceux-ci ne sont donc pas nécessairemement des mots dans le sens courant.

In [ ]:
def positions_occurrences(ciphered_text, length):
    """ Retourne un dictionnaire qui donne, pour chaque mot de longueur
        `length` qui apparaît dans le texte `ciphered_text`, la liste des
        positions où ce mot apparaît.
    """
    ### À COMPLÉTER

Question 16

Conjecturer la longueur de la clé à partir du dictionnaire retourné par positions_occurrences.

In [ ]:
 

Pour continuer, nous avons besoin de la notion d'indice de coïncidence. La variation de fréquences entre les divers symboles d'un texte peut être mesurée par un indicateur appelé Indice de Coïncidence qui se calcule par la formule suivante :

$$IC = \sum_{q\in\scriptsize\mbox{Texte}}\frac{n_q(n_q - 1)}{n(n - 1)}$$

où $n$ est la longueur du texte et $n_q$ le nombre d'occurrences du symbole $q$ dans le texte.

Vous pouvez vérifier que l'$IC$ est égal à la probabilité d'obtenir deux symboles identiques lorsque l'on choisit au hasard deux symboles du texte. L'$IC$ est minimal lorsque tous les symboles du texte ont le même nombre d'occurrences.

Question 17

Coder la fonction IC :

In [ ]:
def IC(text):
    """ Retourne l'Indice de Coincidence de `text`.
    """
    ### À COMPLÉTER

Question 18

Vérifier que votre fonction IC retourne bien une valeur proche de 1/26 lorque le texte contient 1000 occurrences de chacunes des 26 lettres de l'alphabet.

In [ ]:
 

Soit $T$ un texte et $s$ un entier tel que $0\leq s\lt N$. Soit $\mbox{translate}(T, s)$ le texte que l'on obtient si on effectue une translation de $s \bmod N$ sur chacun des codes des symboles de $T$.

Soit $K$ le texte clé et soit $T_i$ ($0\leq i\lt k$) le texte formé des symboles $T[i]$, $T[i+k]$, $T[i+2k]$, $\dots$, où $T$ est le texte à décrypter et $k$ la longueur de la clé. Nous pouvons remarquer que le texte $T_i$ a été entièrement chiffré à partir du symbole $K[i]$.

Posons $s_i=\mbox{ord}(K[i])−\mbox{ord}(K[0])$. Le nombre $s_i$ est le décalage relatif entre le chiffrement de $T_0$ et celui de $T_i$. L'idée pour retrouver la valeur des $s_i$ est de remarquer que si l'on concatène les deux textes $T_0$ et $\mbox{translate}(T_i, -s)$ alors l'indice de coïncidence du texte concaténé sera vraisemblablement maximal pour $s=s_i$.

Question 19

Écrire la fonction python relative_shift qui implémente l'algorithme suivant :

Fonction relative_shift(T, k, i)
    T0 <-- texte formé des symboles T[0], T[k], T[2k], ...
    Ti <-- texte formé des symboles T[i], T[i+k], T[i+2k], ...
    icmax <-- 0
    shift <-- 0
    Pour s variant de 0 à N-1 faire
        concat_text <-- Concaténation de T0 et de translate(Ti, -s)
        ic <-- IC(concat_text)
        Si ic > icmax alors
            icmax <-- ic
            shift <-- s
        Finsi
    FinPour
    Retourner shift
In [ ]:
def relative_shift(text, k, i):
    """ Retourne le décalage relatif entre les codes du premier symbole
        de la clé (indice 0) et le (i+1)-ième (indice i).
    """
    ### À COMPLÉTER

Question 20

Créer la liste shifts contenant les valeurs de $s_i$ pour $0\leq i\lt k$.

In [ ]:
 

Question 21

Notons ciphered_text le texte à déchiffrer, clear_text le texte original à retrouver et translated_text le texte translate(clear_text, ord(K[0])).

Retrouver le texte translated_text à partir de ciphered_text, de k et de la liste shifts.

In [ ]:
 

Question 22

Retrouver le texte original du fichier ciphered-4.txt.

In [ ]: