Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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.

share|improve this answer
1  
Note that this only applies to properly padded RSA. Textbook RSA has weaknesses a plenty. –  CodesInChaos Aug 13 at 8:42
    
@CodesInChaos, "this" being? –  otus Aug 13 at 8:45
    
Your claim that these are the easiest way of breaking RSA. –  CodesInChaos Aug 13 at 8:51
    
@CodesInChaos "for small numbers", but yeah, there are other weaknesses to exploit when the message is unpadded plaintext. –  otus Aug 13 at 8:54
2  

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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