Rabin 数字签名

发表于 | 分类于 | 阅读次数：

本文将详细介绍 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:
    """
    :param p: part of private key
    :param q: part of private key
    :param digest: message digest to sign
    :return: rabin signature (S: int, U: bytes)
    """
    n = p * q
    i = 0
    while True:
        h = hash_to_int(digest + b'\x00' * i) % n
        lp = q * pow(h, (p + 1) // 4, p) * pow(q, p - 2, p)
        rp = p * pow(h, (q + 1) // 4, q) * pow(p, q - 2, q)
        s = (lp + rp) % n
        if (s * s) % n == h % n:
            break
        i += 1
    return s, b'\x00' * i

验签时只需判断 (1) 式是否成立即可。

def verify(n: int, digest: bytes, s: int, u: bytes) -> bool:
    """
    :param n: rabin public key
    :param digest: digest of signed message
    :param s: S of signature
    :param u: padding U of signature
    """
    return hash_to_int(digest + u) % n == (s * s) % n

通过上面的描述你能看到，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:
    """
    :param p: part of private key
    :param q: part of private key
    :param digest: message digest to sign
    :return: rabin signature (S: int, U: bytes)
    """
    n = p * q
    i = 0
    while True:
        h = hash_to_int(digest + b'\x00' * i) % n
        if (h % p == 0 or pow(h, (p - 1) // 2, p) == 1) and (h % q == 0 or pow(h, (q - 1) // 2, q) == 1):
            break
        i += 1
    lp = q * pow(h, (p + 1) // 4, p) * pow(q, p - 2, p)
    rp = p * pow(h, (q + 1) // 4, q) * pow(p, q - 2, q)
    s = (lp + rp) % n
    return s, b'\x00' * i

致谢

虽然只是篇博客文章，但完成它于我并非易事。

特别感谢 nChain Research Team 的 Wei Zhang，对本文内容的审阅和优化，以及对我理解相关数学原理和密码学知识的指导和帮助。

特别感谢 nChain Research Team 的 Owen Vaughan，对我理解 Rabin 签名的指导和帮助。

感谢中国人民大学的研究生李小满，为文中部分证明提供思路。

感谢感应合约团队的顾露、陈诚、蒋杰和陈耀欢，ShowPay 的王宇，以及 sCrypt 的郑宏峰，对我在使用和实践 Rabin 签名过程中的指导和帮助。

谢谢你们在工作和生活之余挤出宝贵时间，热情而耐心的解答我的问题，无私的分享知识和经验。

参考