Public Key Cryptography offers ultimate security being based asymmetric keys; however it does have a specific purpose and is often not a replacement of symmetric crypto algorithms like AES. This article provides some basic information about the security mechanisms behind Public Key Cryptography with practical details on how it is used by some of the popular tools like PGP, SSL as well as Digital Signature.
Public keys and private keys
One of the main problems with symmetric key cryptography is using the same private key for both encryption and decryption. Two parties sending messages to each other must agree to use the same private key before they start transmitting secure information. Since the two parties may be in different parts of the world, private key must be passed through the network.
An interceptor, that manages to get hold of private key somehow, can easily decrypt the encrypted messages. Security of the Private key is the biggest problem with symmetric key cryptography. There need to be a secure way to communicate the private key between the sender and receiver – if there were a secure way to do this, then the cryptography would not have been necessary in the first place in order to create that secure channel.
Public Key Cryptography solves this problem. The primary feature of public-key cryptography is that it removes the need to use the same key for encryption and decryption. With public-key cryptography, keys come in pairs of matched “public” and “private” keys.
The public portion of the key pair can be distributed in a public manner without compromising the private portion, which must be kept secret by its owner.
An operation (for example, encryption) done with the public key can only be undone with the corresponding private key.
Putting public/private to work
Here's how the scheme will work. Let's say Bob and Mary want to communicate securely; they each create a key set and exchange public keys. Bob uses Mary's public key to encrypt a message that only she will be able to read when she decrypts it with her private key. If Marry wishes to issue a secure reply, she uses Bob's public key to encrypt the message so that only Bob can decrypt.
Figure 1 below shows the scheme where both Asymmetric and Symmetric Cryptography is used to transfer message security between two parties.
Figure 1: Using both Public Key Cryptography and Symmetric Cryptography to transfer data securely
Mary generates a Public-Private Key pair and provides her Public Key to Bob. There is no secret with Public key since it is Public so it can be distributed in a public manner without compromising the private portion, which must be kept secret by Mary. Bob generates a Random session key that is used to encrypt the message (using Symmetric Cryptography) Bob wants to send to Mary.
Bob also uses Mary’s Public key and encrypts the random session key (using Asymmetric Cryptography) and send it to Mary. Mary uses her Private key and decrypt the Encrypted session key and re-generate the same random session key that Bob possessed. This session key is now used to decrypt the actual encrypted message Bob has send earlier.
The combination of the two encryption methods combines the convenience of public key encryption with the speed of conventional encryption. Conventional encryption (or Symmetric Cryptography) is about 1, 000 times faster than public key encryption. Public key encryption in turn provides a solution to key distribution and data transmission issues.
Used together, performance and key distribution are improved without any sacrifice in security. This also solves the problem of having to send the session key over the network that anyone can intercept thus providing strong secure channel for communication.
Need for Digital Signature
If hacker manages to change the message before Bob sends the encrypted message to Mary, there is no way for Mary to know if the message originally came from Bob. Since Mary’s public key is known to anyone, anyone could send the encrypted message to Mary, claiming that he/she is Bob.
With his private key and the right software, Bob can put digital signatures on documents and other data. A digital signature is a “stamp” Bob places on the data which is unique to Bob, and is very difficult to forge. In addition, the signature assures that any changes made to the data that has been signed cannot go undetected.
Digital Signature works in the following way:
Step #1: Bob calculates Hash of his message. Hash functions are well-suited for ensuring data integrity because any change made to the contents of a message will result in the receiver calculating a different hash value than the one placed in the transmission by the sender. Since it is highly unlikely that two different messages will yield the same hash value, data integrity is ensured to a high degree of confidence. Note that there is no way to re-generate the message back from the Hash.
Step #2: Bob then encrypts the Hash with his Private key (Figure 2 below ). The result becomes the Digital Signature of Bob.
Step #3: Upon receipt of the digital signature, Mary recovers the hash value calculated by Bob by decrypting the digital signature with Bob’s public key.
Step #4: Mary can then apply the Hash function to Bob’s original message, which she has already decrypted.
If the resultant hash value is not the same as the value supplied by Bob, then Mary knows that the message has been altered; if the hash values are the same, Mary should believe that the message she received is identical to the one that Bob sent.
Figure 2: Public Key Cryptography with Digital Signature providing non-repudiation
This scheme also provides non-repudiation since it proves that Bob sent the message; if the hash value recovered by Mary using Bob’s public key proves that the message has not been altered, then only Bob could have created the digital signature. Mary also has proof that she is the intended receiver; if she can correctly decrypt the message, then she must have correctly decrypted the session key meaning that her is the correct private key.
Pretty Good Privacy (PGP) and Hybrid Cryptography
The above scheme also form the basis of more popular PGP encryption and decryption program widely used to encrypt and decrypt data communication like emails, that used both conventional (aka Symmetric) Cryptography as well as Public Key cryptography.
When a user encrypts plaintext with PGP, PGP first compresses the plaintext. Apart from data compression to save disk space, this also strengthens cryptographic security as it reduces the data patterns found in plain text. Based on random mouse movements and keystroke, PGP creates random session key, to encrypt plain text.
Once the data is encrypted, the session key is then encrypted to the recipient's public key. This public key-encrypted session key is transmitted along with the ciphertext to the recipient.
Decryption works in the reverse. The recipient's copy of PGP uses his or her private key to recover the temporary session key, which PGP then uses to decrypt the conventionally-encrypted ciphertext.
The combination of the two encryption methods combines the convenience of public key encryption with the speed of conventional encryption and works exactly the way explained in previous section.