1
$\begingroup$

n = 187 e = 3 C = 185

How to decrypt message? I know there is some way using cryptogram exponentiation. Can you give me a hint?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

For small $N$, textbook RSA decryption is possible without factoring $N$ using the cycling method, (sometime called cycling attack; see this for a reference):

  • initialize $M\gets C$
  • set $D\gets M^e\bmod N$ (otherwise said, encrypt $M$)
  • if $D\ne C$, then set $M\gets D$ and loop to the previous step
  • output $M$ and exit.

Since encryption is a reversible mapping of the finite integer set $[0,N)$, the algorithm must cycle and stop. Obviously, when it does, we have $C=M^e\bmod N$, thus the algorithm has deciphered $C$.

Note: this is unrelated to small $e$. It works well for small $N$, but for other $N$ or multiple messages to decipher, it is more efficient to factor $N$.

Improve this answer
$\endgroup$

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