Posted on

前言:从三四年前刚刚接触CTF(Capture The Flag,网络安全比赛的一种)第一次参加比赛,到最近的HECC(英国高校网络安全挑战赛),我在杂项类题目中遇到过很多关于二维码的题目。此类题目需要参赛人员对二维码的生成原理有深入了解,同时需要使用图像后期软件对二维码进行处理,最终得到答案。作为摄影爱好者,我对图像处理非常熟练,经常可以通过一些出题者想不到的Photoshop小技巧,很容易地得到二维码题目的答案。由于二维码中QR Code最为常见,因此本文针对二维码仅讨论QR Code。由于基础知识和题目整理两部分内容均有较大篇幅,因此本文分一、二两部分进行更新。第一部分为QR Code基础知识,第二部分为QR Code题目及答题技巧。

1. 什么是QR Code

        解决CTF中的QR Code问题,首先需要对QR Code的种类、基本结构以及生成算法有一定了解。

       QR Code(Quick Response Code)是二维码的一种编码方式,通过与背景颜色存在对比的色块表示二进制数据0和1,通过色块组成的二维矩阵表示数字、英文、汉字、日文等内容[1]。计算机或智能终端可以通过图像识别设备对其进行解码的操作。

        1994年,日本丰田汽车的零部件供应商DENSO WAVE公司的原昌弘设计发明QR Code[2]。DENSO WAVE拥有QR Code的专利权,但为了让更多人使用QR Code,该公司表示放弃行使专利权[3]。QR Code在2000年被制订为ISO/IEC18004标准,并在2006年和2015年两次被优化[4]。由于QR Code具有比条形码存储信息量大,抗干扰能力强等优点,被人们广泛用于手机扫码等操作。

2. QR Code的种类

        目前共有5种类型的QR Code,他们有着不同的特点和用途。分别是[5]:日常使用最广泛的QR Code Model 1/2(本文中提到的QRCode为Model 2)、只有一个定位图案适合小面积印刷的Micro QR Code、信息容量更大的iQR Code,可以存储隐私信息的SQRC(外观和Model 2没有区别)和可以灵活嵌入图案的Frame QR。

图1. QR Code的种类[5]

3. QR Code的生成过程概述

       首先介绍QR Code的结构。构成QR Code的基本结构是码元(Module),即图案中最小的方块[6]。QR Code由功能性图案(定位图案、对齐图案、时间图案、隔离符)和编码区(格式信息、版本信息、数据及容错区)组成。其中定位图案为固定的7*7码元,中间为3*3码元实心正方形,外围为7*7码元空心正方形。对齐图案为5*5码元图案。除版本1不需要定位图案外,其余版本定位图案数量 numbers = pow( (version / 7 -1) , 2 ) – 3。时间图案固定为黑白相间的图案。编码区按照图下图所示的固定顺序进行填充[7]。

       QR Code的生成大致分为5个步骤:选择纠错级别和可以容纳对应数据量的版本、对数据进行分组和编码、计算容错信息、计算并添加合适的掩码(Mask)和计算版本及格式信息。通过以上步骤可以得到一个完整的QR Code图案[7]。

图2. QR Code图案的结构[7]

3.1 选择纠错级别、可以容纳对应数据量的版本

       首先根据需要存储的信息量以及二维码用途决定QR Code纠错级别(Data Correction Level)和版本(Version)。QR Code共有L、M、Q、H四个纠错级别,分别对应约7%、15%、25%和30%的恢复率。例如,将网址“http://li-yang.cn”使用QR Code编码,其包含17位字符,若用于屏幕显示(不易产生遮挡或破损的情况下),纠错级别L即可,查询版本及纠错级别对照表[8],可以得到该网址可以使用版本1存储该网址。QR Code的版本决定了码元数(modules),版本和纠错级别共同决定了可以存储的信息容量(Information Capacity)[8],版本1对应的码元数为21*21。码元数计算公式为:module = 17 + 4 * version。

图3. 版本与码元数的关系[8]

3.2 对数据进行分组和填充

       对需要编码的数据以2为单位进行分组,例如(ht)(tp)(:/)(/l)(i-)(ya)(ng)(.c)(n0)。对照以下字母数字编码表进行编码,并通过公式[7]计算得到二进制值最终得到数据区域的信息。通过对版本信息、格式信息的编码得到格式信息和版本信息的数据。

图4. 字母数字编码表[7]

3.3 计算容错信息

       通过容错计算公式对上一步骤中得到的数据区域的信息进行编码。按照ISO/IEC 18004标准化文档中的描述,该步骤计算过程可以通过逻辑电路图表示。[7]

图5. 容错码计算逻辑电路[7]

3.4 计算并添加合适的掩码(Mask)

       通过以上计算过程,已经得到数据及容错区的内容。为了防止大面积或连续出现黑色或白色图案并防止出现功能性图案出现在数据区域,需要对数据区域的图案添加掩码。一共有8中掩码图案,需要通过计算评估得到哪种掩码图案更适合此处的数据,并对数据和掩码进行异或的操作,得到最终数据去图案。[7]

图6. 掩码图案[7]

3.5 写入版本及格式信息

       对二维码的版本信息、模式信息、掩码信息等参照标准化文档得到对应编码写入对应区域。此处不需要进行二次编码和添加掩码操作。[7]

       通过以上步骤的运算,得到最终的完整图案。

参考链接:

1. https://www.qrcode.com/

2. https://www.denso-wave.com/zh/technology/vol1.html

3. https://www.qrcode.com/en/history/

4. https://www.iso.org/standard/62021.html

5. https://www.qrcode.com/en/codes/

6. https://www.qrcode.com/en/howto/cell.html

6. https://www.qrcode.com/en/about/error_correction.html

7. ISO/IEC 18004-2015 Information technology — Automatic identification and data capture techniques — QR Code bar code symbology specification

8. https://www.qrcode.com/en/about/version.html

发表回复