茹 宇，劉嘉勇，湯殿華

(1.四川大學 電子信息學院，四川 成都 610064；2.保密通信重點實驗室，四川 成都 610041)

基于三角拓撲結構的指紋加密方案*

茹 宇1，劉嘉勇1，湯殿華2

(1.四川大學 電子信息學院，四川 成都 610064；2.保密通信重點實驗室，四川 成都 610041)

模糊金庫作為生物加密領域的經典算法已得到廣泛應用。在模糊金庫方案的基礎上，提出一種基于三角拓撲結構的指紋加密方案。首先提取帶有三角拓撲結構的指紋特征細節(jié)點，然后構造多元線性函數(shù)，將細節(jié)點映射到多元線性函數(shù)上，添加干擾集，生成指紋加鎖集。在解鎖時，比對樣板細節(jié)點和模板細節(jié)點三角拓撲結構，對樣板圖像進行配準。實驗結果表明，該方案解決了樣板指紋需要提前配準的問題，同時很大程度上縮減了秘密信息恢復的時間，提高了系統(tǒng)的效率。

模糊金庫 三角拓撲 多元線性函數(shù)

0 引 言

隨著信息技術和互聯(lián)網技術的普及，信息安全成為人們關注的焦點。然而傳統(tǒng)身份認證，由于用戶口令或者鑰匙容易被盜、丟失、復制，已經不能滿足現(xiàn)代信息安全的需求。生物特征加密技術是將生物識別技術與密碼學理論相結合，克服了傳統(tǒng)身份認證的局限。在所有生物特征中，指紋的綜合性能較高，已被得到廣泛的應用。針對密鑰產生或使用方式的不同，將生物特征加密分為密鑰綁定、密鑰釋放和密鑰生成三種方式[1]。而這三種方式，密鑰綁定方式發(fā)展相對成熟。Jules等人在模糊承諾方案的基礎上提出了模糊金庫方案(Fuzzy Vault)[2]。在Jules等人工作的基礎上，Liu和Wang 提出基于混沌序列的密鑰綁定算法[3]。Uludag等提出了基于多項式的指紋Fuzzy Vault算法[4]，在加鎖Vault和解鎖Vault時都需要構造多項式。但是他們的方案中都存在不足：①匹配時，假設指紋圖像已經配準，然而在實際應用中是不可能的；②恢復秘密信息的細節(jié)點的個數(shù)由多項式的階決定，細節(jié)點數(shù)目過少，會導致系統(tǒng)錯識率提高，從而增加非法用戶獲取簽名密鑰的風險[5]，而較多的細節(jié)點可以提供更高的安全性，然而高階多項式系數(shù)求解的復雜度較高，恢復秘密信息比較耗時。

本文在原始Fuzzy Vault的基礎上提出一種基于三角拓撲的指紋加密方案。提取帶有三角拓撲結構細節(jié)點特征信息，通過分段秘密信息和偽隨機數(shù)構造多元線性函數(shù)，生成加鎖集，解鎖時對細節(jié)點三角拓撲結構進行比對，匹配細節(jié)點，求解多元線性函數(shù)系數(shù)，恢復秘密信息。實驗結果表明該方案克服了現(xiàn)有Fuzzy Vault方案需要預配準、求解多項式耗時的問題，提高了系統(tǒng)的安全性。

1 基于三角拓撲結構的指紋加密方案

由于位移，旋轉，非線性失真，壓力和皮膚狀況等情況，同樣手指的指紋可能不同，同時高階多項式求解比較耗時。因此在加鎖時，本文采用多元線性函數(shù)綁定指紋細節(jié)點和系統(tǒng)秘密信息。而在解鎖時首先比對樣板指紋和模板指紋的三角拓撲結構，對樣板指紋進行配準，然后比對樣板指紋細節(jié)點與模板指紋細節(jié)點的相似性，得到匹配細節(jié)點集合，恢復秘密信息。本文方案主要包括，指紋模糊金庫加鎖，指紋模糊金庫解鎖兩個階段，所有運算均在有限域GF(216+1)內進行。

1.1 指紋模糊金庫加鎖

模糊金庫加鎖主要通過構造多元線性函數(shù)綁定細節(jié)點和系統(tǒng)秘密信息，同時添加干擾點，隱藏真正的細節(jié)點。

(1)指紋特征細節(jié)點提取

指紋細節(jié)點的類型主要有端點、叉點、中心點和三角點。對模板指紋圖像預處理，提取指紋特征細節(jié)點集合Tp={mi=(xi,yi,θi,tri1,tri2,tri3,ti)},其中，1≤i≤n，n為細節(jié)點個數(shù)，xi為指紋特征細節(jié)點的橫坐標，yi為指紋特征細節(jié)點的縱坐標，θi為指紋特征細節(jié)點的方向場角度，ti為細節(jié)點的類型，tri1，tri2，tri3為細節(jié)點的三角拓撲結構。細節(jié)點mi的三角拓撲結構示意圖如圖1所示，具體提取過程如下：

1)提取細節(jié)點mi(1≤i≤n)的橫、縱坐標xi,yi,，方向角θi以及類型ti。在此基礎上以mi為圓心，以R為半徑作圓。

2) 將細節(jié)點mi的方向角θi逆時針旋轉45°，與圓周的第一個交點記為頂點1，此點的方向場角度記為tri1。

3)在頂點1為基礎上，作該圓的內接正三角形，與圓周的交點依次記為頂點2和頂點3，方向場角度分別記為tri2，tri3。

細節(jié)點mi的三角拓撲結構由其內接正三角形三個頂點的方向角構成，tri1，tri2，tri3∈[0，180)。對超出圖像表示范圍的頂點，將其的方向角度均設為固定值255。

圖1 細節(jié)點mi的三角拓撲結構示意

(2)構造多元線性函數(shù)

假設系統(tǒng)隨機產生秘密信息K，長度一般為128 bit，需要d(d>8)個細節(jié)點來綁定秘密信息。

1)構造系數(shù)矩陣。將K從高位到低位，分割為8段，每段長度為16 bit，分別記為a7，a6，a5，a4，a3，a2，a1和a0。系數(shù)a8，…，a(d-2)為隨機產生的16 bit數(shù)。連接a0～a(d-2)，計算連接值的CRC-16值記為a(d-1)。得到多元線性函數(shù)的系數(shù)矩陣記為A=[a0,a1,a2,a3,…,a(d-1)]。

2)產生多元線性函數(shù)，生成真實細節(jié)點集合。連接指紋模板Tp中細節(jié)點mi的xi和yi(1≤i≤n)，記為：gi=xi||yi；以gi作為種子，生成16 bit偽隨機數(shù)分別記為ri1，ri2，…，ri(d-1)，令ri0=gi，mi參數(shù)向量記為：Ri=[ri0,ri1,…,ri(d-1)]，則第i個細節(jié)點的多元線性函數(shù)可用式(1)進行表示

(1)

式中，1≤i≤n，d為綁定秘密信息需要的細節(jié)點個數(shù)，f(Ri)為細節(jié)點mi在線性函數(shù)上的映射。連接所有細節(jié)點的橫、縱坐標，并將其作為種子，生成16 bit偽隨機數(shù)，得到其參數(shù)向量，通過式(1)得到所有細節(jié)點在線性函數(shù)上的映射，生成真實指紋細節(jié)點集合，記為:

Tpt={mi=(xi,yi,θi,tri1,tri2,tri3,ti),f(Ri)|1≤i≤n}

(3)產生干擾點集合

為了隱藏真實指紋細節(jié)點，產生大量的干擾點，干擾點的個數(shù)要遠大于真實點個數(shù)，且與指紋細節(jié)點之間必須滿足一個預設的距離閾值THd，同時干擾點必不能位于秘密信息K的編碼多元線性函數(shù)上。

生成滿足條件的干擾點集合記為

C={mj=(xj,yj,θj,trj1,trj2,trj3),βj}

其中1≤j≤n，βj≠f(Rj)，r(r>>n)為產生干擾點個數(shù)，βj∈(0,217-1)，θj∈(0,360)，trj1∈(0,360)，trj2∈(0,360)，trj3∈(0,360)和tj∈(1,2,3)。

(4)生成加鎖集合

混合真實指紋模板加鎖集Tpt和干擾點集合C，并置亂，形成模糊金庫加鎖集記為

Tptc=Tpt∪C={ms=(xs,ys,θs,trs1,trs2,trs3,ts)f(Rs)}

其中，1≤s≤n+r，n+r表示總數(shù)。

1.2 指紋模糊金庫解鎖

模糊金庫解鎖，通過用戶提供的指紋樣板，與指紋模板的模糊金庫加鎖集匹配，分離出干擾點，從中提取到真實細節(jié)點，恢復出系統(tǒng)秘密信息。

采用1.1節(jié)模板指紋細節(jié)點的提取方法，提取樣板指紋細節(jié)點集合，記為

Fp={mj′=(xj′,yj′,θj′,trj1′,trj2′,trj3,tj′)}

其中，1≤j≤n′，n′表示樣板細節(jié)點個數(shù)。

(1)樣板細節(jié)點配準

首先，從指紋模板mi(1≤i≤n)與樣板mj′(1≤j≤n′)中各任取一點，比較兩個細節(jié)點的類型，若類型不同，則重新從指紋樣板中取一細節(jié)點。

其次，比對兩個細節(jié)點的三角拓撲結構相似性，即計算θi和tri1的方向場角度差C1=|θi-tri1|與θj′和trj1'的方向場角度差C1′=|θj′-trj1′|，以及三角拓撲結構中相互兩個頂點之間的方向場角度差，如果mi和mj′對應角度誤差均在預先設定的角度誤差范圍之內，則認為兩個細節(jié)點的三角拓撲結構相似。若不相似，則重新從指紋樣板中取一細節(jié)點，與指紋模板細節(jié)點比對三角拓撲結構是否相似。然后，對于相似的細節(jié)點，假設樣板中第z個細節(jié)點mz′與模板中的細節(jié)點mi三角拓撲結構。相似則計算兩個細節(jié)點的角度旋轉量：Δθ=(θi-θz′)mod360、橫坐標偏移量：Δx=xi-xz′、縱坐標偏移量：Δy=yi-yz′。通過式(2)對樣板細節(jié)Fp點進行配準，配準后的指紋樣板記為

Ap={mj″=xj″,yj″,θj″,trj1″,trj2″,trj3″,tj″}

其中，1≤j≤n′。

(2)

(2)指紋細節(jié)點匹配

指紋特征細節(jié)點匹配即指紋模板Tptc與配準后的指紋樣板Ap中細節(jié)點的匹配，必須滿足兩個條件：

1)當兩個細節(jié)點滿足式(3)匹配條件時，認為此兩點是匹配的

(3)

式中，Δθ、Δx、Δy和Ed分別表示當前兩個細節(jié)點的夾角、水平距離、垂直距離和距離；THθ、THx、THy和THEd分別表示夾角閾值、水平距離閾值、垂直距離閾值和歐氏距離閾值。

2)當相互匹配的細節(jié)點個數(shù)及相似度均大于預先設定的合格閾值時，認為指紋樣板與模板匹配成功，來自同一手指。得到匹配點集合記為TGmatch={xk,yk,f(Rk)}，其中，1≤k≤n，k為相互匹配的細節(jié)點個數(shù)。

指紋模板與配準后的樣板之間的相似度說明了兩組細節(jié)點集合比對的一致程度，記為SD

SD=4×score×k×maxpnum/(2n′)2

(4)

其中，maxpnum：表示最大指紋特征細節(jié)點個數(shù)；score表示分數(shù)，記錄指紋模板與配準后樣板上可能匹配的細節(jié)點之間，對應特征元素的相對誤差大小累計情況?？山⑷缡?5)所示的關系：初始score=0。

score=score+(THθ-Δθ)+(THEd-Ed)

(5)

設相似度SD的合格閾值記為THSD，細節(jié)點匹配個數(shù)為綁定秘密信息的細節(jié)點個數(shù)為d，只有匹配的細節(jié)點個數(shù)k≥d，相似度SD≥THSD，則認為樣板指紋匹配成功。

(3)重構多元線性函數(shù)，恢復秘密信息K

假設，恢復秘密信息需要d個細節(jié)點，從匹配點集合TGmatch中任選d個點作為候選點集。令gk=xk‖yk,(1≤k≤n)，以gk作為種子產生16 bit偽隨機數(shù)分別記為rk1，rk2，…，rk(d-1)，令rk0=gk。對于每個細節(jié)點的gk，都會得到細節(jié)點mk參數(shù)向量記為

Rk=[rk0,rk1,…,rk(d-1)]

對于每組細節(jié)點候選集，通過式(6)可以得到多元線性方程組

(6)

令f=[f(R0),f(R1),…,f(R(d-1))]T，

A′=[a0′,a1′,…,a(d-1)′]，

則多元線性方程可以表示為

f=A′Rmod65537，

(7)

由于作為種子的gk各不相同，所以得到的參數(shù)向量矩陣每行互不相關，即行列式|R|≠0，則可得到A′=fR-1mod65537。

將a0′，a1′，…，a(d-2)′連接起來，計算連接值的CRC-16值，如果該值等于a(d-1)′，則秘密信息

k=a7′‖a6′‖a5′‖a4′‖a3′‖a2′‖a1′‖a0′，解鎖成功。反之，則需要從匹配點集合TGmatch中在另選d個點重新構造多元線性函數(shù)。若遍歷完匹配點集合中的所有組合都不能恢復出秘密信息，則說明匹配點集合中假細節(jié)點數(shù)量過多。

2 實驗結果與安全性分析

2.1 實驗結果分析

為了驗證本方案的準確性和有效性，本文利用公開指紋庫FVC2004-DB2中的來自100個不同手指的800幅圖像測試評估該方案性能。指細節(jié)點平均個數(shù)為35，添加干擾點個數(shù)300。本文將兩個細節(jié)點三角拓撲的角度誤差設置為8，匹配條件閾值參數(shù)為：夾角閾值THθ=10、水平閾值THx=10、垂直閾值THy=10、距離閾值THEd=10，相似度閾值THSD=100。

對于真匹配，用指紋庫中同一手指的每一個圖像和余下圖像進行比較，進行2 800次真匹配；對于假匹配，取每個手指中細節(jié)點個數(shù)最多的指紋圖像與其余來自不同手指的圖像比較，進行74 250次假匹配測試。依次測試匹配細節(jié)點個數(shù)9到13對應的指紋匹配拒識率(FRR)和誤識率(FAR)，并計算該方案恢復秘密信息需要的時間。

通過表1可以看出隨著匹配時需要細節(jié)點個數(shù)的增多，誤識率FRR逐漸增大，拒識率FAR逐漸減。

表1 不同匹配細節(jié)點個數(shù)的匹配結果

通過表2可以看出，本文采用構造多元線性函數(shù)方案較Uludag等人構造多項式方案大大縮減了時間，因為重構高階多項式的計算比較費時。

表2 比較不同方案恢復秘密信息的平均時間

2.2 安全性分析

本文在構造線性函數(shù)時，引入隨機數(shù)，相對于傳統(tǒng)的模糊金庫方案，函數(shù)的階數(shù)不在由秘密信息的長度決定，而是可以根據要采用的匹配細節(jié)點的個數(shù)來調節(jié)，很大程度上提高了系統(tǒng)的安全性。

由于真實指紋細節(jié)點中添加了大量的干擾點，起到對真實點隱藏的作用，如果攻擊者要從Fuzzy Vault中分離真實細節(jié)點比較困難。同時對于恢復秘密信息需要的細節(jié)點數(shù)越多，攻擊者破解秘密信息的難度也就越大。對于暴力破解，假設攻擊者沒有真實指紋的數(shù)據，用本文方法來計算攻擊者需要嘗試的次數(shù)。文獻[6]指出，只有12個以上的細節(jié)點匹配才是可靠的，因此，取d為13。平均細節(jié)點個數(shù)為35，干擾點個數(shù)為300，則攻擊者需要嘗試的次數(shù)T為:

相當于攻擊者要破解24個字母和10個數(shù)字隨機組合的10位數(shù)的次數(shù)(3410≈2.06×1015)，所以暴力破解的難度也是比較大的。

3 結 語

本文以指紋三角拓撲結構為基礎，采用多元線性函數(shù)綁定秘密信息，匹配時并未對活體指紋樣板進行提前配準操作，而是在解鎖過程中通過對比三角拓撲關系實時配準，得到相互匹配的點對，從而恢復出秘密信息，這在一定程度上改善了提前配準問題。同時實驗結果表明，該方案在很大程度上縮減了恢復秘密信息的時間，提高了效率。然而在指紋模安全性方面還需要進一步提高。

[1] 李鵬，田捷，楊鑫.生物特征模板保護[J]. 軟件學報，2009，20(06):1553-1573. LI Peng, TIAN Jie, YANG Xin. Biometric Template Protect [J] Journal of Software 2009，20(06):1553-1573.

[2] Juels A,Sudan M. A Fuzzy Vault Scheme[J]. Designs, Codes and Cryptography, 2006, 38(2): 237-257.

[3] Hong-wei L,Yao W. A New Fuzzy Fingerprint Vault Using Multivariable Linear Function based on Lorenz Chaotic System[C]//Computer Science and Automation Engineering (CSAE), 2012 IEEE International Conference on. [s.l.]:IEEE, 2012: 531-534.

[4] Uludag U,Pankanti S,Jain A K. Fuzzy Vault for Fingerprints[C]// Audio-and Video-Based Biometric Person Authentication.[s.l.]:Springer Berlin Heidelberg,2005:310-319.

[5] 李丹, 卿昱, 譚平嶂. 一種基于生物特征加密技術的數(shù)字簽名方案[J]. 通信技術, 2010，43 (02): 128-130. LI Dan, QING Yu, TAN Ping-zhang. A Digital Signature Scheme based on Biometric Encryption[J]. Communications Technology, 2010,43(02):128-130.

[6] Pankanti S, Prabhakar S, Jain A K. On theIndividuality of Fingerprints[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on,2002,24(8):1010-1025.

RU Yu(1987-), male , M.Sci. , mainly working at network communication and network security.

劉嘉勇(1962—)，男，教授，博士，主要研究方向為信息安全理論與應用、網絡通信與網絡安全；

LIU Jia-yong(1962-), male, professor, Ph.D., principally working at theory and application of information security, network communication and network security.

湯殿華(1986—)，男，碩士，主要研究方向為信息安全理論與應用。

TANG Dian-hua(1986-)，male， M.Sci., mainly working at theory and application of information security.

Fingerprint Encryption Scheme based on Triangle Topology

RU Yu1，LIU Jia-yong1，TANG Dian-hua2

(1.College of Electronic and Information Engineering, Sichuan University, Chengdu Sichuan 610064, China;2.Science and Technology on Communication Security Laboratory,Chengdu Sichuan 610041, China)

Fuzzy vault, as a classical encryption algorithm, is widely used in biometric encryption. Based on Fuzzy Vault scheme by Jules et al., this paper proposes a fingerprint encryption scheme triangular topology. Firstly, the fingerprint minutiae feature with a triangular topology is extracted, and then multiple linear functions are constructed,finally, the minutiae is mapped onto multiple linear functions, the inteference set added,and the fingerprint locking set generated. Sample image is registrated by comparing triangle topology of sample minutiae with template minutiae during the unlocking process. Experimental results show that this scheme could solve the advanced registration of sample fingerprint while greatly reducing the time for secret information recovery, thus the system efficiency is improved.

fuzzy vault; triangular topology; multiple linear function

date:2014-09-11；Revised date：2014-12-30

TP309

A

1002-0802(2015)03-0362-05

茹 宇(1987—)，男，碩士，主要研究方向為網絡通信與網絡安全；

10.3969/j.issn.1002-0802.2015.03.022

2014-09-01；

2014-12-30