ECC

Elliptic Curve Cryptography

本文部分内容出自 Andrea Corbellini 的系列文章，搭配阅读原文体验更佳 Elliptic Curve Cryptography: a gentle introduction

椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密算法。椭圆曲线在密码学中的使用是在 1985 年由 Neal Koblitz 和 Victor Miller 分别独立提出的。

ECC 的主要优势是它相比 RSA 加密算法使用较小的密钥长度并提供相当等级的安全性[1]。ECC 的另一个优势是可以定义群之间的双线性映射，基于 Weil 对或是 Tate 对。

比特币采用了椭圆曲线签名算法来签署交易。

建议预先掌握的知识点：

• Group (mathematics) 群, Subgroup 子群, Finite field 有限域
  • Abstract Algebra: The definition of a Group
  • Group Definition (expanded) - Abstract Algebra
  • Abstract Algebra: The definition of a Subgroup
• Euler's Totient Function
• Extended Euclidean Algorithm

Elliptic Curves

首先定义椭圆曲线方程，我们需要的是在曲线上的点的集合 (the set of points described by the equation)

Different shapes for different elliptic curves (b = 1, -3 < a < 2)

Types of singularities: 左边是带奇点的曲线，右边是自相交的曲线，都不是有效的椭圆曲线

椭圆曲线关于 x 轴对称。我们还需要定义一个无穷远点作为 0 点 (symbol 0)

最终曲线定义如下

The group law for elliptic curves

Group

理解群的概念

群 G 是一个元素集合，我们给他定义了一个二元运算方法，“加法” +。

1. closure: 对于 G 中的元素 a 和 b, a + b 也是 G 中的元素;
2. associativity: (a+b)+c=a+(b+c);
3. identity element: 单位元 0 ， a+0=0+a;
4. inverse: 每个元素都有一个逆元，即对于 G 中的元素 a 都存在一个元素 b, a + b = 0;

我们附加了一条特性

5. commutativity: a+b=b+a (Abelian group 阿贝尔群)

Geometric addition

我们在椭圆曲线上定义了一个群，是曲线上点的集合

• 元素是椭圆曲线上的点
• identity element 是无穷远的 0 点(point at infinity 0)
• 对于点 P ，inverse (逆元) 是关于 x 轴对称的点
• addition 加法的规则：一条直线与椭圆曲线相交的三个非 0 的点 P, Q, R 他们的和是 0 点，即 P+Q+R=0
  • P+Q=-R
  • -R 是 R 的逆元
  • 即 P+Q 等于 R 相对于 x 轴对称的点

P+Q=-R

直线与椭圆曲线相交有三种特殊情况

1. P=0 or Q=0. 我们不可能在 xy 坐标上标出 0 点(无穷远)，所以也无法画出这条线。但我们可以将 0 点定义为 identity element (单位元)，即 P+0=P and 0+Q=Q
2. P=-Q. P 和 Q 关于 x 轴对称，此时直线将于 x 轴垂直，与椭圆曲线没有第三个交点 R，则 Q 是 P 的逆元，即 P+Q=0
3. P=Q. Q 无限接近 P 点，直线是椭圆曲线的切线,P+Q=P+P=-R

可以到这里尝试自己修改参数，观察曲线和直线交点的变化 HTML5/JavaScript visual tool

Algebraic addition

为了精确计算点的加法，我们需要把上述几何方法转换为代数算法。

已知 P,Q 的坐标，计算 R 点。

$$P=(xP, yP) Q=(xQ, yQ)$$

xP!=xQ

首先考虑 xP != xQ 的情况，直线的斜率 m 为

R 的坐标可以如下计算

或者

推导过程如下(感谢 kaiji 的补充)：

代入 Q 点和 P 点到椭圆曲线

将上述两个等式相减

将 yQ - yR 替换为 m(xQ-xR),等式两边消去 (yQ+yR)

同理可得

将上述两个等式相减

两边同时除以 (xP-xQ)

计算出 R 点之后，进而得出关于 x 轴对称点 -R，即为 P+Q 的结果

(xP,yP) + (xQ,yQ) = (xR,-yR)

我们可以用实际的点去验证上述公式

• (1,2)+(3,4)=(-3,2)
• (-1,4)+(1，2)=(1,-2)

xP=xQ

我们先将椭圆曲线方程改成 y 的一次方形式

当 P，Q 横坐标相同，直线为椭圆曲线的切线，我们将更改斜率 m 的定义为椭圆曲线的导函数

xR 和 yR 的公式保持不变，我们将 P=Q=(1,2) 代入公式验证

(1,2)+(1,2)=2(1,2)=(-1,-4)

Scalar multiplication

上述加法运算中，当 P=Q 时，P+P=2P，我们可以将其定义为 scalar multiplication 标量乘法。

nP=P+P+...+P (n times)

如果 n 在二进制中有 k 位(If n has k binary digits)，其算法复杂度 O(2^k)，我们需要对其优化。

double and add algorithm 用一个例子解释该算法工作原理：假设 n=151,其二进制表示为 10010111

double and add algorithm 将要做的是：

• P, 即 2^0*P
• P+P=2P, 即 2^1*P
• 2P+2P=4P, 即 2^2*P
• 4P+4P=8P, 即 2^3*P
• 8P+8P=16P, 即 2^4*P
• 151P = 2^4*P + 2^2*P + 2^1*P + 2^0*P

算法 python 实现

def bits(n):
    """
    Generates the binary digits of n, starting
    from the least significant bit.

    bits(151) -> 1, 1, 1, 0, 1, 0, 0, 1
    """
    while n:
        yield n & 1
        n >>= 1

def double_and_add(n, x):
    """
    Returns the result of n * x, computed using
    the double and add algorithm.
    """
    result = 0
    addend = x

    for bit in bits(n):
        if bit == 1:
            result += addend
        addend *= 2

    return result

假定 翻倍 doubling 和 加法 adding 操作都是 O(1), 那么这个算法将是 O(log(n)) (如果我们考虑 n 的位数，将是 O(k))

The field of integers modulo p

首先，有限域是具有有限个元素的集合。有限域的一个例子是模 p 的整数集合，其中 p 是素数。它通常表示为 Z/p、GF(p) 或 Fp。我们将使用后一种表示法。

在有限域中，我们有两种二元运算：addition(+), multiplication(·)。两种运算都符合 closed, associative and commutative 特性。

举例说明，对于 F23 (mod 23 的有限域)

• Addition: (18+9) mod 23 = 4
• Subtraction: (7-14) mod 23 = 16
• Multiplication: 4·7 mod 23 = 5
• Additive inverse: -5 mod 23 = 18
  • (5+(-5)) mod 23 = (5+18) mod 23 = 0
• Multiplicative inverse: 9^-1 mod 23 = 18
  • 9·9^-1 mod 23 = 9·18 mod 23 = 1

p 必须是素数！

整数模 4 的集合不是一个域：2 没有乘法逆元（即方程 2⋅x mod 4=1 没有解）。

Division modulo p

在 Fp 中的除法模运算即为求出一个元素的乘法逆元，然后执行乘法运算。

x/y = x·y^-1

根据拓展欧几里得算法 extended Euclidean algorithm , 求出一个元素的乘法逆元的复杂度将是 O(log(p)) (如果考虑二进制位数将是 O(k))。

给定 n 和 p，求 n 在 Fp 中的乘法逆元，即当 n · n^-1 mod p = 1 时，求 n^-1

上述条件可以改写为 n · x - p · y = 1, 其中 y 为 n // p (商) ， x % p 即为 n^-1 (x 有可能比 p 大，固结果还要取模)

Computing the multiplicative inverse Python implementation

• extended_euclidean_algorithm(a, b)
  • 根据拓展欧几里得算法，返回 GCD (最大公约数), x, y
  • 使用辗转相除法，当余数 r 为 0 时终止循环
  • 返回结果满足 a * x + b * y = GCD
• inverse_of(n, p) 求 n 在 Fp 中的乘法逆元
  • 当 gcd = 1 时，乘法逆元即为 x % p
  • 否则 n 在 Fp 中不存在乘法逆元

def extended_euclidean_algorithm(a, b):
    """
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t


def inverse_of(n, p):
    """
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.
        raise ValueError(
            '{} has no multiplicative inverse '
            'modulo {}'.format(n, p))
    else:
        return x % p

Elliptic curves in Fp

对椭圆曲线取模，公式将变成如下形式

0 点仍然是无穷远点，(x, y) 是 Fp 中的整数。

(上图中 p = 19,97,127,487。可以对于每个 x 值，最多存在两个点，每个点关于 y=p/2 上下对称)

(y^2= x^3 (mod 29)) 不是一个有效的椭圆曲线，包含了 0 点 (0,0)

在有限域 Fp 中，椭圆曲线仍然形成一个阿贝尔群。

Point addition

我们之前已经讨论过在椭圆曲线上 P+Q+R=0 的定义，三个点都在实属域 R 中。那么在有限域 Fp 中，将满足以下等式

(curve y^2=x^3-x+3 (mod 127), P=(16,20) and Q=(41,120))

Fp 中的加法属性

• Q + 0 = 0 + Q = Q (单位元的定义)
• 给定非零点 Q，其逆元 -Q 是横坐标相同，但纵坐标关于 y=p/2 横线对称的点，即 -Q=(2, -5 mod 29) = (2, 24)
• P+(-P)=0

Algebraic sum

将上述图形方法转为代数算法来计算 P+Q=-R

直接将实数域的公式增加 mod p

or

对于斜率 m，当 xP != xQ

当 xP = xQ

The order of an elliptic curve group

对于 Fp 的阶数 order (元素个数)，当 p 是一个很大的素数时，要计算 order 数量将会很困难， O(p)

Scalar multiplication and cyclic subgroups

对于椭圆曲线 y^2=x^3+2x+3 (mod 97) 和点 P=(3,6)，P 只需要与自己相加 5 次即可回到初始点。

• 0P=0
• 1P=(3,6)
• 2P=(80,100)
• 3P=(80,87)
• 4P=(3,91)
• 5P=0
• ...

P 的倍数只有 5 个，且是循环出现的，于是我们可以重写一下结果：

• 5kP=0
• (5k+1)P=P
• (5k+2)P=2P
• (5k+3)P=3P
• (5k+4)P=4P

P 的倍数组成的集合是椭圆曲线在 Fp 有限域中的循环子群。 (the set of the multiples of is a cyclic subgroup of the group formed by the elliptic curve.)

在该循环子群中，点 P 为称作生成元 或 基点 (generator or base point)。

循环子群是 ECC 和其他密码系统的基础。

Subgroup order

如何计算子群的阶数？

• order 阶数即为群中元素的个数，对于上述循环子群，order of P 即为满足 nP=0 的最小正整数。
• 根据拉格朗日定理 Lagrange's theorem， order of P 子群的阶数是父群的阶数的除数
  • 换言之，椭圆曲线包含 N 个点，其循环子群包含 n 个点，则 n 是 N 的除数

结合上述两条信息，计算子群阶数的步骤如下：

1. 计算椭圆曲线包含的元素个数 N 使用 Schoof's algorithm
2. 找出所有 N 的除数
3. 对每个 N 的除数 n，计算 nP
4. 满足 nP=0 条件的最小的正整数，即为子群的阶数 order of the subgroup

例 1：在 y^2=(x^3-x+3) mod 37 中，总的点个数 N = 42，可能的 order n=1,2,3,6,7,14,21,42. 给定点 P=（2,3）,我们可以尝试计算 P,2P,3P,6P,7P, 一直到 7P=0，因此由 P 点作为基点的循环子群，其阶数(order of P) n=7

例 2: 在 Y^2=(x^3-x+1) mod 29 中，总的点个数 N = 37。 由于 N 是素数，其除数只有 1 和 37。当子群的 order n = 1 时，其中只能包含一个元素，即无穷远 0 点。当 n = 37 时，子群就是整个曲线点集合。

Finding a base point

寻找基点(生成元)。

对于椭圆曲线加密算法，我们希望基点生成的子群拥有尽量多的个数，即 order 越大越好。因此我们会先算出椭圆曲线的点个数 N，然后选择其最大的除数作为子群的元素个数 n，再去匹配符合要求的基点。

令 h = N/n , 由于 n 是 N 的除数，固也是整数。我们称 h 为子群的辅因子 cofactor of the subgroup。

由于 nP=0 (循环子群的特性)， 而 N 是 n 的倍数，即 N = nh, 我们可得出

n(hP)=0

假设 n 是素数，用 G 表示所求的基点，则 G=hP。方法总结如下：

1. 计算椭圆曲线的点个数 N
2. 选择子群的阶数 n， 满足 n 是素数，且必须是 N 的除数
3. 计算子群辅因子 cofactor h = N/n
4. 在曲线上随机选择一个点 P
5. 计算 G = hP
6. 如果 G 是无穷远 0 点，返回第 4 步；不为 0 点，则我们找到了一个子群的基点(生成元)，其阶数为 n，辅因子为 h。

请注意，此算法仅在 n 是素数时才有效。如果 n 不是素数，则 G 的阶数可能是 n 的除数之一。

Discrete logarithm

在循环子群内，当我们已知 P 和 Q 点，要如何求 P=kQ 中的 k 是多少呢？将循环子群看成一个圆形时钟，从 P 到 Q，实际上我们无法得知究竟转了多少圈。这个逆运算的问题被称为离散对数问题 discrete logarithm problem。

discrete logarithm problem 被认为是很困难的，这一特性同样被运用在其他加密算法中，例如 RSA, D-H。

所不同的是，ECC 使用更少位数的 k 就能达到相同安全级别。

Domain parameters

我们的椭圆曲线算法将在有限域上的椭圆曲线的循环子群中工作。因此，我们的算法将需要以下参数

• 素数 p 作为有限域的阶数.
• 系数 a 和 b 定义椭圆曲线 (y^2 = x^3 + ax +b).
• 循环子群的基点 G 作为生成元.
• 循环子群的阶数 n.
• 循环子群的辅因子 h.

Random curves

尽管椭圆曲线加密大部分是安全的，但仍有一些是比较弱的，会有安全隐患。如何才能保证一条椭圆曲线是安全的呢？

为了解决这个问题，我们使用种子 S 进行 hash 去生成系数 a, b, 或者基点 G，甚至全部用种子随机生成。

(A simple sketch of how a random curve is generated from a seed: the hash of a random number is used to calculate different parameters of the curve.)

(If we wanted to cheat and try to construct a seed from the domain parameters, we would have to solve a "hard" problem: hash inversion.)

参数由随机种子生成的曲线，称之为 verifiably random

Elliptic Curve Cryptography

定义公私钥对

1. private key 是从 [1, n-1] (n 是子群的阶数) 中选取的整数 d
2. public key 是点 H = dG (G 是子群的基点)

如果我们知道私钥 d 和 基点 G 找到公钥 H 0 是很容易的，但是反过来，已知 H 和 G，要找到私钥 d 是很困难的。

Encryption with ECDH

ECDH 是椭圆曲线 Diffie-Hellman 算法的变体。它实际上是一种密钥协商协议 key-agreement protocol，而不是一种加密算法。ECDH 定义了如何在各方之间生成和交换密钥。如何使用这些密钥实际加密数据取决于我们。

Alice 和 Bob 想要隐私且安全的交换信息，不被第三方看到内容：

1. Alice 和 Bob 创建各自的公私钥对。Alice 的私钥 dA 公钥 HA = dA*G，Bob 的是 dB 和 HB = dB * G。 两人使用同一条曲线的同一个有限域（系数和生成元相同）
2. Alice 和 Bob 互相交换公钥 HA 和 HB ，第三方可见公钥，但无法知道两人的私钥。
3. Alice 计算出消息 S = dA*HB , Bob 也计算出消息 S = dB*HA， 两人会得到相同的结果

原理在于两人用自己的私钥乘以对方的公钥，其结果都是 dA*dB*G , 但第三方只知道公钥，就无法得到信息。

现在 Alice 和 Bob 已经获得了共享秘密 S ，他们可以通过对称加密交换数据。

ECDH demo

Ephemeral ECDH

ECDHE 中的“E”代表“Ephemeral”，指的是交换的密钥是临时的，而不是静态的。 例如，在 TLS 中使用 ECDHE，在建立连接时，客户端和服务器都会即时生成它们的公钥-私钥对。然后使用 TLS 证书对密钥进行签名（用于身份验证）并在各方之间进行交换。

Signing with ECDSA

ECDH 不能体现所有权，即 Alice 签名的消息，只有 Bob 可以验证，第三方无法验证真伪。

ECDSA 可以实现这一场景，它是 DSA Digital Signature Algorithm 的一种变体。

ECSDA 处理消息的 hash 而不是消息本身，hash 函数由我们自己选择。hash 会被截断，与 n (子群的阶数)的位数相同，截断后的 hash 应是一个整数，用 z 表示。

Alice 为消息签名所执行的算法如下：

1. 从 [1, n-1] (n 是子群的阶数) 中选取随机的整数 k
2. 计算点 P=kG (G 是子群的基点)
3. 计算 r = xP mod n (xP 是 P 点横坐标)
4. 如果 r 是 0，返回第 1 步
5. 计算 s = k^-1(z + r*dA) mod n (dA 是 Alice 的私钥, k^-1 是 k 在 k mod n 中的乘法逆元)
6. 如果 s 是 0，返回第 1 步

最终 (r, s) 对就是签名

Alice 使用她的私钥 dA 和随机 k 对哈希 z 进行签名。 Bob 使用 Alice 的公钥 HA 验证消息是否已正确签名。

再次强调，n 需要是素数，否则无法求 k^-1。

Verifying signatures

为了验证签名，我们需要 Alice 的公钥 HA、（截断的）hash z，还有签名 (r,s)。

1. 计算整数 u1 = s^-1 * z mod n
2. 计算整数 u2 = s^-1 * r mod n
3. 计算点 P = u1*G + u2*HA

当 r == xP mod n 时，签名有效。

Correctness of the algorithm

算法的逻辑看起来不明显

P = u1*G + u2*HA

公钥的定义是 HA=dA*G (dA 是私钥)

$$P = u1*G + u2*HA = u1*G + u2*dA*G = (u1 + u2*dA)*G$$

再将u1 和u2 的定义代入

$$P = (u1 + u2*dA)*G = (s^-1*z + s^-1*r*dA)*G = s^-1(z + r*dA)*G$$

这里我们为了简洁省略了“mod n”，并且因为 G 生成的循环子群具有 n 阶，因此“mod n”是多余的。

之前我们定义了 s = k^-1(z + r*dA) mod n， 两边乘以 k 再除以 s 则

k = s^-1(z + r*dA) mod n

代入 P 的表达式

$$P = s^-1(z + r*dA)*G = k*G$$

这与签名时第2步相同，即如果 xP mod n 与 r 相同，则说明签名有效。

Playing with ECDSA

a Python script for signature generation and verification

The importance of k

在生成 ECDSA 签名时，将秘密 k 保密很重要。如果我们对所有签名使用相同的 k，或者如果我们的随机数生成器在某种程度上是可预测的，那么攻击者将能够找到私钥！

著名的 PlayStation 3 事故 This is the kind of mistake made by Sony a few years ago。索尼的ECDSA签名算法使用的时静态的 k，即每次的k值都相同，导致攻击者很容易就能破解私钥。

攻击者只需要购买两个游戏，然后提取他们的 hash (z1, z2) 和 签名 (r1,s1),(r2,s2)

1. 首先 r1 = r2 ,因为 r = xP mod n , P = kG ,如果k值不变， r也不会变
2. (s1 - s2) mod n = k^-1(z1 - z2) mod n
3. 两边同时乘以 k ， k(s1 - s2) mod n = (z1 - z2) mod n
4. k = (z1 - z2)(s1 - s2)^-1 mod n

最后通过k计算私钥 dS

s = k^-1 (z + r*dS) mod n

dS = r^-1 (s*k - z) mod n

其他 ECDSA 实现

• ecc-secp256k1.py
• elliptic.py

mac m1 芯片可能无法安装 fastecdsa , 可以使用下列命令安装，详见 Cannot install in macOS BigSur (M1 chip)

CFLAGS=-I/opt/homebrew/opt/gmp/include LDFLAGS=-L/opt/homebrew/opt/gmp/lib python3 -m pip install --no-binary :all: --no-use-pep517 fastecdsa

参考

• Elliptic Curve Cryptography: a gentle introduction
• Elliptic Curve Cryptography: finite fields and discrete logarithms
• Elliptic Curve Cryptography: ECDH and ECDSA
• Elliptic Curve Cryptography: breaking security and a comparison with RSA
• github andreacorbellini/ecc
• ecdsa-math
• https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3
• https://www.youtube.com/watch?v=iB3HcPgm_FI
• https://github.com/wobine/blackboard101/blob/master/EllipticCurvesPart4-PrivateKeyToPublicKey.py
• https://eng.paxos.com/blockchain-101-foundational-math
• https://eng.paxos.com/blockchain-101-elliptic-curve-cryptography