找到计算RSA算法私钥的有效算法

Question

我是一名计算机专业的学生，我正在自学算法课程。

在课程中我看到了这个问题：

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).

我的解决方案：

我从问题中了解到，我们使用 public 键 (N, e)。

RSA 协议使用

two primes p and q and, N = pq

For any e relatively prime to (p − 1)(q − 1)

我知道因为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)

Answer 1

费马小定理说 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，这就是它给出错误结果的原因.

找到计算RSA算法私钥的有效算法

find efficient algorithm that calculate private key for RSA algorithm

encryption

algorithm

rsa