SECON 2017 Online CTF Vigenere3d(Crypto, 100pt)

CTF

score-quals.seccon.jp
とりあえずググると暗号自体の説明が出てきます
ヴィジュネル暗号 - Wikipedia

  • 変換テーブルと鍵文字列の組み合わせで暗号化後の文字が決まる
  • 1文字ずつ変換するので、入力が1文字変わると出力も同じ部分が1文字だけ変わる
  • 鍵文字は周回して使われる

といったことがわかります。
今回の問題では

  • 鍵文字列が２つある
  • 鍵文字列の長さは分かっている
  • 片方の鍵文字列を前後反転させたものがもう片方の鍵文字列になる

といった点が特徴です。
鍵が14文字あるので、仮に0123456789abcdとすると

SECCON{**************************}
0123456789abcd0123456789abcd012345
dcba9876543210dcba9876543210dcba98
↓
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9

という感じになります。

また少し実験すると、鍵のn文字目と14-n文字目は和が同じであれば暗号化結果が同じになることが分かります。
この事実から最初7文字をAに固定すると

SECCON{**************************}
AAAAAAA*******AAAAAAA*******AAAAAA
*******AAAAAAA*******AAAAAAA******
↓
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9

となり、最初の7文字の暗号化結果から逆算すると
鍵がAAAAAAA_aZ2PK_となります。

すると

SECCON{**************************}
AAAAAAA_aZ2PK_AAAAAAA_aZ2PK_AAAAAA
_KP2Za_AAAAAAA_KP2Za_AAAAAAA_KP2Za
↓
POR4dnyTLHBfwbxAAZhe}}ocZR3Cxcftw9

となるのでフラグ部分の文字が逆算できます。

感想

鍵文字列の数を増やしても、長さが同じだったりそれらの間に依存関係があったりすると結局複雑性が増えなくて意味が無いですね、という学びが得られました（？）

SECON 2017 Online CTF 参加記

CTF

DDRという名前の一人チームで参加しました。
score-quals.seccon.jp
234位 / 1029位 (日本勢99位)でした。

参加するまで

CTFは存在こそ（友利奈緒さんが活躍されたりしてたので）知っていたものの、
勉強したことはなく知識皆無の状態でした（というか今もほぼ無知です）。

先月下旬に社内slackで某氏に参加を促されて「よっしゃやったろか」という気分になり
本棚に眠っていたハリネズミ本を取り出しました。
book.mynavi.jp

この読書でアセンブリの読み方とバッファオーバーフロー・format string attackの知識がつきましたが、
実際にエクスプロイトするやる気時間がなかったのでモノにできたとは言えず、
実質無勉でSECCON本番を迎えた形となりました。

コンテストの進め方

そんな感じで0点回避できればいいなくらいな感じだったので、
解いた人数が多い順・得点が低い順に取り組みました。
結局自力の通りという感じで、Powerful Shell以外は最低得点の100点の問題しか解けませんでした。

解いた問題たち

sueki.hatenablog.com
sueki.hatenablog.com
sueki.hatenablog.com
sueki.hatenablog.com
sueki.hatenablog.com
sueki.hatenablog.com
sueki.hatenablog.com


感想

何よりもまず0点覚悟していたので正の点数が取れて本当に良かったです。

競技人口が少ない

自分が普段取り組んでいる競技プログラミングは、
数年ほどやりこんでいますがオンラインコンテストで日本人200位以内に入ることは難しいです。
それに比べるとトータル1000チーム（うち日本チームは500程度）しか参加せず、
日本上位24チームが国内本戦に進めるレギュレーションはやや「おいしい」ように感じました。
（なお競技プログラミングの場合はオンサイト決勝に行けるのが学生限定の場合が非常に多いです。南無）

一人でまるで戦えないコンテストではない

分野も幅広く本当にコアな問題となったら専門家で分業する必要があるでしょうが、
他の方々のWriteupを見る限り、数十チーム解いている問題であれば
典型的なパターンを一通り抑えれば戦えるような印象を受けました。
今回コンテストのために割いたのは10時間程度だったので、
問題数的にも国内予選突破ボーダーくらいなら十分取り組む時間はあると感じました。
（もちろんWorld finalを目指すなら物量的に一人では厳しいですが）

というわけで来年は国内予選突破できるように、
プログラムやバイナリと戯れるだけでなく"SEC"CONをやれるように精進したいと思います。

Codeforces Round #273 (Div. 2) D. Red-Green Towers

Codeforces

問題

r個の赤いブロックとg個の緑色のブロックで、

1段目にn個、
2段目にn-1個、
3段目にn-2個、
・・・
N段目に1個、という三角形型のオブジェを作り上げます。
ただし、それぞれの段は全て同じ色のブロックで作らなければなりません。

　　　赤
　　緑・緑
　緑・緑・緑
赤・赤・赤・赤

例えばr=g=5のときはこんな感じのオブジェが作れます。
両方のブロック合わせて作れるオブジェの最高段数をhとしたとき、
h段のオブジェの作り方の場合の数（mod 1000000007）を求めなさい。

制約

0<=r,g<=200000
1<=r+g

続きを読む

Codeforces Round #281 (Div. 2) D. Vasya and Chess

問題
N*Nのチェス盤があって（座標は1-indexとします）、
(1,1)に自分のクイーン（飛車角両方の動きができるやつ）が、
(1,N)に相手のクイーンがいて、
残りの盤面は全部ポーンがいます。
自分のクイーンをQ、相手のクイーンをq、ポーンをPとすると、

QPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
PPPPPPPP
qPPPPPPP

こんな感じです。

自分が先攻で交互にクイーンを動かしていき、

  • 相手に自分のクイーンを取られる
  • 自分のターンにポーンが取れない

のどちらかになったら負けです。
Nが入力として与えられるので、お互い最善を尽くしたらどちらが勝つのか、自分が勝つ場合は初手でクイーンを動かす座標（複数ある場合は座標が辞書順最小となるもの）も出力しなさい。

制約
2<=N<=10^9

続きを読む

Codeforces Round #281 (Div. 2) E. Vasya and Polynomial

Codeforces

問題

多項式P(x)のうち、係数がすべて非負整数のものについて考える。すなわち、

P(x) =a_0 + a_1 * x + a_2 * x^2 + ... + a_n * x^n

としたとき、a_i>=0(0<=i<=n)となる。
３つの数t,a,bが与えられるので、P(t)=a, P(a)=bとなるような多項式P(x)の数を求めよ。

制約
1<=t,a,b<=10^18

続きを読む

2013年プロコンまとめ

競技プログラミング参加記録

レート推移

topcoder:
1245 → 1517(highest)

codeforces:
1722 → 1860(highest)

というわけで、どちらもhighest更新で終了となりました。



今年まとめ

１月：卒論の現実逃避にたまーにコンテストに出る。
４月：大学院入学。博士課程の先輩がプロコンを最近始めた勢だった。
５月くらいまで：プロコンがどうでもよくなって放置。
６月くらいから：ブログを立てる。
７月末頃から：先輩と「夏休み中にSRM,CDFのdiv1問題100問solveレース」を始める。
９月：問題数を稼ぐためにこどふぉのdiv1A相当の問題ばかり解きまくったため、greedy解法を思いつく系の簡単な問題がすんなり解けるようになった。
９月末：秋休み。先輩は100問solveを達成するも、自分は９月までに80問くらいしか解けなかった。
10月：やればやるほどレートが上がる状態になり、SRMで黄色達成。
12月：生活リズムがゴミになったせいでコンテストに出られない。


雑感

無くは無い程度のモチベでレートを更新し、地力も多少上がったと思われるので善い一年でした。
特に貪欲のゴリ押し力みたいなものがついた気がします。
SRMはもっと早解きを安定させること、
こどふぉは2問solveを安定させることでもっと高いレートを目指したいです。
SRMは「ごく稀にmediumが解ける」ようになりたいので、過去問演習を始めたいと思います。
こどふぉとは問題の出方が全然違って、SRMの問題を見ないと傾向対策が掴めない気がしてます。。。


来年の目標
SRMではレート1800、
こどふぉではレート2000を目標にします。

SRMではeasyの早解きをより安定させ、mediumをたまに解けるようになりたいです。
こどふぉではABが大体解けてCも簡単なら解ける、という状態で安定させたいですね。

テクニック的にできることとしては
・ライブラリ（gcd,bfs,ダイクストラとか）を充実させる
・グラフ関連の問題の練習、ライブラリ整備
あたりで、あとは演習量積むしかないかなと。


それではみなさんよいお年を！

TopCoder SRM600

topcoder 競技プログラミング参加記録

結果

○--　198.54pts 553rd.
1512 -> 1517

所感
easy、一瞬迷ったけどそれなりに順調に実装できたし200点あればそこそこだろうと思っていたらなんと500位台。。。
まあ確かに簡単だったので着想も実装も一瞬であるべきでしたが。
ただ、方針決まってからは下らないミスも特になく一発でテスト通っていつものようにデバッグ時間使いすぎたりしなかったのでそこはよかった。

しかしいい加減mediumの練習しないとレートに未来がないですね・・・