Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Digital Signature Schemes
3.
The RSA cryptosystem
4.
Security of RSA
5.
Full Domain Hash signature scheme 
5.1.
Security of Signature Schemes
5.2.
Security Analysis of Full-domain hash
6.
Frequently asked questions
6.1.
What does it mean by asymmetric key cryptography?
6.2.
What is the need for a Digital Signature?
6.3.
What is Man in the Middle Attack?
6.4.
What is MD5?
6.5.
How are keys in RSA Digital Signature Scheme and RSA different?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

Full Domain Hash in Cryptography

Author Sajid Khan
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

As you move forward in Cryptography subject, you often observe the primary goal of cryptography is to secure the conversation between a sender and receiver. In this blog as well, we are going to discuss an amazing concept through which we can secure the delivery of the message. 

Before we move forward to the topic, let us discuss an example. 

Suppose there are two persons A and B. A has committed that he will give 3000 Rs to B on 3rd of December. 

Now, B has waited till 3rd of December but didn’t got his money. 

digital signature

Since B is worried about his money, he planned to visit A to ask for his money. 

But all of a sudden A has denied to give the money and said he never told to give the money. 

digital signature

Now B has started arguing with A about the conversation they had with each other. 

digital signature

Since there is no proof that A has sent the message to B, as there can be a possibility of account hacking. Now, B has no proof to prove A wrong and take the money. 

Here comes the role of Signature. Likewise we sign the cheque in bank to authenticate ourselves, same as we can do it while sending the message. In the era of Digital world, there is a concept known as Digital Signature is highly being used to authenticate the right person. 

Full-domain hash in Cryptography (FDH) gives one of the most intuitive and appealing approach for creating digital signatures; it is a secure realization of the original ideas of Diffie and Hellman. 

Full Domain Hash in Cryptography

In this section, we will discuss how we can adapt Full Domain Hash signature scheme for digital signatures. To give you a brief overview of the topic: Take the message you would like to sign, but before calling the RSA function, apply special Hash Function. 

Let us start by understanding what are Digital Signature Schemes: 

Digital Signature Schemes

A digital signature is a string of bits that depends on a secret known only to the signer and the content of the signed message. Signatures must be verifiable: Anyone can verify the validity of the signature.

A Signature Scheme consists of the following parts.

  • Gen: The key generation algorithm, a probabilistic algorithm which, if given 1kwill give a pair of matching Public key and Secret keys (pK,sK). 
     
  • Sign: The signing algorithm. It takes the message M to be signed and the secret key sK and returns a signature x = Signsk(M)
     
  • Verify The verification algorithm. It takes a message M, a signature x’, and the Public key(pK). The verifypk(M,x’) will return 1 if the signature x’ is accepted and 0 otherwise.
     

Signature schemes mostly use hash functions. In the following schemes, the hash function is considered a random oracle. The outputs given by the hash function are uniformly distributed points in the range of h.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

The RSA cryptosystem

RSA is an asymmetric cryptography algorithm. It works with the combination of two different keys: A public key that is known to everyone and a private key, that is kept private.

  • If we have an input of 1k, the RSA generator will select 2 distinct k/2-bit primes p and q (randomly), compute N=p*q, randomly picks an encryption exponent e ∈ Z ∗ φ(N) (φ(N) is the Euler totient function), and computes the decryption exponent d given by d=e-1mod φ(N) The generator returns N,e,d. N,e forms the Public key and d is the private key. 
     
  • The encryption function f: Z ∗ N → Z ∗ N is given by f(x) = xemod N.
     
  • The decryption function f −1: Z ∗ N → Z ∗ N is given by f-1(y) = ydmod N.

Security of RSA

  • An inverting algorithm F-1 is said to (t,𝜺)-break RSA if its success probability is at least 𝜺(k) for all k∈N after at most t(k) processing time.
     
  • RSA is said to be (t,𝜺 ) secure if there is no inverter which (t, 𝜺)-breaks RSA.  
     

For signing with RSA, we have to first hash the message, add some padding, and then exponentiate it with the decryption exponent. Let’s see how we accomplish it using RSA with Full domain hash.

Full Domain Hash signature scheme 

The Full Domain Hash signature scheme consists of GenFDH, SignFDH, and VerifyFDH and is defined as follows. The key generation algorithm, on input 1k, runs RSA(1k ), and N, e, d are obtained where we get public key pK=(N,e) and secret key sK=(N,d). The signing and verifying algorithm has oracle access to a hash function H: {0, 1}* → Z*N. Signature generation and verification are shown below:

SignFDHN,d(M)

    y ←H(M)

   Return ymod N

VerifyFDHN,e(M,x)

    y←xe mod N

    y’←H(M)

    If y=y’

   Return 1

   Else

  Return 0

Security of Signature Schemes

A valid forgery is a message/signature pair (M, x) such that Verifypk(M, x) = 1 but the signature of M was never requested by F.

To give a concrete security analysis of the signature schemes, let us consider an Ideal hash function. Resistance against an adaptive chosen message is considered. 

Let’s take a forger F which can obtain signatures on messages of its choice in order to get a valid forgery.

  1. A forger F is said to (t, qsig, qhash,𝜺 )-break the signature scheme if after at most qhash(k) queries to the hash oracle, qsig(k) signatures queries and t(k) processing time, it outputs a valid forgery with probability at least 𝜺(k) for all k ∈ N.
     
  2. A signature scheme is (t, qsig, qhash,𝜺 )-secure if there is no forger who (t, qsig, qhash, 𝜺)-breaks the scheme.

Security Analysis of Full-domain hash

Let’s suppose we are given an RSA which is (t’,𝜺’)-secure.

Then an FDH signature scheme is said to be (t,𝜺) secure such that.

t=t’-(qhash+qsig+1).O(k3

And

𝜺=(qhash+qsig).𝜺’.

  • The disadvantage of the above result is that 𝜺’ could be much smaller than 𝜺. To achieve an acceptable level of security, we must use a larger modulus, which will affect the efficiency of the scheme. 
     
  • Bellare and Rogaway designed a new scheme, the Probabilistic Signature Scheme (PSS). Using this, we can get a better security bound as compared to the above security bound.
     
  • Suppose RSA is (t’, 𝜺’ )-secure. Then the Full Domain Hash signature scheme is (t, 𝜺)-secure where,

     t=t’-(qhash+qsig+1).O(k3

And

𝜺=1(1- 1qsig+1)qsig𝜺’

For a larger qsig,

                  𝜺exp(1).qsig.𝜺’                

Frequently asked questions

What does it mean by asymmetric key cryptography?

Asymmetric encryption is a form of encryption, also called public key cryptography. In this form of cryptography, there are two different keys, one key, a public which is used for encryption, and only the other corresponding key (Private key) is used for decryption. No other key can decrypt the message, not even the original key used to encrypt it.

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 looked into Full Domain Hash and how it is used with RSA for creating secure digital signatures. We also discussed the security of RSA and the security of Digital Signature Schemes, more specifically, the security of Full Domain hash.

Recommended Reading

 

Also, check out some of the Guided PathsContests, and Interview Experiences to gain an edge only on Coding Ninjas Studio.

Previous article
Security of the ElGamal Signature Scheme
Next article
The Schnorr Signature Scheme
Live masterclass