改进的混合基数转换法（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. 计算Bji ← pj−1 (mod  pi)(1≤j<i≤s)；
  2. 令ai1 = di(1≤i≤s)，由递推公式ai(j+1) = (aij−ajj)Bji mod  pi(1≤j<i≤s)，计算a11, a22, ..., ass;
  3. 计算唯一解x ← a11 + a22p1 + a33p1p2 + ... + assp1p2p3...ps。

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

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

可以这样计算：

  1. 计算B12 ← p1−1 (mod  p2)；
  2. a11 = d1，a21 = d2，计算a22 = (a21−a11)B12 mod  p2;
  3. 计算唯一解x ← a11 + a22p1。

MMRC 在 RSA 解密中的作用

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

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

其中m1 = Cd mod  p，m2 = Cd mod  q。

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

  1. 计算m1 ← (C mod  p)d mod  p − 1 mod  p，m2 ← (C mod  q)d mod  q − 1 mod  q；
  2. 计算p−1 (mod  q)；
  3. 计算t ← p−1(m2−m1) mod  q；
  4. 计算明文M ← m1 + tp。

在第 1 步中，由于p是素数，由费马小定理2可得，Cp − 1 ≡ 1 (mod  p)，所以(C mod  p)d mod  p − 1 mod  p = Cd mod  p，m2同理。

下面给出我的代码，完整代码见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));
}

参考资料