1
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Needs another TU! +1 $\endgroup$ – Namaste Nov 30 '13 at 1:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.