# RSA Cryptography math problem

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.

• You should look for the GCD of the two moduli, shouldn't you? Wouldn't that be the lucky prime in question? Dec 11 '15 at 7:02
• @BrianTung Alright, so I got gcd(124137798108168664109413, 283967477199546905990801) = 556864830521... How do I decrypt the message?
– KFC
Dec 11 '15 at 7:13

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.

• So, I'm left with $$257d_1\equiv 1\pmod{(556864830520)(q_1-1)}$$$$257d_2\equiv 1\pmod{(556864830520)(q_2-1)}$$right?
– KFC
Dec 11 '15 at 7:20
• Well, you can find out what $q_1 = m_1/p$ and $q_2 = m_2/p$ are first, yes? You know the two moduli and the lucky prime now. Dec 11 '15 at 7:21
• So$$257d_1\equiv 1\pmod{(556864830520)(222922675852)}$$$$257d_2\equiv 1\pmod{(556864830520)(509939686680)}$$right?
– KFC
Dec 11 '15 at 7:24
• I haven't the wherewithal at the moment to confirm your arithmetic, but the form of the equations are correct. Dec 11 '15 at 7:25
• So how would I find $d_1$ and $d_2$? Would I have to multiply those 2 large numbers together?
– KFC
Dec 11 '15 at 7:27