Lernzettel: Cryptographie historique et cryptanalyse

📋 Plan du Cours

1. Stéganographie : dissimuler sans clé
2. Chiffrements par transposition
3. Chiffrements par substitution
4. Taille des clés et cryptanalyse par fréquences
5. Chiffrement homophonique et extensions
6. Chiffrement polyalphabétique Vigenère
7. Cryptanalyse de Vigenère par Kasiski
8. Principe de Kerckhoffs et sécurité par clé
9. Enigma : rotors, réflecteur et connexions
10. Récupération de clé Enigma et critères observables
11. Cryptanalyse pendant la guerre et bombes
12. Bletchley Park et contributions de Turing

📖 1. Stéganographie : dissimuler sans clé

🔑 Notions clés & Définitions

• Stéganographie : La stéganographie dissimule l’existence d’une information plutôt que de la transformer en secret chiffré.
• Steganos : Steganos signifie étanche et hermétique, renvoyant à l’idée de cacher sans laisser de trace visible.
• Graphein : Graphein renvoie à l’idée d’écrire ou de tracer, associé à la notion de dissimulation d’information.
• Encre invisible : L’encre invisible est un exemple classique de message caché qui devient lisible seulement après un traitement.

📝 Points essentiels

• En stéganographie, il n’y a pas de notion de clé secrète au sens cryptographique classique.
• Une fois la technique découverte, le message peut être retrouvé malgré la dissimulation initiale.
• Exemple historique : enlevant des lettres sur une tablette d’argile (Irak).
• Exemples historiques : dissimulation dans les pixels d’une image et tatouage sur la tête (Grèce antique).
• L’objectif est de cacher le message lui-même, pas de le rendre incompréhensible.
• L’encre invisible illustre une dissimulation où le contenu n’est pas directement visible.

💡 Astuce mémo

Stéga = cacher l’existence, pas chiffrer : pas de clé.

📖 2. Chiffrements par transposition

🔑 Notions clés & Définitions

• Chiffrement par transposition : Un chiffrement par transposition permute les lettres d’un message sans changer leur nature.
• Scytale : La scytale est un dispositif historique de transposition associé à Sparte.
• Rail Fence : Le chiffre Rail Fence est une méthode historique de transposition associée au Rail Fence pendant la Guerre de Sécession.

📝 Points essentiels

• Un chiffrement par transposition consiste à réordonner les lettres du message par une permutation.
• Exemple évoqué : chiffrer un message de 7 lettres avec une clé donnant des correspondances de positions.
• La fonction de chiffrement et la fonction de déchiffrement doivent être décrites proprement pour une transposition.
• Même si la sécurité n’est pas discutée ici, utiliser ce type de chiffrement peut être compliqué en pratique.
• La scytale (Sparte, -400) illustre une transposition par réarrangement physique.
• Le Rail Fence illustre une transposition par réécriture selon une structure en lignes.

💡 Astuce mémo

Transposition = on mélange l’ordre des lettres, pas les lettres elles-mêmes.

📖 3. Chiffrements par substitution

🔑 Notions clés & Définitions

• Chiffrement par substitution : Un chiffrement par substitution remplace chaque lettre par une autre (ou par elle-même) selon une règle fixe.
• Permutation de l’alphabet : Une permutation de l’alphabet est un réarrangement bijectif des lettres qui définit la substitution monoalphabétique.
• Chiffre de César : Le chiffre de César est une substitution par décalage (ici décalage de 3) associée à une période historique mentionnée.
• Chiffre des templiers : Le chiffre des templiers utilise un alphabet de sortie différent pour chiffrer les messages.

📝 Points essentiels

• Une substitution monoalphabétique est définie par une permutation de l’alphabet.
• On peut utiliser un alphabet différent pour les messages chiffrés, ce qui change l’espace de représentation.
• Le chiffre de César est présenté avec un décalage de 3 et un alphabet grec dans le cours.
• Modélisation donnée : A=0, B=1, …, Z=25 et K={0,…,25}=Z/26Z.
• Modélisation donnée : M={A,…,Z}=(Z/26Z) pour formaliser les messages comme suites de symboles.
• Pour décrypter un texte chiffré par substitution, on s’appuie sur l’observation des fréquences et des correspondances probables.

💡 Astuce mémo

Substitution = chaque lettre devient une autre lettre via une permutation.

📖 4. Taille des clés et cryptanalyse par fréquences

🔑 Notions clés & Définitions

• Cryptanalyse par fréquences : La cryptanalyse par fréquences exploite le fait que certaines lettres ou combinaisons apparaissent plus souvent dans une langue donnée.
• Al-Kindi : Al-Kindi est associé au travail historique sur l’analyse de fréquences au 9ème siècle à Bagdad.
• Bigrammes : Les bigrammes sont des paires de lettres utilisées pour affiner une attaque par fréquences après les lettres seules.
• Substitution monoalphabétique : La substitution monoalphabétique est un chiffrement où chaque lettre est remplacée par une seule lettre selon une règle fixe.

📝 Points essentiels

• Le nombre de clés possibles doit être grand pour rendre l’attaque exhaustive difficile.
• Pour une substitution générale sur 26 lettres, le cours donne 26! ≈ 2^88 clés possibles.
• L’analyse des fréquences suppose une langue connue et un texte chiffré suffisamment long.
• Dans une langue à alphabet, certaines lettres ou combinaisons apparaissent avec des fréquences différentes.
• L’attaque associe les lettres les plus fréquentes du chiffré aux lettres les plus fréquentes de la langue d’origine.
• On peut ensuite progresser “de proche en proche” avec les bigrammes fréquents pour retrouver d’autres correspondances.

💡 Astuce mémo

Fréquences : lettres d’abord, puis bigrammes pour verrouiller les correspondances.

📖 5. Chiffrement homophonique et extensions

🔑 Notions clés & Définitions

• Chiffrement homophonique : Le chiffrement homophonique remplace une lettre par plusieurs symboles possibles, choisis selon une règle liée à la fréquence.
• Alphabet de sortie élargi : Un alphabet de sortie élargi signifie que le chiffrement utilise plus de symboles que l’alphabet de départ.
• Chiffrement de bigrammes : Le chiffrement de bigrammes remplace des paires de lettres par un autre caractère selon une règle dédiée.
• Chiffrement de mots fréquents : Le chiffrement de mots fréquents remplace des mots courants par d’autres caractères pour réduire la répétition exploitable.

📝 Points essentiels

• Le chiffrement homophonique remplace chaque lettre par plusieurs lettres possibles.
• Le nombre de remplacements pour une lettre est proportionnel à sa fréquence d’apparition.
• L’alphabet de sortie devient donc plus grand, ce qui perturbe l’analyse simple des fréquences.
• Le cours mentionne aussi l’ajout de caractères nuls dans le texte chiffré.
• Une extension possible consiste à chiffrer des bigrammes avec un autre caractère.
• Une autre extension mentionnée consiste à chiffrer des mots fréquents par un autre caractère.

💡 Astuce mémo

Homophonique = une lettre a plusieurs “sorties”, donc les fréquences se brouillent.

📖 6. Chiffrement polyalphabétique Vigenère

🔑 Notions clés & Définitions

• Chiffre de Vigenère : Le chiffre de Vigenère est un chiffrement polyalphabétique où le décalage dépend d’une clé répétée.
• Giovanni Battista Bellaso : Giovanni Battista Bellaso est cité comme auteur associé à l’idée de chiffrement polyalphabétique (1553).
• Blaise de Vigenère : Blaise de Vigenère est cité avec une date associée (1586) pour le chiffre portant son nom.
• Clé répétée : La clé répétée signifie que la clé est utilisée périodiquement sur les lettres du message.

📝 Points essentiels

• Le cours présente une solution polyalphabétique avec Bellaso (1553) et Vigenère (1586).
• La clé est modélisée comme $K=(Z/26Z)^n$ et le chiffrement comme une application vers $(Z/26Z)$.
• La formule donnée : pour \ell lettres, pour tout $0\le i<\ell$, on a $c_i=m_i+k_i\mod n$.
• Le déchiffrement suit la même structure avec la clé (en pratique, on soustrait le décalage modulo).
• Exemple chiffré fourni : CKRPJIGVLCXAKUCBTWP avec la clé CRYPTO.
• Le cours indique que la clé est utilisée par positions modulo la longueur de clé $n$.

💡 Astuce mémo

Vigenère = décalage qui change à chaque position selon la clé répétée.

📖 7. Cryptanalyse de Vigenère par Kasiski

🔑 Notions clés & Définitions

• Friedrich Wilhelm Kasiski : Friedrich Wilhelm Kasiski est cité comme auteur associé à une méthode d’attaque contre Vigenère.
• Taille de la clé : La taille de la clé est la période $n$ qui détermine comment les décalages se répètent dans Vigenère.
• Répétitions de séquences : Les répétitions de séquences dans le texte chiffré peuvent révéler des alignements de clé identiques.
• Séquences chiffrées avec même partie de clé : Quand une séquence répétée apparaît, elle est chiffrée avec la même portion de clé si l’alignement coïncide.

📝 Points essentiels

• La méthode part d’une question : si on connaît la taille de la clé $n$, que peut-on faire ensuite ?
• Le cours indique que dans toutes les langues, des répétitions assez fréquentes existent.
• Observation clé : les mêmes séquences de lettres sont chiffrées avec la même partie de la clé.
• Le cours illustre avec un texte chiffré où des séquences répétées apparaissent.
• Un exemple complet montre une estimation de la taille de clé $k$ à partir d’un tableau de longueurs possibles.
• Dans l’exemple, la taille de clé est déterminée à 5 lettres (k=5) avant de récupérer une partie de clé.

💡 Astuce mémo

Kasiski : répétitions du chiffré → même alignement de clé → période $n$.

📖 8. Principe de Kerckhoffs et sécurité par clé

🔑 Notions clés & Définitions

• Principe de Kerckhoffs : Le principe de Kerckhoffs affirme que la sécurité d’un système dépend du secret de la clé, pas du secret du système.
• Auguste Kerckhoffs : Auguste Kerckhoffs est cité comme auteur du principe dans un contexte de cryptographie militaire (1883).
• Claude Shannon : Claude Shannon est cité pour l’idée que l’adversaire connaît le système.
• Sécurité par clé : La sécurité par clé signifie que seule la clé reste secrète tandis que le mécanisme est supposé connu.

📝 Points essentiels

• Le cours relie Kerckhoffs à un contexte de guerre franco-prussienne et à l’intérêt français pour la cryptographie.
• Kerckhoffs (1883) : la sécurité ne doit reposer que sur le secret de la clé.
• Shannon : l’adversaire connaît le système, ce qui renforce l’exigence de robustesse face à la connaissance du procédé.
• Le principe sert de cadre pour juger la sécurité des cryptosystèmes historiques et modernes.
• Dans la suite du cours, l’idée “clé seule secrète” motive l’analyse et la cryptanalyse.
• Le cours présente Enigma et ses attaques dans cet esprit : on cherche à récupérer la clé malgré la connaissance de la machine.

💡 Astuce mémo

Kerckhoffs/Shannon : système connu, seule la clé reste secrète.

📖 9. Enigma : rotors, réflecteur et connexions

🔑 Notions clés & Définitions

• Enigma : Enigma est une machine à chiffrer électromécanique dont le fonctionnement repose sur des rotors et un réflecteur.
• Rotors : Les rotors sont des composants qui réalisent des substitutions dépendant de la position et qui changent à chaque lettre.
• Réflecteur : Le réflecteur est une pièce qui renvoie le signal pour assurer une symétrie du chiffrement et du déchiffrement.
• Tableau des connexions : Le tableau des connexions (câblage) définit des transpositions de paires de lettres avant et après le passage dans les rotors.

📝 Points essentiels

• Enigma est inventée par Arthur Scherbius en 1918, et un modèle A est présenté à Berlin en 1923.
• Les parties principales mentionnées sont : clavier, tableau lumineux, rotors, tableau des connexions, réflecteur.
• Le cours décrit une substitution monoalphabétique réalisée par un rotor selon l’alphabet courant.
• Quand on tourne le rotor pour une nouvelle lettre, la substitution change.
• Avec trois rotors, chaque nouveau rotor représente 26 alphabets différents, menant à une substitution avec $26^3$ alphabets différents.
• Le réflecteur rend le processus de chiffrement et de déchiffrement identique dans la machine.

💡 Astuce mémo

Enigma = rotors qui font varier la substitution + réflecteur pour symétrie.

📖 10. Récupération de clé Enigma et critères observables

🔑 Notions clés & Définitions

• Clé secrète Enigma : La clé secrète d’Enigma regroupe l’ordre des rotors, leurs positions et le câblage des connexions.
• Carnet de codes : Le carnet de codes est un document opérationnel reliant des termes comme Tag et positions de rotors aux réglages du jour.
• Kenngruppen : Les kenngruppen sont des groupes de clés mentionnés dans le carnet de codes.
• Message-clé répété : Le message-clé est un mot de 3 lettres répété qui sert à indiquer la position des rotors pour le déchiffrement.

📝 Points essentiels

• Le cours donne une clé secrète composée : ordre des rotors, positions des rotors et 6 couples de lettres transposées.
• Le nombre de possibilités est estimé à environ $6\times 26^3\times 100\,391\,791\,500\approx 2^{53}$ (valeur arrondie dans le cours).
• Avant la guerre, le cours donne aussi des dénombrements : 3 rotors parmi 5, ordre des rotors, positions initiales, et tableau de connexion.
• Le cours indique que chaque message est précédé d’un mot de 3 lettres aléatoires répété.
• Ces 3 lettres en clair donnent la position des rotors à utiliser pour déchiffrer la suite du message.
• Stratégie générale : récupérer une partie de la clé indépendamment du tableau de connexions en cherchant un critère observable lié aux rotors.

💡 Astuce mémo

Enigma : le “message-clé” (3 lettres) révèle la position des rotors, pas le câblage.

📖 11. Cryptanalyse pendant la guerre et bombes

🔑 Notions clés & Définitions

• Bombes de Rejewski : Les bombes de Rejewski sont des machines automatiques conçues pour retrouver la clé du jour d’Enigma.
• Cryptanalyse pendant la guerre : La cryptanalyse pendant la guerre désigne l’effort systématique pour casser les messages chiffrés en exploitant des réglages quotidiens.
• Renforcement de la sécurité : Le renforcement de la sécurité correspond aux modifications apportées à Enigma pour rendre les attaques plus difficiles.
• Ajout de rotors : L’ajout de rotors augmente l’espace des configurations possibles et complique la récupération de clé.

📝 Points essentiels

• Le cours décrit des constructions de machines automatiques pour trouver la clé du jour en environ 2 heures.
• Les bombes de Rejewski visent à exploiter la structure de la clé du jour.
• En 1938, les Allemands renforcent la sécurité d’Enigma.
• Le renforcement inclut l’ajout de 2 nouveaux rotors.
• Les connexions passent de 6 à 10, ce qui modifie le câblage et donc la clé.
• Le cours indique aussi l’abandon du message-clé, supprimant l’indice des 3 lettres répétées.

💡 Astuce mémo

Bombes = automatiser la recherche de clé ; puis Enigma change (rotors + connexions + plus de message-clé).

📖 12. Bletchley Park et contributions de Turing

🔑 Notions clés & Définitions

• Bletchley Park : Bletchley Park est le lieu associé aux cryptanalystes qui exploitent et améliorent les méthodes contre Enigma.
• Marian Rejewski : Marian Rejewski est cité comme mathématicien polonais lié aux méthodes polonaises avant Bletchley Park.
• Mots probables : Les mots probables (cribs) sont des hypothèses de texte clair utilisées pour guider la recherche de clé.
• Alan Turing : Alan Turing est cité pour une méthode de cassage d’Enigma sans dépendre de la répétition du message-clé.

📝 Points essentiels

• Le cours indique que les cryptanalystes de Bletchley Park se familiarisent avec les méthodes polonaises.
• Ils créent de nouveaux raccourcis pour la recherche de solutions.
• Ils exploitent des “cillies”, décrites comme des lettres se suivant au tableau ou des initiales d’une personne liée à l’opérateur.
• Turing vise à casser Enigma sans utiliser l’hypothèse de répétition du message-clé.
• La méthode des mots probables (“cribs”) est associée à un nombre de possibilités estimé à 1 054 560.
• Le cours mentionne aussi l’automatisation de la recherche de clé par des “bombes de Turing” avec 20 280 essais/s et environ 50 s pour retrouver la clé.

💡 Astuce mémo

Turing : cribs (mots probables) + automatisation pour éviter l’indice du message-clé.

📅 Repères chronologiques

📊 Tableaux de synthèse

Transposition vs substitution

Vigenère : monoalphabétique vs polyalphabétique

⚠️ Pièges & confusions fréquents

1. Confondre stéganographie et chiffrement : en stéganographie, il n’y a pas de clé secrète au sens du cours.
2. Croire qu’une transposition “cache” les lettres : elle ne fait que réordonner, donc les lettres restent identifiables.
3. Penser qu’une substitution monoalphabétique résiste aux fréquences : le cours explique au contraire une cryptanalyse par fréquences.
4. Oublier que Vigenère dépend de la taille de clé $n$ : sans $n$, l’attaque par Kasiski perd son levier principal.
5. Croire que Kerckhoffs dit que le système doit rester secret : il impose que seul la clé reste secrète.
6. Penser que le message-clé d’Enigma est toujours disponible : le cours indique qu’il est abandonné après 1938.
7. Confondre la récupération de clé par répétition (avant renforcement) et la méthode de Turing par mots probables (sans répétition).

✅ Checklist Examen

1. Définir la stéganographie et expliquer pourquoi il n’y a pas de clé secrète dans ce cadre.
2. Expliquer le principe d’un chiffrement par transposition et donner ce qui change (ordre) et ce qui ne change pas (lettres).
3. Expliquer le principe d’un chiffrement par substitution et relier substitution monoalphabétique à une permutation de l’alphabet.
4. Donner la modélisation du chiffre de César (A=0,…,Z=25 et $Z/26Z$) et préciser ce que représente la clé.
5. Calculer/justifier l’ordre de grandeur du nombre de clés pour une substitution générale (26! ≈ 2^88) et décrire l’idée de l’analyse des fréquences.
6. Décrire le chiffrement homophonique : plusieurs sorties par lettre, proportionnalité à la fréquence, et effet sur l’analyse des fréquences.
7. Écrire la relation de Vigenère $c_i=m_i+k_i\mod n$ et expliquer le rôle de la clé répétée.
8. Expliquer l’observation de Kasiski : répétitions chiffrées avec la même partie de clé et comment cela mène à la taille de clé.
9. Formuler le principe de Kerckhoffs et l’idée de Shannon : système connu, sécurité portée par le secret de la clé.
10. Lister les composants d’Enigma (clavier, tableau lumineux, rotors, connexions, réflecteur) et expliquer le rôle du réflecteur pour la symétrie chiffrement/déchiffrement.
11. Décrire la composition de la clé Enigma (ordre des rotors, positions, couples de lettres) et l’indice du message-clé de 3 lettres répété.
12. Expliquer ce qui change en 1938 (ajout de 2 rotors, connexions 6→10, abandon du message-clé) et l’impact sur les attaques.
13. Décrire les contributions de Bletchley Park (méthodes polonaises, raccourcis, exploitation des “cillies”) et la méthode de Turing (mots probables/cribs) sans répétition du message-clé.
14. Donner les ordres de grandeur cités pour les essais/s et le temps de récupération de clé avec les bombes de Turing.