Zwei Formeln funktionieren für dieses Austauschproblem mit drei Durchgängen, aber ich kann nicht herausfinden, warum eine davon funktioniert
Problemstellung:
"Angenommen, die Benutzer Alice und Bob führen das 3-Pass-Diffie-Hellman-Protokoll mit p = 101 aus. Angenommen, Alice wählt a 1 = 19 und Bob w 1 = 13. Wenn Alice die geheime Nachricht m = 5 senden möchte Bob, zeige alle Nachrichten, die zwischen Alice und Bob ausgetauscht wurden. "
Offizielle Lösung:
$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 erhält $m$ durch Auswertung $56^{b_2}\bmod p=5$
Lösung, die ich mithilfe einer Hilfe von jemandem erstellt habe (da ich online keine sehr spezifischen Informationen zu diesem Drei-Pass-Protokoll finden kann):
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 zu Bob # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob zu Alice (# 1 - es gibt keine # 2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alice zu Bob # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob erhält die Nachricht wie folgt:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Meine Frage:
Warum verwendet die offizielle Lösung $a_2={a_1}^{-1}\bmod(p-1)=79$ Anstatt von $a_2={a_1}^{p-2}\bmod(p-1)=79$und wie kann diese Äquivalenz im Kontext dieser Art von Problem gerechtfertigt werden? (Ich sage "im Kontext dieser Art von Problem", weil nach meinem Verständnis die beiden Ausdrücke nicht immer gleichwertig sind).
Jede Eingabe, die mir helfen könnte, meine Verwirrung zu klären, wäre sehr dankbar!
PS
- $a_1$ ist Alices Verschlüsselungsschlüssel
- $a_2$ ist Alices Entschlüsselungsschlüssel
- $b_1$ ist Bobs Verschlüsselungsschlüssel
- $b_2$ ist Bobs Entschlüsselungsschlüssel
Antworten
TL; DR: Die zweite Methode funktioniert nur für einen verschwindenden Anteil von Primzahlen $p$.
Die Frage verwendet die gleiche Beziehung zwischen $a_1$ und $a_2$wie in der symmetrischen Chiffre von Pohlig-Hellman. In diesem:
- $p$ ist ein öffentlicher Primparameter,
- Der Verschlüsselungsschlüssel ist eine zufällige Ganzzahl $a_1$ Koprime mit$p-1$,
- Der Entschlüsselungsschlüssel ist eine Ganzzahl $a_2$ so dass $a_1\,a_2=k\,(p-1)+1$ für eine ganze Zahl $k$.
- Verschlüsselung ist per $m\mapsto c=m^{a_1}\bmod p$, zum $m$ im $[0,p)$,
- Entschlüsselung ist per $c\mapsto m'=c^{a_2}\bmod p$und es gilt $m'=m$.
Beweis: $$\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}$$
Anmerkung: Fermats kleiner Satz sagt, wann$p$ ist Prime und $m$ ist kein Vielfaches von $p$, es hält $m^{p-1}\bmod p=1$.
Eine geeignete ganze Zahl $a_2$und der einzige in Reichweite $[0,p-1)\,$ist ${a_1}^{-1}\bmod(p-1)\,$: die multiplikative Umkehrung von$a_1$ Modulo $p-1$. Das ist es, was in der offiziellen Lösung der Frage verwendet wird .
Die Lehrbuchmethode zur Berechnung dieser multiplikativen Inversen ist der Extended Euclidean-Algorithmus . Für praktische Implementierungen empfehle ich diese Variante, die zwei Variablen weniger verwendet und niemals negative Größen manipuliert.
Die andere Lösung der Frage unterscheidet sich nur durch die Berechnung derselben $a_2$ mit einer anderen Formel: ${a_1}^{p-2}\bmod(p-1)$. Die Frage lautet also:
Für Prime $p>2$, warum / wann ist es das? $a^{-1}\bmod(p-1)$ kann berechnet werden als $a^{p-2}\bmod(p-1)$ ?
Per Definition, $a^{-1}\bmod(p-1)$ ist die ganze Zahl $x$ im $[0,p-1)$ mit $a\,x\bmod(p-1)=1$. Es ist nur definiert, wenn$a$ ist Koprime mit $p-1$. Daraus folgt, dass die Frage gleichbedeutend ist mit:
Für Prime $p>2$, warum / wann ist es das? $a^{p-1}\bmod(p-1)=1$ für alle $a$ Koprime zu $p-1$?
Das ist für viele $p$ einschließlich der Fragen $p=101$, aber nicht immer. Das kleinste Gegenbeispiel ist$p=11$, $a=3$. Ein anderer es$p=103$, $a=5$. Es kann überprüft werden, dass mit der zweiten Methode für diese$p$ und Verschlüsselungsschlüssel führen für die meisten zu einer falschen Entschlüsselung $m$.
Dies sind die Primzahlen aus A337119 (für diesen Anlass erstellt), beginnend mit
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
Dies sind auch die Primzahlen $p$ so dass $p-1$ist eine Novák-Carmichael-Nummer A124240 ; oder gleichwertig die Primzahlen$p$ so dass $\lambda(p-1)$ teilt $p-1$ (wo $\lambda$ist die Carmichael-Funktion ). Sie werden schnell dünner als$p$ wächst.
Daher ist die zweite Methode der Frage im Allgemeinen falsch und die meisten Primzahlen$p$von Interesse für die vorliegende Anwendung (da sie groß sein müssen: tausend Bits). Wahrscheinlich kam es als falsche Erweiterung der folgenden Tatsache: wann$p$ ist Prime, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ es sei denn $a$ ist ein Vielfaches von $p$, was aus Fermats kleinem Satz folgt .
Im Drei-Pass-Austausch der Frage $m'$ von Bob am Ende erhalten ist $m$ schon seit $$\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}$$