Asymmetric Cryptography

What is cryptography?

Cryptography is the set of mathematical methods that work to ensure authentication, confidentiality and integrity of data.

What is encryption?

Encryption is an important concept in cryptography. Encryption is the method that provides end-to-end protection of data transmitted between networks and converts a readable message into an unreadable form where only the person with the required key can make the message meaningful again.

Encryption algorithms are divided into two categories as symmetric and asymmetric.

Symmetric Encryption

In symmetric encryption, both parties exchanging messages use the same private key. The sender encrypts the message with the private key and the receiving party decrypts it using the same private key.

AES, RC4, DES, RC5 and RC6 are examples of symmetric encryption.

The key distribution problem in symmetric encryption has brought up asymmetric encryption. In this article I will talk about asymmetric encryption.

Asymmetric Encryption

Whitfield Diffie and Martin Hellman, researchers at the Stanford University, first proposed asymmetric encryption to solve the key deployment problem in their 1977 article.

Asymmetric encryption, also known as public key encryption, has two keys: the public key and the private key. Public key is used for encryption and authentication and is open to access. The private key is personal and it’s used for decryption and digital signing.

A message encrypted with the public key of X can only be decrypted with the X’s private key.

Public keys are put into digital certificates with the use of Public Key Infrastructure (PKI). This certificate is sent to the party to be contacted and the public key distribution is fulfilled.

Asymmetric encryption makes protocols such as SSL/TLS, SMTP, NTP, FTP etc. secure.

Diffie–Hellman key exchange method
Based on the difficulty of the discrete logarithm problem, the Diffie–Hellman key exchange method allows two parties that don’t have any prior knowledge about each other to create a common secret key over an unsafe channel. With this key, the traffic between the two parties is encrypted.

How does the Diffie–Hellman key exchange method work? Let’s explain with an example.

Alice and Bob initially agree on a large prime number “p” and an integer “g” that is not zero. The p and g values determined by Alice and Bob are public information.

Then Alice and Bob determine secret integers for themselves (x and y) and they do the following calculation:

Alice: g^x modp
Bob: g^y modp

They send these values to each other and make another calculation:

Alice: k = (g^y)^x = g^{xy} modp
Bob: k = (g^x)^y = g^{xy} modp

These identical values they obtained are the shared secret. They use this key to encrypt traffic between them.

The Diffie–Hellman Problem (DHP) is the problem of calculating the g^{ab} modp value from the known values of g^a modp and g^b modp. The security of Alice and Bob’s shared key depends on the difficulty of the following potential problems:

  • Discrete logarithm (DL) problem: It’s hard to find the a value from the given g^a modp.
  • Computational Diffie–Hellman (CDH) problem: With the given g^a and g^b values, it’s hard to compute the g^{ab} modp value unless a or b is known
  • Decisional Diffie–Hellman problem: Given g^a and g^b, it’s hard to tell the difference between g^{ab} modp and g^r modp (r is a random number)

It should be noted that Diffie–Hellman key exchange does not provide authentication by itself.

RSA Encryption Algorithm

The RSA algorithm based on the Euler Totient function is used for asymmetric encryption.

First we need to know the Euler Totient function (ϕ(n))

  • Where n≥1, ϕ(n) is the number of integers in the range [1,n] which are relatively prime with n.

For example, let n = 24. In the [1,24] range, integers that are relatively prime with 24 are {1, 5, 7, 11, 13, 17, 19, 23}. So, ϕ(24)=8

Key generation with RSA:

  • 1024 or 2048 bit p and q prime numbers are generated
  • n=pq and ϕ(n)=(p-1)(q-1) are computed
  • A small number e is selected that is relatively prime with ϕ(n)
  • Compute a unique d value where ed ≡ 1 mod ϕ(n)
  • Modular inverse d ≡ e-1 mod ϕ(n)
  • Public key = (e,n); Private key= (d,n)
  • encrypting message m: c = me mod n
  • decrypting message c: cd mod n = (me)d mod n = m

Author: Mahiye Büşra Gökce