Demystifying Public Key Cryptography

Public key cryptography revolutionized the world of encryption and information passing. Before this, if you wanted to send information securely to your friend in another town, you would have had to agree on an encryption scheme (called a shared secret) before hand and hope no one eavesdrops. This was typically done by meeting in person and exchanging notes or memorizing.

Public key cryptography eliminates the need to have a shared secret by asserting that the encryption algorithm and part of the key can be made public. The security is hinged on the practical “impossibility” of deriving the private key from the public key. If you now want to send your friend a message, you simply use their public key and one of the well known algorithms - such as RSA - to encrypt your message. Since only your friend has the corresponding private key, no one else can retrieve the message.

So how is this accomplished? These algorithms are based on the presumed difficulty of solving some mathematical problem such as factoring the product of two large primes. Prime factoring is at the heart of RSA. Other algorithms such as Al Gamal and Elliptic curve are based on similarly difficult mathematical problems.

The applications of this scheme are numerous and far reaching. Whitfield Diffie and Martin Hellman came up with a key exchange algorithm (originally conceptualized by Ralph Merkle) called DH after their initials. DH uses public key cryptography to securely exchange a secret key. This became the basis for SSL/TLS in combination with certificate based authentication. The digital certificate itself uses public key crypto techniques to prove the authenticity of the contents. It contains the identity information of the holder and validity period among other things. This information is hashed into a message digest which is then signed by a trusted third party known as a certificate authority. Digital signing is essentially encrypting data using your own private key. The idea being that it can only be decrypted using your public key and hence proves that only you could have encrypted it.

Pretty good privacy or PGP for short uses a web of trust instead of a centralized certificate authority but the other concepts remain the same.
Other features and functionalities public key cryptography enables are non-repudiation, S/MIME, DKIM and DMARC.