安全素数まとめ - はまやんはまやんはまやん

色々調べたまとめ。

安全素数とは
- pと2p+1がともに素数である場合の2p+1のこと安全素数 - Wikipedia
- ちなみにこの時のpはソフィー･ジェルマン素数ソフィー・ジェルマン素数 - Wikipedia
- ソフィー・ジェルマン素数、安全素数が無数に存在するかは未解決問題（実用的にはたくさんある）
何が『安全』なのか
- 暗号理論において安全であるということ、非安全素数を使うと、離散対数問題が効率的に解かれてしまう
  - 離散対数問題を強度の要にしている以下の方式は、安全素数を使わないと危ない
  - 鍵交換方式 Diffie-Hellman
  - 暗号化方式 ElGamal
なぜ安全ではないのか
- Pohlig–Hellman algorithmというのがあり、非安全素数の場合に効率よく離散対数問題が解けてしまう
- CTFにおける離散対数問題に対するアプローチ - sonickun.log
- MMA CTF 2015: Alicegame - うさぎ小屋
- 安全素数とべき乗と逆元 - Qiita
- 間違ってる気がしてきた。いったん取り消し → ~~雰囲気を説明すると、より簡単な離散対数問題に分けることができるので高速に計算可能~~
  - ~~素数ではφ(n)=n-1なので、安全素数であればφ(n)=n-1=2p+1-1=2pとなり、2*素数で全然分割されてくれない~~
安全素数の生成方法
- 安全素数の生成方法
- ミラーラビンで素数判定して見つけるやり方が紹介されている
- 後述する所では、OpenSSLは対策パッチを出しているので、効率的な安全素数ジェネレータがある？（それか一緒？）
非安全素数を狙った攻撃
- JVNVU#95668716: OpenSSL の DH プロトコルにおける脆弱性
- OpenSSLの更新版公開、2件の脆弱性を修正 - ITmedia エンタープライズ
- アルゴリズムのダウングレードを使って、これもひっぱりだせる
- 鍵交換のDHなので、非安全素数を使うと、離散対数問題が効率よく解けて、危ない
ネタ一覧
- 素数に恋する女：第16話　素数とは安全も違法もある数である
  - 別にネタって訳でもないが、とても面白かった
  - 本になってる！素数姫の素数入門
- (20) 夕叢霧香@競プロさんはTwitterを使っています「1000000007 は安全素数だから、乗法群の要素数が 2*(素数) の形になるので、位数 (a^e=1 (mod 1000000007) を満たす最小の正の整数 e) が大きい元が多い。つまり、愚直な探索をするとTLEしやすいわ。」 / Twitter
  - たまたまなのか、狙ったのか分からないけど、面白い
  - 10⁹以上の最小の素数も1000000007だし、でも競プロだったら安全素数を狙って1000000007というのもありそう…
- 「希望ナンバー」defender_rough2のブログ｜ One Life, Live It !! - みんカラ
  - 安全素数をナンバーにする、なるほど笑
参考