ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

ラーメンに大蒜を投入しすぎてスープの味が変わってしまうことがある

はじめに

今の時代, 公開鍵のビット数がどうであろうとRSAを使うことは推奨されない. が, 今でもRSAの利用を続ける人はいる. ssh-keygenを叩くとデフォルトで出てくるのはRSA(2048 [bits])の鍵ペアだ. (2019-09-09 現在)

ビット数の大きな素数の積を素因数分解するのが困難という話は有名で, 10進数10桁と10進数1000桁なら後者の方が大変そうというのは予想できる. ビット数を大きくすることで安全性を強化できるなら, 今のビット数を2倍, 4倍, ..., としていけば安全なままにしておける. しておけるのだが, 公開鍵をネットワークに流すことを考えると大きなビット数の鍵は適切ではない.

今回は「もうRSAを使うのはやめないか」という話をしようと思う.

ビット数を大きくして嬉しいこと

  • 素因数分解の計算量が大きくなる
    先述した通り.

  • 素数の再利用が起きにくくなる
    あまり触れられることはないが実は大事な要素. もし再利用されていれば \(N_{1} := p*q_{1} \), \(N_{2} := p*q_{2} \)で\(GCD(N_{1}, N_{2}) = p \)なので簡単に素因数分解できてしまう. 公開鍵を大量に収集, もしくは自分で公開鍵を作りGCDを取り続けるという攻撃ができる.

これだけ見ると「GCDを取り続けるのは, 頑張って素因数分解するのとかかる時間にそこまで差異はないのでは?」と思われるかもしれないが, 特定の公開鍵(Moduli)を狙って素因数分解を試すのではなく, ネットワーク上の公開鍵全てに対してGCDが取れることを考えると脅威だと言える. つまり, 自分の公開鍵は簡単に素因数分解されないかもしれないが, 自分以外の誰かが共通の素数を使った公開鍵(素数の片方だけを共有)を所持していれば安全性は崩壊する.

2048 [bits]の素数より4096 [bits]の素数の方が個数が多いのだから, ビット数が大きくなれば再利用が起きにくいのは当然である.

再利用による影響

3192962個の(証明書の)公開鍵を調査し, 103のModuliがGCDによって素因数分解できた[1]. また, ある素数が46回利用されていることもわかっている. 頻度的には相当小さいが, これから同じパターンのビット列を持つ素数が他にもあるのではないかと予想が立つ. 鋭い読者はもう気づいているかもしれないが, 目当ての素数を\(p\), パターンを\(a\), 下位ビットに相当する変数\(x\)を使って多項式\(f_{p}(x) := a + x\)を構成し, coppersmith's attackによって\(N = p*q\)が素因数分解できてしまう可能性がある(上の多項式の解が求められる).

適当なパターンを取り, 持っている公開鍵全てに対してcoppersmith's attackを試し解が得られれば攻撃成功となる. 実際に[1]ではこの方法で新しく素数を得ること(素因数分解)に成功している.

この実験では素数が512 [bits]なので現行のRSAとはビット数が大きく異なるが, 成功確率が下がるだけで本質的には同じである. 4096 [bits]ということは素数のビット数は2048程度なので, 1200 [bits]くらいのパターンがあればsageMathのsmall_rootsで残りの800 [bits]がすぐに求まる.

方針としては
1. 大量の公開鍵を収集, 生成
2. 共通の素数が複数見つかったら, 上位ビットをパターンとして持っている公開鍵に対してcoppersmith's attackを試す

実際に試そうとしても, GCDで素数を見つけることが大変なので現実的な攻撃とは言えない. しかしながら”素数が再利用されていない”ことを示せない限りは脅威になり得る. 今のところRSAは「(GCD以外の方法によって)素因数分解されるかもしれない」「公開鍵をたくさん集めればGCDを取ることによって素数が得られるかもしれない」という危険性を持っている. また最初に述べたように強度のわりにビットサイズが大きい.

おわりに

ここまで言えば「RSAの公開鍵は公開しても大丈夫ではない」ことがわかってもらえたと思う.
RSAを使うのをいい加減やめよう.

本項と全く関係ないが, openssl(修正済み)でRSAの鍵を生成するときに(かなり限られた条件下で)cache-timing attackができるという報告もある.

参考

[1] Factoring RSA Keys from Certified Smart Cards: Coppersmith in the Wild