CTF、RSA暗号解読問題。大きな数の桁数をPythonでカウントする
サイバーセキュリティプログラミング ―Pythonで学ぶハッカーの思考
- 作者: Justin Seitz,青木一史,新井悠,一瀬小夜,岩村誠,川古谷裕平,星澤裕二
- 出版社/メーカー: オライリージャパン
- 発売日: 2015/10/24
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (11件) を見る
RSA暗号の強度はモジュロのとする数（２つの素数の積）の桁数によって変わる
これの2問目を勉強中。もう数日経過。
SECCON Beginners CTF 2018 Write-up
RSA暗号の仕組みが大枠については理解できてきた。
この記事がよかった
上記記事から引用すると、 「現在（2003 年かな？）のＲＳＡ暗号では素数と素数を掛け合わせた後（法とする数）が 310 桁以上にもなる数を用いています。」
「2003 年の年末時点では素数と素数を掛けた数が 174 桁の数が、100 台の業務用コンピュータで協調計算させて 3 ヶ月で素因数分解できることが実証されています」
つまりまとめると、
状況このサイトの引用の引用をすると、わかります。
Electronic Journal: ●「ＲＳＡ暗号は因数分解の原理使用」（ＥＪ第４６６１号）
スパコン 千倍高速コン 量子コンピュータ 因数分解／２百桁 約１０年 約３日 数分 因数分解／１万桁 約千億年 約１億年 数時間～数日 ──竹内茂樹著の前掲書より
これらが事実だとすると、量子コンピュータが実用段階に入るまではRSA暗号は単純に桁数を1万桁くらいまで増やせばいいこともわかります。なるほど・・・
CTFでの対策
以上の調査から、CTFで出てくるRSA暗号は正攻法で溶ける場合は、100桁以下で出題されそうだということがわかるので、その際の判断基準になる素数の積の桁数をpythonでちょっと測るという方法をメモしておきます。
#直感的にわかりやすい方法
>>> s = str("97139961312384239075080721131188244842051515305572003521287545456189235939577")
>>> list(s)
['9', '7', '1', '3', '9', '9', '6', '1', '3', '1', '2', '3', '8', '4', '2', '3', '9', '0', '7', '5', '0', '8', '0', '7', '2', '1', '1', '3', '1', '1', '8', '8', '2', '4', '4', '8', '4', '2', '0', '5', '1', '5', '1', '5', '3', '0', '5', '5', '7', '2', '0', '0', '3', '5', '2', '1', '2', '8', '7', '5', '4', '5', '4', '5', '6', '1', '8', '9', '2', '3', '5', '9', '3', '9', '5', '7', '7']
>>> sl = list(s)
>>> len(sl)
77
#単純に文字列にlenをかけてもでました・・・苦笑
>>> len(s)
77
77桁、これなら解ける！と判断すればいいわけですね。
最近読んだ・読み直した漫画
最近読んだ
BookOffで適当に買って読むなど。
「CAとお呼びっ！」
- 作者: 花津ハナヨ
- 出版社/メーカー: 小学館
- 発売日: 2012/09/25
- メディア: Kindle版
- この商品を含むブログを見る
これは、久しぶりに家で発見したので3巻だけ読み直した。全巻読んだけどね。ちょっともうシチュエーション自体は10年、20年前かなぁという感じはするけど、人間模様が面白い。花津ハナヨさんの作品は好き。
「僕の小規模な生活」
- 作者: 福満しげゆき
- 出版社/メーカー: 講談社
- 発売日: 2012/11/12
- メディア: Kindle版
- この商品を含むブログを見る
BookOffで見つけた。面白かった。なんかこの漫画を描くところを、漫画にしているので、なんか変な感じが面白い笑。作者がポジティブ・ネガティブな面も含めて正直なのでリアリティを感じるし、なんか応援したくなる。明るい奥さんもいい存在感だなァ。
「ヲタクに恋は難しい」
- 作者: ふじた
- 出版社/メーカー: 一迅社
- 発売日: 2015/04/30
- メディア: コミック
- この商品を含むブログ (20件) を見る
これはコンビニで買った。なんか話題作ぽかったからノリで購入。うーむ。まあ最近はファッションオタクで陽キャって人もいるよね。この作品は、ふつうのオタクでリア充ではなく卑屈になっているという設定になっているけど、ストーリーを読むと、 リア充じゃん卑屈になる必要まったくないしコミュニケーションも普通に仕事とかでも取ってるし・・・オタクとは？？ってツッコんでいた。多分時代とともにオタクの定義も多様化しているのかしら・・・
「34歳無職さん」
- 作者: いけだたかし
- 出版社/メーカー: KADOKAWA/メディアファクトリー
- 発売日: 2012/02/20
- メディア: コミック
- この商品を含むブログ (1件) を見る
自分が35歳なので、年齢が近い登場人物の漫画には反応する。状況を書くとネタバレが激しいのでオブラートに包んで書くと、女性が主人公で、仕事をしていたけど、諸々事情があり、退職、1年位貯金で過ごしてみようという方針で淡々と日常を描く作品です。起承転結はないんだけど、不思議とつい全部読んじゃいます。という不思議な魅力の作品でした。続きが気になる・・・『よつばと』とか好きな人にはおすすめできるかも^^
素因数分解パッケージ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
最近作っていたものの記録：不動産サービスの口コミサービス『Retechs』
これの開発に関わりました
最近一番大きなアプリ開発の仕事でした。明日正式オープン（もうオープンしてますけど苦笑）どのくらいかかっただろう・・・ 3ヶ月くらいか・・・これはえらい大変でした^^; 頑張ったゾウ^^/
アーキテクチャ
僕は基本的にバックエンド担当しました。もうひとりがフロントエンドを担当しています。バックエンドは下記のようなアーキテクチャです。
- インスタンス：AWS-EC2
- 静的ファイルストレージ：AWS-S3
- データベース：AWS-RDS(Postgre)
- Webサーバー：Apache
- Runtime：Python3.4(Elasticbeanstalkの対応バージョンこれが最新だから、多分。ちょっと古め)
- バックエンドのフレームワーク：Django(2.0.1)＋Django REST Framework(3.7.7)
フロントエンドは、僕よくわからないので概要しかわかりませんが、最近注目されているvue.js+firebaseでの構築とのことです。（自分も今度多少チュートリアルやってみようかな・・・）
苦労したこと
これは、WebAPIの数と、それをフロントエンドチームに伝えるためのドキュメント作りです。一人開発だと、ドキュメントはEvernoteとかにメモくらいでいいので、こういう作業発生しませんが、チーム開発となるとAPIドキュメントの良し悪しで他の人にどういう仕様で開発したかが伝わるかどうか決まる＝効率になっていくので、わかりやすくするのは大事なのですが、わかりやすくすると簡素さが失われて冗長になってしまったり、仕事時間が無限に膨れてしまうので、その兼ね合いがなかなか悩ましかったです。
このアプリ、APIの数が100超、200以下くらいになってしまったので、その分、githubにwikiでひたすらAPIのcurl例を書きまくり、その時間が開発時間の大半かなと思います。実装は全体の3割くらいです、多分。
と、いうわけで結構苦心したので、このアプリを大事に育てていきたいと思います^^/
CTF for Beginners 2018 で CTF問題演習 Crypto [Warmup] Veni, vidi, vici を解く
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
- 作者: 碓井利宣,竹迫良範,廣田一貴,保要隆明,前田優人,美濃圭佑,三村聡志,八木橋優,SECCON実行委員会
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/09/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (4件) を見る
経緯
こういう感じで、 k-mawa.hateblo.jp
とりあえず、CTFにてもっと解けるように残った問題で手習い開始。
Crypto [Warmup] Veni, vidi, vici
1：問題をダウンロードする。
次のような文字列のファイルが見える
#part1
Gur svefg cneg bs gur synt vf: pgs4o{a0zber
#part2 Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u
#part3
{ʎɥdɐɹɓ0ʇdʎᴚ :sı ɓɐlɟ ǝɥʇ ɟo ʇɹɐd pɹıɥʇ ǝɥ⊥
ふーん。経験値が少なすぎてなんじゃこりゃ・・・って感じ。part3は可読だね。逆さになってるだけだ。逆さになってる文字列を180度回転するモジュールとかあるんかしら・・・
2逆さにした文字を戻す
rot180って通称で呼ばれているようだ。原理は下記のような感じ。W→Mに変換と似ている文字を探して置換しているだけ。
pythonよく使うからpythonでできないかな。これ・・・で、ありました^^/
How to rotate a character or string by 90 or 180 degree in python? - Stack Overflow
upsidedownってモジュールかやってみよ。
$pip install upsidedown==0.3
#!python3.x系はエラー！
#python2.7.10でインストール成功
$python
Python 2.7.10
>>> import upsidedown
>>> print upsidedown.transform('hello world!')
¡pꞁɹoʍ oꞁꞁǝɥ
よしできた！やってみよう。
UnicodeDecodeError: 'ascii' codec can't decode byte 0xca in position 1: ordinal not in range(128)
ん〜もうこの辺は核心部分じゃないから、いいや。多分アルファベットくらいの対応表しか用意してなくて、十分な対応表がないんじゃないかな・・・そのメンテナンスが遊びの割に面倒だから、pythonモジュールあんまなかったのかも。ふつうにWebのツールでやろう。
一瞬でできた、楽やな^^
#part3 解決後 The third part of the flag is: Rypt0graphy}
3
part1,part2は、意味不明な文字列・・・The third part of the flag is: Rypt0graphy} をからすると、The first part of the flag is: … The second part of the flag is: …と、なりそうかなと当たりをつけることはできる。それで、文字自体は対応してないけど、区切りごとの文字数は同じ・・・つまりシーザー暗号かもね。ということで、調べてみた。
wikiわかりやすい。なるほど。アルファベットを半分にして、逆に対応させるのか。それでROT13か。なんかカッコイイな^^ ROT13 - Wikipedia
そのためのツールがpythonにはあると。今度こそpythonで解きたいよね。
#part1を解く
>>> import codecs
>>> str = "Gur svefg cneg bs gur synt vf: pgs4o{a0zber"
>>> codecs.decode(str, 'rot13')
'The first part of the flag is: ctf4b{n0more'
行けたやん！
4 part2を解く
>>> import codecs >>> str = "Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u!" >>> codecs.decode(str, 'rot13') 'Ymj xjhtsi ufwy tk ymj kqfl nx: _hQfxx!hfq_h!'
意味不明だなァ
ここでpythonの文字列の比較演算子の挙動をチェックしてみる…
>>> "a" > "b" False >>> "a" < "b" True >>> "a" < "a" False >>> "a" < "z" True >>> "a" < "B" <"z" False >>> "a" < "b" <"z" True >>> "z" < "b" <"z" False
うーむつまり、単純に文字列がアルファベット順になっていればTrueというわけか。ふーん。
さらに調べると、アスキーコードの数字の大小で調べていることがわかった。つまりこういうこと。ordは組み込みメソッド
>>> ord('A')
65
>>> ord('B')
66
>>> ord('C')
67
>>> ord('a')
97
>>> ord('b')
98
>>> ord('c')
99
つまり1文字ずらすというのは
>>> chr(ord('A') + 1)
'B'
>>> chr(ord('Z') + 1)
'['
おっと循環しているわけではないか。
>>> ord('A')
65
>>> ord('Z')
90
解説を読みながらテスト
>>> str="J"
>>> chr((ord(str) - ord('A') + 13) % 26 + ord('A'))
'W'
OK、じゃあこれで1文字〜13文字までずらした結果を導く関数をつくってみるか。コード書こう。自分でもツールを作りたいからね^^
と、いうわけで小1時間くらい書いてできた！！
#str_rot_n.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import re
def str_rot_n(strings):
strlist = list(strings)
answer_list =[]
for i in range(13):
print("[+]Info:strings rot {}...".format(i+1))
for j in strlist:
if 'A' <= j and j <= 'Z':
roted_str = chr((ord(j) - ord('A') + i+1) % 26 + ord('A'))
answer_list.append(roted_str)
if 'a' <= j and j <= 'z':
roted_str = chr((ord(j) - ord('a') + i+1) % 26 + ord('a'))
answer_list.append(roted_str)
m = re.match(r"[a-z,A-Z]", j)
if not m:
answer_list.append(j)
answer_list = ','.join(answer_list)
answer_list = answer_list.replace(",","")
print("[+]Info:strings rot {}: decode strings is '{}'".format(i+1,answer_list))
answer_list =[]
これを動かすと・・・
>>> import str_rot_n >>> str = "Lzw kwugfv hsjl gx lzw xdsy ak: _uDskk!usd_u" >>> str_rot_n.str_rot_n(str) [+]Info:strings rot 1... [+]Info:strings rot 1: decode strings is 'Max lxvhgw itkm hy max yetz bl: _vEtll!vte_v' [+]Info:strings rot 2... [+]Info:strings rot 2: decode strings is 'Nby mywihx juln iz nby zfua cm: _wFumm!wuf_w' [+]Info:strings rot 3... [+]Info:strings rot 3: decode strings is 'Ocz nzxjiy kvmo ja ocz agvb dn: _xGvnn!xvg_x' [+]Info:strings rot 4... [+]Info:strings rot 4: decode strings is 'Pda oaykjz lwnp kb pda bhwc eo: _yHwoo!ywh_y' [+]Info:strings rot 5... [+]Info:strings rot 5: decode strings is 'Qeb pbzlka mxoq lc qeb cixd fp: _zIxpp!zxi_z' [+]Info:strings rot 6... [+]Info:strings rot 6: decode strings is 'Rfc qcamlb nypr md rfc djye gq: _aJyqq!ayj_a' [+]Info:strings rot 7... [+]Info:strings rot 7: decode strings is 'Sgd rdbnmc ozqs ne sgd ekzf hr: _bKzrr!bzk_b' [+]Info:strings rot 8... [+]Info:strings rot 8: decode strings is 'The second part of the flag is: _cLass!cal_c' [+]Info:strings rot 9... [+]Info:strings rot 9: decode strings is 'Uif tfdpoe qbsu pg uif gmbh jt: _dMbtt!dbm_d' [+]Info:strings rot 10... [+]Info:strings rot 10: decode strings is 'Vjg ugeqpf rctv qh vjg hnci ku: _eNcuu!ecn_e' [+]Info:strings rot 11... [+]Info:strings rot 11: decode strings is 'Wkh vhfrqg sduw ri wkh iodj lv: _fOdvv!fdo_f' [+]Info:strings rot 12... [+]Info:strings rot 12: decode strings is 'Xli wigsrh tevx sj xli jpek mw: _gPeww!gep_g' [+]Info:strings rot 13... [+]Info:strings rot 13: decode strings is 'Ymj xjhtsi ufwy tk ymj kqfl nx: _hQfxx!hfq_h' >>>
おお！[+]Info:strings rot 8...
[+]Info:strings rot 8: decode strings is 'The second part of the flag is: _cLass!cal_c'
というわけで、最後のパーツもそろった！
The first part of the flag is: ctf4b{n0more
The second part of the flag is: _cLass!cal_c
The third part of the flag is: Rypt0graphy}
あわせて、
ctf4b{n0more_cLass!cal_cRypt0graphy}
解けたぁ！！
解説
これを読みつつ復習中 ^^/
CTF初参戦！CTF for Beginners 2018 に参加してみた
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
- 作者: 碓井利宣,竹迫良範,廣田一貴,保要隆明,前田優人,美濃圭佑,三村聡志,八木橋優,SECCON実行委員会
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/09/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (4件) を見る
CTF for Beginners 2018
参加してみた！何もわからんけど、どのくらい行けるかとりあえず参加。無料みたいだし。
１問解けたァ・・・
まあ初めてだし、１問だけでも解けたのは嬉しかった。IRCのチャットルームに行くだけ。そこの上の部分にFLAGがあるからコピペしたらOK。
順位
1問解けただけだけど、1214チーム中の823位。意外と自分みたいにとにかくチャレンジしてみようという人も多かったのかしら・・・
XSSのやつも解きたかったが、あきらめ
Webの１問目。
admin って入れると、偽管理人って$usename変数が変換されるけど、$usename == adminじゃないとFALGが出ない。javascriptコードでエスケープを避けようといろいろごちゃごちゃやるけど、時間内に出来ず。今後の課題だなぁ。POSTじゃなくてGETでもOKとのこと。この辺は勉強してるはずなのに気づかなかったくやし〜 ><
答え書いてくれてる方がいる
復習にいいな！^^/
