背景
由于實(shí)際使用中RSA公鑰通常很短，而私鑰和模位長(zhǎng)度一樣，導(dǎo)致解密(或簽名)時(shí)大數(shù)指數(shù)模運(yùn)算比較慢，故可使用中國剩余定理約簡(jiǎn)模數(shù)和解密指數(shù)，以加快運(yùn)算
描述
x為密文，n為模，p和q為大素?cái)?shù)且滿足n=pq，d為私鑰，設(shè)
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)
根據(jù)中國剩余定理可得
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
根據(jù)
(2)式及費(fèi)小馬定理可得
x
p^d
p ≡ x
pd mod p，x
q^d
q ≡ x
qd mod q, 再結(jié)合(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
春秋十二月 閱讀(1446)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Algorithm