Mawa Town

Mawaという人が作る小さな町でMawaTownです。技術と音楽が好き。

素因数分解パッケージmsieveのMacOSXへの導入メモ[CTF for Beginners 2018]

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

経緯

この記事を元に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
The GNU MP Bignum Library

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