素因数分解用Pythonモジュールprimefacの使い方

CTFをやっているとRSA暗号文の復号などで大きな数の素因数分解をする場面があります.

有名な素因数分解ツールとしてはmsieveが知られていますが,今回はPythonモジュールであるprimefacがいい感じだったので使い方をまとめておきます.

msieveについては以下のサイトなどで詳しくまとめられています.

primefacのどこがいいのか

primefacの特徴として挙げられる特徴には以下のものがあります.

  • 任意の大きさの整数を扱える(gmpyまたはgmpy2がインストールされていると尚良い)
  • ECM(楕円曲線法)を用いる
  • デフォルトで以下の異なるアルゴリズムを5並列で実行する
    1. ポラード・ロー素因数分解法のブレントによる変形版(小さな素因数を高速に抽出できる)
    2. ポラードのp-1法(p-1が小さな素数の積である場合,因数pを高速で発見できる)
    3. ウィリアムズのp+1法(p+1が小さな素数の積である場合,因数pを高速で発見できる)
    4. 楕円曲線法(p-1法の楕円曲線上版)
    5. 多項式二次ふるい法(複雑な数を因数分解するのに向いている)
  • コマンドラインから呼び出せ,逆ポーランド記法に対応している

個人的には5つの手法を並列で試してくれるので,他のツールのようにどの手法を用いるべきか自分で判断する必要がないところが魅力的です.

インストール方法

今回はDebian系ディストリビューションにPython2系でインストールします.(3系でもインストール自体はできますが,コードが2系向けに書かれており,使うとするとエラーを吐きます)

まずはgmpy2をインストールします.
gmpy2にはGMP5.0以上またはMPFR3.1以上,MCP1.0以上が必要なのでインストールします.

$ sudo apt install libgmp3-dev libmpfr2-dev libmpc-dev

gmpy2自体はpipでインストールできます.

$ pip install gmpy2 --user

primefacもpipでインストールすることが可能です.

$ pip install primefac --user

これでインストール完了です.

primefacの使いかた

基本的には素因数分解にしか使わないので,以下のようにコマンドラインから呼び出すことになると思います.

$ python -m primefac 1024
1024: 2 2 2 2 2 2 2 2 2 2

その他にも,主に素数に関する機能を提供しているので,使ってみたい方は公式の説明を読んでみるのがいいと思います.

primefacの使用例

SECCON 2017 Online CTFより,Very smooth (Crypto 300) の一部を解いてみたいと思います.この問題はpcapファイルが与えられ,そこに含まれる証明書からRSA暗号を解き,通信内容を復号するというものです.

この問題で素因数分解する数は

n = 149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897

です.
本来はタイトルのsmoothからp-1法を思いつけるかが決め手となるのですが,そんなことを知らなくても,primefacに突っ込めば

$ time python -m primefac 149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897
149767527975084886970446073530848114556615616489502613024958495602726912268566044330103850191720149622479290535294679429142532379851252608925587476670908668848275349192719279981470382501117310509432417895412013324758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897: 11807485231629132025602991324007150366908229752508016230400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 12684117323636134264468162714319298445454220244413621344524758865071052169170753552224766744798369054498758364258656141800253652826603727552918575175830897

real    0m0.499s
user    0m0.520s
sys     0m0.012s

1秒かからずに解けてしまいます.
とても便利!

おわりに

primefacはたしかに便利なのですが,全ての数の素因数分解に有効なわけではありません.例えば一般数体ふるい法などが必要となる素因数分解では(そんなものはCTFでは出題されないと思いますたい)相応の時間がかかってしまいます(というか解けない).なので素因数分解が必要な問題では,とりあえずprimefacに突っ込んでおいて,ダメそうだったら他の方法を試してみる,というのがいいかもしれません.

参考にしたサイト