I have a couple of questions pertaining to a RSA problem. I need to decipher some ciphertext and find out what the original plaintext was.

Modulus: $n = 2537$ and exponent: $a = 11$

Encrypting function: $E(x) = x^{11} \mod 2537$

Using Fermat's Little Theorem to start, I have successfully encrypted some plaintext and decrypted it, so I do know what the other required numbers in this particular RSA system are, however if initially I am only given $n$ and $a$ can I:

  1. Mathematically work out some plaintext, if the ciphertext, $n$, and $a$ are known? If so would I basically step through the encryption process in reverse?

  2. If not, what is the best/most effective cryptanalysis method to work out what the original plaintext is, if $n$ is relatively small (2537) and $a$ is relatively small (11)?

Note: This is needs to be calculated using the 'maths' behind the system and not a specific computer function.


For small numbers the easiest ways to break RSA are:

  1. Brute force the private (decryption) exponent. I.e. find the smallest value $b$ such that $(x^a)^b \mod n = x$ for all $x$.
  2. Factorize the modulus (trial division is simplest and works fine for small numbers), then use the factors to generate the private exponent.

Assuming you are supposed to use the maths, 2. is probably expected.

  • 1
    $\begingroup$ Note that this only applies to properly padded RSA. Textbook RSA has weaknesses a plenty. $\endgroup$ – CodesInChaos Aug 13 '14 at 8:42
  • $\begingroup$ @CodesInChaos, "this" being? $\endgroup$ – otus Aug 13 '14 at 8:45
  • $\begingroup$ Your claim that these are the easiest way of breaking RSA. $\endgroup$ – CodesInChaos Aug 13 '14 at 8:51
  • $\begingroup$ @CodesInChaos "for small numbers", but yeah, there are other weaknesses to exploit when the message is unpadded plaintext. $\endgroup$ – otus Aug 13 '14 at 8:54
  • 2
    $\begingroup$ @user3728778 Boneh wrote a paper listing most know attacks on RSA $\endgroup$ – CodesInChaos Aug 13 '14 at 19:21

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.