強RSA仮定

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年4月16日 (火) 18:59時点におけるEmausBot (トーク)による版 (ボット: 言語間リンク 1 件をウィキデータ上の d:Q7624514 に転記)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

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

flexible RSA問題

次の問題を flexible RSA 問題(フレキシブル アールエスエイもんだい, flexible RSA problem)という:

nRSAモジュラスとし、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

関連項目