「ウィキペディアのRSA暗号の概要」記事へのコメント

ある程度古いものだと、普通な記述だったりするする

[miyuri (33181)]

https://ja.wikipedia.org/w/index.php?title=RSA%E6%9A%97%E5%8F%B7&o... [wikipedia.org]

まず、適当な正整数 e を選択する。

Re:

[iida (8060)]

もしeを先に選んだら、(p-1)*(q-1)とeが互いに素になるようp、qを選ばないと、dが存在しなくなってしまう。

--
iida

Re:

[miyuri (33181)]

eは素数かつ、値の範囲が適切なら何でもよかった記憶が。

#昔書いたプログラムを読むと、e = 11と決め打ちしていた

Re:ある程度古いものだと、普通な記述だったりするする

[iida (8060)]

いや、eは素数じゃなくても大丈夫。
OpenSSHとか、35を使う実装もある。
d*e≡1mod(p-1)*(q-1)になるのがだいじ。

--
iida

Re:ある程度古いものだと、普通な記述だったりするする

[miyuri (33181)]

最初にφと互いに素数なeを選んだ後、素数pとqを選ぶように書いてある。

選ぶ順番が逆ではないのか。

いや、eは素数じゃなくても大丈夫。
OpenSSHとか、35を使う実装もある。

実用的な実装の一つでは、むしろeを先に選んでいた。

#なぜかSPAM扱いになるので一部略

Re:ある程度古いものだと、普通な記述だったりするする

[iida (8060)]

確かにそういわれると、openssl genrsaでは、利用者に任意で引数でeを選択させた後、pとqを生成している。
参考になった。

--
iida

Re:

[Anonymous Coward]

mod(p-1)*(q-1)
↓
mod(p*q)

(p-1)*(q-1)は、選ぶとき互いに素にする数。