如何處理擴展歐幾里德算法的結果

Question

我目前正在撰寫一篇有關公鑰加密，RSA的文章。 我瞭解公鑰和私鑰生成中涉及的大部分算法。但我很難理解我用Bézout的身份做什麼來獲得私鑰？而且我也不太明白爲什麼使用Bézout的身份？

假設：

n=55 
phi(n)=40  
e = 7 

使E * d MOD島（N）= 1

7*d mod 40 = 1 
gcd(40,7) = 1 

而且使貝祖等式是這樣的：

3(40)-17(7)=1 

在哪裏40和7分別是phi（n）和e。

我從例子中知道d應該是23. 所以我正確的是d = e-17？

如果不是如何得到d？

Answer 1

在你的例子中，d = -17（因爲Bézout的身份說，存在x和y，使得x*a + y*b = gcd(a,b)）。

你正在尋找一個d這樣e*d = 1 mod phi(n)，這樣你就可以這樣消極d轉換成通過簡單地添加的phi(n)倍數仍滿足方程正值。在這種情況下，我們只需要添加phi(n)一次，這給出了d您的期望值：

-17 + phi(n) = -17 + 40 = 23