# RSA Encryption, Decryption, Signing Messages, Signature Verification and Formula

**RSA Encryption, Decryption, Signing Messages, Signature Verification and Formula**

**What is RSA?**

** RSA algorithm** is an encryption algorithm created by Ron

**, Adi**

*Rivest***and Leonard**

*Shamir***(RSA). It is an asymmetric cryptographic algorithm, meaning that it uses two different keys for communication. RSA algorithm works by solving complex mathematical factors of large prime numbers.**

*Adleman*

**How does RSA work?**

Using RSA encryption, a *Message* is converted into a *Cypher/Cipher* by *Encrypting* it using a *Public Key* on the sender’s end. On the recipient’s end, the *Cypher/Cipher* can only be *Decrypted* using a *Private Key*. The Public Key is shared publicly but the Private Key is unknown and has to be calculated. This calculation constitutes the complexity of the RSA encryption.

*[Encryption/ Decryption Process]*

In the RSA encryption/decryption system, the following are involved;

```
- Message
- Public Key
- Cipher
- Private Key
- Prime Numbers
- Modulus
```

The *Public Key e*, is represented by

**, where**

*(e, N)***is the**

*N**, and the*

**Modulus***Private Key*, is represented by

**d****, where**

*(d, N)***N**is the

**.**

*Modulus*

*[Private/ Public Keys Formula]*

The Private and Public Keys can be calculated using the formula; 4

`ed = 1 mod Ø(N), given one of the Keys and the Modulus.`

**[Encryption Formula]**

To Encrypt a Message a standard formula is used;

`C = M^(e mod N), where C is the cipher. In encryption the public key (e, N) is used.`

*[Decryption Formula]*

To Decrypt a Message a standard formula is used;

`M = C^(d mod N), where C is the Cipher. In Decryption the Private Key (d, N) is used.`

**EXAMPLE**

In an example, Alice sends a message to Bob. Assuming that we have the *Public Key ( d, N)* as

*(107, 187)*, the

*Cipher*as

**C***3*and the

*Modulus*as

**N***187*f

*actored to the Prime Numbers 11 and 17*, we need to get the

*Plaintext*using the formula below;

```
M = C^(d mod N)
=>
M = 3^(d mod 187)
```

**[Computing the Private Key]**

Since we don’t know the *Private Key d*, we need to calculate it from the formula;

```
1 = ed mod Ø(N)
```

to get ** d** as;

```
1 = d * 107 mod 187
=>
d * 107 mod 187 = 1
```

After calculation, 7 satisfies the ** Extended Euclidean algorithm congruence** used in RSA, so we use it to satisfy our equation;

`7 * 107 mod 187 = 1`

**[Computing the Plaintext]**

With the *Private Key d = 7* now we can get decode the

*Cipher*

**to**

*C**Plaintext*

**in;**

*M*M = 3^(d mod 187 => M = 3^(7 mod 187) = 21 (Plaintext)

**[Signing Messages with RSA]**

To make sure that the Message was sent by Alice and no one else changed the content, Bob and Alice can use a *Signature*, by utilizing the same RSA encryption. RSA can be used to ** Sign Messages **to ensure

**.**

*Integrity*To sign the message that Alice sent to Bob, Alice should;

- generate its hash value H, and - produce a signature to attach it to the message

To produce the signature S, Alice should take the* hash value H* and

*raise it to the power of ‘*, as if she is Decrypting it;

**d mod N**‘`H^(d mod N) = S`

**NB://** The result of the above calculation is the Signature that should be attached to the Message and sent together.

**[Signature Verification with RSA]**

On the other end, Bob, the recipient of the message, will receive both the Message and the attached Signature. To ** Verify** if the

**was actually from Alice, Bob will take the**

*Message**Signature*and r

**S***aise it to the power of ‘*, as if he is encrypting it;

**e mod N**‘```
S^(e mod N) = H
=>
H = S^(e mod N)
```

The result of the above calculation should match the *hash value H* that Alice generated from the

*Message*, IF the

*Message*has not been

*Altered*. If the

*hash value*from the formula above DOES NOT match the

**H***hash value*of the

**H****then the**

*Message**Message*has been

*Altered*.

**NB://** The Signature method of Verification of Integrity of a Message in RSA encryption works due to the Rules of Exponentiation.

**RSA Encryption, Decryption, Signing Messages, Signature Verification and Formula**

**RSA | thetqweb**