I have this math problem I'm kind of stuck on.
You intercept the message 27284682555982882069237 which was encrypted using a public modulus of 124137798108168664109413 and an encryption exponent 257. The modulus is now too large to be factored by testing successive candidate divisors (although it can be done using more sophisticated algorithms). However Bob, who is the intended recipient of the message, runs several online businesses. and the public key information for his other business is modulus 283967477199546905990801 and encryption exponent 257.
You have heard a rumor that Bob has a ‘lucky prime’, which he uses as one of the prime factors for all the moduli he generates. Verify that this rumor is true (how do you check if the two moduli have a common prime factor?) and then use this information to decrypt the message.
I know that this is an RSA problem... so I believe that $p = 124137798108168664109413$ and $e = 257$, if that's correct... However, I'm sot sure how to continue. Thanks.
Call the moduli $m_1$ and $m_2$, to avoid my having to refer to those big long numbers. The rumor that Bob uses a "lucky prime" $p$ is equivalent to the claim that there exist two other primes $q_1, q_2$ such that $m_1 = pq_1$ and $m_2 = pq_2$.
In that case, the totient values of the two moduli are
$$ \phi(m_1) = (p-1)(q_1-1) $$ $$ \phi(m_2) = (p-1)(q_2-1) $$
We know that for both keys, the encryption exponent is $e = 257$. So then the decryption exponents $d_1, d_2$ are characterized by
$$ ed_1 \equiv 1 \pmod{\phi(m_1)} $$ $$ ed_2 \equiv 1 \pmod{\phi(m_2)} $$
Hopefully, you can take it from here.