GATE IT 2007 | Question: 15

Question

Consider the following two statements:

1. A hash function (these are often used for computing digital signatures) is an injective function.
2. A. encryption technique such as DES performs a permutation on the elements of its input alphabet.

Which one of the following options is valid for the above two statements?

• A. Both are false
• B. Statement (i) is true and the other is false
• C. Statement (ii) is true and the other is false
• D. Both are true

Comments

Not in current syllabus of GATE CS

Answer 1

Answer is C.

i. Hash function is not one one or injective. It is many to one.

ii. True. Uses P-Box permutation.

Comments

any source for DES?

---

@Shubhm DES ,AES are in syllabus now??

Answer 2

Option (i) Here some asymmetrical algorithms where we apply Hashing (Hashing is a method used to verify data integrity).

1. RSA - named after Rivest, Shamir, and Adleman (investor)

2. Diffie-Hellman (DH)

3. ElGamal - based on the DH echange 

4.Digital Signature Algorithm (DSA)- created by NSA 

5. Eliptic Curve Cryptography (ECC)

Here some most popular Hashing types

1. MD5 (Message Digiest 5)

2. SHA 1

3. SHA 2

4. SHA 3

So we can correctly say it is not injective (one to one).

Option (ii) DES (Digital Encryption Standard) is part of symmetric key algorithm where we use same key to encrypt the data and decrypt the data. so calculating we perform permutation.

Statement (ii) is true and the other is false

 

Comments

thanks for better explanation

---

what does injective(one to one) means here? VIKAS TIWARI

---

@VIKAS TIWARI @Rajesh Panwar @PRANAV M

This explanation is wrong. Injective here means that getting the same Message digest for two or more different "Messages". 

Answer 3

COMMENT BELOW IF YOU HAVE ANY DOUBT

Answer 4

ans d)

Comments

The hash function (these are often used for computing digital signatures) such as MD5 and SHA are not injective, a perfect hash function will be injective so i wonder what the answer should be.

---

Answer is (C)

During hash generation more than one message may generate the same HASH value( why should we talk about only about perfect hashing ;That is more than some specific thing !!).So hash function is Many-to-One

---

makes sense.