The cryptosystem works as follows:
The plaintext message is first replaced by ciphers (a=00, b=01, etc.) and then encrypted in blocks of four digits. So if the message is "hi", the plaintext number is 0708. The encrypted message is then: $708^{43}\equiv713\pmod{2551}$.
For decryption, one should first find the so-called recovery exponent. In this case, 1957 is the recovery exponent, since $1\equiv43\cdot1957\pmod{2550}$. Indeed, $713^{1957}\equiv708\pmod{2551}$.
Now this problem is given:
The ciphertext obtained from an exponential cipher with modulus $p=2551$ and enciphering exponent $k=43$ is 1518 2175 1249 0823 2407. Determine the plaintext message.
Same as in the explanation, the recovery exponent is 1957. Then:
- $1518^{1957}\equiv2533\pmod{2551}$
- $2157^{1957}\equiv0021\pmod{2551}$
- $1249^{1957}\equiv0426\pmod{2551}$
- $0823^{1957}\equiv1314\pmod{2551}$
- $2407^{1957}\equiv2223\pmod{2551}$
Converting back to letters gives: Z ? A V E _ N O W X.
It is given that 26 is being used to indicate an empty space and 23 at the end to fill the final block. What should I do with 33? Or am I doing something completely wrong here? Thanks in advance.