hxpctf 2018にnegainoidoで参加していました。 結果は写真の通り。わたしはsh1tty_AI以外の９問を解きました。 Cryptoの問題がなかなかおもしろかったのでWriteupにまとめます。 solved uff 問題概要 NaClの署名システムにたいしてChosen Plain Text Attack…

この記事はHaskellアドベントカレンダーその２の22日目の記事です。 Haskell (その2) Advent Calendar 2017 - Qiita @rst76さんが昨日書いた記事でHaskellのリアルタイムキューがなかったので書きました。 qiita.com 12/23追記 この記事の内容に重大な誤りが…

Common Modulus 1-3 いずれもRSAを解読する問題。 \(C_1 = M^{e_1} \mod N\) \(C_2 = M^{e_2} \mod N\) が与えられる。Common Modulus 1では\(e_1, e_2\)は互いに素なので、拡張ユークリッドの互除法により \[ x e_1 + y e_2 = 1 \] となる\(x, y\)が求めら…

はじめに ある程度大きなプログラムを作ると、いろいろなログを書きだしたくものである。 しかしログというのは文字列ベースなものであり、かつプログラムの構造とは関係なく、一列に並んでしまうものである。 そのため、プログラムの中でどのような計算が行…

今回は一人で参加してました。 解いた問題 CRC crc_82_darc(data) == int(data,2) を満たすdataを作る問題。 crc_82_darcは入力データをビット列であらわしたものを\(b_{n-1} \dots b_{0}\)として（リトルエンディアン） \( f(X) = \sum^{n-1}_{i=0} b_i X^i…

negainoidoというチーム名で2人で参加してました。 順位は912ptsで53位でした。チームで解いた問題は以下のとおりです。 sanity check (Misc 1) echo (Web 200) zipper (Misc 50) logarithms are hard (Misc 10) no_mo_flo (Rev 125) pykemon (Web 151) mult…

今週末はBCTFに参加してました。一人で参加してpwn一問だけ解けたので記録しておきます。 問題概要 配布されたzipファイルにはバイナリbabyuseとlibc.soがもらえます。 $ unzip -l e1b84982-14dc-45f3-a41b-fb80b4805bd1.zip Archive: e1b84982-14dc-45f3-a4…

Japanese Version Task 解析 解法 English Version Task Analysis Solution Japanese Version Task oneTimePad1と同じように暗号化スクリプトoneTimePad2.pyとciphertxtが入ったzipファイルがもらえる。 今度は\(GF(2^{128})\)のブロック暗号システムのよう…

Japanese Version Task 解析 解法 English Version Task Analysis Solution これは0CTFのoneTimePad1という問題のWriteupです。 Japanese Version Task zipファイルを開くと暗号化スクリプトoneTimePad.pyと暗号文ciphertextがある。 暗号化の仕組みはブロッ…

今回の話題は、State MonadはStrictなものを使おうという話である。 StateT s m a HaskellでState Monadを使う際、一番よく使うのは transformer packageのStateT s m aだと思う。 transformers: Concrete functor and monad transformers あるいは、そのwra…

あらすじ プログラミング言語処理系を作成しようとすると避けては通れないのが、構文木データ型の設計である。 言語処理系では構文解析、アルファ変換、脱糖、正規化など構文木を変換するパスがいくつか存在して、それらの構文ごとにデータ型を設計しなけれ…

最近Z3のインストールに複数の意味でハマっていて、その過程で動的ライブラリに対する理解が深まったのでメモしておく。 autotaker.hatenablog.com 動的ライブラリとは 動的ライブラリは静的ライブラリと異なり、実行時にリンクされる。 今まで誤解していた…

新しいMacを手に入れたので環境構築を行っている。 その過程で、Z3のインストールにハマったので忘備録を書いておく。 目標 Z3はMicrosoftが開発しているSMTソルバで、様々な言語のバインディングがある。 公式でサポートしているのはC/C++, Java, Python, O…

Data.List.sortがあまりに遅くてつらいので、vectorを使って書いてチューニングしたら約４倍速くなりましたという話をします。その過程でvectorのmonadic indexingとは何かという話をします。仕様としてData.Listと互換性を持たせるため、次のようなインター…

先週の土曜日にSECCONの決勝大会にnegainoidoというチームで参加してきました。 SECCON 2015 決勝大会 | SECCON 2015 NEWS北千住駅から降りて東京電機大学に着くと受付にかっこいい可視化システムが置いてありました。優勝したチームdodododoは試合開始前か…

この記事はMLアドベントカレンダー22日目の記事です。 プロローグ autotakerはHaskellのList.sortが遅いので嘆いていた。 あまりに遅いので簡単なコードを書いて実験することにした。 gist082402e29104b2f21a6d $ wc test300000.in 300000 300000 2994897 te…

問題 つなぐと 2622440554406490912 + 0147433867683690946 = 4258610457570922687 などと表示される。数字は３秒おきに更新される。 解法 もらったソースを読む。 while 1: x = pow(random.randint(1000000000, 9999999999), n, (n * n)) o = (pow(n + 1, 1…

チームnegainoidoで参加しました。チームメンバーはautotaker, atetubou, cympfh, garasubo, isurugieri, tailedだった。 atetubouとtailedは台湾旅行（ICPCのアジア地区予選）中だったので遠隔参加でした。 コンテスト開始時 開始直後にatetubouがStart SEC…

概要 最近、CodeRunnerというAIコンテストの予選BでJSONデータをいじる必要が出てきたのでHaskellでJSONを読めるようにAesonを触ってみた。さらにTemplateHaskellを用いてレコード型の定義からJSONデコーダを自動導出できるようにしてみた。 背景 予選Bの問…

概要 CPS変換とはラムダ項と継続を入力として型Xを持つラムダ項を出力するプログラム変換である。 HaskellのGADTという機能を使うと型Tを持つラムダ項を表すデータ型Term Tを定義できる。 CPS変換が正しいことは cps :: Term T -> Term ([T] -> X) -> Term X…

構文木に情報を追加したいときにFix使うとちょっと楽だよっていう話。 例えば data Term = Var String | Lam String Term | App Term Termみたいなデータの各ノードにIdを振りたいとする。 ナイーブにやると data ITerm = IVar Int String | ILam Int String…

導入 以下のBNF*1は足し算とlet式からなる式を表す。 <digit> ::= [0-9] <alphabet> ::= [a-zA-Z] <int> ::= <digit> | <digit><int> <id> ::= <alphabet> | <id> <expr> ::= <int> | <id> | '(' <expr> ')' | "let" <id> '=' <expr> "in" <expr> | <expr> '+' <expr>さて、この文法には２つの曖昧性がある。一つは足し算の結合性、もう一つはlet式と足し算の優先順位の曖昧</expr></expr></expr></expr></id></expr></id></int></expr></id></alphabet></id></int></digit></digit></int></alphabet></digit>…

概要 プログラムで画像を作りたい時に便利そうなのでメモ。diagrams-svg: SVG backend for diagrams drawing EDSL. | Hackage これはHaskellでVector画像を描くライブラリである、diagramsライブラリのSVG出力ライブラリとなっている。 diagrams-lib: Embedd…

linuxの実行バイナリであるELFファイルの解析の仕方のメモIBMのスライドを参考にした。 http://www-06.ibm.com/jp/linux/tech/doc/attachments/002cb129_elf_v1_0.pdf サンプルELFの作成 まず、サンプルとなるプログラムを用意する。 // func.c #include <stdio.h> in</stdio.h>…

Haskellの話。Control.Arrow というライブラリがあるのだが、自分に取っては first, second, (***),(&&&)くらいを使うくらいのユーティリティライブラリでしかなかった。 class Category cat where id :: cat a a (.) :: cat b c -> cat a b -> cat a c (>>>…

Intro 問題の発端はこのツイートから四択の問題が全部で10問あるやつ、解答のパターンは40通りあるって、例のあの顔のカッコいい先輩に教えてもらったし、同期の男の子も40だって言ってたけど、 やっぱり納得できないヽ(；▽；)ノ数学苦手ヽ(；▽；)ノどうして…

数式の列挙問題を考えていてよくある例題として四つの数字と四則演算で１０を作るパズルを考えていた。Wikipediaによるとこの問題のことを10パズルというらしい。 wikipedia:10パズル本来やりたかったのは抽象構文木の列挙だったのだが、この問題は逆ポーラ…

先日UTPC2013に参加した。 東京大学プログラミングコンテスト2013問題CでTLEにはまったのでメモ。 問題C概要 ２つの連結グラフG_1, G_2が与えられる。 一つの辺を使ってその２つのグラフを連結するときに、連結したグラフの直径の最大値、最小値を求めよ。 …