RSA找到公開指數的逆

我對RSA密鑰生成及其用法有一個非常基本的疑問。

RSA找到公開指數的逆

在RSA密鑰生成中，您可以選擇一個非常大的訂單中的兩個大素數。然後你乘以它們（等式p * q = N）現在，Euler(N)=(p-1)(q-1)。現在你找到一個數字0 < e < Euler(N)，這樣e和Euler（N）是相互矛盾的。 {e.Euler(N)}成爲您的公鑰。現在你計算d（私鑰），例如e * d =1 (mod(Euler(N)))。
現在假設你用你的公鑰加密了一些東西（m） - c=m^e(mod(N)). 現在用私鑰（d）解密時，你的確做了c^d(mod(N))。
現在我懷疑你是否發現mod（Euler（N））中e的反函數，但是當你解密的時候你是用mod（N）來做的。這怎麼可能？

來源

2012-04-06 Ashwin

查看wikipedia here和here。基本上，你想解密以「撤消」加密。由於E * d = 1個模φ（N）是相當於E * d = 1 + K *φ（N）的一些整數k，則有：

Ç^d模N =（M ^Ë ）^d模N = M ^{（E * d）}模N = M ^{（1個+ K *φ（N））} =（M ）*（米^φ（N））^ķ mod N

通過應用您在代數中學到的以下規則：

1）^XY =（一個^X）^Ý =（一個^Ý）^X，並
2）^{X + Y} =一個^X *一個^ÿ

要完成這一點，並簡化（米）*（米^φ（N））^ķ模N，記得THA T A ^φ（N） = 1模N，因此

（米^φ（N））^ķ模N = 1 ^ķ = 1模N.

來源

2012-04-06 11:56:47

謝謝回覆。但是我仍然沒有得到^ phi（N）= 1的部分。它如何確保a（這是我們的信息）和N是相互矛盾的。我不太理解你的解釋。 – Ashwin 2012-04-06 14:19:48

@Ashwin：不能保證。對於RSA模量的預期大小而言，它實際上不太可能發生，所以可能性被忽略。 – 2012-04-06 21:56:46

沒問題.. N = p * q其中p和q是素數。那麼，a和n不是共素的唯一的cse是a = p還是a = q？這是不太可能的。 – Ashwin 2012-04-07 00:47:12

RSA找到公開指數的逆

回答

相關問題