塗りつぶすだけで別のデータにできるQRコードを無理やり作った

概要

元の QR コードの白を黒く塗りつぶすという動作のみで別のデータに変えることができるような QR コードを作成しました。

具体的には、
https://waryu.dev/?$RpQUqko7G
の QR コードの一部を塗りつぶし、
https://waryu.dev/?$RpIUqko7G
のデータに変えられる QR コードを作成しました。

きっかけ

作っていた名刺に、普通は日本語のサイトが出るけど、特定の場所を塗りつぶせば英語版のサイトが出るようになる QR コードがあったら面白そうじゃね？という思いつきで作り始めました。
実用性は考えていない。

計画

とりあえず QR コードの仕組みを読んでみました。

参考：
https://qiita.com/amanao/items/b7c54a3c73a8301b2412
https://qiita.com/Kta-M/items/6f7049a1e78b1fe7e883

実値データはいいとして、誤り訂正部分がムズ過ぎるので計算で求めるのは不可能と判断しました。

つまり、

1. 二つの https://waryu.dev/?{ランダムな英数字} から QR コードを生成
2. その二つを比較し、片方の白を塗りつぶすだけでもう片方の QR コードにできるかをチェック
3. できないのなら、1 に戻る

という感じでやっていきます。

プログラム

(処理速度が)早い！(個人的に使うのが)うまい！安(全性が高)い！な Rust を使って書きました。

まずは QR コードの生成。

fn to_matrix(url: &str) -> QR {
  let mut result: QR = Vec::new();
  let segs = QrSegment::make_segments(url);
  let qr = QrCode::encode_segments_advanced(
    &segs,
    QrCodeEcc::Low,
    Version::new(2),
    Version::new(2),
    Some(Mask::new(5)),
    false,
  )
  .unwrap();
  for y in 0..qr.size() {
    result.push(Vec::new());
    for x in 0..qr.size() {
      result[y as usize].push(qr.get_module(x, y));
    }
  }
  result
}

qrcodegen を利用して Vec<Vec<bool>>型の QR コードを生成します。

この時、QR コードの mask を指定しています。mask とは、QR コードを読み込ませやすくするために、黒と白がいい感じにばらけるよう調整する素晴らしい仕組みです。しかし、私の作りたい QR コードの前では残念ながら邪魔でしかないため、全ての mask を同じ種類にしています。
また、QR コードの誤り訂正レベルは最低の Low。こうすることで、可能性を高めています。

次に QR コードが私の欲しいものかをチェック。

fn is_only(left: &QR, right: &QR) -> bool {
  let mut which: Option<bool> = None;
  for row_i in 0..left.len() {
    for dot_i in 0..left[row_i].len() {
      if left[row_i][dot_i] ^ right[row_i][dot_i] {
        if let Some(only) = which {
          if left[row_i][dot_i] ^ only {
            return false;
          }
        } else {
          which = Some(left[row_i][dot_i])
        }
      }
    }
  }
  true
}

二つの QR コード(ここでは left と right とする)の同じ座標の値が、同じなら無視、異なるなら left の値を保存。また異なる値が出てきた時に、left の値と保存した値が異なるなら残念、最後まで辿り着けばループは終了です。

といった感じのプログラムを作りました。

実行 & 結果

1 時間ぐらい動かしとけば見つかるだろうと舐めた気持ちで動かしましたが、一向に見つかる気配はありませんでした。

怪訝に思って誤差が 0 ではなく 10 以下のものをログとして出力するようにしたら、誤差 8 までは出やすく、誤差 7 ぐらいになると厳しいという感じで全然ダメ。

簡単に見積もっても、数年は動かし続けないと求め終わらなさそうでした。

しかし諦めるわけにはいかないので効率化を進めていきます。

効率化

まずは並列化

基本的には、今動かしているものを複数スレッドで動かすように変えるだけです。

ただ、どれか一つのスレッドが求められたら、全てのスレッドをループから抜け出させる処理と、何回ループさせたかの集計はスレッド間共有が必要だったのでその処理がちょこちょこしてます。

let is_finished = Arc::new(Mutex::new(false));
let global_counter = Arc::new(Mutex::new(0));

let mut handles = Vec::new();

for _ in 0..3 {
  let is_finished = Arc::clone(&is_finished);
  let global_counter = Arc::clone(&global_counter);

  let handle = thread::spawn(move || {
    let mut rng = rand::thread_rng();
    let mut counter = 0;
    loop {
      counter += 1;
      if generate(&mut rng) {
        let mut finished = is_finished.lock().unwrap();
        *finished = true;
        break;
      }
      if *(is_finished.lock().unwrap()) {
        break;
      }
      if counter % 100000 == 0 {
        let mut c = global_counter.lock().unwrap();
        *c += 100000;
      }
    }
  });

  handles.push(handle);
}

for handle in handles {
  handle.join().unwrap();
}

これで、プログラムを数倍早くできました。

他にも細かな改良を行いました。しかし、数年まではいかなくとも数ヶ月ほどはかかりそうです。

そんな時、画期的な方法を思い付きます。

元々の二つの URL データは、SearchParams をランダムな文字(長さは同じ)にしていましたが、そうすると、誤り訂正だけではなく、実値でも運ゲーが加速してしまいます。

そのため、URL データを、二つの間で一文字だけ異なるようにしました。

例えば、ランダムに https://waryu.dev/?aBcDe という URL が一つ目の URL として生成された場合、二つ目のデータは、https://waryu.dev/?aBcze と一文字だけ違うデータになります。

let length = rng.gen_range(5..=12);
let item_1 = Alphanumeric.sample_string(&mut rng, length);
let item_2_ch = Alphanumeric
  .sample_string(&mut rng, 1)
  .chars()
  .next()
  .unwrap();
let i = rng.gen_range(0..length);
let mut item_2 = String::new();
for (j, ch) in item_1.chars().enumerate() {
  if j == i {
    item_2.push(item_2_ch);
    continue;
  }
  item_2.push(ch);
}
if item_1 == item_2 {
  return false;
}

こうすることで、実値のいくつかの bit 分高速化できるはずです。

テスト

その方法で動くようにしたプログラムを一度実行してみます。

すると、誤差 4 が当たり前になるほど誤差が少なくなり、結果が求まるまでの時間を見積もると、大体丸 1 日動かせば出るほどになりました。

実行 & 結果

あとは時間の問題です。
1 日中プログラムを動かして結果が得られるのを待ちます。

その結果、$RpQUqko7G の QR コードを塗りつぶすだけで $RpIUqko7G にできることを発見しました。（先頭に$があるのは、直前まで JS 書いており、Rust を書くときに混ざっちゃったものです。）

それによって作られたのが以下の QR コードです。

この QR コードをそのまま読み込むと日本語の自分のサイトに飛びますが、灰色を黒に塗りつぶすと英語のサイトに飛ぶようになっています。
塗りつぶした QR コードもこちら(実際は、塗りつぶさなくても上に黒で線を描けば良いです。)

最後に、この QR コードを名刺に載せて完成です。

結論

話のネタにはなるが、名刺を汚すことになるので実際に使われることはなかった。

最後に

今のデータ量でも求めるのに数日かかるので実用的に使うのは無理だと思いますが、何か思いついた方はご自由に！