本文将详细介绍 Rabin 数字签名的算法细节。在开始之前,你需要对模运算、同余和模逆元的概念有一些了解。
算法过程
质数 $p$ 和 $q$,且有 $p \equiv 3 \pmod{4}$,$q \equiv 3 \pmod{4}$。
组合 $(p, q)$ 为私钥,两数的乘积 $n = pq$ 为对应的公钥。
使用私钥 $(p, q)$ 对消息 $m$ 签名的结果为组合 $(S, U)$,满足
$$
S^2 \equiv H(m||U) \pmod{n} \tag{1}
$$
其中的 $U$ 被称为填充值,$H(m||U)$ 的意思是将 $m$ 和 $U$ 的二进制流拼接在一起后再计算哈希,并将哈希结果(二进制流)看成一个整数。
令 $H = H(m||U) \bmod{n}$ 来简化书写。当 $U$ 确定后,可以用下式计算 $S$ 的值。
$$
S = \left[q \cdot (H^{\frac{p+1}{4}} \bmod{p}) \cdot (q^{p-2} \bmod{p}) + p \cdot (H^{\frac{q+1}{4}} \bmod{q}) \cdot (p^{q-2} \bmod{q})\right] \bmod{n} \tag{2}
$$
这样便得到了一组 $(S, U)$,将结果代入 (1) 式验算,若成立则返回这组结果,反之则改变 $U$ 的值重新计算 $S$,直到找到一组满足 (1) 式的解。
请注意,当 $p \equiv 3 \pmod{4}$ 时,$\frac{p+1}{4}$ 是一个整数,同理 $\frac{q+1}{4}$ 也是一个整数。
完整代码请参考 rabin.py。签名时,通过循环在 $m$ 后追加字节 0x00 来改变 $H$ 的值,并在计算出 $S$ 后验证 (1) 式是否成立,是则跳出循环返回,否则继续寻找。
def sign(p: int, q: int, digest: bytes) -> tuple: |
验签时只需判断 (1) 式是否成立即可。
def verify(n: int, digest: bytes, s: int, u: bytes) -> bool: |
通过上面的描述你能看到,Rabin 签名的计算过程相对复杂,但验证过程极其简单。这个特性使得它非常适合在链上直接验签,虽然我们也可以在比特币脚本中实现 ECDSA 的验签逻辑,但它的计算成本要比验证 Rabin 签名高出许多。
整个算法设计基于这样的数学难题:在模是大合数的情况下,求二次剩余平方根是困难的。使用 Rabin 签名时,为了获得足够的安全性,公钥 $n$ 和哈希 $H(m||U)$ 的结果至少需要 3072 位(bit)。
至此,我们介绍了如何计算和验证 Rabin 签名,并给出了完整代码,方便你直接使用。如果你还关心这些结论和公式背后的推导过程,可以继续阅读,我们留了一些问题没有解答:
- 问题一:当 $p \equiv 3 \pmod{4}$ 时,为什么 $\frac{p+1}{4}$ 是一个整数?
- 问题二:公式 (1) 是如何推导出公式 (2) 的?
问题一
证明当 $p \equiv 3 \pmod{4}$ 时,$\frac{p+1}{4}$ 是一个整数。
根据同余的定义,对 $p \equiv 3 \pmod{4}$,存在整数 $m$、$n$ 和 $r$ 满足:
$$\begin{cases} p = 4m + r \\[0.5em] 3 = 4n + r \end{cases}$$两式相减,有
$$
p - 3 = 4(m - n) \tag{3}
$$
因为 $m$ 和 $n$ 都是整数,所以 $(m - n)$ 也是整数。也就是说,若两数在某个模数下同余,则两数的差是模数的整数倍,反之亦然。
等式 (3) 两边同时加 4,得到 $p + 1 = 4(m - n + 1)$,即 $\frac{p+1}{4} = m - n + 1$。因为 $m$ 和 $n$ 都是整数,所以 $(m - n + 1)$ 也是整数,证毕。
二次剩余
在数论特别是同余理论中,一个整数 $X$ 对另一个整数 $p$ 的二次剩余(quadratic residue),指的是 $X$ 的平方 $X^2$ 除以 $p$ 得到的余数。
若存在某个 $X$ 使得 $X^2 \equiv d \pmod{p}$ 成立,则称 $d$ 是模 $p$ 的二次剩余。若对任意的 $X$ 式子 $X^2 \equiv d \pmod{p}$ 均不成立,则称 $d$ 是模 $p$ 的非二次剩余。
例如,2 是模 7 的二次剩余,因为当 $X = 3$ 时 $3^2 \equiv 2 \pmod{7}$ 成立。3 是模 7 的非二次剩余,因为你找不到整数 $X$ 使式子 $X^2 \equiv 3 \pmod{7}$ 成立。
求二次剩余的平方根,即已知 $d$ 和 $p$ 求 $X$,可以使用 Tonelli–Shanks 算法。
当 $p \equiv 3 \pmod{4}$ 时,该算法有简化版本,即
$$X = \begin{cases} d^{\frac{p+1}{4}} \bmod{p} \\[0.5em] -d^{\frac{p+1}{4}} \bmod{p} \end{cases}$$例如,当 $p = 7$ 时,若 $X^2 \equiv 2 \pmod{7}$,则
$$X = \begin{cases} 2^{\frac{7+1}{4}} \bmod{7} = 4 \bmod{7} = 4 \\[0.5em] -2^{\frac{7+1}{4}} \bmod{7} = -4 \bmod{7} = 3 \end{cases}$$你可以验算一下,发现 $4^2 \bmod{7} = 2$,$3^2 \bmod{7} = 2$,根据公式计算出的 $X$ 是正确的结果。
如果你使用同样的方法,计算 $X^2 \equiv 3 \pmod{7}$,可以得到
$$X = \begin{cases} 3^{\frac{7+1}{4}} \bmod{7} = 9 \bmod{7} = 2 \\[0.5em] -3^{\frac{7+1}{4}} \bmod{7} = -9 \bmod{7} = 5 \end{cases}$$再验算一下,发现 $2^2 \bmod{7} = 4 \neq 3$,$5^2 \bmod{7} = 4 \neq 3$,这两个解都是错误的。他们当然是错误的,因为 3 是模 7 的非二次剩余,没有这样的 $X$ 能满足方程。
所以在不确定 $d$ 是否是模 $p$ 的二次剩余时,用公式计算出结果后还需要验算。这也是在利用 (2) 式求解 $S$ 后还需要验算 (1) 式是否成立的原因,因为我们不确定 $H$ 是否是模 $n$ 的二次剩余。先记下这个问题:
- 问题三:在已知 $p$、$q$ 的情况下,有什么方法能快速判断 $H$ 是否是模 $n = pq$ 的二次剩余?
中国剩余定理
南北朝时期的数学著作《孙子算经》中提出了下列“物不知数”问题:
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
即求解同时满足除以 3 余 2,除以 5 余 3,除以 7 余 2 的整数。中国剩余定理(也被称为中国余数定理和孙子定理)给出了此类问题有解的判定条件,并用构造法给出了在有解情况下解的具体形式。
对于 $x$ 的一元线性同余方程组:
$$\begin{cases} x \equiv a_1 \pmod{m_1} \\[0.5em] x \equiv a_2 \pmod{m_2} \\[0.5em] \quad... \\[0.5em] x \equiv a_n \pmod{m_n} \end{cases}$$若整数 $m_1, m_2, …, m_n$ 任意两数互质,则对任意的整数 $a_1, a_2, …, a_n$,上述方程有解。通解可以用下面的步骤构造得到。
- 设 $M = m_1 \times m_2 \times … \times m_n$,$M_i = M / m_i$。即 $M_i$ 是除了 $m_i$ 以外的 $(n-1)$ 个整数的乘积
- 设 $t_i$ 是 $M_i$ 关于模 $m_i$ 的模逆元。即 $t_iM_i \equiv 1 \pmod{m_i}$
- 通解为 $x = kM + \sum_{i=1}^{n}a_it_iM_i$,其中 $k$ 是整数($k \in \mathbb{Z}$)。即 $x \equiv \sum_{i=1}^{n}a_it_iM_i \pmod{M}$,最小整数解是 $(\sum_{i=1}^{n}a_it_iM_i) \bmod{M}$
以求解“物不知数”问题为例。根据描述可以列出下列方程:
$$\begin{cases} x \equiv 2 \pmod{3} \\[0.5em] x \equiv 3 \pmod{5} \\[0.5em] x \equiv 2 \pmod{7} \end{cases}$$对照着通解公式,计算过程为:
- $a_1 = 2$,$a_2 = 3$,$a_3 = 2$
- $m_1 = 3$,$m_2 = 5$,$m_3 = 7$
- $M = m_1m_2m_3 = 105$
- $M_1 = m_2m_3 = 35$,$M_2 = m_1m_3 = 21$,$M_3 = m_1m_2 = 15$
- $t_1 = M_1^{-1} \bmod{m_1} = 35^{-1} \bmod{3} = 2$,$t_2 = 21^{-1} \bmod{5} = 1$,$t_3 = 15^{-1} \bmod{7} = 1$
- $(\sum_{i=1}^{n}a_it_iM_i) \bmod{M}= (140 + 63 + 30) \bmod{105} = 233 \bmod{105} = 23$
- $x \equiv 23 \pmod{105}$
满足条件的解为 $23 + 105k$($k \in \mathbb{Z}$),最小的整数解为 23。
问题二
有了二次剩余和中国剩余定理的知识基础,下面解答公式 (2) 是怎么来的。
根据 Rabin 签名的定义,有
$$
S^2 \equiv H(m||U) \pmod{n} \tag{1}
$$
其中 $n = pq$。注意到,$H(m||U)$ 可能不小于 $n$,令 $H = H(m||U) \bmod{n}$ 来简化书写,有
$$
S^2 \equiv H \pmod{pq}
$$
利用证明问题一时得到的推论,有 $S^2 - H = k \cdot pq = kq \cdot p = kp \cdot q$,其中的 $k$ 为整数($k \in \mathbb{Z}$)。即两数的差是 $p$ 的整数倍,也是 $q$ 的整数倍,所以有
$$
S^2 \equiv H \pmod{p} \tag{A}
$$
$$
S^2 \equiv H \pmod{q} \tag{B}
$$
对 (A) 式使用 Tonelli–Shanks 算法的简化版本,可以得到
$$S = \begin{cases} H^{\frac{p+1}{4}} \bmod{p} \\[0.5em] -H^{\frac{p+1}{4}} \bmod{p} \tag{C} \end{cases}$$同理对 (B) 式,也有
$$S = \begin{cases} H^{\frac{q+1}{4}} \bmod{q} \\[0.5em] -H^{\frac{q+1}{4}} \bmod{q} \tag{D} \end{cases}$$为了使用中国剩余定理,需要保证整数 $m_1, m_2, …, m_n$ 任意两数互质。注意到 $p$ 和 $q$ 都是质数,所以 $p$ 和 $q$ 互质,我们从 (C) 式和 (D) 式中各挑一个解,组成下列方程:
$$\begin{cases} S = H^{\frac{p+1}{4}} \bmod{p} \\[0.5em] S = H^{\frac{q+1}{4}} \bmod{q} \tag{E} \end{cases}$$则该方程有解。
- $a_1 = H^{\frac{p+1}{4}}$,$a_2 = H^{\frac{q+1}{4}}$
- $m_1 = p$,$m_2 = q$
- $M = pq = n$,$M_1 = q$,$M_2 = p$
- $t_1 = M_1^{-1} \bmod{m_1} = q^{-1} \bmod{p}$,$t_2 = M_2^{-1} \bmod{m_2} = p^{-1} \bmod{q}$
$$
S = (\sum_{i=1}^{n}a_it_iM_i) \bmod{M}= \left[q \cdot H^{\frac{p+1}{4}} \cdot (q^{-1} \bmod{p}) + p \cdot H^{\frac{q+1}{4}} \cdot (p^{-1} \bmod{q})\right] \bmod{n} \tag{F}
$$
如果你还记得费马小定理。对整数 $a$ 和质数 $p$,有 $a^p \equiv a \pmod{p}$,当 $a$ 不是 $p$ 的整数倍时,可以直接写成 $a^{p-1} \equiv 1 \pmod{p}$。你可以把这个等式理解成 $a \cdot a^{p-2} \equiv 1 \pmod{p}$,这正是模逆元的定义(一种求解模逆元的方法)。注意到 $p$ 和 $q$ 都是质数,所以 $p$ 不是 $q$ 的整数倍,$q$ 也不是 $p$ 的整数倍。所以有
$$
p^{-1} \bmod{q} = p^{q-2} \bmod{q}
$$
$$
q^{-1} \bmod{p} = q^{p-2} \bmod{p}
$$
代入 (F) 式,得到
$$
S = \left[q \cdot H^{\frac{p+1}{4}} \cdot (q^{p-2} \bmod{p}) + p \cdot H^{\frac{q+1}{4}} \cdot (p^{q-2} \bmod{q})\right] \bmod{n} \tag{G}
$$
为了获得足够的算法安全性,实际使用 Rabin 签名时选取的 $p$、$q$ 和 $H$ 会非常大,导致 (G) 式中的 $H^{\frac{p+1}{4}}$ 和 $H^{\frac{q+1}{4}}$ 部分无法计算。
注意到 (E) 式中的 $H^{\frac{p+1}{4}}$ 可能不小于 $p$,$H^{\frac{q+1}{4}}$ 可能不小于 $q$,所以 (E) 式实际上等价于
$$\begin{cases} S = (H^{\frac{p+1}{4}} \bmod{p}) \bmod{p} \\[0.5em] S = (H^{\frac{q+1}{4}} \bmod{q}) \bmod{q} \tag{E'} \end{cases}$$观察方程 (E) 和公式 (G) 的形式,我们可以直接根据 (E’) 写出最终的 (2) 式。
$$
S = \left[q \cdot (H^{\frac{p+1}{4}} \bmod{p}) \cdot (q^{p-2} \bmod{p}) + p \cdot (H^{\frac{q+1}{4}} \bmod{q}) \cdot (p^{q-2} \bmod{q})\right] \bmod{n} \tag{2}
$$
其中的 $H = H(m||U) \bmod{n}$。虽然 $H^{\frac{p+1}{4}}$ 和 $H^{\frac{q+1}{4}}$ 无法求解,但计算 $(H^{\frac{p+1}{4}} \bmod{p})$ 和 $(H^{\frac{q+1}{4}} \bmod{q})$ 却很简单。
另外注意到,在构造方程 (E) 时,我们还有其他三种情况没有列出,所以 $S$ 的值还可能为
$$S = \quad \begin{cases} \quad \left[q \cdot (-H^{\frac{p+1}{4}} \bmod{p}) \cdot (q^{p-2} \bmod{p}) + p \cdot (H^{\frac{q+1}{4}} \bmod{q}) \cdot (p^{q-2} \bmod{q})\right] \bmod{n} \\[0.5em] \quad \left[q \cdot (H^{\frac{p+1}{4}} \bmod{p}) \cdot (q^{p-2} \bmod{p}) + p \cdot (-H^{\frac{q+1}{4}} \bmod{q}) \cdot (p^{q-2} \bmod{q})\right] \bmod{n} \\[0.5em] \quad \left[q \cdot (-H^{\frac{p+1}{4}} \bmod{p}) \cdot (q^{p-2} \bmod{p}) + p \cdot (-H^{\frac{q+1}{4}} \bmod{q}) \cdot (p^{q-2} \bmod{q})\right] \bmod{n} \end{cases}$$运行代码 rabin.py 中的例子,可以得到签名 (71, 0x00)。改变 $S$ 的计算公式,你会发现 (27, 0x00)、(50, 0x00) 和 (6, 0x00) 都是合法的签名。如何计算 $-H^{\frac{p+1}{4}} \bmod{p}$ 和 $-H^{\frac{q+1}{4}} \bmod{q}$,留给你思考。
问题三
在计算签名时,因为不确定 $H$ 是否是模 $n$ 的二次剩余,所以在利用公式 (2) 计算出 $S$ 后,还需要代入 (1) 式验算,验算失败就要重做。如果我们可以在计算 $S$ 前就确定 $H$ 是模 $n$ 的二次剩余,那么可以减少签名过程中的一些无效运算。
数论中的欧拉准则(也叫欧拉判别法)可以用来确定给定的整数是否是一个质数的二次剩余。
若 $p$ 是奇质数(除了 2 以外的质数)且 $p$ 不能整除 $d$(即 $d$ 不是 $p$ 的整数倍),当且仅当
$$
d^{\frac{p-1}{2}} \equiv 1 \pmod{p}
$$
成立时,$d$ 是模 $p$ 的二次剩余。若 $p = 2$,或 $d$ 是 $p$ 的整数倍,则 $d$ 一定是模 $p$ 的二次剩余,无需判定。
Rabin 签名中的 $p$ 和 $q$ 都是奇质数,但 (1) 式中的模数 $n = pq$ 不是。下面我们来证明:对质数 $p$、$q$,若 $d$ 是模 $p$ 的二次剩余,也是模 $q$ 的二次剩余,那么 $d$ 也是模 $pq$ 的二次剩余。
根据条件及二次剩余的定义,存在整数 $a$、$b$ 满足
$$\begin{cases} a^2 \equiv d \pmod{p} \\[0.5em] b^2 \equiv d \pmod{q} \end{cases}$$根据中国剩余定理,因为 $p$、$q$ 互质,所以存在这样的整数 $x$ 满足
$$\begin{cases} x \equiv a \pmod{p} \\[0.5em] x \equiv b \pmod{q} \end{cases}$$所以 $x^2 \bmod{p} = a^2 \bmod{p} = d \bmod{p}$,即 $x^2 \equiv d \pmod{p}$。也就是说,$(x^2 - d)$ 是 $p$ 的整数倍,即存在整数 $k$ 满足 $x^2 - d = kp$。
同理 $x^2 \bmod{q} = b^2 \bmod{q} = d \bmod{q}$,即 $x^2 \equiv d \pmod{q}$。也就是说,$(x^2 - d)$ 也是 $q$ 的整数倍,即 $kp$ 是 $q$ 的整数倍。
因为 $p$、$q$ 互质,所以 $p$ 不是 $q$ 的整数倍,所以 $k$ 是 $q$ 的整数倍。因此 $x^2 - d = kp$ 是 $pq$ 的整数倍,即 $x^2 \equiv d \pmod{pq}$,证毕。
有了这个结论,我们可以对代码做一些优化,改进后的代码请参考 rabin.py。先用欧拉准则确定 $H$ 是模 $p$ 的二次剩余且是模 $q$ 的二次剩余后,再计算 $S$。
def sign(p: int, q: int, digest: bytes) -> tuple: |
致谢
虽然只是篇博客文章,但完成它于我并非易事。
特别感谢 nChain Research Team 的 Wei Zhang,对本文内容的审阅和优化,以及对我理解相关数学原理和密码学知识的指导和帮助。
特别感谢 nChain Research Team 的 Owen Vaughan,对我理解 Rabin 签名的指导和帮助。
感谢中国人民大学的研究生李小满,为文中部分证明提供思路。
感谢感应合约团队的顾露、陈诚、蒋杰和陈耀欢,ShowPay 的王宇,以及 sCrypt 的郑宏峰,对我在使用和实践 Rabin 签名过程中的指导和帮助。
谢谢你们在工作和生活之余挤出宝贵时间,热情而耐心的解答我的问题,无私的分享知识和经验。
参考
- Rabin Signatures in Bitcoin Cash, Owen Vaughan - Senior Researcher, nChain 原文 译文
- 预言机与 Rabin 签名在比特币智能合约中的应用原理
- sCrypt-Inc/rabin
- OI Wiki 中国剩余定理
- OI Wiki 二次剩余
- 两种求二次剩余平方根算法的比较
- $a \equiv b \pmod{p}$ and $a \equiv b \pmod{q}$. Show that $a \equiv b \pmod{pq}$
- Introduction to Number Theory 2
- Quadratic Residues