Written by Suraj Naranatt

Exchanging Keys

As you know, secure cryptography depends on the existence of entities called cryptographic keys. In case of a transaction between Alice and Bob using symmetric key cryptography, both Alice and Bob need to have a copy of the key. If no special precautions are taken, and if an eavesdropper, say Malroy gets hold of the common key, then she will be able to decrypt all messages between Alice and Bob via a man-in-the-middle attack. If you don’t know what a man-in-the-middle attack is, click here.

Physical Methods

Before the advent of the internet(yes, cryptography is quite old), cryptographic keys were written on physical media, such as paper, and exchanged using trusted couriers, diplomatic bags or other secure communication channels. Over the years, many different methods have been tried, including but not limited to shirt buttons, hollowed coins and even ashtrays A problem with this approach is that couriers may be intercepted or diplomatic relations may break down before communications can be established. Another problem is that secure communication between two parties who haven’t met before is impossible without exchanging the keys, which is also true for online communications. Moreover, physical keys can often be discovered quite easily.

Cryptographic Methods

In the online world, attackers may steal the keys while in transit, thus opening the channel to interception of messages. Keys often exist as strings of numbers which when fed to a special software, can decrypt or encrypt messages. To eliminate these problems, especially online, key exchange algorithms were devised. Symmetric Key Cryptography cannot be used to send an encryption key over an insecure channel. This is because both parties need to know the key to securely send the key. For this reason, public key cryptography is used, often to exchange the secret key.

RSA Key Exchange Algorithm

M=message, E=Key, C=Cipher, Box=Algorithm

There are many different algorithms which are being used for cryptographic key exchange, but the oldest one is RSA, which stands for Rivest-Shamir-Adleman, the names of the inventors. This algorithm is typically used along with symmetric key algorithms such as AES or triple DES to exchange the encryption key.

Let’s assume that Alice and Bob need to securely communicate with each other using messages encrypted using AES-256 encryption. In this scenario, one of them, say Bob generates a key to use with the AES algorithm. Both Alice and Bob have their own pairs of public and private keys, generated using the RSA algorithm. Afterwards, Bob uses Alice’s public key to encrypt the AES key and sends it to Alice. If Malroy is eavesdropping on the communication channel, she cannot find out the AES key without knowing Alice’s private key. On the other end, Alice decrypts the message which in this case is the encrypted key using her private key, and she can use it to send messages to Bob privately.

Internal Workings

The security of RSA entirely depends on the difficulty of factorizing large prime numbers. The algorithm works as follows:

  1. Two distinct large prime numbers, p and q are chosen
  2. A number n is computed such that n = p * q
  3. A function λ(n) is computed, where λ is called the Carmichael’s totient function
  4. An integer e is chosen such that 1 ≤ e ≤ λ(n) and gcd(e, λ(n)) = 1
  5. Determine an integer d such that d ≡ e−1(mod λ(n))

λ(n) is equal to the LCM(p-1) and (q-1). The public key is generated using the value of e and n, whereas the private key is generated using the value of d and n. Later, these keys play their respective roles in the above process. This algorithm is also used for securely sending encrypted messages.

Diffie-Hellman Key Exchange Algorithm

This algorithm was developed for the exclusive purpose of exchanging cryptographic keys. It allows two parties to securely exchange keys over an insecure channel. The security of this algorithm depends on the solution to the discrete logarithm problem. If Alice and Bob wish to exchange an encryption key for future communications, then they proceed as follows:

  1. Both of them agree on two large numbers n and g such that 1 < g < n
  2. One of them, say Alice chooses a random number x such that X = gx mod n and sends X to Bob
  3. Bob chooses a random number y such that Y = gy mod n and sends Y to Alice.
  4. Alice then computes a value k1 = (Y)x mod n
  5. Bob computes a value k2 = (X)y mod n

The two values, k1 and k2 are the same (k1=k2), and correspond to the secret key which is being shared.
This is because (Y)x mod n = (gy)x mod n. Similarly, (X)y mod n = (gx)y mod n. As can be seen, the exponents in both sides are the same.

Why does it work?

In the above example, assume that Malroy is an eavesdropper on the channel(medium of communication). The first three steps involve sending some data which can be easily obtained by Malroy. What prevents Malroy from finding out the secret key is that given X, Y, g and n, it is not possible to find the random values x and y such that X = gx mod n and Y = gy mod n. This is called as the discrete logarithm problem, which is considered to be an intractable problem in computer science.

Enfin

The two algorithms which I mentioned above are not the only ones which can be used for exchanging cryptographic keys. TLS(Transport Layer Security) is a set of protocols used by websites for securely serving web pages to clients(usually web-browsers). It uses a variant of RSA for exchanging cryptographic keys between the client and the server. Both Diffie-Hellman and the RSA key exchange were developed in the 1970s and the fact that most Hopefully, you now have an idea of the two most common key exchange algorithms in cryptography.

References + Further Reading

Leave a comment