How are Elliptic Curve private and public keys actually used to encrypt or sign data?

Question

I've read article after article about curve parameters, generator points, the dot operation, and how you dot the generator point priv times to get the pub point and voila you have ECC! That's where the articles all stop. But how are the number priv and the point pub used to modify data during encryption or signing?

Answer 1

The simplest application of elliptic curves is Diffie–Hellman key agreement. In a curve $E/k$ over a field $k$ with a standard base point $P \in E(k)$ of large prime order $\ell$ among the $k$-rational points (loosely, the points whose $x$ and $y$ coordinates are in $k$, and not in a field extension of $k$), Alice picks a uniform random scalar $a \in \mathbb Z/\ell\mathbb Z$ and publishes the point $A = [a]P$, the scalar multiplication of the standard base point $P$ by $a$; Bob does likewise with $b$ and $B = [b]P$. Now Alice can compute $$[a]B = [a]([b]P) = [a\cdot b]P,$$ and Bob can compute $$[b]A = [b]([a]P) = [b\cdot a]P = [a\cdot b]P.$$ They can then both hash this common curve point into a shared secret $k = H([a\cdot b]P)$, and use $k$ for symmetric-key authenticated encryption, such as AES-GCM.

This is a high-level overview—there are, of course, devils in the details like how to choose the curve, how to represent the curve points, how to perform the computation, etc., some of which are addressed in SafeCurves.

But what about public-key encryption and public-key signature?

Encryption

Instead of using a long-term key pair $(a, A)$, when Alice wants to send a message to Bob she can generate a temporary secret scalar $t$, compute a temporary public key $T = [t]P$, compute a temporary session key $k = H([t]B) = H([t\cdot b]P)$, and transmit $T$ as associated data with a symmetric-key AEAD box (authenticated encryption with associated data) under $k$.

Then Bob, on receipt of $T$ and an AEAD box, computes $k = H([b]T) = H([t\cdot b]P)$, and uses that to open the AEAD box.

That's it. It's just a DH key agreement with a temporary key pair.

Signature

There are a few different signature schemes out there based on elliptic curves. For a detailed discussion of some of the design choices that go into conventional elliptic-curve signature schemes, see djb's blog post on how to design an elliptic-curve signature system. Here's a couple of (very different) examples:

Example 1: EdDSA: Edwards-curve Digital Signature Algorithm (simplified)

This is the general form of the widely used Ed25519 signature scheme, which widely deployed and understood and considered by many to be the modern standard signature scheme.

Parameters. A field $k$, a twisted Edwards curve $E/k: y^2 - x^2 = 1 - d x^2 y^2$ over the field $k$, a standard base point $B \in E(k)$ of large prime order $\ell$, and a hash function $H\colon \{0,1\}^* \to \{0,1\}^{512}$.

Public keys. A public key is the representation of a point $A \in E(k)$.

Signatures. A signature on a message $m$ is the representation of a point $R \in E(k)$ and a scalar $s \in \mathbb Z/\ell\mathbb Z$ satisfying the verification equation $$[s] B = R + [H(\underline R \mathbin\Vert \underline A \mathbin\Vert m)] A.$$ Here $[s]B$ means scalar multiplication of the point $B$ by the scalar $s$, and $\underline R$ means the bit string encoding of the point $R$.

Private keys. A private key is a secret 256-bit string $k$ chosen uniformly at random. The 512-bit hash $H(k)$ is split into two 256-bit halves, the first interpreted as a scalar $a \in \mathbb Z/\ell\mathbb Z$ and the second taken as a bit string $h$.

To sign a message $m$, the signer computes the scalar $r = H(h \mathbin\Vert m)$, the point $R = [r]B$, and the scalar $$s = r + H(\underline R \mathbin\Vert \underline A \mathbin\Vert m) a.$$

Verifying that signatures created this way satisfy the verification equation is left as an exercise for the reader.

Example 2: BLS signatures using pairing-based cryptography

The Boneh–Lynn–Shacham signature scheme uses a function called a pairing, which is a bilinear map $e\colon E(k) \times E(k) \to G$ from the group $E(k)$ of $k$-rational -points on a curve $E/k$ with coordinates in the field $k$ to a multiplicative group $G$, typically the multiplicative group $(\mathbb Z/p\mathbb Z)^\times$ of integers modulo a prime $p$.

‘Bilinear’ means that if $X$, $Y$, and $Z$ are elements of $E(k)$, then $e(X + Y, Z) = e(X, Z) \cdot e(Y, Z)$ and $e(X, Y + Z) = e(X, Y) \cdot e(X, Z)$, i.e. that addition of two inputs carries through to multiplication of the outputs. This further means scalar multiplication $[a]X$ the curve carries through to exponentiation $g^a$ in the target group: $e([a]X, [b]Y) = e(X, Y)^{a b}$.

Pairing-based cryptography is not as widely deployed, and its security is not as well-understood, but it admits very short signatures (half the size of Ed25519 with a curve of comparable conjectured security, for example), and it is simple to state.

Parameters. A field $k$, an elliptic curve $E/k$, group $G$, a bilinear map $e \colon E(k) \times E(k) \to G$, a standard base point $B \in E(k)$ of large prime order $\ell$, and a hash function $H\colon \{0,1\}^* \to E(k)$ mapping messages to curve points.

Public keys. A public key is the representation of a point $P \in E(k)$.

Signatures. A signature on a message $m$ is the representation of a point $S \in E(k)$ such that $$e(S, B) = e(H(m), P).$$

Private keys. A private key is a secret scalar $p \in \mathbb Z/\ell\mathbb Z$ such that $P = [p]B$, the scalar multiplication of $B$ by $p$.

To sign a message $m$, the signer simply computes $S = [p] H(m)$.

Verifying that signatures created this way satisfy the verification equation is left as an exercise for the reader.