素因数分解パッケージmsieveのMacOSXへの導入メモ[CTF for Beginners 2018]
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
- 作者: 碓井利宣,竹迫良範,廣田一貴,保要隆明,前田優人,美濃圭佑,三村聡志,八木橋優,SECCON実行委員会
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/09/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (4件) を見る
経緯
この記事を元にCTF復習中 SECCON Beginners CTF 2018 Write-up
2問目は素因数分解するためにmsieveというパッケージがあると便利っぽいので、インストールすることになり経緯をとりあえずメモる。
手順
1:DL
DL先
https://sourceforge.net/projects/msieve/
2:DL後の解凍〜make all
#ダウンロードしたディレクトリにcd $ tar xvzf msieve153_src.tar.gz x msieve-1.53/ x msieve-1.53/aprcl/ x msieve-1.53/aprcl/jacobi_sum32.h x msieve-1.53/aprcl/mpz_aprcl32.c x msieve-1.53/aprcl/mpz_aprcl32.h ・・・ x msieve-1.53/zlib/trees.c x msieve-1.53/zlib/trees.h x msieve-1.53/zlib/uncompr.c x msieve-1.53/zlib/zconf.h x msieve-1.53/zlib/zlib.h x msieve-1.53/zlib/zutil.c x msieve-1.53/zlib/zutil.h
makeしてみる
$ cd msieve-1.53/ msieve-1.53$ ls Changes aprcl build.cuda.vc14 cub zlib Makefile bin build.vc10 demo.c Readme build.cuda.vc10 build.vc11 gnfs Readme.nfs build.cuda.vc11 build.vc14 include Readme.qs build.cuda.vc12 common mpqs msieve-1.53$ make to build: make all add 'WIN=1 if building on windows add 'WIN64=1 if building on 64-bit windows add 'ECM=1' if GMP-ECM is available (enables ECM) add 'CUDA=1' for Nvidia graphics card support add 'MPI=1' for parallel processing using MPI add 'BOINC=1' to add BOINC wrapper add 'NO_ZLIB=1' if you don't have zlib
make allってやらないとダメらしい。 ので、make all してみる
msieve-1.53$ make all gcc -O3 -fomit-frame-pointer -march=native -D_FILE_OFFSET_BITS=64 -DNDEBUG -D_LARGEFILE64_SOURCE -Wall -W -DMSIEVE_SVN_VERSION="\"Unversioned directory\"" -I. -Iaprcl -Iinclude -Ignfs -Ignfs/poly -Ignfs/poly/stage1 -c -o aprcl/mpz_aprcl32.o aprcl/mpz_aprcl32.c aprcl/mpz_aprcl32.c:37:10: fatal error: 'gmp.h' file not found #include <gmp.h> ^~~~~~~ 1 error generated. make: *** [aprcl/mpz_aprcl32.o] Error 1
参考記事と同じエラーが出てくるので想定内。gmpってのを入れよう。
3:GMPのダウンロード〜install
DL箇所はホームページ内の
Download the latest release of GMP
って言う場所のに以下のようにずらずら並んでいるリンクがあるからそれ。
GMP 6.1.2 lz, 1939430 bytes xz, 1946336 bytes bz2, 2386766 bytes Main site, gmplib.org, via https gmp-6.1.2.tar.lz gmp-6.1.2.tar.xz gmp-6.1.2.tar.bz2
そのうちのこれをクリックしてダウンロードした
gmp-6.1.2.tar.bz2
#ダウンロードしたディレクトリにcd #解凍開始 $ tar zxvf gmp-6.1.2.tar.bz2 x gmp-6.1.2/ x gmp-6.1.2/cxx/ x gmp-6.1.2/mini-gmp/ x gmp-6.1.2/Makefile.am x gmp-6.1.2/configure ・・・ x gmp-6.1.2/cxx/osmpf.cc x gmp-6.1.2/cxx/osmpq.cc x gmp-6.1.2/cxx/osmpz.cc $cd gmp-6.1.2 gmp-6.1.2$./configure gmp-6.1.2$make #ぶわーっとなにか始まる。5分くらい?時間かかる gmp-6.1.2$make check #再びぶわーっとなにか始まる。時間数分かかるかな? gmp-6.1.2$sudo make install #終わる
これでよし。
4:msieveのインストール
#msieve-1.53のディレクトリに戻る。cd msieve-1.53$ make all 再びぶわーっとなにか始まる。
5:msieve実行してみる
msieve-1.53$ ./msieve --h Msieve v. 1.53 (SVN Unversioned directory) usage: ./msieve [options] [one_number]
できたね。
試しに素因数分解もwriteupの記事のCTFの問題で出た数字のひとつについて素因数分解をやってみよう
$ ./msieve -e -p -q -v "97139961312384239075080721131188244842051515305572003521287545456189235939577" ぶわーっと始まる recovered 18 nontrivial dependencies p39 factor: 299681192390656691733849646142066664329 p39 factor: 324144336644773773047359441106332937713 elapsed time 00:02:49
おお!2分弱くらいかな!解けてるすごいね^^
参考記事
ほぼこれの通りバージョンを変えるだけでした^^ bias.hateblo.jp