Public Key Cryptography

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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