久しぶりの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=C^D mod N みたいな計算）を高速に行うためのものだそうだ。

n を法とする冪剰余の計算
k=1024 の場合、n は1024ビットサイズという大きな数となり、d もほぼ n と同サイズの数となる。 a=b^d mod n を計算するには、バイナリ法というアルゴリズムを用いると、剰余乗算 (1024bit × 1024bit) を、1500回程繰り返すことで実現できる。 これには相当の計算時間を要するため、中国の剰余定理を用いて、

ap = b^{d mod φ(p)} mod p
aq = b^{d 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日閲覧）

だそうで、なぜこれで計算が速くなるのかを確認したいというのが今回の話。

Wikipediaの記載を見ると、apの計算に用いられているのがexponent1で、aqの計算に用いられているのがexponent2であり、a'の計算の第1項に用いられているのがcoefficientであることが確認できる。これらの計算はそれなりに時間が掛かるということなのだろう（容易ではないとは言ってない）。でも p^-1 mod q は前もって計算してないようだ。おそらくWikipediaに書かれているのとはちょっと違う式を使うのだろうが、ここではそれは無視して先に進む。（フラグが立ったような気がする…）
Wikipediaの記載に合わせて、N（Wikipediaではn）は1024ビットであるとしよう。そうするとpとqはだいたい512ビットであろう。秘密鍵D（Wikipediaではd）は E^-1 mod φ(N) で、φ(N) = φ(p)φ(q) = (p-1)(q-1) なので、長さはだいたい1024ビットとしてよいだろう。（ここまではWikipediaの説明の通り）

さて復号の処理は c^D mod N なので、c × c という掛け算を D-1 回する必要があるのだが、バイナリー法というのを使うとDのビット数の2倍程度、ほぼ2000回くらいで計算できる。（Wikipediaでは1500回となっている。おそらく最悪が2000回で最良が1000回なので平均は1500回くらいということで1500回という記載になっているのか？）Nのオーダーの処理がlogNのオーダーで可能になるのでこれはすごい。
これが中国の剰余定理を使わなかったときの掛け算（以後「バカ正直な方法」と呼ぶ）の回数になる。

一方、中国の剰余定理を使うと、ap = b^{d mod φ(p)} mod p というような計算を2回行う必要がある。上の記載と表記を合わせると、c^exponent1 mod p となる。exponent1 は D mod (p-1) なので、p-1 と同じくらいのビット数、つまり512ビット程度になるだろう。となると、apの計算には c × c という掛け算を1000回くらい行う必要がある。aqの計算も同様で1000回くらい。合わせると2000回くらい。

あれ？ 掛け算の回数が変わっていないのではないか？

実はここでしばらく悩んだのだが、現時点では以下のように考えている。

注目すべき違いは、mod N なのか mod p なのかという点。
冪剰余の計算はすべての数字を掛けてから剰余の計算をする必要はなくて、一つの掛け算をする前に剰余を計算すればよい。
（ABの積の剰余を考えると、AB = (aN + c)(bN + d) = (abN + ad + bc)N + cd なので、ABの剰余はcdの剰余と等しいことがわかる）
つまり、バカ正直な方法は mod N なので、N つまり1024ビット程度の数字の掛け算を2000回行う必要がある。
一方、中国の剰余定理を使うと、mod p なので、p つまり512ビット程度の数字の掛け算を2000回行う必要がある。
長さが2倍違う掛け算なので、計算時間は4倍以上違ってくるだろう。

ほんとかな？ 想像していたほど大きな違いではないので驚いている。どこか間違っているかもしれない。