跟我一起學習玩轉二維碼

2019-05-31 338252人圍觀 ,發現 14 個不明物體 極客

有些時候二維碼被嚴重破壞導致無法掃描,促使我去學習了一波關于二維碼的知識。二維碼一共有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 的正方形。

二維碼格式示例如下:跟我一起學習玩轉二維碼

定位圖案

定位圖案,就是每個二維碼都有的左上、左下和右上三個角的“回”字形的標志。用于標記二維碼的矩形大小他的尺寸都是7*7的模塊。

跟我一起學習玩轉二維碼功能性數據:存在于所有的尺寸中,用于存放一些格式化數據的,主要內容為“糾錯碼等級(3bit)+掩碼類別(2bit)+BCH code(10bit,用于糾錯)”,然后這15個bits還要與101010000010010做XOR操作,主要是為了如果選用了00的糾錯級別和000的Mask,從而造成全部為白色,這會增加掃描器的圖像識別的困難。比如:

跟我一起學習玩轉二維碼  而這15個bit在format information區域內的分布如下:

跟我一起學習玩轉二維碼  在 Version 7以上,需要預留兩塊3 x 6的區域存放一些版本信息。

 數據碼和糾錯碼

 除了上述的那些地方,剩下的地方存放 數據碼 和糾錯碼。就是最前面兩張圖的深灰色區域,一般數據都是從右下角開始填充,先填充數據碼,數據碼填充完畢之后再填充糾錯碼,以v1為例,數據的填充順序,是這樣的:


跟我一起學習玩轉二維碼

數據編碼

QR碼支持如下的編碼:

數字編碼:從0到9;

字符編碼:包括 0-9,大寫的A到Z(沒有小寫),以及符號$ % * + – . / : 包括空格;

字節編碼:可以是0-255的ISO-8859-1字符;

日文編碼:也是雙字節編碼;

Extended ChannelInterpretation (ECI) mode 主要用于特殊的字符集。并不是所有的掃描器都支持這種編碼;

Structured Appendmode 用于混合編碼,也就是說,這個二維碼中包含了多種編碼格式;

FNC1 mode 這種編碼方式主要是給一些特殊的工業或行業用的。比如GS1條形碼之類的

下表是每個模式的編碼相對應的“編號”,這個編號,存在于format information區域。

跟我一起學習玩轉二維碼

因為種類較多較復雜,而且為了方便大家理解,我們在這里值選擇數字編碼和字符編碼舉例,其它的編碼,有興趣的同學可以查看官方文檔。
示例一:

數字編碼,從0到9。如果需要編碼的數字的個數不是3的倍數,那么,最后剩下的1或2位數會被轉成4或7bits,則其它的每3位數字會被編成10位的二進制數,最后將這些二進制數據連接起來并在前面加上編碼模式的編號和字符計數指示符(就是表示了被編碼的信息有多少個字符),字符計數指示符的長度取決于編碼的模式和所要編成二維碼的版本,在數字編碼中,字符計數指示符如下表對應的有10、12或14位:

跟我一起學習玩轉二維碼

比如在Version 1的尺寸下,糾錯級別為H(糾錯級別我們會在下面講到)的情況下,我們要編碼: 01234567

(1)把上述數字分成三組: 012 345 67

(2)把他們轉成10bit二進制:  012 轉成 0000001100;345 轉成 0101011001;67 轉成1000011。

(3)把這三個二進制串起來: 0000001100 0101011001 1000011

(4)把數字的個數轉成二進制 (version 1-H是10 bits ): 8個數字的二進制是0000001000

(5)把數字編碼的標志0001和第4步的編碼加到前面:  0001 00000010000000001100 0101011001 1000011

示例二:

字符編碼(也叫字母數字編碼)。包括 0-9,大寫的A到Z(沒有小寫),以及符號$ % *+ – . / : 包括空格。這些字符會映射成一個字符索引表。如下所示(兩個表,中英文對照):(其中的SP是空格,Char是字符,Value是其索引值),編碼的過程是把字符兩兩分組,然后轉成下表的45進制,然后轉成11bits的二進制,如果最后有一個落單的,那就轉成6bits的二進制。而字符計數指示符需要根據不同的Version尺寸編成9, 11或13個二進制(如上表)。

跟我一起學習玩轉二維碼image.png

在V 1的尺寸下,糾錯級別為H的情況下,編碼: AC-42

(1)從字符索引表中找到 AC-42 這五個字條的索引 (10,12,41,4,2)

(2)兩兩分組: (10,12) (41,4) (2)

(3)把每一組轉成11bits的二進制:(10,12) 10*45+12 = 462 轉成 00111001110;(41,4)41*45+4 = 1849 轉成 11100111001;

(4)把這些二進制連接起來:00111001110 11100111001 000010

(5)把字符的個數轉成二進制 (Version 1-H為9 bits ): 5個字符,5轉成 000000101

(6)在頭上加上編碼標識 0010 和第5步的個數編碼:  0010 00000010100111001110 11100111001 000010

結束符和補齊符

以上述示例一為基礎,在編碼結束后,我們得到了如下編碼:

然后,我們還要加上結束符,表示真正的額數據已經結束。

編碼 字符數 HELLO WORLD的編碼
0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101

我們還要加上結束符:

編碼 字符數 HELLO WORLD的編碼 結束
0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101 0000

按每組8個bit分組,如果所有的編碼加起來不是8個倍數我們還要在后面加上足夠的0,比如上面一共有45個bit,所以,我們還要加上3個0,然后按8個bits分好組:0001000000100000 00001100 01010110 01100001 10000000

接著就是補齊符,如果還沒有達到我們最大的bits數的限制,我們還要加一些補齊碼就是重復下面的兩個bytes:11101100 00010001。(使用這兩個字節的主要原因是,為了防止在填入數據時出現大片的深色或淺色區域,對掃描器產生干擾,使得二維碼難以正常掃描),至于要補多少個補齊符,需要查看文檔中相應的字符數和數據容量對應表,在官方文檔中,相對應的是表7-表11

跟我一起學習玩轉二維碼

從表中,我們可以知道,v1-H的數據容量為9個數據碼字(每個數據碼字為8位),而我們上面已經有了6個數據碼字,所以要補充三個8bit,補充完畢如下:0001000000100000 0000110001010110 01100001 10000000 11101100 00010001 11101100 上面的每一組數據為一個數據碼字,Data Codewords,現在也只是原始數據,還需要對其加上糾錯碼。

糾錯碼

上面我們提到了糾錯級別,二維碼中有四種級別的糾錯(從低到高為L、M、Q、H),這就是為什么有人在二維碼的中心位置加入圖標,也依舊能夠掃描(就是二維碼殘缺量不超過所對應的糾錯等級能允許的范圍時,使用掃描工具依舊能掃描出內容的原因)。

image.png

至于糾錯碼是如何計算的,這涉及到里德-所羅門糾錯算法,里德-所羅門碼是定長碼。這個比較復雜,但是萬能的Pythom里面有一個交reedsolo的庫可以直接調用。這意味著一個固定長度輸入的數據將被處理成一個固定長度的輸出數據。在最常用的(255,223)里所碼中,223個里德-所羅門輸入符號(每個符號有8個 位元)被編碼成255個輸出符號。大多數里所錯誤校正編碼流程是成體系的。這意味著輸出的碼字中有一部分包含著輸入數據的原始形式。符號大小為8位元的里所碼迫使碼長(編碼長度)最長為255個符號。標準的(255,223)里所碼可以在每個碼字中校正最多16個里所符號的錯誤。由于每個符號事實上是8個位元,這意味著這個碼可以校正最多16個短爆發性錯誤。里德-所羅門碼,如同卷積碼一樣,是一種透明碼。這代表如果信道符號在隊列的某些地方被反轉,解碼器一樣可以工作。解碼結果將是原始數據的補充。但是,里所碼在縮短后會失去透明性。在縮短了的碼中,“丟失”的比特需要被0或者1替代,這由數據是否需要補足而決定。(如果符號這時候反轉,替代的0需要變成1)。這樣就需要在里所解碼前對數據進行強制性的偵測決定。

我們有現成的python模塊來運算出糾錯碼——python的reedsolo模塊。我們可以對照官方文檔中的糾錯特性表。以下表為例:

跟我一起學習玩轉二維碼

以版本1-H為例進行解釋,從表中,我們可以清晰的知道,糾錯碼字數應該為17個,糾錯的塊數為1(表示這個版本要編碼的數據只會分為一個數據塊),(26,9,8)表示,這個版本的二維碼總共可以存放26個碼字,但是這26個碼字中,有9個碼字為數據碼字,17個為糾錯碼字(8*2+1=17),8位糾錯容量。每個表的下方否有注釋信息:

跟我一起學習玩轉二維碼

這也是為什么糾錯碼字數為r*2,當后面有一個箭頭時,表示r*2之后還要加1。在給數據碼字添加糾錯碼時,還有對數據碼字分塊的操作,因為version1的二維碼對數據碼字之分一個塊,不夠明顯,所以我們采用網上的一個例子:

跟我一起學習玩轉二維碼上述的Version 5 + Q糾錯級:需要4個塊(2個塊為一組,共兩組),頭一組的兩個Blocks中各15個字節(數據碼字)數據 加上 各 9個字節的糾錯容量(18個字節的糾錯碼字)。因為二進制寫起來會讓表格太大,所以,都用了十進制來表示,我們可以看到每一個數據塊的糾錯碼有18個字節,也就是18個8bits的二進制數。

跟我一起學習玩轉二維碼

5.   最終編碼,穿插放置。

此時,編碼的過程,只剩下最后一步。

對于數據碼字:把每個塊的第一個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

對于糾錯碼,也是一樣:

跟我一起學習玩轉二維碼

和數據碼取的一樣,得到:213,87,148,235,199,204,116,159,…… …… 39,133,141,236

然后,再把這兩組放在一起(糾錯碼放在數據碼之后)得到:

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加零就好了。關于哪些Version需要多少個Remainder bit,可以參看官方文檔的表一(這里列出一部分)。

跟我一起學習玩轉二維碼

掩碼(也叫掩模)

編碼的步驟是完成了,但是要想生成一個完好的二維碼,還需要先將現在所擁有的數據填入提前準備的空白模板后,選擇一個合適的掩碼,將原模板的數據與掩碼進行異或運算,最后,再將format information填進去就生成了二維碼。掩碼存在的意義:二維碼是要拿來掃描的,而掃描怕的就是無法清晰地分辨出編碼信息的每一位。要是二維碼中黑白點數量不均,或是空間分布不均都會導致大色塊區域的出現,而大色塊區域的出現會增加掃描時定位的難度,從而降低掃描的效率。更嚴重的情況下,如果數據填入后碰巧出現了功能性標識,比如定位標識的圖樣,還會干擾正常功能性標識的作用,導致QR碼無法掃描。在計算機科學中,掩碼就是一個二進制串,通過和數據進行異或運算來變換數據。在QR碼中,掩碼也是通過異或運算來變換數據矩陣。所以你可能已經猜到了,QR碼的掩碼就是預先定義好的矩陣。QR標準通過生成規則定義了八個數據掩碼:

跟我一起學習玩轉二維碼前面的三位二進制的數據就是每個模式掩碼相對應的編號,這個信息也是要填入format information中的。

跟我一起學習玩轉二維碼從這個圖我們就可以直觀的看到每種掩碼的模板樣子,以掩碼2(編號為010)為例,j mod 3 = 0 就是表示從左變開始數,能被3整除的列,都要取逆(黑塊變白塊,白塊變黑塊),當然二維碼的固定格式區域的信息時不用取逆的,所以要使用掩碼2,需要取逆的列數為:0、3、6、9…..。

跟我一起學習玩轉二維碼當然,官方規定在進行異或時,原始的數據模板要與每個掩碼模板進行異或運算后,要進行如下的規則進行計分(處罰),最后選擇分數最低的一個作為最佳的掩碼選擇。

跟我一起學習玩轉二維碼

另外,使用python的reedsolo模塊,能夠在二維碼損壞超出相應級別的容錯范圍時也能夠恢復數據。

Python2環境下的reedsolo模塊基本使用方式

1. 首先安裝reedsolo模塊,python官方下載的reedsolo模塊版本為0.3,不是很好用,這次使用的reedsolo模塊存放在下載包中的reedsolomon-master.zip,解壓后在該路徑下運行cmd命令python setup.py install即可。

跟我一起學習玩轉二維碼2.     進入python環境,導入reedsolo模塊。定義一個對象,設置生成的糾錯碼個數為10個。

跟我一起學習玩轉二維碼3.    為字符串“hello world”編碼,生成糾錯碼。

跟我一起學習玩轉二維碼

4.   進行解碼

跟我一起學習玩轉二維碼5.    現在大致了解了reedsolo模塊的使用方法,那現在了解一下糾錯碼的作用,比如,我們現在將“hello world”寫成錯誤的“hellx xorld”,這里我們出現了兩個錯誤,配上之前生成的糾錯碼進行解碼,輸出的就是正確的字符串,糾錯碼就是這樣了。

跟我一起學習玩轉二維碼6.    糾錯碼算法是對所要糾錯的內容一個字節一個字節地進行編碼,所以編碼后生成的是一個字節數組。

7.   將編碼后的內容轉化為十進制輸出

跟我一起學習玩轉二維碼

學以致用,復現MMA2015-MISC400-qr的二維碼恢復挑戰的解題步驟,原版write-up地址為:https://github.com/pwning/public-writeup/blob/master/mma2015/misc400-qr/writeup.md

1.   題目給出的二維碼如下圖

跟我一起學習玩轉二維碼

這是一個25*25的二維碼,也就是version2的二維碼,二位從它能看見的部分我們可以得到format information的一部分信息:??????011011010

2.   對照下面這個網址所給出的對應表,可以知道這個二維碼使用了什么編碼模式和使用了哪一個掩碼

https://www.thonky.com/qr-code-tutorial/format-version-tables#list-of-all-format-information-strings

跟我一起學習玩轉二維碼

經對照可知,完整的format information信息應該是:010111011011010。且可以得到的信息還有該二維碼使用的掩碼為6,所對應的糾錯等級為Q。

3.   將被遮擋的固定信息部分以及format information信息補充完整。

跟我一起學習玩轉二維碼  與相對應的掩碼進行異或運算,得到原始的數據中的一部分數據碼字和糾錯碼字。下圖就是掩碼6相對應的圖案。

跟我一起學習玩轉二維碼4.    將掩碼應用到我們補充完的二維碼上,翻轉與掩碼中深色區域相對應的區域的顏色,并用灰色將format information覆蓋,方便讀取數據,如下圖。

跟我一起學習玩轉二維碼

5.   從右下角開始,按下圖的蛇形順序讀取數據碼字和糾錯碼字的信息,至于不同區域塊的信息讀取順序,可以參考官方文檔。

跟我一起學習玩轉二維碼跟我一起學習玩轉二維碼

跟我一起學習玩轉二維碼且相對應的數據塊分布應該如下圖所示:

跟我一起學習玩轉二維碼

6.   將全部可讀的信息讀取出來:      

跟我一起學習玩轉二維碼

7. 根據官方文檔的糾錯特性表,可知version2-Q的糾錯碼字數有22個,數據碼字數也有22個,在Q級別,它可以恢復不超過25%的損壞的字節,但是我們只有16個完整的字節,即超過63%的字節丟失,仔細查看Reed-Solomon的糾錯能力,并意識到它可以糾正多達兩倍的擦除——也就是說,如果 它知道錯誤在哪里,那么糾錯能力就強得多。這意味著我們的代碼可以從丟失的字節的50%恢復過來!但這意味著我們只能糾正多達22個丟失的字節,但是我們目前依然只有16個完整的字節,所以我們要想辦法恢復一部分字節使得達到22個字節這個最低要求。

跟我一起學習玩轉二維碼

8.   我們先將獲得的可讀取數據整理一下:

     0010:【編碼模式=字符編碼(字母數字模式)】

     000010100:【9個bit長度的字符計數標識符=20個字符】

     01010111000:【FL】

     00111010010:【AG】

     11001100110:【 I】

     1010001000?:【S?】

我們計算一下,22個數據碼字,就是176個bit,而20個字符,在編碼的時候分為10組,每組11個bit,所以4+9+10*11=123個bit,123/8=15余3,再加上4個0(結束符) ,以及8bit重組時需要補充為8的倍數,8-3-4=1,所以還需要加1個0。這時候總共也就16個數據碼字,22-16=6,所以還要加上6個 字節的 補齊碼,如下(紅色的是原本被遮住的數據):

00100000 10100010 10111000 00111010 01011001 10011010 10001000 ???????????????? ???????? ???????? ???????? ???????? ???????? ???????? ??000000     1110110000010001 11101100 00010001  11101100  00010001

這樣,我們就回復了6個字節的數據,此時我們丟失的字節就只剩下22個了,正好達到了最低的要求。我們就可以使用糾錯碼恢復原本的數據。

9.   編寫腳本利用python的reedsolo模塊進行糾錯。

跟我一起學習玩轉二維碼

10.   得到全部的信息。

跟我一起學習玩轉二維碼

11. 拆分和解碼

跟我一起學習玩轉二維碼參考文獻

https://zhuanlan.zhihu.com/p/21463650     

https://coolshell.cn/articles/10590.html

官方文檔(中文版):

https://wenku.baidu.com/view/ef77275f312b3169a451a4a4.html?pn=50

里德-所羅門碼:

https://www.jianshu.com/p/8208aad537bb    

https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders#Encoding_outline

https://stackoverflow.com/questions/30363903/optimizing-a-reed-solomon-encoder-polynomial-division

MMA2015-MISC400-qr的write up:

https://github.com/pwning/public-writeup/blob/master/mma2015/misc400-qr/writeup.md

合天智匯:

http://www.hetianlab.com/expc.do?ec=ECID3581-0d42-4928-b602-ddd8e61b24a3

*本文作者:LEdge1,轉載請注明來自FreeBuf.COM

這些評論亮了

  • hetianlab (1級) 領先的實踐型網絡安全在線學習平臺-合天網安實驗室 真實環境,... 回復
    大段copy我們網站實驗指導書內容,不注明來源的嗎?
    )16( 亮了
發表評論

已有 14 條評論

取消
Loading...

填寫個人信息

姓名
電話
郵箱
公司
行業
職位
css.php jizzz