30 min de cours gratuit et sans engagement !

Obtenir un cours gratuit
Physique • 9e HarmoS • Codes secrets

Énoncé de l'exercice 9

Réf: phys-9h-code-009
Initiation à la cryptographie asymétrique (échange de clé de Diffie–Hellman) :
Alice et Bob veulent fabriquer un code secret commun en communiquant uniquement sur un canal public où un espion écoute tout. Ils choisissent publiquement les nombres p=23p = 23 et g=5g = 5.
  • Alice choisit secrètement a=6a = 6, calcule A≡56(mod23)A \equiv 5^6 \pmod{23} et l'envoie publiquement à Bob.
  • Bob choisit secrètement b=4b = 4, calcule B≡54(mod23)B \equiv 5^4 \pmod{23} et l'envoie publiquement à Alice.
  1. Calculer les valeurs publiques AA et BB envoyées par Alice et Bob.
  2. Alice calcule ensuite KA≡Ba(mod23)K_A \equiv B^a \pmod{23} et Bob calcule KB≡Ab(mod23)K_B \equiv A^b \pmod{23}. Vérifier qu'ils obtiennent la même clé secrète KK.
  3. Pourquoi l'espion qui connaît p,g,A,Bp, g, A, B a-t-il du mal à retrouver KK lorsque pp est un très grand nombre premier (de plusieurs centaines de chiffres) ?

Réponse finale

  1. A=8A = 8 et B=4B = 4 ; 2. KA=KB=K_A = K_B = 22 ; 3. Car il est facile de calculer ga(modp)g^a \pmod p, mais très difficile d'inverser l'opération pour retrouver aa à partir de ga(modp)g^a \pmod p (problème du logarithme discret).

Corrigé détaillé et méthode étape par étape

Développement pédagogique complet conforme aux exigences HarmoS.

  1. Calcul des nombres publics AA et BB modulo 2323 :
  • 51=55^1 = 5
  • 52=25≡2(mod23)5^2 = 25 \equiv 2 \pmod{23}
  • B≡54=(52)2≡22=4(mod23)B \equiv 5^4 = (5^2)^2 \equiv 2^2 = 4 \pmod{23}   ⟹  \implies B=4B = 4.
  • A≡56=54×52≡4×2=8(mod23)A \equiv 5^6 = 5^4 \times 5^2 \equiv 4 \times 2 = 8 \pmod{23}   ⟹  \implies A=8A = 8.
  1. Calcul de la clé partagée :
  • Chez Alice : KA≡Ba=46(mod23)K_A \equiv B^a = 4^6 \pmod{23}. 42=164^2 = 16, 43=64≡18≡−5(mod23)4^3 = 64 \equiv 18 \equiv -5 \pmod{23}, donc 46=(43)2≡(−5)2=25≡4^6 = (4^3)^2 \equiv (-5)^2 = 25 \equiv 2(mod23)2 \pmod{23}.
  • Chez Bob : KB≡Ab=84(mod23)K_B \equiv A^b = 8^4 \pmod{23}. 82=64≡−5(mod23)8^2 = 64 \equiv -5 \pmod{23}, donc 84=(82)2≡(−5)2=25≡8^4 = (8^2)^2 \equiv (-5)^2 = 25 \equiv 2(mod23)2 \pmod{23}. Ils partagent exactement le même secret K=2K = 2 (car (5b)a=5ab=(5a)b(5^b)^a = 5^{ab} = (5^a)^b).
  1. Sécurité du protocole : L'exponentiation modulaire est une fonction à sens unique : calculer ga(modp)g^a \pmod p est très rapide, mais pour de très grands nombres, retrouver l'exposant aa à partir de AA (logarithme discret) demande des temps de calcul astronomiques.