1. ## RSA cryptology question

I have this problem:

Eve is trying to break an RSA mssage which she knows is based on the modulus n = 3454039
Suppose she discovers that the primes p,q giving n = pq sum to 4880
Knowing that the encrypting exponent is e = 151
help her compute the decrypting exponent d. also, help her reconstruct the primes p,q giving n=pq

so my first problem is how do factor out n? Is there a trick to it considering that p and q sum to 4880? Then after I factor n, I compute the Euler phi function of n to compute the decrypting exponent through d*e = 1 mod phi(n) right?

2. ## Factoring Trick

I don't remember the exact details of RSA, but consider:

$\displaystyle pq=3454039$ and $\displaystyle q=4880-p$, so $\displaystyle p(4880-p)=3454039$, ergo $\displaystyle p^2-4880p+3454039=0$ . This is quadratic with $\displaystyle p,q$ the roots, can you take it from there?

3. Originally Posted by dlbsd
I have this problem:

Eve is trying to break an RSA mssage which she knows is based on the modulus n = 3454039
Suppose she discovers that the primes p,q giving n = pq sum to 4880
Knowing that the encrypting exponent is e = 151
help her compute the decrypting exponent d. also, help her reconstruct the primes p,q giving n=pq

so my first problem is how do factor out n? Is there a trick to it considering that p and q sum to 4880? Then after I factor n, I compute the Euler phi function of n to compute the decrypting exponent through d*e = 1 mod phi(n) right?
It appears as if you were given all of the information necessary to understand the RSA system. Not to burden you, but could you state the basic function of the RSA method. This is for my own review, plus it may assist you.
Along with that, do you have the actual message that Eve is attempting to de-crypt?

What we know:
n = 3454039 = p*q
p+q = 4880
e = 151
plus
(p-1)(q-1) = pq -p -q +1 = phi(n)