RSA暗号体験入門
目次 | 第１章 | 第２章 | 第３章 | 第４章
本章ではRSA暗号の基本的な原理や使用法を説明します。RSA暗号はRivest，Shamir，Adleman という３人の研究者によって考案されたものであり，その名称はそれぞれの名前の頭文字を取って付けられたものです。
この暗号方式には以下のような特徴があります。
- RSA暗号方式は，公開鍵暗号の中で信頼性が高く最も広く使われている。
- RSAは暗号化も復号化も行える公開鍵暗号方式であり，鍵の長さは可変長である。
- RSAの利用者は，安全性の強化のためには長い鍵を，効率のためには短い鍵を選べばよい。
- RSAの平文の長さ（暗号化されるデータのサイズ）もまた可変長である。
- 平文の長さは，鍵の長さよりも小さい必要がある。
- 暗号文の長さは鍵の長さと同じになる。
初めは意味が分からないかもしれませんが，本章を精読後まとめとして読んで理解できれば大丈夫です。
ここからはRSA暗号の原理について説明しますが，説明文中に"＾"という記号が登場します。
これは，例えば ａ＾ｂ と表記した場合，ａのｂ乗を意味します。つまりべき乗の演算子です。
また，説明文中に頻繁に"mod"という記号が登場します。
これは例えば次のような意味として使われます。すなわち，
b = a mod n
と表記した場合，aはnを法として考えたとき，bになるという意味です。
さらに分かりやすく言うと，「aをnで割った余りはbになる」ということです。
| 具体例： |
1 = 10 mod 3 |
| 7 = 37 mod 10 |
| 5 = 53 mod 12 |
| 13 = 1234 mod 111 |
まず，暗号化を行う前に，予め以下の手順に従って秘密鍵と公開鍵を作成しておく必要があります。
- ２つの大きな素数ｐ，ｑを選択する。
- ｎ＝ｐｑとφ(ｎ)＝（ｐ−１）（ｑ−１）を計算する。
このｎを係数と呼ぶ。
- gcd（ｅ,φ(ｎ)）＝１の関係をもつ乱数ｅ（公開指数）を選択する。
ちなみにgcdとは２つの引数の最大公約数を意味する。
この公開指数ｅと係数ｎが公開鍵（ｅ,ｎ）となる。
- １＝ｄｅ mod φ(ｎ)となるｄ（秘密指数）を計算する。
この秘密指数ｄと係数ｎが秘密鍵（ｄ,ｎ）となる。
- 公開鍵（ｅ,ｎ）を公開する。ｐ，
ｑ，ｄは誰にも知られないようにしておく。
平文をＭ，暗号文をＣとすると，Ｍ＜ｎであれば，以下の関係式が必ず成り立ちます。
Ｃ＝Ｍ＾ｅ mod ｎ ・・・・・・（１）
Ｍ＝Ｃ＾ｄ mod ｎ ・・・・・・（２）
RSA暗号の原理は，これらの関係式が必ず成り立つという数学的特性を利用しています。
ただしその理由はここではあえて言及しません。
（１）が暗号化の操作，（２）が復号化の操作をそれぞれ示しています。
実は，ここでいくら暗号文Ｃ，係数ｎおよび公開指数ｅの値を知っていたとしても，
秘密指数ｄの値を知らなければ暗号文Ｃから平文Ｍを得ることは計算量的に殆ど不可能なのです。
この事がRSA暗号の安全性を保証しているわけです。
以下に，鍵の作成から暗号化，復号化までの一連の流れの例を示します。
ただし，分かりやすくするために安全でない鍵を使うものとします。
ＡさんはＢさんからネットワークを介して，ある極秘情報が記載された重要文書Ｍ
（その内容は簡単のため数値化されているとして，仮に10000であるとします）を受け取りたいとします。
そこで，ＡさんはＢさんにRSA暗号を用いて暗号化して送ってもらおうと考えます。
そのためには，Ａさんは秘密鍵（ｄ,ｎ）を，
Ｂさんはそれに対応する公開鍵（ｅ,ｎ）をそれぞれ持っていなければなりませんが，
あいにく今は持ち合わせていません。そこで，Ａさんはそれら２つの鍵を作成することにします。
- まず，２つの素数に例えばｐ＝1231，
ｑ＝4567を選びます。
（ただし，実際にはもっと大きな値にする必要があります。）
- 次に，これらを用いてｎとφ(n)を求めると，
ｎ＝1231＊4567＝5621977
φ(n)＝（1231-1）＊（4567-1）＝1230＊4566＝5616180
となります。
- 続いて，gcd（ｅ,φ(ｎ)）＝１の関係をもつ乱数ｅ（公開指数）を選択します。
（これは第３章で述べるEuclidアルゴリズムを用いて簡単に見つけられますが，
最大公約数の計算をしたい場合は桁数無制限電卓をご利用下さい。）
ただし，一般的にはｅに65537または3が使われることが多いので，
ここではｅに65537を選択しました。
確かに，gcd（65537,5616180）＝１の関係が成り立ちます。
- 次に，拡張Euclidアルゴリズム（第３章で触れますが
鍵生成アプレットを使う場合理解する必要はありません）を用いて秘密指数ｄを計算します。
つまり，ｅ＾-1＝ｄ mod φ(ｎ) のｄを計算して求めます。
ｄ＝3988493
となります。つまり，秘密鍵（ｄ,ｎ）は（3988493,5621977）となります。
- これで，公開鍵（ｅ,ｎ）と秘密鍵（ｄ,ｎ）が求まったので，
Ａさんは公開鍵（65537,5621977）だけをＢさんに知らせます。
公開鍵の正当性が保証されるような通信路であればどのような方法で知らせてもよく，
Ｅメールで送っても構いません。ただし，知らせてもよいのは公開鍵だけであり，
ｄ，ｐ，
ｑなどの値は絶対に知られてはいけません。
以上の作業は鍵生成アプレットを使うと数学的な知識なしに簡単に行えます。
Ａさんから公開鍵を受け取ったＢさんは，早速上述した暗号化の式（１）を使って，
重要文書Ｍ（内容は10000）を暗号化します。
Ｃ＝10000＾65537 mod 5621977 ∴Ｃ＝4030596
Ｂさんはこの暗号文Ｃ＝4030596をＥメールに付けて，Ａさんに送ります。
Ｂさんから送られた暗号文を受け取ったＡさんは，早速上述した暗号化の式（２）を使って，
暗号文Ｃ（内容は4030596）を復号化します。
Ｍ＝4030596＾3988493 mod 5621977 ∴Ｍ＝10000
以上のような暗号処理により，ＡさんはＢさん以外の誰にも重要文書の元の内容を知られることなく，
無事にその内容Ｍを得ることができるのです。
暗号化および復号化はRSA暗号アプレットを使って実行してください。
RSA暗号の安全性の前提は，大きな数を素因数分解するのが難しいという仮定であり，
上述した暗号化の式（１）が一方向性である，
つまり攻撃者が暗号文を復号化することが計算量的に困難であるという期待に基づいています。
また，RSA暗号はこれまで多くの人々の間で使われてきましたが，
誰もその破り方を見つけられていないということによって信頼性を得ているわけです。
もし素因数分解を簡単に行うことができれば，RSAを破ることは可能です。
公開鍵（ｅ,ｎ）を知っていて，さらにもしｎを因数分解してｐとｑを知ることができれば，
秘密指数ｄはそれらから簡単に求められます。
ただし，ｎを素因数分解することだけがRSAを破る唯一の方法かどうかは分かっていないのが現状です。
ところで，RSAの使い方を誤ると，秘密鍵を知らない者によって，
ｎを因数分解することなしに暗号文と公開鍵から平文を求められてしまう場合があります。
例えば，選挙で６人の候補者がいる場合に，
その中から一人を選んで彼の名前の文字列を暗号化して送ること（簡単な電子投票）を考えてみましょう。
その場合，送られた暗号データを盗聴した者（公開鍵（ｅ,ｎ）のみを知っている）は，
その暗号データが誰の名前を暗号化したものかが簡単に分かります。
というのは，６人の各候補者の名前をそれぞれ既知の公開鍵で暗号化してみて，
その中から盗聴した暗号データと一致するものを調べれば，
元の投票データがどの候補者の名前であるかが分かるからです。
この場合，盗聴した者は多くとも６通り試すだけで投票内容（平文）を知ることができるのです。
何故このような問題が起こるのかと言えば，RSA暗号の使い方が誤っているからなのです。
この問題は，投票内容である候補者名の前に大きな乱数を連結した上で暗号化することによって解決されます。
例えば乱数の大きさとして６４ビットを取れば，投票された暗号データを盗聴した者は，
６通りではなく6＊2＾64通りの暗号化及び比較をしなくてはならなくなります（それは計算量的に不可能）。
目次 | 第１章 | 第２章 | 第３章 | 第４章
CyberSyndrome - The Proxy Search Engine