RSA

RSAについての簡単な説明

RSA公開鍵暗号は、MITの３人の数学者によって１９７７年に開発されたものです。現在RSA Data Security社が中心となり、インターネット上での一般的なデータの暗号方式として広く利用されています。あなたも知らない間に使っているかもしれません。（今このページを閲覧されているブラウザがインターネットエクスプローラーならヘルプ～バージョン情報を開いてみてください。開かれるウインドウの中の真ん中の窓をスクロールすると”Contains security software licensed from RSA Data Security Inc.”とあるはずです。）

暗号化（Encryption）と非暗号化（平文化、Decription）は、素因数分解の難しさを利用しています。まず、ある数式を使って暗号化の鍵（施錠鍵）となる数字を求めます。同様に非暗号化のための鍵（開錠鍵）も数式から求めることができます。この施錠鍵は、一般に公開され、この数字に基づいてデータの暗号化が施されます。受け取り側では、別の数字である開錠鍵をもちいて暗号化されたデータをもとのデータに戻すことができます。でも、公開されている施錠鍵では、ほとんど開錠鍵をつくることができない（論理的には可能なのですが、有限時間ではほぼできないと言えるため、作ることができないとされます。）のがこの公開鍵方式がインターネットで利用される一番の理由です。

この暗号に使われる数式とは、単純に数字のかけ算です。ただし、使う数字が素数なのです。とても大きな素数同士を掛け合わせたとき、その答えから、元の２つの素数を求めることは非常に難しいのです。この掛け合わされた数字ともう一つの数字が組になって公開される施錠鍵となります。そして、この掛け合わされた数字と別のもうひとつの数字が組になり、今度は秘密にされた開錠鍵となります。

言葉だけでは、分かりにくいので実際の数字を使って説明します。実際は、大きな素数（先のインターネットエクスプローラーなら１２８ビット　２の１２８乗・・・３９桁ほど数字）を使うのですが、目で計算が追えるように３と１１を使います。（電卓で検算をされるのなら１１桁以上の計算ができるものが必要です。）

まず、これらの数の積（N）は　N＝ｐｘｑ　で求められます。　したがって、Nは　３　ｘ　１１　＝　３３

後で計算できるよう暗号化に使われるもう一つの数Eは、　（ｐ－１）ｘ（ｑ－１）と互いに素（公約数が１のみの数字）な任意の数字が選ばれます。
PHI：（ｐ－１）ｘ（ｑ－１）は、（３－１）ｘ（１１－１）＝２０なので、今回はEを３とします。

このN（３３）とE（３）が公開される施錠鍵です。

一方、秘密の開錠鍵（D）は、PHIを法とするEの逆数と定義されます。なにやら訳の分からない話ですが、E ｘ D　＝　PHI ｘｋ　＋１を成り立たせるDとｋの整数解の組のことなので拡張ユークリッドの互除法によりこの数式は解くことができます。数式に数字を入れると

３ｘ　D ＝２０ｘｋ＋１　なのでD＝７、ｋ＝１となりますから、開錠鍵のDはこの場合７が使えます。（D＝２７、ｋ＝４など解の組み合わせは沢山あります。）もちろんこれは秘密にされる鍵です。

これで必要な鍵が揃いました。次にこれを使ってどのように暗号化＜－＞非暗号化するのかをやってみます。
今回は、アルファベットをAから順に１，２，３・・・と数字に置き換えることにします。暗号化する単語を「word」とします。

【暗号化】
wordのままでは計算式が使えませんから、数字で取り扱えるように文字を数字に置き換えます。今回はアルファベットの順番ですから、ｗ＝２３、o＝１５、ｒ＝１８、ｄ＝４とそれぞれの数字に変換できます。
暗号化は、C＝M＾E mod Nと言う式で与えられる方法で変換されます。数式をみるとややこしいようですが、「変換する文字の数字をE乗してNで割ったときの余り」と言う意味ですから、計算自身は電卓をたたいて簡単に出来る計算です。それではそれぞれの数字を計算してみましょう。

ｗ＝２３は、２３＾３ mod ３３　つまり２３ｘ２３ｘ２３（１２１６７）を３３で割ったときの余りなので、”２３”です

o＝１５は、同様に１５ｘ１５ｘ１５÷３３＝１０２・・・９だから”９”

ｒ＝１８は、１８ｘ１８ｘ１８÷３３＝１７６・・・２４なので”２４”

ｄ＝４は、４ｘ４ｘ４÷３３＝１・・・３１から”３１”

となり暗号文は、「２３０９２４３１」となります。９の前に０が入っているのは、今回の例では全て２桁以下の数字になるので、復号時に（暗号を平文化するときに）それぞれの数字を切り分けられるように全ての文字を２桁で表すために追加したものです。

【平文化】
受け取った暗号は「２３０９２４３１」ですから、この数字を各文字に当たる２桁の数字に切り分けます。この場合、４文字で”２３”、”９”、”２４”、”３１”となります。この数字は、暗号化に使われた”３”と”３３”からでは暗号化前のもの戻すことが難しいです。（今の例では、理解のため桁数が小さいので多少の手間で暗号を解くことが可能ですが、現実には上に書いたように４０桁ほどの数字なので、ほとんど解けないと言うことができます。）

さて、受け取り側では、簡単な計算でこれを元に戻すための数字（開錠鍵：D）がわかっています。今回は、７でした。
平文化の式は、C＾D mod Nで与えられます。この式の意味は、「暗号化された数字CをD乗し、Nで割ったときの余り」と言う意味です。
従って、

”２３”は、２３＾７ mod ３３　より２３ｘ２３ｘ２３ｘ２３ｘ２３ｘ２３ｘ２３（３４０４８２５４４７）を３３で割った余りなので”２３”

”９”は９ｘ９ｘ９ｘ９ｘ９ｘ９ｘ９（４７８２９６９）を３３で割った余りの”１５”

”２４”は２４ｘ２４ｘ２４ｘ２４ｘ２４ｘ２４ｘ２４（４５８６４７１４２４）÷３３から”１８”

”３１”も同様にして”４”

以上から、元の数字がそれぞれ２３，１５，１８，４であったことが上述の簡易な計算で求まり、これをテーブルで文字に変換し、元の言葉（平文）”word”に戻すことができます。

これらの説明は、ほとんど下記参考文献の受け売りです。なぜ、上記の式と数字を使えば、一意に暗号化、平文化できるのか等、バックグランドについては、下記を参照してください。また、現実の計算では上記の計算方法では計算量が大きすぎるようです。そのあたりの説明も下記の日本語のものにあります。

☆ 上記書くときに使ったの参考文献

RSAの簡単な説明とJavaScripitによる計算：http://www.orst.edu/dept/honors/makmur/

RSAを含む暗号についてのプレゼンドキュメント：http://www.cs.utah.edu/classes/cs6934/lecture/gerhard/Cryptographic.ppt（PowerPointのファイルです。）

その他の日本語で説明されているもの

サルにも分かるＲＳＡ暗号：http://www.maitou.gr.jp/rsa/
（日本語は平易ですが、数字の取り扱いは少し注意深く読む必要があります。でも、私の説明よりよくわかるように原理からかかれています。）

RSA暗号体験入門：http://www8.big.or.jp/~000/CyberSyndrome/rsa/
（上のものより詳しい分、内容が少し高度になります。）