2020-11-21-PKC.md

layout	post
title	Public Key Cryptography
author	Sarthak
categories	Cryptography Security Public Key Cryptography
tags	cryptography pkc public key cryptography diffie-hellman
image	https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/British_2nd_Infantry_Division.svg/768px-British_2nd_Infantry_Division.svg.png
usemathjax	true
excerpt	Public key cryptography is the most significant development in modern cryptography since it allows for secure communication even over insecure lines.
featured	true

This article continues on Public Key Cryptography from the article [Cryptographic alogrithms]({{ site.baseurl }}{% post_url 2020-11-13-crypto-algo %}) (and if you don’t know what "cryptography" is check out the article [Introduction to cryptography]({{ site.baseurl }}{% post_url 2020-10-27-intro-to-crypto %}) ).

First, let us have a quick recap to jog your memory (although I insist you go through the article [Cryptographic alogrithms]({{ site.baseurl }}{% post_url 2020-11-13-crypto-algo %}) if you haven't). Public key cryptography (PKC) has been deemed as the most significant development in modern cryptography since it allows for secure communication even over insecure lines. So you can safely communicate with people without meeting in person or making any prior agreements (which are required in SKC). The mathematical method depends on "trapdoor functions", which are easy to process, but are extremely difficult to revert, unless you have specific special information. Since this method uses two keys, it is also called "Asymmetric Key Encryption". The two keys are called the Public key and the Private key and are self-explanatory in their names.

Generic PKC employs two keys that are mathematically related. However, knowledge of one key does not allow someone to determine the other key easily. One key is used to encrypt the plaintext and the other key is used to decrypt the ciphertext. The important point here is that it does not matter which key is applied first, but both keys are required for the process to work.

Modern PKC was first described publicly by Stanford University professor Martin Hellman and graduate student Whitfield Diffie in their paper titled "New Directions in Cryptography" in 1976. They make a clear distinction between a public key cryptosystem and public key distribution system. Consider an inverse-pair of functions defined for all $$K$$ in the set of keys $${K}$$, $$E_K:{M}\rightarrow{M}$$ and similarly defined $$D_K$$, where $${M}$$ is set of messages (plaintext). Additionally, it should be easy to compute $$E_K$$ and $$D_K$$, but a computational equivalent of $$D_K$$ must be infeasible to obtain by knowing only $$E_K$$, and $$E_K$$ and $$D_K$$ must be easy to compute once $$K$$ is given. Such a system is called a Public key cryptosystem. An example is the method provided by R.L. Rivest, A. Shamir, and L. Adleman in their paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" in the year 1977, now of course better known as RSA. Check out the article on [RSA]({{ site.baseurl }}{% post_url 2020-11-23-RSA %})!

On the other hand, in a Public key distribution system, the goal is for two users, A and B, to securely exchange a key over an insecure charmel. This key is then used by both users in a [Secret Key cryptosystem]({{ site.baseurl }}{% post_url 2020-11-16-SKC %}) for both enciphering and deciphering. They provide one example by using the properties of discrete logarithms. Let us first look at the explanation and later the math behind it.

Diffie-Hellman Key Exchange

The Public key consists of two numbers - n and g, where n is a prime number and g is a generator of the group $$Z^{*}_n$$ (since n is a prime, there are no elements other than zero that are not invertible). Consider two people A and B who are communicating. They agree on n and g beforehand. Let us assume; for the sake of explanation, these are 17 and 3 respectively. Now A chooses a number $$a$$, say 15, and computes
{:refdef: style="text-align: center;"} $$X \equiv 3^{15} \mod 17 \equiv 6$$ {:refdef} to send it to B. Similarly, B chooses $$b$$, say 13, and computes
{:refdef: style="text-align: center;"} $$Y \equiv 3^{13} \mod 17 \equiv 12$$ {:refdef} to send it to B. At this point both A and B can compute the key independently:

• A calculates the key as $$K \equiv 12^{15} \mod 17 \equiv 10$$
  
• B calculates the key as $$K \equiv 6^{13} \mod 17 \equiv 10$$
  

Let us do a recap before delving into the math.

1. A and B agree on prime n and generator g<n
2. A chooses a natural number $$a$$ < n and sends $$X \equiv g^a \mod n$$
3. B chooses a natural number $$b$$ < n and sends $$Y \equiv g^b \mod n$$
4. Both A and B independently generate the secure secret key, A with $$K \equiv Y^a \mod n$$ and B with $$K \equiv X^b \mod n$$

Let us first look at the reason why both A and B get the same key.

• A calculates $$K \equiv Y^a \mod n$$, and we know that $$Y \equiv g^b \mod n$$
  $$\therefore K \equiv (g^b \mod n)^a \mod n$$
• B calculates $$K \equiv X^b \mod n$$, and we know that $$X \equiv g^a \mod n$$
  $$\therefore K \equiv (g^a \mod n)^b \mod n$$

This is just an extension of the law of commutativity in indices. You may also note that both $$a$$ and $$b$$ are needed to compute $$K$$. Remember that both of these properties were discussed for a generic PKC. Now let's see this from a third-person perspective, like that of a hacker. Suppose that we can access all the information exchanged between A and B. Thus, we have $$n, g, X, Y$$ and want to generate $$K$$. Suppose we try to calculate it like A does:
{:refdef: style="text-align: center;"} $$K \equiv Y^a \mod n$$
{:refdef} The only unknown here would be $$a$$. To find this, we know $$X$$ and that $$X \equiv g^a \mod n$$.
In the given example above, $$X=6$$, $$g=3$$ and $$n=17$$, so we get $$6 \equiv 3^a \mod 17$$. Go ahead and try to find a from just this information! Doing this is the only way to give you a sense of why this is a difficult procedure. You probably guessed the numbers one by one, from 1, 2, 3, ... , n-1; calculating the exponent and respective modulus each time. We know $$a$$ could be anywhere between 1 and n. Since this was an example for explanation, n was taken as 17. Imagine the computation required when n is 10⁹+7.

Concluding remarks

• Versed with basic Group theory? If you revisit the recap but instead of n as a prime, take it to be the order of the Group, then you get the generalised steps for a finite cyclic group G.
• This explanation is of the original proposal so does not cover authentication, such as a digital certificate, of the communicating parties and hence is susceptible to MITM attacks.
• This can be extended to multiple users on the same network as well!