Lernzettel: Introduction à la cryptographie et nombres premiers

📋 Plan du Cours

1. Rôle des nombres premiers en cryptographie
2. Cryptographie : confidentialité et protection
3. Sécurité des cartes bancaires et codes PIN
4. Chiffrement de César et déchiffrement
5. Limites du chiffrement par décalage
6. Machines de guerre et essor du déchiffrement
7. Réinvention de la cryptographie face aux ordinateurs
8. Chiffrement par substitution et permutations
9. Chiffrement RSA et fondement mathématique
10. Définition des nombres premiers et théorème fondamental
11. Factorisation en nombres premiers et difficulté
12. Exposants RSA et déchiffrement par opérations inverses

📖 1. Rôle des nombres premiers en cryptographie

🔑 Notions clés & Définitions

• Nombres premiers : Les nombres premiers sont des entiers positifs ayant exactement deux diviseurs, 1 et eux-mêmes.
• Cryptographie : La cryptographie est l’ensemble des techniques qui transforment des données en un message illisible pour protéger leur confidentialité.
• Confidentialité des données : La confidentialité correspond au fait que seules les personnes autorisées puissent comprendre le message, les autres voyant un contenu incompréhensible.
• Déchiffrement : Le déchiffrement est l’opération inverse qui permet de retrouver le message original à partir du message chiffré.

📝 Points essentiels

• Les nombres premiers servent de base à des méthodes de chiffrement où la sécurité dépend de calculs liés à la factorisation.
• L’informatique et Internet augmentent fortement les ressources disponibles pour déchiffrer, ce qui pousse à des techniques plus difficiles à casser.
• La cryptographie vise à rendre un message incompréhensible pour toute personne autre que le destinataire.
• La sécurité recherchée est un compromis entre protection forte et capacité du destinataire à lire le message.
• Le texte relie l’usage quotidien de la cryptographie à la protection des transactions bancaires par Internet.

💡 Astuce mémo

Premier = 2 diviseurs : 1 et lui-même ; si on ne peut pas factoriser, on ne peut pas remonter.

📖 2. Cryptographie : confidentialité et protection

🔑 Notions clés & Définitions

• Chiffrer un message : Chiffrer un message consiste à le transformer en une forme illisible afin d’empêcher sa lecture par des tiers.
• Message incompréhensible : Un message incompréhensible est un texte chiffré qui ne révèle pas directement le contenu original sans la bonne méthode de déchiffrement.
• Données privées : Les données privées sont des informations personnelles ou sensibles que la cryptographie cherche à protéger contre l’accès non autorisé.
• Transactions bancaires : Les transactions bancaires sont des échanges financiers qui doivent être protégés pour éviter l’interception ou la lecture frauduleuse.

📝 Points essentiels

• La cryptographie est définie comme l’art de chiffrer ou sécuriser un message ou des données.
• Le but central est d’assurer la confidentialité en transformant les données en un message illisible.
• La cryptographie s’applique à des acteurs variés : individus, entreprises, armée, gouvernements.
• Le texte insiste sur la protection de messages hautement confidentiels et de données privées.
• L’évolution technologique impose des techniques de cryptage plus pointues car le déchiffrement devient plus accessible.

💡 Astuce mémo

Confidentialité = rendre illisible + permettre lecture uniquement au destinataire.

📖 3. Sécurité des cartes bancaires et codes PIN

🔑 Notions clés & Définitions

• Code PIN : Un code PIN est un code numérique utilisé pour authentifier l’accès à une carte bancaire.
• Espace de recherche : L’espace de recherche est l’ensemble des combinaisons possibles à tester pour trouver un code correct.
• Tentatives limitées : Les tentatives limitées sont des restrictions qui réduisent le nombre d’essais possibles avant échec ou blocage.
• Probabilité de réussite : La probabilité de réussite est la chance qu’un essai aléatoire tombe sur le bon code parmi toutes les possibilités.

📝 Points essentiels

• Un exemple de carte bancaire donne un PIN de 4 chiffres, avec 10 possibilités par chiffre.
• Le nombre total de PIN possibles vaut 10×10×10×10 = 10 000.
• En testant toutes les possibilités à 2 secondes par test, il faut jusqu’à 20 000 secondes pour trouver le bon code.
• Avec un ordinateur capable d’un million de tests par seconde, toutes les combinaisons seraient testées en un centième de seconde.
• Le texte propose comme parade de limiter le nombre de tentatives à 3, ce qui réduit fortement les chances de succès.
• Avec une probabilité de réussite par essai de 1/10 000 et n = 3, le texte donne une valeur de 0.0003 = 0.03%.

💡 Astuce mémo

4 chiffres → 10 000 PIN ; si on n’a que 3 essais, la réussite devient ~3/10 000.

📖 4. Chiffrement de César et déchiffrement

🔑 Notions clés & Définitions

• Chiffrement de César : Le chiffrement de César est une méthode de substitution par décalage où chaque lettre est déplacée d’un nombre fixe de positions dans l’alphabet.
• Décalage de trois rangs : Le décalage de trois rangs est le paramètre du chiffrement de César utilisé dans l’exemple du texte.
• Alphabet circulaire : L’alphabet circulaire est l’idée que le décalage « boucle » en passant de z à a, comme dans l’exemple.
• Déchiffrement par décalage inverse : Le déchiffrement par décalage inverse consiste à appliquer le décalage opposé pour retrouver les lettres d’origine.

📝 Points essentiels

• Le chiffrement de César est présenté comme un décalage de 3 lettres vers la droite dans l’alphabet.
• Dans l’exemple, a devient d, b devient e et c devient f.
• Le texte montre le caractère circulaire : x devient a, y devient b et z devient c.
• Pour décoder, on décale de 3 crans vers la gauche.
• Le mot « gladiateur » devient « jodgldwhxu » avec le décalage de 3 vers la droite.

💡 Astuce mémo

César : +3 pour chiffrer, -3 pour déchiffrer (et ça boucle après z).

📖 5. Limites du chiffrement par décalage

🔑 Notions clés & Définitions

• Sécurité limitée : Une sécurité limitée signifie que la méthode peut être cassée par essai de clés ou analyse statistique avec des moyens actuels.
• Analyse fréquentielle : L’analyse fréquentielle est une méthode qui exploite la fréquence des lettres pour déduire le décalage utilisé.
• Lettre la plus utilisée : La lettre la plus utilisée est la lettre dominante d’une langue, utilisée comme repère pour retrouver le décalage dans un texte chiffré.
• Nombre de décalages possibles : Le nombre de décalages possibles est le nombre de clés distinctes correspondant à des décalages différents dans l’alphabet.

📝 Points essentiels

• Le texte affirme que le chiffrement de César n’est plus sûr aujourd’hui.
• Il indique que la technique est limitée par le nombre d’options de décalage liées au nombre de caractères différents.
• Pour trouver la clé, il suffit de tester les différentes options sur une portion du message.
• Le texte utilise l’exemple de la lettre « e » comme la plus utilisée en français.
• Il explique que si « h » apparaît plus souvent, on peut en déduire que « h » correspond à « e » après le décalage de César.
• La difficulté générale de la cryptographie est de protéger sans empêcher le destinataire de lire le message.

💡 Astuce mémo

Décalage cassable : soit on teste toutes les clés, soit on repère la lettre dominante (e ↔ h dans l’exemple).

📖 6. Machines de guerre et essor du déchiffrement

🔑 Notions clés & Définitions

• Enigma : Enigma est une machine de cryptage utilisée par les Allemands pendant la Seconde Guerre mondiale.
• Colossus : Colossus est présenté comme le premier ordinateur de l’histoire, utilisé pour déchiffrer des échanges.
• Lorentz : Lorentz est une machine de cryptage mentionnée comme utilisée par les généraux pour communiquer.
• Supercalculateurs : Les supercalculateurs sont des machines capables d’effectuer un très grand nombre d’opérations par seconde, accélérant le déchiffrement.

📝 Points essentiels

• Le texte cite la Seconde Guerre mondiale comme étape marquante de l’évolution de la cryptographie.
• Les Allemands utilisent la machine Enigma pour chiffrer des communications.
• Enigma est vaincue par des mathématiciens polonais et britanniques, dont Alan Turing, aidés de gros calculateurs.
• Les Britanniques mettent au point le Colossus pour déchiffrer des échanges entre Hitler et ses généraux.
• Les généraux utilisent une autre machine de cryptage, la machine Lorentz.
• Le texte explique que les supercalculateurs réalisent des quantités d’opérations bien supérieures à l’homme, avec des milliards voire dizaines de milliards de calculs par seconde selon les modèles.

💡 Astuce mémo

Guerre → machines : plus de calculs = plus de déchiffrement, donc cryptos plus dures à casser.

📖 7. Réinvention de la cryptographie face aux ordinateurs

🔑 Notions clés & Définitions

• Réinvention de la cryptographie : La réinvention de la cryptographie désigne l’adaptation des méthodes pour que le déchiffrement devienne trop coûteux même pour les ordinateurs.
• Coût de déchiffrement : Le coût de déchiffrement est la quantité de calculs nécessaire pour casser un message chiffré.
• Cryptage par décalage amélioré : Le cryptage par décalage amélioré est une variante où les lettres sont associées à d’autres lettres selon un schéma aléatoire.
• Notion de clé : Une clé est l’information nécessaire pour décoder un message chiffré selon une méthode donnée.

📝 Points essentiels

• Le texte affirme que la cryptographie doit employer des techniques dont le déchiffrement demande un nombre de calculs insurmontable.
• Il indique que la première technique post-guerre est une version améliorée du chiffrement par décalage.
• Dans cette version, chaque lettre est associée à une autre lettre selon un aléatoire (exemple donné : H ↔ B et B ↔ Z).
• Le texte explique que posséder la notice (le schéma) permet de décoder.
• Le texte calcule le nombre d’assignations possibles en utilisant l’idée que l’ordre compte et qu’il n’y a pas de répétition.
• Il donne une formule de permutation $N!$ et applique $26!$, avec une estimation d’environ $4\times 10^{26}$.

💡 Astuce mémo

Ordre + pas de répétition → permutations : $26!$ devient énorme, donc casser devient difficile.

📖 8. Chiffrement par substitution et permutations

🔑 Notions clés & Définitions

• Substitution : La substitution est une méthode où chaque lettre du message est remplacée par une autre lettre selon une correspondance définie par la clé.
• Permutation : Une permutation est un réarrangement où chaque élément apparaît une seule fois, ce qui correspond ici à l’assignation des lettres.
• Correspondance aléatoire : Une correspondance aléatoire est un mapping lettre→lettre choisi de façon non déterministe pour rendre le décodage plus difficile sans la clé.
• Factorielle $N!$ : La factorielle $N!$ est le produit des entiers de 1 à $N$, utilisée ici pour compter le nombre de permutations possibles.

📝 Points essentiels

• Le texte décrit une technique où chaque lettre est remplacée par une autre dans un schéma aléatoire.
• Il précise que l’ordre compte dans le comptage des correspondances.
• Il précise que la répétition n’est pas possible dans l’assignation des lettres.
• Le nombre de permutations est donné comme $N!$.
• Dans le cas de l’alphabet à 26 lettres, le texte utilise $26!$.
• Le texte estime $26!$ à environ $4\times 10^{26}$.

💡 Astuce mémo

Substitution sans répétition = permutation ; compter les clés revient à compter $N!$.

📖 9. Chiffrement RSA et fondement mathématique

🔑 Notions clés & Définitions

• RSA : RSA est un système de chiffrement introduit en 1977, basé sur des calculs arithmétiques et la difficulté liée aux nombres premiers.
• Clé RSA : Une clé RSA est l’ensemble des paramètres (dont des exposants) permettant de chiffrer puis déchiffrer via des opérations inverses.
• Exposants : Les exposants sont des puissances utilisées dans RSA pour transformer les nombres chiffrés et permettre l’opération inverse au déchiffrement.
• Nombres premiers : Les nombres premiers sont la notion mathématique centrale dont la factorisation influence la sécurité de RSA.

📝 Points essentiels

• Le texte attribue l’introduction de RSA à Ron Rivest, Adi Shamir et Leonard Adleman en 1977.
• RSA est présenté comme très utilisé pour protéger des échanges de données.
• Le texte indique que RSA repose sur des calculs arithmétiques comme des exposants et des divisions avec reste.
• La sécurité de RSA est liée à une méthode de chiffrement et à la notion essentielle des nombres premiers.
• Le texte affirme que RSA code un caractère via une combinaison de deux nombres entre 00 et 99.
• Le texte mentionne un défaut des techniques précédentes où on pouvait deviner progressivement, ce qui motive des méthodes plus robustes.

💡 Astuce mémo

RSA = exposants + nombres premiers : la sécurité vient de ce que la factorisation est difficile.

📖 10. Définition des nombres premiers et théorème fondamental

🔑 Notions clés & Définitions

• Nombre premier : Un nombre premier est un entier positif ayant exactement deux diviseurs.
• Diviseurs 1 et lui-même : Pour un nombre premier, les seuls diviseurs sont 1 et le nombre lui-même.
• 1 non premier : Le nombre 1 n’est pas premier car il ne possède qu’un seul diviseur : lui-même.
• Théorème fondamental de l’Arithmétique : Le théorème fondamental de l’arithmétique affirme que tout entier strictement supérieur à 1 s’écrit comme un produit de nombres premiers.

📝 Points essentiels

• Le texte donne la définition : exactement deux diviseurs pour un nombre premier.
• Il précise que ces deux diviseurs sont nécessairement 1 et le nombre lui-même.
• Exemples donnés : 2, 3, 29 et 71 sont premiers.
• Le texte explique que 4 n’est pas premier car divisible par 2.
• Le texte explique que 1 n’est pas premier car il n’a qu’un seul diviseur.
• Le texte énonce le théorème fondamental : tout entier > 1 s’écrit comme un produit de nombres premiers.

💡 Astuce mémo

Premier = 2 diviseurs ; et tout nombre >1 se décompose en produit de premiers.

📖 11. Factorisation en nombres premiers et difficulté

🔑 Notions clés & Définitions

• Décomposition en facteurs premiers : La décomposition en facteurs premiers est l’écriture d’un nombre comme produit de nombres premiers.
• Factorisation : La factorisation est l’opération qui consiste à trouver les facteurs premiers d’un nombre.
• Difficulté de calcul : La difficulté de calcul correspond au fait qu’une factorisation peut demander un temps de calcul énorme.
• Supercalculateurs : Les supercalculateurs sont utilisés quand les calculs nécessaires dépassent les capacités d’un ordinateur ordinaire.

📝 Points essentiels

• Le texte relie RSA à la factorisation : le message chiffré doit être décomposé en produit de nombres premiers.
• Il donne des exemples de décompositions : 6 = 2×3, 9 = 3×3, 42 = 2×3×7.
• Il donne un exemple : 221 = 13×17.
• Il affirme que factoriser un grand nombre issu du chiffrement nécessite beaucoup de calculs.
• Pour un texte d’environ 10 lignes, le texte indique qu’un ordinateur lambda aurait besoin de plus d’une semaine pour trouver la décomposition.
• Le texte conclut que cette difficulté justifie l’usage de supercalculateurs côté serveurs.

💡 Astuce mémo

RSA tient grâce à la factorisation : sans facteurs premiers, pas de remontée vers le message.

📖 12. Exposants RSA et déchiffrement par opérations inverses

🔑 Notions clés & Définitions

• Exposant de cryptage : Un exposant de cryptage est un paramètre propre à chaque personne utilisé pour transformer les nombres via des puissances.
• Opérations inverses : Les opérations inverses sont des calculs qui annulent l’effet de l’opération de chiffrement pour retrouver la valeur précédente.
• Racine de l’exposant : La racine de l’exposant est décrite dans le texte comme l’opération inverse permettant de revenir au nombre chiffré de base.
• Produit des premiers : Le produit des premiers est la recomposition du nombre à partir de ses facteurs premiers après l’opération inverse.

📝 Points essentiels

• Le texte explique qu’un pirate pourrait multiplier les nombres premiers pour retrouver le message chiffré non factorisé, si la factorisation est connue.
• Pour contrer cela, chaque personne possède un exposant de cryptage qui lui est propre.
• Le texte décrit que chaque nombre premier de la liste factorisée est élevé à cette puissance.
• Le destinataire, connaissant son exposant, effectue l’opération inverse.
• Le texte indique que l’inverse consiste à prendre la racine de l’exposant puis à recombiner par produit des différents premiers.
• Le texte conclut que cette recombinaison permet de remonter au message chiffré de base et de le déchiffrer avec la notice.

💡 Astuce mémo

Exposant privé : on élève à la puissance ; pour inverser, on prend l’inverse (racine) puis on recombine.

📅 Repères chronologiques

📊 Tableaux de synthèse

Casser un code PIN : humain vs ordinateur

César : chiffrer vs déchiffrer

⚠️ Pièges & confusions fréquents

1. Confondre chiffrement et déchiffrement : dans César, le sens du décalage s’inverse.
2. Croire que 1 est un nombre premier : le texte précise qu’il n’a qu’un seul diviseur.
3. Penser que la sécurité RSA vient du fait de « cacher » le message : le texte insiste sur la difficulté de factoriser.
4. Oublier que le texte relie la casse du PIN à la vitesse de test : limiter les tentatives change radicalement les chances.
5. Confondre substitution et permutation : ici, la correspondance lettre→lettre sans répétition se compte comme une permutation $N!$.
6. Croire qu’un pirate peut toujours remonter au message : le texte ajoute l’idée d’exposant propre à chaque personne.

✅ Checklist Examen

1. Définir la cryptographie et son objectif de confidentialité.
2. Expliquer pourquoi les nombres premiers interviennent dans des systèmes de protection.
3. Calculer le nombre de PIN possibles pour 4 chiffres et interpréter l’impact du nombre de tentatives.
4. Décrire le chiffrement de César avec un décalage de 3 vers la droite et donner le principe du déchiffrement.
5. Expliquer pourquoi le chiffrement par décalage est cassable (test des clés et repérage via fréquence des lettres).
6. Citer les machines de guerre et leur rôle : Enigma, Colossus, Lorentz, et l’idée générale de l’accélération du déchiffrement.
7. Expliquer la réinvention : rendre le déchiffrement trop coûteux et comprendre le comptage via permutations $N!$.
8. Définir substitution et permutation dans le contexte du mapping lettre→lettre sans répétition.
9. Présenter RSA : auteurs, année, et l’idée que la sécurité dépend des nombres premiers et de calculs arithmétiques.
10. Donner la définition d’un nombre premier et énoncer le théorème fondamental de l’arithmétique.
11. Expliquer la factorisation en facteurs premiers et pourquoi elle devient difficile pour de grands nombres.
12. Décrire le rôle des exposants RSA et l’idée d’opérations inverses (racine de l’exposant puis recombinaison).