2024.06 Vol.3

Asymmetry

Back in the late 70’s, the bombshell papers by Ron Rivest, Adi Shamir and Leonard Adleman (RSA) and Diffie–Hellman (DE) dropped and the world was rocked. Or should have been, I dunno I wasn’t there. But these papers defined asymmetric cryptographic schemes for encryption, signatures, and key exchanges. Asymmetry brought about the “public” and “private” components of cryptographic schemes which leverage a trapdoor function. And while asymmetric cryptography was introduced with math backed by prime factorization, this implements the same abstract algebra layer which elliptic curve operations implement today. The prime factorization is a group (technically a subgroup) over a finite set whose operation (multiplication) has the discrete log problem. There are performance differences and tradeoffs between multiplying primes and adding elliptic curve points, but they provide the same guarantees and don’t affect the mental model for how encryption, signatures, and keys are provided.

So, just how is that encryption provided? In symmetric cryptography land, the model is simple, a single key is used to encrypt and decrypt data. And symmetric ciphers are fantastic at doing these operations. The difficult part is securely sharing that key between parties. In asymmetric land, one of the keys is designed to be shared in the open, the public key, so that challenge is way easier! Now if Alice wants to send a private message to Bob, she needs to encrypt it with Bob’s public key, so that only he can decrypt it with his private key. This is where things get way harder, because she can’t go using one of those finely tuned symmetric ciphers with the public key, because then anyone with that public key could decrypt the message. We need to somehow leverage the asymmetric trapdoor function. There are a lot of subtleties to do this right, and adding to the confusion, probably an infinite number of ways to do this. But walking through a simple (definitely not completely secure) example gives you the jist.

In order to leverage the trapdoor function, the message to encrypt needs to somehow be converted into elliptic curve points (or raised primes if using the older implementation, but just gonna focus on points). This is the only way to hide it when sent over a public channel. The ElGamal scheme is an option. Let’s assume for now that we have a way to map some random message m to a point M. Alice wants to send message m to Bob who has the public key P and private key p.

// Alice chooses a random nonce scalar n and raises it to a point C_1.
C_1 = n * G  

// Alice tweaks Bob's public key P with the nonce n and adds the message point M.
C_2 = n * P + M

// Alice passes Bob the (C_1, C_2) pair of points over a public channel.
// The points are useless for anyone else listening in. 
// Bob pulls out the message M by tweaking C_1 with his private key p.
M = C_2 - p * C_1 
M = (n * P + M) - p * (n * G)
M = (n * P + M) - n * (p * G)
M = (n * P + M) - n * P
// See?
M = M

Embed a message M in two points to send over a public channel.

So Alice is able to hide a message M by sending two points over a channel. Now we are just left with what exactly is the mapping of the original message m to the point M? Well, if m is small enough to be a scalar, we could then just raise it by G to get a point M. But that would leave Bob in a tough spot where he needs to crack the DLP in order to map M back to m. What if we instead treat the point M like plaintext. M is a point, coordinates (x, y), can we embed m in those coordinates? If m is small enough, we could just split it and treat the first 256 bits (if using a curve like secp256k1) as x and the second chunk as y, but the chances of this actually being a point on the curve are extremely low. What if m fit into just 256 bits? Then we could fit it into just x and calculate an appropriate y. For some curves, not every x coordinate has a y on the curve, but it turns out there is usually about a 50% chance. So with a small amount of extra bits to pad and grind we can find a point pretty quick. If m is longer than the amount of bits in x, it can be chunked up into multiple points.

This is just one possible scheme, but it shows the general challenge of the overhead due to asymmetric encryption. Compared to a finely tuned symmetric encryption cipher, we now have a random nonce per message chunk, some extra calculations to find a coordinate, and each chunk is sent over the wire as two points. This is a good amount more computation and space requirements. Good thing though it is easy to get the best of both worlds! We use asymmetric encryption to establish a symmetric key (relatively small amount of data) over a public channel and then use symmetric encryption to encrypt the bulk of the data. Pretty much everyone and their mom agrees this is an awesome combo, but there are surprisingly large number of ways it is actually implemented in the wild.

Key Establishment

How do we establish a symmetric key using asymmetric cryptography? The OG of key establishment protocols is the previously mentioned Deiffie-Hellman (DE). DE leverages some more algebra to describe a key exchange, or key agreement, which is a sub-case of key establishment where the symmetric key is derived from inputs from both parties. In DE’s case, the inputs are Alice and Bob’s public keys.

// Alice and Bob's private public key pairs.
P_a = p_a * G
P_b = p_b * G  

// Alice and Bob exchange public keys. 
// They then tweak it with their private key to arrive at the same secret point K.
K = P_a * p_b = P_b * p_a
K = (p_a * G) * p_b = (p_b * G) * p_a
K = p_a * p_b * G = p_a * p_b * G

Establish a shared secret over an open channel with an anonymous elliptic curve Deiffie-Hellman key exchange.

Another sub-case of key establishment is key transport, or key encapsulation mechanism (KEM), where one party creates a secret (so only one party provides inputs) and then just sends it to the other. This might be helpful in use cases where you don’t want to wait for collaboration with the other party to start sending some encrypted data.