5
$\begingroup$

Assuming that a message has been sent via the RSA scheme with $p=37$, $q=73$, and $e=5$, what is the decoding of the received message "34?"

So far, I have $x^5 \pmod{37\times73} \equiv 34$. How do I invert a mod?

$\endgroup$
2
$\begingroup$

We need the totient function of the modulus, hence we get:

$$\varphi(N) = \varphi(37 \times 73) = 36 \times 72 = 2592$$

First you need to find the decryption exponent.

$$d = e^{-1} \pmod {\varphi(n)} = 5^{-1} \pmod {2592} = 1037$$

Decryption:

$$\displaystyle m = c^{\large d} \pmod N \rightarrow 34^{1037} \pmod {2701} = 1415$$

$\endgroup$
  • $\begingroup$ we can find even smaller exponent using Carmichael function(find in my answer), $$5^{-1}\equiv29\pmod{72}$$ $\endgroup$ – lab bhattacharjee Nov 29 '13 at 16:19
  • $\begingroup$ Another T-U-V $+1$ $\endgroup$ – Namaste Nov 29 '13 at 16:51
1
$\begingroup$

$$n=37\cdot 73 \,;\, phi(n)=(37-1)\cdot (73-1)$$

Calculate $\phi(n)$ and then solve

$$de \equiv 1 \pmod{\phi(n)}$$

Then

$$x\equiv 34^d \pmod{n} \,.$$

$\endgroup$
1
$\begingroup$

HINT:

using Carmichael function,

$$\lambda(37\cdot73)=72\implies x^{72}\equiv1\pmod{37\cdot73}$$ as $(x,37\cdot73)=1$ as $(34, 37\cdot73)=1$

$$ \implies x^{144}\equiv1\pmod{37\cdot73}\implies x^{145}\equiv x\implies x\equiv (x^5)^{29}\equiv34^{29}\pmod{37\cdot73}$$

Now, we can find $ 34^{29} \pmod{37\cdot73}$ using congruence properties

$\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.