如何確定此RSA算法示例中的d？

作爲我大學課程的一部分，我得到了一個要解決的問題。這是關於RSA算法的主題。如何確定此RSA算法示例中的d？

我已經給出P = 29，Q = 17和E = 5

我必須確定d。

所以我知道N = 29×17 => 493和phi（N）= 448

於是我坐下來，我知道

5 * d mod 448 = 1

然後我按照歐幾里得算法點得到

448 = 89(5) + 3

其中3是其餘（商）。在前面的例子中，我完成了商數最終爲1的情況，解決d是很容易的。然而，我不知道如何去做這個例子，其餘的是3.

有沒有人知道如何做到這一點？幫助將不勝感激。

來源

2017-02-15 Alex Naughton

這東西，我不能選另一個。我在這個問題中被賦予了e = 5，並且僅限於此。 –

你沒有完成擴展的歐幾里德算法。（https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm）

你應該有(r_i, s_i, t_i)：

(448,1,0) => 1*448 + 0*5 = 448 
(5, 0, 1) => 0*448 + 1*5 = 5 
(3, 1, -89) => 1*448 - 89*5 = 3 
(2, -1, 90) => -1*448 + 90*5 = 2 
(1, 2, -179) => 2*448 - 179*5 = 1

您可以檢查一下是否2*448 - 179*5 = 1，所以-179 * 5 = 1 mod 448，或269*5 = 1 mod 448，你的答案是d = 269

來源

2017-02-15 05:40:59

但是5 * d mod 448必須等於1嗎？ –

當然，它確實對不起，我失算了 –

如何確定此RSA算法示例中的d？

回答

相關問題