Introduction

Lots of security concepts in information technology fundamentally rely on Public Key Cryptography, more formally called Asymmetric Cryptography. As a companion to other docs that I’m writing I wanted to write a separate piece just about the core concepts of public-private keys, how they work, how they facilitate basic security concepts and how they are used as building blocks in larger systems.

History

The basic idea of an asymmetric public-private key cryptosystem is attributed to Whitfield Diffie and Martin Hellman, who published the concept in 1976, although their formulation left open the problem of creating a one-way function. Ron Rivest, Adi Shamir, and Leonard Adleman did further work and ultimately published their version of a complete cryptosystem in 1997. The algorithm became known as RSA, named for the initials of the scientists in the order presented in their paper.

RSA was the dominant scheme for some time but ultimatey other schemes (e.g. Ellitic Curve Cryptography) (ECC) were developed and adopted, first for specific use cases and then later for others.

Common structural features

Public/private key pair

Whether it’s RSA or ECC, both schemes allow for the generation of …

• A public key (to be freely shared)
• A private key (to be kept secret)

The keys are mathematically related, but - and this is the critical part …

“Given the public key, it is computationally infeasible to compute the private key”

That infeasibility is based on a hard mathematical problem:

System	Hard Problem
RSA	Integer factorization
ECC	Elliptic curve discrete logarithm

One-way function

Both rely on a function that …

• Is easy to compute in one direction
• Is hard to reverse
• Is easy to reverse if you know the private key

This is called a trapdoor one-way function. That structure is what enables all three major uses.

Modular arithmetic structure

Both operate in structured mathematical groups …

• RSA - integers mod n
• ECC - points on an elliptic curve over a finite field

In both cases …

• There is a defined operation
• That operation is associative
• Inverses exist
• There is an identity element

That algebraic structure is what makes them usable for encryption, signatures, and key exchange.

Uses

Public key encryption

The public key performs a transformation and only the private key can reverse it.

RSA was originally designed for encryption (Encryption: \(c = m^e \bmod n\), Decryption: \(m = c^d \bmod n\)). The public key is (n, e) and the private key is d.

ECC is not usually used directly for encryption.

Digital signatures

A signature is created only by the private key holder and is verifiable by anyone with the public key. This requires a function that depends on the private key and a verification equation that uses the public key.

With RSA the basic idea is that you hash the message and then raise the hash to a private exponent to calculate the signature (\(s = H(m)^d \bmod n\)). Then both the message and its signature are diseminated.

To verify the message you calculate the hash two ways …

• By applying the known hash function (e.g. SHA256) to the message body
• By extracting the hash from the signature using the public key (\(H(m) = s^e \bmod n\))

If both hashes match then the message has not been modified since it was signed. As above, the public key is (n, e) and the private key is d.

The ECC scheme is called ECDSA. It is different mathematically but structurally similar. The signature depends on a private scalar and a random nonce. Verification uses a public key (a curve point) and group arithmetic. Security depends on the hardness of the elliptic curve discrete log and the inability to derive the private scalar from the public key.

Key exchange

RSA can be used for key exchange by …

• Client generates random symmetric key
• Encrypts it with server’s public key
• Server decrypts with private key

But that’s not a true “shared computation”, it’s more like “one side generates a secret and protects it”.

ECC Key Exchange (Elliptic Curve Diffie-Hellman or ECDH) works differently.

Both sides …

• Agree on a generator point on a known elliptic curve: G
• Generate a private scalar: Alice chooses a, Bob chooses b
• Compute a public point: Alice calculates A = aG, Bob calculates B = bG
• Exchange public points: Alice receives B, Bob receives A
• Compute the shared secret: Alice calculates S = aB = a(bG), Bob calculates S = bA = b(aG). But elliptic curve scalar multiplication is associative so a(bG) = b(aG). Thus both calculate the same secret.

Both sides independently compute the same value. No secret is transmitted.

The shared secret is not directly used as a symmetric key. Instead the x-coordinate of point S is fed into a key derivation function to produce symmetric encryption keys (\(\text{Session Key} = \text{KDF}(S_x)\)).

Summary

Asymmetric cryptography supports public key encryption, digital signatures and key exchange. RSA was originally used for all three use cases but modern libraries (TLS 1.3) use Elliptic Curve Cryptopgraphy for digital signatures (ECDSA) and key exchange (ECDH).