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.
n = 2537 and a (or the exponent) = 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:
a) 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?
b) 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.
Just factor 2537, as it is small. It's $43 \times 59$ of course, so $\phi(n) = 42 \times 58 = 4236$, so we just invert $e=11$ modulo $4236$ to get $d = 443$. Now you can decrypt using this decryption exponent.
Because $n$ is small and RSA in your form is purely deterministic, you could also brute force all $1 < x < n$ and trying $x^e$ mod $n$ for all these $x$ till you hit the ciphertext. But for large $n$ this is infeasible of course, unless you know more about the structure of the plaintext.
The size of $e$ (your $a$) doesn't matter much, the size of $n$ large is needed to avoid this brute force and of course, the most efficient attack (known so far): factor $n$ and find $d$. Knowing $d$ is equivalent to knowing the factorisation of $n$, and in this case you could also brute force $d$ if you liked (as $d$ is smaller then $n$, it slightly more efficient).