---
lang: ja-jp
breaks: true
---

PNG over Teregraph
===

## 問題概要
### ジャンル
Crypto

### 点数
300 points

### 問題文
PNG over Telegraph
Analyze signal in this video.
You will able to get PNG, if you success to decode it.
https://youtu.be/Y6voaURtKlM

### フラグ
SECCON{SEMAPHORE_LINE_IS_THE_1ST_TELEGRAPH_SYSTEM_IN_THE_WORLD}

### 挑戦者
idzuna

## 解法
### フレームの切り出し
動画のフレームを1秒ごとに切り出す．
オフセットは試行錯誤の結果，0.8秒がちょうどよかった．

ffmpeg -i video.mp4 -vf crop=200:200:260:20 -ss 0.8 -r 1 -f image2 %06d.bmp

### 符号の推測
動画を見ていると，腕木のシンボルは32通りあるっぽい．
三十二進数であると仮定して，PNGフォーマットのヘッダ構造や，特定の符号 (0や31) が連続することなどから，腕木シンボルと数値の対応関係を推測する．

動画の冒頭部分を見ると，腕木のシンボルと，A-Yまでのアルファベットの対応がわかる．
これら A-Y はそれぞれ三十二進数の 0 - 24 に対応しているっぽい．
残りの 25 - 31 も，A-Y までの規則性などからなんとなく推測できる．
わからないところは試行錯誤．

### 画像のマッチング
三十二進数に対応する32種類の画像を人力で探し出し，それらとマッチさせる．
単純に画像をベクトルと見なして，平均0, ノルム1になるように正規化しておき，内積の大きいやつを選べば識別できた．
腕木がぶれたりカメラの位置がずれたりするので，画像を1画素ずつずらしながらマッチングし，一番内積が大きいものを採用する．

#include <TNLib\Bitmap.hpp>
#include <TNLib\Raw.hpp>
#include <Eigen\Eigen>
#include <string>
#include <sstream>
#include <iomanip>
#include <iostream>

int main()
{
  const int h = 184;
  const int w = 192;
  Eigen::MatrixXd pattern[32];

  for ( int i = 0 ; i < 32 ; ++i )
  {
    pattern[i].resize( w*h , 128 );

    Eigen::MatrixXd r , g , b;
    std::ostringstream filename;
    filename << "pattern/(" << i << ").bmp";
    std::cout << filename.str() << std::endl;
    TNLib::loadBitmap( filename.str() , r , g , b );

    for ( int k = 0 ; k < 16 ; ++k )
    for ( int l = 0 ; l < 8 ; ++l )
    {
      for ( int j = 0 ; j < w ; ++j )
        pattern[i].block(j*h,k*8+l,h,1) = r.block(k,l+j,h,1);
      pattern[i].col(k*8+l) = pattern[i].col(k*8+l).array() - pattern[i].col(k*8+l).mean();
      pattern[i].col(k*8+l).normalize();
    }
  }

  static int indices[2984];
#pragma omp parallel for
  for ( int i = 0 ; i < 2984 ; ++i )
  {
    Eigen::MatrixXd r , g , b;
    std::ostringstream filename;
    filename << std::setfill('0') << std::setw(6) << (i+78) << ".bmp";

    std::cout << filename.str() << std::endl;
    TNLib::loadBitmap( filename.str() , r , g , b );

    Eigen::VectorXd v(w*h);
    for ( int j = 0 ; j < w ; ++j )
      v.block(j*h,0,h,1) = r.block(8+i*8/2984,j+4-i*3/2984,h,1);
    v = v.array() - v.mean();
    v.normalize();

    double result[32];
    for ( int j = 0 ; j < 32 ; ++j )
    {
      Eigen::VectorXd prod = pattern[j].transpose() * v;
      result[j] = prod.maxCoeff();
    }
    indices[i] = static_cast<int>( std::distance( result , std::max_element( result , result + 32 ) ) );
  }
  TNLib::saveArrayToFile( "indices.bin" , indices );
  return 0;
}

### 復号

#include <TNLib\Raw.hpp>
#include <string>
#include <sstream>
#include <iomanip>
#include <iostream>

int main()
{
  static int indices[2984];
  TNLib::loadArrayFromFile( "indices.bin" , indices );
  std::ofstream out( "out.png" , std::ios::out | std::ios::binary );

  for ( int i = 0 ; i < 2984 ; i += 8 )
  {
    std::uint64_t v = indices[i];
    v = ( v << 5 ) | indices[i+1];
    v = ( v << 5 ) | indices[i+2];
    v = ( v << 5 ) | indices[i+3];
    v = ( v << 5 ) | indices[i+4];
    v = ( v << 5 ) | indices[i+5];
    v = ( v << 5 ) | indices[i+6];
    v = ( v << 5 ) | indices[i+7];

    char buf[5];
    buf[0] = ( v >> 32 ) & 0xff;
    buf[1] = ( v >> 24 ) & 0xff;
    buf[2] = ( v >> 16 ) & 0xff;
    buf[3] = ( v >>  8 ) & 0xff;
    buf[4] =   v         & 0xff;

    out.write( buf , sizeof(buf) );
  }
  return 0;
}

これが出てくる．

## 議論
三十二進数っぽい
三十二進数なので，それに加えて7つのシンボルがあるみたいだけど対応がよくわからない．