改进的混合基数转换法（MMRC）

发表于 分类于 ， 阅读次数： 本文字数： 617 阅读时长 ≈ 2 分钟

混合基数转换法（Mixed-Radix Conversion, MRC）是求 CRT 唯一解的方法，Kunth 对其进行了改进。可将改算法改进为改进的混合基数转换法（Modified Mixed-Radix Conversion, MMRC）。

MRC 比较复杂，在这里不做介绍，可以参考《中国剩余定理在 RSA 解密中的应用》1。

MMRC

下面来介绍一下 MMRC：

设同余方程组为：

\[ \begin{cases} x≡d_1\pmod{p_1}\\ x≡d_2\pmod{p_2}\\ ......\\ x≡d_s\pmod{p_s}\\ \end{cases} \]

  1. 计算\(B_{ji}\gets p_j^{-1}\pmod{p_i}(1\leqslant j<i\leqslant s)\)；
  2. 令\(a_{i1}=d_i(1\leqslant i\leqslant s)\)，由递推公式\(a_{i(j+1)}=(a_{ij}-a_{jj})B_{ji}\mod{p_i}(1\leqslant j<i\leqslant s)\)，计算\(a_{11},a_{22},...,a_{ss}\);
  3. 计算唯一解\(x\gets a_{11}+a_{22}p_1+a_{33}p_1p_2+...+a_{ss}p_1p_2p_3...p_s\)。

特别地，对于只包含两个方程的方程组

\[ \begin{cases} x≡d_1\pmod{p_1}\\ x≡d_2\pmod{p_2}\\ \end{cases} \]

可以这样计算：

  1. 计算\(B_{12}\gets p_1^{-1}\pmod{p_2}\)；
  2. \(a_{11}=d_1\)，\(a_{21}=d_2\)，计算\(a_{22}=(a_{21}-a_{11})B_{12}\mod{p_2}\);
  3. 计算唯一解\(x\gets a_{11}+a_{22}p_1\)。

MMRC 在 RSA 解密中的作用

RSA 的解密过程为\(M=C^d\mod N\)，而\(N=pq\)且\(p\)和\(q\)互素，所以 M 可以通过下式求出：

\[ \begin{cases} m_1≡C^d\pmod p\\ m_2≡C^d\pmod q\\ \end{cases} \]

其中\(m_1=C^d\mod p\)，\(m_2=C^d\mod q\)。

由此我们可以得到快速解密的算法：

  1. 计算\(m_1\gets (C\mod p)^{d\mod{p-1}}\mod p\)，\(m_2\gets (C\mod q)^{d\mod{q-1}}\mod q\)；
  2. 计算\(p^{-1}\pmod q\)；
  3. 计算\(t\gets p^{-1}(m_2-m_1)\mod q\)；
  4. 计算明文\(M\gets m_1+tp\)。

在第 1 步中，由于\(p\)是素数，由费马小定理2可得，\(C^{p-1}≡1\pmod p\)，所以\((C\mod p)^{d\mod{p-1}}\mod p=C^d\mod p\)，\(m_2\)同理。

下面给出我的代码，完整代码见MeanZhang/RSA: RSA-Java。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * RSA解密
 * 使用了MMRC算法
 *
 * @param c 密文
 * @param d 私钥d
 * @param p p
 * @param q q
 * @return 明文
 */
public static BigInteger decrypt(BigInteger c, BigInteger d, BigInteger p, BigInteger q) {
    // m1 ≡ c^d ≡ (c mod p)^(d mod (p-1))(mod p)
    BigInteger m1 = c.mod(p).modPow(d.mod(p.subtract(BigInteger.ONE)), p);
    // m2 ≡ c^d ≡ (c mod q)^(d mod (q-1))(mod q)
    BigInteger m2 = c.mod(q).modPow(d.mod(q.subtract(BigInteger.ONE)), q);
    BigInteger invP = p.modInverse(q);
    // t = p^(-1) * (m2-m1) mod q
    BigInteger t = invP.multiply(m2.subtract(m1)).mod(q);
    return m1.add(t.multiply(p));
}

参考资料

  1. 中国剩余定理在 RSA 解密中的应用--《河北省科学院学报》2003 年 03 期↩︎

  2. 费马小定理 - 维基百科，自由的百科全书↩︎