RSA Encryption with number theory

1.7k Views Asked by At

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:

$$a=0,b=1,c=2,d=3,o=4,k=5,f=6,h=7,l=8,j=9$$

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:

$$J=1,N=2,R=3,H=4,D=5,A=6,S=7,Y=8,T=9,O=0$$

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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.