At practically the same time the DHM methods was found, the RSA public key cryptography was presented. Anyone who wants the capability of receiving encrypted data simply makes known their public key, which anyone else can then use to encrypt messages to them. The beauty of the system is that the receiver possesses another private key, necessary for decrypting but never released to anyone else.
|
RSA: A Public Key Cryptography Scheme Alice (the receiver) completes the following steps. Step 1 Choose two prime numbers, p and q, which they Alice keeps secret. Step 2 Compute the modulus n (which is the product \(p \cdot q\). Step 3 Compute \(l = (p-1)(q-1)\). Step 4 Choose the encryption exponent e, which can be any integer between 1 and l that is relatively prime to l, that is, has no common factors with l. Step 5 Find Alice's decryption exponent d, a number satisfying \[e \cdot d \equiv 1 \pmod{l}\] Alice keeps d secret. Step 6 Provide Bob with Alice's public key, which consists of the modulus n and the encryption exponent e. Now Bob (the sender) completes the following steps. (Recall that the purpose of all this is for Bob to be able to send Alice secure messages.) Step 7 Convert the message to be send to Alice into a number M (sometimes called the plaintext). Step 8 Encrypt M, that is, use of Alice's public key (n and e) to generate the encrypted message C (sometimes called the ciphertext) according to the formula \[ C = M^e \pmod{n}\] Step 9 Transmit C to Alice. When Alice receives C, she completes the final step: Step 10 Decrypt C, that is, use Alice's private key, consisting of n (also part of her public key) and d, to reproduce the original plaintext message M according to the formula \[M=C^d \pmod{n}\] |
Creating a Public Encryption Key
Step 1 Let's choose the prime values \(p = 11\) and \(q = 13\).
Step 2 \(n=p\cdot q=11\cdot 13 =143\)
Step 3 \(l =(p-1)(q-1)=10\cdot 12 =120\)
Step 4 There are many choices for a prime number between 1 and 120. Let's choose \(e=17\)
The public key is \(n=143, e=17\). (Prime factors p and q must be kept secret).
Finding a Private Decryption Key
Step 5 The decryption exponent d must satisfy
\(e\cdot d =1 \pmod{l}\) or \(17d \equiv 1 \pmod{120}\).
One way to find a solution to this equation is to check the powers of 17 to find one that satisfies the equation.
\(17^1 \equiv 17 \pmod{120} , \quad 17^2 \equiv 49 \pmod{120}, \quad 17^3 \equiv 113 \pmod{120}, \quad 17^4 \equiv 1\pmod{120}\)
We found \(17^4 \equiv 1 \pmod{120}\), we take \(d=17^3 =4913\) and
\[e\cdot d =17\cdot 17^3 =1 \pmod{120}\]
Therefore, Alice's private key is \(n = 143,\, d = 4913\).
Encrypting a Message for Transmission
Let's use the RSA to encrypt the message "HI" for Bob to send to Alice. Use Alice's public key: \(n = 143,\, e= 17\).
Step 7 A simple way to convert "HI" is to note that H and I are the 8th and 9th letters of the alphabet. So the plaintext message is
\[\underbrace{8}_{\text{H}}\underbrace{9}_{\text{I}}\]
So the plaintext \(M = 89\)
Step 8 Now compute the ciphertext C: \(C = m^e \pmod{n} = 89^{17} \pmod{143} \)
Since you need the exact quotient to find the remainder, this may be too large for your calculator to handle. However, we can break down the exponents.
\[89^{17} =89^1\cdot 89^{16} = 89 \cdot \left(89^4\right)^4 \]
Now we can calculate the residues.
\begin{align} 89 \pmod{143} &\equiv 89 \\ 89^4 \pmod{143} &\equiv 133 \\ 133^4 \pmod{143} &\equiv 133 \end{align}
So, \( 89 \cdot \left(89^4\right)^4 \equiv 89 \cdot 133 \equiv 11,837 \equiv 111 \pmod{143} \).
The plaintext \(M=89\) (for the message "HI") has been converted to ciphertext \(C=111\).
Decrypting a Received Message
To decrypt the ciphertext \(C=111\), use Alice's private key \(d=4913, n=143\)
Step 10 The decryption formula
\begin{align} M &= C^d \pmod{n} \\ &= 111^{4913} \pmod{143} \\ &= 111^{17\cdot17\cdot17} \pmod{143} \\ &= \{\left[111^{17}\right]^{17}\}^{17} \pmod{143} \\&=\left[89^{17}\right]^{17} \pmod{143} \\ &=\left(111\right)^{17} \pmod{143} \\ &=89 \pmod{143} \end{align}
We have correctly decrypted \(C=111\) to obtain \(M=89=\) "HI".
