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

学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

2の補数表現について

「2の補数表現で負の数を作るには,正の数の表現のビットを反転して1カウントアップする」という2の補数表現の解説に対する補足です.なぜこの方法で負の数を表現できるのかを補足します.

a : 32bitの整数
~a : aの反転


a + \tilde{} a = 2^{32}-1 \\
a + \tilde{} a \equiv -1 (\mod 2^{32}) \\
 -a \equiv \tilde{} a + 1 (\mod 2^{32})

というわけです.
あとはどの範囲を表現させるか決めればok.

第三回ドワンゴからの挑戦状(dwacon)参加記

予選

Aやるだけ,B問題に手間取った.B問題に手間取ったときはもうだめかと思ったが,C問題D問題が得意な感じの問題だったので助かった.E問題の部分点確定で18卒パワーを使って予選通過が決まると思ったでEの部分点を取りに行った.方針は比較的早く立ったが,苦手な感じのDPで部分点を確定させるのに手間取ってしまった.

結局32位に食い込むことができ,非18卒が上に11人以上居れば通過が確定.後日予選通過メールが届いた.

本戦

前日

オープンコンテストの告知で公開された500-1100-1200(25)-1300という配点を見て凍りつく.Acで525ptsとった後は座るだけになることが見える.変な貪欲が想定解法の500ptsだと最悪0完もあり得るなと絶望するなどしていた.

本戦開始前

集合時刻の4時間前に宿泊先のホテルを出て,部屋は清掃中の時間だし行くあて無いなーとか言いつつ歌舞伎座周辺をぶらぶら.

15時頃にドワンゴのオフィスに上がる.

集合時刻が15時というドワンゴ的かつ人道的な時間.さすがドワンゴ

受付が終わった後,控え室でTシャツを着たりニコ生用のアンケートを記入するなどする.Tシャツにタグがついていたのだけれど,はさみを持っていなかったので噛み切ろうと試みるも失敗.思いっきり引っ張ってみたらタグの糸が切れてタグを外すことができた.

準急さんやtozangezanさんが,「自己紹介書けないんだけど」と言いながら競プロerのいつものノリで会話をしていた.

コンテスト

A問題を500点と思って舐めてかかったら痛い目を見た.30分経ってもA問題の方針が見えない.辛い.正しい式にできるかどうかの判定は式が破綻した部分を数える感じで判定できることが分かったが,式の計算結果の最大化の方法が全くわからない.DPできる感じに見えなかったので必死になって貪欲を考える.

A解けないことが有り得ると思い,先にCの部分点を確保しに行く.Cの部分点は自明に二重ループ回すだけだった.35分ちょっとで25ptsを確定させる.

再びA.頭を冷やして考える.段々とDPが見えてくるが状態の持ち方がわからない.スタックの状態どうやって持つのとか言っていた.このあたりでは貪欲の可能性は完全に捨てていたが状態の持ち方が見えない.

続A.さらに冷静になって考える.O(|S|^3 * K^2)の区間DPがようやく見える.区間DPだと気付いた後の遷移のさせ方は単純なので迷わなかった.実装量はDPにしては多いと思ったが,そんなにバグる要素は無かったので落ち着いて実装.しかし答えを出力する部分で謎のbool値を出力する痛恨のミスを犯し10分ほど溶かす.死.82分ちょっとでAC.これ500ptsとは思えない.

C問題は考察しやすそうだったが,残り時間であの手の問題の実装をするのは無理だと判断し,順位表を見てBに着手する.問題設定からして「これ平方分割だよな〜」という感じの問題.いい感じの平方分割を思いついたと思ったが,実装を進めているとMLEしてしまうことに気づき無事死亡.MLE防ぐにはTLEする方法しか見えないしこれなんなんだーって言っていたらコンテストが終わった.

Acで19位.DDCCの順位も19位だったのでこの数には何かと縁がある模様.

解説

A問題の解説でchokudaiさんが「ここに居る人はこんなのサクッと通しましたよね〜」と18卒パワーで通った弱小コーダーを煽る.つらい.

B問題ついに逃げ続けてきたMo's Algorithmと向き合う日が来たのかと思った.ちゃんと勉強しようね.うん.

C問題は「なるほどね」って感じだった.コンテストが終わって実装したい感じの問題ではない.

D問題は読んで無いので解説もよくわからなかったが面白そうな雰囲気を感じたので後で解いておこうと思います.

表彰式

yutaka1999さんの名前が間違えられたのがハイライト

会社見学

社内を見せてもらえる機会があった.詳しくは書かないが,ドワンゴなるほどドワンゴという感じだった.

懇親会

タダ酒とタダ飯にありつく.人の金で飲み食いするのは楽しかった.

kobaさんやkimiyukiさんとお話しする.競プロな人とお話し.もるさんとお話ししたり,江添さんとお話ししたり,どわんごな人とお話し.

余興のぷよぷよ大会でchokudaiさんが優勝する.完全にプロ.ぷよぷよ大会の後 chokudaiさんを捕まえて,「A問題本当にあれ500ptsですか?」と聞いたところ「典型典型〜」とのこと.

あとケーキ


帰路

おひらきになったあと,ホテルまで戻る電車ではかみぺさんと一緒だった.Mo's algorithmのお話しとか「SRMのd1m埋めは効くぞ」という話しをしてもらう.「今日のA問題あれ500ptsじゃなくて800ptsぐらいあると思うんですけど」と言ったところ「800ptsも無くて多分600ptsぐらい.典型と言えば典型だし.」という意見をもらう.僕がDP苦手なだけだった.

その後,かみぺさんとお別れしホテルに戻りドワコン終了.

感想

コンテストは辛かったが,社内見学と懇親会は楽しかった.タダ飯はうまい.ドワコンのレベル的に自分が本戦に来れるとは思っていなかったので,本戦に出れたこと自体嬉しかった.

DDCC2016参加記

要約

切る削る磨くのコンテストで19位でした.

予選

A,Bやるだけ.Cは大根2に出といて助かったなという感じだった.Dはマージテクを疑いつつも解けず.18卒パワーで予選通過した.

本戦

コンテスト

配点を確認してできて3完だなーと思う.席が自由席で近くにヘクトさんゆらふなさんしょらーさんが居たので雑談してた.

A問題はやるだけだったのでやる.

B問題は冷静になって考えると,貪欲で良いことが分かるので貪欲にやると通った.27分でAC.

C問題はさすが700ptsという感じだったが,落ち着いて考察を詰めると普通に探索でとけるのでまあ700pts.61分でAC.

D問題は途中まで貪欲で詳細をDPで詰めるタイプの問題だなーと思ったのでそういう考察を詰めて実装したがWAだった.考察の方針は合ってそうだがよくわからん.

DDCC特別ビュッフェ

Discoの飯は旨い.高そうなご飯が並んでいた.チョコレートフォンデュを食べたり,t9qmib各位とお話ししたり,その他18卒の知り合いとお話ししていた.
さてさんを闇討ちするため「ドーモ,サテサン.コンジョウデス.」と挨拶する.結局闇討ちには失敗した.

厚切り.json

厚切りジェイソン氏の講演があった.芸人としての講演ではなく,IT企業役員としての講演だった.

会社見学

福利厚生施設すごい.あと,B問題の答え合わせ(物理)がDisco社によって行われた.

懇親会

1回のコンテストで2回も旨い飯が食べられるとは思ってなかった.お酒も出た.あとケーキ.

懇親会にて順位表の凍結が解除され,表彰式が行われるなどする.順位表凍結前にantaさんが全完して1位を確定させていたので完全に茶番.最終結果19位でした.

らて君やasiさんと初対面するなどする.中二双子やまるーんさんも居たが,声をかける勇気なし.らて君が久留米の人でよかった.多少声がかけやすかった.

感想

Disco含めプロコンを開いてくれる企業は良い企業です.最終結果19位はなかなかパフォーマンス出ていたと思う.ratedでなかったのが残念.コンテストの成績はまあ良いほうだったし,ご飯は美味しいしで大満足でした.

参加者の皆様,スタッフの皆様,ありがとうございました.

CODE FESTIVAL 2016 参加記

予選

予選A

インターン中だったので,インターンの滞在先から出ていた.早解きしてどうにか通過できた.10分前後で勝負が決まってしまうのってどうなの...理想を言えば予選Aでは800ptsが解けるかどうかぐらいが通過ラインになって欲しいんだけどな...

予選B

予選B通過できなかった.

予選C

予選C通過できなかった.

本戦

0日目

昨年,当日に福岡出発だと間に合わないということが実測で分かっていたので今年は前泊を申請.前泊が認められ確率統計のテストが終わった(オワタ)後東京へ飛んだ.B787に乗ってみようと思って便を取っていたのだが機材変更でB777になった.1WA.


東京に到着し,ホテルへ向かう.
京急線から大江戸線へ乗り入れている電車に乗ったのだけど「会社違うんだから当然乗り換えやろ〜〜」と言って電車を降りてしまう.同じ電車でよかったことはその電車が出発した後で気づきました.2WA.

大江戸線人形町駅日本橋駅を間違えて降りる.3WA.
東京の終電って恐ろしいですね.文字通りすし詰めで体が当たるとか荷物引っかかって人の迷惑とかそんなこと考えてたら電車から降りることができないなんて.

そうして人形町駅を降りて宿泊先のホテルへ.



宿泊先のホテルをGoogleさん勘違いしてる4WA.ちなみに,4WA目にはペナルティとしてタクシー代が1200円つきました.電車終わってたし仕方なし.

さすがにタクシーがホテルの場所を間違えることはなかった.無事にホテル到着.

1日目

本戦

105位.Ω\ζ゜)チーン

A-Dまでは割とすんなり溶けたがEが難しかった.難しかったけどパーカーがかかっていたので Convex hull で殴りにいってパーカーを獲得した.暴力的に得点を取ってしまったので反省.

tourist トーク

7歳から始める競技プログラミング
英語力が低いので内容の理解は通訳任せ.プログラミング用語含めて訳していて本業の通訳の恐るべく実力を知った.

山本一成さん講演

山本さん「みんなご飯食べてきなよ.なくなっちゃうよ.」
との計らいで開始が15分ずれ込む.寿司・肉・ピザおいしかったです.山本さんが「みんなkaggleやろうよ.なんでやってないの.」と発言したことによりTODOにkaggleが積まれた.

書道コーディング

「数弱黄色」と書いておいた.

エキシビジョン

国内プロ,海外プロ,indeedプロが3人で組んでICPC形式のエキシビジョン.海外のプロ集団の優勝不可避だと思っていた.まさかの2/3チーム0完でindeedチームの勝ちという番狂わせが起こる.たしかにindeedチームのメンバー真っ赤だけどさ,海外チームはtarget2人ですよ......完全にプロ企業.

飲み会

ホテルにチェックインしようとするとロビーでツカサさんにやざてんさんにうどんさんにほかにも知ってる競技勢と会う.みんなでお酒飲みに行こうという話をしていたところらしく,集団に加わりお酒を飲みに行った.お酒を飲みに行こうとしたところ,ホテルのロビーでtuboさんに会いさらに人数が増える.うちの大学は来年ICPCがどうとか,コンパイルコンパイラがどうとかで盛り上がった.翌日の朝プロで全滅しないように気をつけないとねなどと冗談もとぶ.

2日目

会場まで

会場まで歩いているとバタ子さんと合う.「本戦F問題1000ptsも無いですよ.さっさと解きましょ.」と煽られる.(後日解いたけど確かに1000ptsもなさそう)

トーナメント

asa!

今年はレベル別に30分,30分,40分のコンテスト3本でトーナメントをやるらしい.

トーナメント1回戦
0完.満点解が見えたので取りに行ったら実装が間に合わなかった.MSTとLCAを使う結構重めの実装だったのに満点を狙いに行ったのがだめだったらしい.

トーナメント2回戦オープン
部分点だけ.普通にDPすればよかったらしいが,DPの方針を間違えてて死.やっぱり自分は青なのだなあ.

トーナメント3回戦オープン
1完!.やったね.ついに1完できたよ.スライド最小値を実装したことはなかったのだけど,hadroriさんの書いた記事を見ながら実装したらどうにかなった.しかし,3回戦が40分だったので救われたというところがあって辛い.

お昼ご飯

あまり見ない鳥の肉のお弁当を食べた(雉?鴨?どっちだっけ).鶏肉とそんなに歯ごたえは変わらない.

体力測定

前屈をしたら腹筋を攣った.あとは右利きのはずなのに左手の方が10kg握力が強かったりとか.

りんごさんクイズ

例によって例のごとくあのノリで競プロのプロたちにクイズを出していた.地図を使ったゲームで「これ自明に勝てる手が存在するんですけど」とか言われていたのが面白かった.

リレー

gcdやるだけ問題の担当だった.
リレーにて,よすぽさんは天才ということを再確認した.

感想

こどふぇはやはりこどふぇだった.今年も面白かった.

参加者の皆様,スタッフの皆様,ありがとうございました.

WhiteHatCTF2016 WriteUp

WhiteHatCTF2016にチームHarekazeで参加しました。400点分の write up

write up

Bun cha (crypto 100pts)

やるだけ。diffie-hellmanの鍵共有でメッセージをやり取りしていたと書いてあるが、渡される暗号文やら公開鍵やら見てみるとmod取ってない。何も考えずに割ると平文が出てくる。

flag : WhiteHat{sha1(Bun_cha_ca)}

Banh cuon (crypto 200pts)

やるだけ。RSAでやりとりしたと書いてある。pもqも合成数ということが問題。しかし、p1, p2, ..., p5と怪しい数が書かれていて、試してみるとpqの(確率的素数判定で間違ってなければ)素因数はp1, p2, ..., p5, (pq) / (p1*p2*...*p5) の6つであるとわかる。あとはRSAと同じ理屈でeの逆元をmod phi(pq) = (p1 - 1) * (p2 - 1) * ... でとればよい。

flag : WhiteHat{ff94658cf7612e7f68de6d960caf6f9b92e8a4a4}

English version

需要があるようなので英語版の解説もつけときますね.
Sorry for my poor English skill.

Solution is simple.
We should notice the fact p and q are composite number. There are suspicious numbers p1 to p5. In fact, p1 to p5 are divisor of product of p and q. Moreover, p1, p2, …, p5 and (pq)/(p_1 p_2 p_3 p_4 p_5) are prime. Thus, the prime factorization of pq is p_1 p_2 p_3 p_4 p_5 ( (pq) / (p_1 p_2 p_3 p_4 p_5) ) .

So, we could calculate d such as  ed \equiv 1 (\mod \phi(pq)) and decipher the cipher text c by calculate c^d (\mod pq).

The flag is WhiteHat{ff94658cf7612e7f68de6d960caf6f9b92e8a4a4}

Banh da Ke (misc 100pts)

やるだけ。対話的なプログラムがサーバの上で走っていて、コマンドを実行してくれる。ただし、catやlessやheadなどのコマンドは受け付けない。0 - 9999 の10000個のディレクトリの中に"乱数.乱数"という名前のファイルがフラグ文字列の長さと同じ数だけ作られ、そのそれぞれにフラグの文字がひとつづつ書き込まれている。なお、ファイルに書き込まれる文字のフラグ文字列中での順序と、フラグの文字が書き込まれたディレクトリの数の順序は一致する。

catが使えなければgrepを使えばいいじゃない。ということで grep -r "." で dirname/filename/:Fの形式の出力が得られる。あとはディレクトリ名をキーにしてソートしてフラグを復元するだけ。

flag : WhiteHat{sha1(WhiteHat{ke3p_c4lm_4nD_try_h4rd})}

WhiteHat{}ごとsha1とらないといけないところが悪質。

感想

自明問しか解けてなくてつらい。

SECCON2016qual 参加記

プログラミング 雑記 CTF

はじめに

SECCON2016予選にチームHarekazeの黒木洋美として参戦していました。

普段は競技プログラミングをしているのですが、ある日hiwwさんからお誘いいただきCTFに参加することになりました。

(現在の記事は速報版です)
2016/12/12 深夜 更新(未完。まあちまちま完成に向けて更新していきます。)
2016/12/15 完成?

結果

個人的0完。延長戦でcrypt200pts Backpacker's Capricious Cipher を解いたので解説(CTF界隈ではWriteUpと言うらしい?)を貼っておきます。コンテスト中は競技の知識に付け焼刃でなんとかなりそうな暗号問に取り組んでました。

Backpacker's Capricious Cipher (crypt 200pts) 解法

解法概要

つらいやるだけ。手計算をがんばる。オイラーフェルマーの小定理を知っていれば小学生でも解ける。

問題概要

暗号化/復号用のソースコードと、公開鍵と暗号文が渡されるので復号してくださいという問題。暗号化のアルゴリズムは部分和問題の難しさを拠り所にしたものでした。後述しますが、この問題の場合はナップザック問題を解くことなく復号できます。

蛇足。同じく部分和問題の難しさを拠り所にした暗号にはナップザック暗号というものがあるらしいです(チームメイトが教えてくれました)。しかし、この問題の暗号はナップザック暗号ではないようです。これは次の理由によります。Wikipediaの解説によればナップザック暗号は超増加数列というものを利用するらしいのですが、ナップザック暗号で用いる素数Pは使用する超増加列の総和よりも大きく選ぶ必要があります。数列の和が最小となるような超増加列は\{1,2,4,8,16,32,...\}と、初項1、公比2の等比数列であり(このことは帰納法で証明できる)、その総和は長さNの超増加列では2^N-1となります。ところがこの問題で与えられるパラメータを見てみると、2^N -1 \gt Pでありナップザック暗号のPの選び方からは外れていることがわかります(ナップザック暗号だという勘違いを防ぐいいヒントですね!)。よって、この問題がナップザック暗号ではなく、別の何かの方法で暗号化されていてこれを復号する必要があるということがわかります。ナップザック暗号だと思って時間を溶かした各位は反省しましょう。

暗号化手法(配布されたコード中での)

私のような脳みそ空っぽ人間にはrubyで書かれた元のコードは難しすぎた。ということで、cipher.rbと等価なコードをpythonで書きました(等価になってるはず?)。python固有の機能はほぼ使ってないし、コメントもたくさんいれたので動作は理解できるはず?

#!/usr/bin/env python3
# -*- coding : utf-8 -*-
import random

def keygen(N, P) :
	k = [] # 鍵の集合(公開鍵)
	K = 0  # kの部分和(公開鍵)
	priv = [] # 和がKとなるようなkの選び方(秘密鍵)
	for i in range(N) :
		# [0,P)の区間から整数を一つランダムに選ぶ
		k.append(random.randint(0,P-1))
	for i in k :
		# 1/2の確立でkからアイテムを選択する
		if random.randint(0,1) :
			K = (K+i) % P
			priv.append(1)
		else :
			priv.append(0)

	return K, k, priv # (公開鍵,公開鍵,秘密鍵)

def encrypt(msg, N, k, K, P) :
	# vec_Aの内容は、[ [-K,[]], [k[0], [0]], [k[1], [1]], ... ]
	vec_A = [[-K,[]]]
	for i, key in enumerate(k) :
		vec_A.append([key,[i]])

	# 暗号化に使用する乱数を事前生成しておく
	R0 = []
	R1 = []
	R2 = []
	for i in range(N) :
		R0.append(random.randint(0,P-1))
		R1.append(random.randint(0,P-1))
		R2.append(random.randint(0,P-1))
	
	# vec_Bの内容は [ [R0[0], [0]], [R1[0], []], [R0[1], [1]], [R1[1], []], ... ]
	vec_B = []
	for i in range(N) :
		vec_B.append([R0[i], [i]])
		vec_B.append([R1[i], []])
	
	# normalize + multiply を含んだ処理。addはvec_Bを生成しているので考えなくてよい
	enc_dic = {tuple([]):msg} # もとのコードのrに相当
	for i in vec_A :
		for j in vec_B :
			# この辺はmultiplyに相当
			mul = (i[0] * j[0]) % P

			# この辺はnormalizeに相当
			vec_key = i[1] + j[1]
			# vec_key[0] <= vec_key[1] を保証
			if len(vec_key) == 2 and vec_key[0] > vec_key[1] :
				# swap
				vec_key[0], vec_key[1] = vec_key[1], vec_key[0]

			# vec_keyをキーとしたハッシュテーブルに値を足しこむ
			if not(tuple(vec_key) in enc_dic) :
				enc_dic[tuple(vec_key)] = 0
			enc_dic[tuple(vec_key)] = (enc_dic[tuple(vec_key)] + mul) % P
	
	for i in range(N) :
		enc_dic[tuple([i])] = (enc_dic[tuple([i])] - R2[i] + P) % P
		enc_dic[tuple([i,i])] = (enc_dic[tuple([i,i])] + R2[i]) % P
	
	# return用にencを成形する。特に意味はない。
	enc = []
	for i in range(N+1) :
		for j in range(i,N+1) :
			vec_key = [i-1,j-1]
			if i == 0 and j == 0 :
				vec_key = []
			elif i == 0 :
				vec_key = [j-1]
			enc.append([enc_dic[tuple(vec_key)], vec_key])
	return enc

def decrypt(enc, p) : #暗号文、秘密鍵
	msg = 0
	for i in enc :
		# i は [num,[a,b]] の形で、[a,b]はencryptのvec_keyに相当するもの
		add_flg = True
		for j in i[1] :
			add_flg = add_flg and p[j]

		# iが[num,[a,b]]であり、k[a]とk[b]がともに公開鍵Kを作るために使われていればnumを加算
		if add_flg :
			msg = (msg + i[0]) % P
	return msg

if __name__ == "__main__" :
	# 試しに暗号化/復号をしてみる
	N = 128
	P = 79228162514264337593543950319
	K, k, priv = keygen(N,P)
	# こいつを暗号化
	msg = 12345678987654321
	enc = encrypt(msg, N, k, K, P)
	msg_ = decrypt(enc, priv)

	print(msg, msg_)

暗号化に用いられているコードを読むと、それと等価なpythonのコード中でvec_Aとvec_Bの乗算が行われていることがわかる。この手のコードを読むには表を書いてしまうのが楽なので表を書くと次のようになる。

vec_A
-K, [ ]k[0], [0]k[1], [1]...k[N-1], [N-1]
vec_BR0[0], [0]-K*R0[0], [0]k[0]*R0[0], [0,0]k[1]*R0[0], [0,1]...k[N-1]*R0[0], [0,N-1]
R1[0], [ ]-K*R1[0], [ ]k[0]*R1[0], [0]k[1]*R1[0], [1]...k[N-1]*R1[0], [N-1]
R0[1], [1]-K*R0[1], [1]k[0]*R0[1], [0,1]k[1]*R0[1], [1,1]...k[N-1]*R0[1], [1,N-1]
R1[1], [ ]-K*R1[1], [ ]k[0]*R1[1], [0]k[1]*R1[1], [1]...k[N-1]*R1[1], [N-1]
..................
R0[N-1], [N-1]-K*R0[N-1], [N-1]k[0]*R0[N-1], [0,N-1]k[1]*R0[N-1], [1,N-1]...k[N-1]*R0[N-1], [N-1,N-1]
R1[N-1], [ ]-K*R1[N-1], [ ]k[0]*R1[N-1], [0]
k[1]*R1[N-1], [1]
...k[N-1]*R1[N-1], [N-1]

この表の内容の要素を足しあげて暗号化を行っているので、表の要素の和をキーとなるリストの要素ごとに取ると、

[] : -K*sum(R1)
[i] : -K*R0[i] + k[i]*sum(R1)
[i,i] : R0[i]*k[i]
[i,j] : R0[i]*k[j] + R0[j]*k[i] (i < j)

となる。さらに平文・乱数が足しこまれ、最終的には

[] : msg - K*sum(R1)
[i] : -K*R0[i] + k[i]*sum(R1) - R2[i]
[i,i] : R0[i]*k[i] + R2[i]
[i,j] : R0[i]*k[j] + R0[j]*k[i] (i < j)

となる。暗号文は、各キーとそれに紐づく数のタプルの集合である。

復号手法(配布されたコード中での)

秘密鍵として保存された、公開鍵Kをつくるような鍵kのインデックスの集合をIとすると、[], [i], [i,i], [i,j] (i, j \in I)に紐付く数を足し上げることで復号を行っている。実際に足し上げると

msg + (\sum_{i \in I} k_i - K)(\sum_{i \in I} R0_i + \sum_{i}R1_i)
となることが分かり、\sum_{i \in I} k_i = Kであるから、配布されたコード中に記された方法で確かに復号できることがわかる。

解読手法

記号類の定義

msg : 復号を目指す数(未知)
k_i : 鍵i(既知)
K : 鍵iの部分集合の和(既知)
R0_i : 乱数(未知)
R1_i : 乱数(未知)
R2_i : 乱数(未知)
S_{i,j} : enc.txtの[i,j]に紐付く内容 (i \lt j)(既知)

また、合同式の法は常に素数Pとする。

解読

以下が成り立つ。

  1.  S_{Null,Null} \equiv msg - K  \sum_{i}R1_i
  2.  S_{i,Null} \equiv -K \cdot R0_i + k_i \cdot \sum_{j}R1_j - R2_i
  3.  S_{i,i} \equiv R0_i \cdot k_i + R2_i
  4.  S_{i,j} \equiv R0_i \cdot k_j + R0_j \cdot k_i

式4から

\begin{cases}
R0_0 \cdot k_1 + R0_1 \cdot k_0 \equiv S_{0,1} \\
R0_0 \cdot k_2 + R0_2 \cdot k_0 \equiv S_{0,2}
\end{cases}
ここからR0_0を消去して整理すると

R0_1 \cdot k_2 - R0_2 \cdot k_1 \equiv (S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^{-1}
さらに式4から導かれる式と連立して

\begin{cases}
R0_1 \cdot k_2 + R0_2 \cdot k_1 \equiv S_{1,2} \\
R0_1 \cdot k_2 - R0_2 \cdot k_1 \equiv (S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^{-1}
\end{cases}
これを解いて
R0_1 = ((S_{0,1} \cdot k_2 - S_{0,2} \cdot k_1) \cdot k_0 ^ {-1} + S_{1,2}) \cdot (2k_2) ^{-1}
R0_0 = (S_{0,1} - R0_1 \cdot k_0) \cdot k_1^{-1}

式4を変形して

R0_i = (S_{i,j} - R0_j \cdot k_i) \cdot k_j ^{-1}

R0_0 , R0_1が既知なので、上式を用いてすべてのiに対してR0_iを求めることができる。(j=0とすればよい)

式2,3より
-K \cdot R0_i + k_i \cdot \sum_{j} R1_{j} + R0_i \cdot k_i \equiv S_{i,Null} + S_{i,i}
これを変形して
 \sum_{j}R1_j \equiv ((S_{i,Null} + S_{i,i}) + K \cdot R0_{i} - R0_{i} \cdot k_{i} ) \cdot k_i ^{-1}

右辺は既知なので、R1の総和\sum_{i}R1_i が求まる。

式1より
msg \equiv S_{Null,Null} + K \cdot \sum_{i} R1_{i}
となり、msgを復号できる。

msg = 0x534543434f4e7b6b70736b7d
であり、フラグはSECCON{kpsk}

ソースコード
#!/usr/bin/python3

P = 79228162514264337593543950319
k_hs = 14883097866997387203089669453
keys = # 省略します。解説中のk_iを埋め込んでください

def mod_inv(n) :
	global P
	res = 1
	p = P-2
	while p :
		if p % 2 :
			res = (res * n) % P
		p //= 2
		n = (n * n) % P
	return res

# enc.txtから
c = # 省略します。解説中のS_{i,j}を[S_{i,j},[i,j]] のリストの形で埋め込んでください。Nullのところは要素数を減らして対応します。

sum_all = 0
tab = {}

for i in c :
	sum_all += i[0]
	tab[tuple(i[1])] = i[0]
	sum_all %= P

r0 = [0 for i in range(128)]
sum_r0 = 0

r0[1] = mod_inv(2*keys[2]) * ((tab[tuple([0,1])] * keys[2] - tab[tuple([0,2])] * keys[1]) * mod_inv(keys[0]) + tab[tuple([1,2])])
r0[0] = (tab[tuple([0,1])] - r0[1] * keys[0]) * mod_inv(keys[1])

r0[0] = (r0[0] % P + P) % P
r0[1] = (r0[1] % P + P) % P

sum_r0 = r0[0] + r0[1]

for i in range(2,128) :
	r0[i] = (tab[tuple([0,i])] - r0[0] * keys[i]) * mod_inv(keys[0])
	r0[i] = (r0[i] % P + P) % P
	sum_r0 += r0[i]

#assert
for i in range(128) :
	for j in range(i+1,128) :
		#print(i, j, (keys[i] * r0[j] + keys[j] * r0[i]) % P, tab[tuple([i,j])])
		assert((keys[i] * r0[j] + keys[j] * r0[i]) % P == tab[tuple([i,j])]);

sum_r1 = mod_inv(keys[0]) * ((tab[tuple([0,0])]+tab[tuple([0])]) + k_hs * r0[0] - r0[0] * keys[0])

sum_r0 = (sum_r0 % P + P) % P
sum_r1 = (sum_r1 % P + P) % P

#assert
for i in range(1,128) :
	tmp = mod_inv(keys[i]) * (tab[tuple([i,i])] + tab[tuple([i])] + k_hs * r0[i] - r0[i] * keys[i])
	tmp = (tmp % P + P) % P
	assert(sum_r1 == tmp)

ans = sum_all - ((sum(keys) - k_hs) % P) * (sum_r0 + sum_r1)
ans = (ans % P + P) % P

assert(ans == ((tab[tuple([])] + k_hs * sum_r1) % P + P) % P)

print(hex(ans))

問題雑感

初めて解いたCTFの古典暗号でない問題で、面白さを感じた。面白さを感じて解説を書いていたら長文になってしまった。rubyを読むのは辛かったが、解くのにそう必要な知識も多くなく「CTFの暗号問題はクソなぞなぞや謎知識を要求する問題の山」だと思っていたCTF初心者の私には良い影響を与えてくれたと思う。現代暗号面白そうなのでがんばろう。

感想

ひと月ほど準備期間があったが、論文やらCODEFESTIVALやらDDCCやらでなかなか準備できていなかった。正直役に立てる気がしていなかったが案の定役に立ってなかった。

Cryptは数弱にはつらい問題だったが、どうにかなりそうなのがCryptしかなかったのでCryptに取り組んでいた。はじめて読むrubyはつらかった。

オイラーフェルマーの小定理さえ知ってれば小中学生でも解けるCrypt200が解けなかったのは恥としか言えない。今後一層精進したい。

AOJ2335 : 10-Year-Old Dynamic Programming / 10歳の動的計画 解説(別解)

競技プログラミング プログラミング

はじめに

AOJ2335:10歳の動的計画法を解いたが、非想定解で解説記事が書かれてなかったので書くことにした。別解の中で使ってるテクニックは他でも使おうと思えば使える気がします。

問題概要

2次元平面上で、次のルールで(0,0)から(N,M)まで移動するときの経路数を答えよ。

  1. 移動は複数のステップからなる
  2. 1ステップではx軸またはy軸に沿う方向に1だけ移動できる
  3. x軸負方向またはy軸負方向への移動回数の合計はKステップである
  4. x座標、y座標が負となるような移動はできない

制約
1 <= N,M <= 100,000, 0 <= K <= 10,000
8sec, 64MB (AOJ)

解法

想定解はJAGのページにある。この記事ではDPで解く別解について解説する。

まず、x軸方向の移動とy軸方向の移動は分けて考えることができる。

x軸上の移動を考える。k回の負方向への移動を含む移動によってx=pにたどり着いたとする。このときの経路数をf(k,p)と表記する。また、この経路数はy軸上の移動でも同じである。

x軸負方向にk回移動したのちに(N,M)にたどり着いたとしよう。すると、
x軸に沿った移動回数 N+2*k 回
y軸に沿った移動回数 M+2*(K-k) 回
となる。

つまり、答えは次の式で求まることになる。
 \sum_{k=0}^{k=K} f(k,N)f(K-k,M)\binom{N+M+2K}{N+2k}

二項係数の計算はO(N+M+K)ぐらいの前計算からO(1)で求まるため、前計算の結果と、f(k,N)とf(k,M)がk<=Kについて分かっていればO(K)で答えが求まることが分かった。f(k,N)とf(k,M)をk<=Kについて求める方法を考えればよい。

O(K * (N+M+K))のDPをすることでf(k,N)とf(k,M)は求まるのだが、これでは時間がかかりすぎてしまう。そうであっても、行うDPは別解とそう変わらないのでこのDPについても説明しておく。

dp(i,k) := i回の移動を行い、そのうちk回が負方向への移動であるような経路数。
として、更新は次の式で行う

dp(i,k) = \begin{cases}
    dp(i-1,k) + dp(i-1,k-1) & (i \geq 2k \text{ and } k \geq 1) \\
    dp(i-1,k)               & (\text{else})
    \end{cases}
このようにしてDPを行えば、f(k,p) = dp(p+2k,k)
としてf(k,M)とf(k,N)を求めることができる。

さて、K回以上正方向に移動を行っていれば、その後どのような順番で移動しようともルールを満たしながら移動することができる。つまり、2*K回以上の移動を行った後であれば、どのタイミングで負方向への移動を行っても構わないことになる。

2*K回の移動が終わるまではDPで経路数をもとめ、2*K回以上の移動を行う経路については2*K回の移動が終わった時点のDPの結果をもとに計算すればよい。

つまり、

dp(i,k) = \sum_{k'=max(0,2K-i+k)}^{k'=k} dp(2K,k') \binom{i-2K}{k-k'}
でdp(i,k) (i > 2*K) を求めることができる。和をとる範囲について補足する。2*Kステップにk'回の負方向への移動が含まれていた場合、正方向への移動は2*K-k'回である。全体で正方向への移動はi-k回であるから、2*K-k' <= i-k が成立しなければならない。よって、和はk'=max(0,2K-i+k)からとる。

計算量は、DPを途中まで行うのにO(K^2)、DPの結果から、dp(N,k)とdp(M,k)を計算しf(k,N)とf(k,M)を求めるのにO(K)これが0<=k<=Kについて計算されるからO(K^2)となり、f(k,N)とf(k,M)を計算する処理全体でO(K^2)となる。

問題全体を通した計算量は、O(N+M+K^2)である。

実装

#include <iostream>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
const ll mod = 1e9+7;
ll tab[10100];
ll tmp[10100];
ll ver[10100];
ll hol[10100];
 
ll fact[300100];
ll inv_fact[300100];
 
int main() {
    fact[0] = inv_fact[0] = 1;
    for(ll i = 1; i < 300100; i++) {
        ll t = mod-2, x;
        fact[i] = (fact[i-1] * i)%mod;
        x = fact[i];
        inv_fact[i] = 1;
        while(t) {
            if(t&1) {
                inv_fact[i]*= x;
                inv_fact[i]%= mod;
            }
            x = x*x%mod;
            t >>= 1;
        }
    }
    ll N, M, K;
    cin >> N >> M >> K;
    tab[0] = 1;
    for(int i = 1; i <= 2*K ; i++) {
        for(int j = 0; j <= K; j++) {
            tmp[j] = 0;
            tmp[j] = (((i >= 2*j && j) ? tab[j-1] : 0)
                + tab[j]) % mod;
        }
        for(int j = 0; j <= K; j++) {
            tab[j] = tmp[j];
            if(i - 2*j == N) {
                ver[j] += tab[j];
                ver[j] %= mod;
            }
            if(i - 2*j == M) {
                hol[j] += tab[j];
                hol[j] %= mod;
            }
        }
    }
    for(int i = 0; i <= K; i++) {
        for(int j = 0; j <= i; j++) {
            if(2*K-N-i <= j && (N+2*i>2*K)) {
                ver[i] += (tab[j] * fact[N+2*i-2*K] % mod)
                    * (inv_fact[i-j] * inv_fact[N+2*i-2*K - (i-j)] % mod);
                ver[i] %= mod;
            }
            if(2*K-M-i <= j && (M+2*i>2*K)) {
                hol[i] += (tab[j] * fact[M+2*i-2*K] % mod)
                    * (inv_fact[i-j] * inv_fact[M+2*i-2*K - (i-j)] % mod);
                hol[i] %= mod;
            }
        }
    }
    ll res = 0;
    for(int i = 0; i <= K; i++) {
        res += ((ver[i] * hol[K-i] % mod) *
            ((fact[2*K+M+N] * inv_fact[N+2*i] % mod) * inv_fact[2*K+M+N -(N+2*i)] % mod)) % mod;
        res %= mod;
    }
    cout << res << endl;
}

感想

想定解あたまいい。今回は非想定解だったけども、途中までDPをしてあとは計算頑張るという方針はどこかで使えそうだ。