RSA Signature Scheme in Cryptography

RSA Signature Scheme

RSA (Ron, Adi, and Leonard) is a very popular asymmetric key Cryptography algorithm. It is used mainly for encrypting messages, but RSA can also be used to sign messages digitally with a few changes. Key generation in RSA Signature Scheme is carried out in the same manner as in RSA encryption.

RSA Signature Key consists of the following:

• Public key: (n,e)
• Private key: (n,d)
   

Here n is the product of two very large prime numbers, p and q.

• phi(n) = (p-1) X (q - 1)
• e is a number in the range 1 < e < phi(n)
• d is the multiplicative inverse of e in tn modulo (n)
   

Let us take a look at how we can sign messages using RSA:

Let us assume that there is a sender, Andy, and a Reciever Bert. Andy wants to send a message M to Bert with a Digital Signatures (DS) attached.

Step 1:

Andy uses a Message-Digest Algorithm, let us say here, for example, MD5, to calculate the Digest for Message M.

MD = hash(message) where hash is the Message-Digest algorithm function.

(see Hash Functions and Data Integrity in Cryptography)

 

Step 2:

Andy now Encrypts the message with their private key. The generated text is called the Digital Signature.

Digital Signature(DS) = (MD^d) mod n

 

Step 3:

Andy now sends the original message along with the Digital Signature to Bert over the communication channel.

Message Sent = Original Message + Digital Signature(DS)

 

Step 4:

When Bert receives the message from Andy, it uses the same Message-Digest Algorithm as Andy to create a Message Digest (MD_Bert) from the Original Message they receive.

MD_Bert = hash(M1)

 

Step 5:

Now, Bert uses Andy’s Public key to decrypt the Digital Signature sent by Andy and get a Message Digest MD_Dec.

MD_Dec = (DS^e) mod n
 

Step 6:

Now, if we get MD_Dec == MD_Bert, it means that the message has not been tampered with and is original. This also means that the message received was actually from Andy and not someone else.

MD_Dec = (DS^e) mod n 

= ((MD^d)^e) mod n= (MD^(de)) mod n

Due to the combination property of RSA, we know that d and e are multiplicative inverses of each other, and thus,

(MD^(de)) mod n = (MD) mod n = MD

Thus , MD_ Dec = MD

The Message Digest created by Andy was encrypted using their private key to create the Digital Signature. The Digital Signature can be decrypted using Andy’s public key to get the original Message Digest.

This is possible due to the nature of asymmetric key cryptography. 

As Bert decrypts the Digital Signature using Andy’s public key, it checks the message's authenticity. This also establishes that it was Andy who sent the message.

If the message had been altered, the digest that Bert would create using the received message would be different from the one obtained after decrypting the Digital Signature. This would tell Bert that the message has been modified.

However, to successfully trick Bert into accepting the message, the attacker must encrypt the Message Digest using Andy’s Private Key. This isn’t easy to achieve as Andy’s Private Key is only known to Andy.

Therefore the RSA Signature Scheme in Cryptography is very secure and reliable.

Possible Attacks on RSA Digital Signature Scheme

Now that we have understood how RSA Digital Signature Scheme works, let us take a closer look at what are possible attacks the RSA Digital Signature System would be susceptible to.

A few of the major attacks that are carried out on the RSA Digital Signature Schemes are

1. Chosen Message Attack
2. Key-Only Attack
3. Known-Message Attack

Chosen Message Attack

In this type of attack, the attacker, for e.g., Eve, creates two different messages, M1, and M2. Eve then convinces Andy, who is a genuine user somehow, to sign these messages. Now Eve computes a new message M which is M1XM2, and then claims that Andy has signed it and sent it to Bert.

Key Only Attack

In the Key-Only attack, the attacker Eve has access to the Public key of the genuine user Andy. Eve also tries to get a Message and a Digital Signature. After this, Eve tries to create a different message MM which is such that the signature that Eve already has would work on the message MM. 

However, the computational costs for this are high, and therefore it is hard to perform a Key-Only Attack.

Known Message Attack

In the Known Message Attack, the attacker, Eve, tries to utilize a property of RSA, which states that the signature of a combination of two different messages is the combination of their signature. 

Let there be messages M1 and M2 that have signatures S1 and S2, respectively, which are known to eve. Then, if a new message M = (M1 X M2) MOD N, then the signature for that message (S = S1 X S2) MOD N. 

Thus, using this property, Eve can compute a message M which is M1 X M2 and a signature S which would be S1 X S2 and pretend to be Andy.

Implementation of RSA Digital Signature Scheme in Python

def _gcd(p,q):
    # Gives gcd of two numbers p and q
    if q == 0:
        return p
    else:
        r = p%q
        return _gcd(q,r)
   
def exteuclid(a, b):
    # Extended euclidian algorithm to find the multiplicative inverse    
    r_1 = a
    r_2 = b
    s_1 = int(1)
    s_2 = int(0)
    t_1 = int(0)
    t_2 = int(1)
    while r_2 > 0:
        temp = r_1//r_2
        r = r_1-temp * r_2
        r_1 = r_2
        r_2 = r
        s = s_1-temp * s_2
        s_1 = s_2
        s_2 = s
        t = t_1-temp * t_2
        t_1 = t_2
        t_2 = t
    if t_1 < 0:
        t_1 = t_1 % a

    return (r_1, t_1)

# p and q two large prime numbers
p = 823
q = 953
n = p * q
# phi_n
Pn = (p-1)*(q-1)

# Encryption key generation in range 1<e<Pn
possible_key = []

for i in range(2, Pn):
    gcd = _gcd(Pn, i)  
    if gcd == 1:
        possible_key.append(i)


# An encryption key is selected from the list of keys
e = int(-1)
# the multiplicative inverse of generated key is computed
for key in possible_key:
    r, d = exteuclid(Pn, key)
    if r == 1:
        d = int(d)
        e = int(key)
        print("Encryption Key is: ", e)
        print("Decryption Key is: ", d)
    if e != -1:
        break
if e==-1:
    print("No possible encryption key!!!")
    exit(0)
    
# Message which has to be sent
M = 14123

# Signature is created by Andy
S = (M**d) % n

# Andy sends the message M and Signature S to Bert
# Bert generates a Message M1 using the Signature S and Andy's Public Key (e,n)
M1 = (S**e) % n

# If M = M1 only then Bert accepts the message sent by Andy.

if M == M1:
    print("As M == M1, the Message is Accepted and the sender is verified as Andy!")
else:
    print("As M not equal to M1, the message is rejected!")

Output:

Frequently Asked Questions

What is RSA?

RSA is an asymmetric key encryption algorithm. It stands for the names of its creators, Ron, Adi, and Leonard.

What is the need for a Digital Signature?

A Digital Signature is needed to verify the authenticity of the message contents and the credibility of the sender.

What is Man in the Middle Attack?

In Man in the Middle Attack, the attacker, Eve, intercepts the communication between two parties and then pretends to be one of the parties involved.

What is MD5?

MD5 is a Message Digest Algorithm that produces a 128 bit hash for a message.

How are keys in RSA Digital Signature Scheme and RSA different?

The Key generation process in RSA and RSA Digital Signature Scheme is the same; however, the roles of public and private keys are interchanged.

Conclusion

In this article, we briefly discussed what a Digital Signature is. We dove deep into the workings of the RSA Signature Scheme and possible attacks that can be made of the RSA Signature Scheme. 

We also saw the implementation of the RSA Signature Scheme in Python.

Recommended Reading:

• Cryptanalysis of Substitution Cipher
• What is Cryptography?
• Public Key Cryptography
• Cryptanalysis of Hill Cipher
   

Also, check out some of the Guided Paths, Contests, Interview Preparation, and many more things on Coding Ninjas Studio.