0
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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