このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

  • 追加された行はこの色です。
  • 削除された行はこの色です。
*目次 [#f2b694ab]

#contents


*RSA仮定 [#abaf5632]

[定義]~
与えられた(N,e,C)から、c=mSUP{e}; (mod N)となるmを求める問題を''RSA問題''という。

 RSA暗号が安全であるためには、素因数分解が困難でなければならならい。しかしながら、素因数分解が困難であればRSA暗号が安全かはわかっていない。よって、RSA問題(RSA暗号の解読)は素因数分解よりやさしい可能性がある。

[定義]~
RSA問題を効率的に解くアルゴリズムは存在しないとする仮定を''RSA仮定''という。

#img(http://s-akademeia.sakura.ne.jp/main/image9/rsa1.jpg)
#img(,clear)


*他の仮定との関係 [#r256a725]

 不等号は仮定の強弱を意味する。

-[[素因数分解仮定]]≦RSA仮定≦[[強RSA仮定]]