Full Domain Hash in Cryptography

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 1^k, 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) = x^emod N.
   
• The decryption function f −1: Z ∗ N → Z ∗ N is given by f^-1(y) = y^dmod 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 1^k, runs RSA(1^k ), 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:

SignFDH_N,d(M)

    y ←H(M)

   Return y^d mod N

VerifyFDH_N,e(M,x)

    y←x^e 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 q_hash(k) queries to the hash oracle, q_sig(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’-(q_hash+q_sig+1).O(k³) 

And

𝜺=(q_hash+q_sig).𝜺’.

• 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’-(q_hash+q_sig+1).O(k³) 

And

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

For a larger q_sig,

                  𝜺exp(1).q_sig.𝜺’                

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

• RSA Signature Scheme in Cryptography
• The Digital Signature Algorithm
• Hash function and data integrity in Cryptography

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