iidaの日記： ウィキペディアのRSA暗号の概要

ウィキペディアのRSA暗号の概要がえらいことになっている。
最初にφと互いに素数なeを選んだ後、素数pとqを選ぶように書いてある。
「φ」はオイラーのφ(n)で、n=p*qだろう。
選ぶ順番が逆ではないのか。
それにPKCS#1では、オイラーのφ関数でなく、カーマイケルのλ関数となっている
(実際上の意味はさして変わりないが)。

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

[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)は、選ぶとき互いに素にする数。

Re:

[Anonymous Coward]

「適当な正整数 e」ではダメということですね。「適当な」は「適切な」という意味だし先にeを選ぶなら素数でないと(p-1)*(q-1)と互いに素になることが保証されなくて不適切だから明記されていなくても素数だとか数学の文章で強弁しませんよね。

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

[iida (8060)]

全整数から適当に選ぶんじゃなく、互いに素な整数から適当に選ばないとです。
偶数のeがないのは、p-1もq-1も偶数で、互いに素にならないから。

--
iida