🔢

Arithmétique Modulaire

Congruences, Algorithmes et Cryptographie RSA - UTC501

≡

1. Les Congruences

📐 Définition

Soient a, b et n des entiers, avec n ≠ 0.

a ≡ b (mod n) ⟺ n | (a - b)
⟺ ∃k ∈ ℤ, a = b + kn

🎯 Propriétés Fondamentales

↺

Réflexive

a ≡ a [n]
Tout nombre est congru à lui-même

⇄

Symétrique

a ≡ b [n] ⟹ b ≡ a [n]
La relation est bidirectionnelle

⟹

Transitive

a ≡ b [n] et b ≡ c [n]
⟹ a ≡ c [n]

💡 Point clé : La congruence modulo n est une relation d'équivalence qui partitionne ℤ en n classes.

⚙️ Opérations sur les Congruences

Si a ≡ a' [n] et b ≡ b' [n], alors :
  • Addition : a + b ≡ a' + b' [n]
  • Soustraction : a - b ≡ a' - b' [n]
  • Multiplication : a × b ≡ a' × b' [n]
  • Puissance : ak ≡ a'k [n]
∞

2. Algorithme d'Euclide & Bézout

🔄 Algorithme d'Euclide

Calcul rapide du PGCD de deux nombres a et b :

1

Si b = 0
PGCD(a, 0) = a

→
2

Si b ≠ 0
PGCD(a, b) = PGCD(b, r)

→
3

Répéter jusqu'à
reste = 0

Exemple : PGCD(96, 81)
96 = 81 × 1 + 15
81 = 15 × 5 + 6
15 = 6 × 2 + 3
6 = 3 × 2 + 0
⟹ PGCD = 3

🔗 Identité de Bézout

Théorème : Si d = PGCD(a, b), alors il existe u, v ∈ ℤ tels que :
au + bv = d
🎓 Théorème de Bézout : a et b sont premiers entre eux ⟺ ∃u, v ∈ ℤ : au + bv = 1
φ

3. Euler & Fermat

📊 Fonction Indicatrice d'Euler

φ(n) = nombre d'entiers ∈ {1, 2, ..., n-1} premiers avec n
Propriétés :
  • Si p est premier : φ(p) = p - 1
  • Plus généralement : φ(pk) = pk-1(p - 1)
  • Si PGCD(m, n) = 1 : φ(mn) = φ(m) × φ(n)

⚡ Petit Théorème de Fermat

Si p est premier et p ∤ a
alors ap-1 ≡ 1 [p]

🎯 Théorème d'Euler

Si PGCD(a, n) = 1
alors aφ(n) ≡ 1 [n]
⚠️ Attention : Ces théorèmes sont fondamentaux pour la cryptographie RSA !
🔐

4. Cryptographie RSA

🔑 Création des Clés

1

Choisir p, q
Nombres premiers distincts
n = pq

→
2

Calculer φ(n)
φ(n) = (p-1)(q-1)
Choisir e premier avec φ(n)

→
3

Trouver d
ed ≡ 1 [φ(n)]

🔓 Clé Publique : (n, e)
🔒 Clé Privée : (n, d)

📨 Chiffrement & Déchiffrement

Chiffrement : C ≡ Me [n]

Déchiffrement : M ≡ Cd [n]

🔬 Preuve du Déchiffrement

Cd = (Me)d = Med = M1+kφ(n) = M × (Mφ(n))k
Or par le théorème d'Euler : Mφ(n) ≡ 1 [n]
Donc : Cd ≡ M × 1k ≡ M [n]
🛡️ Sécurité RSA :
  • La sécurité repose sur la difficulté de factoriser n
  • Taille recommandée : au moins 2048 bits
  • Sans p et q, impossible de calculer φ(n) et donc d
📝

5. Exemple RSA Complet

Données : p = 53, q = 11, e = 3
Étape Calcul Résultat
Module n = 53 × 11 n = 583
Phi d'Euler φ(n) = 52 × 10 φ(n) = 520
Clé privée 3d ≡ 1 [520] d = 347
Chiffrement du message M = 123 :
C = 1233 mod 583 = 1860867 mod 583 = 166
💡 Vérification :
166347 mod 583 = 123 ✓
✅

Points Clés à Retenir

🎯 Essentiel pour l'examen :

  • Congruences : Relation d'équivalence, opérations autorisées
  • Algorithme d'Euclide : Calcul du PGCD par divisions successives
  • Bézout : PGCD(a,b) = 1 ⟺ ∃u,v : au + bv = 1
  • Euler : φ(n) et aφ(n) ≡ 1 [n]
  • Fermat : ap-1 ≡ 1 [p] si p premier
  • RSA : Clés (n,e) et (n,d), chiffrement Me, déchiffrement Cd
🧮 Formules Essentielles :
a ≡ b [n] ⟺ n | (a-b)
φ(pk) = pk-1(p-1)
ed ≡ 1 [φ(n)]
C = Me mod n
⚠️ Pièges Classiques :
  • Ne pas confondre PGCD et φ(n)
  • Vérifier que e est premier avec φ(n)
  • Utiliser l'algorithme d'Euclide étendu pour trouver d
  • Bien calculer les restes modulo n