RSA DIGITAL SIGNATURE ALGORITHM WITH SOLVED EXAMPLES

RSA algorithm is an asymmetric cryptography algorithm. Asymmetric actually means that it works on two different keys i.e. Public Key and Private Key. As the name describes that the Public Key is given to everyone and the Private key is kept private.

An example of asymmetric cryptography :

A client (for example browser) sends its public key to the server and requests for some data. 

The server encrypts the data using the client’s public key and sends the encrypted data. 

Client receives this data and decrypts it. 

Since this is asymmetric, nobody else except the browser can decrypt the data even if a third party has the public key of browser.

Digital signatures are used to verify the authenticity of the message sent electronically. A digital signature algorithm uses a public key system. The intended transmitter signs his/her message with his/her private key and the intended receiver verifies it with the transmitter’s public key. A digital signature can provide message authentication, message integrity and non-repudiation services.  

RSA Digital Signature scheme:

• RSA idea is also used for signing and verifying a message it is called RSA digital signature scheme.

• Digital signature scheme changes the role of the private and public keys

• Private and public keys of only the sender are used not the receiver

• Sender uses her own private key to sign the document and the receiver uses the sender’s public key to verify it.

  

• The signing and verifying sets use the same function, but with different parameters. The verifier compares the message and the output of the function for congruence. If the result is two true the message is accepted.

Key generation in RSA

Key generation in RSA digital signature scheme is exactly the same as key generation in RSA cryptosystem.

Working of RSA digital signature scheme:

Sender A wants to send a message M to the receiver B along with the digital signature S calculated over the message M

Step1: The sender A uses the message digest algorithm to calculate the message digest MD1 over the original message M

Step 2: The sender A now encrypts the message digest with her private key. The output of this process is called the digital signature.

Step 3: Now the sender A sends the original message M along with digital signature DS to receiver B

Step 4: After the receiver B receives the original message M and the sender A’s digital signature, B uses the same message digest algorithm which was used by A and calculate its own message digest MD2 as shown below.

Step 5: The receiver B now uses the sender’s A’s public key to decrypt the digital signature. Note that A had used his private key to decrypt the message digest MD1 to form the digital signature. Therefore only A’s public key can be used to decrypt it. The output of this process is the original message digest which was calculated by A (MD1) in step 1.

Step 6: B now compare the following two message digests.

1. MD2, which it had calculated in step 4

2. MD1, which is retrieved from A’s digital signature in step 5

   If MD1 = MD2 the following facts are established:

a. B accepts the original message (M) as the correct, unaltered message from A

b. B is also assured that the message came from A and not from someone else attached, posing as A

Thus, the principle of digital signature is quite strong, secure and reliable.

Algorithm

RSA Key Generation: Choose two large prime numbers p and q 

• Calculate n=p*q 
• Select public key e such that it is not a factor of (p-1)*(q-1) 
• Select private key d such that the following equation is true (d*e)mod(p-1)(q-1)=1 or d is  d= (1+k * Φ(n))/e.

RSA Digital Signature Scheme: In RSA, d is private; e and n are public.  

• Alice creates her digital signature using S=M^d mod n where M is the message 
• Alice sends Message M and Signature S to Bob 
• Bob computes M1=S^e mod n 
• If M1=M then Bob accepts the data sent by Alice. 

Example - I:

I will give a simple example with RSA signing. I’m going to assume you understand RSA.

 First key gen:

P=7, q=13, n=pq=91, e=5, d=29.

Thus your public key is (e, n) and your private key is d.

Say we want to sign the message:

M= 35

We compute Signature:

S = M^d  Mod N

   = 35²⁹ Mod  91

   = ((35¹⁰ Mod  91) (35¹⁰ Mod  91) (35⁹ Mod  91)) Mod  91

   = (35 * 35 * 14) Mod 91

   = 42

The Message and signature get sent to the other party(m,s)=(35,42). Who takes the signature and raises it to the S^e Modulo N.

Compute Message:

M1 = S^e Mod N

       = 42⁵ Mod 91

       = 35

Then make sure that this value is equal to the message that was received, which it is, so the message is valid.

Example – II

P and Q are two prime numbers. P=7 and Q=17. Take public key E=5. If plain text value is 6. Then what will be cipher text value according to RSA algorithm? Again calculate plain text, signature and verify signature.

Solution:

 Here P=7, Q=17, E=5, M=6, n=?, Φ(n)=?, D=? and C=?

Modulus of N is:

N= P * Q

   = 7 * 17

 N= 119

Calculate Euler’s Totient Phi Value:

Φ(n)= (P-1) (Q-1)

         = (7-1) (17-1)

         = 6 * 16

 Φ(n)= 96

Calculate Private Key D Value:

Formula: 

D= (1+K. Φ(n))/E       Here K is 0,1,2,3,……

   = (1+4 * 96)/5        Here K=4

   = 385/5

 D= 77

Calculate Cipher text(Encryption):

C = M^E  Mod N

   = 6⁵ Mod 119

   = 7776 Mod 119

   = 41

According to RSA algorithm, the Cipher Text is 41.

Calculate Plain text(Decryption):

M = C^D Mod N

     = 41⁷⁷ Mod 119

     = ((41¹⁰ Mod 119) (41¹⁰ Mod 119) (41¹⁰ Mod 119) (41¹⁰ Mod 119)

         (41¹⁰ Mod 119) (41¹⁰ Mod 119) (41¹⁰ Mod 119) (41⁷ Mod 119)) 

         Mod 119

     = (36 * 36 * 36 * 36 * 36 * 36 * 36 * 97) Mod 119

     = 6

As per the RSA algorithm Plaintext from Ciphertext is: 6

Now Calculate Digital Signature:

S = Md  Mod N

   = 6⁷⁷ Mod  119

   = ((6¹⁰ Mod 119) (6¹⁰ Mod 119) (6¹⁰ Mod 119) (6¹⁰ Mod 119)

         (6¹⁰ Mod 119) (6¹⁰ Mod 119) (6¹⁰ Mod 119) (6⁷ Mod 119)) 

         Mod 119

     = (15 * 15 * 15 * 15 * 15 * 15 * 15 * 48) Mod 119

     = 27

As per the RSA Digital signature algorithm signature is: 27

Now Verify Digital Signature:

M1 = S^e Mod N

       = 27⁵ Mod 119

M1 = 6

As per RSA digital signature algorithm sent message and verified message is valid.

For practice: Click here for more examples