背景
由于实际使用中RSA公钥通常很短，而私钥和模位长度一样，导致解密(或签名)时大数指数模运算比较慢，故可使用中国剩余定理约简模数和解密指数，以加快运算
描述
x为密文，n为模，p和q为大素数且满足n=pq，d为私钥，设
x
p ≡ x mod p，x
q ≡ x mod q
(1)
d
p ≡ d mod (p-1)，d
q ≡ d mod (q-1)
(2)
y
p = x
p^d
p mod p，y
q = x
q^d
q mod q
(3)
则有 x
d ≡ ((qc
p)y
p + (pc
q)y
q) mod n，其中 c
p ≡ q
-1 mod p ， c
q ≡ p
-1 mod q
证明
由(1)式可得
x
pd ≡ x
d mod p，x
qd ≡ x
d mod q
(4)
根据中国剩余定理可得
x
d ≡ ((qc
p)x
pd + (pc
q)x
qd) mod n，下面只要证明y
p和x
pd一样同余于x
d模p，y
q和x
qd一样同余于x
d模q
根据
(2)式及费小马定理可得
x
p^d
p ≡ x
pd mod p，x
q^d
q ≡ x
qd mod q, 再结合(4)得
x
p^d
p ≡ x
d mod p，x
q^d
q ≡ x
d mod q，故
y
p = x
d mod p，y
q = x
d mod q 证毕
posted on 2021-10-01 17:32
春秋十二月 阅读(1390)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm