初めまして、理工学部電子情報工学科１回生 システム管理局 小林です。
自分は前期・後期グループ活動でSECCON班に所属していました。
「SECCON（SECurity CONtest）」とは、情報セキュリティをテーマに多様な競技を開催する情報セキュリティコンテストイベントです。
問題が約30問与えられ、それを24時間以内にそれぞれの問題に隠されたflagを探し出す競技です。
SECCONの問題は様々なジャンルの問題が出されますが、毎年QRコードにまつわる問題が出題されていました。
そこで前期グループ活動で自分は右半分のみのQRコードを読み取る方法を調べました。
QR コードの右半分のみではQR コードリーダーで読み込むことは不可能なので、自力でデータを解読する必要がある。
QR コードには、右側半分に生データ、左側半分が誤り訂正符号化されたものが書かれている。
生データが欠けずに全て残されている場合、マスク処理を再度行うことによって元のデータが求められ、それを規則に従い二進数をデータとして入力し、文字に変換することで読み解くことができます。
マスクパターンは８種類あり、まず行と列を(i,j)とおきます。
そして、以下の各条件を満たす点においてbit を反転(黒と白を入れ替える)させます。
マスクパターン
・ (i+j) mod 2 = 0
・ i mod 2 = 0
・j mod 3 = 0
・(i+j) mod 3 = 0
・(( i div 2)+(j div 3)) mod 2 = 0
・(ij) mod 2 + (ij) mod 3 = 0
・((ij) mod 2 +(ij) mod 3) mod 2 = 0
・((ij)mod 3 + (i+j) mod 2) mod 2 = 0
(※ mod は剰余計算、div は整数除算)
これをすべて自力で求めるのは不可能なので全通りを求めるプログラムを作成しました。
また、ここで一気にQRコードの読み取る順番も考慮し、二次元配列から一次元配列に落とし込みます。
#include<stdio.h>
int main()
{
char i, j, x=0, s, t, k, a=21, temp; //aは行と列の数
char data[21][21] = {
{ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 1, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1}
, { 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 1, 1, 0, 1, 1, 1 ,1 ,0 ,1}
};
for (k = 0; k < 8; k++){
for (j = 0; j < a; j++){
for (i = 0; i < a; i++){
switch (k){
case 0: x = (i + j) % 2; break;
case 1: x = i % 2; break;
case 2: x = j % 3; break;
case 3: x = (i + j) % 3; break;
case 4: x = ((i / 2) + (j / 3)) % 2; break;
case 5: x = (i * j) % 2 + (i * j) % 3; break;
case 6: x = ((i * j) % 2 + (i * j) % 3) % 2; break;
case 7: x = ((i * j) % 3 + (i + j) % 2) % 2; break;
}
if(x == 0){
if (data[i][j] == 0)data[i][j] = 1;
else if (data[i][j] == 1)data[i][j] = 0;
else data[i][j] = 2;
}
}
}
printf("マスクパターン%d\n",k);
for (s = 0; s < a/2; s++){
for (t = 1; t <= a; t++){
if (s % 2 == 0){
temp = data[a - t][a - (2 * s) - 1];
if (temp == 0)printf("0");
else if (temp == 1)printf("1");
temp = data[a - t][a - (2 * s) - 2];
if (temp == 0)printf("0");
else if (temp == 1)printf("1");
}
else{
temp = data[t-1][a - (2 * s) - 1];
if (temp == 0)printf("0");
else if (temp == 1)printf("1");
temp = data[t-1][a - (2 * s) - 2];
if (temp == 0)printf("0");
else if (temp == 1)printf("1");
}
}
}
/*
printf("\n");
for (t = 0; t < a; t++){
for (s = 0; s < a; s++){
char nom = data[t][s];
printf("%d", nom);
}
printf("\n");
}
*/
printf("\n");
}
return 0;
}
マスクパターン0 001000000100010011010001101001101011010101110001010001000000000011101100010101011010011001101011100100111001000111110010010111001000000101001110110110100011100011000011 マスクパターン1 111011001000100000011101100101011000011001000010100010001100110000100000111111110011111111110010000010100111011110010100001110101110011100101000101011110110110110010110 マスクパターン2 111011001000100000011101001111110010110011101000110111011001100101110101111111110011111111110010000010100010001011000001011011111011001001111101111011110110110110010110 マスクパターン3 100011010000111000000101101011010110010111001100010110111000000100010100110110111010110110111011001011101010111011110001101011001011111001001101001010111111111111011111 マスクパターン4 010011101100110111000110001110111111001101011010011001111011110100101000000101110100110001011010110011110110010110111010111001111111010100000110011011011001100110111001 マスクパターン5 010000101110110100000100100100000101100111100000001010111101100111101110100101010000110111011110110101110011001011101111100100101010001001010011000111111101000010011101 マスクパターン6 001111100100101011001110001011111111001000011010111001011011010100001000011101101101110000110011110010011110010100011010111011011111010110100110011010010000101111110000 マスクパターン7 001101011001101001110011010011011000010000111101010111001010111010011001011010101110001100110000001110011000100101010100001010010001100111101000101101010111101000110111
得られた結果の最初４桁はモード指示子を示している。モードとはQRコード内に含まれている文字コードのようなものです。モードは４種類存在し、以下のモード支持しと対応している。
・数字モード—0001
・英数字モード—0010
・8bit モード—0100
・漢字モード—1000
先ほどbit反転させた結果の最初4bitと同じモード指示子が存在するマスクパターンが当たりであると予測できます。
次の以下に対応するbit が文字数指示子であり、QRコード内に含まれているデータの文字数です。
・数字モード—10bit
・英数字モード—9bit
・8bitモード—8bit
・漢字モード—8bit
これ以降には元のデータが含まれており、ここからはモードごとに読み方が異なってくる。
今回は英数字モードについてのみ話させてもらいます。
まずデータを11bitごとに区切ったものを2進数から10進数に変換する。
次にそれを45で割って商と余りを求める。
最後に、商を1文字目、余りを2文字目とし、以下の対応表を用いて文字に変換します。これを11bitごとに区切った全てのデータで繰り返し、文字数指示子が示す文字数になるまで変換する。
以上の方法でQRコードに含まれたデータを読み取ることができます。
自分は簡略化するために表計算ソフトを用いて以下の画像のように実行しました。
どうでしたか？思ったより簡単ですよね？
明日からは、わざわざ携帯でQRコードを読み取る必要なんてありません!!
だってあなたはもう人間QRコードリーダーなんだから＾＾
2015年12月05日(土) に行われたSECCON 2015 オンライン予選に参加したのですが、今年はQRコード問題は出たものの上で説明したようなデータの解析問題ではなく、QRコードパズルのプログラム問題だったので予想以上に自分は戦力になりませんでした；＿；
なので来年も機会があればSECCONに参加しようと考えています。
では、これで終わらせていただきます。よいお年を〜〜(まだクリスマスも来ていない)
次の記事は西村さんの記事です。
