第9話まで連載してきてRSAに到達しました。いやあ長いですねえ。
秘密鍵の計算で中国剰余定理っていうなんか凄そうな物が出てきます。
これは中国の算術書『孫子算経』に由来するものです。
原文は「今有物、不知其数。三・三数之、剰二。五・五数之、剰三。七・七数之、剰二。問物幾何？」
もうちょっとわかりやすく書いてみますね。
ここに、数がわからないあるものの山があります。（今有物、不知其数）
・3つずつまとめて数えると、2つ余る。（三・三数之、剰二）
・5つずつまとめて数えると、3つ余る。（五・五数之、剰三）
・7つずつまとめて数えると、2つ余る。（七・七数之、剰二）
さて、このものは全部でいくつ？（問物幾何？）
これ、割と簡単に解けます。まず注目するのは同じ余りの2。3と7どちらで割っても2余るので、最小公倍数21の倍数に+2したもの。23/44/65/86....となります。
次に5で割ったら3余る。おお！ 23が正解ですね。
とはいえ割った余りなので周期があります。3x5x7=105なので23+105の128も答えとして正しくなります。
ただ、中国剰余定理はこの除数の積の間に必ず一つ答えがあることを示します。
さて、ここでRSAでの復元を考えます。RSAは暗号文cに対し以下の処理でもとに戻します
m = c^d mod n
RSAのnはpとqの合成数でした。中国剰余定理を使うならn=pqなので mod p / mod q の世界の結果から求めることができます。
で、余りを求める場合、掛け算を繰り返すともとに戻るという性質があり（フェルマーの小定理）その周期は除数-1です。ということは d を p-1 で割った余りを dp、q-1で割った余りをdq とすると
m1 = c^d mod p = c^dp mod p
m2 = c^d mod q = c^dq mod q
として中国剰余定理を適用することで m を求めることができます。
この計算において演算量はべき乗数のビット数とハミング重みと法のビット数で決まります。
ハミング重みは二進数表記したときの1になるビットの数です。まあ確率的にはビット数の半分くらいですかね？
そして主に大きな変動は法のビット数で、半減すると1/4くらいに下がります。
n = p*q なので p/q は n の半分のビット数になりますね。
なのでm1の演算量は素朴に計算した場合のmに比べるとべき乗のビット数で半分(dp = d mod (p-1)なのでpのビット数以下）、法のビット数が半減で1/4、すべて掛け合わせて1/8になります。そしてm2も同じだけの演算量なので1/8。m1m2からmを求めますから1/8+1/8で1/4の演算量になります。
ただTOYの実装は素朴な実装なのでそこまで速くなっていません。本気で突き詰めるなら中国剰余定理を使用しない実装に対し3倍～4倍くらいの速度はたたき出せるようになっています。
次に公開鍵のeが65537である理由は、eが素数だとRSAの鍵の条件を満たしているかの確認が自明であることと、その上でハミング重みが2で最小と計算が軽いことが理由です。
作中でTOYはフェルマーに敬意を評して65537と述べています。この65537はフェルマー数というもので、定義は2^(2^n)+1です。このフェルマー数はF0～F4までが素数であることがわかっています。
F0 = 2^1 + 1 = 3
F1 = 2^2 + 1 = 5
F2 = 2^4 + 1 = 17
F3 = 2^8 + 1 = 257
F4 = 2^16 + 1 = 65537
フェルマーは発表当時すべてのフェルマー数は素数だと考えていたのですが、F5がそうではないことをオイラーが示しました。
F5 = 2^32 + 1 = 4294967297 = 641 * 6700417
さて、このべき乗計算において前述の通り演算量はビット数とハミング重みで決まるわけですね。そしてかつてRSAの公開鍵では3が使われていたのはビット数2ハミング重み2でとても計算が軽かったから、なのですが……小さすぎるeは攻撃に弱いことがわかっているため、現代では使われていません。
TOYはなんとなく「フェルマー数でいいか」みたいな解決していますが本来はそうやって決めてきたものなんです。
なんでeが小さいと危ないか、すごくシンプルでわかりやすい理由を一つ。
RSA は暗号データ c を平文データ m から以下のように求めます。
c = m^e mod n
さて、ここでe=3、ということは m^3 ということです。これが n よりも小さかったら？
c = m^3 となってしまうのでなんか簡単に計算できそうですね。
ちいさな m はあり得ないことはないです。結果逆算できてしまう。よくないですね。
他にも同じデータを異なる公開鍵で暗号化して送り出した場合についてそれぞれの法をn1,n2,n3としたときc1,c2,c3が分かっているので中国剰余定理で求められてしまう問題もあります。このため小さなeはよくない、のです。