ホーム

VASS
デジカメ
小物箱
 RSA実体験
 CpxHP
 WHP
 六曜取得DLL
 98DOS
β版

M.I.B.
壁紙
マンデル

雑誌掲載
DLカウント

スペシャル
書いてけ堀
りんく



RSAの原理実地体験

動作環境Windows95/98/NT4.0
開発言語Borland Delphi3.1
種別フリーウェア
ファイルサイズ186,628 byte
最新版ダウンロードrsaex101.exe

 

 公開鍵方式の主流はRSA暗号から楕円暗号に移りつつありますが、公開鍵方式の基本であるRSAを理解しておくことは意義が有ると考え、簡単に原理を体験できるソフトを作成しました。
 ソフトを実行すると、写真のような画面が現われ、次のステップでRSAを体験できます。

1.まず1組の素数PとQを選択
 2から199の範囲の素数をプルダウンリストから選択します。PとQには異なる素数を選びます。

2.N、φ(N)、φ(N)の素因数を自動計算
 2つの素数を選ぶと、(P−1)と(Q−1)の最小公倍数であるφ(N)、φ(N)の素因数が自動的に計算され表示されます。
 Nは法(モジュロ)、φ(N)はある数をべき乗し、Nでモジュロをとったときに元の数に戻る周期になります。ちなみに、最初に現れる元の数のべき乗値はφ(N)+1になります。φ(N)の素因数は、最初の鍵Eを決定する際、共通因数が無いことを確認するためのものです。

3.最初の鍵Eを選択
 最初の鍵Eはプルダウンリストから選択します。プルダウンリストには、φ(N)より小さくて、φ(N)と互いに素(つまり共通因数が無い)数が列挙されています。
 この数と、法のNをペアにしたものが暗号鍵(公開鍵)になります。つまり、この鍵を公開しておいて、自分宛ての文書をこの鍵で暗号化して送ってもらうわけです。暗号化された文章は次に出てくる復号鍵(秘密鍵)でなければ解くことができません。
 プルダウンリストから、どれでも好みの数を決定してください。

4.2つめの鍵Dを自動決定
 1つめの鍵を決定すれば、2つめの鍵は自動的に決定されます。決定する方法は
    E×D=n×φ(N)+1
 を最小のnで満足するDを求めることです。
 DはNとペアで復号鍵(秘密鍵)になります。暗号鍵(公開鍵)で暗号化された文は、復号鍵でなければ解けません。
 このとき注意しなければならないのは、Eを選択したときにDにも同じ数があらわれることが有りますが、そのような場合はEを選択し直してください。これは矛盾しているわけではなく、ある数をべき乗してモジュロをとって選られる数(暗号化)をさらにべき乗してモジュロをとって選られた数(復号化)を求めるときに、たまたまそのべき乗数が同じになってしまっただけなのです。
 あなたは、これを公開鍵として友達(およびその他の人々)に公開します。

5.さぁ、暗号化
 2つの鍵がもとまりました。さぁ暗号化してみましょう。元の文(専門的には平文といいます)には Hello RSA. と書いてあります。ここは自由に書き換えることができますが、まずはこのままやってみましょう。
  『数値化』ボタンを押すと、1文字毎にASCII数値として表現されます。暗号化の 準備段階です。
 『Eによる暗号化』ボタンを押すと、隣の枠にカンマで区切られた数字の列が現れます。これが暗号化された数列です。
 (このとき入力された文字のASCII値よりNが小さかった場合はメッセージが出ますので、P,Qの値を大きくしたペアを選び直してください。)
 具体的には
 1)元の文から1文字(1バイト)取り出します。(何バイトを単位とするかはシステム設計に依ります。)
 2)その文字をASCII数値に置き換えます。たとえば最初の『H』は72(16進で48H)です。
 3)得られた数をEでべき乗し、Nでモジュロをとります。これが暗号化された数になります。
 4)これをすべての文字について行い、暗号化数列を得ます。
 あなたは、この暗号化された数列を友達から受け取るわけです。友達(およびその他の人々)は暗号化してしまった後はそれを復号する手段を持ちません。

6.次は復号化
 友達から受け取った暗号文を復号してみましょう。
 復号のための鍵(秘密鍵)はあなただけが知っているDとNのペアです。本ソフトでは、試験的にいろいろな数値を設定できるようになっていますが、Dを確実に入力するために『Dからコピー』ボタンがありますので、これを押してみましょう。これで、Dがきまりました。
 このDを使って復号を実行します。具体的には
 1)暗号化数列から1バイト分取り出します。
 2)その数値をDでべき乗し、Nでモジュロをとります。これで復号できます。
 3)これをすべての数列についておこない、復号化数列を得ます。
 4)この数列をASCII文字に当てはめると、元の文を復元することが出来ます。
 どうです。E(とN)で暗号化し、D(とN)で復号できたでしょう? E(とN)は公開されますが、D(とN)はあなただけが知っているわけですから、あなたの公開鍵で暗号化されたあなたあての文章は、あなた以外の誰も読むことは出来ないのです。

7.鍵を逆に使ってみよう
 RSAでは暗号鍵(公開鍵)と復号鍵(秘密鍵)の間に双方向性があります。いまの実験では暗号鍵で暗号化し、復号鍵で復号化しました。ところが、復号鍵で暗号化し、暗号鍵で復号化することも出来るのです。
 Eのプルダウンリストから先ほどのDの値を選んでください。するとDには先ほど選んだEの値が出てきます。先ほどと同じように暗号化、復号化を行うときちんともとの文に戻ることを確認してください。
 詳しい話は専門の文献に譲りますが、この性質を利用して電子署名の証明ができるのです。つまり、同じ鍵のペアを使って暗号文の生成復号、署名と証明が可能になるのです。
 念のため言っておきますが、これはあくまでも体験。ですから、ここで作った鍵は簡単に見破られてしまうでしょう。しかし、実際に使われる鍵は1024ビットとか2048ビットという巨大な鍵になります。この大きさになると誰も見破ることは出来ないのです。

モジュロテーブル  さて、一歩突っ込んでみましょう。

 モジュロテーブルというボタンがあります。これを押すとモジュロテーブルのウィンドウが表示されます。このテーブルによっていろいろなことを知ることができます。

 まず、ディフォルトで表示されるP=13、Q=17を例に取ってみましょう。
 Nは221になります。つまり221のモジュロの世界が構築されます。数値は0から220の間に存在します。これが左側一列に示されている数値です。上一列には右方向へ向かってべき乗数として取られる数値が並んでいます。1の列は1乗ですから、元の数と変わりません。2乗の列以降はべき乗した結果にN(この場合221)でモジュロを取った数値が枠内に書かれています。

 次にφ(N)は48と計算されました。48は(P−1)と(Q−1)の最小公倍数です。さらに最初に再出現するべき乗は+1つまり、49であると説明しました。
 表をスクロールさせてべき乗値49の列を見てください。あっと驚くきれいに数値が並んでいますね。そしてφ(N)である48はこの再出現の周期であると説明しました。49+48=97の列を見てください。同様にきれいに並んでいますね。RSAはこの表の性質をうまく利用しているのです。

 では、Eを35に選んだ場合で検証してみましょう。D=11になります。

1)文字『H』をASCIIで数値化すると72
2)暗号化:E=37からべき乗値35の列の72は132に変換
3)復号化:D=11からべき乗値11の列の132は72
4)72をASCII化すると『H』

 ということで、きちんと復号化できました。

 その他、表を眺めていると、いろいろな性質が判ります。例えば、べき乗値12の列などは同じ数値が出現しています。このようなべき乗値を選んだのでは復号化しようがありません。φ(N)と互いに素である数をEに選ぶことによって、このような列が選ばれることを 回避しているのです。

 P=13、Q=17の例では、Nが221という数値なのに、φ(N)が48という、比較的小さな数になってしまいました。これは、(P−1)と(Q−1)の間に比較的大きな共役数が存在するため、その最小公倍数が小さくなってしまったのです。つまり、モジュロに対して実効的な鍵が小さくなってしまうわけです。実際にRSAを運用する場合には、大きな共役数を持たないペアをできるだけ選ばないような工夫も重要になると思います。

謝辞
 V1.00 における疑問点(φ(N)+1よりも小さいべき乗で再出現する)は kob. さんの(P-1)x(Q-1) ではなく LCM( (P-1),(Q-1) ) であるという指摘によって氷解しました。どうも有り難うございました。
 しかしながら、実際には (P-1)x(Q-1) と表現している文献、WEBが数多く存在しているのも事実です。初心者にとってはじめて目に触れるであろうそれらが、一日も早くはやく修正されるよう願っています。


RSA関連の解説ページリンク
RSAセキュリティ社HP
『(新)サルにもわかるRSA暗号』 大変わかりやすいRSAの原理解説ページ


このHPは HyperEdit で作成しました。