背景
由于實際使用中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
春秋十二月 閱讀(1455)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm