Explanation of Asymmetric Cryptography

Before you start

Objectives: Learn what is asymmetric cryptography, how does it work, and about different implementations.

Prerequisites: you should know what is symmetric cryptography.

Key terms: key, cryptography, private, receiver, asymmetric, public, message, symmetric, encrypted, digital


Key Pairs

In asymmetric cryptography system both the sender and the receiver have their own key pair which consists of one public and one private key. Public key is available to anyone and is publicly distributed. The private key is kept secret, and it’s available only to the owner. The public and the private keys are mathematically related, but they can’t be derived from each other. Both keys are required to perform an operation. Data encrypted with the private key is encrypted with the public key, and data encrypted with the public key is encrypted with the private key. The public key can’t be used to decrypt messages that were encrypted with the public key, nor can we decrypt messages with the private key that were encrypted with the private key. Remember that we have to use the opposite key to decrypt messages.

The private key must be kept private at all times. If not, we break down the security of the whole system. If the private key is ever discovered, a new key pair must be generated. Asymmetric cryptography is very scalable. Everybody has their own key pair (keys are not shared). Unfortunately, asymmetric cryptography is not suited for bulk encryption because it is much slower then symmetric cryptography. Because of that it is usually used to encrypt small amounts of data.

How Does it Work

In asymmetric cryptography we have a sender and a receiver. Both the sender and the receiver will have a key set. They will have a key that is private and a key that is public.

 1 Private-public Keys

Different Keys

When the sender wants to send a message to the receiver, the sender will encrypt the message with the its private key, and then use the public key from the receiver and encrypt it again.

 2 Message Encrypted

Message Encrypted

The encrypted message is then transmitted to the receiver. The receiver will then use its private key to decrypt the outside encryption on the message (which was encrypted with its private key), and then uses the public key from the sender to decrypt the message which was encrypted with the private key from the sender.

 3 Message Decrypted

Message Decrypted

The receiver then gets the original message. This is basically how asymmetric cryptography or public/private key system works.

Usage of Asymmetric Cryptography

We can use asymmetric cryptography in different ways. For example, if we only use the senders private key on the message, we basically get a digital signature functionality. In order to use a digital signature feature, the sender and the receiver have to use a special variation of the asymmetric cryptography system. The sender takes the message and encrypts it with its private key, and sends the encrypted message to the receiver. The receiver then uses the senders public key and decrypts the message.

 4 Digital Signature

Digital Signature

By using this implementation of asymmetric cryptography, the receiver gets the original document and is able to prove that it came from the sender because the only key that is able to unlock the message is the public key from the sender. This proves the identity of the person who sent the message.

Another implementation of asymmetric cryptography is when we only use the receivers public key on the message. This way  we get a digital envelope functionality. The sender will take the message and encrypt it with the public key from the receiver. The receiver will then use his private key to decrypt the message.

 5 Digital Envelope

Digital Envelope

The private key from the receiver is the only key which can decrypt the public key from the receiver. This fact ensures that the only person which will be able to read the message is the receiver. This way we get a digital envelope feature from the asymmetric cryptography system. We often use this feature to authenticate the receiver.

Confusing Private Key Terminology

Be sure that you understand how to differentiate the symmetric cryptography from the asymmetric cryptography when we talk about private keys. For example, the term private key always refers to the private key in the asymmetric key pair, from the asymmetric cryptography system. The term private key cryptography always refers to the symmetric cryptography. Because of that the asymmetric cryptography is often refered to as the public key cryptography.

One-way Function

The public key cryptography is based on a special mathematical function called a One-way Function. This mathematical function enables us to compute it in one way very easily, but it makes it nearly impossible to compute it in the opposite direction. Asymmetric cryptography takes this function and also adds a trap-door mechanism. The private key actually serves as the trap-door, with the special capability to unlock and reverse the one way function. This enables us to encrypt the message, and also have a secret key to unlock it.

The problem of Symmetric Key Exchange

As you will notice, asymmetric cryptography is often used to exchange symmetric keys, rather than the data itself. For example, let’s say that we have a sender and the receiver which want to communicate. To keep the communication between them private but also fast, the best solution is to use symmetric cryptography. However, exchanging symmetric keys is often difficult because there is usually an untrusted network between the sender and the receiver. Despite that, they have to somehow exchange the same key between them, and keep it secret at all times. Because of that, keys are exchanges by using the asymmetric cryptography. The sender takes the symmetric key and encrypts it with its private key, and then encrypts all that with the receivers public key. The symmetric key will then be transmitted to the receiver where the receiver will first use its private key, and then the senders public key to decrypt the original message, which is the shared symmetric key. At this pont, the sender and the receiver are able to encrypt data by using the shared symmetric key, and transfer files very efficiently.

There are several implementations of asymmetric cryptography that we have to be aware of. The first one is the RSA (Rivest, Shamir, Adleman).

RSA

The RSA is based on the difficulty of factoring a prime number which is a product of two very large prime numbers (200 digits). Multiplying two large numbers that are prime together is very easy, but trying to factor them back to the original prime numbers is very difficult. RSA can be used for encryption, for key exchange, and for digital signature.

Diffie-Hellman Key Exchange

Another example of key exchange solution is the Diffie-Hellman Key Exchange. This method is also used to exchange symmetric keys over insecure medium.

Al Gamal

This method is actually an extension of Diffie-Hellman method and it is used to in encryption and to perform digital signatures. Both Al Gamal and Diffie-Hellman are not used often anymore because they have been replaced by newer technologies, but technologies used in them are still used in many different encryption methods today.

Elliptic Curve

Elliptic curve is not actually a cryptography system itself. It is a mathematical function which can be used in existing systems to reduce the key size. Many public key algorithms (asymmetric cryptography systems), can be implemented in conjunction to Elliptic curve which results in shorter, but stronger keys. This enables us to use less memory and less CPU to work with public-key cryptography. Elliptic applied algorithms is often used on wireless devices and smart cards.