Cryptography/椭圆曲线 Ed25519 + Eddsa 签名

欢迎来到 ed25519 快速入门指南. 该指南将向您介绍 ed25519 的核心概念, 并且在此之前并不要求您具备多高深的密码学知识. Ed25519 是一条椭圆曲线, 它及其签名算法 eddsa 被 solana 用于其签名系统中. 与常见的公链对比如下:

	btc	ckb	sol
椭圆曲线	secp256k1	secp256k1	ed25519
签名算法	ecdsa & schnorr	ecdsa	eddsa

Ed25519 在 Solana 账户系统中的应用

私钥: ed25519 私钥, 32 byte 长度.
公钥: ed25519 公钥, 32 byte 长度.
地址: 公钥的 base58 表示.
钱包导入格式: 链接私钥 + 公钥, 并将结果进行 base64 编码.
钱包导出格式: 链接私钥 + 公钥, 并将结果进行 base58 编码 (哪个天才做出的这种设计).

试一试

有 solana 私钥 0000000000000000000000000000000000000000000000000000000000000001, 计算其公钥, 地址, 以及钱包导入格式. 要执行下面代码, 首先需要安装 pysol 依赖.

import base64
import sol

prikey = bytearray.fromhex('0000000000000000000000000000000000000000000000000000000000000001')
pubkey = sol.eddsa.pubkey(prikey)
print(pubkey.hex())
# 4cb5abf6ad79fbf5abbccafcc269d85cd2651ed4b885b5869f241aedf0a5ba29

addr = sol.base58.encode(pubkey)
print(addr)
# 6ASf5EcmmEHTgDJ4X4ZT5vT6iHVJBXPg5AN5YoTCpGWt

wif = base64.b64encode(prikey + pubkey).decode()
print(wif)
# AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFMtav2rXn79au8yvzCadhc0mUe1LiFtYafJBrt8KW6KQ==

我们可以在solana 浏览器中查询该地址, 惊奇的发现这个地址里面有钱! 于是, 可以便可以使用 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAFMtav2rXn79au8yvzCadhc0mUe1LiFtYafJBrt8KW6KQ== 在 solana 钱包中导入这个账号, 这样我们就拥有了该账号的所有权. 话虽如此, 但此账号余额过少, 无法完成一次转账交易.

Ed25519 的命名

Ed25519 是椭圆曲线中的一种. 目前, 大家普遍认为 ed25519 各方面都要优于 secp256k1 曲线. 这条曲线的命名非常有趣. 通常, 描述一个特定的椭圆曲线需明确六个参数: P, A, B, G, N, H. 其中 P 是一个大素数, N 是该椭圆曲线的阶. 对于 ed25519, 有:

P = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed # 2**255 - 19
N = 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed

其 P 与 N 两个常数的十六进制表示都以 ed 结尾, 且 P 等于 2**255 - 19, 这就是其 ed25519 名字的来源.

什么是阶?
在群论这一数学的分支里, 阶这一词被使用在两个相关连的意义上: - 一个群的阶是指其势, 即其元素的个数; - 一个群内的一个元素 a 之阶(有时称为周期)是指会使得 aᵐ = e 的最小正整数 m(其中的 e 为这个群的单位元素, 且 aᵐ 为 a 的 m 次幂). 若没有此数存在, 则称 a 有无限阶. 有限群的所有元素都有有限阶.

Ed25519 的优点

与 secp256k1 + ecdsa 相比, ed25519 + eddsa 优势有如下.

Secp256k1 私钥范围是 [0, 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141), 而 ed25519 则是 [0, 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff], 使用了 32 byte 能表示的所有空间.
Secp256k1 公钥的非压缩表示是 64 byte, 压缩表示是 33 byte, 而 ed25519 公钥只有 32 byte. 更短的长度意味着可以直接使用公钥表示地址, 而不是使用公钥的哈希. 同时它具有一些隐藏的好处:
- 在 golang 里, 由于 32 是 2 的指数形式, 32 长度的切片比起 33 来讲, 多数情况下具有更高的内存分配效率. 这是由 golang 切片的自动扩容机制决定的.
- 在 rust 里, 只为小于等于 32 长度的数组实现了 clone 和 copy.
- 在 c/c++/asm 中, 复制 32 长度的 byte 数组和 33 长度的 byte 数组, 其效率最高可能相差数倍. 这是因为 memcpy() 对于不同长度的数组并不是一视同仁的.
  - 在 linux x86 boot 代码中, 采用的是一次复制 4 个 byte 的方式: https://github.com/torvalds/linux/blob/master/arch/x86/boot/copy.S#L18-L32, 因此 32 长度的 byte 数组需要搬运 8 次, 33 长度则是 9 次.
  - 在 glibc 的 aarch64 代码中, 小于等于 32 byte 的数组拷贝被称之为 small copy, 使用了一个快速算法. https://github.com/bminor/glibc/blob/master/sysdeps/aarch64/memcpy.S
- ... ...
Ed25519 签名时避免使用分支条件, 以减轻旁路攻击. 所谓旁路攻击, 是指通过分析程序的时间信息, 功率消耗, 电磁泄露或甚是声音获取额外的信息来源, 用于对系统的进一步破解.

简单比较下 secp256k1 和 ed25519 椭圆曲线上的点加操作:

# Secp256k1
def __add__(self, data: Self) -> Self:
    # https://www.cs.miami.edu/home/burt/learning/Csc609.142/ecdsa-cert.pdf
    # Don Johnson, Alfred Menezes and Scott Vanstone, The Elliptic Curve Digital Signature Algorithm (ECDSA)
    # 4.1 Elliptic Curves Over Fp
    if self.x == Fq(0) and self.y == Fq(0):
        return data
    if data.x == Fq(0) and data.y == Fq(0):
        return self
    if self.x == data.x and self.y == -data.y:
        return I
    x1, x2 = self.x, data.x
    y1, y2 = self.y, data.y
    if self.y == data.y:
        s = (x1 * x1 + x1 * x1 + x1 * x1 + A) / (y1 + y1)
    else:
        s = (y2 - y1) / (x2 - x1)
    x3 = s * s - x1 - x2
    y3 = s * (x1 - x3) - y1
    return Pt(x3, y3)

# Ed25519
def __add__(self, data: Self) -> Self:
    # https://datatracker.ietf.org/doc/html/rfc8032#ref-CURVE25519
    # Points on the curve form a group under addition, (x3, y3) = (x1, y1) + (x2, y2), with the formulas
    #           x1 * y2 + x2 * y1                y1 * y2 - a * x1 * x2
    # x3 = --------------------------,   y3 = ---------------------------
    #       1 + d * x1 * x2 * y1 * y2          1 - d * x1 * x2 * y1 * y2
    x1, x2 = self.x, data.x
    y1, y2 = self.y, data.y
    x3 = (x1 * y2 + x2 * y1) / (Fq(1) + D * x1 * x2 * y1 * y2)
    y3 = (y1 * y2 - A * x1 * x2) / (Fq(1) - D * x1 * x2 * y1 * y2)
    return Pt(x3, y3)

简单比较下 secp256k1 和 ed25519 签名操作:

# Secp256k1
def sign(prikey: btc.secp256k1.Fr, m: btc.secp256k1.Fr) -> typing.Tuple[btc.secp256k1.Fr, btc.secp256k1.Fr, int]:
    # https://www.secg.org/sec1-v2.pdf
    # 4.1.3 Signing Operation
    for _ in itertools.repeat(0):
        k = btc.secp256k1.Fr(random.randint(0, btc.secp256k1.N - 1))
        R = btc.secp256k1.G * k
        r = btc.secp256k1.Fr(R.x.x)
        if r.x == 0:
            continue
        s = (m + prikey * r) / k
        if s.x == 0:
            continue
        v = 0
        if R.y.x & 1 == 1:
            v |= 1
        if R.x.x >= btc.secp256k1.N:
            v |= 2
        return r, s, v

# Ed25519
def sign(prikey: bytearray, m: bytearray) -> bytearray:
    # The inputs to the signing procedure is the private key, a 32-octet string, and a message M of arbitrary size.
    # See https://datatracker.ietf.org/doc/html/rfc8032#section-5.1.6
    assert len(prikey) == 32
    h = hash(prikey)
    a = int.from_bytes(h[:32], 'little')
    a &= (1 << 254) - 8
    a |= (1 << 254)
    a = sol.ed25519.Fr(a)
    prefix = h[32:]
    A = pt_encode(sol.ed25519.G * a)
    r = sol.ed25519.Fr(int.from_bytes(hash(prefix + m), 'little'))
    R = sol.ed25519.G * r
    Rs = pt_encode(R)
    h = sol.ed25519.Fr(int.from_bytes(hash(Rs + A + m), 'little'))
    s = r + h * a
    return Rs + bytearray(s.x.to_bytes(32, 'little'))

签名过程不依赖随机数. Secp256k1 发生过一起非常严重的安全事件, Sony PlayStation 3 的固件更新服务因在每次签名时使用了相同的随机数, 导致其私钥泄露. Ed25519 则不存在此问题. 如果您想复刻该攻击, 可以参考 Cryptography/椭圆曲线 ECDSA 签名的错误用法.

Cryptography/椭圆曲线 Ed25519 + Eddsa 签名

Ed25519 在 Solana 账户系统中的应用

Ed25519 的命名

Ed25519 的优点

Ed25519 的代码实现

参考