我是一名計算機科學專業的學生，??我正在獨立學習演算法課程。
在課程中，我看到了這個問題：
Assume we try to implement the RSA algorithm with public key (p, e) for a prime p (and e such that gcd(e, p ? 1) = 1). Show that this scheme is insecure. That is, show an efficient algorithm that given p, e and m^e(mod p), computes m (mod p).
我的解決方案：
我從這個問題中了解到，我們使用公鑰（N，e）。
RSA協議使用
兩個素數 p 和 q 并且，N = pq
對于任何與 (p ? 1)(q ? 1) 互質的 e
我知道因為 N 等于質數 p，所以我可以有效地計算私鑰 d 和 m。在多項式時間內。
我的想法是因為我知道 p 和 e，我可以計算 d，d 是 e 的倒數。
這是我寫的演算法，但我很難做到
function privatekey(N,e)
Input: Prime integer N , integer e relative prime to N
Output: Private key integer d
d = ext_gcd(N,e)
return d
ext_gcd(X,Y) //ax by = GCD(a,b) = 1
Input: integer a , integer b
Output: return integer y
gcd_steps <= new stack
integer q <= a / b
integer r <= a-b*q
do while (r != 1)
gcd_steps.push(a,b,q,r)
q = a / b
r = a-b*q
a = b
b = r
integer a',b',q',r'
a,b,q,r = gcd_steps.pop()
while (!gcd_steps.isempty())
b' = a
r' = gcd_steps.top_q()*r q
a' = gcd_steps.top_a()
q' = gcd_steps.top_b()*r
a,b,q,r = a',b',q',r'
gcd_steps.pop()
return r
我不確定演算法是否正確，我想找到 d，然后我將能夠使用 d 作為私鑰來讀取加密訊息 m^e(mod p)
uj5u.com熱心網友回復：
費馬小定理說 m^(p-1) = 1 (mod p)，所以你需要找到 d 使得 ed = 1 (mod p-1)，然后 (m^e)^d = m^( ed) = m (mod p)。
因此，找到 d，即 e mod p-1 的乘法逆元，如果 e 和 p-1 互質，這是可能的。然后，您可以通過將訊息 m^e (mod p) 提高到 d (mod p) 的冪來“解密”訊息，以取回明文 m (mod p)。
假設您的擴展歐幾里得演算法代碼是正確的，您的代碼會找到 e mod p 的乘法逆元，而不是 e mod p-1，這就是它給出錯誤結果的原因。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446435.html
下一篇：從兩個節點之間的最短路徑顯示節點