Deux formules fonctionnent pour ce problème d'échange en trois passes, mais je ne comprends pas pourquoi l'une d'elles fonctionne
Énoncé du problème:
"Supposons que les utilisateurs Alice et Bob exécutent le protocole Diffie-Hellman à 3 passes avec p = 101. Supposons qu'Alice choisisse a 1 = 19 et que Bob choisisse b 1 = 13. Si Alice veut envoyer le message secret m = 5 à Bob, montre tous les messages échangés entre Alice et Bob. "
Solution officielle:
$a_2 = {a_1}^{-1}\bmod(p-1)=79$
$b_2=77$
Alice → Bob: $m^{a_1}\bmod p=37$
Bob → Alice: $80$
Alice → Bob: $56$
Bob obtient $m$ en évaluant $56^{b_2}\bmod p=5$
Solution que j'ai faite avec l'aide de quelqu'un (car je ne trouve pas d' informations très spécifiques sur ce protocole à trois passes en ligne):
Alice:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$
Bob:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$
Alice à Bob # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob à Alice (# 1 - il n'y a pas de # 2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alice à Bob # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob obtient le message comme suit:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Ma question:
Pourquoi la solution officielle utilise-t-elle $a_2={a_1}^{-1}\bmod(p-1)=79$ au lieu de $a_2={a_1}^{p-2}\bmod(p-1)=79$, et comment justifier cette équivalence dans le contexte de ce type de problème ? (Je dis "dans le cadre de ce type de problème" car, à ma connaissance, les deux expressions ne sont pas toujours équivalentes).
Toute contribution qui pourrait m'aider à clarifier ma confusion serait grandement appréciée!
PS
- $a_1$ est la clé de chiffrement d'Alice
- $a_2$ est la clé de déchiffrement d'Alice
- $b_1$ est la clé de chiffrement de Bob
- $b_2$ est la clé de déchiffrement de Bob
Réponses
TL; DR: la deuxième méthode ne fonctionne que pour une proportion de nombres premiers qui disparaît $p$.
La question utilise la même relation entre $a_1$ et $a_2$comme dans le chiffre symétrique de Pohlig-Hellman. Dans ce:
- $p$ est un paramètre public principal,
- la clé de chiffrement est un entier aléatoire $a_1$ coprime avec$p-1$,
- la clé de déchiffrement est un entier $a_2$ tel que $a_1\,a_2=k\,(p-1)+1$ pour un entier $k$.
- le cryptage est par $m\mapsto c=m^{a_1}\bmod p$, pour $m$ dans $[0,p)$,
- le décryptage est par $c\mapsto m'=c^{a_2}\bmod p$, et ça tient $m'=m$.
Preuve: $$\begin{align} m'&=c^{a_2}\bmod p&&\text{by construction of $m '$}\\ &=(m^{a_1}\bmod p)^{a_2}\bmod p&&\text{since $c = m ^ {a_1} \ bmod p$}\\ &=m^{a_1\,a_2}\bmod p\\ &=m^{k\,(p-1)+1}\bmod p&&\text{by construction of $a_2$}\\ &=m^{(p-1)\,k}\,m^1\bmod p\\ &=(m^{p-1})^k\,m\bmod p\\ &=(m^{p-1}\bmod p)^k\,m\bmod p\\ &=1^k\,m\bmod p&&\text{per Fermat's little theorem}\\ &=m\bmod p\\ &=m&&\text{since $m$ is in $[1, p)$} \end{align}$$
Remarque: le petit théorème de Fermat dit que quand$p$ est premier et $m$ n'est pas un multiple de $p$, ça tiens $m^{p-1}\bmod p=1$.
Un entier approprié $a_2$, et le seul à portée $[0,p-1)\,$, est ${a_1}^{-1}\bmod(p-1)\,$: l' inverse multiplicatif de$a_1$ modulo $p-1$. C'est ce qui est utilisé dans la solution officielle de la question .
La méthode classique pour calculer cet inverse multiplicatif est l' algorithme euclidien étendu . Pour des implémentations pratiques, je recommande cette variante qui utilise deux variables en moins et ne manipule jamais les quantités négatives.
L'autre solution de la question ne diffère qu'en calculant la même $a_2$ en utilisant une formule différente: ${a_1}^{p-2}\bmod(p-1)$. La question se résume donc à:
Pour prime $p>2$, pourquoi / quand est-ce que $a^{-1}\bmod(p-1)$ peut être calculé comme $a^{p-2}\bmod(p-1)$ ?
Par définition, $a^{-1}\bmod(p-1)$ est l'entier $x$ dans $[0,p-1)$ avec $a\,x\bmod(p-1)=1$. Il n'est défini que lorsque$a$ est coprime avec $p-1$. Il s'ensuit que la question équivaut à:
Pour prime $p>2$, pourquoi / quand est-ce que $a^{p-1}\bmod(p-1)=1$ pour tous $a$ coprime à $p-1$?
C'est pour beaucoup $p$ y compris la question $p=101$, mais pas toujours. Le plus petit contre-exemple est$p=11$, $a=3$. Un autre$p=103$, $a=5$. On peut vérifier qu'en utilisant la deuxième méthode pour ces$p$ et les clés de cryptage conduisent à un décryptage incorrect pour la plupart $m$.
Ce sont les nombres premiers A337119 (créés pour l'occasion), commençant par
2 3 5 7 13 17 19 37 41 43 61 73 97 101 109 127 157 163 181 193 241 257 313 337 379 401 421 433 487 541 577 601 641 661 673 757 769 881 883 937 1009 1093 1153 1201 1249 1297 1321 1361 1459 1601 1621 1801 1861 1873
Ce sont aussi les nombres premiers $p$ tel que $p-1$est un numéro Novák-Carmichael A124240 ; ou de manière équivalente les nombres premiers$p$ tel que $\lambda(p-1)$ se divise $p-1$ (où $\lambda$est la fonction Carmichael ). Ils s'amincissent rapidement comme$p$ grandit.
Par conséquent, la deuxième méthode de la question est erronée en général, et la plupart des nombres premiers$p$d'intérêt pour l'application en question (puisqu'ils sont gros: mille bits). Il s'agissait probablement d'une extension incorrecte du fait suivant: quand$p$ est premier, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ sauf si $a$ est un multiple de $p$, qui découle du petit théorème de Fermat .
Dans l'échange à trois passes de la question, $m'$ obtenu par Bob à la fin est $m$ depuis $$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &={({m_\text{BobToAlice}}^{a_2}\bmod p)}^{b_2}\bmod p\\ &={m_\text{BobToAlice}}^{a_2\,b_2}\bmod p\\ &={({m_\text{AliceToBob1}}^{b_1}\bmod p)}^{a_2\,b_2}\bmod p\\ &={m_\text{AliceToBob1}}^{b_1\,a_2\,b_2}\bmod p\\ &={(m^{a_1}\bmod p)}^{b_1\,a_2\,b_2}\bmod p\\ &=m^{a_1\,b_1\,a_2\,b_2}\bmod p\\ &=m^{(a_1\,b_1)\,(a_2\,b_2)}\bmod p\\ &=(m^{a_1\,a_2}\bmod p)^{b_1\,b_2}\bmod p\\ &=m^{b_1\,b_2}\bmod p\\ &=m \end{align}$$