09 Sécurisation des communications

🔐 Table des matières

1️⃣ Rappels
2️⃣ Vocabulaire
3️⃣ Introduction
4️⃣ Le chiffrement
5️⃣ Le protocole HTTPS
6️⃣ Exercices
7️⃣ Projet

🎯 Compétences évaluables

Décrire les principes de chiffrement symétrique (clé partagée) et asymétrique (clé publique/clé privée).
Décrire l’échange de clé symétrique via un protocole asymétrique — cas du HTTPS.

🌐 1. Rappels : que se passe-t-il quand on tape une URL ?

⚓︎

TCP Handshake

📌 Exemple : navigation vers http://gs-cassaigne.fr/

✅ Étape 1 — Le navigateur analyse l’URL⚓︎

Le navigateur découpe l’URL en 3 parties :

protocole : http (ou https)
nom de domaine : gs-cassaigne.fr
chemin : / (la racine du site)

📌 Le chemin désigne la ressource demandée : /index.html, /images/logo.png, etc.

✅ Étape 2 — Résolution DNS : du nom de domaine vers une adresse IP⚓︎

Pour envoyer des données sur Internet, il faut une adresse IP.

Le navigateur (via le système) interroge le DNS pour obtenir l’IP correspondant au nom de domaine.

➡️ Commandes adaptées :

Bash

nslookup gs-cassaigne.fr
````

ou

```bash
ping gs-cassaigne.fr

⚠️ Remarque : l’adresse IP peut varier (plusieurs serveurs, répartition de charge, CDN…).

✅ Étape 3 — Connexion : TCP et le « 3-way handshake »⚓︎

Une fois l’IP obtenue, le navigateur établit une connexion vers le serveur :

HTTP → port 80
HTTPS → port 443

Pour TCP, la connexion commence par un handshake en 3 étapes :

Client → Serveur : SYN
Serveur → Client : SYN-ACK
Client → Serveur : ACK

➡️ Une fois ce handshake réalisé, la connexion TCP est ouverte (communication fiable).

✅ Étape 4 — Échange de données : HTTP au-dessus de TCP/IP⚓︎

Une fois la connexion établie, le navigateur envoie une requête HTTP (ex. « donne-moi / »). Le serveur répond avec :

du HTML
puis souvent d’autres ressources : CSS, JavaScript, images, polices, etc.

📦 Tout cela est encapsulé en couches :

Encapsulation

HTTP = contenu applicatif (page web)
TCP = transport fiable (segments, accusés de réception)
IP = routage (trajet réseau)
Ethernet/Wi-Fi = transport sur le réseau local (trames)

🧠 Rappel du modèle TCP/IP⚓︎

Couche	Rôle	Exemples
Accès réseau	Envoi sur le support physique	Ethernet, Wi-Fi (802.11…)
Internet	Routage des paquets	IP
Transport	Fiabilité, flux, ports	TCP (fiable), UDP (rapide, moins de garanties)
Application	Services aux utilisateurs	HTTP(S), DNS, IMAP, SMTP…

😬 Problème : Internet n’est pas “privé”⚓︎

Les paquets IP passent de routeur en routeur jusqu’à destination.

Routage

👉 Sur le trajet, des intermédiaires peuvent voir au minimum :

les adresses IP source/destination
les ports utilisés
et si la communication n’est pas chiffrée (HTTP), le contenu peut être lu

➡️ Si on transmet des infos bancaires, médicales, identifiants, données privées, ce n’est pas acceptable.

🎯 Objectifs de la sécurisation des communications⚓︎

Avant d’aborder le chiffrement, on retient que sécuriser une communication vise à garantir :

Sécurité	Question
🔒 Confidentialité	Le message est-il lisible uniquement par l’émetteur et le destinataire ?
✅ Authenticité	Est-ce bien le serveur (ou l’interlocuteur) attendu ?
🧱 Intégrité	Le message a-t-il été modifié pendant le transport ?

🧩 2. Vocabulaire

⚓︎

Coder : représenter une information avec des symboles selon des règles.
Décoder : interpréter ces symboles pour retrouver l’information.

✅ Sans notion de secret : ce n’est pas une technique de sécurité.

Cryptographie : discipline qui protège les messages (confidentialité, authenticité, intégrité).
Cryptanalyse : retrouver un message sans information secrète (c’est une attaque).
Chiffrer : rendre le message illisible à un observateur non autorisé.
Déchiffrer : retrouver le message original (dans un cadre légitime).
Décrypter : retrouver le message original sans disposer des éléments nécessaires (sens “attaque”).

💡 La cryptographie existe depuis l’Antiquité (ex : chiffre de César).

🎬 3. Introduction

⚓︎

📽️ Vidéo recommandée : Comprendre SSL/TLS avec des emojis & le HTTPS 👉 https://ladigitale.dev/digiview/#/v/66c3acacea2f2

🔐 4. Le chiffrement

⚓︎

Scénario classique :

Alice 👩 veut envoyer un message secret à Bob 👨‍💻 via Internet 🌍 (non sécurisé) → Le message peut être intercepté 🚫

📌 Pour sécuriser l’échange : ➡️ On chiffre le message à l’aide :

d’un algorithme de chiffrement
d’une clé

🔐 4.1.Le chiffrement symétrique

⚓︎

🎯 4.1.1.Le principe

⚓︎

Dans un chiffrement symétrique, la même clé est utilisée pour chiffrer 🔒 et déchiffrer 🔓 le message.

❓ Qu’appelle-t-on une clé ?

Une clé est une donnée permettant le chiffrement/déchiffrement. Elle peut être :

🔢 un nombre (ex : chiffrement de César)
✍️ une phrase (ex : masque jetable / One-Time Pad)
🖼️ une image (on peut faire un XOR sur les pixels)

📌 Si la même clé permet de chiffrer → déchiffrer : ➡️ Chiffrement symétrique

✅ Avantage du chiffrement symétrique

➡️ Très rapide et peu coûteux en ressources ➡️ Adapté au chiffrement de gros volumes de données (vidéo, web…)

🧠 → C’est ce que l’on utilise dans HTTPS, pour chiffrer les données échangées.

❌ Inconvénient majeur

👉 La clé doit être partagée entre l’émetteur et le destinataire.

Si la clé est interceptée → tout le système est compromis

C’est ce qu’on appelle le problème de distribution de clé.

🔍 Un chiffrement symétrique est-il faible ?

🚫 NON ! Il peut être extrêmement robuste, voire inviolable ✅ si bien appliqué :

📌 Exemple : Masque jetable (One-Time Pad)

clé aussi longue que le message
clé utilisée une seule fois
XOR bit à bit

➡️ Sécurité mathématiquement parfaite

Exemple avec le message « LUNDI » : L’attaquant doit tester 26⁵ clés possibles → 11 881 376 possibilités…

📌 Et autant de messages déchiffrés possibles ⇒ aucune certitude

C’est le principe de Kerckhoffs ✅ « La sécurité repose sur la clé, pas sur le secret de l’algorithme »

🔥 Chiffrements symétriques modernes : AES

L’algorithme le plus utilisé aujourd’hui 🔐

chiffrement par bloc de 128 bits
transformations basées sur rotations, substitutions, transpositions, etc.
clé de 128 / 192 / 256 bits
aucune attaque efficace connue contre AES-256

💪 Une attaque brute-force nécessiterait 2²⁵⁶ essais ➜ un nombre gigantesque (78 chiffres…)

🛠️ 4.1.2. Réalisation pratique

⚓︎

1️⃣ Message clair (ASCII → binaire) Exemple : Hello World!

📋 Texte

010010000110010101101100011011000110111100100000010101110110111101110010011011000110010000100001

🌐 Outil : https://www.rapidtables.com/convert/number/ascii-to-binary.html

2️⃣ Clé symétrique Mot choisi : toto

📋 Texte

01110100011011110111010001101111

3️⃣ Chiffrement par XOR 📌 Table XOR :

👉 La clé est répétée jusqu’à atteindre la taille du message :

📋 Texte

  010010000110010101101100011011000110111100100000010101110110111101110010011011000110010000100001
⊕
  011101000110111101110100011011110111010001101111011101000110111101110100011011110111010001101111
  ________________________________________________________________________________________________
  001111000000101000011000000000110001101101001111001000110000000000000110000000110001000001001110

🖥️ Interception par un tiers = texte illisible :

4️⃣ Déchiffrement (chez Bob) Même opération XOR ✅

📋 Texte

  001111000000101000011000000000110001101101001111001000110000000000000110000000110001000001001110
⊕
  011101000110111101110100011011110111010001101111011101000110111101110100011011110111010001101111
  ________________________________________________________________________________________________
  010010000110010101101100011011000110111100100000010101110110111101110010011011000110010000100001

→ Conversion binaire → ASCII : ➡️ ✅ 💬 Hello World!

https://www.rapidtables.com/convert/number/binary-to-ascii.html

📌 Conclusion :

✅ Si P intercepte le message → illisible ✅ Si B possède la clé → message récupéré parfaitement

🧠 Capytale activités : Le code sera fourni par votre enseignant.

🧠 Activité n° 1 — Chiffrement symétrique XOR

👉 Écrire une fonction chiffre(message, masque) qui chiffre (et déchiffre) un message avec un XOR.

🔑 Clé (masque) : Vive la NSI !!
✉️ Message : Je suis en spécialité NSI et j’adore

📌 Conditions : - Convertir le texte et le masque en octets UTF-8 - Répéter le masque sur toute la longueur du message - Appliquer XOR octet par octet - Vérifier que :

📋 Texte

chiffre(chiffre(message, masque), masque) == message

✅ Solution complète (Python)

🐍 Script Python

def xor(caractere_message, caractere_masque):
    return ord(caractere_message) ^ ord(caractere_masque)

def chiffre(message, masque):
    resultat = ""
    taille_masque = len(masque)

    for i in range(len(message)):
        caractere_message = message[i]
        caractere_masque = masque[i % taille_masque]  

        caractere_code = xor(caractere_message, caractere_masque)

        resultat += chr(caractere_code)

    return resultat

masque = "Vive la NSI !!"
message_clair = "Je suis en spécialité NSI et j’adore"


print("Message chiffré :", chiffre(message_clair, masque))

message_chiffre = chiffre(message_clair, masque)
print("Message déchiffré :", chiffre(message_chiffre, masque))



#########################################
# pour aller plus loin : XOR sur octets UTF-8
# version qui gère les accents proprement (base64)

def chiffre(message, masque):
    # Conversion en octets UTF-8
    message_bytes = message.encode("utf-8")
    masque_bytes = masque.encode("utf-8")

    # Répéter le masque à la longueur du message
    masque_long = (masque_bytes * ((len(message_bytes) // len(masque_bytes)) + 1))[:len(message_bytes)]

    # XOR octet par octet
    resultat = bytes([m ^ k for m, k in zip(message_bytes, masque_long)])
    return resultat


# Données
message = "Je suis en spécialité NSI et j’adore"
cle = "Vive la NSI !!"

# Chiffrement
chiffre_msg = chiffre(message, cle)
print("🔐 Message chiffré (bytes) :", chiffre_msg)

# Déchiffrement → appliquer XOR à nouveau
dechiffre_msg = chiffre(chiffre_msg.decode("latin1"), cle)
print("🔓 Message déchiffré :", dechiffre_msg.decode("utf-8"))

# Test automatif
assert dechiffre_msg.decode("utf-8") == message

🔑 4.2. Le chiffrement asymétrique

⚓︎

🧠 4.2.1. Le principe

⚓︎

Exemple :

Alice génère une paire de clés : 🔓 clé publique (diffusée) & 🔑 clé privée (gardée secrète).
Bob récupère la clé publique d’Alice et chiffre son message.
Seule Alice peut déchiffrer avec sa clé privée.

Avantage : même si le message est intercepté, sans la clé privée, il reste illisible. Inconvénients :

Le chiffrement asymétrique est nettement plus lent que le symétrique (on l’utilise surtout pour échanger une clé symétrique).
Chaque destinataire possède sa propre paire de clés ; l’expéditeur doit connaître la clé publique de chaque destinataire.

⚠️ Authentification : pour être sûr de parler au bon destinataire, il faut authentifier la clé publique (certificats, PKI). Sans ça, une attaque de l’homme-du-milieu est possible.

🔄 4.2.2. Échange d’une clé symétrique avec de l’asymétrique — idée de Diffie–Hellman

⚓︎

En 1976, Diffie & Hellman proposent un échange de clé : Alice et Bob construisent ensemble un secret commun sur un canal écouté, sans l’envoyer tel quel.

🧰 Analogie “double cadenas” (commutatif), pour l’idée générale :

Alice met le message 📃 dans une boîte 📦 et met son cadenas 🔒.
Elle envoie 📦🔒 à Bob.
Bob ajoute son cadenas → 📦🔒🔒 (il ne peut pas ouvrir celui d’Alice).
Il renvoie 📦🔒🔒 à Alice.
Alice retire son cadenas → 📦🔒.
Elle renvoie 📦🔒 à Bob.
Bob retire le sien → 📦 ouverte.
Bob lit 📃.

👉 Pour HTTPS, ce “message” est en pratique une clé symétrique 🔐 qui servira ensuite à chiffrer toutes les données (rapide & efficace).

⚠️ Important : l’analogie illustre le principe de “verrous commutatifs”, pas le vrai protocole mathématique (qui s’appuie sur des exposants modulo un grand nombre). Seul, Diffie–Hellman non authentifié est vulnérable au MITM ; HTTPS lève ce risque grâce aux certificats.

🔗 À lire : différences DH / RSA (clé d’accord vs chiffrement). https://www.venafi.com/fr/blog/en-quoi-les-echange-de-cles-diffie-hellman-et-rsa-different-ils

🔐 4.2.3. Exemple d’asymétrique : RSA

⚓︎

📏 Les congruences

30 = 1×24 + 6 → 30 ≡ 6 [24]
53 = 2×24 + 5 → 53 ≡ 5 [24]

🧠 Activité n° 2 — Congruences & PGCD

Compléter les congruences suivantes :

a) 103 ≡ … [24]
b) 13 ≡ … [5]
c) 42 ≡ … [7]

🔢 Rappel : Nombres premiers entre eux - Si PGCD(a, b) = 1 alors a et b sont premiers entre eux - Exemple : 12 et 5 ✅ premiers entre eux
- 33 et 27 ❌ car PGCD = 3

✅ Solution

✏️ On cherche le reste de la division euclidienne :

a) 103 ÷ 24 → 24 × 4 = 96
103 − 96 = 7
✅ 103 ≡ 7 [24]

b) 13 ÷ 5 → 5 × 2 = 10
13 − 10 = 3
✅ 13 ≡ 3 [5]

c) 42 ÷ 7 → division exacte
reste = 0
✅ 42 ≡ 0 [7]

➜ Résultat final : - a) 7 - b) 3 - c) 0

🧠 Activité n° 3 — Nombres premiers avec 12

Lister tous les entiers < 12 qui sont premiers avec 12.

🔎 Rappel : Deux nombres sont premiers entre eux si : - leur PGCD = 1 - ils ne partagent aucun diviseur commun sauf 1

✅ Solution

✏️ On teste les valeurs de 1 à 11 :

PGCD(1,12) = 1 ✅
PGCD(2,12) = 2 ❌
PGCD(3,12) = 3 ❌
PGCD(4,12) = 4 ❌
PGCD(5,12) = 1 ✅
PGCD(6,12) = 6 ❌
PGCD(7,12) = 1 ✅
PGCD(8,12) = 4 ❌
PGCD(9,12) = 3 ❌
PGCD(10,12) = 2 ❌
PGCD(11,12) = 1 ✅

✅ Les nombres premiers avec 12 sont : 1, 5, 7, 11

🧪 Construction RSA

Étape 1. Alice choisit deux nombres premiers p et q. Ici : p = 3, q = 11.

Dans la réalité ces nombres seront vraiment très grands (plus de 100 chiffres).

Étape 2. Calculer n = p × q = 33. La sécurité vient de la factorisation difficile de n.

Alice multiplie ces deux nombres p et q et obtient ainsi un nombre n appelé module de déchiffrement..

😊 Il est très facile pour Alice de calculer n en connaissant p et q.

😢 Il est extrêmement difficile pour Eve de faire le travail inverse : trouver p et q en connaissant n prend un temps exponentiel avec la taille de n.

C'est sur cette difficulté (appelée difficulté de factorisation) que repose la robustesse du système RSA. (Cf. vidéo « chiffrement RSA »)

Étape 3. Clé publique

ϕ(n) = (p − 1)(q − 1) = 20 (indicatrice d’Euler).
Alice choisit un nombre e appelé exposant de chiffrement, qui doit être premier avec 𝝓(n) c'est-à-dire pgcd(e,𝝓(n))=1.

Dans notre exemple, (p −1)(q −1)=20, Alice choisit donc e =3. (mais elle aurait pu aussi choisir 7, 9, 13...).

Le couple (e,n) sera la clé publique d'Alice. Elle la diffuse à qui veut lui écrire.

Clé publique = (e, n) = (3, 33).

Étape 4. Clé privée

Alice calcule maintenant sa clé privée : elle doit trouver un nombre d qui vérifie l'égalité e × d ≡ 1 [ϕ(n)].
Ici, 3 × 7 ≡ 1 [20] → d = 7.
Clé privée = (d, n) = (7, 33).

En pratique, il existe un algorithme simple (algorithme d'Euclide étendu) pour trouver cette valeur d, appelée inverse de e.

Étape 5. Bob chiffre pour Alice (avec clé publique d’Alice)

Message M = 4
clé publique d'Alice : (3,33) → C = \(M^e\) mod n soit \(4^3\) mod 33 = 31.

Cela se note \(4^3\)≡31[33]

Il envoie 31.

Si Eve intercepte cette valeur 31, même en connaissant la clé publique d'Alice (3,33), elle ne peut pas résoudre l'équation \(x^3\)≡31[33] de manière efficace.

Étape 6. Alice déchiffre (avec clé privée)

Clé privée = (d, n) = (7, 33).

M = \(C^d\) mod n

soit \(31^7\) mod 33 = 4 ✅

Pourquoi ça marche ? Par les propriétés d’Euler/Fermat, on montre que M^(ed) ≡ M [n] dès que ed ≡ 1 [ϕ(n)]. 👉 Les rôles publique/privée sont symétriques (signature vs chiffrement).

🔗 Animation : https://animations.interstices.info/interstices-rsa/rsa.html

🧠 Activité n° 4 — Chiffrement RSA

Alice veut écrire à Bob.
Soit le couple de nombres premiers (p, q) avec p = 5 et q = 13.

a) Calculer \(n\) et \(varphi(n)\).
b) Justifier que (9, 65) ne peut pas être une clé publique.
c) Vérifier que (11, 65) est une clé publique (clé publique de Bob).
d) Vérifier que 35 est un inverse de 11 modulo 48.
e) En déduire la clé privée de Bob.
f) Chiffrer le nombre secret d’Alice 17 avec la clé publique de Bob.
g) Déchiffrer le nombre reçu par Bob.

✅ Correction (pas à pas)

a) \(n = p \times q = 5 \times 13 = 65\).

\(\varphi(n) = (p-1)(q-1) = 4 \times 12 = 48\).

b) Une clé publique \((e,n)\) doit vérifier \(pgcd\) \((e,\varphi(n))=1\).

\(pgcd\) \((9,48)=3 \neq 1\) ⇒ (9,65) est invalide.

c) \(pgcd\) \((11,48)=1\) ⇒ (11,65) est valide (clé publique ok).

d) Chercher \(d\) tel que \(e\cdot d \equiv 1 \pmod{48}\).

\(11 \times 35 = 385 \equiv 1 \pmod{48}\) ⇒ 35 est bien l’inverse de 11.

e) Clé privée de Bob : \((d,n) = (35,65)\).

f) Chiffrement de \(M=17\) :

\(C = M^{e} \bmod n = 17^{11} \bmod 65 = \mathbf{23}\).

g) Déchiffrement :
\(M = C^{d} \bmod n = 23^{35} \bmod 65 = \mathbf{17}\) (on retrouve bien le message).

🔐 RSA, un système inviolable ?

Le chiffrement RSA a des défauts (gros entiers ⇒ coût CPU/mémoire). Sa sécurité repose sur la factorisation difficile de (n=pq).

Les tailles recommandées aujourd’hui : 2048 bits (minimum), 3072 bits voire 4096 bits pour une marge supplémentaire (⚠️ 1024 bits est désormais considéré insuffisant).
Il n’existe pas, à ce jour, d’algorithme classique (non quantique) polynomial pour factoriser des entiers de plusieurs centaines/milliers de bits.

Deux menaces théoriques :

la découverte d’un algorithme de factorisation bien plus efficace (classique) ;
l’ordinateur quantique à grande échelle, avec l’algorithme de Shor (et non Schor) permettant une factorisation rapide. → D’où les travaux en cryptographie post-quantique.

🕵️ 4.3. Attaque de l’homme du milieu (MITM)

⚓︎

Alice et Bob croient utiliser la clé de l’autre, mais utilisent en réalité la clé de Jimmy (l’attaquant placé « au milieu »). → MITM : possible si la clé publique n’est pas authentifiée.

🔏 Certification (PKI)

Pour s’en prémunir : une autorité de certification (CA) atteste l’identité du serveur via un certificat. Les navigateurs valident la chaîne de certification avec leur magasin de confiance (et, selon les cas, OCSP/CRL).

🧠 Activité n° 5 — Certificat HTTPS du site de l’Élysée

Aller sur https://www.elysee.fr/
→ cliquer sur le cadenas dans la barre d’adresse
→ Afficher le certificat puis relever : - l’émetteur du certificat (Authority) - le sujet (site concerné) - les dates de validité - l’algorithme de chiffrement - les usages de clé (key usage)

✅ Exemple de réponse (au 23/10/2025)

📌 Les informations peuvent évoluer dans le temps.
À la date de vérification :

Sujet (CN) : www.elysee.fr
Émetteur : R3 - Let's Encrypt
Valide du : 01/10/2025
Valide jusqu’au : 30/12/2025
Algorithme de la clé publique : RSA (2048 bits)
Signature : SHA-256 with RSA
Key Usage :
Digital Signature ✅
Key Encipherment ✅
Extended Key Usage :
TLS Web Server Authentication ✅
TLS Web Client Authentication ✅

🔐 Cela confirme que la connexion HTTPS est chiffrée et authentifiée.

🔐 5. Le protocole HTTPS

⚓︎

🌍 5.1. Principe général

⚓︎

Aujourd’hui, la grande majorité du trafic web est chiffrée 🔒 :

❌ On évite HTTP en clair (contenu lisible/modifiable sur le trajet)
✅ On utilise HTTPS
🔁 HTTPS = HTTP sur TLS
🛡️ TLS (successeur de SSL) assure :
- ✅ l’authentification du serveur (certificat)
- 🔒 la confidentialité
- 🧱 l’intégrité des échanges
- 🔑 l’établissement d’un secret de session (accord de clé)
📡 HTTP transporte ensuite les données chiffrées et authentifiées via un chiffrement symétrique AEAD (souvent AES-GCM ou ChaCha20-Poly1305)

❓ Pourquoi ne pas tout chiffrer en RSA ?
➡️ 🔓 L’asymétrique est trop lent et trop coûteux pour chiffrer de gros flux

✅ Stratégie hybride : - 🔑 Asymétrique → authentification + accord sur un secret de session - 🚀 Symétrique → chiffrer tout le trafic applicatif rapidement

🤝 5.2. (HP) Fonctionnement de TLS — Handshake (moderne)

⚓︎

🧭 Résumé TLS 1.3

💬 ClientHello → versions/suites + paramètres (extensions) + clé éphémère (ECDHE, key_share)
📨 ServerHello → choix des paramètres + clé éphémère du serveur (ECDHE)
🪪 Authentification du serveur (messages typiques) → Certificate (certificat) + CertificateVerify (signature) + Finished
✅ Le client vérifie le certificat, calcule le secret partagé ECDHE puis envoie Finished
🔑 Clés symétriques dérivées du secret via HKDF
🔒 Le trafic HTTP devient chiffré & authentifié (AEAD : AES-GCM / ChaCha20-Poly1305)

🔎 Important : En TLS 1.3, on ne chiffre pas directement une “clé AES” avec la clé publique RSA ❌
→ les clés de session sont dérivées d’un secret partagé ECDHE → HKDF/KDF → clés symétriques ✅

📉 L’échange de clé RSA (historique) est déprécié / supprimé en TLS 1.3 ✅

POUR ALLER PLUS LOIN : Concours Alkindi — https://concours-alkindi.fr/main.html#/pageDiscover

Merci à Gilles Lassus et Mireille Coilhac

🔎 6. Exercices

⚓︎

🧠 Capytale : Le code sera fourni par votre enseignant.

🧩 Exercice n°1 : chiffre_xor

✍️ Objectif :
Écrire en Python une fonction chiffre_xor(msg, cle) qui prend deux chaînes d’octets (bytes) en argument
et qui renvoie le chiffrement XOR du message avec la clé, sous forme d’un objet bytes.

⚙️ Rappel technique : - L’opérateur XOR en Python est ^ - Le XOR fonctionne bit par bit - Pour gérer les lettres accentuées, il faut encoder en UTF-8 avec .encode()

🧪 Vérification du XOR avec le cours :

📋 Texte

>>> xor(0,0)
0
>>> 0^0
0
>>> xor(1,0)
1
>>> 1^0
1
>>> xor(0,1)
1
>>> 0^1
1
>>> xor(1,1)
0
>>> 1^1
0

🔡 Encodage UTF-8 :

📋 Texte

>>> m = "je suis un élève".encode()
>>> print(m)
b'je suis un \xc3\xa9l\xc3\xa8ve'

📌 Utilisation de bytes :

📋 Texte

>>> bytes([65, 66, 67])
b'ABC'

🔑 Indication importante :
Pour un chiffrement XOR, la clé doit être étendue à la longueur du message.
On pourra utiliser intelligemment l’opérateur % dans une compréhension de liste.

✅ Test automatique à réussir :

🐍 Script Python

m = "L'informatique c'est super".encode()
c = "NSI\n".encode()

assert chiffre_xor(m, c) == b"\x02t  5&<>(::8;6i-t,='i=&9+!"
assert chiffre_xor(b"\x02t  5&<>(::8;6i-t,='i=&9+!", c) == b"L'informatique c'est super"

🧩 Exercice n°2 : dechiffre_xor

🔐 Comme expliqué dans le cours :
un chiffrement XOR simple n’est pas sécurisé si la clé est courte ➜ on peut facilement la retrouver.

📌 On dispose d’un message déjà chiffré :

📋 Texte

b'\x0c7,)x8,=#z,+5-/\x99\xf1y69y8774=y(\x9b\xf0*77)=x'

✅ On sait que : - la clé fait exactement 3 caractères - ce sont des lettres majuscules sans accent (A → Z) - les 4 derniers caractères du message en clair sont :

📋 Texte

b"nse!"

👉 tester avec :

🐍 Script Python

mon_test.endswith(b"nse!")

🛠️ Travail demandé : - importer la fonction chiffre_xor de l’exercice précédent - essayer toutes les clés possibles (brute force) - arrêter dès que la bonne clé est trouvée - afficher : - ✅ la clé trouvée - ✅ le message déchiffré - ✅ le temps d’exécution

⏱️ Indication pour mesurer le temps :

🐍 Script Python

import time
debut = time.time()
# code…
print(time.time() - debut, "secondes")

🎯 Objectif pédagogique : → Montrer qu'un XOR avec une clé trop courte = ❌ attaque triviale

🧠 Capytale : Le code sera fourni par votre enseignant.

🔎 7. Projet

⚓︎

Exercice n°01 : clé symétrique :

La situation : Alice veut établir une liaison sécurisée avec Bob en chiffrement symétrique avec la clef kfinale. Mais comment transmettre cette clef à Bob sans que celle-ci ne soit interceptée ?

Etapes du processus : Voici comment Alice et Bob vont procéder :

La clef ne sera jamais "transmise", mais elle sera créée par Bob, et retrouvée par Alice.

1er temps : Alice génère une clef publique (notée kpub) et l'envoie à Bob. Cette clef peut être interceptée mais ce n'est pas grave.

En même temps que la clef publique, elle génère une clef privée (notée kpriv). Les deux clefs sont liées, nous verrons un peu plus tard comment.

2ème temps : Bob génère une clef kfinale qu'il garde secrète et qui servira à chiffrer les échanges avec Alice. Il chiffre cette clef qui devient kFinaleChiffree grâce à kpub qu'il a reçu d'Alice. Il envoie kFinaleChiffree à Alice.
3ème temps : Alice déchiffre kFinaleChiffree avec sa clef privée et trouve kfinale.

kfinale est donc maintenant connue d'Alice et de Bob qui vont pouvoir l'utiliser pour communiquer en chiffrement symétrique.

Lien entre clef publique et clé privée : Notons 𝑓(kpub, m) le message m chiffré avec la clef publique, et 𝑓(kpriv, m) le message m chiffré avec la clef privée.

kpub et kpriv obéissent à :

📋 Texte

𝑓(kpriv, 𝑓(kpub, m)) = 𝑓(kpub,  𝑓(kpriv, m)) = m

En d'autres termes, si Bob chiffre avec la clef publique, Alice saura déchiffrer avec sa clef privée connue d'elle seule. Le système exige aussi que la connaissance de la clef publique ne permette pas de déchiffrer le message envoyé par Bob. C'est le cas quand on chiffre avec des fonctions de hashage, mais ici, pour comprendre le principe, nous allons simplifier et utiliser un chiffrement proche de celui de Vigenère.

Nous admettrons, pour l'exemple, que l'on ne peut pas décrypter le message de Bob avec la clef publique, ni découvrir la clef privée à partir de la clef publique.

1. 1^er temps : Créer la clé publique

Dans notre exemple, on va utiliser un code proche du codage de Vigenere

On génère 10 nombres aléatoire entre 0 et 36 qui seront les décalages à appliquer
On convertit ces nombres en hexa de longueur 2
On concatène pour créer une clef de longueur 20 (mais elle serait très simple à casser !)

nous allons utiliser un alphabet de 36 lettres : [0-9] et [A-Z].

Vous pourrez utiliser la fonction suivante qui convertit un entier (entre 0 et 255) en une chaine hexadécimale de 2 chiffres.

📌 Imports & utilitaires

🐍 Script Python

from random import randint, seed

ALPHA = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def d2H(n: int) -> str:
    """
    convertit un nombre décimal compris entre 0 et 255 en un hexadécimal à 2 chiffres
    :param n: entier à convertir en base 16
    :return: une chaine de caractère représentant le nombre en base 16 sur deux caractères
    >>> d2H(10)
    '0a'
    >>> d2H(100)
    '64'
    """
    h = hex(n)[2:]
    if len(h) < 2:
        h = "0" + h
    return h

# Vérifications demandées
assert d2H(10) == '0a'
assert d2H(100) == '64'

📌 1.1 : création de clé publique — À COMPLÉTER

💻 Ajouter et compléter la fonction creCle()

Voici son fonctionnement :

On génère 10 nombres aléatoires entre 0 et 255.
On convertit ces nombres en hexadécimal de longueur 2, en utilisant la fonction d2H
On concatène pour créer une clef de longueur 20. Les lettres devront être converties en majuscules.

Cette clef serait très simple à casser, mais nous étudions ici seulement le principe.

🐍 Script Python

from random import randint

def creClef() -> str:
    """ Version 1 : renvoie une seule clé publique (20 caractères hex en MAJ) 
    Crée un clef de chiffrement composée de 20 caractères 
    parmi ceux-ci : 0, 1, 2, ..., 9, A, B, C, D, E, F
    :return: renvoie 20 caractères de 0, 1, 2, ..., 9, A, B, C, D, E, F
    Par exemple : 'C5D71484F8CF9BF4B76F'
    C5 représente 197, D7 représente 215 etc...
    """
    pass  # ← compléter ici

print(creClef())

Aide : on pourra utiliser join() et upper()

Tests aléatoires ― À COMPLÉTER

🐍 Script Python

for _ in range(3):
    print(creClef())

📌 1.2. Vérification avec seed() :

🤔 Pour tester notre fonction, comment obtenir des nombres "aléatoires" toujours identiques? En fait random crée des nombres "pseudos-aléatoires". Si on lui donne une initialisation a avec seed(a) , les nombres générés seront toujours identiques.

Par défaut l'initialisation se fait avec la date actuelle, qui change tout le temps ..

🐍 Script Python

for i in range(5):
    print([randint(0, 255) for i in range(10)])

On utilise une initialisation, par exemple seed(0)

🐍 Script Python

from random import seed
for i in range(5):
    seed(0)
    print([randint(0, 255) for i in range(10)])

Nous aurions pu en choisir une autre, par exemple seed(42)

🐍 Script Python

from random import seed
for i in range(5):
    seed(42)
    print([randint(0, 255) for i in range(10)])

Que remarquez vous ?

😀 Nous pouvons donc tester notre fonction !

Ajouter

🐍 Script Python

from random import seed
seed(0)
assert creClef() == 'C5D71484F8CF9BF4B76F'

📌 Partie 2 : création de (clé publique, clé privée)

🔑 Il faut aussi créer une clef privée, liée à la clef publique. Dans notre exemple, le processus de création de la clef est très simple, et la conversion en hexadécimal est totalement factice. Il ne s'agit, comme dans le chiffrement de Vigenère, que d'appliquer un décalage variable des lettres. Pour les 10 premières lettres, le décalage est codé dans la clef, pour la 11ème on reprend le décalage de la 1ere, et ainsi de suite.... c'est ce qu'avait imaginé Vigenère.

❓ Comment faire ?

Pour créer une clef qui permette de respecter :

📋 Texte

𝑓(kpriv, 𝑓(kpub, m)) = 𝑓(kpub,  𝑓(kpriv, m)) = m

il suffit de créer les décalages qui compensent.

Rappelons que nous allons utiliser un alphabet de 36 lettres :

📋 Texte

ALPHA = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'

Par exemple, si on décale vers la droite de 12 (%36), il suffit de décaler encore de 36 - 12 = 24, en bouclant au début de l'alphabet, pour "retomber" sur le même caractère.

On pourrait donc choisir un décalage dPriv = 36 - dPub % 36 .

Pour "compliquer", on peut choisir également comme décalage dPriv = 36 - dPub % 36 + randint(1, 6) * 36 En effet, cela ne changera rien d'ajouter un décalage d'un nombre entier de fois 36. (On se limite à randint(1,6) pour que le nombre soit possible à coder en hexadécimal sur deux caractères).

Voilà comment procéder pour créer la clef privée :

📋 Texte

pour chaque décalage dPub de la clef publique :
    dPriv = 36 - dPub % 36 + randint(1, 6) * 36 
    coder dPriv en hexa2
concaténer les hexa2(dPriv) en une chaine

💻 Ajouter et compléter la fonction creClef()

Attention, elle doit renvoyer un tuple (clef publique, clef privée)

🐍 Script Python

def creClef() -> tuple:
    """
    creClef doit renvoyer un tuple avec les 2 clefs: la publique et la privée
    Exemple renvoyé:
    ('47904730804B9E3225A9', '91D82584A08DCAEE6BBF')
    """
    pass  # ← compléter ici

print(creClef())

📌 Partie 3 — Lecture des décalages

Tester ci-dessous

Prenons un exemple kpub = '48E52E29A3FA379A953F'

Le premier décalage est codé par les deux premiers caractères 48, qui en décimal et modulo 36 sera :

🐍 Script Python

int('48', 16) % 36

Le second est E5

🐍 Script Python

int('E5', 16) % 36

Si la clef privé est kpriv = 'D883116D359FEC5CED375', les deux premiers décalages sont :

🐍 Script Python

print('D8 -> d = ',int('D8',16) % 36)
print('83 -> d = ',int('83',16) % 36)

Dans l'exemple ci-dessus, la somme des décalages

pour le 1er caractère vaut : 0 + 0 = 0
pour le 2ème caractère vaut : 13 + 23 = 36
On pourrait ainsi vérifier que pour n'importe quel caractère, la somme des décalages est égale à 0 ou à 36, ce qui, modulo 36, fait toujours 0.

L'application de kpriv compensera donc l'application de kpub, ce qui assure la condition !

Ajouter le script suivant au fichier echange_cle.py.

Pour bien comprendre, voici comment retrouver les décalages en lisant les clés :

🐍 Script Python

# le code ci-dessous vous montre comment retrouver les décalages en lisant les clefs
# la fonction decal(clef, i) convertit la tranche clef[i:i+2] en décimal
(kpub, kpriv) = creClef()
print('clef publique :', kpub, '\t clef privée :', kpriv)

def decimal_tranche_i(clef, i):
    return int(clef[i:i + 2], 16)

for i in range(0, 20, 2):
    dPub = kpub[i:i + 2]
    dPriv = kpriv[i:i + 2]
    dPub_dec = decimal_tranche_i(kpub, i)
    dPriv_dec = decimal_tranche_i(kpriv, i)
    print(dPub, dPriv, dPub_dec, dPriv_dec)
    assert (dPub_dec + dPriv_dec) % 36 == 0

📌 Partie 4 — Clé symétrique de Bob

💻 Ajouter et compléter la fonction qui va être utilisée pour créer une clef de chiffrement symétrique kfinale

🐍 Script Python

def creeKFinale() -> str:
    """
    crée un mot de 20 lettres dans ALPHA (chiffrement symétrique)
    :return: par exemple 'KFIBCB2GU458925YPXHX'
    """
    pass  # ← compléter

print(creeKFinale())

seed(0)
assert creeKFinale() == 'OQ2GWVPJUMDW8I86GY9J'

Bob doit maintenant chiffrer cette clef finale avec la clef publique d’Alice.

📌 Partie 5 — Calcul des décalages

Il nous faut donc une fonction f(k, m) qui chiffre un message m avec une clef k.

Nous aurons besoin de la fonction ci-dessous à ajouter au fichier :

🐍 Script Python

def decal(clef: str) -> list:
    """
    :param clef: chaîne de 20 caractères parmi 0, 1, 2, ..., 9, A, B, C, D, E, F
    Par exemple : 'C5D71484F8CF9BF4B76F'
    :return: liste de 10 entiers qui correspondent aux décalages en décimal à 
    appliquer dans le chiffrement modulo 36
    >>> decal('C5D71484F8CF9BF4B76F')
    [17, 35, 20, 24, 32, 27, 11, 28, 3, 3]
    En effet C5 correspond à 197 en décimal, et 197 % 36 = 17
    """
    return [int(clef[i:i+2], 16) % 36 for i in range(0, len(clef), 2)]

📌 Parie 6 — Fonction f(k, m)

Principe de la fonction f(k, m) :

Cette fonction chiffre le message m par le principe du chiffrement de Vigenère avec la clef k.

📋 Texte

f respecte f(kpriv, f(kpub,m)) = m.

Elle est cependant très basique : elle effetue un décalage des lettres conforme à la clef... C'est un décodage de Vigenère dont la clef serait publique donc trivialement cassée.

💻 Ajouter et compléter la fonction avec :

- On définit ALPHA : chaîne des caractères possibles utilisés.

- On convertit la clef en une liste de décalages avec la fonction decal

- On initialise m_chiffre = ""

- pour chaque ième caractère de m :

déterminer son rang dans ALPHA : rang = ALPHA.index(lettre)
déterminer decaler_dele decalage à appliquer à rang. Il s'obtient pour la lettre de rang i de la clef. La clef étant plus courte que m, on boucle sur la clef. Le décalage est donc pour le rang i : decaler_de = decalages[i % len(decalages)]
déterminer idx qui est l'indice dans ALPHA du caractère chiffré.

- idx = (rang + decaler_de) % 36

📋 Texte

- ajouter à m\_chiffre le caractère chiffré correspondant à idx

- renvoyer m_chiffre

🐍 Script Python

# Bob chiffre la clef finale
def f(k: str, m: str) -> str:
    """
    Cette fonction chiffre le message m par le principe du chiffrement de 
    Vigenère avec la clef k.
    :param k: clef qui sert au chiffrement (on boucle la clef sur la longueur de m)
    :param m: message à chiffrer
    :return: le message chiffré
    >>> f("00000000000000000000", "CLE2CHIFFRER")
    'CLE2CHIFFRER'
    >>> f("C5D71484F8CF9BF4B76F", "CLE2CHIFFRER")
    'TKYQ88T7IUVQ'
    """
    pass  # ← compléter ici

assert f("00000000000000000000", "CLE2CHIFFRER") == 'CLE2CHIFFRER'
assert f("C5D71484F8CF9BF4B76F", "CLE2CHIFFRER") == 'TKYQ88T7IUVQ'

📌 Partie 7 — Scénario Alice ↔ Bob

💻 Ajouter et compléter le scénario :

😀 Nous avons maintenant tout ce qu'il nous faut, l'échange peut avoir lieu.

📅 Nous allons reprendre nos 3 temps expliqués dans les étapes du processus au début de ce TP.

🧗 Le déroulé est donné ci-dessous, les seules information qui peuvent être interceptées sont présentées décalées à droite :

1^er temps :

🐍 Script Python

# Création des clef publique et privée
(kpub,kpriv) = creClef()
print('Alice crée une clef publique :', kpub)
print('clef privée associée :', kpriv)

kfinale = ???  # ← compléter
kFinaleChiffree = ???  # ← compléter

print("Alice obtient :", ???)  # ← compléter
assert ??? == kfinale  # ← compléter

😀 Le tour est joué ! Alice et Bob connaissent la clef kFinale, il vont pouvoir communiquer en utilisant un chiffrement symétrique !

📌 Partie 8 — Chiffrement symétrique

Maintenant Alice et Bob vont communiquer avec cette clef échangée kfinale.

Ajouter les scripts suivants. Ils vont utiliser le chiffrement symétrique de Vigenère du TP précédent, dont on donne ci-dessous un script :

🐍 Script Python

def chiffrement_Vigenere(k: str, m: str, sens: int) -> str:
    """
    Chiffre ou déchiffre le message m avec la clef k
    :param k: la clef de chiffrement
    :param m:  le texte à chiffrer
    :param sens: sens = 1 pour le chiffrage et sens = -1 pour le déchiffrage
    :return: la fonction renvoie le texte chiffré ou déchiffré suivant le sens choisi: type str.
    Par exemple :
    >>> chiffrement_Vigenere('bizare', 'abominable', 1)
    'ucgfskucdx'
    >>> chiffrement_Vigenere('bizare','ucgfskucdx', -1)
    'abominable'
    """
    m_chiffre = ""
    for i in range(len(m)):
        code = ord(m[i])
        decal = sens * ord(k[i % len(k)])
        if 65 <= code <= 90:
            code = ((code + decal) - 65) % 26 + 65
        elif 97 <= code <= 122:
            code = ((code + decal) - 97) % 26 + 97
        elif 32 <= code <= 64:
            code = ((code + decal) - 32) % 33 + 32
        m_chiffre += chr(code)
    return m_chiffre

Alice veut demander à Bob son mot de passe (qui est "bRa1cAPStp3").

Bob chiffre donc son mot de passe avec kfinale qu'ils connaissent maintenant tous les deux, puis l'envoie :

🐍 Script Python

mdp_chiffre = chiffrement_Vigenere(kfinale,'bRa1cAPStp3',1)
print("Bob envoie 'bRa1cAPStp3' chiffré avec kFinale -> ", mdp_chiffre)

Alice déchiffre le mdp reçu avec kfinale:

🐍 Script Python

mdp_clair = chiffrement\_Vigenere(kfinale,mdp_chiffre,-1)
print('Alice déchiffre avec kfinale ->', mdp_clair)

🌞 Mission réussie !

📌 Partie 9 — Attaque MITM (Jimmy)

Alice et Bob sont habitués à procéder comme nous venons de le voir. Bob va donc créer kFinale qui va leur servir pour communiquer en chiffrement symétrique.

💣 Mais Jimmy va un peu changer les données du problème. Pour communiquer, Alice et Bob envoient des paquets qui transitent sur de nombreux routeurs. L'un d'eux appartient à Jimmy....

🦸‍♂️ Dans ce qui suit, vous êtes Jimmy.

💻 Ajouter et compléter le scénario :

1) 👩 Tout commence comme d'habitude : Alice crée une clef publique et une clef privée :

🐍 Script Python

# # créez les clef publiques et privées d'Alice :
(kpubAlice, kprivAlice) = creClef()

print("clé publique de Alice :", ❓)
print("clé privée de Alice :", ❓)

2) 👩 Alice envoie à Bob la clé publique Du moins, c'est ce qu'elle pense. Elle ignore votre présence ...

3) 🦸‍♂️ Mais... Vous intervenez ... Vous interceptez l'envoi. Vous n'allez pas envoyer cette clef à Bob mais une autre : la votre !

🐍 Script Python

# créez votre clef publique et votre clef privée associée
(kpubJimmy, kprivJimmy) = creClef()

print('clé publique de Jimmy :', ❓)
print('clé privée de Jimmy :', ❓)

Vous avez une clef publique et une clef privée. Vous envoyez votre clef publique à Bob, qui pensera qu'il s'agit de la clef publique d'Alice.

4) 👨 Bob ne se doute de rien !

Bob chiffre kFinale (la clé finale) avec cette clé publique qu'il vient de recevoir, et envoie cette clé chiffrée à Alice (où du moins, c'est ce qu'il pense. Mais vous êtes là...)

La clé finale crée par Bob est : '0VLFK4CEF9YS55KWV6JZ'

Créez la clé finale chiffrée avec votre clé publique (celle que Bob imagine être la clé de Alice)

🐍 Script Python

kFinale = "0VLFK4CEF9YS55KWV6JZ"
# codez cette clef avec la clé publique de Jimmy (Bob croit qu'il s'agit de celle de Alice)
kfinaleChiffreBob = ❓
print('Bob envoie sa clé privé chiffrée avec la clé publique de Jimmy :', kfinaleChiffreBob)

5) 🦸‍♂️ Vous interceptez cette clef !

Vous déchiffrez cette clef interceptée grâce à votre clef privée :

Vous obtenez donc kFinale_decryptee.

🐍 Script Python

kFinale_decryptee = ❓
print(kFinale_decryptee)

🦸‍♂️ Sans surprise, vous voyez que vous détenez bien la clé finale.

En effet kFinale_decryptee que vous avez reconstituée est bien égale à kFinale créée par Bob.

6)🦸‍♂️ Vous faites comme si vous étiez Bob !

Vous allez maintenant chiffrer kFinale_decryptee avec la clé publique d' Alice, et lui envoyer.

🐍 Script Python

# Créez la clé finale chiffrée avec la clé d'Alice :
kfinaleChiffreAlice = ❓

print("Jimmy envoie la clé privée de Bob chiffrée avec la vraie clé publique d'Alice :", kfinaleChiffreAlice)

7) 👩 Alice reçoit cette clef et la déchiffre avec sa clé privée.

🐍 Script Python

print(f(kprivAlice, kfinaleChiffreAlice))

Elle obtient kFinale la bonne clé créée par Bob, et ils vont l'utiliser pour communiquer.

8) 👩🦸‍♂️👨Tous les échanges ultérieurs seront interceptés et décryptés par Jimmy !

Ni Alice ni Bob ne se doute que Jimmy bad boy connait aussi la clé kFinale...

👍 Bravo, vous avez réussi une attaque par l'homme du milieu.

🧩 Exercice n° 02 : chiffrement RSA

SUR THONNY

1 - PRINCIPE DU CRYPTAGE ASYMÉTRIQUE

Il y a eu plusieurs types de systèmes de chiffrement asymétrique. Nous ne verrons que la version qui correspond à la version actuelle de ce type de système : le système RSA.

Il comporte un clé Publique et une clé Privée dont voici le principe.

La clé Publique ne permet pas de décrypter les messages cryptés avec la clé Publique.
La clé Privée ne permet pas de décrypter les messages cryptés avec la clé Privée.
On peut décrypter avec la clé Privée les messages cryptés à l'aide de la clé Publique.
On peut décrypter avec la clé Publique les messages cryptés à l'aide de la clé Privée.

principe du chiffrement asymétrique

L'une des conditions de l'utilisation d'un tel chiffrement : qu'on ne puisse pas retrouver la valeur de la clé privée connaissant la valeur de la clé privée ou d'un message crypté quelconque. Il faut que cela soit trop compliqué et demande trop de temps ou qu'il existe beaucoup de valeurs possibles par exemple.

RSA est basé sur le principe des fonctions à sens unique : connaissant le message m, il est facile de chiffrer le message en calculant f(m) mais connaissant f(m) il est "difficile" de retrouver m. La notion de complexité algorithmique donne un moyen de quantifier la notion sinon floue de "difficile".

En outre, RSA utilise des fonctions à sens unique possédant une brèche : connaissant la clé de déchiffrement, il devient "facile" de retrouver m connaissant f(m).

Là où c'est compliqué à mettre en place, c'est que trouver la brèche doit s'avérer "impossible" en un temps raisonnable.

2 - RSA

Le chiffrement RSA date de 1977 et doit son nom aux initiales de ses trois inventeurs :

Ronald Rivest (né en 1947, cryptologue américain)
Adi Shamir (né en 1962, mathématicien et cryptologue israélien)
Leonard Adleman (né en 1945, chercheur américain en informatique théorique, et en informatique-biologie moléculaire)

RSA a été breveté par le MIT (Massachusetts Institute of Technology) en 1983 aux États-Unis.

Le brevet a expiré le 21 septembre 2000.

Le cryptage RSA utilise de grands nombres premiers et le petit théorème de Fermat (lié à la division entière et à la congruence).

La facilité du cryptage et la difficulté du décryptage sont liées au fait qu'il est facile de calculer le produit n = p*q de deux nombres premiers p et q mais qu'il est difficile de retrouver p et q si on ne connaît que n.

Vous allez donc comprendre l'intérêt qu'on porte aux nombres premiers et aux diviseurs communs.

Division entière ou euclidienne

Nous avons déjà vu la division euclidienne et la notion de reste.

Si a = b*q + r alors

La division euclidienne de a par b donne q : a // b = q .
Le reste de cette division entière est alors r : a % b = r avec r dans [0;b[ .

Exemple

Si on prend 15, on peut écrire que 15 = 2*6 + 3 .

La division euclidienne de 15 par 6 donne 2 : 15 // 6 = 2 .

Le reste de cette division est de 3 : 15 % 6 = 3 .

Congruence

La notion de congruence (hors programme en NSI, on ne l'aborde ici qu'en terme de culture générale) est liée à ce reste.

Exemples sans définition exacte

0, 6, 12, 18, 24, 30... sont congrus modulo 6 entre eux car le reste de leur division euclidienne par 6 donne un reste de 0 à chaque fois.

1, 7, 13, 19, 25, 31... sont congrus modulo 6 entre eux car le reste de leur division euclidienne par 6 donne un reste de 1 à chaque fois.

2, 8, 14, 20, 26, 32... sont congrus modulo 6 entre eux car le reste de leur division euclidienne par 6 donne un reste de 2 à chaque fois.

etc. ...

Définition

Soient

n un entier naturel non nul et,
a et b deux entiers relatifs.

On dit que a et b sont congrus modulo n s'ils ont le même reste dans une division euclidienne par n.

En Python, on peut donc écrire a % n == b % n .

On dit aussi que a est congru à b modulo n .

Notation mathématique

La notation mathématique est a ≡ b (mod n) pour signaler que a et b sont congrus modulo n .

Exemple

156 = 17*9 + 3 . Donc 156 % 17 donne un reste de 3 .
105 = 17*6 + 3 . Donc 105 % 17 donne un reste de 3 .
On peut donc écrire que 156 ≡ 105 (mod 17) pour dire que 156 est congru à 105 modulo 17.

Conséquence

On remarquera que a ≡ b (mod n) implique que (a-b) est divisible par n :

En Python : (a-b) % n == 0

Ou encore : (a-b) // n == k avec k entier.

156 ≡ 105 (mod 17) implique que (156-105) / 17 donne un résultat entier.

En Python : (156-105) / 17 = 51 / 17 = 3.0

Exemple d'utilisation

La Clé Publique est un n-uplet cpub = (n, e) contenant deux informations notées n et e.

Sur notre exemple, nous prendrons cpub = (2159, 437)

Si m est un bout du message à chiffrer, on obtient le message chiffré mc correspondant en utilisant cette formule :

mc = (m^e) % n

n se nomme le module de chiffrement car il sert à faire un modulo et
e est l'exposant de chiffrement car on l'utilise en tant que mise à la puissance du message.

En Python, ça donnera :

mc = (m**e) % n

La Clé Privée est un n-uplet cpri = (n, d) contenant

le module de chiffrement n et
l'exposant de déchiffrement d.

Si mc est un bout du message chiffré, on obtient le message déchiffré md correspondant en utilisant cette formule :

md = (mc^d) % n

Bien entendu, si les valeurs sont correctes, on aura md = m !

Pour notre exemple, nous prendrons (pas par hasard !) cpri = (2159, 1181) .

On la gardera secrète de façon à être le seul à pouvoir déchiffrer les messages chiffrés avec la Clé Publique.

2.1. On désire transmettre par exemple 500 et 1000 de façon cryptée. Calculer les deux messages mc à envoyer après application basique du chiffrement sur 500 et 1000 avec cpub = (2159, 437) .

mc = (m**e) % n

2.2. Que va donner le chiffrement d'un message valant 6000 ?

2.3. La personne ayant émis la clé publique reçoit le message suivant : 504 - 1746 - 900. Sa clé privée (tenue secrète) est cpri = (2159, 1181) .

Comment retrouver le message déchiffré ?

Limitation du message chiffré par rapport au module de chiffrement n

La valeur de n permet d'obtenir la plage des valeurs qui seront déchiffrables : les valeurs m à chiffrer doivent impérativement être dans l'intervalle [0,n[ ou [0,n-1], sinon on ne peut parviendra pas à déchiffrer correctement la valeur initiale.

Ici puisque n = 2159, cela veut dire qu'on ne peut chiffrer que des valeurs comprises entre 0 et 2158.

Attention, certaines valeurs ont un chiffrement assez problématique :

Les deux premières valeurs (0 et 1) et la dernière valeur (2158) posent problème :

📋 Texte

>>> (0**437) % 2159
0        Un peu inutile car on retrouve le message de base...

>>> (2159**437) % 2159
0        Inutile car on obtiendra 0 en déchiffrant !


>>> (1**437) % 2159
1        Pas vraiment un chiffrement...

>>> (2158**437) % 2159
2158        Pas vraiment un chiffrement...

Entre 2 et 2157, ça fonctionne correctement :

📋 Texte

>>> (2**437) % 2159
389

>>> (2157**437) % 2159
1770

Principe d'un vrai chiffrement

Le vrai chiffrement se fait sur un bloc d'octets en réalité sinon, on transforme simplement une valeur comprise entre 0 et 255. C'est problématique dans le cas d'un texte car il suffit alors de connaître la fréquence du "e" dans la langue utilisée, et on pourrait retrouver assez facilement la valeur chiffrée du "e".

On considère donc plutôt un encodage basé sur un ensemble d'octets et pas un octet unique.

On pourrait par exemple vouloir transmettre le string "AB" qui va se retrouver encodé en deux octets YZ: Y = 65 suivi de Z = 66 en ASCII.

On va alors considérer que le message m à envoyer est 65*256 + 66, soit 16706.

Dans ce cas, il faut donc que n soit supérieur à 255*256 + 255, 65535. Il faut donc un module de chiffrement n au moins égal à 65536...

C'est logique, 2 octets correspondent à 16 bits, 2¹⁶ possibilités, donc 2¹⁶ - 1 pour la valeur maximale en entier naturel.

Puisque n = p * q, les nombres premiers p et q ne doivent donc pas être trop petits à cause de cela également.

Une autre technique courante consiste à utiliser des permutations d'octets par exemple. Mais le but ici n'est pas de faire un exposé sur les implémentations réelles de RSA.

2.4. Quelle doit être la valeur minimale du module de chiffrement si on veut envoyer des blocs chiffrés de 4 octets ?

2.5. Peut-on utiliser des blocs de deux octets avec nos clés ?

2.6. Envoyer le message "Bonjour à tous" en utilisant simplement UNICODE : on chiffre chaque caractère directement par sa valeur unicode.

On utilisera les clés fournies dans cette activité.

On peut trouver les valeurs unicode des caractères en utilisant la fonction native de Python ord :

📋 Texte

>>> ord('A')
65

>>> chr(65)
'A'

Attention à l'espace, qui est bien un caractère en lui-même.

Créer une fonction Python pour trouver la valeur UNICODE et une fonction Python pour renvoyer la valeur chiffrée pourrait vous simplifier la vie...

3 - DÉTERMINATION DES CLÉS RSA

Le principe de l'utilisation étant posé, regardons comment déterminer les clés.

Etape 1 : choisir deux nombres entiers p et q

Assez facile.

Pour notre exemple, nous prendrons par exemple p = 17 et q = 127 .

Attention, pour obtenir des clés réellement utilisables, il faut prendre de très grands nombres premiers !

Etape 2 : calculer le module de chiffrement n

Facile, c'est une multiplication.

n = p * q

Cette valeur sera transmise à la fois dans la clé publique et la clé privée.

La valeur de n n'est donc pas d'une donnée secrète. Par contre, les valeurs de p et q devront être dissimulées.

Avec nos valeurs de test, on obtient n = 17 * 127 , soit n = 2159 .

Ce nombre n'est pas un nombre premier, puisqu'il est décomposable.

Néanmoins, c'est bien de là que vient la "difficulté" du retour en arrière : si on vous donne un n très grand, on ne pourra pas retrouver p et q en un temps raisonnable.

Avec n = 2159 , ce n'est pas très difficile ok.

Avec n = 35823194494940926873 , c'est déjà plus diffile, non ?

Et encore, ce nombre n'est pas si grand que cela puisqu'il ne nécessite que 65 bits pour être encodé :

📋 Texte

>>> n = p*q
>>> n
35823194494940926873

>>> bin(n)[2:]
'11111000100100101100011011001011111111110101011101101001110011001'

>>> len(_)
65

>>> p
3875804809

>>> q
9242775697

Si on prend un nombre n beaucoup plus grand, cela va forcément être encore plus diffile. Pour information, le nombre de bits de n est directement lié aux nombres de bits de p et q :

📋 Texte

>>> len(bin(p)[2:])
32

>>> len(bin(q)[2:])
34

Prendre des nombres p et q de 1000 bits chacun, et tout de suite ça vous donne une idée de la difficulté à retrouver p et q connaissant n.

Taille de la clé asymétrique

Actuellement (2021), on considère que les clés asymétriques basées sur un nombre n de 2048 bits sont valables en terme de sécurité jusqu'en 2030. Au delà, on conseille d'augmenter le nombre de bits car la puissance de calculs aura bien évolué. Est-ce à dire que les clés asymétriques de 1024 bits ne sont plus sécurisées ? Tout dépends de ce que voulez protéger. Augmenter le nombre de bits, augmente en effet le temps d'exécution du chiffrement/déchiffrement.

En effet, contrairement au cas symétrique (où avec 128 bits, on a vraiment presque 2¹²⁸ valeurs possibles), une clé asymétrique de 128 bits ne présente qu'une seule factorisation possible. Cela restreint fortement le nombre de possibilités à tester. Il faut donc augmenter la taille de la clé.

Comment obtenir un nombre n sur 2048 bits

Le plus simple est d'avoir deux nombres premiers p et q de 1024 bits chacun.

Etape 3 : calculer indicatrice d'Euler φ

Etape facile, c'est un simple calcul.

φ = (p-1) * (q-1)

Ici, on obtient φ = (17-1) * (127-1) , soit φ = 2016 .

Etape 4 : choisir l'exposant de chiffrement e

Cette étape est plus délicate à réaliser. Nous allons voir qu'il va falloir utiliser l'algorithme d'Euclide.

Sans un bon algorithme, cette simple recherche peut prendre du temps.

Ce exposant de chiffrement e doit être

1. un entier inférieur à φ 2. premier avec φ : e ne doit pas partager de diviseur commun avec φ , d'où l'algorithme d'Euclide.

Ici, on a φ = 2016 et on ne pourrait pas prendre e = 2014 car 2016 et 2014 sont divisibles par 2.

On peut décomposer 2016 de cette façon : 2016 = 2⁵ * 3² * 7 : 2, 3 et 7 sont donc les diviseurs à ne pas prendre pour e.

Il suffit donc de prendre un nombre e qui ne soit divisible ni par 2, ni par 3, ni par 7.

Prenons par exemple e = 19 * 23 , soit e = 437 .

Il existe donc de nombreuses valeurs admissibles de e. Ces valeurs dépendent de φ et donc uniquement indirectement de p et q. Le principe est de ne pas permettre à quelqu'un connaissant la clé publique (donc e) d'obtenir d'indice supplémentaire sur les valeurs possibles de p et q.

Etape 5 : trouver l'exposant de déchiffrement d (connaissant e et φ)

Ce exposant de déchiffrement d doit être l'inverse de e modulo φ.

Cela veut dire qu'il faut respecter cette condition : le reste de la division entière de (e*d) par φ vaut 1.

(e * d) % φ = 1

D'où la notion d'inverse "e = 1 / d".

Dans le cas de notre exemple :

Indicatrice d'Euler φ = 2016
Exposant de chiffrement e = 437
on détermine que l'exposant de déchiffrement est d = 1181

Vérification avec Python :

📋 Texte

>>> e = 437
>>> d = 1181
>>> phi = 2016
>>> (e*d) % phi
1

Cette fois, il faudra utiliser l'algorithme d'Euclide étendu. Sinon, encore une fois, cela prendrait un temps énorme pour p et q de grande taille.

Trouver d ?

Pour déterminer d, il faut connaître e (facile, c'est dans la clé publique) et φ (non connue car cette valeur n'est pas publiée). Or pour connaître φ, il faut parvenir à retrouver p et q à partir de n ! C'est donc difficile algorithmiquement.

On vient donc bien de dire que connaître la clé publique (n ,e) ne permet pas de trouver facilement la clé privée ou secrète (n, d).

4 - TP PYTHON - VÉRIFIER LA PRIMALITÉ D'UN ENTIER

Le but de cette activité est d'automatiser tout cela pour générer une clé privée et une clé publique automatiquement.

Il ne s'agit pas de réaliser une véritable implémentation de RSA permettant de générer une clé de 2048 bits ! Juste de manipuler un peu le système pour voir qu'il fonctionne et que manipuler des grands nombres nécessite de faire attention à nos algorithmes, sinon c'est looooooooooong.

4.7. Installer matplotlib.

Nous allons devoir trouver deux nombres premiers.

Il va donc falloir vérifier qu'un entier donné est un nombre premier ou pas. Une tâche pas trop compliqué si ce nombre est petit mais un calcul qui devient de plus en plus long lorsque le nombre devient important.

Nombre premier

Définition : un nombre premier est un nombre entier naturel qui n'est divisible que par 1 et par lui-même.

Exemples :

5 est premier car il n'est divisible que par 1 et 5.
6 n'est pas premier car il est divisible par 1, 2, 3 et 6.
7 est premier car il n'est divisible que par 1 et 7.
8 n'est pas premier car il est divisible par 1, 2, 4 et 8.

Les nombres premiers inferieurs à 100 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,67,71, 73, 79, 83, 89 et 97.

Jusque là, tout va bien.

Mais comment faire pour un nombre de grande taille, disons 170141183460469231731687303715884105727 ?

Une version naïve d'une fonction vérifiant si un nombre est premier est donc de vérifier qu'il ne soit pas divisible par l'un des entiers qui lui sont strictement inférieurs (à part 1).

Algorithme le plus brute et naïf qui soit

On tente de diviser x un par un par tous les nombres entiers dans [2;x[.

La version avec un while :

🐍 Script Python

def est_premier_v1(x):
    '''Fonction très naïve qui recherche si un nombre est premier par force brute'''
    assert type(x) == int
    d = 2
    while x % d != 0:  # tant que d n'est pas un diviseur de x
        d = d + 1
    if d < x:  # on a rencontré un diviseur avant d'atteindre x
        reponse = False
    else:
        reponse = True
    return reponse

La version avec un for :

🐍 Script Python

def est_premier_v1(x):
    '''Fonction très naïve qui recherche si un nombre est premier par force brute'''
    assert type(x) == int
    for d in range(2, x, 1):
        if x % d == 0:  # si d est un diviseur de x
            return False  # On vient de rencontrer un diviseur
    return True  # Nous n'avons pas rencontré de diviseur

Prenons le cas de 18. On voit bien que pour tester la primalité, il suffira de le diviser par deux et c'est plié : le reste est nul.

4.8. Première question : un nombre (et donc pair) peut-il être divisible par 4, 8, 16... sans être divisible par 2 ?

Deuxième question : une fois qu'on a vérifié la division par 2, quels sont les prochains diviseurs à tester ?

4.9. Fichier est_premier.py ! Version avec un peu d'algorithmique : modifier la fonction (version avec while) de façon à ce qu'elle renvoie bien la bonne réponse mais en utilisant le petit truc de la parité :

Si x est égal à 2 : on renvoie True.
Sinon si x est pair : on renvoie False.
Sinon : on effectue la boucle TANT QUE mais cette fois, on commence à 3 et on augmente de 2 pour ne prendre que les nombres impairs.

Prenons le cas de 100. Voici les différentes façons de décomposer 100 (qui n'est pas premier)

100 = 1 * 100
100 = 2 * 50
100 = 4 * 25
100 = 5 * 20
100 = 10 * 10.

Au delà de la racine de 100, 10, on va donc retrouver les mêmes valeurs mais en inversant leur ordre :

100 = 20 *5
100 = 25 * 4
100 = 50 * 2
100 = 100 * 1

Prenons le cas de 103. Sa racine vaut approximativement 10.14889156509222. Pour savoir s'il est premier, il est inutile de chercher un diviseur éventuel supérieur à 10 :

- soit on trouve un diviseur inférieur à 10 et on saura que 103 n'est pas premier.

103 % 2 = 1 car 103 = 2 * 51 + 1
103 % 3 = 1 car 103 = 3 * 34 + 1
103 % 5 = 3 car 103 = 5 * 20 + 3
103 % 7 = 5 car 103 = 7 * 14 + 5
103 % 9 = 4 car 103 = 9 * 11 + 4

- il est inutile de continuer : il faudrait écrire 11 * quelque chose de supérieur à 10 sinon nous l'aurions trouvé avant ! Or, même 10*11 donne 110 donc quelque chose de supérieur à 103...

Trouver un diviseur avec la racine

Pour un nombre x, s'il existe un diviseur supérieur à la racine de x, c'est qu'il existe nécessairement un diviseur inférieur à la racine de x.

x = a * b

S'il existe a plus grand que la racine de x, c'est que b est plus petit que la racine de x
S'il existe a plus petit que la racine de x, c'est que b est plus grand que la racine de x.

Moralité : si on cherche les diviseurs du plus grand ou plus petit, on finira pas tomber d'abord sur le plus petit : inutile de continuer après la racine si on n'a pas trouver avant la racine.

4.10. Considérons un nombre x et notons r sa racine carrée. Montrer par l'absurde qu'on ne peut pas écrire x = a * b avec a et b supérieurs à r.

4.11. Programmation et bugs : Quelqu'un veut créer un programme en utilisant cette notion de a et b supérieurs à r. Voici l'un de ses tests. Que teste-on réellement ici ?

📋 Texte

if a and b > r:

Que faut-il écrire pour réellement tester a et b supérieurs à r ?

4.12. >Utiliser la (mauvaise) fonction booléenne est_premier_v1(x) pour vérifier qu'elle renvoie bien True si x est premier et False sinon.

Cette fonction va au-delà de la racine et est donc assez mal codée.

La fonction gère déjà le cas 2 ou pair. Le TANT QUE doit gérer le cas d'un diviseur supérieur ou égal à 3 puisqu'on commence à diviser x par 3. Il faut continuer à modifier d dans la boucle non bornée TANT QUE la division euclidienne de x par d ne donne par un reste nul et que d est inférieur à x.

📋 Texte

>>> est_premier_v1(13)
True

>>> est_premier_v1(8191)
True

>>> est_premier_v1(131071)
True

>>> est_premier_v1(524287)
True

>>> est_premier_v1(1008001)
True

>>> est_premier_v1(10003199)
True

>>> est_premier_v1(100003679)
True

La fonction a l'air de fonctionner mais...

4.13. Programmation et bugs : Pourquoi la fonction ne fonctionne-t-elle pas pour 2 alors qu'elle ne provoque pas d'erreur et qu'elle semble fonctionner pour les valeurs supérieures à deux ?

Modifier la fonction pour qu'elle fonctionne, même pour 2.

📋 Texte

>>> est_premier_v1(2)
False

4.14. Programmation et bugs° Aidez ce pauvre programmeur qui ne comprend pas pourquoi sa propre fonction ne fonctionne pas alors qu'il a bien fait ce qu'on lui demande : on divise par les entiers de 3 jusqu'à l'entier x dont on veut tester la primalité. Il a pourtant "presque" la même chose que nous... Et c'est ce "presque" qui pose problème.

📋 Texte

>>> est_premier_v1(13)
False

Voici sa fonction :

🐍 Script Python

def est_premier_v1(x):
    '''Fonction naïve qui recherche si un nombre est premier par force brute'''
    assert type(x) == int
    if x == 2:  # si x vaut 2, on renvoie True
        reponse = True
    elif x % 2 == 0:  # sinon si x est pair, on renvoie False
        reponse = False
    else:  # sinon, il faut chercher
        d = 3
        while x % d != 0:  # tant que d n'est pas un diviseur de x
            d = d + 2
        if d <= x:  # on est sorti avant d'avoir atteint x
            reponse = False
        else:
            reponse = True
    return reponse

4.15. Fichier rsa.py. Mettre le code en mémoire. Il comporte 5 fonctions :

la fonction booléenne est_premier_v1(x) qui teste naïvement si x est premier en allant au delà de la racine
la fonction booléenne est_premier_v2(x) qui teste naïvement si x est premier en allant uniquement jusqu'à racine de x.
la fonction duree_v1(x, nb_essais=10) qui renvoie un float correspondant au nombre de secondes pour que la fonction est_premier_v1 réponde, sur une moyenne de 10 essais par défaut.
la fonction duree_v2(x, nb_essais=10) fait la même chose mais pour est_premier_v2.
la fonction trace_duree(t, nb_essais=10) qui trace un graphique correspondant aux durées moyennes pour répondre à la primalité des entiers contenus dans le tableau t, entier par entier. Elle ne renvoie rien, c'est une fonction-procédure d'interface créant un simple affichage.

4.16. Tester la rapidité des deux fonctions en utilisant les nombres premiers stockés dans NBP, le tableau de NomBres Premiers.

📋 Texte

NBP = [3, 7, 13, 29, 47, 127, 179, 257, 521, 1039, 2111]
>>> duree_v1(NBP[0])
1.8533000911702402e-06

>>> duree_v1(NBP[1])
3.363799987710081e-06

>>> duree_v1(NBP[2])
4.335299854574259e-06

>>> duree_v1(NBP[3])
6.7793998823617585e-06

>>> duree_v1(NBP[4])
1.0627700066834223e-05

>>> duree_v1(NBP[5])
1.2311300088185817e-05

>>> duree_v1(NBP[6])
1.2284100012038835e-05

>>> duree_v1(NBP[7])
4.099059988220688e-05

>>> duree_v1(NBP[8])
5.155100006959401e-05

>>> duree_v1(NBP[9])
0.00012017009994451655

>>> duree_v1(NBP[10])
0.000294514900087961

Question : que constate-t-on au niveau des temps de réponses lorsque le nombre premier devient de plus en plus grand ? A quoi est-ce dû ?

4.17. Comparer plusieurs durées d'exécution pour un même nombre premier en fournissant un seul essai à chaque fois. Pourquoi a-t-on de telles différentes ?

📋 Texte

>>> duree_v1(2111, 1)
0.0002949560002889484

>>> duree_v1(2111, 1)
0.00023148800028138794

>>> duree_v1(2111, 1)
0.00027341500026523136

>>> duree_v1(2111, 1)
0.0007015280007180991

4.18. Pour obtenir un temps d'exécution moyen, on peut donc demander à notre fonction d'évaluer cette durée non pas sur un seul essai mais sur plusieurs milliers par exemple.

📋 Texte

>>> duree_v1(2111, 1000)
0.00017470132400012516

>>> duree_v1(2111, 1000)
0.0001734132050005428

>>> duree_v1(2111, 1000)
0.0001750983299989457

>>> duree_v1(2111, 1000)
0.00017563680700004625

Que vaut cette durée ici avec un seul nombre significatif ?

4.19. Comparer les temps d'exécution pour notre deuxième fonction de recherche, celle qui ne cherche les diviseurs que jusqu'à la racine carré de x.

📋 Texte

>>> duree_v2(2111, 1000)
4.331548000563634e-06

Exprimer les durées des questions 18 et 19 en puissance de 10^-6 puis comparer les durées moyennes d'exécution des questions 16 et 17.

4.20. La durée est liée aux nombres de diviseurs à vérifier (nombre de fois où on effectue la boucle), à la taille (en octets) du nombre x par rapport aux nombres d'octets ainsi qu'à la taille (en octets) du diviseur...

📋 Texte

>>> duree_v2(1008001, 10000)
8.181419499996992e-05

>>> duree_v2(1008003, 10000)
1.609260599980189e-06

>>> duree_v2(1008005, 10000)
1.8608375999974668e-06

>>> duree_v2(1008002, 10000)
6.398853001883253e-07

Questions

Pourquoi les temps de réponses pour 1008003, 1008005 et 108002 (ces 3 nombres ne sont pas premiers) sont-ils bien plus bas que pour le nombre premier 1008001 ?
Pourquoi la réponse pour 108002 est-elle encore plus rapide ?
Que devrait faire cette durée pour vérifier de vrais nombres premiers de plus en plus grands ?

4.21. Utiliser les appels suivants qui vont permettre de comparer les durées mais également les allures des coûts. Gagne-t-on simplement en temps en utilisant la limite de la racine carrée ?

📋 Texte

>>> trace_duree(NBP, duree_v1, 1000)

>>> trace_duree(NBP, duree_v2, 100000)

Complexité de l'algorithme naïf

Nous avons vu qu'avec un peu d'algorithmique (on teste uniquement les entiers impairs) et de mathématique (on teste uniquement les diviseurs jusq'à la racine carrée), on était parvenu à améliorer la rapidité de la réponse pour un entier premier.

📋 Texte

>>> trace_duree(NBP2, duree_v2, 100000)

Réfléchissons un peu au coût d'une réponse sur un nombre premier x.

Avec 2 bits b, on peut écrire des nombres de 0 à 3.

Avec 3 bits b, on peut écrire des nombres de 0 à 7.

Avec 4 bits b, on peut écrire des nombres de 0 à 15.

Avec b bits, on peut écrire des nombres de 0 à 2^b-1.

Le lien entre n et b est donc de type 2^b.

Cela veut donc dire que le lien entre b et n est de type log2(n).

Si on en revient à notre algorithme :

Au pire, on doit faire autant de tours de boucle que la racine carrée de x. La complexité semble donc liée à ceci :

coût de l'algorithme naïf

On pourrait croire que le coût de l'algorithme est lié à la racine carré mais en réalité la difficulté du travail demandé dépend du nombre de bits nécessaires à l'encodage du nombre.

coût de l'algorithme naïf

Or, puisque la racine carré n'est rien d'autres que la mise à la puisance 1/2, on peut donc écrire que :
Le coût de la recherche de primalité d'un nombre quelconque s'exprimant avec b bits est en O(2^b/2)
Le coût de la recherche de primalité d'un nombre premier s'exprimant avec b bits est en Θ(2^b/2)

Conclusion : on ne pourra pas utiliser cet algorithme pour créer des nombres premiers de 512 bits au moins.

Déçu ? Eh oui. Il va falloir cette fois abandonner les méthodes de résolution purement informatique et sortir l'arsenal des mathématiques. Mais ce n'est pas pour tout de suite, ni pour cette année. Nous allons donc nous limiter à des recherches sur des nombres premiers d'une vingtaine de bits chacune. C'est déjà pas mal. Ca permettra de créer des clés de 40 bits.

En prenant quelques minutes, on pourrait rajouter quelques bits supplémentaires mais rien qui permettent de vraiment d'atteindre 1024 bits ou plus. Pour cela, il va falloir gagner quelques niveaux en mathématiques d'abord.

4.22. Décommenter la ligne 111. Vous allez pouvoir obtenir la comparaison entre la courbe réelle des durées d'exécution et la courbe théorique exponentielle.

coût de l'algorithme naïf

🐍 Script Python

# Création du graphique
plt.plot(axe_x, axe_y, label="Temps de recherche 1er essai", color='red')
plt.plot(axe_x, [2**(b/2)/((2**(axe_x[-1]/2))/axe_y[-1]) for b in axe_x], color='blue', label="Temps de recherche théorique")

Pour finir avec cette partie, voici l'allure des durées de traitement pour déterminer la primalité des entiers jusqu'à 1 million (à peine 20 bits donc)

On peut voir que la durée évolue à peine dans le cas d'un nombre non-premier (le bas de la courbe) mais qu'il devient de plus en plus long d'estimer si un grand nombre premier est premier.

durées pour prouver la primalité

4.23. programmation et bugs Dernière chose : quelqu'un propose une dernière implémentation de la fonction. Plutôt que d'utiliser un while pour implémenter le TANT QUE, il est passé par un for associé au fait qu'on sorte de la fonction après avoir rencontré un return.

Questions :

qu'est-ce qui provoque l'exécution des exemples du docstring (qui normalement ne sont que des exemples présents dans la documentation ?
Pourquoi les exemples ne font-ils pas se lancer automatiquement si on importe le module et qu'on le lance depuis un autre script ?
Pourrait-on la ligne vide 21 ?
où se trouve l'erreur ? Modifier le code pour qu'elle fonctionne.

🐍 Script Python

def est_premier_v3(x: int) -> bool:
    '''Fonction naïve qui recherche si un nombre est premier par force brute
    :: param x(int)   :: un entier positif
    :: return (bool)  :: True si x est premier, False sinon
    .. ATTENTION : cette version disfonctionne si elle n'est pas modifée

    :: exemples ::
    >>> est_premier_v3(7)
    True
    >>> est_premier_v3(5)
    True
    >>> est_premier_v3(25)
    False
    >>> est_premier_v3(4)
    False
    >>> est_premier_v3(11)
    True
    >>> est_premier_v3(15)
    False

    '''

    if x == 2:
        return True
    elif x % 2 == 0:
        return False
    else:
        limite = math.floor(math.sqrt(x))
        for d in range(3, limite, 2):
            if x % d == 0:
                return False
    return True


if __name__ == '__main__':
    import doctest
    doctest.testmod()

🐍 Script Python

**********************************************************************
File "activite_prog_rsa.py", line 31, in __main__.est_premier_v3
Failed example:
    est_premier_v3(25)
Expected:
    False
Got:
    True
**********************************************************************
File "activite_prog_rsa.py", line 37, in __main__.est_premier_v3
Failed example:
    est_premier_v3(15)
Expected:
    False
Got:
    True
**********************************************************************
1 items had failures:
2 of   6 in __main__.est_premier_v3
***Test Failed*** 2 failures.

5 - ETAPES 1-2-3

Maintenant que nous savons déterminer (avec un algorithme assez peu performant) si un entier est premier ou pas, nous allons pouvoir réaliser les trois premières étapes de RSA :

Etape 1 : choisir deux nombres entiers p et q de b bits.

Etape 2 : calculer le module de chiffrement n.

n = p * q

Etape 3 : calculer indicatrice d'Euler φ

φ = (p-1) * (q-1)

Commençons par nous souvenir qu'avec b bits, on peut encoder un entier naturel dont la valeur varie de 0 à 2^b - 1 , soit 2^b entiers au total.

On veut créer un nombre qui nécessite vraiment b bits et qui ne soit pas zéro : il faut donc que le bit de poids fort et le bit de poids faible ne soient pas 0 : 1-------1 .

Au minimum : seuls ces deux bits sont à 1. On a alors 2^b-1 + 1 .
Au maximum : tous les bits sont à 1. On a alors la valeur maximale 2^b - 1

Si on désire créer un nombre premier aléatoire de b bits, il suffit naïvement d'utiliser cet algorithme (on ne considèrera pas le cas où 2 est un premier possible, puisqu'on désire générer des grands nombres):

La fonction trouver_premier(b)

Calcule le plus petit et le plus grand nombre possible
Tire un nombre aléatoire IMPAIR entre ces deux nombres
Renvoie le premier nombre premier qu'on trouve à partir de ce nombre IMPAIR

5.24. programmation et bugs : Fichier rsa_v2.py. Mettre ce programme en mémoire.

Lancer l'appel suivant puis corriger l'erreur qui apparaît.

📋 Texte

>>> est_premier_v2(13)
True

>>> est_premier_v2(23)
True

>>> nombre_impair(13, 23)
    while x % 2 == 0 or x < minimum or x > maximum:
UnboundLocalError: local variable 'x' referenced before assignment

Finalisons.

Algorithme pour obtenir un nombre premier au hasard

Remarque : l'algorithme utilise

la fonction est_premier, ici dans sa version 2.
la fonction nombre_impair(minimum, maximum) qui renvoie un nombre impair aléatoire dans l'intervalle [minimum, maximum]

Description de l'algorithme de recherche renvoyer_premier(b)

📋 Texte

    minimum ← le plus petit nombre IMPAIR voulu (2b-1 + 1)
    maximum ← le plus grand nombre IMPAIR voulu (2b - 1)
    x ← nombre_impair(minimum, maximum)
    TANT QUE NON est_premier_v2(x)
        x ← x + 2
        SI x > maximum
            x ← minimum
        Fin SI
    Fin TANT QUE
    Renvoyer x

5.25. Réaliser l'implémentation de la fonction renvoyer_premier.

Ouf. Presque fini avec l'étape 1, 2 et 3 :

Structure d'un programme ou d'un module

On place les éléments dans un ordre précis et en séparant clairement les parties :

- les importations

- les CONSTANTES éventuelles

- les déclarations de Classes

- les déclarations de fonctions en séparant si possible :

les fonctions internes (pas d'appel depuis l'extérieur)
les fonctions d'interface (utilisables)

- le programme qu'on veut voir s'exécuter uniquement en cas d'appel direct

Voici ci-dessous le programme permettant de (presque) gérer les étapes 1, 2 et 3.

5.26. Fichier rsa3.py : Observer la fonction creer_cles puis lancer le programme. Observer les erreurs d'exécution fournies par le module doctest.

Questions

Où se trouve l'appel de la fonction creer_cles ?
Sous quelle condition cet appel ne se fera-t-il pas ?

6 - TESTER

Avant de continuer, voyons comment vérifier le bon déroulement du programme même si un utilisateur envoie un mauvais argument à l'une des fonctions d'interface.

Nous allons revoir qu'on gère différemment

les fonctions d'interface : l'utilisateur a potentiellement envoyé n'importe quoi, il convient donc de vérifier les paramètres avant de demander aux fonctions internes de travailler sur ces données.
les fonctions internes : normalement, ces fonctions ont été testées et validées avant utilisation, si on leur transmet de bons arguments, pas de raison qu'elles dysfonctionnent.

Tester les fonctions avec des assertions

Première façon de faire : on stoppe l'exécution du programme

si l'une des préconditions est fausse (conditions sur les paramètres d'ENTREES)
si l'une des postconditions est fausse (conditions sur la réponse en SORTIE)

Avantage : on surveille tout et on détecte tous les dysfonctionnements qu'on peut tenter de gérer ensuite

Désavantage : ça coupe tout au moindre problème et ça ralentit le tout à cause du nombre importants de tests.

On peut voir cela comme de la programmation "défensive" : on accepte de travailler qu'avec des données valides et on refuse de continuer au moindre problème. Ca peut être bien sur certaines applications où les problèmes engendrés peuvent être pires qu'une simple interruption.

6.27. On va étudier deux fonctions supplémentaires. Lancer le fichier rsa4.py.

En vous aidant de la première, créer des assertions pour la seconde fonction :

1. les préconditions AVANT de commencer à calculer phi.

2. vérifiez les deux postconditions suivantes APRES avec calculer phi mais avant de faire répondre la fonction :

phi est bien un entier et
phi < p*q

6.28. Tester si p et q sont premiers est-il rapide ou lent ?

Est-ce bien utile d'ailleurs pour une fonction qui est juste censée renvoyer une multiplication ?

Conclusion sur l'utilisation des assertions

Tout vérifier est contre-productif. Il faut vérifier ce qui est important pour la fonction en elle-même, sans oublier qu'elle s'insère dans un ensemble.

déroulement des appels

6.29. Pourquoi n'est-ce pas la peine de vérifier la primalité de p et q dans calculer_module si on a bien vérifié la fonction renvoyer_premier ?

Habituellement (sauf exception), on va donc supprimer une bonne partie des exceptions après la phase de développement. En garder quelques-unes bien choisies permet de détecter plus facilement les dysfonctionnements pour une cause non prévue si on n’a pas montrer la correction de toutes les fonctions.

Une fois toutes les fonctions internes validées, il ne reste qu'à bien filtrer les arguments envoyés aux fonctions d'interface.

Filtrer les paramètres des fonctions d'interface (hors programme, simple présentation de culture générale) Avec les fonctions d'interface, c'est plus compliqué : le contenu des paramètres est potentiellement mauvais.

Soit on met des assertions : tant pis pour l'utilisateur qui fait n'importe quoi (on protège les données). Mais ça fait stopper le système.

🐍 Script Python

def creer_cles(b: int) -> tuple:
    '''Renvoie un tuple contenant la clé publique et la clé privée ou None

    :: param b(int)        :: le nombre de bits voulus pour les entiers premiers
    :: return (tuple|None) :: un tuple contenant les clés ou None en cas de problème

    '''

    assert type(b) == int, "b n'est pas un entier"
    assert b > 0

    ..code
    normal..

Soit on fait des tests d'erreurs (avec des if) sur les erreurs d'entrée qu'on peut prévoir, et on réalise autre chose que la séquence normale si c'est le cas. Il faut penser à tout et dire à l'utilisateur qu'on va renvoyer un mauvais résultat s'il envoie n'importe quoi... Est-ce mieux ?

🐍 Script Python

def creer_cles(b: int) -> tuple:
    '''Renvoie un tuple contenant la clé publique et la clé privée ou None

    :: param b(int)        :: le nombre de bits voulus pour les entiers premiers
    :: return (tuple|None) :: un tuple contenant les clés ou None en cas de problème

    '''

    if type(b) == int and b > 0:

        ...
        code
        normal...

    else:

        return None

Soit on tente de faire fonctionner le système (avec des try) et en cas déclenchement d'une erreur, on prévoit autre chose (avec des except). Mais on n'en parlera pas plus que ça, ce n'est pas au programme et il faut faire attention à ce qu'on fait aussi : si on envoie un flottant, ça passera ici ! Je n'en parle qu'en terme de culture générale, pour que vous sachiez ce que cela fait si vous tombez sur un tel code. On en parlera plus ensuite.

🐍 Script Python

def creer_cles(b: int) -> tuple:
    '''Renvoie un tuple contenant la clé publique et la clé privée ou None

    :: param b(int)        :: le nombre de bits voulus pour les entiers premiers
    :: return (tuple) :: un tuple contenant les clés
    .. on utilisera des premiers sur 20 bits en cas de problème quelconque

    '''

    try:
        b = int(b)
    except:
        b = 20

    if not b > 0:
        b = 20

    ..code
    normal..

Le problème des méthodes 2 et 3 : il n'y pas toujours facile de retrouver la raison initiale d'une erreur à un moment si on a modifier les 'mauvaises' données envoyées par l'utilisateur. Bref, comme vous le voyez c'est un vrai sujet qui mérite des heures de formation.

A retenir pour cette année :

On distinguera 3 grands types d'erreur :

les erreurs de syntaxe : facile à détecter par l'interpréteur (on a oublié un :, on a écrit dec plutôt que def...)
les erreurs d'exécution : le code est "propre" mais l'un des contenus n'est pas du bon type ou ne contient pas ce qu'il faut. Il faut vérifier le contenu des variables pour savoir d'où vient le problème. Et si on a trop filtrer les arguments, il est possible que cela soit encore plus difficile !
Les erreurs logiques ou sémantiques : le code a l'air propre mais l'algorithme est faux. Cela ne déclenche pas d'erreur mais renvoie de mauvaises réponses. Comme elles ne déclenchent pas d'erreur en elles-même, ces erreurs sont compliquées à gérer. C'est l'un qu'un bon choix d'assertions permet de couper le programme à l'endroit où les préconditions ou postconditions ne sont plus bonnes.

Quelques bonnes pratiques pour limiter le nombre d'erreurs :

Faire de petites fonctions ET les tester avant de passer à autre chose : c'est l'intéret des jeux de tests
Placer des assertions permettant de vérifer les préconditions et les postconditions (cela coupe le déroulement du processus lorsqu'on détecte un problème)
Choisir judicieusement les assertions en prenant en compte la position de la fonction dans le programme ou le module (fonction d'interface, fonction interne...)
Le filtrage des paramètres est possible mais nécessite des précautions et n'est pas une solution miracle non plus : cela peut même compliquer la recherche de la source d'un bug.

7 - DÉTERMINER L'EXPOSANT E DE CHIFFREMENT

Rappel :

Etape 4 : choisir l'exposant de chiffrement e

Cette étape est plus délicate à réaliser. Nous allons voir qu'il va falloir utiliser l'algorithme d'Euclide.

Sans un bon algorithme, cette simple recherche peut prendre du temps.

Ce exposant de chiffrement e doit être

un entier inférieur à φ
premier avec φ : e ne doit pas partager de diviseur commun avec φ , d'où l'algorithme d'Euclide.

Ici, on a φ = 2016 et on décompose 2106 de cette façon : 2016 = 2⁵ * 3² * 7 : 2, 3 et 7 sont donc les diviseurs à ne pas prendre pour e.

Il suffit donc de prendre un nombre e qui ne soit divisible ni par 2, ni par 3, ni par 7.

Le plus grand commun diviseur de deux nombres premiers entre eux est donc ... 1 !

Il existe donc de nombreuses valeurs admissibles de e. Ces valeurs dépendent uniquement de φ (et donc indirectement de p et q).

Commençons par voir comment fonctionne l'algorithme d'Euclide qui permet de déterminer le plus grand commun diviseur (PGCD) entre deux entiers.

Le principe est de diviser un dividende par un diviseur pour trouver le reste.

Le diviseur devient alors le dividende et le reste devient le diviseur.

Si avant de faire la division, on voit que le diviseur est 0, on renvoie le dividende et il s'agit alors du PGCD.

Cherchons le plus grand commun diviseur de 20 et 12 :

euclide_1

Le reste (qui est devenu le diviseur 8 maintenant) n'est pas nul, on continue.

euclide_2

Le reste (qui est devenu le diviseur 4 maintenant) n'est pas nul, on continue.

euclide_3

Le reste (qui est devenu le diviseur 0 maintenant) est nul : on arrête et on renvoie le nouveau dividende qui est le ... dernier diviseur non nul.

euclide_4

C'est bien la bonne réponse puisque 20 = 4 * 5 et que 12 = 3 * 4. 4 est bien le Plus Grand Commun Diviseur.

Notez bien qu'avec Python, ce sera simple à coder puisqu'on peut obtenir le reste directement.

📋 Texte

>>> 20 % 12
8

>>> 12 % 8
4

>>> 8 % 4
0

Le principe de l'algorithme est simple à appliquer (je ne parlerai pas des justifications, et démonstration ici)

Algorithme d'Euclide

Euclide

Gravure d'Euclide (depuis https://fr.wikipedia.org/wiki/Euclide#/media/Fichier:Euklid-von-Alexandria_1.jpg) - Domaine Public

BUT

Renvoyer le plus grand commun diviseur de deux nombres entiers.

Si on travaille avec :

1614915 qu'on peut décomposer sous cette forme 5 * 9 * 17 * 2111 de multiplication d'entiers et
25455706711 dont la décomposition est 23 * 2111 * 524287
le plus grand commun diviseur est 2111

ENTREES

Deux nombres a et b

Préconditions

Ce sont bien des entiers
Si a < b, on rajoute juste une étape supplémentaire : l'algorithme parvient automatiquement à inverser a et b !

Description de l'algorithme

📋 Texte

    dividende ← a
    diviseur ← b
    TANT QUE diviseur est différent de 0
            reste ← dividende % diviseur
            dividende ← diviseur
                on remplace le dividence par l'ancien diviseur
            diviseur ← reste
                on remplace le diviseur par le reste obtenu
    Fin TANT QUE
    Renvoyer dividende

on renvoie donc le diviseur ayant mené à un reste nul

7.30. Fichier rsa5.py : Réaliser l'implémentation de l'algorithme via la fonction pgcd en ligne 116 : quelqu'un vous a déjà tapé deux lignes de code pour récupérer a et b. Il vous suffit donc de remplacer le pass par l'implémentation du while.

Votre fonction doit passer les tests.

Attention, une faute d'inattention se cache dans les quelques lignes déjà tapées. Mais les jeux de tests devraient vous dire clairement ce qui ne va pas.

Bug typique

Il s'agissait donc ici d'un mauvais nommage de variables

D'où l'intérêt d'utiliser les propositions automatiques qui s'affichent sur les bons éditeurs de code.

7.31. Observer euclide_bis. Les noms ne sont pas explicites cette fois : certaines préfèrent de telles versions "épurées" avec des noms courts. Le problème vient de la compréhension du code quelques semaines, mois ou années plus tard.

7.32. Votre fonction renvoie le plus grand commun diviseur. Quel doit être le PGCD de deux nombres premiers entre eux (tels que e et φ) ?

8 - DÉTERMINER L'EXPOSANT D DE DÉCHIFFREMENT

Voici le code si vous redemarrez à partir d'ici pendant une nouvelle séance et que vous n'êtes plus certain d'avoir un code valide : fichier rsa6.py

Etape 5 : trouver l'exposant de déchiffrement d (connaissant e et φ)

Ce exposant de déchiffrement d doit être l'inverse de e modulo φ.

Cela veut dire qu'il faut respecter cette condition : le reste de la division entière de (e*d) par φ vaut 1.

(e * d) % φ = 1

D'où la notion d'inverse "e = 1 / d".

Dans le cas de notre exemple :

Indicatrice d'Euler φ = 2016
Exposant de chiffrement e = 437
on détermine que l'exposant de déchiffrement est d = 1181

Vérification avec Python :

📋 Texte

>>> e = 437
>>> d = 1181
>>> phi = 2016
>>> (e*d) % phi
1

Cette fois, il faudra utiliser l'algorithme d'Euclide étendu. Sinon, encore une fois, cela prendrait un temps énorme pour p et q de grande taille.

Nous n'allons pas l'étudier, il est déjà codé et fonctionnel ici.

Par contre, vous aller créer une fonction qui fait la même chose mais en version naïve et nous verrons que notre RSA maison ne fonctionnera plus trop bien sur cette dernière étape : trop lent pour de grandes clés.

8.33. Coder la fonction calculer_d_naif pour qu'elle renvoie la valeur de d en respectant cette technique

Connaissant e et φ, tester toutes les valeurs possibles de d jusqu'à trouver celle qui répond à :

(e * d) % φ = 1

Prenons le premier exemple du cours :

p = 17
q = 127
n = 2159
φ = 2016
e = 437

La valeur de d est alors 1181.

8.34. Tester ceci pour voir que les deux fonctions fonctionnent :

📋 Texte

>>> e = 437
>>> φ = 2016
>>> calculer_d(e,φ)
1181

>>> calculer_d_naif(e,φ)
1181

Voilà, vous avez codé de bout en bout la génération de clés RSA. Même la fin visiblement. Les oiseaux chantent, un arc-en-ciel apparâit, tout va bien dans le meilleur des mondes.

Prenons cet exemple :

p = 703837
q = 844127
n = 594127815299
φ = 594126267336
e = 135478415797

La valeur de d est alors 378707856781.

8.35. Tester ceci pour voir que les deux fonctions fonctionnent, ou de façon problématique pour l'une d'entre elles, devinez laquelle ;o) :

📋 Texte

>>> e = 135478415797
>>> φ = 594126267336
>>> calculer_d(e,φ)
378707856781

>>> calculer_d_naif(e,φ)
378707856781

9 - ET AVEC UN VRAI FICHIER ?

Maintenant que vous avez un moyen de générer de (petites) clés RSA, il est tenté de partager une clé publique avec quelqu'un que vous connaissez pour qu'il puisse vous transmettre des fichiers cryptés.

8.36. Documentation et programmation° Fichier rsa7.py : Placer le gros programme suivant en mémoire. Ensuite, taper ceci dans la console pour comprendre comment fonctionne le chiffrement et le déchiffrement d'un fichier quelconque.

📋 Texte

>>> cpub, cpri = creer_cles(20)
>>> cpub
(524019377303, 89243442031)

>>> cpri
(524019377303, 453869594791)

>>> help(chiffrer_fichier)

>>> help(dechiffrer_fichier)

Voici un exemple d'utilisation :

📋 Texte

>>> cpub, cpri = creer_cles(20)
>>> cpub
(501751207679, 233074674377)

>>> cpri
(501751207679, 316864673033)
>>> chiffrer_fichier(cpub, "test.png", "chiffre.png")

Chiffrement en cours...
50 ko - 100 ko - 150 ko - 200 ko -
Chiffrement terminé

>>> dechiffrer_fichier(cpri, "chiffre.png", "dechiffre.png")

Déchiffrement en cours...
50 ko - 100 ko - 150 ko - 200 ko - 250 ko -
Déchiffrement réalisé

8.37. Générer deux clés. Gardez les valeurs de la privées. Envoyer via l'ENT ou par mail la clé publique à vos destinataires.

8.38. Demander à cette personne de créer un fichier (texte, musique, pdf, video...) et de vous l'envoyer après l'avoir crypté avec la clé publique.

Il ne restera qu'à la décrypter avec la clé privée.

Attention : ça peut être long. C'est pour cela qu'on préférera utiliser un chiffrement symétrique une fois le canal sécurisé par le système asymétrique.

Enfin, le chiffrement et le déchiffrement sont moins gourmands en temps avec un système symétrique.

10 - FAQ

Petit théorème de Fermat (hors programme)

Enoncé

Si p est un nombre premier et si a est un entier non divisible par p ,

alors a^p–1 – 1 est un multiple de p.

On pourrait donc écrire a^p–1 – 1 = k*p .

Ou on peut aussi écrire a^p–1 = k*p + 1 .

Or, le reste de la division de 1 par n'importe quel nombre donne bien un reste de 1. On peut donc écrire :

a^p–1 % p == 1 % p

Conséquence

Version 1 a^p–1 ≡ 1 (mod p)

Version 2 a^p ≡ a (mod p) (en multipliant par a de chaque côté)

Exemple

Prenons le nombre premier p = 17.

Prenons le nombre entier a = 50, non divisible par 17 : 50 / 17 =

📋 Texte

>>> p = 17
>>> a = 50

>>> (a**(p-1)) % p == 1 % p
True

>>> (a**p) % p == a % p
True