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

Posted on by

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

What is RSA?

RSA algorithm is an encryption algorithm created by Ron Rivest, Adi Shamir and Leonard Adleman (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.

 

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 (e, N), where N is the Modulus, and the Private Key d, is represented by (d, N), where 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 C as 3 and the Modulus N as 187 factored 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 C to Plaintext M in;

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 ‘d mod N‘, as if she is Decrypting it;

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 Message was actually from Alice, Bob will take the Signature S and raise it to the power of ‘e mod N‘, as if he is encrypting it;

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 H from the formula above DOES NOT match the hash value H of the Message then the 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