SECCON 2017 Very smooth writeup / RustでP-1法素因数分解器を実装した話
TSG Advent Calendar 2017 14日目です。遅れました。
adventar.org
こないだSECCON CTFがありました。
素因数分解するだけ問題が2つありました。
Ps and Qsは自明で、Very smoothも自明のはずでした。
まず意味ありげなタイトルなので、smoothでググるわけですが、smooth numberなんかという単語がヒットします。
どうやら小さい素数の積ででてきているような数のことのようです。
素因数分解アルゴリズムについて若干でも知っていれば、ここからP-1法とかのあたりを連想するのは簡単なはずです。
ってかさっきWikipedia見たら、powersmoothって書いてありました。
で、p-1素因数分解は前実装した気もするんですが、無くしたので、
今回はツールでも探すかって"linux p-1 factor"みたいにググったら、gmp-ecmというのがヒットして、これP-1法もできるらしいんですが、なんかできない。
競技終了後にちゃんと見てみると、たぶんp-1法の亜種の2-phase algorithmを採用しているせいかなぁという気がしてきました。今回の場合最大の素数が5で、大きな素数は1つもないので。(天下り的ですが)
競技中はmoratoriumくんに頼んだら一瞬で素因数分解してくれました。
gmp-ecmは役に立たないことが判明したので、まあ実装し直すかーという話です。
言語は最近勉強しているRustです。
github.com
num::bigintつよい。しかしsqrtやlogはないっぽい。
ついでにFermat法も実装しました。これでSECCON 2014の4096bit合成数も素因数分解できます。
a4lg.com
P-1法はgmp-ecmでいうところのB1パラメタがあって、これによって計算時間が変わりますが、ソース中で1000となっています。
これでもrelease buildにすれば10秒以内に終わります。debug buildだと無限に終わりません。(いいえ)(3分です)
fermat法側は
gmpy.next_prime(3<<512) * gmpy.next_prime((3<<512) + (1<<265))
の素因数分解が秒くらいで終わりますというくらいですね。
おわりです。アンパサンドがたくさんになると、C言語病のせいで、特に初心のRustだと不安になるんですが、やっぱり筋の悪いコードなんですかね。
TSG slackbot sushibot
てぃーえすじー すらっくぼっと すしぼっと (575)
TSG advent calendar 5日目です。
adventar.org
hakatashiさんがbotの流れを作ろうとしている気がするので、書くことにしました。sushi botというbotを作りました。たった36行です。
「すし」「スシ」「寿司」を含むような寿司発言に対して「🍣:sushi:🍣」 reactionをつけます。
これによって、みんな寿司が食べたくなり、日本の経済がよくなる効果が期待できます。
こういうのをつくると、くろごま氏が「スシ」という文を投稿してきて、『スシにも対応しろ』と圧力をかけてきます。
対応すると、くろごま氏が「すシ」などを投稿してきます。
対応すると、くろごま氏が「壽司」などを投稿してきます。
対応すると、くろごま氏が「鮨」などを投稿してきます。
結局、
rtext = rtext. replace(/鮨/g, 'すし'). replace(/([Ss][Uu]|[Zz][Uu]|ス|ズ|ず|寿|壽)/g, 'す'). replace(/([Ss][Hh]?[Ii]|[Cc][Ii]|し|シ|司)/g, 'し');
とnormalizeしてから「すし」を含むものを寿司発言としました。
当然、逗子は寿司発言ではありません。
さらに、同じような戦略で実装できる追加機能として、擬akouryy発見機能もついています。
akouryy氏のつづりはなかなかむずかしいので、間違える人がよくいるとかいないとか。
そのため、擬akouryyを発見し、矯正するために、reactionをつきます。
擬akouryy発言とは、以下のnormalizeを施した後、akouryyが含まれるものです。
rtext = rtext. replace(/akouryyy/g, 'akkoury'). replace(/akouryy/g, ''). replace(/kk/g, 'k'). replace(/rr/g, 'r'). replace(/y/g, 'yy');
雑実装ですね。
ついでに、僕が凍結された頃、さらなる凍結者を出さないために、「殺」「死」発見、警告機能もついています。
これのお陰で、今のところ僕を除いて凍結者はでていません。
ところで今気づいたんですが、/[Zz]/とかって/z/iでよくないですか。
初心者がつまづいたGAEの無料枠の話
この記事を何も考えずに信用されても困りますし、それによって不利益があっても僕は知りません。ちゃんと原典にあたってください。
僕はGCP初心者です。
GAEとはGoogle App Engineの略です。
Google App Engineとは、Google Cloud Platformで提供されている、おそらく典型的にはHTTPサーバをたてるような、Webアプリを動かすためのものです。Herokuみたいなものだと思っています。
今年夏、とある事情からついにGoogle Cloud Platformに登録しました。
登録から1年間、あと280日で$300のクレジットを使い切らなくてはなりません。
しかし僕はお金を使うのが本当に不得意なので、クレジットさえも消費されると悲しくなってしまいます。
ところでGCPには無料枠というのがあり、トライアル期間中かどうかに関係なくいつまでも無料で使える枠があります。
僕の感覚からすると、無料枠でだいたい収まるアプリが、たまに枠をはみ出してクレジットをじりじり削っていくくらいがいいのです。
なにが無料枠で使えるのかというと、↓ここに細かいことは抜きにしてざっとしたことがリストになっています。
cloud.google.com
この記事の焦点はGAEなわけですが、ここでGAEの欄に書かれていることの詳細は、
欄をクリックしたここにあります。
僕は頭が悪いので、この文章の解釈がぱっとできませんでした。
そのせいで10日間で\841がクレジットから飛んでいったので、その話をします。
とんでいった料金の確認
- まずコンソールにアクセスします https://console.cloud.google.com
- メニューを出して、「お支払い」を押します。クレジットの残高はここに見えます。
- 「料金の履歴」を押します。
- 各月で、いくらか請求が発生し、その分がクレジットから引かれて、実際の請求は\0となっていることが確認できます。
ちなみに、「お支払い」で「予算とアラート」から適当に予算を作って「クレジットを予算として含める」と、クレジットが減るとメールが飛んできて悲しくなれます。
GAE無料枠の使い方
フレキシブル環境とスタンダード環境
GAEには「フレキシブル環境」と「スタンダード環境」が用意されています。
僕の重大なミスは、なんとなくフレキシブル環境を使ってしまったことでした。
今から思えば、語感から考えても「フレキシブル」のが強そう=高そうなのに、なんだか弱そうに感じてしまったのでした。
ここの文章で、「無料」を含む文章は、スタンダード環境での文脈です。
このページには28インスタンス時間が無料とありますが、これはフレキシブル環境では一切関係ありません。
Scalingの設定をして1 instanceしか起動しないように設定しようとも、ここの表の通り課金されます。
これより、スタンダード環境にない、たとえばRubyやNode.jsでアプリを書いてしまった時点で、それはGAE無料枠では動きません。
Scaling
GAEのScaling手法には、Automatic, Basic, Manualの3種類があります。
ここにあるように、Automaticに関しては28インスタンス時間が無料枠になりますが、
他のBasic, Manual scalingをとった場合、無料枠は9インスタンス時間となります。
この無料インスタンス時間の違いもそうですが、scaling手法は、単にscalingがどうなるか以外にもかなり意味を持つようなので注意しましょう。
特にここが参考になります。
インスタンスクラス
GAE Standard環境には、インスタンスクラスというのがあります。
ここに列挙されていますが、
書いてある通り、scaling手法によって使えるクラスが変わったりします。
で、無料枠との兼ね合いがどうなるのかという話で、これはちゃんと検証もせず、無責任に書くことなのですが、
今のところクラスを上げると時間が減ることを匂わせるような記述には出会っていません。
無料枠を突破したあとはクラスが高いほど高額の請求が来ることは自明なんですが、
クラスによって無料枠の長さは変わらないことが期待できるかもしれません。
設定によって無料枠を突破しない自信があるなら、高いクラスを指定してみてもよいかもしれません。
システムプログラミング実験2017
理学部情報科学科の授業です。個人的にとても楽しかった実験なので、復習しておきましょう。グダグダ書きます。
来年以降受ける人にも、若干は役に立つような記事にしたいです。(来年も同じ内容と仮定していますが)
回数は、提出回によります。(1提出 1コマとは限りません)
第1回
Makefile/shellscriptの回でした。
課題Bはたぶんアプローチが異なりうる気がするので、みんなどうやったのかは若干気になります。
事件として、この回の採点後に、採点に対する抗議が出ました。
sortを同じ引数で起動しても、人により挙動が異なるというものでした。
来年以降受ける方は、この辺を深追いしても楽しいかもしれません。原因と、挙動の妥当性とか。
まあ原因を掘り下げていけば、学科PC供給の時点で、環境が全く同じでないことが悪な気もしますが。採点者は、”環境は、学科PCの環境に準ずる”としていたはずなので。
第2回
システムコールの回でした。
getpid/syscall(SYS_getpid)などの比較をしました。
glibcもがんばってるんですね。
glibc wrapperがないsyscallを呼んでみるという課題Eは、若干興奮を覚えました。Windows Undocumented APIにハマったタイミングが昔ちょっとだけあったので、そんな気分です。
今こうやって記事を書きながら、man 2 getpidを読んで発見したんですが、NOTESになかなかおもしろいことが書いてありますね。
ずっとどうやっているのか気になっていたんですが、なるほどという感じです。
glibcのソースを追いたいときは、githubのUIに慣れていれば非公式ですがbminor/glibcとか見るといいと思います。
writeの挙動を見落としていたために弾かれた人が多かったと聞きます。
まあちゃんとスライドを読めというところですが、これ以降を考えると、man 2 writeをよく読んで、それを把握することでスライドなしでも気づきたいところです。
このread/writeの挙動は、これ以降の回でも、主にソースが汚くなるという意味で苦しめられます。
ネットワークの速度計測回では、これを考えるかどうかで結果が無意味にもなるはずなので、気をつけてください。
第3回
マルチスレッドの回でした。
個人的にはわりとがんばった回のひとつです。
課題Aで並列処理の性能上げをがんばりました。
スライドの関数一覧をよく読むと、ノードの削除はサポートする必要がありません。ここは1つの鍵かと思います。並列にできるね。
僕の私物PCは非力で、並列処理の実感があまりなかったので、ECCSを活用するなどして並列性を比較してました。
10秒が0.5秒まで改善されていくのは心地よかったです。(こなみかん)
clone syscallもなかなか闇が深くて楽しそうですね。
raw clone syscallを呼ぶときは、man 2 cloneの"The raw system call interface"をよく読みましょう。
なーにが"The raw system call interface on x86 and many other architectures is roughly:"じゃというかんじです。
BUGSにもさっきみたのと関係するようなことが書いてありますね。このへんでなんかCTF問題作れないでしょうか。
第4回
課題Aは、クライアントはわりと手抜きをしようと思えばできると思います、ユーザと対話をする方なので。
しかしサーバは、任意のUDPクライアントを仮定して、ちゃんと仕様を満たそうとするとちょっと大変な気がします。
man 7 udpを適当に読みましょう。
正直言って、どうせUDPなので、バグが入って欠損してもUDPの信頼性の無さを言い訳にするのも1つの手です。(ほんまか)
課題Bは、selectがなかなかのおもしろ関数です。
FD_ISSETとか補助関数をたくさん従えているあたりがいいですよね。
FD_SETSIZEが云々してundefined behaviorしそうな雰囲気もかなりあるので、適当に処理しましょう。
課題Cは、なにげ計測本体よりも、いかにして計測時間制限をクリアしつつ、質の高い(時間をなるべくフルに使った)計測をするかというのが悩ましいところです。
ネットワーク通信にかかる時間は、どう考えてもどことどこをどうつなぐかでオーダーが変わりうるので、その全てでまともな結果を返そうとすると、設計を頑張らないといけないでしょう。
第5-6回
シェル制作回です。
実装は泥臭いだけなので、設計ゲーですね。
慣れていない僕は、予めそれなりに時間をかけて設計を考えて、適当にいろんなstructにメンバ変数を持たせたり、片方向リストを生やしたりしてました。
どのプロセスがどんな死に方をするのかがわからないので、気を遣うのが大変で。
built-inはjobs, bg, fg, cdだけです。
どうせただのシェルなので、これはちょっと公開してみてます。GitHub - cookie-s/is17-shell
まあ、たぶんバグがあるに違いありません。
第7回
システムコールを生やします。
kmalloc/vmallocの違いをちょっとだけは感じられましたが、あんまり追えてはいません。
普通にバカなバグをやらかして、唯一の再提出を喰らいました。くっそ。。
GBオーダのデータを投げられても動くようにはがんばりました。
第8回
みんなお待ちかねのベアメタル回初回です。
かなり環境が整備されているのは間違いないのですが、やっぱりVagrantやQEMUやvncやと盛りだくさんな環境な上に、ベアメタルという特殊な状況なので、自力でデバッグ手法を開発するなどに時間を取られます。
デバッグ的な意味で、把握するべき鍵となる命令はhltです。名前から挙動を適当に想像しないで、マニュアルを一度開いてみると、これからにつながります。
ただ、時間をかける場所を間違えたということはないはずで、実際に書くコードはかなり軽いです。
SDMに触れることが目的、と言われた気がしますが、まったくその通りで、欠かすことのできない回だったと思います。
第9回
前回苦しい思いをしたあとに、文字表示ができるようにもなるし、楽しいベンチマーク取る回です。
しかもこれ、USBに焼くとUEFIで起動して、ちゃんと動くのでめっちゃ楽しい。
どでかい罠があるんですが、詳細は書きません。
僕はお人好しではないので、みんなにもハマってもらいたいからです。
1人でも多くの人にハマってもらうために、その入り口を書いておくと、2種類のカウンタってほんとうにちゃんと同じ時間を測れているんでしょうか。
まあもしこの辺についてスライドが詳しく書くようになってしまったら、ふーんという感じです。
第10回
マルチコア!!!ロック!同期!たのしい!
まず一度はロックを入れないせいでprintfが死ぬ様子を見るべきです。めっちゃ楽しい。
本当は写真を載せたいんですが、Twitter凍結されちゃって写真なくなっちゃった。
マルチコア動作を入れ始めると、QEMUと実機で動きが結構変わってくるので、実機のバグをデバッグするのが大変です。
どうすればいいということはなくて、ひたすらprintfデバッグとかをするしかないんじゃないかなぁ。
ひとつには、printfの中のロックがイケてないせいで、printfデバッグを書くとバグるというのは経験しましたが。
ひとつ情報を出しておくと、AVXを使うときには、CR4を弄ってから、XGETBV/XSETBVでXCR0を弄って有効化する必要があります。
第11回
はい。
結論
たのしい。
来年はもっと楽しくなるってTAさんがいってたので、がんばってね。
ASIS CTF Quals 2017 writeup
wasamusumeで参加しました。
最近ずっとwriteup書いてなかったけど、書く気になったので書きます。