3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So if I understand correctly, if the field is limited by $\ell$ then any private key (Alice's $a$, Bob's $b$ or a temporary key of $t$) larger than $\ell$ is equivalent to that key mod $\ell$, right? Basically any scalar you multiply the generator point by has no benefit to being larger than $\ell$? I'm still processing Example 2, maybe a larger scalar matters there. $\endgroup$ – Corey Ogburn Nov 6 '17 at 16:58
  • $\begingroup$ Yes: secret scalars are always elements of $\mathbb Z/\ell\mathbb Z$. Note that $\ell$ is not a property of the field, although it is limited by the size of the field, according to Hasse's theorem—it is a property of the field and the curve, and may vary from point to point in cases of curves like Curve25519 with composite order. See an earlier answer I wrote for more details on how they are related. $\endgroup$ – Squeamish Ossifrage Nov 6 '17 at 17:12
  • $\begingroup$ @SqueamishOssifrage: you've posted an abundance of incredibly useful and helpful on this forum (some of which I actually understood ;-) ). anyway -- under "Encryption", you wrote compute a temporary session key 𝑘=𝐻([𝑡]𝐵)=𝐻([𝑡⋅𝑏]𝐵), and transmit 𝑇 -- seems that there might be typo? Seems like 𝑘=𝐻([𝑡]𝐵)=𝐻([𝑡⋅𝑏]P) might be the intent? Always intimidating to post a suggested correction to an expert, sorry if I missed the boat here. $\endgroup$ – Dan Jun 8 at 22:17
  • $\begingroup$ @Dan Thanks, you are absolutely correct: it was a typo! Fixed. $\endgroup$ – Squeamish Ossifrage Jun 9 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.