TP 1 - Chiffrements historiques
Afin de simplifier l’implémentation des algorithmes en Python. Seul les caractères alphabétiques minuscules et majuscules sont pris en compte.
Chiffrements historiques
César
Le chiffrement de César a été inventé et utilisé par Jules César pour ses correspondances.
Il y employait, pour les choses tout à fait secrètes, une espèce de chiffre qui en rendait le sens inintelligible (les lettres étant disposées de manière à ne pouvoir jamais former un mot), et qui consistait, je le dis pour ceux qui voudront les déchiffrer, à changer le rang des lettres dans l’alphabet, en écrivant la quatrième pour la première, c’est-à-dire le d pour le a, et ainsi de suite
— Suétone, Vie des douze César, Livre I, paragraphe 56.
Initiallement, le chiffrement de César se fait avec un décallage de 3 lettres (d \(\rightarrow\) a). De façon plus générale, il désigne tout chiffrement par décallage.
Question 1
À partir de la description fournie par Suétone, implémenter le chiffrement enc_caesar dans le fichier TP1.py. Le chiffrement prend en paramètres deux valeurs :
- \(K\) qui indique la taille du décallage dans l’alphabet ;
- \(M\) le texte à chiffrer.
Question 2
Implémentez maintenant la fonction dec_caesar permettant de déchiffrer les messages chiffrés avec le chiffrement de César. La fonction prend deux paramètres en entrée :
- \(K\) qui indique la taille du décallage dans l’alphabet ;
- \(C\) le texte à déchiffrer.
Question 3 : rot_x
Il existe une permutation spéciale telle que le chiffrement et le déchiffrement soient la même fonction. Quelle est la valeur de \(X\) ?
Implémentez la fonction rot_x de telle manière que :
\[ \texttt{rot}\_\texttt{x}(M) = C \text{ et } \texttt{rot}\_\texttt{x}(C) = M \]
Chiffrements par permutations
Vigenère
Le chiffrement de Vigenère est un chiffrement par substitution polyalphabétique1 a été (re)crée en 15862. Malgré une conception simple, il a résisté aux attaque jusqu’en 1863 lorsque le majour prussein Friedrich Kasiski a publié sa méthode.
L’algorithme repose sur le chiffrement de César en ajoutant une clé. Dans le cas du chiffrement de César, toutes les lettres du messages sont décalées de la même valeur. Dans le cas du chiffrement de Vigenère, les lettres vont être décallées en fonction des valeurs de la clé.
Par exemple, le texte “bonjour tout le monde” chiffré avec la clé “CLE” donnera “dzrlzyt eswe pg xspoi”.
Le détail de la conversion est donnée ci-dessous.
| C | L | E | C | L | E | C | L | E | C | L | E | C | L | E | C | L | E | |||
| \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | \(\boxplus\) | |||
| b | o | n | j | o | u | r | t | o | u | t | l | e | m | o | n | d | e | |||
| = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | |||
| d | z | r | l | z | y | t | e | s | w | e | p | g | x | s | p | o | i |
L’opérateur \(\boxplus\) représente l’addition modulo (26 dans notre cas).
Cryptanalyse
Avec l’avénement des ordinateurs modernes, de nombreux algorithmes qui étaient sécurisé face à une attaque par brute force (recherche exhaustive de toutes les clés) ne sont plus sécurisé de nos jours. Une technique nécessaire, mais non suffisante, pour résister face aux technologies modernes et d’augmenter la taille des clés de façon à rendre l’attaque par brute force impossible en pratique. Par exemple, un chiffrement avec une clé 256 bits nécessiteras \(2^{256}\) essais (dans le pire des cas) pour réussir.
Alice souhaite communiquer avec Bob mais ne possède qu’un chiffrement avec une petite clé. Elle a donc pour idée de chiffrer deux fois son message avec deux clés différentes :
\[ E_K(M) = E_{K_2}(E_{K_1}(M)) \]
\(K\) est alors la paire \((K_1, K_2)\). Si \(K_1\) et \(K_2\) sont deux clés de \(n\) bits alors le nombre de clé possibles pour \(K\) est :
\[ 2^n \times 2^n = 2^{2 n} \]
Question
Cherchez comment réaliser une attaque qui ne nécessite pas \(2^{2 n}\) opérations et implémentez la. L’implementation devra se faire dans la fonction decrypt du fichier TP1.py.
La signature de la fonction est la suivante :
def decrypt(
K_domain: iter,
encryption: callable,
decryption: callable,
M: str,
C: str
) -> tuple[str, str]:Le paramètre \(K_{\text{domain}}\) contient l’ensemble des valeurs possible pour une clé. On parle ici de la clé \(K_1\) ou \(K_2\). \(\text{encryption}\) (resp. \(\text{decryption}\)) la fonction de chiffrement (resp. déchiffrement) utilisée. \(M\) et \(C\) un texte clair et le chiffré associé.
De façon algorithmique :
encryption(K2, encryption(K1, M)) = C
decryption(K1, decryption(K2, C)) = M