公開鍵暗号の仕組みを教えて!

ttp://www.faireal.net/articles/5/24/#d20523
ここの「鍵生成の舞台裏」の章の

・「エンコード用の指数αは2以上で、 (p-1)(q-1) と互いに素であるように選ぶ」なぜそのような条件で選ぶのか?

・「規則Eは、入力が違えば、必ず違うコードにエンコードしてくれる。」なぜそうなるのか?

・「秘密鍵βを、αβ≡1 (mod (p-1)(q-1))を満たすように選ぶ。」なぜそのような条件で選ぶのか?

このページの他の内容については理解できましたがここだけ分かりませんでした。要は、なぜ秘密鍵なるものが数学的に生成できるのかを知りたいです。
あまり難しい数式などではない文系的な説明なら尚歓迎です。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/10/02 02:42:44
  • 終了:--

回答(1件)

id:montagne No.1

montagne回答回数53ベストアンサー獲得回数12005/10/02 04:48:02

ポイント40pt

http://www.maitou.gr.jp/rsa/rsa10.php

サルにもわかるRSA暗号: RSA暗号の世界

Z_n:0からnまでの整数の集合

E:エンコードの関数、D:デコードの関数

としておきます。


<一つ目と二つ目の質問>

上の二つの質問は本質的には同じことを言っています。

エンコードの関数はα乗してnで割ったあまりなので、Z_nからZ_nへの関数となります。

二つ目の「入力が違えば必ず違うコードにエンコードする」というのは関数で言えば、全単射といいます。

αを適当に選んだのであれば、Eが全単射するとは限りません。Eが全単射するための条件が一つ目の質問の文中に書かれているものなのです。


<三つ目の質問>

Eはαを選ぶことにより全単射になるといいましたが、更に条件をつけると恒等写像、つまりどの数をエンコードしても元の数となるものがあります。その条件が三つ目の質問の条件にあるαβなのです。αβ乗することにより元の数に戻るのでデコードできるということになるのです。


正直言葉だけではなかなか伝わらないかもしれません。

詳しくはリンク先を参照してください。比較的平易に書かれていて、イメージをつかむことができると思います。

このリンク先のように検証するときの数値を小さいものにするとわかりやすいと思います。

これを証明するならば、整数論の知識が必要になるでしょう。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません