https://ja.stackoverflow.com/a/72891/754 の質問を調べていく過程で、 RSA の秘密鍵は、その素数p
, q
以外にも、いくつかの値を前もって計算しておくことで、復号化の処理を高速化しているのだ、という記述を見つけました。具体的には、この回答から抜粋すると以下です。
modulus: n := p * q
publicExponent: e := 65537 (==0x10001)
privateExponent: d := e^-1 mod LCM(p-1, q-1) ※LCM は 最小公倍数関数
prime1: p
prime2: q
exponent1: dP := d mod (p-1)
exponent2: dQ := d mod (q-1)
coefficient: q_inv := q^(-1) mod p
このとき、 英語版 Wikipedia の記述に依れば、クライアントから送られてきた暗号文C == M^e
に対して、以下の処理を行なうと、その結果 M'
は、その実、RSA 暗号を復号化した原文(M
)になっている、すなわち、 M' == (M^e)^d mod n == M
が成立するそうです。
m1 := C^dP mod p
m2 := C^dQ mod q
h := q_inv * (m1 - m2) mod p
M' := m2 + h * q mod n
ちょっと考えて、どうしてこのように計算すると M' == M
が成立するのかが、自分には理解できていません。
質問
上記 RSA の復号化処理の高速化は、どうしてたしかに正しく復号ができているのでしょうか?
追記@2020/12/29
中国人剰余定理自体は理解していて、つまり、以下という認識です。
互いに素な数a
, b
があったとき、ある数x
が
x ≡ n_a mod a
x ≡ n_b mod b
を満たすとき、
x ≡ n mod (a * b)
が一意に存在する、ということです。この定理をどのように適用すると、この高速化が確かに正しい計算結果を得ていることになるのかが、分かっていないことです。