在給定公共指數和使用擴展歐幾里得的模因子時計算 RSA 私有指數
給予時 $ p = 5, q = 11, N = 55 $ 和 $ e = 17 $ ，我正在嘗試計算 RSA 私鑰 $ d $ .
我可以計算 $ \varphi(N) = 40 $ ，但我的講師然後說使用擴展歐幾里得算法來計算 $ d $ . 這就是我卡住的地方。
到目前為止，這是我的工作：
首先我使用歐幾里得算法來計算：
40 = 2(17) + 6 17 = 2(6) + 5 6 = 1(5) + 1 = gcd所以我知道 GCD 是 1。應用算法的“擴展”部分：
6 = 40-2(17) 5 = 17-2(6) 1 = 6-1(5) 1 = 6-1(17-2(6)) 3(6) = 1 (17) 3(40 - 2(17)) - 1(17) 3(40) - 3(17)我知道答案是 $ 33 $ ，但我不知道如何使用擴展的歐幾里得算法到達那裡。我不知道為什麼我會得到 $ 3(40) - 3(17) $ 當我知道答案應該包含 $ 33 $ .
擴展的歐幾里得算法本質上是向後執行的歐幾里得算法（對於 GCD 的）。
你的目標是找到 $ d $ 這樣 $ ed \equiv 1 \pmod{\varphi{(n)}} $ .
呼叫 EED 計算 $ x $ 和 $ y $ 這樣 $ ax + by = \gcd{(a, b)} $ . 現在讓 $ a = e $ , $ b = \varphi{(n)} $ ， 因此 $ \gcd{(e, \varphi{(n)})} = 1 $ 根據定義（它們需要互質才能存在逆）。然後你有：
$$ ex + \varphi{(n)} y = 1 $$ 取這個模 $ \varphi{(n)} $ ，你得到：
$$ ex \equiv 1 \pmod{\varphi{(n)}} $$ 很容易看出，在這種情況下， $ x = d $ . 的價值 $ y $ 實際上並不重要，因為它會被模消除 $ \varphi{(n)} $ 不管它的價值。EED 將為您提供該值，但您可以放心地丟棄它。
現在，我們有 $ e = 17 $ 和 $ \varphi{(n)} = 40 $ . 寫出我們的主要方程：
$$ 17x + 40y = 1 $$ 我們需要解決這個問題 $ x $ . 所以應用普通的歐幾里得算法：
$$ 40 = 2 \times 17 + 6 $$ $$ 17 = 2 \times 6 + 5 $$ $$ 6 = 1 \times 5 + 1 $$ 把最後一個寫成：
$$ 6 - 1 \times 5 = 1 $$ 現在將第二個方程代入 $ 5 $ :
$$ 6 - 1 \times (17 - 2 \times 6) = 1 $$ 現在將第一個方程代入 $ 6 $ :
$$ (40 - 2 \times 17) - 1 \times (17 - 2 \times (40 - 2 \times 17)) = 1 $$ 注意這是一個線性組合 $ 17 $ 和 $ 40 $ ，簡化後得到：
$$ (-7) \times 17 + 3 \times 40 = 1 $$ 我們得出結論 $ d = -7 $ , 這實際上是 $ 33 $ 模組 $ 40 $ （自從 $ -7 + 40 = 33 $ ).
如您所見，基本思想是使用 GCD 計算的連續餘數將初始整數代入最終方程（等於 $ 1 $ ) 給出所需的線性組合。
至於您的錯誤，您似乎只是在這裡犯了一個計算錯誤：
3(40 - 2(17)) - 1(17)
錯誤地變成了：
3(40) - 3(17)
看來您忘記了左邊 17 的因子 3，正確的結果是：
3(40 - 2(17)) - 1(17) = 3 * 40 - 3 * 2 * 17 - 1 * 17 = 3 * 40 + (-7) * 17
這是預期的-7。