|
有些時候二維碼被嚴(yán)重破壞導(dǎo)致無法掃描，促使我去學(xué)習(xí)了一波關(guān)于二維碼的知識。二維碼一共有40個尺寸。V 1是21 x 21的矩陣，V2是 25 x 25的矩陣，V3是29的尺寸，每增加一個等級，就會增加4的尺寸，公式是：(V-1)*4 + 21 最高V 40，(40-1)*4+21 = 177，所以最高是177 x 177 的正方形。 二維碼格式示例如下： 定位圖案定位圖案，就是每個二維碼都有的左上、左下和右上三個角的“回”字形的標(biāo)志。用于標(biāo)記二維碼的矩形大小他的尺寸都是7*7的模塊。
數(shù)據(jù)碼和糾錯碼除了上述的那些地方，剩下的地方存放 數(shù)據(jù)碼 和糾錯碼。就是最前面兩張圖的深灰色區(qū)域，一般數(shù)據(jù)都是從右下角開始填充，先填充數(shù)據(jù)碼，數(shù)據(jù)碼填充完畢之后再填充糾錯碼，以v1為例，數(shù)據(jù)的填充順序，是這樣的： 數(shù)據(jù)編碼QR碼支持如下的編碼：
下表是每個模式的編碼相對應(yīng)的“編號”，這個編號，存在于format information區(qū)域。 因為種類較多較復(fù)雜，而且為了方便大家理解，我們在這里值選擇數(shù)字編碼和字符編碼舉例，其它的編碼，有興趣的同學(xué)可以查看官方文檔。示例一： 數(shù)字編碼，從0到9。如果需要編碼的數(shù)字的個數(shù)不是3的倍數(shù)，那么，最后剩下的1或2位數(shù)會被轉(zhuǎn)成4或7bits，則其它的每3位數(shù)字會被編成10位的二進制數(shù)，最后將這些二進制數(shù)據(jù)連接起來并在前面加上編碼模式的編號和字符計數(shù)指示符（就是表示了被編碼的信息有多少個字符），字符計數(shù)指示符的長度取決于編碼的模式和所要編成二維碼的版本，在數(shù)字編碼中，字符計數(shù)指示符如下表對應(yīng)的有10、12或14位： 比如在Version 1的尺寸下，糾錯級別為H（糾錯級別我們會在下面講到）的情況下，我們要編碼： 01234567
示例二： 字符編碼（也叫字母數(shù)字編碼）。包括 0-9，大寫的A到Z（沒有小寫），以及符號$ % *+ – . / : 包括空格。這些字符會映射成一個字符索引表。如下所示（兩個表，中英文對照）：（其中的SP是空格，Char是字符，Value是其索引值）,編碼的過程是把字符兩兩分組，然后轉(zhuǎn)成下表的45進制，然后轉(zhuǎn)成11bits的二進制，如果最后有一個落單的，那就轉(zhuǎn)成6bits的二進制。而字符計數(shù)指示符需要根據(jù)不同的Version尺寸編成9, 11或13個二進制（如上表）。 在V 1的尺寸下，糾錯級別為H的情況下，編碼: AC-42
結(jié)束符和補齊符以上述示例一為基礎(chǔ)，在編碼結(jié)束后，我們得到了如下編碼： 然后，我們還要加上結(jié)束符，表示真正的額數(shù)據(jù)已經(jīng)結(jié)束。
我們還要加上結(jié)束符：
按每組8個bit分組，如果所有的編碼加起來不是8個倍數(shù)我們還要在后面加上足夠的0，比如上面一共有45個bit，所以，我們還要加上3個0，然后按8個bits分好組：0001000000100000 00001100 01010110 01100001 10000000 接著就是補齊符，如果還沒有達到我們最大的bits數(shù)的限制，我們還要加一些補齊碼就是重復(fù)下面的兩個bytes：11101100 00010001。（使用這兩個字節(jié)的主要原因是，為了防止在填入數(shù)據(jù)時出現(xiàn)大片的深色或淺色區(qū)域，對掃描器產(chǎn)生干擾，使得二維碼難以正常掃描），至于要補多少個補齊符，需要查看文檔中相應(yīng)的字符數(shù)和數(shù)據(jù)容量對應(yīng)表，在官方文檔中，相對應(yīng)的是表7-表11 從表中，我們可以知道，v1-H的數(shù)據(jù)容量為9個數(shù)據(jù)碼字（每個數(shù)據(jù)碼字為8位），而我們上面已經(jīng)有了6個數(shù)據(jù)碼字，所以要補充三個8bit，補充完畢如下：0001000000100000 0000110001010110 01100001 10000000 11101100 00010001 11101100 上面的每一組數(shù)據(jù)為一個數(shù)據(jù)碼字，Data Codewords，現(xiàn)在也只是原始數(shù)據(jù)，還需要對其加上糾錯碼。 糾錯碼上面我們提到了糾錯級別，二維碼中有四種級別的糾錯（從低到高為L、M、Q、H），這就是為什么有人在二維碼的中心位置加入圖標(biāo)，也依舊能夠掃描（就是二維碼殘缺量不超過所對應(yīng)的糾錯等級能允許的范圍時，使用掃描工具依舊能掃描出內(nèi)容的原因）。
至于糾錯碼是如何計算的，這涉及到里德-所羅門糾錯算法，里德-所羅門碼是定長碼。這個比較復(fù)雜，但是萬能的Pythom里面有一個交reedsolo的庫可以直接調(diào)用。這意味著一個固定長度輸入的數(shù)據(jù)將被處理成一個固定長度的輸出數(shù)據(jù)。在最常用的（255,223）里所碼中，223個里德-所羅門輸入符號（每個符號有8個 位元）被編碼成255個輸出符號。大多數(shù)里所錯誤校正編碼流程是成體系的。這意味著輸出的碼字中有一部分包含著輸入數(shù)據(jù)的原始形式。符號大小為8位元的里所碼迫使碼長（編碼長度）最長為255個符號。標(biāo)準(zhǔn)的（255,223）里所碼可以在每個碼字中校正最多16個里所符號的錯誤。由于每個符號事實上是8個位元，這意味著這個碼可以校正最多16個短爆發(fā)性錯誤。里德-所羅門碼，如同卷積碼一樣，是一種透明碼。這代表如果信道符號在隊列的某些地方被反轉(zhuǎn)，解碼器一樣可以工作。解碼結(jié)果將是原始數(shù)據(jù)的補充。但是，里所碼在縮短后會失去透明性。在縮短了的碼中，“丟失”的比特需要被0或者1替代，這由數(shù)據(jù)是否需要補足而決定。（如果符號這時候反轉(zhuǎn)，替代的0需要變成1）。這樣就需要在里所解碼前對數(shù)據(jù)進行強制性的偵測決定。 我們有現(xiàn)成的python模塊來運算出糾錯碼——python的reedsolo模塊。我們可以對照官方文檔中的糾錯特性表。以下表為例：
以版本1-H為例進行解釋，從表中，我們可以清晰的知道，糾錯碼字?jǐn)?shù)應(yīng)該為17個，糾錯的塊數(shù)為1（表示這個版本要編碼的數(shù)據(jù)只會分為一個數(shù)據(jù)塊），（26,9,8）表示，這個版本的二維碼總共可以存放26個碼字，但是這26個碼字中，有9個碼字為數(shù)據(jù)碼字，17個為糾錯碼字（8*2+1=17），8位糾錯容量。每個表的下方否有注釋信息：
這也是為什么糾錯碼字?jǐn)?shù)為r*2，當(dāng)后面有一個箭頭時，表示r*2之后還要加1。在給數(shù)據(jù)碼字添加糾錯碼時，還有對數(shù)據(jù)碼字分塊的操作，因為version1的二維碼對數(shù)據(jù)碼字之分一個塊，不夠明顯，所以我們采用網(wǎng)上的一個例子：
5. 最終編碼，穿插放置。 此時，編碼的過程，只剩下最后一步。 對于數(shù)據(jù)碼字：把每個塊的第一個codewords先拿出來按順度排列好，然后再取第一塊的第二個，如此類推。上述示例中的Data Codewords如下：
我們先取第一列的：67， 246 ， 182 ， 70 然后再取第二列的：67， 246， 182 ， 70， 85，246 ，230 ，247 如此類推：67， 246， 182 ， 70， 85，246 ，230 ，247 ……… ……… ， 38 ，6，50， 17 ，7，236 對于糾錯碼，也是一樣：
和數(shù)據(jù)碼取的一樣，得到：213，87，148，235，199，204，116，159，…… …… 39，133，141，236 然后，再把這兩組放在一起（糾錯碼放在數(shù)據(jù)碼之后）得到： 67, 246, 182, 70, 85, 246, 230, 247, 70, 66, 247, 118, 134, 7, 119, 86, 87,118, 50, 194, 38, 134, 7, 6, 85, 242, 118, 151, 194, 7, 134, 50, 119, 38, 87,16, 50, 86, 38, 236, 6, 22, 82, 17, 18, 198, 6, 236, 6, 199, 134, 17, 103, 146,151, 236, 38, 6, 50, 17, 7, 236, 213, 87, 148, 235, 199, 204, 116, 159, 11, 96,177, 5, 45, 60, 212, 173, 115, 202, 76, 24, 247, 182, 133, 147, 241, 124, 75,59, 223, 157, 242, 33, 229, 200, 238, 106, 248, 134, 76, 40, 154, 27, 195, 255,117, 129, 230, 172, 154, 209, 189, 82, 111, 17, 10, 2, 86, 163, 108, 131, 161,163, 240, 32, 111, 120, 192, 178, 39, 133, 141, 236剩余位最后再加上Reminder Bits，對于某些Version的QR，上面的還不夠長度，還要加上Remainder Bits，比如：上述的5Q版的二維碼，還要加上7個bits，Remainder Bits加零就好了。關(guān)于哪些Version需要多少個Remainder bit，可以參看官方文檔的表一（這里列出一部分）。
掩碼（也叫掩模）編碼的步驟是完成了，但是要想生成一個完好的二維碼，還需要先將現(xiàn)在所擁有的數(shù)據(jù)填入提前準(zhǔn)備的空白模板后，選擇一個合適的掩碼，將原模板的數(shù)據(jù)與掩碼進行異或運算，最后，再將format information填進去就生成了二維碼。掩碼存在的意義：二維碼是要拿來掃描的，而掃描怕的就是無法清晰地分辨出編碼信息的每一位。要是二維碼中黑白點數(shù)量不均，或是空間分布不均都會導(dǎo)致大色塊區(qū)域的出現(xiàn)，而大色塊區(qū)域的出現(xiàn)會增加掃描時定位的難度，從而降低掃描的效率。更嚴(yán)重的情況下，如果數(shù)據(jù)填入后碰巧出現(xiàn)了功能性標(biāo)識，比如定位標(biāo)識的圖樣，還會干擾正常功能性標(biāo)識的作用，導(dǎo)致QR碼無法掃描。在計算機科學(xué)中，掩碼就是一個二進制串，通過和數(shù)據(jù)進行異或運算來變換數(shù)據(jù)。在QR碼中，掩碼也是通過異或運算來變換數(shù)據(jù)矩陣。所以你可能已經(jīng)猜到了，QR碼的掩碼就是預(yù)先定義好的矩陣。QR標(biāo)準(zhǔn)通過生成規(guī)則定義了八個數(shù)據(jù)掩碼：
另外，使用python的reedsolo模塊，能夠在二維碼損壞超出相應(yīng)級別的容錯范圍時也能夠恢復(fù)數(shù)據(jù)。 Python2環(huán)境下的reedsolo模塊基本使用方式 1. 首先安裝reedsolo模塊，python官方下載的reedsolo模塊版本為0.3，不是很好用，這次使用的reedsolo模塊存放在下載包中的reedsolomon-master.zip，解壓后在該路徑下運行cmd命令python setup.py install即可。
4. 進行解碼
7. 將編碼后的內(nèi)容轉(zhuǎn)化為十進制輸出
學(xué)以致用，復(fù)現(xiàn)MMA2015-MISC400-qr的二維碼恢復(fù)挑戰(zhàn)的解題步驟，原版write-up地址為：https://github.com/pwning/public-writeup/blob/master/mma2015/misc400-qr/writeup.md 1. 題目給出的二維碼如下圖
這是一個25*25的二維碼，也就是version2的二維碼，二位從它能看見的部分我們可以得到format information的一部分信息：??????011011010 2. 對照下面這個網(wǎng)址所給出的對應(yīng)表，可以知道這個二維碼使用了什么編碼模式和使用了哪一個掩碼 https://www./qr-code-tutorial/format-version-tables#list-of-all-format-information-strings
經(jīng)對照可知，完整的format information信息應(yīng)該是：010111011011010。且可以得到的信息還有該二維碼使用的掩碼為6，所對應(yīng)的糾錯等級為Q。 3. 將被遮擋的固定信息部分以及format information信息補充完整。
5. 從右下角開始，按下圖的蛇形順序讀取數(shù)據(jù)碼字和糾錯碼字的信息，至于不同區(qū)域塊的信息讀取順序，可以參考官方文檔。
6. 將全部可讀的信息讀取出來：
7. 根據(jù)官方文檔的糾錯特性表，可知version2-Q的糾錯碼字?jǐn)?shù)有22個，數(shù)據(jù)碼字?jǐn)?shù)也有22個，在Q級別，它可以恢復(fù)不超過25%的損壞的字節(jié)，但是我們只有16個完整的字節(jié)，即超過63%的字節(jié)丟失，仔細查看Reed-Solomon的糾錯能力，并意識到它可以糾正多達兩倍的擦除——也就是說，如果 它知道錯誤在哪里，那么糾錯能力就強得多。這意味著我們的代碼可以從丟失的字節(jié)的50%恢復(fù)過來！但這意味著我們只能糾正多達22個丟失的字節(jié)，但是我們目前依然只有16個完整的字節(jié)，所以我們要想辦法恢復(fù)一部分字節(jié)使得達到22個字節(jié)這個最低要求。
8. 我們先將獲得的可讀取數(shù)據(jù)整理一下：
我們計算一下，22個數(shù)據(jù)碼字，就是176個bit，而20個字符，在編碼的時候分為10組，每組11個bit，所以4+9+10*11=123個bit，123/8=15余3，再加上4個0（結(jié)束符） ，以及8bit重組時需要補充為8的倍數(shù)，8-3-4=1，所以還需要加1個0。這時候總共也就16個數(shù)據(jù)碼字，22-16=6，所以還要加上6個 字節(jié)的 補齊碼，如下（紅色的是原本被遮住的數(shù)據(jù)）： 這樣，我們就回復(fù)了6個字節(jié)的數(shù)據(jù)，此時我們丟失的字節(jié)就只剩下22個了，正好達到了最低的要求。我們就可以使用糾錯碼恢復(fù)原本的數(shù)據(jù)。 9. 編寫腳本利用python的reedsolo模塊進行糾錯。
10. 得到全部的信息。
11. 拆分和解碼
|
|
|
