中国剩余定理的密码学应用

中国剩余定理（CRT）在密码学中最著名的应用是加速 RSA 解密与签名：把大模数 $n=pq$ 上的模幂拆成模 $p$、模 $q$ 两个小模幂再重组，速度约提升 4 倍。这是数论定理转化为工程优化的典型例子。

CRT-RSA 解密

设 $n=pq$，私钥 $d$。预计算

$$d_p\equiv d\pmod{p-1},\qquad d_q\equiv d\pmod{q-1}$$

对密文 $c$：

$$m_p\equiv c^{d_p}\pmod p,\qquad m_q\equiv c^{d_q}\pmod q$$

再由中国剩余定理重组

$$m\equiv m_p+p\left((m_q-m_p)\cdot p^{-1}\bmod q\right)\pmod n$$

其中 $p^{-1}$ 是 $p$ 模 $q$ 的逆。小指数 $d_p,d_q$ 使两次模幂远快于一次大模幂。

示例

$p=61$，$q=53$，$d=2753$：$d_p=2753\bmod60=53$，$d_q=2753\bmod52=49$。解密 $c=2790$：

$$m_p\equiv2790^{53}\equiv4\pmod{61},\qquad m_q\equiv2790^{49}\equiv12\pmod{53}$$

$p^{-1}\equiv61^{-1}\equiv20\pmod{53}$（$61\cdot20=1220\equiv1$），故

$$m\equiv4+61\cdot((12-4)\cdot20\bmod53)=4+61\cdot1=65\pmod{3233}$$

与直接计算 $2790^{2753}\equiv65\pmod{3233}$ 一致。

安全注意

CRT 实现若无冗余校验，故障注入（差分错误分析）可泄露私钥；实践中以 $m_p^e\equiv c\pmod p$ 校验结果。

应用

CRT-RSA 广泛用于智能卡与 TLS 服务器；CRT 还用于构造秘密共享（见Shamir秘密共享）与密钥分发协议。