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.

Alice (the receiver) completes the following steps.
p and q, which they Alice keeps secret.
modulus n (which is the product \(p \cdot q\).
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.
decryption exponent d, a number satisfying \[e \cdot d \equiv 1 \pmod{l}\]Alice keeps
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.)
M (sometimes called the plaintext).
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}\]
C to Alice.When Alice receives
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

\(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

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**".

Designed by Matthew Cheung. This work is licensed under a Creative Commons Attribution 4.0 International License.

- Last Updated: Oct 21, 2021 11:53 AM
- URL: https://libraryguides.centennialcollege.ca/c.php?g=717548
- Print Page

chat loading...