Website of Chuck Easttom, Ph.D., D.Sc.




Ancient Ciphers  |  Symmetric Cyphers |  Classic Asymmetric Cryptography | Quantum Resistant Asymmetric Cryptography


  1. AES Animation
  2. RSA Expalined
  3. Diffie Hellman Explained
  4. Learning With Errors Explained
  5. NIST PQC Round 4
  6. Kyber Algorithm

Asymmetric Algorithms

 

Diffie - Hellman

A cryptographic protocol that allows two parties to establish a shared key over an insecure channel.
Developed by Whitfield Diffie and Martin Hellman in 1976. An interesting twist is that the method had actually been developed a few years earlier by Malcolm J. Williamson of the British Intelligence Service, but it was classified.

Many cryptography textbooks use the fictitious characters ‘alice’ and ‘bob’ to illustrate cryptography and we will do that here as well:
1. Alice generates a random private value a and Bob generates a random private value b. Both a and b are drawn from the set of integers
2. They derive their public values using parameters p and g and their private values. Alice's public value is ga mod p and Bob's public value is gb mod p.
3. They exchange their public values.
Alice computes gab = (gb)a mod p, and Bob computes gba = (ga)b mod p.
4. Since gab = gba = k, Alice and Bob now have a shared secret key k.

 

RSA

The algorithm was publicly described in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT; the letters RSA are the initials of their surnames. This is perhaps the most widely used public key cryptography algorithm in existence today.
It is based on some interesting relationships with prime numbers. The security of RSA derives from the fact that it is difficult to factor a large integer composed of two or more large prime factors.

 

Key generation
Generate two large random primes, p and q, of approximately equal size such that their product n = pq is of the required bit length (such as 2048 bits, 4096 bits, etc.)
Let n = pq
Let m = (p-1)(q-1)
Choose a small number e, co-prime to m (note: Two numbers are co-prime if they have no common factors.)
Find d, such that de % m = 1
Publish e and n as the public key. Keep d and n as the secret key.

 

Encrypt
C= Me % n
Put another way
Computes the ciphertext c = me mod n
Decrypt
P = Cd % n
Put another way
Uses his private key (d,n) to compute m = cd mod n

Elgamal

It is based on the Diffie–Hellman key exchange. It was first described by Taher Elgamal in 1984. ElGamal is based on the Diffie Hellman key exchange algorithm described earlier in this chapter.  It is used in some versions of PGP

The ElGamal algorithm has three components: the key generator, the encryption algorithm, and the decryption algorithm. 

MQV

 MQV (Menezes–Qu–Vanstone) is a protocol for key agreement that is based on Diffie–Hellman. It was first proposed by Menezes, Qu and Vanstone in 1995 then modified in 1998.

MQV is incorporated in the public-key standard IEEE P1363. HQMV is an improved version. The specific algorithm is related to elliptic curves



Rabin

This algorithm was created in 1979 by Michael Rabin. Michael Rabin is an Israeli cryptographer and a recipient of the Turing Award. The Rabin cryptosystem can be thought of as an RSA cryptosystem in which the value of e and d are fixed.

e = 2 and d = ½

The encryption is C ≡ P2 (mod n) and the decryption is P ≡ C1/2 (mod n).