pub[i][j] = h(seed, i, j) # i in {0,1}, j in {0, ..., 255}
总共生成 2 * 256 = 512 个公钥值
对于需要签名的 256 位消息摘要 01101110..., 按位检查每个比特位:
如果比特位为 0, 则使用 pub[0][j] 作为签名的一部分
如果比特位为 1, 则使用 pub[1][j] 作为签名的一部分
将所有 256 个公钥值作为签名输出
接收方使用公钥种子 seed 重新计算出所有 512 个公钥值
对于收到的签名, 按位检查每个比特位:
如果比特位为 0, 则检查对应的 pub[0][j] 是否与签名中的值匹配
如果比特位为 1, 则检查对应的 pub[1][j] 是否与签名中的值匹配
如果所有比特位的验证都通过, 则认为签名有效
这种方法可以扩展，只要尚未揭露私钥。我们可以生成很多组公钥用于签名。
如果要签名四次，那么一共要生成 64 KB 的公钥。 随着签名次数的增大，需要在本地存储线性级别增长的公钥。并且对于每个验证者，都需要向他出示之前生成过的所有公钥。
解决方法是 Merkle 树。
一种未在加密货币领域使用的对称加密算法。
支持盲签名（即在内容不揭露的情况下签名），过程如下：
$m' = m + r$ 对原始消息 添加一个随机数得到一个新的消息 。对消息进行随机化的方法,目的是为了提高签名的安全性。
$\mathrm{sig} (m') = s'$ 对修改后的消息进行签名,得到签名值 。签名算法可以是 RSA 签名、ECDSA 签名等。
$s = s' - r$ 通过减去之前添加的随机数 ,得到最终的签名值 。
这样做的目的是为了保证签名值 $s$ 与原始消息 $m$ 的签名一致,即 $\mathrm{sig}(m) = s$。
这个过程中，签名的人不会知道它签的原始消息是什么。
RSA 算法的 setup 步骤如下:
选择两个大素数 $p$ 和 $q$。
计算 $n = p \times q$。素数性质保证很难找到 $n$ 的 preimage。
计算 $\phi(n) = (p-1)(q-1)$, 其中 $\phi(n)$ 是 Euler 函数。
选择一个整数 $e$, 使得 $1 < e < \phi(n)$ 且 $\gcd(e, \phi(n)) = 1$。通常选择 $e = 65537$，或者 $3$。这个数可以公开。
计算 $d$ 使得 $d \times e \equiv 1 \pmod{\phi(n)}$。这可以通过扩展欧几里得算法来实现。或者写作 $d=e^{-1} \bmod (p-1) \times(q-1)$
此时,公钥为 $(e, n)$,私钥为 $(d, n)$. $p, q$ 可以丢掉。
在 RSA 算法中,签名和验证的过程如下:
使用私钥 $(d, n)$ 对消息 $m$ 进行签名:
s = m^d \mod n
其中 $s$ 就是签名结果。
使用公钥 $(e, n)$ 对签名 $s$ 进行验证:
m' = s^e \mod n
比较 $m'$ 和原始消息 $m$ 是否相等。如果相等,则说明签名有效,否则签名无效。
具体步骤如下:
发送者使用自己的私钥对消息 $m$ 进行签名,得到签名 $s$。
接收者使用发送者的公钥对签名 $s$ 进行验证,得到 $m'$。
如果 $m' = m$,则说明签名有效,消息未被篡改。
这样可以确保消息的完整性和来源的真实性。
Bitcoin 使用 $y^2=x^3+7$，在曲线上画一条割线，交于 $P,Q,-R$，满足 $P+Q-R=0$，则 $-R$ 的对称点满足 $R=P+Q$
实际计算时，计算机处理的是模运算，保持了一些性质，但曲线不会像上面这么好看。
椭圆曲线上的点运算
在椭圆曲线上,有三种基本的点运算:
点加法 (Point Addition):
给定两个不同的点 $P(x_1, y_1)$ 和 $Q(x_2, y_2)$,计算它们的和 $R = P + Q$。
计算方法是:
计算斜率 $\lambda = (y_2 - y_1) / (x_2 - x_1)$
计算 $x_R = \lambda^2 - x_1 - x_2$
计算 $y_R = \lambda(x_1 - x_R) - y_1$
点加法 ($P + Q$): 对于曲线上的两个点 $P$ 和 $Q$,作过这两点的直线与曲线的第三个交点,然后以这个交点关于 $x$ 轴对称的点作为 $P + Q$ 的结果。
点倍乘 ($k \cdot P$): 对于曲线上的一个点 $P$,作过 $P$ 的切线与曲线的第二个交点,然后以这个交点关于 $x$ 轴对称的点作为 $2 \cdot P$ 的结果。重复这一过程 $k$ 次,即可得到 $k \cdot P$ 的结果。
点相反 ($-P$): 对于曲线上的一个点 $P$,以 $P$ 关于 $x$ 轴对称的点作为 $-P$ 的结果。
椭圆曲线中点的加法满足交换律，即 $aB = bA$。
推导如下：由于加法满足交换律，所以有 $aB = a(bG) = (ab)G = b(aG) = bA$。因此，无论先将 $G$ 点乘以 $a$ 再乘以 $b$，还是先乘以 $b$ 再乘以 $a$，结果都是相同的。
随机生成一个大整数 $a$,作为用户的私钥。
一般选择一个 256 位的标量。
计算公钥 $A = a \cdot G$,其中 $G$ 是椭圆曲线 $y^2 = x^3 + 7$ 上的随机选取的基点（生成点，Generator Point）。
$x_{A},y_{A}$ 都是 32 bytes 整数，因此一共需要 64 bytes 空间存储公钥。
考虑到曲线是关于 $x$ 轴对称的，可以压缩到 33 bytes, 其中一个 byte 用来指示是在正半轴还是负半轴。
因此只需要判断 $R == sG + h(m,R)A$
所以验证等式其实就是签名等式乘以基点 $G$ 得到的。签名过程只有持有私钥 $a$ 的签名者才能完成,而任何人都可以用公钥 $A$ 进行验证。
考虑 $A=aG, B=bG, aB = bA = C$，$C$ 称为 Diffie Hellman 密钥交换点。我们可以用 $C$ 作为共享的公共密钥，在信道中不会传输 $C$，而是各自通过公开信息计算出来（比如对于 A 方而言，通过 $bA$ 来计算），因此可以加密内容并安全地交换。
在 ECC 中，可以将两个密钥组合成一个新的密钥（Key Combination）。
设 $G$ 为椭圆曲线上的一个生成元（Generator），$a$ 和 $b$ 为两个整数。我们可以计算出两个点：
\begin{aligned}
A &= aG \\
B &= bG
\end{aligned}
根据椭圆曲线上点的加法规则，我们可以将这两个点相加，得到一个新的点 $D$：
D = A + B = (a+b)G
这里的 $a+b$ 实际上是在有限域上进行模加法运算。
多方签名：假设 Alice 和 Bob 分别持有私钥 $a$ 和 $b$，他们可以各自计算出 $A=aG$ 和 $B=bG$，然后将这两个公钥相加得到组合公钥 $D$。当需要签名时，Alice 和 Bob 分别使用自己的私钥对消息进行签名，然后将两个签名相加，得到最终的组合签名。验证者可以使用组合公钥 $D$ 来验证这个签名的有效性。
密钥托管：用户可以将自己的私钥分成两部分 $a$ 和 $b$，分别托管给两个不同的机构。当需要使用私钥时，用户可以从两个机构分别获得 $aG$ 和 $bG$，然后自己相加得到完整的公钥 $D$。这样可以提高私钥的安全性，防止单点失败。
1. Signatures, Hashing, Hash Chains, e-cash, and Motivation - YouTube
