問題：BBQR
Let's enjoy BBQR!
とりあえず、まずは問題の画像から読み解きます。
写っているマーカーと形式情報から、バージョン3のQRコードの左半分っぽいですね。
形式情報は全部残っていて、001011010001001と読めます。
誤り訂正レベル(Error Correction Level)：00
マスクパターン参照子(Mask Pattern)：101
誤り訂正レベルとマスクパターン参照子から算出した訂正ビット(Format error correction)：1010001001
なので、訂正レベルH、マスクパターンは市松模様だと分かります。
バージョン3で訂正レベルHのQRコードは、データコード数26、エラー訂正コード数44、RSブロック数2です。
合成すると...
キレイにE1〜E44までのエラー訂正コードが残っています。
キレイにするとこんな感じかな？
左下図の赤がマスクパターン、右下図はパターンに従ってマスクしたところ。
このアンチマスクを合成して...
これを読んでいくと、下表のとおり。
以下のページを参照すると
http://www.swetake.com/qrcode/qr3.html
f(x)をg(x)で除算して... 排他的論理和を計算して... というのを26回ほど繰り返すと剰余R(x)が出てくるという感じだそうで。
データコードを係数とした多項式f(x)→これが分かるとflagが出てくる
エラー訂正コードの生成多項式g(x)→データコード数から算出可能
剰余R(x)→今回のQRコードで残っている部分
ここでタイムアップでした。
ここから先、解けたら追記していきます。
というより、このアプローチで正しいのかすら分かりません。
前回同様に人力解読に挑戦していますが、QRコードリーダのプログラムを上手く改良してエラー訂正コードのみからデータを取り出せるようにすることが出来るかもしれませんし...
※まだ解けてないので、上の画像(QRコードや表、剰余の式)は正しいと保証できませんのであしからず...
追記 2014/12/07 20:24：マスクパターンを掛け間違っていたので、画像を差し替えました
追記 2014/12/08 03:40：問題制作者とのやりとり
@9SQ ゼロ知識から本当に手計算で解く、って意味なら無理だと思う。フラグ形式がそうなってる、って情報は今だからわかることであって、もしかしたら別の情報も入ってたかもしれないし。リードソロモンの仕組みを確認したい、って意味なら止めない。かなり勉強になるはず。
— きくちゃん (@kikuchan98) 2014, 12月 7
手動解析、朝が来るまでに終わるのか pic.twitter.com/Xm4QGqzTBR
— けーいち (@9SQ) 2014, 12月 7
@9SQ あー、そういうアプローチかー。いいね。
— きくちゃん (@kikuchan98) 2014, 12月 7
というわけで、今回はflagのフォーマットが SECCON{〜} の形になっていると想定して進めます。当初は全て8ビットバイトモードで記述されていると思って、8ビットバイトモードで求めていたのですが、うまくいかず...
@9SQ パンケーキの方と比べてみるとわかるけど、モードは混在できるのよ。
— きくちゃん (@kikuchan98) 2014, 12月 7
というわけで、混合モードというものがあるそうで（初めて知った...先頭のSECCONは英数字モード、それ以降の{〜}を8ビットバイトモードであると仮定して...
英数字モード6文字=0010 000000110
SE=45*28+14=1274=10011111010
CC=45*12+12=552=01000101000
ON=45*24+23=1103=10001001111
ここまでで、4+9+11+11+11 = 46 bit
8ビットバイトモード18文字=0100 00010010
{=123=01111011
ここまでで、66 bit → 66/8 = 8.25 → D1〜D9の先頭2bitまで分かる
逆に終端は
}=125=01111101
ここまでで、202bitなので208bitになるように6bitを0で埋める
??011111 → D25
01000000 → D26
残り、D9後半6bit〜D25先頭2bitまでの合計128bit、16文字が不明。
αの指数と整数の対応表は http://www.swetake.com/qrcode/qr_table4.html を参照
でも、この手法だと8回目で計算できなくなる...
色々とアレだったので、改めて解法を別記事に書き直します...
(問題作成者からもアドバイスを頂いたので、それも含めて。)
以下おまけ。元々のD1〜D26。
これを当てはめて市松模様でマスクを掛けると以下のQRコードが復元できます。
