Ed25519 曲线

标量、点，以及整个门罗币所依赖的那一个运算

为什么用曲线

我们需要一个“带锁的单向函数”：从秘密很容易得到公开的东西，但反过来不行。同时我们还希望能对公开的东西做算术：把它们相加，或乘以某个数。椭圆曲线恰好提供了这些。

门罗币使用的曲线与 Ed25519 签名（Daniel J. Bernstein 等人）相同：一条扭曲 Edwards 曲线

一个点就是满足这个方程的一对数 (x, y)。所有计算都对素数 p 取模，所以这条“曲线”实际上是由大约 2²⁵⁵ 个离散点组成的一团点云。

点的加法

点可以相加：P + Q = R，其中 R 也在曲线上。在 Edwards 曲线上，一个公式就能涵盖所有情况（既方便又安全）：

这种加法的行为与普通加法相似：满足交换律和结合律，有一个“零”——点 (0, 1)——并且每个点都有一个相反点 (−x, y)。

乘以一个数

把一个点乘以 x，就是把它与自身相加 x 次。当然没有人会真的加 2²⁵² 次：“倍加-相加”（double-and-add）方法只需约 256 次倍加和约 128 次加法。

基点 G 与阶 l

所有人都使用同一个事先约定的基点 G。把 G 依次乘以 1、2、3……经过 l 步后又回到零：

l 是由 G 生成的子群的阶。曲线上的点总数是它的 8 倍（8·l）；8 被称为余因子。这个余因子是门罗币中几处微妙问题的根源：你会在一次性地址的公式中看到因子 8，而在 2017 年，“小阶点”曾可能让一个输出产生多个 key image（通过检查 l·I = 0 修复）。

为什么这适用于密钥

取一个随机数 x——这就是私钥。计算 P = x·G——这就是公钥。公开 P 是安全的。关键在于，点支持代数运算：

第二个恒等式是 Diffie–Hellman 密钥交换的基础：Alice 知道 a 并看到 B = b·G；Bob 知道 b 并看到 A = a·G。两人都能算出同一个点 a·B = b·A = ab·G，而外人却不能。一次性地址就建立在这一点之上。

第一个恒等式是 Pedersen 承诺的基础：隐藏在点中的金额可以相加。

用 32 字节编码一个点

点以紧凑的方式存储：写下 y 坐标（255 位，小端序），再把 x 的奇偶性放在最后一个字节的最高位。x 可以通过曲线方程由 y 恢复（只差一个正负号——由那个比特给出）。你查看门罗币公钥时看到的十六进制 32 字节就是这样来的。

例如，基点 G 写作：

5866666666666666666666666666666666666666666666666666666666666666

（它的 y = 4/5 mod p，且 x 为偶数）。

代码

一个使用 BigInt 的最小 JavaScript 实现——摘自 xmrcrypto.js，本站的所有工具都在使用它：

const P = (1n << 255n) - 19n;
const L = (1n << 252n) + 27742317777372353535851937790883648493n;
const D = mod(-121665n * inv(121666n));

// points in extended coordinates (X:Y:Z:T), x = X/Z, y = Y/Z
function add(p, q) {
  const A = mod((p.Y - p.X) * (q.Y - q.X));
  const B = mod((p.Y + p.X) * (q.Y + q.X));
  const C = mod(2n * D * p.T * q.T);
  const Dd = mod(2n * p.Z * q.Z);
  const E = B - A, F = Dd - C, G = Dd + C, H = B + A;
  return { X: mod(E * F), Y: mod(G * H), Z: mod(F * G), T: mod(E * H) };
}

// scalar multiplication: double-and-add
function mul(k, p) {
  let r = ZERO, q = p;
  while (k > 0n) { if (k & 1n) r = add(r, q); q = add(q, q); k >>= 1n; }
  return r;
}