Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a number theory class but my professor just put the homework about RSA encryption where we have absolutely no clue how to do, here's the two question, help appreciated:

a) A word has been broken into blocks of two letters and converted to two-digit numbers using the correspondence:


The blocks are then encoded using the public key code with base 87 and exponent 19. The coded message is $04/10$. Find the word which was coded.

b) A public key code has base 143 and exponent 103. It uses the following letter-to-number equivalents:


A message has been converted to numbers and broken into blocks. When coded using the above base and exponent the message sent is $10/03$. Decode the message.

share|cite|improve this question
Allow me, how can you have absolutely no clue, you should have been exposed to RSA before this exercise. – Andreas Caranti Mar 22 '13 at 7:08
Your professor must have a sense of humour, as the first word is fool (no joke). The second one is JOHN. – Andreas Caranti Mar 22 '13 at 7:15
up vote 5 down vote accepted

Part (a) really has two ciphertexts you have to decode: $04$ and $10$. I'll step you through the decoding of $04$. Using the notation from the Wikipedia article, you have $n=87$, $e=19$, and $c=04$.

To decode, you need to compute the decoding exponent $d=e^{-1} \text{ mod}$ $\varphi(n)$. You can do that using the extended Euclidean algorithm. You should get $d=3$.

Now the original message will be $m=c^d \text{ mod } n = 04^3 \text{ mod } 87 = 64 $. This corresponds to the letters fo by the key you gave in the question.

Try to apply a similar process to the others. Andreas gave the correct answers in the comments, so you can check your work against those.

share|cite|improve this answer
Shouldn't the first one be "FOOD"? – user67258 Mar 22 '13 at 16:10
Oops. Yes, it should. – Snowball Mar 22 '13 at 19:26

Your Answer


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