解決 Diffie-Hellman 密鑰交換的捷徑
我正在嘗試在不使用計算器的情況下手動計算 Alice 和 Bob 的共享密鑰，因為我覺得這是進入密碼學的一個重要特徵。
我知道您可以使用平方和乘法方法，但是我們正在學習一種我不太了解的快捷方法。
問題範例：
Alice 和 Bob 使用 DH 協議，p = 19,g = 2，秘密 a = 6 和 b = 8。他們同意什麼密鑰？
他們沒有太多解釋就給了我們這個過程： $$ K = 2^{6×8} ≡8^{2×8} ≡7^8 ≡11^4 ≡7^2 ≡11 \pmod{19} $$
$ 2^{6×8} $ ，不知道如何將乘法作為上述問題的冪。
如果有人可以一步一步地深入解釋上面完成的快捷過程。我真的很感激
我了解某些部分，例如 $ g^a*b \pmod{19} = 6 = 2^3 = 8 $ ，但是我從那裡有點困惑。
回想一下，對於 $ \forall x\in\mathbb N $ , $ \forall m,u,v\in\mathbb N^* $ ， 它擁有 $ {(x^u\bmod m)}^n\equiv{(x^u)}^v\equiv x^{u\times v}\pmod m $ ， 在哪裡 $ y\equiv x\pmod m $ 方法 $ m $ 劃分 $ x-y $ ， 和 $ x\bmod m $ 是唯一定義的整數 $ y $ 這樣 $ 0\le y<m $ 和 $ y\equiv x\pmod m $ .
共享的秘密是 $ K=(g^a\bmod p)^b\bmod p=(g^b\bmod p)^a\bmod p $ , 或等效地 $ K=g^{a\times b}\bmod p $ . 我們的任務是對此進行評估 $ a=6 $ , $ b=8 $ , $ g=2 $ , $ p=19 $ .
問題中的方法是： $$ \begin{array}{} K&={(2^6\bmod19)}^8\bmod19&&=2^{6\times8}\bmod19\ &=2^{(3\times2)\times8}\bmod19&={(2^3)}^{2\times8}\bmod19&=8^{2\times8}\bmod19\ &={(8^2)}^8\bmod19&=64^8\bmod19\ &&=(64-19\times3)^8\bmod19&=7^8\bmod19\ &={(7^2)}^4\bmod19&=49^4\bmod19\ &&=(49-19\times2)^4\bmod19&=11^4\bmod19\ &={(11^2)}^2\bmod19&=121^2\bmod19\ &&=(121-19\times6)^2\bmod19&=7^2\bmod19\ &=49\bmod19&=49-19\times2&=11\ \end{array} $$ 並且（保留最右邊的列）可以濃縮為： $$ K\equiv2^{6\times8}\equiv8^{2\times8}\equiv7^8\equiv11^4\equiv7^2\equiv11\pmod{19}\ \text{ thus }\ K=11 $$
如果我要在沒有計算器的情況下計算這個，我會把它寫成 $ K=2^{48}\bmod19 $ ，然後使用費馬小定理。它說當 $ p $ 是素數並且 $ g $ 不是的倍數 $ p $ , 如果成立 $ g^{p-1}\bmod p=1 $ . 這允許減少模 $ (p-1) $ 的任何指數 $ g $ 計算模時 $ p $ . 完整的計算如下： $$ \begin{array}{} K&=2^{6\times8}\bmod19&&=2^{48}\bmod19\ &=2^{48\bmod(19-1)}\bmod19&=2^{48-18\times2}\bmod19&=2^{12}\bmod19\ &=4096\bmod19&=4096-19\times215&=11\end{array} $$
注：在 $ 48-18\times2=12 $ ， 這 $ 2 $ 作為商獲得 $ \lfloor48/18\rfloor $ , 很像 $ 4096-19\times215=11 $ 這 $ 215 $ 是 $ \lfloor4096/19\rfloor $ .
實際的密碼學使用的整數對於可靠的人類計算來說太大了；例如 $ p $ 可以是 2048 位，即 617 位十進制數字。