AjaxによるRSAアルゴリズム体験

こちらはAjaxによるDESアルゴリズム体験


作成目的：このページは作成者の担当する 「情報セキュリティ」（短大、2年後期開講）授業科目のために作られたもので あり、公開鍵暗号（RSA暗号）の理解のお助けになれば幸いです。各ステップを 手動で行いながら、体験してください。

1桁から9桁までの素数の生成は、「試行割算法（trial division）」によるもの で、選ばれたものは確実に素数となる。10桁以上の素数は、素数性テスト のMiller-Rabinテストによる「確率素数」である。

注：JavaScript仕様互換性の関係上、Internet Explorer6.0のブラウザ環境を利 用してください

Step 1：素数の生成
まずは、二つの異なる大きな素数pとqを選択する。作成する素数の 大きさを選択して下さい（選択した桁内の10進素数がランダム的に生成さ れる）。セキュリティ上の関係で、普通、pとqは同じ桁数の素数を使った ほうが望ましい。生成した二つの素数pとqは、公開指数と秘密指数が作成されたら、 完全に破棄してかまいません（破棄すべきである）
　１桁 　２桁 　３桁 　４桁 　５桁 　６桁 　７桁 　８桁 　９桁
　１０桁 　２０桁 　３０桁 　４０桁 　５０桁 　６０桁 　７０桁 　８０桁 　９０桁
１００桁 １１０桁 １２０桁 １３０桁 １４０桁 １５０桁 １６０桁 １７０桁 １８０桁
１９０桁 ２００桁 ２１０桁 ２２０桁 ２３０桁 ２４０桁 ２５０桁 ２６０桁 ２７０桁
２８０桁 ２９０桁 ３００桁 ３１０桁 ３２０桁 ３３０桁 ３４０桁 ３５０桁 ３６０桁
　or　 リストから素数を選択する：

　１桁 　２桁 　３桁 　４桁 　５桁 　６桁 　７桁 　８桁 　９桁
　１０桁 　２０桁 　３０桁 　４０桁 　５０桁 　６０桁 　７０桁 　８０桁 　９０桁
１００桁 １１０桁 １２０桁 １３０桁 １４０桁 １５０桁 １６０桁 １７０桁 １８０桁
１９０桁 ２００桁 ２１０桁 ２２０桁 ２３０桁 ２４０桁 ２５０桁 ２６０桁 ２７０桁
２８０桁 ２９０桁 ３００桁 ３１０桁 ３２０桁 ３３０桁 ３４０桁 ３５０桁 ３６０桁
　or　 リストから素数を選択する：

Step 2：n=p×q、及びφ(n)=(p-1)×(q-1)の計算
次に、n=p×qを計算する。このnが公開鍵と秘密鍵の一部分 となる。一般的に、数が巨大であるため、nをpとqに素因数分解するには非常 に困難（計算時間的に不可能）となる

（クライアント側処理能力とサーバ計算時間を考慮して、n≦450のときのみ利用できる）
　
更に、φ(n)=(p-1)×(q-1)を計算する

注:φ(n)=(p-1)×(q-1)=GCD(p-1, q-1)×LCM(p-1, q-1)により、ed=1 mod (p-1) ×(q-1)を求めるのに対して、ed=1 mod LCM(p-1, q-1)で置き換えることが できる。両方を試して見ましょう。

　or　

Step 3：公開指数【 e 】の選択
公開指数【 e 】（public exponent）を選ぶ（デフォルト値は 65537）。(p-1)(q-1)と互いに素な数（一般的に素数を選ぶ）eを選択する。つまり、 gcd((p-1)(q-1),e)=1を満たすような数eを求める。実際には、ある数（素 数）を選び、、ユークリッドの互除法でgcd((p-1)(q-1),e)=1を満たすかチェックすることによって決める
公開指数を入力：　or　 リストから選択：

Step 4：秘密指数【 d 】の計算
秘密指数【 d 】（private exponent）を計算する。 ed=1 mod (p-1)(q-1)となるような整数eを拡張ユークリッド互除法によっ て計算する


Step 5：暗号化する（まず、数値で 試しましょう）
これで、暗号の準備ができた。(n,e)が公開鍵であり、(n,d) は秘密鍵である。mは暗号化したい平文（ある数値）だとし、m^e mod nに よって暗号文cを生成する。cからもとのmに復号するには、c^d mod nによっ て得ることができる。

ここで、注意しなければならないのは、正しく暗号処理できる数値はnより 小さい整数である。試しにnより大きい数値で暗号化してみましょう。

nより大きい数値を暗号化できるようにしたいときはどうすればいいでしょ う？何かの方法で、大きい数値をnより小さい幾つかのブロックに分けてそ れぞれのブロックを暗号化する工夫が必要となります。

暗号化する整数【m】を入力（0≦m＜nを満たすようなものを入力してください）


Step 6：復号する
秘密鍵(n,d)を使って、暗号文cからもとの平文mを復号するには、c^d mod nによっ て得ることができる。


Step 5'：暗号化する（さあ、文章 を暗号化、復号してみましょう）
これで、暗号の準備ができた。(n,e)が公開鍵であり、(n,d) は秘密鍵である。mは暗号化したい数値だとし、m^e mod nによって暗号文c を生成する。cからもとのmに復号するには、c^d mod nによって得ることが できる。

折角ですので、実際に文章（日本語文も含めて）を暗号化、復号 してみましょう。まず、文章を暗号化できるように数値化しなければなり ません。数値化にはいろいろな方法がありますが、ここでは、文字列のバ イナリデータを利用する方法を使いました。次の手順で文章の暗号化と復 号を行なう。

「文章」
【s】		 ⇒ 「数値」
【m】		 ⇒ 「暗号化」
【c】		 ⇒ 「復号」（数値）
【dm】		 ⇒ （暗号文章のBase64文字列） ⇒「復号した文章」










Step 6'：復号する
秘密鍵(n,d)を使って、暗号文cからもとの平文mを復号するには、c^d mod nによっ て得ることができる。