人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

公開鍵暗号の仕組みを教えて!
ttp://www.faireal.net/articles/5/24/#d20523
ここの「鍵生成の舞台裏」の章の

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

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

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

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

●質問者: alteron
●カテゴリ:ビジネス・経営 コンピュータ
✍キーワード:.NET 24 mod ttp:// WWW
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● montagne
●40ポイント

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

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

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

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

としておきます。


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

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

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

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

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


<三つ目の質問>

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


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

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

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

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ