Just Cryptography

Learn Cryptography and Information Security

Home » Blog » What are Asymmetric algorithms?

What are Asymmetric algorithms?

Asymmetric algorithms are very important in cryptography and especially in digital signatures.

The first asymmetric cryptography algorithms were introduced by Whitfield Diffie and Martin Hellman in the 1970s. The main difference between classical and symmetric cryptography is that instead of using a key to encrypt and decrypt, you should now use a pair of keys.

The security of this mechanism is based on mathematical problems that are difficult to solve.

Although asymmetric algorithms can be difficult to understand due to their mathematical basis, the principle is very simple: What is encrypted with a key is decrypted with the other (it’s corresponding) key. The same key cannot be used to encrypt and decrypt the message.

Table of Contents

Key-exchange problem

One of the main problems symmetric cryptography has when encrypting a message is how the key that was used to encrypt is delivered to the recipient of the message.

The key must be sent through a secure communication channel. But if there is such a channel, why not send the message using it?

Another option is to previously agreed between both parties one a key. That option is often not viable. Information is currently processed between people who are very distant from each other and who do not have the possibility of meeting in person.

Imagine that you must visit every contact with whom you want to communicate securely using Facebook or WhatsApp.

That problem is known as the key exchange problem.

How asymmetric cryptography works?

In asymmetric cryptography, each user or entity has a pair of keys, known as public and private keys. These keys are generated at the same time by mathematical functions and are closely related. However, if you have the public key, you cannot guess or infer the private key.

What is encrypted with a certain public key is decrypted only with its corresponding private key. This characteristic of the keys allows different uses depending on what you want to ensure in the message. These concepts are explained in the article General concepts to study Cryptography.

Encryption and decryption with asymmetric algorithms

Each user has a key pair. One is secret and only known to the owner. The other is public and is known to everyone who wants to communicate with the user. Each algorithm has its way of implementing this principle but in general, it works as explained below:

  • User A has a secret key As and a public key Ap.
  • User B has a secret key Bs and a public key Bp.
  • User A wants to send a message M to user B.
  • User A knows user B’s public key (Bp). He/she encrypts the message M with the key Bp obtaining the encrypted message Mc.
  • User A sends Mc to user B.
  • User B decrypts the message Mc with his/her private key (Bs) and obtains the plain text message M.

As you can see, any user knowing the public key Bp can encrypt information and send it to B. Only B can decrypt it because he/she is the only one who knows his/her secret key Bs.

The same happens if B wants to send information to A, he must encrypt it with user A’s public key (Ap).

In the previous example, we can see how confidentiality is achieved.

Digital signature using asymmetric algorithms

The problem we want to solve now is, user B wants to be sure that the message was sent by user A.

Following the same principle as the example in the previous section, now A wants to send a signed message M to B. See the steps below:

  • User A encrypts M with his/her private key As obtaining Mc.
  • The message Mc is sent from user A to user B.
  • User B uses the public key Ap to decrypt the message Mc obtaining M.

As you can see, anyone who knows Ap can read the message, but only A could have encrypted it with As. That way B is sure that the message is from A.

In the previous example, we can see how authenticity is achieved.

Combining the example of this section with the one in the previous section, it is possible that only user B can decrypt the message received. Also, user B can be sure that the message was sent by user A.

Use and limitation of asymmetric algorithms

The main drawback of asymmetric algorithms is that they are computationally less efficient than symmetric ones. This means that they are very slow to encrypt large volumes of data.

Usually, this type of algorithm is used in combination with symmetric algorithms and hashing functions to get the most out of them by encrypting small volumes of data. You can find more information about cryptographic hash functions in this post.

Generally, what is digitally signed is the hash of a message since it is smaller, and the encryption takes less time.

In the following example we will show how to combine algorithm families to achieve different objectives:

  • encrypt data with symmetric cryptography
  • perform the exchange of keys and the signature of the message with asymmetric cryptography
  • check the integrity of the message with a hash function.

Example:

  • User A wants to encrypt a message M and send it to B.
  • User A generates a private key P. Then, A encrypts M with the key P using a symmetric algorithm obtaining Mp.
  • The private key P is encrypted (by user A) with the public key Bp using an asymmetric algorithm obtaining PBp.
  • A calculates the hash H1 to M and encrypts the H1 with its secret key As using an asymmetric algorithm obtaining H1As. Then A sends Mp, PBp and H1As to B.
  • B decrypts PBp with his private key Bs, using an asymmetric algorithm obtaining P.
  • User B decrypts Mp using P (and using a symmetric algorithm) and obtains M. Then, B decrypts H1As with the public key Ap obtaining H1.
  • As a next step, user B calculates the Hash to M obtaining H2.
  • Finally, user B compare H1 and H2, if they are the same, it means that the message was not modified and was sent by A.

Asymmetric algorithm security

The security in asymmetric algorithms as mentioned above is based on mathematical functions easy to execute in one way, but difficult to execute in the inverse way.

For example, it is very easy to multiply or add 2 numbers and obtain a result, but it is difficult from the result to identify which numbers were added or multiplied. The problem becomes more complex if the result is a large number that allows many combinations.

The following example shows the operation of an encryption algorithm:

  • The message is M
  • The secret key is N
  • The encryption algorithm consists of raising the binary number that makes up the message to the binary number that makes up the key, obtaining the ciphertext C.
  • C is sent as an encrypted message.

The brute force cryptanalysis for this algorithm knowing C consists of testing numbers N and M until you can discover which ones are correct. The same happens if, through the inverse operation to exponentiation, which is the logarithm, one begins to try numbers to discover N and decipher the messages.

Remember that in asymmetric algorithms the same key is not used for encryption and decryption, in this example, the encryption key would be obtained through exponentiation and the decryption key through logarithm.

With current computational power, if we use large enough prime numbers, trying random numbers to find the expected result in either of the 2 operations would take thousands of years.

Large prime numbers

One way to make the calculation easier is to try breaking the numbers down into smaller numbers and trying to find the result in parts.

For this reason, operations in asymmetric cryptography use prime numbers so that they cannot be factored in, and the calculations have to be carried out with the complete numbers.

The word “large” refers to numbers with a large number of digits compared to the existing calculation capacity. Keys of 2048 or 4096 bits in length are currently used.

Asymmetric algorithms requirements

Asymmetric algorithms must meet the following requirements:

  • Efficient: Public and private keys must be generated in polynomial time.
  • One key must be kept secret.
  • Secure: With the knowledge of the public key, it is computationally infeasible to obtain the secret key.
  • Condition: If D is the decryption algorithm, E is the encryption algorithm, ks the secret key, kp the public key and Tcl the plain text, it is true that Dks(Ekp(Tcl))=Tcl

Summary

• Asymmetric algorithms are based on the computational security that offers encryption made in polynomial time complexity and that require cryptanalysis with exponential time complexity.

• Asymmetric algorithms are efficient at encrypting small volumes of data, which is why they are generally used for key exchange and digital signature.

Related posts

,

Recent posts