ホームＶＡＳＳデジカメ
小物箱
ＲＳＡ実体験
ＣｐｘＨＰＷＨＰ六曜取得DLL９８ＤＯＳβ版Ｍ．Ｉ．Ｂ．壁紙マンデル雑誌掲載DLカウントスペシャル書いてけ堀りんく
| 動作環境 | Windows95/98/NT4.0 |
| 開発言語 | Borland Delphi3.1 |
| 種別 | フリーウェア |
| ファイルサイズ | 186,628 byte |
| 最新版ダウンロード |  rsaex101.exe |
公開鍵方式の主流はＲＳＡ暗号から楕円暗号に移りつつありますが、公開鍵方式の基本であるＲＳＡを理解しておくことは意義が有ると考え、簡単に原理を体験できるソフトを作成しました。
ソフトを実行すると、写真のような画面が現われ、次のステップでＲＳＡを体験できます。
１．まず１組の素数ＰとＱを選択
２から１９９の範囲の素数をプルダウンリストから選択します。ＰとＱには異なる素数を選びます。
２．Ｎ、φ（Ｎ）、φ（Ｎ）の素因数を自動計算
２つの素数を選ぶと、（Ｐ−１）と（Ｑ−１）の最小公倍数であるφ（Ｎ）、φ（Ｎ）の素因数が自動的に計算され表示されます。
Ｎは法（モジュロ）、φ（Ｎ）はある数をべき乗し、Ｎでモジュロをとったときに元の数に戻る周期になります。ちなみに、最初に現れる元の数のべき乗値はφ（Ｎ）＋１になります。φ（Ｎ）の素因数は、最初の鍵Ｅを決定する際、共通因数が無いことを確認するためのものです。
３．最初の鍵Ｅを選択
最初の鍵Ｅはプルダウンリストから選択します。プルダウンリストには、φ（Ｎ）より小さくて、φ（Ｎ）と互いに素（つまり共通因数が無い）数が列挙されています。
この数と、法のＮをペアにしたものが暗号鍵（公開鍵）になります。つまり、この鍵を公開しておいて、自分宛ての文書をこの鍵で暗号化して送ってもらうわけです。暗号化された文章は次に出てくる復号鍵（秘密鍵）でなければ解くことができません。
プルダウンリストから、どれでも好みの数を決定してください。
４．２つめの鍵Ｄを自動決定
１つめの鍵を決定すれば、２つめの鍵は自動的に決定されます。決定する方法は
Ｅ×Ｄ＝ｎ×φ（Ｎ）＋１
を最小のｎで満足するＤを求めることです。
ＤはＮとペアで復号鍵（秘密鍵）になります。暗号鍵（公開鍵）で暗号化された文は、復号鍵でなければ解けません。
このとき注意しなければならないのは、Ｅを選択したときにＤにも同じ数があらわれることが有りますが、そのような場合はＥを選択し直してください。これは矛盾しているわけではなく、ある数をべき乗してモジュロをとって選られる数（暗号化）をさらにべき乗してモジュロをとって選られた数（復号化）を求めるときに、たまたまそのべき乗数が同じになってしまっただけなのです。
あなたは、これを公開鍵として友達（およびその他の人々）に公開します。
５．さぁ、暗号化
２つの鍵がもとまりました。さぁ暗号化してみましょう。元の文（専門的には平文といいます）には Hello RSA. と書いてあります。ここは自由に書き換えることができますが、まずはこのままやってみましょう。
『数値化』ボタンを押すと、1文字毎にＡＳＣＩＩ数値として表現されます。暗号化の 準備段階です。
『Ｅによる暗号化』ボタンを押すと、隣の枠にカンマで区切られた数字の列が現れます。これが暗号化された数列です。
（このとき入力された文字のＡＳＣＩＩ値よりＮが小さかった場合はメッセージが出ますので、Ｐ，Ｑの値を大きくしたペアを選び直してください。）
具体的には
１）元の文から１文字（１バイト）取り出します。（何バイトを単位とするかはシステム設計に依ります。）
２）その文字をＡＳＣＩＩ数値に置き換えます。たとえば最初の『H』は７２（１６進で４８H）です。
３）得られた数をＥでべき乗し、Ｎでモジュロをとります。これが暗号化された数になります。
４）これをすべての文字について行い、暗号化数列を得ます。
あなたは、この暗号化された数列を友達から受け取るわけです。友達（およびその他の人々）は暗号化してしまった後はそれを復号する手段を持ちません。
６．次は復号化
友達から受け取った暗号文を復号してみましょう。
復号のための鍵（秘密鍵）はあなただけが知っているＤとＮのペアです。本ソフトでは、試験的にいろいろな数値を設定できるようになっていますが、Ｄを確実に入力するために『Ｄからコピー』ボタンがありますので、これを押してみましょう。これで、Ｄがきまりました。
このＤを使って復号を実行します。具体的には
１）暗号化数列から１バイト分取り出します。
２）その数値をＤでべき乗し、Ｎでモジュロをとります。これで復号できます。
３）これをすべての数列についておこない、復号化数列を得ます。
４）この数列をＡＳＣＩＩ文字に当てはめると、元の文を復元することが出来ます。
どうです。Ｅ（とＮ）で暗号化し、Ｄ（とＮ）で復号できたでしょう？ Ｅ（とＮ）は公開されますが、Ｄ（とＮ）はあなただけが知っているわけですから、あなたの公開鍵で暗号化されたあなたあての文章は、あなた以外の誰も読むことは出来ないのです。
７．鍵を逆に使ってみよう
ＲＳＡでは暗号鍵（公開鍵）と復号鍵（秘密鍵）の間に双方向性があります。いまの実験では暗号鍵で暗号化し、復号鍵で復号化しました。ところが、復号鍵で暗号化し、暗号鍵で復号化することも出来るのです。
Ｅのプルダウンリストから先ほどのＤの値を選んでください。するとＤには先ほど選んだＥの値が出てきます。先ほどと同じように暗号化、復号化を行うときちんともとの文に戻ることを確認してください。
詳しい話は専門の文献に譲りますが、この性質を利用して電子署名の証明ができるのです。つまり、同じ鍵のペアを使って暗号文の生成復号、署名と証明が可能になるのです。
念のため言っておきますが、これはあくまでも体験。ですから、ここで作った鍵は簡単に見破られてしまうでしょう。しかし、実際に使われる鍵は１０２４ビットとか２０４８ビットという巨大な鍵になります。この大きさになると誰も見破ることは出来ないのです。
さて、一歩突っ込んでみましょう。モジュロテーブルというボタンがあります。これを押すとモジュロテーブルのウィンドウが表示されます。このテーブルによっていろいろなことを知ることができます。
まず、ディフォルトで表示されるＰ＝１３、Ｑ＝１７を例に取ってみましょう。
Ｎは２２１になります。つまり２２１のモジュロの世界が構築されます。数値は０から２２０の間に存在します。これが左側一列に示されている数値です。上一列には右方向へ向かってべき乗数として取られる数値が並んでいます。１の列は１乗ですから、元の数と変わりません。２乗の列以降はべき乗した結果にＮ（この場合２２１）でモジュロを取った数値が枠内に書かれています。
次にφ（Ｎ）は４８と計算されました。４８は（Ｐ−１）と（Ｑ−１）の最小公倍数です。さらに最初に再出現するべき乗は＋１つまり、４９であると説明しました。
表をスクロールさせてべき乗値４９の列を見てください。あっと驚くきれいに数値が並んでいますね。そしてφ（Ｎ）である４８はこの再出現の周期であると説明しました。４９＋４８＝９７の列を見てください。同様にきれいに並んでいますね。ＲＳＡはこの表の性質をうまく利用しているのです。
では、Ｅを３５に選んだ場合で検証してみましょう。Ｄ＝１１になります。
１）文字『Ｈ』をＡＳＣＩＩで数値化すると７２
２）暗号化：Ｅ＝３７からべき乗値３５の列の７２は１３２に変換
３）復号化：Ｄ＝１１からべき乗値１１の列の１３２は７２
４）７２をＡＳＣＩＩ化すると『Ｈ』
ということで、きちんと復号化できました。
その他、表を眺めていると、いろいろな性質が判ります。例えば、べき乗値１２の列などは同じ数値が出現しています。このようなべき乗値を選んだのでは復号化しようがありません。φ（Ｎ）と互いに素である数をＥに選ぶことによって、このような列が選ばれることを 回避しているのです。
Ｐ＝１３、Ｑ＝１７の例では、Ｎが２２１という数値なのに、φ（Ｎ）が４８という、比較的小さな数になってしまいました。これは、（Ｐ−１）と（Ｑ−１）の間に比較的大きな共役数が存在するため、その最小公倍数が小さくなってしまったのです。つまり、モジュロに対して実効的な鍵が小さくなってしまうわけです。実際にＲＳＡを運用する場合には、大きな共役数を持たないペアをできるだけ選ばないような工夫も重要になると思います。
謝辞
V1.00 における疑問点（φ(N)＋１よりも小さいべき乗で再出現する）は kob. さんの(P-1)x(Q-1) ではなく LCM( (P-1),(Q-1) ) であるという指摘によって氷解しました。どうも有り難うございました。
しかしながら、実際には (P-1)x(Q-1) と表現している文献、ＷＥＢが数多く存在しているのも事実です。初心者にとってはじめて目に触れるであろうそれらが、一日も早くはやく修正されるよう願っています。
ＲＳＡ関連の解説ページリンク
ＲＳＡセキュリティ社ＨＰ
『（新）サルにもわかるＲＳＡ暗号』 大変わかりやすいＲＳＡの原理解説ページ