久しぶりのRSA暗号ネタ。RSAで遊ぼうの続き。
OpenSSL RSA暗号の秘密鍵ファイル（private.key）の中に書かれている数字の一部が「exponent1」、「exponent2」、「cofficient」という3つの数字。ここで、
exponent1 = D mod (p-1)、
exponent2 = D mod (q-1)、
coefficient = q-1 mod p（coefficient*q=1 mod p）、
pとqは公開鍵N=pqの2つの素数pとqで、
Dは復号に使われれる秘密鍵。
「exponent1」、「exponent2」、「cofficient」は中国の剰余定理を使って復号のときの冪剰余計算（M=CD mod N みたいな計算）を高速に行うためのものだそうだ。
n を法とする冪剰余の計算
k=1024 の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。 a=bd mod n を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 (1024bit × 1024bit) を、1500回程繰り返すことで実現できる。 これには相当の計算時間を要するため、中国の剰余定理を用いて、ap = bd mod φ(p) mod p
aq = bd mod φ(q) mod q
a' = ap(q-1 mod p)q + aq(p-1 mod q)pとして求めることがある。
https://ja.wikipedia.org/wiki/RSA%E6%9A%97%E5%8F%B7（2021年11月27日閲覧）
だそうで、なぜこれで計算が速くなるのかを確認したいというのが今回の話。