Public Key Ecryption

For completeness we discuss the public key encryption in this lesson but you may skip this lesson as it doesn’t directly relate to Kerberos. However, bear in mind that Kerberos uses private/symmetric key encryption which is opposite of public/asymmetric key encryption in its theory and implementation.

Cryptographic algorithms can be classified as Symmetric and Asymmetric based on the number keys they use. The former use a secret key and the latter use a combination of secret and public keys.

Symmetric cryptographic algorithms use the same secret key to encrypt and decrypt. Asymmetric algorithms use two keys. The public key is used for encryption and the private or secret key is used to decrypt the message. Diffie and Hellman are acknowledged as the founders of asymmetric cryptography with the publication of their paper New Directions in Cryptography in 1976.

Asymmetric encryption overcomes two main problems of symmetric encryption.

1. The first is secure transmission of the key. Symmetric encryption uses the same key for encryption and decryption, so sharing the key secretly is of paramount importance. If the key is compromised then there is no point of encryption.

2. The second problem is key management. As the number of users increases, the number of keys increases rapidly as every pair needs a different key for private communication. Thus n users need $n * \frac{(n-1)}{2}$ keys.

Asymmetric encryption deals with both these problems. The public key can be shared with anyone but the messages encrypted using the public key can only be decrypted using the corresponding private key. The Math behind the keys is such that even though both keys are generated in pairs and are mathematically related, an outsider is unable to derive one key (private key) even if he knows the other (public key) or vice versa.

Consider there are four participants A, B, C and D. For all the participants to communicate amongst themselves securely, we need to issue 6 symmetric keys:

1. Key for A and B
2. Key for A and C
3. Key for A and D
4. Key for B and C
5. Key for B and D
6. Key for D and C

In case of public key encryption, we’ll generate a pair of public/private key per participant so that with four participants we’ll have a total of $2n$ keys in the system or 8 keys for four participants. If M participants want to communicate with a entity in a symmetric key system, M unique keys will be used for communication. In contrast, in an asymmetric key system, the M participants will use the same public key of the entity they all want to communicate with. This is how the number of keys is significantly reduced when using asymmetric encryption. Key management becomes a problem in large networks when symmetric encryption is used. However, it is not an issue with asymmetric encryption as every party only has one secret key and all other keys are known.

Some reputed implementations of asymmetric encryption algorithms include Rivest-Shamir-Adleman (RSA), Diffie-Hellman key exchange, ElGamal, Digital Signature Standard (DSS), Elliptic-curve, Cramer-Shoup and YAK key agreement protocol.

Below is a Java sample program that encrypts a message using a public key and then decrypts it using the corresponding private key. You can change the key size on line#16 or the algorithm on line#15 to see how the encrypted string changes.