第4回：素因数分解とRSA暗号

いまこれを読んでいる方で、｢7387｣という数の素因数分解を電卓使わずにできる人は何人いるでしょうか。恐らく早々いるものではないと思います。
答えは、7387 = 83 x 89 です。
たった2桁の素数の積でも道具を使わずに分解するのは厳しいでしょう。
前回の第3回でちょっと名前を出した｢RSA暗号｣はこの｢2つの素数を素因数分解する困難さ｣を暗号に利用した暗号法なのです。上の例くらいではコンピュータを用いれば0.01秒もかからずに解いてしまいますので、実際には512bit(150桁程度)から2048bit(600桁程度)の素数を用います。
桁数の計算はこのように。
桁数：N、ビット数：bとすると N = Log₁₀2^b = b x Log₁₀2

有名な暗号ソフトで｢PGP｣と言う暗号ソフトをご存知の方もいると思いますが、以前このソフトはこの暗号法を用いて暗号化していました(現在はIDEAという暗号法に変わっています)。今回はちょっとこのコンテンツの趣旨に外れる気もしますが、前回予告っぽい発言もしてしまったし、このことについて書いてみることにしました。
暗号化ソフト｢PGP｣とその作者についてはこちらをご覧ください。

この暗号法は前回説明しましたDESとは違い、鍵を公開してしまう暗号法です。鍵を公開したら暗号文が第3者に見られる心配があるのではという疑問については問題ありません。と言うのはこのタイプの暗号法は｢公開鍵｣と｢復号鍵｣の2種類の鍵を対にして持つからです。公開するのは名のとおり、公開鍵のほうです。なのでこの暗号法は｢公開鍵式暗号｣、あるいは数学的に｢非対称暗号系｣と呼ばれます。非対称と言うのは暗号化する鍵と復号する鍵が異なることからついた名前です。これに対してDESは暗号化と復号を1つの鍵で行うので｢共通鍵式暗号｣、あるいは｢対称暗号系｣と呼ばれます。
この方式は今まで本来、鍵は送受信を行う両者が持つ共通鍵1種類だったものを、公開鍵と秘密鍵の2種類にし、公開鍵はすべてのユーザーに公開して、どのユーザーにもその公開鍵で暗号文を作成し、送信してもらうのです。そして復号の際に秘密保管していた秘密鍵を使って暗号文を平文にします。この鍵を生成する際にお互いが無関係に作られては暗号復号が正確に行われないので、公開鍵の中に秘密の仕掛けを組み込んでおき、それを秘密鍵とするのです。
これによっていくつかメリットが生じます。
メリットとは鍵の少量化と管理の便利性についてです。考えてみてください。例えば50人の小規模ネットワークでそれぞれがお互いに暗号しか使わないで通信を行っている状況があるとします。そうすると全体の鍵の総量は50人が49種類の鍵を持つので2450種類です。しかもそれぞれを厳重に管理しなければなりません。1人あたり49個をそれぞれのユーザーに使い分けなくてはならないのです。これでは鍵の間違いや紛失が起こる可能性も高いですし、紛失の時には少なくとも2者間で再発行をしなければならなくて非常に煩わしい限りです。
そこで暗号形態を公開鍵暗号に変えてみたとします。
これだと暗号化の際に用いる鍵の総数は全体で50種類です。しかもそれは公開されているので保持、管理する必要はありません。使うときになったら公開してある所を参照すればいいのです。そして復号に用いる鍵の種類は誰から送られてきた文章であろうと、自分の秘密鍵を使えばいいので1種類です。実質上、鍵の管理の問題は2450種類から1種類に変わったのです。ここでは50人の小規模ネットワークを仮定していますが、インターネットを考えるとそのような場において公開鍵暗号は非常に効果的であることがお分かりでしょう。

今回のテーマであるRSA暗号は1977年にマサチューセッツ工科大学のリベスト、シャミア、アドルマンによって開発され、3人の頭文字をとって｢RSA暗号｣と名づけられました。
暗号発見の経緯は、当時リベストが｢公開鍵暗号など実現できない｣と考えており、その証明を試みていたことに始まります。その中で彼らがディフィ・へルマンの公開鍵暗号方式の問題点を探ろうとしていたとき、逆にその発想を基に優れた暗号方式が実現することを発見したと言うわけです。
当時のRSA暗号の登場は米国政府にとって衝撃的なものだったようです。RSA暗号の研究成果の発表準備を行っていたとき、国防省の人物から発表の自粛を促されました。高度な暗号技術の拡散は安全保障上好ましくないと考えられていたからです。国家安全保障局の暗号技術の優位性もこの発表によって覆されると考えたのかもしれません。

RSAの原理はこうです。
まず数字の１を考える。1は何を掛け合わせても1であるという性質があり、これをうまく利用すれば暗号に使うことができます。例えば、
1 =（1 / 2）x 2 と分解します。
1 / 2を公開鍵として、ある平文に1 / 2をかけて暗号化すれば、秘密鍵に当たる2をかければ復号できることになります。しかしこの例では誰でも秘密鍵を求めることができます。そこでオイラーの定理からnと互いに素であるMに対して、
M^φ(n) mod n = 1であることを利用します。
(φ(n)はオイラー関数と言い、１≦α＜nである整数のαのうち、nと互いに素であるαの個数を表します。)
この"mod"と言うのは｢～を法とする世界｣という意味でつまるところ、その前のオペランドを後ろのオペランドで割ったあまりを意味します。(例 : 3 ≡ 11 mod 4)この方法は現代の暗号法でよく使われます。と言うのはなんの変哲もない線形変化もこのmodというルールを適用すると途端に予測しにくい不規則な値をとるからです。
この定理を変形するとnと互いに素である自然数Mに対して、
M = M^{(k ･ φ(n) + 1)} mod n (kは任意の整数)
ここでk ･ φ(n) = ed とすると
M=(M^e)^d mod n となります。
つまりnを法とする世界でMをe乗して、さらにd乗すると元のMに戻る、ということをあらわしています。
以上のことからRSA暗号を作ると、

公開鍵 e，n　　　秘密鍵 d
平文　 M　　　　暗号文 C
暗号化 C=M^e mod n
復号化 M=C^d mod n

と置き換えられます。
nを2つの十分大きな素数p，qの積とすると、φ(n) = (p - 1)(q - 1)に互いに素となるeを選び、(e，n)を公開鍵に、秘密鍵dの方は
ed = k(p - 1)(q - 1) + 1となる数dと決定します。
暗号文の受信者には十分安全な方法で(d, n)を知らせます。
因みにオイラー関数でnはpの倍数をq個、qの倍数をp個持っているので、
φ(n) = n - p - q + 1 = pq - p - q + 1 = (p - 1)(q - 1) となります。
第三者にはもしeが知られてもφ(n)を知らないとdを求められませんし、またφ(n)を知るにはn = pqを知らなければ、すなわち膨大な素因数分解をしなければ、解を求めるのが非常に困難なのです。
この画期的な仕組みのRSAにもいくつか欠点があります。まず同じ鍵長のDESと比較したときに、暗号化に最低でも数千倍の時間がかかると言うことです。しかしこのことは裏を返せば鍵長が同じならば、解読にはそれだけ時間がかかるということで、RSAの方が強固であると言えます。実際に使用するときには、まずDES用の共通鍵をRSAで暗号化して送信し、暗号文自体はDESを使って送る、という手法がとられる事が多いようです。特に電子メールではこの方法が定着しています。またもう一つの欠点は最近になって従来は十分と思われていた256bit(80桁)の鍵長が素因数分解の研究やコンピュータの処理能力の向上から簡単に分解されるようになってしまったことです。実際に1994年には1600台のコンピュータをネットワークで介して接続し8ヶ月で129桁の素因数分解を実現しています。計算に要した演算量は5000Mips Year(Million Introductions Per Second Year)だそうです。
これらの点から鍵長は最低でも512bit（160桁）以上、十分な安全性を確保するには1024bit（300桁）以上は必要と考えられるようになりました。このアルゴリズムでさらに10年以上のライフサイクルを考えると2048bit、あるいはそれ以上に対応必要があるように思えます。

clefの連絡先はこちら↓
clef@mutt.freemail.ne.jp