プログラミングにおいて、ある処理にどれくらいの時間がかかりそうか、という感覚は持っておいて損がないものである。今回は RSA 2048 について見よう。
RSA 2048 は、相異なる 1024 ビットの素数 p, q を使って 2048 ビットの整数 n = pq を作り、x^e mod n や x^d mod n を計算したりする暗号技術である。
以下の理由で、d 乗の方が 128 倍くらい掛かりそうに思える:
e は 65537 だから 16 ビット程度、d は基本的には 2048 ビットなので、2048 / 16 = 128
しかし現実はさにあらず。実際は 40 倍程度しか掛からないのである。
https://stackoverflow.com/questions/20840805/openssl-rsa-benchmark-vs-actual-rsa-sign-speed によると 35 倍程度
手元で openssl speed rsa-sign を実行したときも 40 倍程度だった
これには以下の 2 個の理由があると思う。
d 乗するときには p も q も分かっている。x^d mod n を計算するとき、直接計算するのではなく x^d mod p と x^d mod q を計算して、その後中国剰余定理によって x^d mod n を復元する方が速い。なぜならこれのボトルネックは x^d mod (素数) の部分で、乗算が O(ビット数^2) 程度の時間を要するため mod p や mod q でやると mod n でやるときの 1/4 倍の時間で済むため。mod p と mod q の 2 回やる必要があるので合計で 1/2 倍の時間がかかる。
x^d mod p を求めるとき、フェルマーの小定理から実は x^{d mod (p-1)} mod p を計算すれば良い。d mod (p-1) は 1024 ビット程度なのでこれで時間が 1/2 倍になる。
このように、ナイーブな予測値と実測値が食い違うことは珍しくないし、今回のようにその理由を追うことで天才的な発想に触れられることもあるかもしれない。特に openssl のような、数えきれない人数の目に晒され高速化をしつくされてきたソフトウェアには。