Actually Understanding Modern Cryptography Algorithms

Before crypto was short for cryptocurrencies, it was short for cryptography. I learned a lot of the concepts in this field just to lately realize how recent these inventions are. Surprisingly and pleasantly, I learned that every researcher on the subject is alive. Ralph Merkle of "Merkle Trees" is now working on cryonics.

The guide that dragged me in the worm hole again last night, was giving an intensive Intro. (opens new window) which isn't exactly in my learning zone. Everyone appreciates an interesting story though, for example in Lecture 10:

We only found out much later that in the late 1960’s, a few years before Merkle, James Ellis of the British Intelligence agency GCHQ was having similar thoughts. His curiosity was spurred by an old World-War II manuscript from Bell labs that suggested the following way that two people could communicate securely over a phone line. Alice would inject noise to the line, Bob would relay his messages, and then Alice would subtract the noise to get the signal. The idea is that an adversary over the line sees only the sum of Alice’s and Bob’s signals, and doesn’t know what came from what.

Brilliant system. Two equally brilliant concepts are fundamental to Today's cryptography (including cryptocurrencies), those are:

  • Symmetric Cryptography (Diffie-Hellman Key Exchange): Both parties have the deciphering key.
  • Asymmetric Cryptography (RSA Encryption Algorithm): Only one party has the deciphering key.

# Diffie-Hellman Key Exchange

This is a Symmetric Cryptography algorithm, where there is one shared key between two parties, so that they can communicate. The fascinating thing about it is that the key itself doesn't need to be sent! That way, eavesdropping becomes pointless. This video explains how:

Except the part about modulus exponents. Let's see why this is true:

(x*y) mod c = (x mod c)(y mod c) mod c

The way I described that for myself is by geometry. If we draw an x * y rectangle, we can cross out the parts with a c multiplication, except a box at the corner which is (x mod c) * (y mod c)

# RSA Encryption

But while the above works well for a two way communication, it has many limitations for the networking. An Asymmetric system allows a party to create a Public and Private set of keys. The Private key, as the name suggests, is not shared. But if another party encrypts something with the public key, it can't be broken by other observers; except for the private key holder.

So the key maker can accept messages from multiple other parties with one key pair. Another Khan Academy video to explain:

The only thing video misses at 12:00 is the Euler's Theorem explanation. The proof may be found here (opens new window) but it's too hard to follow. Instead, this video is more understandable (opens new window)

As for why when P is prime, ϕ(P^2) = P^2 - P: knowing that ϕ(p) = P - 1, I find it easy to say P^2 has P^2 - 1 numbers before it, P-1 of which are multiplications of P, P, 2P, 3P, ... (1-P)P. We just need to remove those multiplies from all numbers: (P^2 - 1) - (P - 1) gives the result.

This video is the practical solving of the algorithm (opens new window)