第 2 章：门限签名所需的数学基础

学习定位：前置为导读与实验 0；配套完成实验 1：玩具有限域。本章产物是能手算并实现有限域、群和拉格朗日插值。

门限签名的公式通常不长，真正容易出错的是：一个数属于哪个集合、一次运算在哪个集合里完成。本章不会试图压缩一门完整的抽象代数课程，而是建立后续实现所需的“数学类型系统”。

本手册中的算法用于学习。即使测试全部通过，也不代表实现已经具备抵抗侧信道、恶意参与者或真实网络攻击的能力。

学习目标

完成本章后，你应该能够：

熟练进行模加、模乘、求逆和模除法；
解释有限域、循环群、生成元和群阶；
区分椭圆曲线的基域与签名算法使用的标量域；
判断一个公式两边的数学类型是否一致；
用拉格朗日插值恢复多项式在零点的值；
理解离散对数困难性为何能保护公钥对应的私钥。

2.1 先建立一张符号表

不同论文经常复用同一个字母。为了减少歧义，本手册采用以下约定：

符号	含义	类型
\(p\)	椭圆曲线坐标所在基域的模数	素数
\(q\)	所用素数阶子群的阶	素数
\(\mathbb F_p\)	椭圆曲线坐标使用的有限域	域
\(\mathbb Z_q\)	私钥、nonce、挑战值和签名响应所在的标量域	域
\(\mathbb G\)	阶为 \(q\) 的加法循环群	群
\(G\)	\(\mathbb G\) 的生成元	群元素（点）
\(x,r,c,z\)	私钥、nonce、挑战、响应	标量，属于 \(\mathbb Z_q\)
\(X,R\)	公钥、nonce 承诺	群元素，属于 \(\mathbb G\)
\(m\)	待签名消息	字节串

从实现角度看，最好把它们想象成完全不同的 Rust 类型：

Scalar + Scalar -> Scalar
Scalar * Point  -> Point
Point  + Point  -> Point
Hash(bytes)     -> bytes
HashToScalar(bytes) -> Scalar

下面这些表达式则没有意义：

Point + Scalar
Point * Point
message mod q
把一个任意字节串直接当成合法曲线点

数学类型意识是密码学实现中最便宜、也最有效的一道防线。

2.2 模运算：结果只关心余数类

若整数 \(a-b\) 能被 \(n\) 整除，就写作：

\[ a \equiv b \pmod n \]

例如：

\[ 20 \equiv 3 \pmod {17} \]

因为 \(20-3=17\)。在模 \(17\) 的世界里，\(20\)、\(3\)、\(-14\) 表示同一个余数类。

加法和乘法可以先运算再取模：

\[ (a+b)\bmod n \]

\[ (ab)\bmod n \]

例如在模 \(17\) 下：

\[ 13+9=22\equiv5\pmod {17} \]

\[ 7\cdot8=56\equiv5\pmod {17} \]

负数不是异常情况

在模 \(17\) 下：

\[ -3\equiv14\pmod {17} \]

实现时应把结果规范化到库约定的唯一表示，而不是让同一个标量存在多种字节编码。

模除法其实是乘逆元

有限域里没有普通意义上的除法。表达式

\[ \frac ab\pmod p \]

表示：

\[ a\cdot b^{-1}\pmod p \]

其中 \(b^{-1}\) 满足：

\[ b\cdot b^{-1}\equiv1\pmod p \]

例如在 \(\mathbb F_{17}\) 中，\(2^{-1}=9\)，因为：

\[ 2\cdot9=18\equiv1\pmod {17} \]

于是：

\[ 3/2\equiv3\cdot9\equiv10\pmod {17} \]

若模数是素数 \(p\)，每个非零元素都有乘法逆元。利用费马小定理还可写成：

\[ a^{-1}\equiv a^{p-2}\pmod p \]

真实实现应优先使用密码学库提供的常数时间求逆方法，而不是照搬一个会泄漏分支或执行时长的教学算法。

2.3 有限域：可安全做四则运算的有限集合

当 \(p\) 是素数时，

\[ \mathbb F_p=\{0,1,\ldots,p-1\} \]

在模 \(p\) 的加、减、乘、除（除数非零）下构成有限域。

“域”的关键性质是：

加法和乘法都封闭；
每个元素都有加法逆元；
每个非零元素都有乘法逆元；
运算满足结合律、交换律和分配律。

Shamir 秘密共享之所以选择在域上定义多项式，正是因为插值中的分母只要非零就一定可逆。

如果模数不是素数，非零元素未必有逆元。例如模 \(8\) 下不存在 \(2^{-1}\)，因为 \(2k\) 不可能与 \(1\) 模 \(8\) 同余。随意把复合数当作域模数，会让插值公式失效。

2.4 多项式与“点决定曲线”

在域 \(\mathbb F\) 上，一个次数不超过 \(d\) 的多项式可以写成：

\[ f(X)=a_0+a_1X+a_2X^2+\cdots+a_dX^d \]

注意这里的大写 \(X\) 是形式变量，不是 Schnorr 公钥。多项式的常数项为：

\[ f(0)=a_0 \]

直觉上：

一条一次多项式（直线）需要两个不同点才能唯一确定；
一条二次多项式需要三个不同点；
一般地，次数至多为 \(d\) 的多项式需要 \(d+1\) 个横坐标互不相同的点。

这个事实正是 Shamir \(t\)-of-\(n\) 方案选择“次数 \(t-1\)”的原因。

2.5 拉格朗日插值

给定 \(t\) 个横坐标互不相同的点：

\[ (x_1,y_1),\ldots,(x_t,y_t) \]

存在唯一一个次数不超过 \(t-1\) 的多项式穿过这些点。拉格朗日插值写作：

\[ f(X)=\sum_{i=1}^{t} y_i L_i(X) \]

其中：

\[ L_i(X)=\prod_{\substack{j=1\\j\ne i}}^{t} \frac{X-x_j}{x_i-x_j} \]

秘密共享最关心 \(f(0)\)，因此通常直接计算零点处的拉格朗日系数：

\[ \lambda_i=L_i(0)= \prod_{\substack{j\in S\\j\ne i}} \frac{-x_j}{x_i-x_j} \]

于是：

\[ f(0)=\sum_{i\in S}\lambda_i y_i \]

所有加、减、乘、求逆都在同一个域中进行。

小例子：在 \(\mathbb F_{17}\) 中恢复常数项

假设有两个点：

\[ (1,8),\quad(2,11) \]

零点处的系数为：

\[ \lambda_1=\frac{0-2}{1-2}=2 \]

\[ \lambda_2=\frac{0-1}{2-1}=-1\equiv16\pmod {17} \]

因此：

\[ f(0)=8\cdot2+11\cdot16=192\equiv5\pmod {17} \]

可以反推这两个点位于直线 \(f(X)=5+3X\) 上。

两个重要观察：

系数依赖于参与插值的横坐标集合 \(S\)；更换集合后必须重算。
如果两个横坐标相同，就会出现 \(x_i-x_j=0\)，而零没有乘法逆元。

2.6 群、标量乘法与离散对数

Schnorr 签名在一个阶为素数 \(q\) 的循环群 \(\mathbb G\) 中工作。采用加法记号时：

单位元写作 \(\mathcal O\)；
群加法写作 \(P+Q\)；
点 \(P\) 的逆元写作 \(-P\)；
标量乘法 \(aP\) 表示把 \(P\) 相加 \(a\) 次。

若 \(G\) 是生成元，那么群中每个元素都能写成：

\[ P=aG,\qquad a\in\mathbb Z_q \]

群阶为 \(q\) 意味着：

\[ qG=\mathcal O \]

因此标量按 \(q\) 约简：

\[ (a+q)G=aG \]

由标量 \(a\) 和点 \(G\) 计算 \(P=aG\) 很容易；已知 \(G\) 与 \(P\)，反求 \(a\) 被称为离散对数问题。在合适的群和参数下，这个反向问题被认为在计算上不可行。

这给出了公私钥关系：

\[ \text{私钥 }x\in\mathbb Z_q,\qquad \text{公钥 }X=xG\in\mathbb G \]

公钥可以公开，因为从 \(X\) 恢复 \(x\) 被离散对数困难性保护。

2.7 最重要的区别：基域不是标量域

以短 Weierstrass 形式为例，椭圆曲线方程可能写成：

\[ y^2=x^3+ax+b\pmod p \]

这里点坐标 \(x,y\) 和曲线参数位于基域 \(\mathbb F_p\)。

但私钥、nonce 和 Schnorr 响应是乘在群元素上的系数，位于标量域 \(\mathbb Z_q\)：

\[ x_{\text{secret}},k,c,z\in\mathbb Z_q \]

虽然两个集合里的值在程序中最后都可能表现为若干字节，但它们不是同一种数学对象。通常 \(p\ne q\)，也不能互换取模。

操作	正确模数或对象
曲线点坐标运算	\(p\)
私钥加法、nonce 加法	\(q\)
Shamir 共享 Schnorr 私钥	\(q\)
Schnorr 挑战和响应	\(q\)
点加法、点压缩与解压	由曲线/群库处理