強RSA仮定 – Wikipedia
|
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。2017年2月)
( |
強RSA仮定(きょうRSAかてい)とは、暗号技術において、RSA暗号やRSA類似の暗号方式の安全性研究に使用される仮定の一つである。
flexible RSA問題[編集]
次の問題を flexible RSA 問題(フレキシブル アールエスエイもんだい, flexible RSA problem)という:
n をRSAモジュラスとし、a を
Zn∗{displaystyle Z_{n}^{*}}
組
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。
Recent Comments