強RSA仮定 – Wikipedia

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。 出典検索?: “強RSA仮定” – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年2月）

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

flexible RSA問題[編集]

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

n をRSAモジュラスとし、a を

Zn∗{displaystyle Z_{n}^{*}}

の元とする。
組

(b,e)∈Zn∗×Z{displaystyle (b,e)in Z_{n}^{*}times Z}

で、

a=be(modn){displaystyle a=b^{e}{pmod {n}}}

となるものを求めよ。

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

強RSA仮定[編集]

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

素数生成機

G{displaystyle G}

で次を満たすものが存在する：
任意の多項式時間アルゴリズム A に対し、

Pr(p←G(1k),q←G(1k),n←pq,a←RZn∗,(b,e)←A(n):a=bemodn∧e≠1){displaystyle mathrm {Pr} (pgets G(1^{k}),qgets G(1^{k}),ngets pq,agets _{R}Z_{n}^{*},(b,e)gets A(n):{a=b^{e}{bmod {n}}wedge eneq 1})}

はnegligible。

関連項目[編集]