強RSA仮定のソースを表示

'''強RSA仮定'''（きょうRSAかてい）とは、[[暗号理論|暗号技術]]において、[[RSA暗号]]やRSA類似の暗号方式の安全性研究に使用される仮定の一つである。

==flexible RSA問題==
次の問題を '''flexible RSA 問題'''（フレキシブル アールエスエイもんだい, flexible RSA problem）という：

''n'' を[[RSAモジュラス]]とし、''a'' を <math>Z_n^*</math> の[[元 (数学)|元]]とする。
組 <math>(b,e)\in Z^*_n\times Z</math> で、<math>a=b^e \pmod n</math> となるものを求めよ。

文献によっては flexible RSA 問題の事を'''強 RSA 問題'''（きょうアールエスエイもんだい, strong RSA problem）と呼んでいるものもある。（注：この問題は RSA 問題よりも簡単な（難しくない）ので強 RSA 問題と呼ぶのはおかしい）。

==強RSA仮定==
「flexible RSA 問題は難しい」という仮定を'''強RSA仮定'''（きょうアールエスエイかてい, strong RSA assumption）という。より正確には、以下の通り。

素数生成機 <math>G</math> で次を満たすものが存在する：
任意の[[多項式時間]][[アルゴリズム]] A に対し、
:<math>\mathrm{Pr}(p\gets G(1^k),q\gets G(1^k), n\gets pq, a\gets_R Z^*_n, (b,e)\gets A(n): {a=b^e \bmod n \wedge e\neq 1})</math>
は[[negligible]]。

==関連項目==
* [[RSA暗号]]
* [[RSAモジュラス]]
* [[RSA仮定]]
* [[暗号理論]]

[[Category:暗号技術|きようああるえすえいかてい]]