2
$\begingroup$

I'm trying to find

3185^2753 mod 3233

to decode a RSA message. How can I do it? What is the theorem behind this, if any?

The original question is:

What is the original message encrypted using the RSA system with n=53·61 and e=17 if the encrypted message is 3185 2038 2460 2550? (To decrypt, first find the decryption exponent d, which is the inverse of e=17 modulo 52·60.)

$\endgroup$
3
$\begingroup$

Hints without many words (arithmetic modulo $\,53\,,\,61\,$, Fermat's Little Theorem...):

$$3233=61\cdot 53$$

$$3185=13\pmod {61}\;,\;\;3185=5\pmod {53}\;,\;2753=61\cdot 45+8\;,\;\;2753=53\cdot 52-3$$

$$\implies 3185^{2753}=\left(13^{61}\right)^{45}\cdot 13^8=13^{53}=\left(13^3\right)^{17}\cdot 13^2=1\cdot169=47\pmod{61}$$

$$3185^{2753}=\left(5^{53}\right)^{52}\cdot 5^{-3}=5^{-3}=\left(5^{-1}\right)^3=32^3=14\pmod{53}\ldots$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.