読者です 読者をやめる 読者になる 読者になる

0CTF Writeup: oneTimePad2

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

0CTF Writeup: oneTimePad1

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

State Monadと正格性について

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

僕の考えたさいきょうの抽象構文木データ型

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

OS Xにおける共有ライブラリについてのメモ

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

MacにZ3をインストールした。

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

vectorを使ったData.List.sortより4倍速いsortアルゴリズムの実装

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

SECCON 2015 Final (Intercollege) 参加記

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

OCamlの末尾再帰について

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

SECCON 2015 Qual Writeup Crypto 200 Find the prime numbers

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

SECCON 2015 Qualに参加しました。

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

Template HaskellでJSONデコーダの導出

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

GADTを用いた型安全なCPS変換の実装

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

構文木にIdを振りたい。

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

let式の構文解析

導入 以下の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>さて、この文法には2つの曖昧性がある。一つは足し算の結合性、もう一つはlet式と足し算の優先順位の曖昧</expr></expr></expr></expr></id></expr></id></int></expr></id></alphabet></id></int></digit></digit></int></alphabet></digit>…

Haskell組み込みDSLでSVGを書く

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

ELF解析のはじめ

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>…

KleisliでもArrowしたい。

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

ちょまどパズルの下界が8である証明

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

10パズルを解いてみた。

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

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