Computing RSA Algorithm

Question

Modulus $N=247$; encryption exponent $r=7$
Encrypt $100$; Decrypt $120$.
$Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$.
For a discrete math textbook I'm reading, I am faced with the above question. It gives the solution but does not really explain how they got it. So at the moment I am completely confused with RSA. Any step by step explanation would be great.

Answer 1

Encryption:

$$\displaystyle c = m^{\large e} \pmod N \rightarrow 100^7 \pmod {247}$$

We need the totient function of the modulus, hence we get:

$$\varphi(N) = \varphi(247) = 216$$

Note that $N = 247 = 13 \cdot 19$, and since each of those is prime (an RSA requirement), we can immediately write $\varphi(N) = \varphi(p \cdot q) = (p - 1)(q-1) = 12 \cdot 18 = 216$. Of course, for real sized RSA numbers, you wouldn't be able to factor them (as far as we know) and use this observation.

To find the decryption exponent , we just find the modular inverse of the encryption exponent using the totient result, hence:

$$d = e^{-1} \pmod {\varphi(n)} = 7^{-1} \pmod {216} = 31$$

Decryption:

$$\displaystyle m = c^{\large d} \pmod N \rightarrow 120^{31} \pmod {247}$$

Where:

• $m$ = message to encrypt or plaintext
• $c$ = encrypted message or ciphertext
• $e$ = encryption exponent
• $d$ = decryption exponent
• $N$ = modulus which was formed from the two primes $p$ and $q$
• $\varphi(N)$ = Euler Totient function

Lastly, you might want to read the Wiki RSA.