Dwie formuły działają w przypadku tego problemu z wymianą trzech przebiegów, ale nie mogę zrozumieć, dlaczego jedna z nich działa
Opis problemu:
„Załóżmy, że użytkownicy Alicja i Bob wykonują 3-przebiegowy protokół Diffie-Hellman z p = 101. Załóżmy, że Alicja wybiera 1 = 19, a Bob wybiera b 1 = 13. Jeśli Alicja chce wysłać tajną wiadomość m = 5 do Bob, pokaż wszystkie wiadomości wymieniane między Alicją i Bobem ”.
Oficjalne rozwiązanie:
$a_2 = {a_1}^{-1}\bmod(p-1)=79$
$b_2=77$
Alicja → Bob: $m^{a_1}\bmod p=37$
Bob → Alicja: $80$
Alicja → Bob: $56$
Bob uzyskuje $m$ oceniając $56^{b_2}\bmod p=5$
Rozwiązanie, które zrobiłem korzystając z czyjejś pomocy (ponieważ nie mogę znaleźć bardzo szczegółowych informacji o tym protokole trójprzebiegowym w Internecie):
Alicja:
$\begin{align} a_2&={a_1}^{p-2}\bmod(p-1)\\ &=19^{99}\bmod100\\ &=79\end{align}$
Pion:
$\begin{align} b_2&={b_1}^{p-2}\bmod(p-1)\\ &=13^{99}\bmod100\\ &=77\end{align}$
Alicja do Boba # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob do Alicji (nr 1 - nie ma nr 2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alicja do Boba # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob otrzymuje wiadomość w następujący sposób:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Moje pytanie:
Dlaczego oficjalne rozwiązanie używa $a_2={a_1}^{-1}\bmod(p-1)=79$ zamiast $a_2={a_1}^{p-2}\bmod(p-1)=79$i jak uzasadnić tę równoważność w kontekście tego typu problemu ? (Mówię „w kontekście tego typu problemu”, ponieważ w moim rozumieniu te dwa wyrażenia nie zawsze są równoważne).
Każdy wkład, który pomógłby mi wyjaśnić moje zamieszanie, byłby BARDZO doceniony!
PS
- $a_1$ to klucz szyfrujący Alicji
- $a_2$ to klucz deszyfrujący Alicji
- $b_1$ to klucz szyfrujący Roberta
- $b_2$ to klucz odszyfrowywania Roberta
Odpowiedzi
TL; DR: druga metoda działa tylko dla znikającej części liczb pierwszych $p$.
Pytanie wykorzystuje tę samą relację między $a_1$ i $a_2$jak w szyfrze symetrycznym Pohliga-Hellmana. W tym:
- $p$ jest publicznym parametrem głównym,
- klucz szyfrowania jest losową liczbą całkowitą $a_1$ względnie pierwsze z$p-1$,
- klucz odszyfrowywania jest liczbą całkowitą $a_2$ takie że $a_1\,a_2=k\,(p-1)+1$ dla jakiejś liczby całkowitej $k$.
- szyfrowanie jest na $m\mapsto c=m^{a_1}\bmod p$, dla $m$ w $[0,p)$,
- odszyfrowanie jest na $c\mapsto m'=c^{a_2}\bmod p$i utrzymuje $m'=m$.
Dowód: $$\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}$$
Uwaga: małe twierdzenie Fermata mówi, kiedy$p$ jest liczbą pierwszą i $m$ nie jest wielokrotnością $p$, zawiera $m^{p-1}\bmod p=1$.
Jedna odpowiednia liczba całkowita $a_2$i jedyny w zasięgu $[0,p-1)\,$, jest ${a_1}^{-1}\bmod(p-1)\,$: The Liczba odwrotna od$a_1$ modulo $p-1$. To właśnie jest używane w oficjalnym rozwiązaniu pytania .
Podręcznikową metodą obliczania tej multiplikatywnej odwrotności jest algorytm rozszerzonego euklidesa . Dla praktycznych wdrożeń polecam ten wariant, który używa dwóch mniej zmiennych i nigdy nie manipuluje wielkościami ujemnymi.
Inne rozwiązanie tego pytania różni się tylko obliczeniem tego samego $a_2$ używając innego wzoru: ${a_1}^{p-2}\bmod(p-1)$. Więc pytanie sprowadza się do:
Za najlepsze $p>2$, dlaczego / kiedy to jest to $a^{-1}\bmod(p-1)$ można obliczyć jako $a^{p-2}\bmod(p-1)$ ?
Zgodnie z definicją, $a^{-1}\bmod(p-1)$ jest liczbą całkowitą $x$ w $[0,p-1)$ z $a\,x\bmod(p-1)=1$. Jest definiowany tylko wtedy, gdy$a$ jest względnie pierwsze z $p-1$. Wynika z tego, że pytanie jest równoważne z:
Za najlepsze $p>2$, dlaczego / kiedy to jest to $a^{p-1}\bmod(p-1)=1$ dla wszystkich $a$ względnie pierwsze do $p-1$?
To dla wielu $p$ w tym pytanie $p=101$, ale nie zawsze. Najmniejszy kontrprzykład to$p=11$, $a=3$. Jeszcze jedno$p=103$, $a=5$. Można to zweryfikować za pomocą drugiej metody$p$ a klucze szyfrujące prowadzą do nieprawidłowego odszyfrowania większości plików $m$.
Są to liczby pierwsze z formularza A337119 (stworzonego na tę okazję), zaczynając od
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
To także są liczby pierwsze $p$ takie że $p-1$to numer Novák-Carmichael A124240 ; lub równoważnie liczby pierwsze$p$ takie że $\lambda(p-1)$ dzieli $p-1$ (gdzie $\lambda$jest funkcją Carmichaela ). Szybko się rozrzedzają$p$ rośnie.
Dlatego druga metoda pytania jest ogólnie błędna i większość liczb pierwszych$p$interesujące dla aplikacji (ponieważ są duże: tysiące bitów). Prawdopodobnie było to nieprawidłowe rozszerzenie następującego faktu: kiedy$p$ jest pierwsza, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ chyba że $a$ jest wielokrotnością $p$, co wynika z małego twierdzenia Fermata .
W trójprzebiegowej wymianie pytania $m'$ uzyskane przez Boba w końcu jest $m$ od $$\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}$$