Question

We previously saw in the class that the number of keys in a system with n users (where every possible pair of users desire to securely communicate between themselves) using symmetric cryptography is n(n − 1)/2. Is there a way to reduce the number of keys?
If yes, outline such a system.

Answer 1

Consider a group of n users. If symmetric key cryptography is used, we have to associate every pair of user to a different key leading to nC2 keys i.e. (n*(n-1))/2.

We can reduce the number of keys to 2*n. Consider each user has their own private key and a public key. Private key is to be kept secure while the public key is to be announced to everyone. Here public will be used to encrypt message while private key will be used to decrypt message. If A wants to send message to B, A will use public key of B to encrypt message and send data to B. Then B will use it's private key and decrypt message. If B wants to send message to A, A's public key will be used to encrypt message and A's private key will be used to decrypt the message.

In general, each user will have a public key for which other users will be able to encrypt message for that user and only that user will be able to decrypt. This is Asymmetric Key Cryptography. There are many asymmetric key cryptosystems like Knapsack cryptosystem, RSA cryptosystem, Elgamal cryptosystem etc..These cryptosystems are very difficult to crack provided we have a large size private key.

So for a group of n users, we have n public keys and n private keys. Total keys=2*n