Elliptic Curve Cryptography

椭圆曲线源自求椭圆弧长的椭圆积分的反函数。

椭圆曲线密码（Elliptic Curve Cryptography）包括：

基于椭圆曲线的公钥密码
基于椭圆曲线的数字签名
基于椭圆曲线的密钥交换

椭圆曲线密码密钥短但强度高，密钥长度为 224-255 比特的椭圆曲线密码与密钥长度为 2048 比特的 RSA 具备几乎相同的强度。

Elliptic Curve Math

Finite Fields

A finite field consists of a finite set of objects called field elements together with the description of two operations — addition and multiplication — that can be performed on pairs of field elements. There is a finite field containing $$q$$ field elements if and only if $$q$$ is a power of a prime number, and furthermore that for each such $$q$$ there is precisely one finite field.

对于包含 $$q$$ 个元素的有限域，要满足 $$q = p^r$$，其中底数 $$p$$ 是素数，指数 $$r$$ 是正整数（可以是 1）。

Two common types of finite field:

Prime finite field: $$F_p$$
- $$q = p = p^1$$, $$p$$ is an odd prime.
- The finite field containing $$q$$ elements is denoted by $$F_q$$.
Characteristic 2 finite fields: $$F_{2^m}$$
- $$q = 2^m$$, $$m ≥ 1$$

$$F_p$$ contains $$p$$ elements represented by the set of integers $$\{0, 1, . . . , p − 1\}$$, with addition and multiplication defined as follows:

Addition: If $$a, b ∈ F_p$$, then $$a + b = r$$ in $$F_p$$, where $$r ∈ [0, p − 1]$$ is the remainder when the integer $$a + b$$ is divided by $$p$$.
- This is known as addition modulo $$p$$ and written $$a + b ≡ r \ (mod \ p)$$.
Multiplication: If $$a, b ∈ F_p$$, then $$ab = s$$ in $$F_p$$, where $$s ∈ [0, p − 1]$$ is the remainder when the integer $$ab$$ is divided by $$p$$.
- This is known as multiplication modulo $$p$$ and written $$ab ≡ s \ (mod \ p)$$.

In this representation of $$F_p$$, the additive identity or zero element is the integer 0, and the multiplicative identity is the integer 1.

It is convenient to define subtraction and division of field elements just as it is convenient to define subtraction and division of integers.

Additive inverse (subtraction): If $$a ∈ F_p$$, then the additive inverse $$(−a)$$ of $$a$$ in $$F_p$$ is the unique solution to the equation $$a + x ≡ 0 \ (mod \ p)$$.
Multiplicative inverse (division): If $$a ∈ F_p$$, $$a ≠ 0$$, then the multiplicative inverse $$a^{−1}$$ of $$a$$ in $$F_p$$ is the unique solution to the equation $$ax ≡ 1 \ (mod \ p)$$.
- Multiplicative inverses can be calculated using the extended Euclidean algorithm.

There is this restriction $$⌈log_2p⌉ ∈ \{192, 224, 256, 384, 521\}$$.

$$⌈⌉$$ means ceiling.
It is designed to facilitate interoperability, while enabling implementers to deploy implementations which are efficient in terms of computation and communication since $$p$$ is aligned with word size, and which are capable of furnishing all commonly required security levels.
Inclusion of $$⌈log_2p⌉ = 521$$ instead of $$⌈log_2p⌉ = 512$$ is an anomaly chosen to align this document with other standards efforts — in particular with the U.S. government’s recommended elliptic curve domain parameters.

有限域中的运算是时钟运算：想象一个表盘上有 $$p$$ 个数字的时钟，在这个时钟上进行加减乘除运算，直观来说，就是用整数来计算坐标，并将结果除以 $$p$$ 求余数。

Elliptic Curves

An elliptic curve over $$F_p$$ is defined in terms of the solutions to an equation in $$F_p$$. Let $$F_p$$ be a prime finite field so that $$p$$ is an odd prime number, and let $$a, b ∈ F_p$$ satisfy $$4a^3+27b^2 \not \equiv 0 \ (mod \ p)$$. Then an elliptic curve $$E(F_p)$$ over $$F_p$$ defined by the parameters $$a, b ∈ F_p$$ consists of the set of solutions or points $$P = (x, y)$$ for $$x, y ∈ F_p$$ to the equation $$y^2 ≡ x^3 + ax + b \ (mod \ p)$$ together with an extra point $$O$$ called the point at infinity.

The equation $$y^2 ≡ x^3 + ax + b \ (mod \ p)$$ is called the defining equation of $$E(F_p)$$.
For a given point $$P = (x_P , y_P )$$, $$x_P$$ is called the $$x$$-coordinate of $$P$$, and $$y_P$$ is called the $$y$$-coordinate of $$P$$.
$$F_p$$ 上的椭圆曲线 $$E(F_p)$$ 就是 $$x, y ∈ F_p$$ 且满足椭圆曲线方程 $$y^2 ≡ x^3 + ax + b \ (mod \ p)$$ 的点 $$(x, y)$$ 的集合加上无穷远点 $$O$$。
- $$F_p$$ 的元素个数是 $$p$$，$$F_p$$ 上的元素可以表示为整数集合 $$\{0,1,…,p−1\}$$，而 $$x, y ∈ F_p$$，所以 $$x$$ 和 $$y$$ 必然都是整数；整数意味着不连续，因此椭圆曲线对应的图像实际上是散点图。
- Because this curve is defined over a finite field of prime order instead of over the real numbers, it looks like a pattern of dots scattered in two dimensions on an unfathomably large grid.

The number of points on $$E(F_p)$$ is denoted by $$\#E(F_p)$$. $$\#E(F_p)$$ is called the order of the curve $$E$$.

The Hasse Theorem states that $$p + 1 - 2 \sqrt p \leq \#E(F_p) \leq p + 1 + 2 \sqrt p$$.

Addition rule of adding points on $$E$$:

$$O + O = O$$.
$$(x, y) + O = O + (x, y) = (x, y)$$ for all $$(x, y) ∈ E(F_p)$$.
$$(x, y) + (x,−y) = O$$ for all $$(x, y) ∈ E(F_p)$$.
- I.e. the negative of the point $$(x, y)$$ is $$−(x, y) = (x,−y)$$.
Let $$(x_1, y_1) ∈ E(F_p)$$ and $$(x_2, y_2) ∈ E(F_p)$$ be two points such that $$x_1 \neq x_2$$. Then $$(x_1, y_1) + (x_2, y_2) = (x_3, y_3)$$, where $$x_3 \equiv λ^2 − x_1 − x_2 \ (mod \ p)$$, $$y_3 \equiv λ(x_1 − x_3) − y_1 (mod \ p)$$, and $$λ \equiv \frac{y_2 − y_1}{x_2 − x_1} (mod \ p)$$.
Let $$(x_1, y_1) ∈ E(F_p)$$ be a point with $$y_1 \neq 0$$. Then $$(x_1, y_1) + (x_1, y_1) = (x_3, y_3)$$, where $$x_3 \equiv λ^2 − 2x_1 \ (mod \ p)$$, $$y_3 \equiv λ(x_1 − x_3) − y_1 (mod \ p)$$, and $$λ \equiv \frac{3x_1^2 + a}{2y_1} (mod \ p)$$.

The group points on $$E(F_p)$$ is abelian — meaning that $$P_1 + P_2 = P_2 + P_1$$ for all points $$P_1, P_2 ∈ E(F_p)$$.

Elliptic curve addition is defined such that given two points $$P_1$$ and $$P_2$$ on the elliptic curve, there is a third point $$P_3 = P_1 + P_2$$, also on the elliptic curve. Geometrically, this third point $$P_3$$ is calculated by drawing a line between $$P_1$$ and $$P_2$$. This line will always intersect the elliptic curve in exactly one additional place. Call this point $$P_3’ = (x, y)$$. Then reflect in the $$x$$-axis to get $$P_3 = (x, –y)$$. If $$P_1$$ and $$P_2$$ are the same point, the line “between” $$P_1$$ and $$P_2$$ should extend to be the tangent to the curve at this point $$P_1$$. This tangent will intersect the curve at exactly one new point.

In elliptic curve math, there is also a point called the “point at infinity,” which roughly corresponds to the role of the number zero in addition.

In some cases (e.g., if $$P_1$$ and $$P_2$$ have the same $$x$$ values but different $$y$$ values), the line will be exactly vertical, in which case $$P_3 =$$ the point at infinity.
- 点 $$A$$ 关于 $$x$$ 轴对称位置的点定义为 $$-A$$，这样的运算称为“椭圆曲线上的正负取反运算”。计算 $$A + (-A)$$ 时，过 $$A$$ 和 $$-A$$ 的直线与椭圆曲线之间只有 $$A$$ 和 $$-A$$ 这两个交点，于是认为这条直线与椭圆曲线在“无限远点”的位置相交，无限远点无法画出来，记作 $$O$$；无线远点 $$O$$ 的作用与数字 0 类似。
If $$P_1$$ is the point at infinity, then $$P_1 + P_2 = P_2$$. Similarly, if $$P_2$$ is the point at infinity, then $$P_1 + P_2 = P_1$$.

On computers, it’s sometimes represented by $$x = y = 0$$ (which doesn’t satisfy the elliptic curve equation, but it’s an easy separate case that can be checked).

$$+$$ is associative, which means that $$(A + B) + C = A + (B + C)$$ and we can write $$A + B + C$$ (without parentheses) without ambiguity.

Cryptographic schemes based on ECC rely on scalar multiplication of elliptic curve points. Given an integer $$k$$ and a point $$P ∈ E(F_p)$$, scalar multiplication is the process of adding $$P$$ to itself $$k$$ times.

The result of this scalar multiplication is denoted $$kP$$.
Scalar multiplication of elliptic curve points can be computed efficiently using the addition rule together with the double-and-add algorithm or one of its variants.

Elliptic curve domain parameters over $$F_p$$ are a sextuple: $$T = (p, a, b, G, n, h)$$

Integer $$p$$ specifies the finite field $$F_p$$.
Two elements $$a, b ∈ F_p$$ specify an elliptic curve $$E(F_p)$$ defined by the equation: $$E: y^2 \equiv x^3 + ax + b \ (mod \ p)$$.
A base point $$G = (x_G, y_G)$$ on $$E(F_p)$$.
A prime $$n$$ which is the order of $$G$$.
- The order of a point $$P$$ is the smallest positive integer $$n$$ such that $$nP = O$$ (the point at infinity).
- $$n \neq p$$
An integer $$h$$ which is the cofactor $$h = \#E(F_p)/n$$.

Ethereum uses the exact same elliptic curve ($$y^2 = x^3 +7 \ (mod \ p)$$, $$p = 2^{256} – 2^{32} – 2^9 – 2^8 – 2^7 – 2^6 – 2^4 – 1$$), called secp256k1, as Bitcoin. That makes it possible to reuse many of the elliptic curve libraries and tools from Bitcoin.

NIST 推荐的一种椭圆曲线 Curve P-521，其质数 $$p = 2^{521} - 1$$ 是长达 157 位的数。

Elliptic Curve Key Pairs

Given some elliptic curve domain parameters $$T = (p, a, b, G, n, h)$$, an elliptic curve key pair $$(d,Q)$$ associated with $$T$$ consists of an elliptic curve secret key $$d$$ which is an integer in the interval $$[1, n − 1]$$, and an elliptic curve public key $$Q = (x_Q, y_Q)$$ which is the point $$Q = d×G$$.

Private Key

A private key is simply a number, picked at random. It can be any nonzero number up to a very large number slightly less than $$2^{256}$$—a huge 78-digit number, roughly $$1.158 * 10^{77}$$.

The visible universe is estimated to contain $$10^{80}$$ atoms.
If you pick a private key randomly, there is no conceivable way anyone will ever guess it or pick it themselves.

To create a private key, we randomly pick a 256-bit number and check that it is within the valid range.

This is usually achieved by feeding an even larger string of random bits (collected from a cryptographically secure source of randomness) into a 256-bit hash algorithm such as Keccak-256 or SHA-256. If the result is within the valid range, we have a suitable private key. Otherwise, we simply try again with another random number.
- It is vital that you use a cryptographically secure pseudorandom number generator (such as CSPRNG) with a seed from a source of sufficient entropy.
The private key generation process is an offline one.

Public Key

A public key is a point on an elliptic curve, meaning it is a set of $$x$$ and $$y$$ coordinates that satisfy the elliptic curve equation.

The public key is calculated from the private key using elliptic curve multiplication, which is practically irreversible (“finding the discrete logarithm” problem): $$K = k × G$$.

$$k$$ is the private key;
$$G$$ is the base point called the generator point;
$$×$$ is the special elliptic curve “multiplication” operator;
$$K$$ is the resulting public key;

Signature Schemes

Signature schemes are designed to be used by two entities — a signer U and a verifier V — when U wants to send a message M in an authentic manner and V wants to verify the authenticity of M. In fact, once a message is signed, any entity V having a copy of U’s public key may verify the signature S.

Signature schemes are described in terms of a signing operation, a verifying operation, and associated setup and key deployment procedures.

There are 2 types of signature schemes:

Signature schemes with appendix in which U must convey both M and S to V.
Signature schemes with message recovery in which M can be recovered from S, so U need convey only S to V.

ECDSA

ECDSA (Elliptic Curve Digital Signature Algorithm) uses only integer mathematics, there are no floating points.

The range of the numbers is bound by how many bits are used in the signature. Usually ECDSA will use 160 bits (49 digits in decimal). ECDSA is used with a SHA1 hash algorithm. SHA1 outputs 160 bits.

前置准备：

约定曲线参数 $$p,a,b,G,n,h$$，$$y^2 = x^3 + ax + b \ (mod \ p)$$；
- The modulo $$p$$ is a prime number and makes sure that all the values are within the range of 160 bits, and it allows the use of “modular square root” and “modular multiplicative inverse” mathematics which make calculating stuff easier.
生成私钥 $$d_A$$ 和公钥 $$Q_A$$；
- $$d_A$$ 是在 $$[1, n − 1]$$ 范围内的 160 bits 的随机数；
- $$Q_A = d_A × G$$

m 是待签名的消息，签名结果的大小是 40 字节，由 $$R$$ 和 $$S$$ 两个 20 字节的数组成。

In Ethereum’s implementation of ECDSA, the “message” being signed is the Keccak-256 hash of the RLP-encoded transaction data.

签名过程：

计算 $$R$$：
1. 生成密码学安全的 $$[1, n-1]$$ 范围内的随机数 $$k$$；
  - $$k$$ ensures that the sender’s actual private key can’t be calculated by attackers watching signed transactions.
2. 计算点 $$(x, y) = k × G$$；
3. $$x$$ 就是 $$R$$（如果 $$R = 0$$，回到 1.1 重新开始）。
计算 $$S$$：
1. 计算消息摘要 z = HASH(m)；
2. 计算 $$S = k^{-1} (z + d_AR) \ (mod \ p)$$（如果 $$S = 0$$，回到 1.1 重新开始）。

Sony Playstation 3 Hack 就是每次使用相同的 $$k$$ 导致的，攻击过程如下：

拿到消息 m 和 m' 的签名，由于 $$k$$ 相同，两个签名的 $$R$$ 也相同；
z = HASH(m)，z' = HASH(m')；
$$S = k^{-1} (z + d_AR) \ mod \ p$$
$$S’ = k^{-1} (z’ + d_AR) \ mod \ p$$
$$S - S’ = k^{-1} (z + d_AR - z’ - d_AR) = k^{-1} (z - z’)$$；
$$k = (z – z’) / (S – S’)$$；
由 $$S = k^{-1} (z + d_AR) \ (mod \ p)$$ 得到 $$d_A = (Sk - z) / R$$。

验签过程：

$$R$$ 和 $$S$$ 都在 $$[1, n-1]$$ 范围内；
计算消息摘要 z = HASH(m)；
计算 $$u_1 = zS^{-1} \ mod \ p$$；
计算 $$u_2 = RS^{-1} \ mod \ p$$；
计算点 $$(x_1, y_1) = u_1 × G + u_2 × Q_A$$，记为 $$C$$；
- $$C = u_1 × G + u_2 × Q_A$$，代入 $$Q_A$$；
- $$C = u_1 × G + u_2d_A × G$$，提取 $$× G$$；
- $$C = (u_1 + u_2d_A) × G$$，代入 $$u_1$$、$$u_2$$；
- $$C = (zS^{-1} + RS^{-1}d_A) × G$$，提取 $$S^{-1}$$；
- $$C = (z + Rd_A)S^{-1} × G$$，代入 $$S$$；
- $$C = (z + Rd_A)(z + d_AR)^{-1}(k^{-1})^{-1} × G$$；
- $$C = k × G$$，同时 $$(x, y) = k × G$$，$$x$$ 正是 $$R$$。
若 $$R ≡ x_1$$，则签名合法。

A signer U may verify U’s own signatures more efficiently using U’s own private key. A situation where this could be useful is when a CA verifies its own certificates.

SM2

$$Z_A$$ 用于表示关于用户 A 的可辨别标识、部分椭圆曲线系统参数和用户 A 公钥的杂凑值。

$$Z_A = H_{256}(ENTL_A || ID_A || a || b || x_G || y_G || x_A || y_A)$$

$$H_{256}$$ 是国密哈希函数 SM3;
$$x || y$$ 表示 $$x$$ 与 $$y$$ 的拼接，$$x$$ 与 $$y$$ 可以是比特串或字节串；

签名者 A 的可辨别标识 $$ID_A$$ 的比特数记为 $$entlen_A$$，$$ENTL_A$$ 是由整数 $$entlen_A$$ 转换而成的两个字节；

id := []byte("1234567812345678")
entlenA := uint16(len(id) * 8)
// https://github.com/Hyperledger-TWGC/ccs-gm/blob/4f6995bffc6d60c0f1b147688c42facb038f76f8/sm2/sm2.go#L96
// https://github.com/tjfoc/gmsm/blob/master/sm2/sm2.go#L443

$$a$$、$$b$$ 是椭圆曲线参数；
$$x_G$$、$$y_G$$ 是基点的坐标；
$$x_A$$、$$y_A$$ 是签名者 A 的公钥坐标。