GATE IT 2008 | Question: 70

Question

The total number of keys required for a set of $n$ individuals to be able to communicate with each other using secret key and public key cryptosystems, respectively are:

• A. $n(n-1)$ and $2n$
• B. $2n$ and $\dfrac{n(n - 1)}{2}$
• C. $\dfrac{n(n - 1)}{2}$ and $2n$
• D. $\dfrac{n(n - 1)}{2}$ and $n$

Answer 1

For private key crypto for communication between each pair of individuals on secret key will be required, so if an individual wants to communicate with other $\text{n-1}$ individuals he should have $\text{n-1}$ secret keys,

So, the total number of secret keys for private encryption,

$=n\times (n-1)$ (If we include copies) or $n\times \dfrac{(n-1)}{2}$ (distinct keys).

For public key encryption each individual needs to have a public and private key,
so the total keys required in $2\times n$.

From the tone of the question the answer seems to be C) $\dfrac{n(n-1)}{2}$ and $2n$.

Comments

I was including copies in my answer since both sender and receiver will need to store it, but I guess question is asking for distinct keys in which case we should divide by 2.

---

If there are three hosts A,B and C.

Then A has Private=2 and Public=1

        B has Private=2 and Public=1

        C has Private=2 and Public=1

All the private keys are unique. So here the answer should be 6 for Private keys and 3 for public key? Please explain if I am missing anything.

---

The question is asking for number of keys in private and public crypto system, not the number of private and public keys. If you have used public crypto system in your example they why does A need 2 private keys?

Answer 2

in private key encryption a key used for encryption as well as decryption.  so no of keys required for n individuals is same as no of communication link between any two individuals.
no links = nC2
no of keys = n*(n-1)/2

in case of Public key each sender has its own public as well as private key so no of keys are 2n..

Comments

I understand in asymmetric key cryptography,  n private keys are required but why would we take n public keys if public key is known to everyone

---

Every individual has a public and private key bcz. if someone wants to communicate any msg. to that individual using Public Key Cryptography he needs to encrypt that msg. using the individual's public key. Then at the receiver side, only the receiver could decrypt the msg. using his private key. You can treat public and private keys as reciprocal of one another!

 

Hope it helps.

Answer 3

For a private key encryption

If there are 2 individuals then total number of distinct keys for communication will be 1 Similarly for 3 individuals we will need 2 distinct keys. Like ways for n users we will need n-1 keys So, total number of keys will be

1+2+3+…n-1 = (n (n-1)/2)

public key encryption scheme

Every individual will have two keys one public key and one private key.
Therefore, for n individuals to communicate we will have 2* n keys
Hence, the correct answer will be ((n(n – 1))/2) and 2n.

Answer 4

For secret or symmetric key cryptography, we need a key between each pair of hosts. So, $n_{C_{2}}$ keys,

For public key cryptography, each host would have two keys — public key and private key. So, $2n$

Option C