Dua rumus berfungsi untuk masalah pertukaran tiga lintasan ini, tetapi saya tidak tahu mengapa salah satunya berfungsi
Pernyataan masalah:
Misalkan pengguna Alice dan Bob melaksanakan protokol Diffie-Hellman 3-pass dengan p = 101. Misalkan Alice memilih 1 = 19 dan Bob memilih b 1 = 13. Jika Alice ingin mengirim pesan rahasia m = 5 ke Bob, tunjukkan semua pesan yang dipertukarkan antara Alice dan Bob. "
Solusi resmi:
$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 memperoleh $m$ dengan mengevaluasi $56^{b_2}\bmod p=5$
Solusi yang saya buat menggunakan bantuan seseorang (karena saya tidak dapat menemukan informasi yang sangat spesifik tentang protokol tiga jalur ini secara online):
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 ke Bob # 1:
$\begin{align} m_\text{AliceToBob1}&=m^{a_1}\bmod p\\ &=5^{19}\bmod101\\ &=37\end{align}$
Bob to Alice (# 1 - tidak ada # 2):
$\begin{align} m_\text{BobToAlice}&={m_\text{AliceToBob1}}^{b_1}\bmod p\\ &=37^{13}\bmod101\\ &=80\end{align}$
Alice ke Bob # 2:
$\begin{align} m_\text{AliceToBob2}&={m_\text{BobToAlice}}^{a_2}\bmod p\\ &=80^7\bmod101\\ &=56\end{align}$
Bob mendapatkan pesan sebagai berikut:
$\begin{align} m'&={m_\text{AliceToBob2}}^{b_2}\bmod p\\ &=56^{77}\bmod101\\ &=5\end{align}$
Pertanyaan saya:
Mengapa solusi resmi digunakan $a_2={a_1}^{-1}\bmod(p-1)=79$ dari pada $a_2={a_1}^{p-2}\bmod(p-1)=79$, dan bagaimana kesetaraan dalam konteks jenis masalah ini dapat dibenarkan? (Saya mengatakan "dalam konteks jenis masalah ini" karena, menurut pemahaman saya, kedua ekspresi tersebut tidak selalu sama).
Setiap masukan yang dapat membantu saya menjelaskan kebingungan saya akan SANGAT dihargai!
PS
- $a_1$ adalah kunci enkripsi Alice
- $a_2$ adalah kunci dekripsi Alice
- $b_1$ adalah kunci enkripsi Bob
- $b_2$ adalah kunci dekripsi Bob
Jawaban
TL; DR: metode kedua hanya berfungsi untuk proporsi bilangan prima yang menghilang $p$.
Pertanyaannya menggunakan relasi yang sama antara $a_1$ dan $a_2$seperti pada sandi simetris Pohlig-Hellman. Di dalam:
- $p$ adalah parameter prima publik,
- kunci enkripsi adalah bilangan bulat acak $a_1$ coprime dengan$p-1$,
- kunci dekripsi adalah bilangan bulat $a_2$ seperti yang $a_1\,a_2=k\,(p-1)+1$ untuk beberapa bilangan bulat $k$.
- enkripsi adalah per $m\mapsto c=m^{a_1}\bmod p$, untuk $m$ di $[0,p)$,
- dekripsi adalah per $c\mapsto m'=c^{a_2}\bmod p$, dan itu berlaku $m'=m$.
Bukti: $$\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}$$
Catatan: Teorema kecil Fermat mengatakan bahwa kapan$p$ adalah bilangan prima dan $m$ bukan kelipatan $p$, itu berlaku $m^{p-1}\bmod p=1$.
Satu bilangan bulat yang cocok $a_2$, dan satu-satunya dalam jangkauan $[0,p-1)\,$, adalah ${a_1}^{-1}\bmod(p-1)\,$: kebalikan perkalian dari$a_1$ modulo $p-1$. Itulah yang digunakan dalam solusi resmi pertanyaan itu .
Metode buku teks untuk menghitung pembalikan perkalian itu adalah algoritma Extended Euclidean . Untuk implementasi praktis, saya merekomendasikan varian ini yang menggunakan dua variabel lebih sedikit dan tidak pernah memanipulasi jumlah negatif.
Solusi pertanyaan lain hanya berbeda dengan menghitung hal yang sama $a_2$ menggunakan rumus yang berbeda: ${a_1}^{p-2}\bmod(p-1)$. Jadi pertanyaannya adalah:
Untuk prime $p>2$, mengapa / kapan seperti itu $a^{-1}\bmod(p-1)$ dapat dihitung sebagai $a^{p-2}\bmod(p-1)$ ?
Menurut definisi, $a^{-1}\bmod(p-1)$ adalah bilangan bulat $x$ di $[0,p-1)$ dengan $a\,x\bmod(p-1)=1$. Ini didefinisikan hanya jika$a$ adalah coprime dengan $p-1$. Oleh karena itu, pertanyaannya sama dengan:
Untuk prime $p>2$, mengapa / kapan seperti itu $a^{p-1}\bmod(p-1)=1$ untuk semua $a$ coprime untuk $p-1$?
Itu untuk banyak orang $p$ termasuk pertanyaannya $p=101$, tapi tidak selalu. Counterexample terkecil adalah$p=11$, $a=3$. Lain itu$p=103$, $a=5$. Dapat dibuktikan bahwa menggunakan metode kedua untuk ini$p$ dan kunci enkripsi menyebabkan sebagian besar dekripsi salah $m$.
Ini adalah bilangan prima A337119 (dibuat untuk acara ini), dimulai dengan
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
Ini juga merupakan bilangan prima $p$ seperti yang $p-1$adalah nomor Novák-Carmichael A124240 ; atau setara dengan bilangan prima$p$ seperti yang $\lambda(p-1)$ membagi $p-1$ (dimana $\lambda$adalah fungsi Carmichael ). Mereka dengan cepat menipis$p$ tumbuh.
Oleh karena itu metode kedua pertanyaan itu salah secara umum, dan paling prima$p$menarik untuk aplikasi yang ada (karena ukurannya besar: ribuan bit). Kemungkinan itu datang sebagai perpanjangan yang salah dari fakta berikut: kapan$p$ adalah bilangan prima, $a^{-1}\bmod p\;=\;a^{p-2}\bmod p$ kecuali kalau $a$ adalah kelipatan dari $p$, yang mengikuti dari teorema kecil Fermat .
Dalam pertukaran tiga jalur pertanyaan, $m'$ yang didapat oleh Bob pada akhirnya adalah $m$ sejak $$\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}$$