『電子署名≠秘密鍵で暗号化』で、『RSAという暗号アルゴリズムは秘密鍵を使う処理も公開鍵を使う処理もまったく同じようにできるという素晴らしい対称性を持っている』と書いた。これがどういうことかと言えば(まぁ、ここを読むよな人なら誰でも知ってるだろうがいちおう)、
秘密鍵を使う処理:
P=CD mod N
公開鍵を使う処理:
C=PE mod N
というようにまったく同じ形で処理が行えるということを意味するわけだ。
もちろん、この通りの処理を行なうのでまったく問題なく動作はする(というか動作しなきゃ困るんだが)。実際、手を抜いてそんな実装にしちまってるアプリケーションもあるんだろう。
ちなみにちょっと脱線するけど、公開鍵暗号って当然公開鍵から秘密鍵を導出することはえらく難しくなくちゃ困るんだが、その逆は簡単とか思ってない?たしかにElGamalとかの離散対数系のやつぁそういう傾向があるんだけど、↑のようにRSAをナイーブに実装していると、逆に秘密鍵から公開鍵を導出するのも十分難しいんだよね(ただし鍵の生成も含めてほんとーにナイーブに実装してる場合のみね。ちょっとマジメに実装する場合は公開鍵となる乗数は固定しちゃうもんだから導出するまでもない話)。何故そうなるのかはRSAのアルゴリズムを眺めながら考えてみよう!
さて、閑話休題。
それじゃあマトモなRSA実装ならどういう風にしているんじゃいと言えば、そこでようやく出てくるのがタイトルになっている『中華風剰余定理』ということなわけ。はぁ、タイトルに辿り着くまでが長かったぜ。それでは以下次号。
とか言ってるとまたおちょくってるのかと怒られそうなのでおとなしく先を続けとこーか。
中華風剰余定理って書くとなんとなくおいしそうでしょ?『中国人の剰余定理』とか呼ぶのが普通なんだろうとは思うんだけど、原語(なのか?)がChinese Remainder Theoremなんで、この“Chinese”は“中国人”ではなく“中国の”と解釈する方が適切に思えるので。で、“中国の”ではなくあえて“中華風”と記述しているのは、昔NetNewsのfj.sci.mathかなんかでたしか現(当時も、かもしれんけど)奈良女子大の鴨さんが使っていたのを見て以来、その語感がえらく気に入って使っているのであった。
おっと、また脱線しかけちまったけど、じゃぁ、その中華風剰余定理ってのはなんなんじゃい、と言えば、RSA での応用に即した形で言えば、 二つの素数P,Qの積を法とする剰余類ZPQ={0,1,2,...,PQ-1}の各要素を、P,Qそれぞれを法とする二つの剰余類ZP={0,1,2,...,P-1}とZQ={0,1,2,...,Q-1}の要素の組に対応付ける関係は一意的であり、かつ、その関係はそれぞれの剰余類内で乗算/加算を行った結果を通じて保存される、ということになる(本来的な中華風剰余定理は二つじゃなく任意の個数の積を法とする剰余類でいいし、条件も素数じゃなきゃいけないわけじゃなくってそれらの数が互いに素であればそれで構わない)。
具体的に例を挙げれば、Z15の要素7はZ3では 1、Z5では 2 となるし(単に7を3で割った余りと5で割った余り、ということ)、72をZ15で計算すれば4となるが、これはZ3では 1、Z5では4ということで上の 1 と 2 をそれぞれ 2 乗した値と等しい。これが『対応関係が乗算の結果を通じて保存される』ということで、同じことがすべての要素に関して言えるし、それは加算でも同じ、というのが中華風剰余定理の主張なのさ。
ということは、RSAで利用されるN=PQを法とする累乗演算というのも、被乗数 CもしくはPをそれぞれP、Qを法とする剰余類での表現に変換した上で演算し、その結果を改めてNを法とする剰余類での表現に戻してやる、という処理ができる(ただし、P、Qを知られてしまうと秘密鍵まで計算できることになるため、公開鍵側の処理でこの最適化を用いることは不可)。実用的なRSAで用いられるようないわゆる多倍長整数演算では、累乗計算のコストは(たしか)ビット長の 3 乗に比例するため、ZPQでの演算は、ZPとZQそれぞれで演算する場合と比べてざっと 4 倍程度の計算コストがかかることになる。逆に言えば、RSA の秘密鍵に関する処理は、二つの素数P、Qそれぞれの剰余類に分解した形で演算する方が計算コストを 1/4 程度にできるということを意味しているわけ。だからこそ、真っ当な RSA 実装はこの中華風剰余定理による最適化が使えるような形で秘密鍵データを保存しているし、実際にそれを使って高速化している。
たとえば、opensslで生成した秘密鍵ってのは
modulus:
00:f3:ed:88:e2:d0:91:1e:47:d2:74:b6:2a:f9:a7:
d7:16:49:a4:22:00:88:9d:21:5f:b1:c3:d4:fe:cb:
cf:75:05:c9:01:c9:90:ee:0d:24:00:52:8b:9f:f2:
0b:aa:ed:a2:ee:df:e9:cb:b3:70:1c:77:6a:3d:d1:
ad:83:4c:a5:d3
publicExponent: 65537 (0x10001)
privateExponent:
6c:f0:57:e3:1c:4c:c3:5e:46:32:93:ad:0b:c4:96:
bd:c0:73:ca:2f:bc:d3:98:35:19:ba:21:25:0e:36:
ff:c6:8f:6e:3d:56:4c:2e:62:71:85:3e:69:32:08:
5a:d3:2c:86:12:22:74:62:36:44:ee:1d:1a:13:a2:
b7:fa:c5:91
prime1:
00:fd:18:1e:f1:28:c6:dd:ee:56:03:db:10:88:9a:
66:02:4f:6e:1b:5c:ec:86:2b:f2:a2:d1:ed:1d:60:
67:3a:bb
prime2:
00:f6:ba:79:00:32:1c:03:9d:92:e8:a4:16:29:2b:
74:9c:0e:17:17:a0:95:0d:a6:6a:54:55:7c:98:80:
54:8b:c9
exponent1:
02:68:e8:62:83:70:e1:4c:13:a5:95:c0:62:8c:95:
cc:0f:d5:8c:8d:25:f3:61:17:be:55:21:5c:d6:3e:
25:61
exponent2:
00:ac:9c:c4:ee:a8:20:05:3f:86:7a:0f:e2:19:27:
77:cb:7d:e8:15:f5:98:92:16:2d:29:97:2d:36:1c:
02:0a:51
coefficient:
00:9b:87:71:43:f9:e2:5b:a7:96:0b:25:47:1c:db:
41:73:4a:5c:9f:d5:fb:17:86:69:92:e9:9c:c6:22:
7b:e6:e4
こんな内容になる。
上の“prime1”以降が中華風剰余定理を適用するためのデータね。あと、ZPもしくはZQで演算する場合でも Private Exponentは元のまま使っても別に構わないんだけど、たとえばZPで演算する場合、P-1 乗するごとに結果は 1 になるため、Private ExponentについてもP-1もしくはQ-1でそれぞれ剰余を取った結果が保存されてある。それがexponent1とexponent2ね。で、最後のcoefficientというのはZPおよびZQで演算した結果からZPQでの対応する要素を計算するために必要な値というわけだ。
とまぁ、こんな具合にRSAのように単純なアルゴリズムであっても、いろいろと工夫する余地があるわけで、一口にRSAと言っても実装方法にはこれまたいろいろとあり得るわけだ。実は、このような実装面での差異以外にも RSA というのは根本的な差がある二種類の定義があったりするんだが、まぁ、それに関してはまた別稿『二つの RSA って？』で。