一、编写目的

二、算法流程图

三、步骤分析

1.公钥生成

Welcome to Code Block's blog

本篇文章主要介绍了

[加密算法:深度解析Ed25519加密]

❤博主广交技术好友，喜欢文章的可以关注一下❤

一、编写目的

在 Solana 开发过程中，我一直对 Ed25519 加密算法 如何生成公钥、签名以及验证签名的机制感到困惑。为了弄清这一点，我查阅了大量相关资料，终于对其流程有了更清晰的理解。在此记录实现过程，方便日后查阅。

二、算法流程图

编辑

通过官网上的算法流程图可以看到,其中有几个部分是彩色的,其解释如下:

seed(k):随机的32bytes的值.该值为加密核心值,也是组成私钥的左半部分.
pubkey(A):公钥.作为用户的地址,在ed25519加密算法中作为私钥右半部分.
msg(M):需要被签名的消息.
R:组成签名的左半部分,为签名随机值.
S:组成签名的右半部分,为签名验证数据.

三、步骤分析

1.公钥生成

def publickey(sk):
    """
    生成给定私钥的公钥。
    参数:
    sk (bytes): 私钥，字节序列。
    返回:
    bytes: 公钥，字节序列。
    该函数首先计算私钥的哈希值，然后根据哈希值生成一个标量 a。
    使用标量 a 和基点 B 进行标量乘法运算，得到点 A。
    最后将点 A 编码为字节序列并返回。
    注意:
    - 函数依赖于外部定义的 H、bit、scalarmult、B 和 encodepoint 函数或变量。
    - b 是一个全局变量，表示位数。
    """
    h = H(sk)
    a = 2 ** (b - 2) + sum(2 ** i * bit(h, i) for i in range(3, b - 2))
    print(a)
    A = scalarmult(B, a)
    print(A)
    return encodepoint(A)

Sha512

当随机seek值(32 bytes)生成后,将seek值通过Hash算法sha512转换其为hash值(64 bytes).

sk派生a

通过下述派生公式,生成一个派生的随机值:

这里说是随机值,但因为是规定的派生方法,所以seek值不变的情况下,a的值也不会发生改变.

这也是为什么私钥不变生成的公钥不变.

计算曲线点(scalarmult(B, a))

通过固定的基点B,将a作为标量值,进行累加的标量乘法运算,其得出的值为椭圆曲线上的一个点.即solana公钥为椭圆曲线上的点.

编码为公钥(encodepoint(A))

将生成的椭圆上的点,通过遍历的方式将其转换为32 bytes的值,该值作为公钥,同时也是私钥的右半部分.

测试:

import os
from ed255191 import publickey
import base58
seed = os.urandom(32)
# 计算 Ed25519 公钥
pk = publickey(seed)
# Solana 私钥 = 种子（32 字节） + 公钥（32 字节）
solana_secret_key = seed + pk
# 以base58打印密钥
print("Public Key 32 bytes:", base58.b58encode(pk))
print("Solana Private Key 64 bytes:", base58.b58encode(solana_secret_key))

输出:

Public Key 32 bytes: b'8Y4MaxUyeTrXFsDGtAAoqHvuZNKNGgd43KaYtyQ29wdq'
Solana Private Key 64 bytes: b'53eadFesuqNF1PMW4cd6PTrrmYaPJAUc19upagtRQfiYLQfTRDKSgbBFcShEHM9qghrmo1SuKFoJbzeqLaGNyczT'

输出上述内容,可以直接在solana作为公私钥地址使用.

2.消息签名

def signature(m, sk, pk):
    """
    生成Ed25519签名。
    参数:
    m (bytes): 要签名的消息。
    sk (bytes): 私钥。
    pk (bytes): 公钥。
    返回:
    bytes: 签名，由 R 和 S 组成。
    过程:
    1. 计算私钥哈希 h。
    2. 从 h 中提取部分位生成私钥 a。
    3. 使用 h 的一部分和消息 m 生成随机数 r。
    4. 计算随机点 R = r * B。
    5. 计算哈希值 c = Hint(encodepoint(R) + pk + m)。
    6. 计算签名 S = (r + c * a) % l。
    7. 返回签名 encodepoint(R) + encodeint(S)。
    注意:
    - r 对于每条不同的消息 m 都是不同的，确保签名的唯一性。
    - S 包含了随机数 r 和私钥 a 的隐藏计算，保证签名的安全性。
    """
    h = H(sk)
    a = 2 ** (b - 2) + sum(2 ** i * bit(h, i) for i in range(3, b - 2))
    #取 h 的部分（h[b // 8 : b // 4]）作为一个随机种子 结合m 生成hash值
    #这样 r 对于每条不同的 m 都是不同的，确保签名的唯一性。
    r = Hint(h[b // 8 : b // 4] + m)
    #随机值生成随机点
    R = scalarmult(B, r)
    #计算 c = Hint(encodepoint(R) + pk + m)，即对 R、公钥 pk 和消息 m 进行哈希。
    #计算 S = (r + c * a) % l，这里：
    #       c * a 相当于用私钥 a 进行了一次隐藏的计算。
    #       r 作为随机数，确保 S 是不可预测的。
    #       mod l 使得 S 处于有限域 l 内，保证安全性。
    S = (r + Hint(encodepoint(R) + pk + m) * a) % l
    return encodepoint(R) + encodeint(S)

sha512和派生a

这里使用与公钥生成时同样的算法对h和a进行计算.

生成随机值R

通过h(seek的32位bytes)后32为与r进行相加,通过Hint方法计算哈希值的位的加权和。再通过标量乘法计算R.(32 bytes) 然后根据Schnorr 签名公式(该公式保证了该签名可被验证):

mod l

计算出S.R和S共同组成了签名消息.

R 对于每条不同的消息 m 都是不同的，确保签名的唯一性。
S 包含了随机数 r 和私钥 a 的隐藏计算，保证签名的安全性。

测试:

sign=signature(b"123",seed,pk)
print("signature the 123:",base58.b58encode(sign))

输出:

R: [6324733128348069932552712847458797216869310762106586087538471940014706165507, 28062308455787357155134324845859090190481803788753592421647963767216412318834]
S: 5332744685477174614042576231653933898918923940183121946240407635890135823280
signature the 123: b'3HcZN9B8WExQdTqiFPEZUGndqVgtrJhwNoCwMm7wHCq2K5wxrWpdJXgMFBgkimA4r1nKqCpekurwstkimY6au9Dc'

3.签名验证

def checkvalid(s, m, pk) -> bool:
    """
    验证给定的签名是否有效。
    参数:
    s (bytes): 签名，长度应为 b // 4。
    m (bytes): 消息。
    pk (bytes): 公钥，长度应为 b // 8。
    返回:
    bool: 如果签名有效，返回 True；否则抛出异常。
    异常:
    Exception: 当签名长度或公钥长度不正确时抛出。
    Exception: 当签名验证失败时抛出。
    """
    if len(s) != b // 4:
        raise Exception("Signature length is wrong")
    if len(pk) != b // 8:
        raise Exception("Public-key length is wrong")
    #----------------签名的前半部分和后半部分--------------------------
    R = decodepoint(s[: b // 8])  # s取前32位 (反向计算随机点)
    S = decodeint(s[b // 8 : b // 4]) # s取32到64位
    #-----------------公钥和挑战值-----------------------------------
    A = decodepoint(pk)           # pk为32位 (计算公钥点)
    c = Hint(encodepoint(R) + pk + m) # 计算挑战值
    #-----------------验证签名---------------------------------------
    #计算 c = Hint(encodepoint(R) + pk + m)，即对 R、公钥 pk 和消息 m 进行哈希。
    #计算 S = (r + c * a) % l，这里：
    #       c * a 相当于用私钥 a 进行了一次隐藏的计算。
    #       r 作为随机数，确保 S 是不可预测的。
    #       mod l 使得 S 处于有限域 l 内，保证安全性。
    #       S⋅B=R+c⋅A
    #       S=(r + Hint(encodepoint(R) + pk + m) * a) % l
    #       A=B*a
    #       S*B=B*r+c.B*a=B*(r+c*a)
    #       B*S=B*(r+c*a)
    #       B*r+B*a*c=B*(r+c*a)
    if scalarmult(B, S) != edwards(R, scalarmult(A, c)):
        raise Exception("Signature does not pass verification")
    return True

分割出R和S

因为签名时使用(R,S)组合进行签名,所有这边直接对字节进行操作,取签名s的前32 bytes即为R,后32位即为S.

计算A
在以知公钥的情况下计算A,使用decodepoint将其转换为在椭圆上的点.
计算h
这是签名里计算S时的一部分,该部分在验证签名值是已知的(因为A,pk,m都是已知参数).

然后使用下述公式对其进行对比验证:

测试:

valid=checkvalid(sign,b"123",pk)
print("valid:",valid)

输出:

valid: True

这里签名为什么可以被验证?

这里的签名为什么可以被验证,这里可以对公式进行做步骤推导:

在签名时R的计算公式为可以表示为:

在公钥生成时A的计算公式可以表示为:

将其带入公式后,原公式可表示为:

右边公式将提出后即可表示为:

这里即可得出在签名时使用的S为:

那S计算时还有个mod l为什么这里没有?

因为椭圆曲线上的点加法是基于有限域运算的，即使不显式地写 mod l，计算仍然在这个有限集合内进行.

四、源代码

import hashlib
b = 256  # 位数
q = 2**255 - 19  # 素数 q
l = 2**252 + 27742317777372353535851937790883648493  # 素数 l
# 哈希函数，使用 SHA-512
def H(m):
    """
    计算给定消息的SHA-512哈希值。
    参数:
    m (bytes): 要进行哈希计算的消息。
    返回:
    bytes: 消息的SHA-512哈希值。
    """
    return hashlib.sha512(m).digest()
# 模幂运算，计算 (b^e) % m
def expmod(b, e, m):
    """
    计算 (b^e) % m 的值，使用递归的快速幂算法。
    参数:
    b (int): 底数
    e (int): 指数
    m (int): 模数
    返回:
    int: (b^e) % m 的结果
    示例:
    >>> expmod(2, 10, 1000)
    24
    如果 e == 0，返回 1。
    否则，递归地计算 expmod(b, e // 2, m) 的平方并取模 m。
    如果 e 是奇数，再乘以 b 并取模 m。
    """
    if e == 0:
        return 1
    t = expmod(b, e // 2, m) ** 2 % m  # 使用 `//` 确保 `e` 是整数
    if e & 1:
        t = (t * b) % m
    return t
# 计算 x 的逆元，满足 (x * inv(x)) % q == 1
def inv(x):
    """
    计算给定数值 x 在模 q 下的乘法逆元。
    这是通过使用费马小定理实现的，该定理指出，对于一个素数 q 和一个整数 x，
    x^(q-1) ≡ 1 (mod q)。因此，x^(q-2) ≡ x^(-1) (mod q)。
    参数:
    x (int): 需要计算逆元的整数。
    返回:
    int: x 在模 q 下的乘法逆元。
    """
    return expmod(x, q - 2, q)
d = -121665 * inv(121666)  # 常数 d
I = expmod(2, (q - 1) // 4, q)  # 常数 I
# 根据 y 坐标恢复 x 坐标
def xrecover(y):
    """
    根据给定的 y 值恢复 x 坐标。
    该函数用于从给定的 y 坐标恢复 x 坐标，适用于椭圆曲线密码学中的 Ed25519 算法。
    参数:
    y (int): y 坐标值。
    返回:
    int: 恢复的 x 坐标值。
    注意:
    - 该函数假设存在全局变量 d 和 q，它们分别是 Ed25519 曲线的常数。
    - inv 函数用于计算模逆。
    - expmod 函数用于计算模幂。
    - I 是虚数单位的平方根。
    """
    xx = (y * y - 1) * inv(d * y * y + 1)
    x = expmod(xx, (q + 3) // 8, q)
    if (x * x - xx) % q != 0:
        x = (x * I) % q
    if x % 2 != 0:
        x = q - x
    return x
By = 4 * inv(5)  # 基点 B 的 y 坐标
Bx = xrecover(By)  # 基点 B 的 x 坐标
B = [Bx % q, By % q]  # 基点 B
# 爱德华兹曲线上的点加法
def edwards(P, Q):
    """
    计算爱德华曲线上的点加法。
    参数:
    P (tuple): 第一个点 (x1, y1)。
    Q (tuple): 第二个点 (x2, y2)。
    返回:
    list: 结果点 (x3, y3)，其中 x3 和 y3 都是模 q 的结果。
    公式:
    注意:
    - inv 表示求逆运算。
    - d 是爱德华曲线的常数参数。
    - q 是模数。
    """
    x1, y1 = P
    x2, y2 = Q
    x3 = (x1 * y2 + x2 * y1) * inv(1 + d * x1 * x2 * y1 * y2)
    y3 = (y1 * y2 + x1 * x2) * inv(1 - d * x1 * x2 * y1 * y2)
    return [x3 % q, y3 % q]
# 标量乘法，计算 e * P
def scalarmult(P, e):
    """
    对给定的点 P 进行标量乘法运算，计算 e * P。
    参数:
    P (list): 椭圆曲线上的一个点，表示为 [x, y]。
    e (int): 标量值。
    返回:
    list: 结果点 Q，表示为 [x, y]。
    说明:
    该函数使用二进制方法进行标量乘法运算。初始化结果点 Q 为无穷远点 [0, 1]。
    在循环中，如果 e 的最低位为 1，则将当前点 P 累加到 Q 上。然后将 P 自加（倍点运算），
    并将 e 右移一位（除以 2）。循环结束后返回结果点 Q。
    """
    Q = [0, 1]  # 初始化为无穷远点
    while e > 0:
        if e & 1:
            Q = edwards(Q, P)  # 累加
        P = edwards(P, P)  # 自加（倍点运算）
        e //= 2
    return Q
# 将整数编码为字节
def encodeint(y):
    """
    将整数编码为字节序列。
    参数:
    y (int): 要编码的整数。
    返回:
    bytes: 编码后的字节序列。
    """
    bits = [(y >> i) & 1 for i in range(b)]
    return bytes([sum([bits[i * 8 + j] << j for j in range(8)]) for i in range(b//8)])
# 将点编码为字节
def encodepoint(P):
    """
    将给定的点P编码为字节序列。
    参数:
    P (tuple): 一个包含两个整数 (x, y) 的元组，表示点的坐标。
    返回:
    bytes: 编码后的字节序列。
    说明:
    该函数首先将y坐标的每一位提取出来，形成一个位列表，然后将x坐标的最低位添加到该列表的末尾。
    最后，将这些位打包成字节序列并返回。
    """
    x, y = P
    bits = [(y >> i) & 1 for i in range(b - 1)] + [x & 1]
    return bytes([sum([bits[i * 8 + j] << j for j in range(8)]) for i in range(b // 8)])
# 获取哈希值的第 i 位
def bit(h, i):
    """
    返回字节数组 `h` 中第 `i` 位的值（0 或 1）。
    参数:
    h (bytes): 字节数组。
    i (int): 要检查的位的索引。
    返回:
    int: 位的值（0 或 1）。
    """
    return (h[i // 8] >> (i % 8)) & 1  # 修正 `ord()`
# 生成公钥
def publickey(sk):
    """
    生成给定私钥的公钥。
    参数:
    sk (bytes): 私钥，字节序列。
    返回:
    bytes: 公钥，字节序列。
    该函数首先计算私钥的哈希值，然后根据哈希值生成一个标量 a。
    使用标量 a 和基点 B 进行标量乘法运算，得到点 A。
    最后将点 A 编码为字节序列并返回。
    注意:
    - 函数依赖于外部定义的 H、bit、scalarmult、B 和 encodepoint 函数或变量。
    - b 是一个全局变量，表示位数。
    """
    h = H(sk)
    a = 2 ** (b - 2) + sum(2 ** i * bit(h, i) for i in range(3, b - 2))
    print(a)
    A = scalarmult(B, a)
    print(A)
    return encodepoint(A)
# 计算消息的哈希值
def Hint(m):
    """
    计算消息 m 的哈希值，并返回哈希值的位的加权和。
    参数:
    m (str): 输入消息。
    返回:
    int: 哈希值的位的加权和。
    该函数首先计算消息 m 的哈希值 h，然后计算 h 的每个位的加权和。
    加权和的计算方式是将每个位乘以 2 的该位索引次方，然后求和。
    """
    h = H(m)
    return sum(2 ** i * bit(h, i) for i in range(2 * b))
# 生成签名
def signature(m, sk, pk):
    """
    生成Ed25519签名。
    参数:
    m (bytes): 要签名的消息。
    sk (bytes): 私钥。
    pk (bytes): 公钥。
    返回:
    bytes: 签名，由 R 和 S 组成。
    过程:
    1. 计算私钥哈希 h。
    2. 从 h 中提取部分位生成私钥 a。
    3. 使用 h 的一部分和消息 m 生成随机数 r。
    4. 计算随机点 R = r * B。
    5. 计算哈希值 c = Hint(encodepoint(R) + pk + m)。
    6. 计算签名 S = (r + c * a) % l。
    7. 返回签名 encodepoint(R) + encodeint(S)。
    注意:
    - r 对于每条不同的消息 m 都是不同的，确保签名的唯一性。
    - S 包含了随机数 r 和私钥 a 的隐藏计算，保证签名的安全性。
    """
    h = H(sk)
    a = 2 ** (b - 2) + sum(2 ** i * bit(h, i) for i in range(3, b - 2))
    #取 h 的部分（h[b // 8 : b // 4]）作为一个随机种子 结合m 生成hash值
    #这样 r 对于每条不同的 m 都是不同的，确保签名的唯一性。
    r = Hint(h[b // 8 : b // 4] + m)
    #随机值生成随机点
    R = scalarmult(B, r)
    #计算 c = Hint(encodepoint(R) + pk + m)，即对 R、公钥 pk 和消息 m 进行哈希。
    #计算 S = (r + c * a) % l，这里：
    #       c * a 相当于用私钥 a 进行了一次隐藏的计算。
    #       r 作为随机数，确保 S 是不可预测的。
    #       mod l 使得 S 处于有限域 l 内，保证安全性。
    S = (r + Hint(encodepoint(R) + pk + m) * a) % l
    print("R:",R)
    print("S:",S)
    return encodepoint(R) + encodeint(S)
# 检查点是否在曲线上
def isoncurve(P):
    """
    检查给定点 P 是否在曲线上。
    参数:
    P (tuple): 包含点的 x 和 y 坐标的元组。
    返回:
    bool: 如果点在曲线上则返回 True，否则返回 False。
    """
    x, y = P
    return (-x * x + y * y - 1 - d * x * x * y * y) % q == 0
# 将字节解码为整数
def decodeint(s):
    """
    解码整数
    该函数将字节串 `s` 解码为一个整数。它通过对每个字节的位进行加权求和来实现这一点。
    参数:
    s (bytes): 要解码的字节串
    返回:
    int: 解码后的整数
    """
    return sum(2**i * bit(s,i) for i in range(0,b))
# 将字节解码为点
def decodepoint(s):
    """
    解码给定的字节串以恢复椭圆曲线上的点。
    参数:
    s (bytes): 要解码的字节串。
    返回:
    list: 椭圆曲线上的点 [x, y]。
    异常:
    Exception: 如果解码的点不在曲线上，则抛出异常。
    """
    y = sum(2**i * bit(s,i) for i in range(0,b-1))
    x = xrecover(y)
    if x & 1 != bit(s,b-1): x = q-x
    P = [x,y]
    if not isoncurve(P): raise Exception("decoding point that is not on curve")
    return P
# 验证签名
def checkvalid(s, m, pk) -> bool:
    """
    验证给定的签名是否有效。
    参数:
    s (bytes): 签名，长度应为 b // 4。
    m (bytes): 消息。
    pk (bytes): 公钥，长度应为 b // 8。
    返回:
    bool: 如果签名有效，返回 True；否则抛出异常。
    异常:
    Exception: 当签名长度或公钥长度不正确时抛出。
    Exception: 当签名验证失败时抛出。
    """
    if len(s) != b // 4:
        raise Exception("Signature length is wrong")
    if len(pk) != b // 8:
        raise Exception("Public-key length is wrong")
    #----------------签名的前半部分和后半部分--------------------------
    R = decodepoint(s[: b // 8])  # s取前32位 (反向计算随机点)
    S = decodeint(s[b // 8 : b // 4]) # s取32到64位
    #-----------------公钥和挑战值-----------------------------------
    A = decodepoint(pk)           # pk为32位 (计算公钥点)
    h = Hint(encodepoint(R) + pk + m) # 计算挑战值
    #-----------------验证签名---------------------------------------
    #计算 c = Hint(encodepoint(R) + pk + m)，即对 R、公钥 pk 和消息 m 进行哈希。
    #计算 S = (r + c * a) % l，这里：
    #       c * a 相当于用私钥 a 进行了一次隐藏的计算。
    #       r 作为随机数，确保 S 是不可预测的。
    #       mod l 使得 S 处于有限域 l 内，保证安全性。
    #       S⋅B=R+c⋅A
    #       S=(r + Hint(encodepoint(R) + pk + m) * a) % l
    #       A=B*a
    #       S*B=B*r+c.B*a=B*(r+c*a)
    #       B*S=B*(r+c*a)
    #       B*r+B*a*c=B*(r+c*a)
    if scalarmult(B, S) != edwards(R, scalarmult(A, h)):
        raise Exception("Signature does not pass verification")
    return True