find efficient algorithm that calculate private key for RSA algorithm-CodePudding

I am a computer science student, I am studying the Algorithms course independently.

During the course I saw this 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).

my solution:

What I understand from the question is, we use a public key (N, e).

RSA protocol using

two primes p and q and, N = pq

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

I know that because N is equal to p which is a prime number, I can efficiently calculate the private key d and then also m. In polynomial time.

my idea is because i know p and e, i can calculate d, d is reciprocal for e.

this the an algorithm that i write, but I have struggle to do it

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

i dont sure if the algorithm is right , i want to find d , and than i will able using d as private key to read encrypted message m^e(mod p)

CodePudding user response：

Fermat's Little Theorem says that m^(p-1) = 1 (mod p), so you need to find d such that ed = 1 (mod p-1), and then (m^e)^d = m^(ed) = m (mod p).

Thus, find d, the multiplicative inverse of e mod p-1, which is possible if e and p-1 are coprime. Then you can "decrypt" a message m^e (mod p) by raising it to the power of d (mod p) to get back the plaintext m (mod p).

Assuming your extended Euclidean algorithm code is correct, your code finds the multiplicative inverse of e mod p, rather than e mod p-1, which is why it is giving the wrong result.