2014年12月7日

SECCON CTF 2014 online予選 QR400

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
前回の2013年で出た問題の逆(?)パターンでしたね。

問題: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:問題制作者とのやりとり



というわけで、今回はflagのフォーマットが SECCON{〜} の形になっていると想定して進めます。
当初は全て8ビットバイトモードで記述されていると思って、8ビットバイトモードで求めていたのですが、うまくいかず...
というわけで、混合モードというものがあるそうで(初めて知った...
先頭の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コードが復元できます。

2014年11月30日

aitendoの正方形LCDをmbedで駆動させる

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

久々にハードウェア系のネタ。
今回は、aitendoで販売されているスクエアLCD「ZY-FGD1442701V1」をmbed(1768)で動かします。

特徴は...
・128×128ピクセル
・65535色(16bitカラー)
・接続は8bitパラレル
・1000円くらい(割と安い?)

TFT液晶モジュール(1.44/128×128) [ZY-FGD1442701V1] (液晶単体)
1.44インチ液晶withキャリーボード [2P-1442701V1-PCB] (キャリーボード付き)

追記(2015/10) : 上記の商品は取り扱い終了しています。現時点では、以下の商品で同じように動かせるはず。
TFT液晶モジュール(1.44/8bit) [Y1411A1]

ネットで「ZY-FGD1442701V1」を検索すると先人たちの記事が出てきますが、いずれも搭載されているコントローラがST7735のもので、現在販売されているST7735S搭載版についての記事が見つかりません。
ST7735→ST7735Sでコマンドなどが一部変更になっているので、これに対応するようにしました。
初期化コードはaitendoが公開しているものに少々手を入れています。
#データシートもaitendoの商品ページにあるので助かりました

コードは以下(mbed Hg repository)に全て置いてます。
ZY_FGD1442701V1_BusOut_SDHC

以下は解説スライド (Qemb#03での発表を前提に準備してましたが、開催できなかった...)


スライド中で扱っている描画速度ですが、このスライドを作った後に別のSDHCカードで試してみたところ最終的に150ms程度で描画することができました。
また、画像ではなく黒や白で塗りつぶした(for文で0xffffffff、0x00000000を128*128*2回ぶん回した)場合、BusOutで105ms、PortOutで24msでした。

追記:LPCXpresso NXP LPC1769が手元に届いたので、これでも動作チェックしてみたいと思っています。

2014年10月16日

OpenLayers 3でOpenStreetMap上にピンを打つ

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
OpenLayers 3を使って、緯度経度で指定したポイントやポイントを結んだ形の図形をOpenStreetMap上に表示してみた。
OpenLayersは2から3へのアップデートで結構変わってる上にドキュメントは微妙、日本語での解説は2ばかりという状況なので、色々と試しながらです。

問題点は
・OpenStreetMapは球面メルカトル図法(EPSG:3857)で描画される
・ポイントは緯度経度(WGS84/EPSG:4326)で示したい
・EPSG:3857とEPSG:4326のレイヤーは同時に表示できない

最終的には
format: new ol.format.GeoJSON({
    defaultProjection: 'EPSG:4326'
}),
projection: 'EPSG:3857',
みたいな感じで解決できました。

以下、ソースコード

GeoJSONの仕様は
http://s.kitazaki.name/docs/geojson-spec-ja.html
を参考に。

上記コード内では、textで直接GeoJSONを書き込んでいるが、実際はurlで外部からjsonファイルを引っ張ってくる使い方が一般的(のはず)。

ちなみに、Polygonは閉路になる順にcoordinatesを指定してしないと捻れちゃうので、その辺も要注意。
そういうのを踏まえて、投げられた複数のジオタグから凸包を描くようなGeoJSONを吐くプログラムを現在製作中...

2014年10月9日

X220にArch Linuxを入れた時の覚書

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

ThinkPad X220にArch Linux、Xfceなどを入れて諸々の設定を行った時のメモ。
地味に初Archです。#普段はサクッとFreeBSDをインストールする派

使用したX220は、Core i5 2520M 2.5GHz、RAM 4GB(2GB*2)、HDD 320GBという構成のモデルナンバー4290RW4、2011年春発売のモデル。
指紋センサーあり、カメラは無し、無線LANはCentrino Advanced-N 6205を搭載、液晶は非IPSで視野角狭めな感じの、ベーシックタイプ。
これのHDDをIntel SSD 320 120GBに換装して、Arch Linuxをインストールしました。

インストール自体は既にネット上に大量にある情報とほぼ変わらないが、
・UEFI+GRUB
・指紋認証
・ファンコントロール
・音量ボリュームキー他の有効化
の4つは結構大事な情報で、これらも含めてまとまっている情報が無かったので、ここに残すことに。


Chrome、Eclipse、Wireshark等々を入れて落ち着いた状態が↑これ
スッキリ、シンプルで非常に快適。

以下、インストール時に行った操作など、まとめ。

2014年9月28日

X230tのHDDをCT512MX100SSD1に換装

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

前回、新装整備品のThinkPad X230 Tabletを買った記事を書きましたが、今回はこれのHDDを512GBのSSDに換装した話。
今回購入したのは、割と評判が良くて安価なCrucial CT512MX100SSD1です。
CrucialはMicron Technologyのブランドなので信頼性は高いイメージ。

まずは、現在入っているHDDからSSDにデータを移行します。
これには、CT512MX100SSD1に付属しているAcronis True Image HDを使ってディスククローンしてあげればOK。


USB-SATAケーブルはaitendoの実店舗で980円くらいで売ってあった(気がする)もの。
2.5インチサイズまでしか電源の関係で駆動できないけど、1本持ってると便利。


Acronis True Image HDは現在稼働中のWindowsが入っているHDDにインストールして使います。
自身が入っているディスクをクローンする時は、再起動後に独自のシステムが起動してクローンしてくれます。

クローンが終了したら、スタイラスペンが収納されている側にあるHDDスロットカバーをプラスドライバーで開けて、ベロを引っ張り古いHDDを引き抜きます。
レールを外して同じようにSSDに付け替え、元の様にスロットに戻し、スロットカバーを閉めれば終了。

手順を何も間違っていなければ、電源ONで今まで通りの環境が立ち上がるはずです。

ちなみに元から入っていたHDDはHGSTのHTS545032A7E380でした。
リカバリディスク製作済みorリカバリ領域もクローン済みなら、初期化して外付けHDDケースなどに入れて使うのも良いかも。(ただし5400rpmなので読み書きは遅め)

2014年8月22日

新装整備品Thinkpad X230 Tabletを購入

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

発売当初から欲しかったThinkpad X230 Tabletを買いました。
開封済み・新装整備品でお値段は54000円(税込)で、色々遊ぶには最高なんじゃないかと考えてたらポチってました。

ThinkPad X230 Tablet - 開封済み・新装整備品 | 3436XF1 | Lenovo Outlet (JP)
http://shopap.lenovo.com/jpoutlet/itemdetails/3436XF1/445/628C87959CB248F78E23CB2244F4AEC9

実際に買ったのは1ヶ月くらい前だけど、色々追加したり環境整えたりする作業をダラダラやってたので今更まとめということで。

その1:無線LANカードが載ってない

無線系はBluetoothしか載ってないので、無線LANカードを買って増設しました。
アンテナ線は3本(黒、灰、白)来てるので、WiMAXのカードとか3本アンテナ必要なカードとかも刺せる。
ちなみに、WWAN用のアンテナ線も2本来てます。(青と赤)
WWANカードを載せないなら、mSATA SSDカード用に使える。(ただし、SATA2の速度までしか出ない)


買ったのはIntel Centrino Advanced-N 6205。
FRU品じゃないとBIOSで弾かれるので60Y3253という型番のカードを買いました。
お値段2158円。

その2:メモリ搭載量が少ない

流石に2GBは少ないので、換装します。
Lenovoのサイトには2GB (空スロット:0)と書いてあるけど、実際には2GBが1枚刺さってるので、トータル4GBでよければ2GBを刺すのもあり。


まぁ、ここは積めるだけ積んでおこうということで8GB*2枚の16GBを買いました。
お値段14796円。
#エルピーダが死んでから高騰が激しくて辛いですね...

ここまでで、トータル71054円。
来月辺りで320GBのHDDを512GBのSSDに換装しようと考えているので、最終的には10万円弱になりそうですが...
デジタイザ搭載マシンが欲しかった&VMでは無い純粋なWindows機が欲しかったので、どちらも達成できて満足。
Linux走らせて遊ぶだけなら無線LANカードを追加するくらいで十分そう。

ここ数年ずーっとMacしか買ってなかったので、バラバラ分解可能でバッテリーも取り外せるThinkpadが斬新すぎる。
特に最近のMacBook系なんてRAMまでオンボだし...

そのうちmSATAなSSDでも買ってLinuxとデュアルブートにしたいなぁ

2014年8月19日

桜島が噴火したYoの裏側

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

作ってから1週間くらい経ってますが、プログラムの紹介というか詳解というか...
実は初めてのJava Servlet(&Tomcat)だったんですが、Eclipseからwar書き出して置くだけでdeploy完了というのは素晴らしい。
#小5の頃にPerlでCGI書いて動いた時くらいの感動

で、実際の仕組みは...
  1. 気象庁からPuSH(PubSubHubbub)で来るfeedを受け取る
  2. entryをSAX(Simple API for XML)で解析する
  3. 桜島に関する情報(噴火 or 爆発第1報)の場合はYoを送信
という感じ。

気象庁が公開している気象庁防災情報XMLフォーマットについては、下記を参照。
http://xml.kishou.go.jp/open_trial/

PubSubHubbubは以下。
https://code.google.com/p/pubsubhubbub/

ここ↑にはJavaで書かれたSubscriber Clientsの紹介もあるのですが、こちらはServletじゃないです。
特にServletに対するこだわりは無いけど、最近Scalaとかに興味あるのでWebサービスを書く為のJavaを学んでおこうかと...

セキュリティ上の都合で全てのコードを公開できる訳ではないのですが、PuSHの購読&受信とfeedの解析部分は以下の様な感じ。
#例のごとく酷いコードなので参考までに...

上がSAXハンドラ、下がPuSHサブスクライバです。
#Gistってファイル単位でバラしてコード貼り付けできないのね... (今更

実際には、このSAXハンドラのpublic void characters内で「現  象:噴火」「第1報 現  象:爆発」がcontent要素内に含まれる場合に分岐させてYoを送るメソッドを呼んでます。
それと、これも上記コードには含まれてませんが、受け取ったfeedに記載された全てのxmlは取得&保存しています。
#つまり、天気予報とか天気概要とか注意報警報なども"現在は"使ってないけど、保存はしてるっていうこと。

先日のYoアップデートの際にURLの添付が可能になったのですが、これに伴って噴火の詳細情報をYoにくっつけて送るアップデートをしようかなぁっと。
現在フロントエンドを書いてる途中で、これの仕組みは、保存されたxmlをパースして表示するだけですね。はい。

これに並行して、WebSocketでpushを... なんてのも準備中。
PuSHはネット上からアクセス可能なサーバでしか受けられないので、これを転送したいなぁっと。
これができると、噴火したら火口が赤LEDで光る桜島オブジェなんてものも作れちゃう訳です。

そういえば2週間弱くらい大学行って研究してない気がするけど... アッ(

2014年8月11日

桜島が噴火したYoを作った

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

鹿児島県の桜島が噴火(爆発)したときに「Yo」で通知してくれる仕組みを作ってみた。

QuitSquare » 桜島が噴火したYo
http://www.quitsq.com/sakurajima_yo/

使い方 
  1. Yoを起動します。
  2. 「SAKURAJIMA」にYoを送信します。
  3. 終わりです。
以降、桜島が噴火する度にYoが送信されます。
解除したい場合はSAKURAJIMAをブロックしてください。


実際にはこんな感じでYoが来る。
2014年 8月11日 15時01分 (今年199回目)の爆発時の通知なのですが、時刻を見れば分かるとおり15分遅れてます。
これは自分の書いたプログラムとかYo APIの遅延じゃなくて、気象庁が電文を公開するまでの時間なので、こちら側で何とかできる訳ではありません。
だいたい10〜15分程度は遅れるようなので、噴火「速報」的な使い方は全く保証できません。
が、実際噴火してから降灰するまでには時間があるので、降灰注意には使えるかも。

後ろの仕組みは簡単。
気象庁発表の電文をパース、桜島が噴火もしくは爆発した第1報を元にYo APIを叩くというもの。
Javaで書いてるのですが、ちゃっちゃと書いたせいで汚いのでキレイキレイしてから公開します。

他にも桜島の噴火情報を利用したサービスを考え中なので、そのうち作るかも...
その時は気象庁防災情報XMLについても書く予定。

2014年7月31日

ATtiny85で赤外線シリアル通信

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

前回前々回の続き。
赤外線LED(OSI5FU5111C-40)とフォトトランジスタ(L-51ROPT1D1)を使ったシリアル通信をATtiny85で実現させます。
さらに、このATtiny85とArduinoをI2Cで接続し、I2C-赤外線通信コンバーター化します。

構成はこんな感じ。

ATtiny85の各ピンは以下の通り。

pin1 - RESET
pin2 - Serial RX (from フォトトランジスタ)
pin3 - Serial TX (to 赤外線LED)
pin4 - GND
pin5 - I2C SDA (Arduino A4)
pin7 - I2C SCL (Arduino A5)
pin6 - not used(D1)
pin8 - VCC

pin6が空いているので、更に何か追加することもできますが、今回は未使用。

ATtiny85をArduinoとして扱う方法は「Programming an ATtiny w/ Arduino 1.0」 を参考にしました。
書き込みはaitendoで購入し、以前の記事でファームウェアのアップデートを行ったUSBasp-Bを使用。
ATtiny85は内蔵RC 8MHz駆動です。

プログラムは以下の様な感じ。(たぶんもっとキレイに書けるはず...)

#include <SoftwareSerial.h>
#include "TinyWireS.h"

#define I2C_SLAVE_ADDR  13
#define IR_RX 3 // pin2
#define IR_TX 4 // pin3

SoftwareSerial irPort(IR_RX, IR_TX, false);

void receiveEvent(uint8_t a) {
  int i = 0;
  char c;
  char buf[100];
  if (TinyWireS.available()) {
    while(TinyWireS.available()){
      c = TinyWireS.receive();
      buf[i] = c;
      i++;
      buf[i] = '\0';
      delay(2);
    }
    irPort.write(buf);
  }
}

void requestEvent() {
  if(irPort.available()){
    char c = irPort.read();
    if(c!=255)
      TinyWireS.send(c);
  }
}

void setup() {
  TinyWireS.begin(I2C_SLAVE_ADDR);
  irPort.begin(1200);

  TinyWireS.onReceive(receiveEvent);
  TinyWireS.onRequest(requestEvent);
}

void loop() {

}

Arduino UNO側はこんな感じ。

#include <Wire.h>

void setup(){
  Serial.begin(9600);
  Wire.begin();
}

void loop(){
  if(Serial.available()){
    int i = 0;
    char c;
    char buf[100];
    while(Serial.available()){
      c = Serial.read();
      buf[i] = c;
      i++;
      buf[i] = '\0';
      delay(2);
    }
    Wire.beginTransmission(0); //broadcast
    Wire.write(buf);
    Wire.endTransmission();
  }

  Wire.requestFrom(13,1);
  if(Wire.available()){
    byte b = Wire.read();
    if(b!=0xff && b!=0x0a && b!=0x00)
      Serial.write(b);
  }
}

これで、一番上の写真のように向かい合わせにして赤外線通信ができます。
UNO側のコードでbroadcastにしているのは訳があって、このあとATtiny85を複数個ぶら下げる予定。

2014年6月1日

続・赤外線LEDとフォトトランジスタでシリアル通信

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

前回の続き。
赤外線LED(OSI5FU5111C-40)とフォトトランジスタ(L-51ROPT1D1)を使ったシリアル通信。
今回は、送受信×2で双方向(全二重)通信を実現させます。

構成は...
PC <---Serial---> Arduino <---赤外線---> Arduino <---Serial---> PC
こんな感じ。

前回のものを一体化して、以下のようにする。

これを2個用意し、互い違いになるように向かい合わせて配置。


プログラムは以下の通り。

#include <SoftwareSerial.h>

SoftwareSerial irPort(10, 11, false);

void setup() {
  irPort.begin(1200);
  Serial.begin(9600);
}

void loop() {
  int i = 0;
  char c;
  char buf[100];
  if(Serial.available()){
    while(Serial.available()){
      c = Serial.read();
      buf[i] = c;
      i++;
      buf[i] = '\0';
      delay(2);
    }
    irPort.print(buf);
  }

  if (irPort.available())
    Serial.write(irPort.read());
}

最初はSerialから赤外線へ渡す部分を
if (Serial.available()) {
    irPort.write(Serial.read());
}
こんな感じにしていたけど、これだとループの早さにSerial.readが追いつかないっぽい。
abcdefgと送るとabcgになる等、データが途中で抜けたりするので一旦バッファに全部溜めてからprintするようにしました。
ちなみに、上記コード中のdelay(2)を取ると、途中が抜けたり最初の3文字くらいしか取れない現象が発生するので、やはりSerial.readが原因の模様。
当初のコードのirPort.writeの前行にdelayを入れるのも試してみたが、10msくらいにしないとダメだったので、バッファに溜めた方が早いかなと。

上記写真のような配置で距離を離して双方同時に送信すると、互いが干渉して文字抜けや化けが発生するので、実際は間に遮蔽を入れるなどの工夫が必要。
試しに紙を1枚入れてみたら安定して通信できました。

2014年5月31日

赤外線LEDとフォトトランジスタでシリアル通信

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

久々のArduinoネタ。
赤外線LED(OSI5FU5111C-40)とフォトトランジスタ(L-51ROPT1D1)を使ってシリアル通信をする。
最終的にATtiny85に載せる計画なので、SerialではなくSoftwareSerialを使っています。

送信側はこんな感じ。
普通のLEDと同様に抵抗1本を入れる。


受信側はこんな感じ。
トランジスタ(2SC1815)を入れてD10に接続。


これを向かい合わせにして、配置する。


プログラムは以下のような感じ。
送信側
#include <SoftwareSerial.h>

SoftwareSerial sender(10, 11);

void setup() {
  sender.begin(1200);
}

void loop() {
  sender.println("Hello World!");
  delay(1000); 
  sender.println("1234567890");
  delay(1000);
  sender.println("abcdefghijklmnopqrstuvwxyz");
  delay(1000); 
}

受信側
#include <SoftwareSerial.h>

SoftwareSerial receiver(10, 11, false);

void setup() {
  receiver.begin(1200);
  Serial.begin(9600);
}

void loop() {
  if (receiver.available()) {
    Serial.write(receiver.read());
  }
}

送信側のプログラムは、「Hello World!」→「1234567890」→「a〜z」を1s毎に出力、受信側は赤外線で受け取ったデータをSerialにそのままフォワーディングするような感じ。
仕組み的には独自のプロトコルではなく、Serial(SoftwareSerial)を使っているので特に複雑な訳でもなくサクッと使えるのが利点。

環境にもよると思いますが、この構成だと約20cmくらいまで離しても通信できました。
通信距離を伸ばすには赤外線LEDの球数を増やす、電圧を上げる(もちろん高出力タイプに置換した上で)等で出力を強くする必要あります。

次の記事では送受信×2で双方向(全二重)を実現させます。

2014年2月26日

MP268 FR4 ワイヤレス給電モジュール

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

久々の電子工作系のネタ(といっても工作じゃありませんが...)
dealextremeでワイヤレス給電のモジュールが売ってあったので、2種類買ってみました。
1つめは特に規格などが定められてないMP268 FR4 DIY Wireless Power Supplyというもので、もう1つはqi規格に対応したモジュール... なのですが別々に発送されて先にMP268が届いたので、こちらから先に調べてみました。

中身は上の写真の通り。
給電モジュールと受電モジュールのセットで、受電側は何かに貼り付けられるように両面テープみたいになってます。
ちなみに、受電モジュールの正極側のリード線が付いてなかったので、この後自分で付けました...

説明書によれば入力はDC12Vとのことですが、商品ページには10〜12Vとか9〜12Vとか色々書いてあるので、とりあえず試してみました。
直流安定化電源は菊水のPMC18-3Aです。

左上12V、右上9V、左下7V、右下5V。



7Vくらいまでは大丈夫そう。(余裕を見れば9V〜12Vといったところでしょうか)
いずれもコイル間の隙間がほぼゼロの状態なので、実際に何かに組み込む際はもう少し下がるでしょう。

以下は実際にLEDを繋いでみた&スマートフォンを繋いでみた動画。(入力は12V)



実用的で夢拡がる感じなのは良いとして、何に組み込もうか...

追記:説明書の裏に使用用途例が書いてありました。(なぜ気づかなかった?)


2014年1月27日

SECCON CTF 2013 online予選 forensics 400

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
SECCON CTF 2013 オンライン予選のフォレンジックス400点の解法です。
競技中は解けませんでしたので、終わってからじっくり解いてみました。

問題:QRコードの断片を読み取れ
富士山麓で焼け落ちたQRコードの断片が発見された。 損傷が激しい。内容を復元することはできるだろうか?
qr-photo.jpg

QRコードの仕様について詳しく知らなかったので、調べました。
http://ja.wikipedia.org/wiki/QR%E3%82%B3%E3%83%BC%E3%83%89

・バージョンがある(1〜40)
誤り訂正レベルがある(L,M,Q,H)
・モードがある(数字、 英数字、8ビットバイト、漢字)
・どのモードを使っているかを表すモード指示子がある
・文字列/データの長さを表す文字数指示子がある
・QRコードは読み取り精度を高めるためにマスク処理が行われている
・どのようなマスクが掛かっているかを表すマスクパターン参照子がある

Wikipedia英語版では図解で説明されていました。
http://en.wikipedia.org/wiki/QR_code


QRコードの3つの角に付いてるマーカー、そのうち左側のマーカーの周りには、誤り訂正レベル(Error Correction Level)、マスクパターン参照子(Mask Pattern)、誤り訂正レベルとマスクパターン参照子から算出した訂正ビット(Format error correction)が配置されています。
残る1つ、右上のマーカーの下には、この訂正ビットの下8ビットが配置されています。

ここまでで分かったことは...
QRコードにはマスクが掛かっているが、どのマスクパターンが掛かっているかはマスクパターン参照子が無いと分からない。
→でも、写真のQRコードには左半分が無いから、マスクパターンの種類は分からない。
→ついでに誤り訂正レベルも分からない。

ここで、英語版Wikipediaにある次の画像に注目しました。
誤り訂正レベルHでバージョン3のQRコードのコード配置の説明画像です。


とりあえず、これに写真のQRコードを合成してみよう...


なんと、ドットのサイズも配置もバッチリじゃないですか...
どうやら、写真に写っているのはバージョン3らしく、誤り訂正レベルHのQRコードと仮定すればデータ領域は全部残っているとみることが出来そうです。
誤り訂正はできませんが、この部分が読み取れれば何とかなりそう。
しかし、マスクが被さっているので、このまま読んでも意味が通じません。
→なんとかしてマスクパターンが知りたい
→右上のマーカーの下(上図の赤い部分)に付いている訂正ビットの下位8bitは分かる!

左が上位ビットらしいので、これを読むと、下位8bitは10001001と分かります。

http://www.swetake.com/qrcode/qr5.html
http://www.swetake.com/qrcode/qr6.html

↑こちらのサイトによれば、誤り訂正レベル(Error Correction Level)、マスクパターン参照子(Mask Pattern)、誤り訂正レベルとマスクパターン参照子から算出した訂正ビット(Format error correction)を形式情報と呼び、15bitで表現されるようです。
15bitのうち、最初の5ビット(誤り訂正レベル2bit+マスクパターン参照子3bit)をBCH符号化したものが10bitの訂正ビットで、最初の5bitとBCH符号化した10bitを引っ付けた15bitを更に101010000010010とXORしたものがQRコードに刻まれるとのこと。

ここで、誤り訂正レベルをH(上位2bitが10)と仮定すると、マスクパターンは全てで8種類なので...
10000、10001、10010、10011、10100、10101、10110、10111をBCH符号化して求めた10bitの訂正ビットをそれぞれに付け、これをXORしたものの下位8bitが10001001であるものがあれば、マスクパターンを特定することができます。


というわけで、計算すると下位8bitが一致するのはマスクパターン参照子000となります。
写真QRコードと判明した形式情報からQRコードを描くと、以下になります。
(まだリーダーなどでは読み込めません)


マスクパターン参照子000のマスクは(i+j) mod 2 = 0なので、マスクは市松模様のようになります。
もう一度マスクを掛ければ元に戻るので、上記のQRコードのマーカーと形式情報を除外した場所を市松模様状にマスクを掛け、先ほどのコード配置図を合成すると、以下のようになります。


D1からD26まで、ビット配置の規則に従って読んでいくと、


http://www.swetake.com/qrcode/qr2.html

↑こちらサイトによれば、最初の4bitはモード指示子で、この場合は0010なので英数字モード、次の9bitが文字数指示子で000100011なので10進数にすると35文字ということになります。
それ以降は11bitずつ区切れば良いそうで、区切った11bitを10進数に変換すると以下の通り。
(35文字なので、最後の1文字だけ上位6bitを読んで10進数に変換)


この10進数の値は英数字2文字分で、1文字目のコードに45掛けた数値と2文字目のコードの和になっているとのこと。
(文字コード対応表は下記)


という訳で、全てのパターンを計算しました。安定のC(白目

#include <stdio.h>

int main(void) {
 int i,j;
 for(i=0;i<=44;i++){
  for(j=0;j<=44;j++){
   printf("45*%d+%d=%d\n",i,j,45*i+j);
  }
 }
 return 0;
}

実行結果は下記
http://ideone.com/phmtrx

必ず一意の数値になるので、10進数に直した数字で一覧を検索すると下記のように対応します。


並べると「CONGRATS. FLAG IS VIVA REED-SOLOMON」で、Keyは「VIVA REED-SOLOMON」となります。

おまけ:完全復元したQRコード
感想:QRコードを学べる良い機会になりました!
(もう二度とQRコード印刷した紙を燃やしたりしないでください >Kちゃん先生)

Recent Photos from Atelier (Flickr)

作業場で撮影した写真をアップロードしています。記事にする前の試作なども公開中です。