細切れになったQRを頑張って読み解くツールを作った話

この投稿はUDHI-LAB++; Advent Calender 2022 7日目の記事です


# なんで？
CTFを授業で取り扱っていた際に新しい問題の作成に悩み、たどり着いたのがQRコードを細切れにして解読するお話でした。
割と苦行なのですが、実際やってみると絶対読めないように思えるQRコードも頑張れば解読できることが楽しくなっていきます。(白目)
(QRを読むためだけの知識のため、浅いところが多いです…)

:::note warn
ここから大量に細切れにされたQRコードが何度か出てきます。
気持ち悪くなったらすみません。
:::

# 本題
今回の問題はこちらです
![4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/37de1007-c6eb-5e75-8137-436c70df3128.png) ![12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/255e6cfd-9531-b1f3-0a18-e64140652a85.png) ![9.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/b561ebc0-5b86-20b5-8aae-5e239a7e661c.png) ![20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/45e4616b-83f3-b72d-6504-1e53ea8f60bc.png) ![19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/b296a5b7-35de-9e8f-070f-872846c9315d.png) ![31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/7d3c4246-29fc-da42-6873-35d143cf43bf.png) ![24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/c999e120-d089-8481-b7df-7c1a8fc8841d.png) ![27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/e786a528-9e90-11b0-3165-8e8d2b6f981e.png) ![59.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/b514266b-ad50-cde4-4efa-8b26eaf0d798.png) ![62.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/0beee59d-72dd-94d4-f55a-562569aa70f3.png) ![63.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/74f9e63a-aaa0-03fe-cfbf-fdd31c1cad76.png) ![68.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/10e63082-1d62-9de1-35f2-4503814a25b0.png) ![69.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/a5100373-924b-543d-bce9-c000168aa12c.png) ![71.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/c774be1e-aaf9-36fb-8f37-e1281543af00.png) ![77.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/ea89fd00-3062-4350-b800-172ca18ff564.png) ![84.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/2de7c8c3-e0bb-e568-7947-1be6f0531643.png) ![86.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/920e76c2-e543-a191-fdea-c3cd48414b36.png) ![88.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/abc01a21-365c-d2ef-d601-90a0c5f3bfc3.png) ![91.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/db4730f4-7218-367c-1226-72ea5393539d.png) ![94.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/949b6914-1f13-4fa1-9aa7-2637a4c4d15d.png) ![96.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/dd7524db-d4ea-80c8-0cbf-be9e56c1b253.png) ![97.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/2bfc986d-e01c-568f-69e4-df4ac0d47e5d.png) ![100.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/c363ffa3-3e2b-3923-b69a-8568fe3ce55b.png) ![38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/6c3fadf3-9b9b-6103-01be-82d9cc7e3188.png) ![39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/1ae3911e-fead-e1fc-e95a-23c9b423ae3e.png) ![46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/f6c34dee-87ec-5e41-67c5-0fbefdc70400.png) ![48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/6ec156a9-47d1-ce69-05e1-d6c30f392aaa.png) ![51.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/612ed060-6b52-19d5-9bf2-21123541865c.png) ![52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/f8a86947-a2fc-2251-1a43-be25a384f567.png)
計29枚の画像ファイルになります。

ここからは別のQRでまずは僕が解析によく使っているQRコードの決まりを説明していきます。
一番目立つところから行くとファインダパターン
左上、左下、右上に配置されている三つです
![QR_644850_find.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/aa9f13f0-ec4b-6ddd-7fea-e1fd87349c30.png)
次にアライメントパターン
右下中央寄りに配置されています
![QR_644850_araiment.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/87ca2507-9903-e411-3c8d-4b56051ca766.png)
そしてタイミングパターン
規則的に並んでいるやつです
![QR_644850_timing.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/cbae4e2c-e1d9-85c9-322d-4ced6529101d.png)
最後にフォーマット情報
これは左下から右上と左上のパターンが同じになるので一番助けられます
![QR_644850_format.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/75df5051-aa11-8ff8-a445-b56aaa35e3c0.png)

この知識を前提として
まずは僕の作った[ツール](https://yugu0202.github.io/QR-CTF/)に29x29分打ち込んでいきます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/f21c1acc-d608-6649-0f53-1070d4a28e5a.png)
そうしたら、明らかなファインダパターンから揃えていきます。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/b718007e-4b32-eb54-696e-84fcf0724ad9.png)
その時点でここまで確定し、ほかも結構絞れます
そしてアライメントパターンとフォーマット情報から解読を進めていきます
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/17e1f0d1-939f-abd0-7113-eaa5f53f14e3.png)
右側のファインダパターンの間は2分の1なので両方試して埋めてしまいます
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/102b7717-9e68-cab7-fcea-6b91abc6a18b.png)
なんだか答えが見えてきましたね…
ここからはタイミングパターンとアライメントパターンを見て埋めていきます
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/608139/8d787c56-896e-619e-3530-7f90504f69b3.png)
と、後半は総当たり気味ですが、こんな風に解読することができました！！
# 最後に
これでもしQRコードをシュレッダーにかけてしまったとしても読めますね！！！
今回はツールを作った話をする予定が問題の解き方になってしまいました…
もし細切れのQRコードに出会ったときはこのツールで解読してあげてください()