Editing RSA cryptosystem (section)

===Example===
Here is an example of RSA encryption and decryption:{{efn|The parameters used here are artificially small, but one can also [[b:Cryptography/Generate a keypair using OpenSSL|OpenSSL can also be used to generate and examine a real keypair]].}}

# Choose two distinct prime numbers, such as
#: <math>p = 61</math> and <math>q = 53</math>.
# Compute {{math|1=''n'' = ''pq''}} giving
#: <math>n = 61\times 53 = 3233.</math>
# Compute the [[Carmichael's totient function]] of the product as {{math|1=''&lambda;''(''n'') = [[least common multiple|lcm]](''p'' − 1, ''q'' − 1)}} giving
#: <math>\lambda(3233) = \operatorname{lcm}(60, 52) = 780.</math>
# Choose any number {{math|1 &lt; ''e'' &lt; 780}} that is [[coprime]] to 780. Choosing a prime number for {{mvar|e}} leaves us only to check that {{mvar|e}} is not a divisor of 780.
#: Let <math>e = 17</math>.
# Compute {{mvar|d}}, the [[modular multiplicative inverse]] of {{math|''e'' (mod ''&lambda;''(''n''))}}, yielding<br /><math display="block">d = 413,</math> as <math>1 = (17 \times 413) \bmod 780.</math>

The '''public key''' is {{math|1=(''n'' = 3233, ''e'' = 17)}}. For a padded [[plaintext]] message {{mvar|m}}, the encryption function is
<math display="block">\begin{align}
 c(m) &= m^{e} \bmod n \\
      &= m^{17} \bmod 3233.
\end{align}</math>

The '''private key''' is {{math|1=(''n'' = 3233, ''d'' = 413)}}. For an encrypted [[ciphertext]] {{mvar|c}}, the decryption function is
<math display="block">\begin{align}
 m(c) &= c^{d} \bmod n \\
      &= c^{413} \bmod 3233.
\end{align}</math>

For instance, in order to encrypt {{math|1=''m'' = 65}}, one calculates
<math display="block">c = 65^{17} \bmod 3233 = 2790.</math>

To decrypt {{math|1=''c'' = 2790}}, one calculates
<math display="block">m = 2790^{413} \bmod 3233 = 65.</math>

Both of these calculations can be computed efficiently using the [[square-and-multiply algorithm]] for [[modular exponentiation]]. In real-life situations the primes selected would be much larger; in our example it would be trivial to factor {{math|1=''n'' = 3233}} (obtained from the freely available public key) back to the primes {{mvar|p}} and {{mvar|q}}. {{mvar|e}}, also from the public key, is then inverted to get {{mvar|d}}, thus acquiring the private key.

Practical implementations use the [[Chinese remainder theorem]] to speed up the calculation using modulus of factors (mod ''pq'' using mod ''p'' and mod ''q'').

The values {{mvar|d<sub>''p''</sub>}}, {{mvar|d<sub>''q''</sub>}} and {{mvar|q<sub>inv</sub>}}, which are part of the private key are computed as follows:
<math display="block">\begin{align}
           d_p &= d \bmod (p-1) = 413 \bmod (61 - 1) = 53, \\
           d_q &= d \bmod (q-1) = 413 \bmod (53 - 1) = 49, \\
  q_\text{inv} &= q^{-1} \bmod p = 53^{-1} \bmod 61 = 38 \\
               &\Rightarrow (q_\text{inv} \times q) \bmod p = 38 \times 53 \bmod 61 = 1.
\end{align}</math>

Here is how {{mvar|d<sub>''p''</sub>}}, {{mvar|d<sub>''q''</sub>}} and {{mvar|q<sub>inv</sub>}} are used for efficient decryption (encryption is efficient by choice of a suitable {{mvar|d}} and {{mvar|e}} pair):
<math display="block">\begin{align}
  m_1 &= c^{d_p} \bmod p = 2790^{53} \bmod 61 = 4, \\
  m_2 &= c^{d_q} \bmod q = 2790^{49} \bmod 53 = 12, \\
    h &= (q_\text{inv} \times (m_1 - m_2)) \bmod p = (38 \times -8) \bmod 61 = 1, \\
    m &= m_2 + h \times q = 12 + 1 \times 53 = 65.
\end{align}</math>