SMT Solver無しでXorshift128+を解く

先週のCBCTFではXorshift128+の32個の出力列が与えられた場合にその先を予測させる問題が出題された(Random RSA)。 想定解はSMT Solverを使うのだが、宗教上の理由で使えない人が居るかもしれないため別の解法を考えた。 なお、先に言っておくとこの解法は…

CBCTF Writeups

miyaji-labで参加した。これは暗号系研究室に所属している以上Cryptoを全完するという強い決意を表している(大嘘)。 結果としてはRandom RSAを時間中に解くことが出来なかった。悲しい。 Common Modulus 1 Common Modulus Attackをする。 Common Modulus 2…

KRACKについての私的まとめ

技術詳細を解説した日本語記事が見当たらなかったため簡単に纏める。 なお、冗長になるため断定調で書いているが怪しい箇所も多い(間違ってたら教えてください)。 あと、図は無いです(許して)。 WPA2とは何か 新しい規格である802.11iの標準化が進められ…

ICPC2017国内予選

きゅうりが消えたため、たこの友人を新しくチームメイトに加えた。 なお彼は競プロ初心者らしいのだが、頭が良いのでアジア地区では化けてくれると信じている。 僕らのチームはどちらかというと考察が得意で実装が苦手なため、初動で遅れることは予想してい…

WoTの当たり判定を色付きで表示するMODを作った

github.com 動機 最近World of Tanksという戦車ゲームにハマった。嬉しいことにこのゲームはMODを作ることを歓迎している。 戦車の装甲値などを一覧で見たかったので、csvにまとめるツールを作った。 github.com しかし、実際には戦車の装甲値は位置によって…

GCJ 2017 Round 1B

B問題をクッソバグらせて絶望していたがCが瞬殺されてギリギリ964位だった。初Round1突破っっぽいので記念に解説を書く。 A 略解 一番ゴールするのが遅い馬と同時にゴールする。 証明 一番ゴールするのが遅い馬(以下B)に注目する。 Bと自身(以下A)が同時…

Nintendo Challenge解いた

まーす氏が突然問題を送ってきた。 @aki33524 https://t.co/OdsGbvIZGS 解いて— まーす (@__math) 2017年4月9日 https://www.nerd.nintendo.com/files/HireMe.cpp 実は初日で解法分かってたのにプログラムにバグが有って数バイト書き換えたら出来てクッソし…

GCJ2017qual AをO(N)で解く

概要 長さNのbit列が与えられる。長さKの連続した列をflipして、全て1になるようにしたい。不可能ならIMPOSSIBLE、可能ならflipする最小数を答える。 略解 左から貪欲に0になっているところからflipする。背理法で証明できる。 largeケースですらなので普通…

映像研には手を出すな!がヤベエ

映像研には手を出すな!を読んだ。感想を一言で言えば、「ヤベエ漫画が出て来やがったぜ」。 それ町*1のようなハイコンテクストなギャグを挟みながら、それでいてアツい漫画だった。 まだ読んでない?一話だけならタダで読めるぞ! spi-net.jp もしまだこの漫…

競プロ勢のためのデバッグテクニック

Facebook Hacker Cup Round1の問題をオーバーフローと配列外参照で2問落としてしまい、反省を込めてデバッグテクニックを調べました。 競技勢がやらかすケアレスミスなバグの多くはこの2つだと思うので、この2つのみについて述べていきます。また、僕は普段…

tf-idfを使ったDbpediaの型推定

卒論が上手く行かないので逃避していたらまぁまぁ良さそうなので公開しておく。 前提 DbpediaとはWikipediaを元に半自動で変換したLODである。 各リソース(記事)にはclass(人とか政治家とか虫とか)が定義されたりされなかったりする。 全リソースの3割ほ…