1978年R. L. Rivest, A. Shamir, L. M. Adleman は新しい公開鍵暗号システムを発表しました。この暗号は現在，３人の名前を取ってRSA暗号と呼ばれ，現在インターネット上で実際に 広く使われています。 ここでは，公開鍵暗号とその中で代表的な暗号である RSA暗号を紹介します。
現在使われている暗号の分類法で，共通鍵暗号，公開鍵暗号というものがあります。 暗号は 平文→（暗号化）→暗号文→（復号）→平文 のように，暗号化と復号によって構成されます。この暗号化と復号では各々鍵を使います，それらをそれぞれ暗号化鍵，復号鍵と言います。 普通の暗号は 暗号化鍵と復号鍵が同じか，一方から他方が簡単に計算できる 性質があります。この場合，暗号化鍵または復号鍵の両方を秘密にする必要があります。このような暗号を共通鍵暗号と言います。 これに対して，暗号化鍵からは復号鍵が分からない暗号を作ることができます。このような暗号では，暗号化鍵を公開しても，復号鍵は分かりません。このように 暗号化鍵を公開する暗号を公開鍵暗号 と言います。公開鍵暗号は，現在のインターネット社会では大変便利な暗号として，色々な場面で使われています。 例えば，Ｃさんがインターネットで買い物をするとします。あるＢ社にインターネットを使って商品を注文するとき，注文の内容は相手のＢ社だけに知らせて，（プライバシーの保護の視点から）他の人には分からないようにしたいと思うのは自然です。このような状況は，公開鍵暗号を使うことで実現できます。 それには，Ｂ社は公開鍵暗号を使用し， 暗号化鍵を広く公開します。 この鍵は広く公開されているので，誰でも使うことができます。そこでＣさんは この暗号化鍵を使って注文書を暗号文にします。 そしてそれをＢ社に送ります。 Ｂ社では暗号化された注文書を復号鍵を使って元の注文書に戻します。 ここで，Ｂ社以外の人或いは組織が暗号化された注文書を見たとしても，復号鍵が分からないので，元の注文書の中身は分かりません。 これが目的とするものでした。 では，暗号化鍵から，復号鍵が分からないような暗号は作れるのでしょうか？ このアイデアが始めて提案されたとき，多くの人が実現に懐疑的でした。実際，数学的に見れば，暗号化鍵と復号鍵は互いに逆写像になっています。当然ですが，逆写像は元の写像から一 通りに決ります。ですから，数学的に見れば，暗号化鍵から，復号鍵が一通りに決定します。従って，暗号化鍵から復号鍵を求めることができる筈です。 確かに理論的に見れば，暗号化鍵から復号鍵を求めることができます。しかし，ここで着目するのは理論的と言う言葉です。数学で理論的といった場合，それを計算する時間について特に断らない限り無制限です。ですから，求めることができるが，時間が大変かかると言い換えると，求める性質は数学の理論と矛盾しません。 つまり，正確に言うと， 暗号化鍵から復号鍵を求めるには大変時間がかかる というものなら作れそうです。そしてこの復号鍵を求める時間が，暗号を解読として意味が無いくらい長くかかるものであれば，実際に使うことが出来ます。 そしてこの性質を満たす暗号として始めて提案されたのがこのＲＳＡ暗号でした。 以下，ＲＳＡ暗号について説明します。現在使われている，公開鍵暗号としてはＲＳＡ暗号の他，離散対数型公開鍵暗号があります。これについては項を改めて説明します。
ｎを相異なる素数ｐ１，ｐ２，・・・，ｐｒ の積とします。 ｅ を gcd(e,φ(ｎ))=1 となる正整数とします。 ここで，φ(ｎ) は ｎのオイラー関数です。このとき，,φ(ｎ) を法とするeの逆元が存在します（整数の合同参照）。それを d （1≦d≦p-1）とします。このとき， ed ≡ 1 (mod φ(ｎ)) が成立します。従って ｘ （0≦ｘ＜ｎ）に対して，オイラーの定理から， xed≡x (mod ｎ) となります。（gcd(x,n)>0のときはオイラーの定理は使えませんが，この場合でも上の式は成立することが分かります。） 上の性質からxの範囲が0≦ｘ＜n であることを使うと，dを知っていれば，xeから x が求められることになります。従って x →（暗号化）→ xe →（復号）→ xed≡ x (mod n) によって，eを暗号化鍵，dを復号鍵とする暗号が得られます。ここまでは指数型暗号(exponentiation cipher)と よく似ています。しかし，１つだけ重要な違いがあります。それは，次のことです。 e から d を計算するとき，φ(ｎ)が必要となります。しかし他方，ｘから xe を計算するときはｎが必要ですが，φ(ｎ)は必要 はありません。さらに，ｎからφ(ｎ)を求めるには ｎの素因数分解が必要になります。 そこで次のような場合を考えます。 ｎの素因数分解が難しい場合 この場合は，仮にeを知られても，dを求めることは出来ません。つまりこの場合，e だけを知っていた場合，暗号化は出来ますが，復号は出来ません。 この場合，ｅとｎを公開し，ｄとｎの素因数分解を秘密にします。
具体的な例を使って説明しましょう。Tiny Basic で扱える範囲の数ということと，例ということから，実際に使われているものより小さい数を使います。（実際に使われるｎは数百桁という大きな整数です。） まず， p = 9010279，q = 9623083 として， n = p ×q = 86706662670157 とします。また例えば， e = 184436886841 とします。ここで，φ(n)=(p-1)*(q-1)= 86706644036796 と e との最大公約数は 1 となり，上の条件を満たします。そこで， ed ≡ 1 (mod φ(ｎ)) となるn未満の正整数 d を計算します。この計算は拡張ユークリッドの互除法を使うと高速に計算できます。実際に求めてみると， d = 70276475859277 となります。 そこで，e と n の組 (e, n) = (184436886841, 86706662670157) を公開し，n 未満の非負整数 x に対して， ｘe (mod n) によって暗号化します。例えば，x = 1234567890123 を暗号化するとします。このとき， ｘe (mod n) = 1234567890123184436886841 (mod 86706662670157) = 17175526914607 となります。この計算は冪乗法を使うと高速に計算できます。17175526914607が暗号文です。これを受け取った側は，これを d 乗してもとの文を求めます。実際，これを計算すると， 17175526914607d (mod n) = 1234567890123 が得られ，復号されたことが分かります。 d の計算には，φ(n)= 86706644036796 が必要でした。しかし，φ(n) の計算には n の素因数分解が必要です。ここで， 大きな数 n の素因数分解は大変時間がかかる ことが経験上知られています。ですから，pとqを知らない場合，φ(n) の計算は難しいことになります。 勿論，この例の数くらいであれば，すぐに因数分解できますが，１００桁も越える数が与えられたとき，その因数分解は特別なもの以外できません。
上の例をもう少し，暗号らしい形にして見ましょう。 暗号は文字などを変換して暗号化するものですから，上の例にある，数を変換するのはあまり適当ではないかもししれません。コンピュータで扱うデータの基本はバイト＝８ビットです。ですから，コンピュータで扱われる全てのデータは８ビットの列と見ることができます。この８ビット列を上の方法で，暗号化する方法を考えましょう。 上の例では，n=86706662670157でした。そこで，256 の冪でn未満の最大のものを考えます。今の場合は 2565 < 86706662670157 < 2566 ですから，5が最大冪です。そこで，5個の８ビット列を一まとまりとして
とします。ここで，各桁は１バイトですから，aからeは０から２５５までの数です。これを２５６進法で考えると， x = a・2564 + b・2563 + c・2562 + d・256 + e という数が得られます。この数は 0 ≦ x ＜ 2565 を満たします。この x に対して，上の暗号化された数 y = ｘe (mod n) を計算します。これは， 0 ≦ y ＜ 86706662670157 < 2566 を満たしますから，これを２５６進法として表すと y = f・2565 + g・2564 + h・2563 + i・2562 + j・256 + k と一通りに表されます。ここで， f から k は ０から２５５までの数です。これに対して，
と８ビット６個の列と考えて，これを暗号文とします。この方法だと， ５バイト → ６バイト の暗号化ということが出来ます。 この考えで， Basic という文字列を暗号化してみましょう。この文字列を５個の８ビット列と見ると，各文字のアスキーコードを並べて，
が得られます。これらを５桁２５６進数としてみると 66*256^4 + 97*256^3+115*256^2+105*256+99=285102795107 になります。これを暗号化すると， xe = 285102795107 184436886841 (mod 86706662670157) ≡14123999253219 が得られます。ここで 14123999253219= 12*256^5+216*256^4+127*256^3+245*256^2+82*256+227 ですから，暗号化された８ビット列は
となります。このバイト列は文字列として表示するとは出来ませんので，例えば１６進数列として表すと CD87FF552E3 となります。
RSA暗号は便利な暗号ですが，現実への適用は，効率と安全性との間の微妙でなバランスの上で成立します。ｐとｑが大きな数になればなるほど，ｎ＝ｐｑの素因数分解が難しくなり，暗号の安全性は高くなります。他方，ｐ，ｑが大きくなればなるほど，逆に計算に時間がかかり，暗号の効率は落ちます。現在では２００桁程度の数であれば，特別な性質をもつものでなければその素因数分解は難しいとされています。しかし，２００桁の数を使って上のような計算を大量に行うのは現在の計算機ででも簡単なこととは言えません。 計算をいかに効率的に行うかは工夫をする価値のあるものですが，比較的簡単な数学的原理に基づいているRSA暗号の計算法は 標準的な方法に限られます。必要な計算をまとめてみると：
１．の計算は一度だけ行えば良いので，実際は，余り問題ではありません。２と３が本質的です。 ２．暗号化では冪乗法を使って計算しますが，大きなｅに対しても冪乗法でほぼｅの桁数に比例する回数で計算できます。この回数はｅに比べて非常小さくなり，効率的な計算が可能ですが，ここで，ｎの桁数が大きいと１回の計算そのものにある程度時間がかかります。従って，効率的には計算できますが，非常に高速と言うわけには行きません。 ３．復号も基本的に２と同じですが，２より少し有利です。復号する側はｎの素因数分解を知っています。従って，各素因数についてｄ乗を冪乗法で計算して，中国の剰余定理を使って復元することが出来ます。これは，プログラムとしては複雑になりますが，高速な計算法です。この方法は実際のRSA暗号でも使われています。 これを上の例で説明します。 上の Basic と言う文字列の暗号化数 14123999253219 を復号するには，今の場合，d = 70276475859277ですから， 1412399925321970276475859277 (mod 86706662670157) を計算します。これをそのまま計算すると，答えとして 285102795107 が得られます。これをそのままではなく， ｎ＝86706662670157=9010279×9623083 に注目して， 1412399925321970276475859277 (mod 9010279) 1412399925321970276475859277 (mod 9623083) を計算するわけですが，この左辺はそれぞれｐ，ｑを法として考えればよい訳ですから，もっと簡単です。実際は，d ではなく， edp ≡ 1 (mod p-1)，edq ≡ 1 (mod q-1) となるdp=1673257，dq = 2959903 を使って， 141239992532191673257 (mod 9010279) 141239992532192959903 (mod 9623083) を計算します。この計算は，法の桁数，冪の桁数がそれぞれ半分程度になっているので，元のものより高速に計算されます。（勿論この例の場合のような桁数では関係ありません。数百桁の場合です。）計算すると， 8557268 (mod 9010279) 9338149 (mod 9623083) が得られます。これを中国の剰余定理を使って解くと求める 285102795107 が得られます。
RSA暗号は便利な暗号ですが，普通に使われる共通鍵暗号に比べて計算量が多くなります。ですから，大きなファイルを暗号化するには時間がかかり，実用上問題があります。このため，RSA暗号（一般に現在使われている公開鍵暗号）の実際上の利用の多くは，秘密鍵の送信に使われます。 公開鍵暗号（ｄを公開鍵，ｅを復号鍵）を使って，大きな文章Ｐを暗号化して送る場合を考えます。これは次のように行います。
このような方法を使えば，公開鍵暗号で大きな文章Ｐを暗号化して送ったのと同様なことになります。 上の計算に使ったプログラムRSA.tbt はここにあります。
|