RSA encryption/decryption scheme

Question

I've been having trouble with RSA encryption and decryption schemes (and mods as well) so I would appreciate some help on this question: Find an $e$ and $d$ pair with $e < 6$ for the integer $n = 91$ so that $n,e,d$ are the ingredients of an RSA encryption/decryption scheme. Use it to encrypt the number $9$. Then decrypt the result back to $9$. In the encryption and decryption it will be helpful to use the fact that $81\equiv -10 \pmod {91}$.

Thank you ever so much to whomever lends a hand. I really, really appreciate it.

Answer 1

We are given $N$ and that will give us the prime factors $p$ and $q$ as:

$$N = 91 = p \times q = 7 \times 13$$

We need the Euler Totient Function of the modulus, hence we get:

$$\varphi(N) = \varphi(91) = (p-1)(q-1) = 6 \times 12 = 72$$

Now, we choose an encryption exponent $1 \lt e \lt \varphi(N) = 72$. We were told to pick an an $e \lt 6$, so lets choose $e = 5$ and see if that works, where it should be coprime with $\varphi(N)$.

$$(5, 72) = 1 \rightarrow e = 5$$

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)} = 5^{-1} \pmod {72} = 29$$

Encryption:

$$\displaystyle c = m^{\large e} \pmod N \rightarrow 9^5 \pmod {91} = 81$$

Decryption:

$$\displaystyle m = c^{\large d} \pmod N \rightarrow 81^{29} \pmod {91} = 9$$

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.