Asymmetric Encryption

Diffie-Hellman Key Exchange

The main disadvantage of private key cryptosystems (DES or AES) is that the private key must be exchanged. Well Diffie-Hellman algorithm is able to exchange private keys over a public channel. It was invented in 1976 by Diffie, Hellman and Merkle. So this approach is not for encryption or decryption but to securely exchange the private keys for asymmetric cryptosystems. And we can create private keys separately based on modular arithmetic.

First we have to generate huge prime numbers n and g. However g must be the primitive root of n in other words g is the primitive root n if g mod n, g² mod n ... g^n-1 mod n generates all the integers within the range [1, n-1].

1. The sender (Alice) generates huge prime numbers n and g (the primitive root of n) and sends it to the receiver (Bob) (it is not a problem if someone knows these numbers). These numbers are typically > 1024 bits.
2. Both the sender and receiver generate a random number < n-1, Alice generates x and Bob generates y (these are the private keys).
3. Alice calculates k₁ = g^x mod n and send it to Bob and Bob calculates k₂ = g^y mod n and sends it to Alice.
4. They can calculate the shared secret key :
5. Alice calculates k^x₂ mod n = (g^y mod n)^x mod n = g^xy mod n
6. Bob calculates k^y₁ mod n = (g^x mod n)^y mod n = g^yx mod n

It is very important to choose n to be prime because if n is not a prime number it's easier to crack Diffie-Hellman cryptosystem, and the whole cryptosystem relies heavily on the fact that solving the Discrete Logarithm problem has exponential running time complexity, so it's extremely hard to crack. However, if we use composite numbers for n then solving the discrete logarithm problem (cracking it) is easier because of the Chinese Remainder Theorem.

RSA (Rivest-Shamir-Adleman) cryptosystem

It is a public key cryptosystem (so it has a private key and a public key), it was constructed in 1977 by Rivest, Shamir and Adleman. Every public key cryptosystem relies heavily on a trapdoor function and RSA is secure because of the integer factorization problem. Which consist in validating the result by multiplying two numbers and that is easy but finding the factors is hard.

Let's have p be a prime number than for any integer a (a is not divisible by p) the number a^p-1-1 is an integer multiple of p.

a^p-1 ≡ 1 (mod p) which is Fermat's Little Theorem. We can generalize this theorem with Euler's Φ(n) function : this totient function counts the positive integers up to a given integer n that are relative prime to n and the formula is : a^Φ(n) ≡ 1 (mod p). Notably by relative prime we mean that two integers a and b are said to be relative prime or coprime if the only positive integer (factor) that divides both of them is 1 with this formula : gcd(a, b) = 1

1. We generate 2 large prime numbers p and q, for this we can use Rabin-Miller very optimized algorithm to do so.
2. We calculate n = p * q so let's multiply the prime numbers : Φ(n) = (p - 1) * (q - 1)
3. Let's calculate the public key e parameter, we can calculate e such that gcd(e, Φ(n)) = 1. So basically e and Φ(n) are relative primes.
4. Let's calculate the private key d parameter : let's calculate the modular inverse of e (this is why it is crucial that e and Φ(n) are coprime) : d * e mod Φ(n) = 1, after solving this equation we get the d parameter.

Then we have PUBLIC KEY : (e, n) and PRIVATE KEY : (d, n)

After those steps, to encrypt the message we first have to transform the plaintext into blocks (we can use ASCII table to convert text into numbers) where every block is smaller than n and as usual we use the public key for encryption and the private key for the decryption. That way ciphertext_block = plaintext_block^e mod n and plaintext_block = ciphertext_block^d mod n

1. We talked a lot, now let's try this in a real example, let's generate large prime numbers : p = 17 and q = 23.
2. Let's calculate n = p * q = 17 * 23 = 391 so Φ(17 - 1) * (23-1) = 352.
3. We have to find now an e number where gcd(e, Φ(n)) = 1 with Euclide Algorithm and we get e = 21.
4. We finally have to find the modular inverse of e using Extended Euclidean Algorithm and we get d = 285

Now that we have the Public key : (21, 391) and Private key : (285, 391) we can encrypt a message.

Let's say we have the character a to encrypt. The ASCII representation of a is 97.

Encryption → ciphertext_block = plaintext_block^e mod n = 97²¹ mod 391 = 37

Decryption → plaintext_block = ciphertext_block^d mod n = 37²⁸⁵ mod 391 = 97

Elliptic Curve Cryptography (ECC)

There are several problems with the RSA cryptosystem, factorization is the trapdoor-function in RSA, but it has never been proven that factorization is hard. General number field sieve (GNFS) algorithm is the fastest known algorithm for prime factorization. This is why we need huge prime numbers, therefore we use at least 2048 bits long sequences as RSA keys which is 512 hexadecimal digits. However quantum computing will make RSA obsolete in the future.

The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S.Miller in 1985. It's one of the most popular public key cryptosystems, and Bitcoin uses Elliptic Curve Cryptography.

If we are dealing with an E elliptic curve defined by y² = x³ + ax + b equation and |E| = n and P(x, y) and R(x, y) are points on the elliptic curve, the aim is to find 1 ≤ x ≤ n such that P + P + P + ... + P = R and xP = 5. This is a typical trapdoor-function : we can calculate xP with O(m) linear running time complexity but (if we have R) we have to use brute-force approach to find x and it has O(2^m) exponential running time.

In a public key (asymmetric) cryptosystem all the users have two keys : public key and private key, these keys are not independent of each other, the private key can decrypt a message that has been encrypted with the public key and vice versa. Everyone can send an encrypted message to a given user using his/her public key and only the given user can decrypt that message using his private key.