3

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.

hjg hjg
  • 463
  • 3
  • 10
  • 1
    (1) Have you factored $247$ into prime factors? (2) Does your textbook explain how to find the decryption exponent when you know the encryption exponent and the prime factorization of the modulus? If not, look in another book. – Andreas Blass May 03 '13 at 03:54

1 Answers1

5

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.

Amzoti
  • 56,093