一種生物證書密鑰生成算法

王金海, 魏 寧, 崔 軍, 李雪妍, 李秀艷

(天津工業大學 電子與信息工程學院, 天津 300387)

?

一種生物證書密鑰生成算法

王金海, 魏 寧, 崔 軍, 李雪妍, 李秀艷

(天津工業大學 電子與信息工程學院, 天津 300387)

生物特征數字證書涉及的RSA公私鑰對可以由近似隨機信號的生物特征密鑰派生，但是生物特征密鑰長度較短，而基于大素數分解困難的RSA算法要求密鑰較長. 為了解決該問題，提出一種生物證書密鑰生成算法，結合對稱加密算法和大素數生成算法生成生物大素數，并采用哈希算法對生物大素數進行可用性設計，在解決密鑰長度問題的同時保證生物大素數安全可用，以便用于生成生物特征數字證書中的RSA公私鑰對. 基于VC6.0和MIRACL大數庫的實驗結果表明：基于生物特征密鑰生成的生物大素數滿足確定性和可用性，能夠應用于生物數字證書之中. 本文所提算法行之有效，且具有實際應用價值.

生物特征加密; 生物證書; 生物特征密鑰; RSA; 大素數

近年來，快速發展的生物特征加密技術越來越實用化，其應用到數字證書的研究與日俱增[1-3]. 文獻[4]于2007年提出了生物證書的概念，把生物證書定義成CA頒發的綁定了用戶身份及其生物特征信息并經過CA簽名的數據結構. 國內學者提出了一種基于生物屬性證書的生物認證系統，進一步推動了生物特征與數字證書的結合研究[5-6].

事實上，基于原始生物特征數據直接或間接生成的生物特征密鑰(簡稱BioKey，生物密鑰)是指一個穩定的近似隨機的二進制序列[7]. 它的長度是相對有限的，一般為百位左右比特量級[8]，如Nandakumar[9]使用指紋庫FVC2002-DB2基于指紋Fuzzy Vault生成的BioKey長度為128 bits， George S. Eskander[10]基于各種生物特征使用Fuzzy Vault算法生成的各生物特征的密鑰熵為69 bits. 而數字證書對密鑰是有一定要求的，主要體現在RSA算法對密鑰的要求上. RSA算法是基于“對于兩個大素數p和q，計算它們的乘積n(n的二進制位數即為密鑰長度)十分容易，但要對n進行因式分解得到p和q卻極其困難”的思想，將乘積n公開，作為公開密鑰. RSA算法的安全性依賴于大素數n被分解的難度. 在實際應用中，為保證加密的安全性和可靠性，RSA算法要求大素數p和q均為512 bits，即RSA的密鑰長度為1024 bits[11].

針對長度較短的BioKey無法滿足數字證書中RSA算法對密鑰要求的問題，目前相關探討較少，僅在2012年，Vincenzo[12]提出了一種基于生物特征密鑰利用映射表生成RSA公私鑰對的方法，但是該文獻沒有詳細描述如何構造映射表以及進一步評估論證派生的大素數p和q是否安全可用和唯一確定. 而且注意到，這個映射表中大素數的個數是2n，是相對有限的，這樣肯定導致不同BioKey映射成相同大素數p和q的碰撞概率較大. 但是通過增大2n值來降低碰撞概率顯然是不可取的，因為存儲映射表的智能卡存儲空間是有限的. 假設這個映射表里有100 000個512 bits的大素數，那么就要求智能卡的容量至少達到64 MB，而這個量級的存儲容量是當前一般智能卡所不支持的.

因此，對基于較短BioKey構造出長度相對較長的BioRSA大素數p和q(簡稱BioPrimes，生物大素數)的密鑰擴散問題進行研究是很有必要的. 如何由BioKey生成BioPrimes是本文擬解決的首要問題，當然，在此基礎上，生成的BioPrimes還應滿足確定性(即同一個BioKey每次都會確定生成同一個BioPrimes)和可用性(即生成的BioPrimes可以無差錯地應用到RSA算法中). 因此，本文除了研究BioPrimes生成方法之外，還需要對生成的BioPrimes做關于可用性和確定性的設計與驗證.

針對以上問題，本文基于長度較短的BioKey提出一種RSA大素數生成方法，即由BioKey構造出長度相對較長的BioRSA大素數p和q，即BioPrimes.

1 RSA算法和大素數生成算法

1.1 RSA算法

RSA算法是一種典型的公鑰密碼算法，具有公開密鑰和私有密鑰兩個緊密相關但卻不同的密鑰，即公鑰和私鑰：1)公鑰可以公開給任何人，用于加密數據(僅對應的私鑰能解密)，或驗證簽名(對應私鑰進行簽名)；2)私鑰不能公開，必須安全保存. RSA算法的理論基礎是一種特殊的可逆模指數運算，它的安全性基于分解大素數n的困難性，其算法描述如下[13]：

1)獨立地選取兩個大素數p和q(保密)，計算n=pq(公開)，φ(n)=(p-1)(q-1)(保密)，其中φ(n)是歐拉函數；

2)選取一個整數e，滿足1≤e<φ(n)，且gcd(φ(n),e)=1，其中gcd()表示求最大公約數；

3)計算d(保密)，滿足ed=1mod φ(n)，即d是e在模φ(n)下的乘法逆元；

4){e,n}為公鑰，{d,n}為私鑰，p和q則丟棄.

假設要加密的明文為M，密文為C，則加密過程為C=E(M)=Me(mod n)，解密過程為M=D(C)=Cd(mod n).

RSA算法中的p、q、φ(n)和d是秘密保存的，只有私鑰擁有者才知曉. 如果要對RSA算法加密后的密文進行破譯，唯一可能的破解方法就是對公鑰{e,n}中的n進行因子分解. 對于大素數的因子分解，分解次數與其長度有關，隨著密鑰長度的增加，分解所需的時間就會成指數增加，密鑰就越難破譯，加密強度就越高.

由此可見，要使RSA加密的數據安全可靠，關鍵是生成兩個滿足長度要求的大素數p和q. RSA加解密算法的安全性與其所使用的大素數有密切關系，構造符合RSA安全體系要求的大素數是RSA算法實用化的基礎. 因此，針對生物特征密鑰與公鑰數字證書的結合應用，研究基于較短BioKey生成較長BioPrimes，對BioRSA算法的安全性具有實際應用價值.

1.2 大素數生成算法

素數生成的核心問題是判斷一個數是否為素數. 目前，生成素數的一般方法可以分為兩類，即確定性素數生成算法和概率性素數生成算法.

確定性素數生成算法是指其生成的數一定是素數. 在確定性素數生成算法中，素數是按照一定公式或者能夠滿足素數充分必要特性的規則進行素數生成. 現有的確定性素數生成算法有許多，其中比較有代表性的是AKS算法[14]. 這類算法的優點是生成的必然是素數，但卻帶有一定的限制. 假若算法設計不佳，便容易構造出帶有規律性的素數，攻擊者能夠分析出素數的變化，進而可以猜到該系統中使用的素數. 另外確定性素數生成算法運行耗時太長，因此在實際應用中較少采用.

概率性素數生成算法與確定性素數生成算法的最大不同是其生成的數可能是偽素數，盡管其生成合數的可能性很小，但不能為0. 此類方法缺點明確，即存在誤判的可能性；優點也很明顯，就是生成速度較快，生成的素數無規律. 概率性素數生成算法是當前素數生成的主要方法，其中較為著名的算法有Miller-Rabin算法[15]等.

本文以這兩種大素數生成算法為基礎，通過合理設計與驗證，選擇實用的大素數生成算法，實現生物大素數生成.

2 一種生物證書密鑰生成算法

如何由長度相對較短的BioKey構造出確定的BioPrimes，進而保證其真正可用，最終生成BioRSA公私鑰對并應用于證書中，本文將給出一種基于生物特征的生物證書密鑰生成算法，該方法分為注冊和驗證兩個階段.

2.1 注冊階段

注冊階段旨在基于由生物特征圖像利用Fuzzy Vault算法生成的128 bits BioKey間接構造出可用于RSA算法中的512 bits BioPrimes. BioKey應用于BioRSA時必須保證其可用性，即保證生成的BioPrimes可以無差錯地應用到RSA算法中. 可能的問題點：1)在驗證階段，BioKey恢復時并不能保證與注冊時生成的BioKey完全相同；2)在生物大素數生成方法中，不同的素數生成算法會導致BioPrimes的生成概率不一定是百分之百，即不能完全保證同一個BioKey每次都會確定生成同一個BioPrimes. 所以，最終得到的BioPrimes并不一定能用于生成BioRSA公私鑰對. 本文采用哈希算法解決這兩個問題.

哈希算法[16]是將任意長度的二進制值映射為較短的固定長度的二進制值，這個小的二進制值稱為哈希值. 哈希值是一段數據唯一且極其緊湊的數值表示形式. 如果修改一段明文而且哪怕只更改該段落的一個字母，隨后的哈希都將產生不同的值. 要找到哈希值相同的兩個不同的輸入，在計算上幾乎是不可能的. 目前比較常用的哈希算法是MD5和SHA-1.

參照圖1，注冊階段具體包含以下幾個步驟：

1)輸入128 bits 注冊BioKey，并對其做隨機數測試[17]，以保證BioKey為近似隨機數；

2)將通過隨機數檢測的注冊BioKey做哈希運算，得到注冊BioKey的哈希值；

3)隨機產生兩個512 bits通過隨機數測試的隨機數因子；

4)將BioKey作為對稱加密算法(如AES[17])密鑰用來加密兩個隨機數因子，得到兩個幫助數據；

5)將BioKey分別與兩個隨機數因子異或，異或后的值利用大素數生成方法生成512 bits BioPrimes；

6)512 bits BioPrimes一方面通過哈希運算得到生成BioPrimes的哈希值，另一方面進行BioRSA公私鑰對生成，以便用于證書中.

通過上述步驟，128 bits的近似偽隨機數BioKey首先間接生成512 bits大素數BioPrimes，然后再由BioPrimes生成公私鑰對，其中，在注冊階段得到的幫助數據和兩個哈希值均保存起來在驗證階段輔助恢復出BioRSA公私鑰對. 需要注意的是，由于素數生成算法有確定性生成和概率性生成之分，前者可給出確定的結果但通常較慢，后者則反之. 因此，本文后面實驗部分將通過仿真實驗，針對運算性能和確定性，對確定性生成算法和概率性生成算法進行實用性評估，以選擇實用的素數生成算法為本文方法所用.

圖1 注冊階段

2.2 驗證階段

驗證階段過程與注冊階段過程最大的不同體現在：1)通過解密幫助數據得到隨機數因子；2)通過兩次比較哈希值以保證恢復的BioPrimes可用于恢復BioRSA公私鑰對.

流程圖如圖2所示，具體步驟如下：

1)輸入128 bits驗證BioKey，并對其做隨機數測試；

2)對通過隨機數檢測的驗證BioKey做哈希運算，得到驗證BioKey的哈希值；

3)對比注冊BioKey與驗證BioKey的哈希值，若相等轉步驟4)，否則需重新輸入驗證BioKey；

4)將注冊BioKey作為對稱加密算法密鑰用來解密幫助數據，恢復出隨機數因子；

5)恢復出的隨機數因子與驗證BioKey異或后利用大素數隨機數方法恢復出512 bits BioPrimes；

6)512 bits BioPrimes通過哈希運算，得到恢復BioPrimes的哈希值；

7)對比生成BioPrimes與恢復BioPrimes的哈希值，若相等則基于該BioPrimes恢復BioRSA公私鑰對，否則需重生成BioPrimes.

步驟3)中，若注冊BioKey與驗證BioKey的哈希值相等，則說明驗證BioKey與注冊BioKey完全相同，保證了BioKey的可用性；步驟7)中，通過對比生成BioPrimes與恢復BioPrimes的哈希值，保證了同一個BioKey每次都會確定生成同一個BioPrimes，即保證了BioPrimes的可用性. 當然，如果連續多次(例如3次)哈希值對比失敗，則可以認為不是同一個BioKey導致，驗證階段異常終止.

圖2 驗證階段

3 實驗驗證與結果分析

針對BioPrimes素數生成算法選擇實驗、確定性驗證實驗和可用性驗證實驗進行詳細闡述，根據實驗結果選擇合適的素數生成算法，并做確定性和可用性驗證評估.

本文的算法均采用C++語言在VC6.0和MIRACL大數庫仿真環境下實現. MIRACL大數庫(Multiprecision Integer and Rational Arithmetic C/C++ Library)是由Shamus Software Ltd.開發的關于大數運算函數庫，用來設計與大數運算相關的密碼學之應用. 本文主要用到MIRACL庫中isprime函數、nxprime函數、AES加解密函數和SHA-1哈希函數等. 3.1 生物大素數生成算法選擇實驗

分別選用AKS算法和Miller-Rabin算法作為生物大素數生成方法中的確定性、概率性素數生成算法. 如果選擇AKS算法生成生物大素數，理論上同一個BioKey每次都會確定生成同一個BioPrimes，需要檢驗其運算性能是否符合實用要求；如果選擇Miller-Rabin算法，則還需要進一步驗證其理論上的不確定性在實際中體現為多少. 因此本文先實驗對比這兩種算法生成的素數和運算性能(指時間消耗)，從實用性角度選擇合適的素數生成算法來輔助生成BioPrimes.

由于MIRACL函數庫已用isprime函數對Miller-Rabin算法進行封裝，故本文僅需調用isprime函數做Miller-Rabin算法素性判斷即可.

先隨機生成一個n bits的二進制數p并設高低位為1，高位設為1是為了保證隨機數的位數，低位設為1是為了過濾掉偶數. 然后，分別利用AKS算法和Miller-Rabin算法(isprime函數)對p進行素數判定，若p是素數則輸出p和運行時間，反之p自加2再進行素數判定，直到找到比p大的第一個素數(流程圖見圖3). 記錄分別用這兩種方法找到的n bits素數p和其運行所需時間，然后對比分析數據確定選用何種算法輔助生成BioPrimes.

圖3 生物大素數生成算法選擇實驗流程圖

Fig.3 Flowchart of the selection of BioPrimes generation algorithm

根據圖3，編寫調試C++程序，并以表格形式給出分別用AKS算法和Miller-Rabin算法(isprime函數)找到的n bits素數p與運行所需時間的數據結果(見表1).

表1 AKS算法和Miller-Rabin算法對比

由表1的前四行可以看出，當n一定時，利用AKS算法和Miller-Rabin算法(isprime函數)產生的素數相同，但運行時間卻相差很大. 如當n為40時，利用AKS算法找到素數EDD71C57CD的時間為7 303.633 s(約為121.73 min)，而利用Miller-Rabin算法(isprime函數)找到的素數相同，運行時間卻是0.035 s. 當n>40 bits時，AKS算法素數生成整個過程消耗的時間將不可估量，而利用Miller-Rabin算法(isprime函數)生成128位素數僅需0.146 s. 理論上，AKS算法的時間復雜度是O((logn))，而Miller-Rabin算法的時間復雜度是O((logn)/7)，這一實驗結果也驗證了二者的時間復雜度問題. 所以，AKS算法由于時間消耗問題并不適合大整數的素性檢測，故選用Miller-Rabin算法(isprime函數)作為本文所提生物大素數生成方法中的素數生成算法.

3.2 生物大素數確定性驗證實驗

由于Miller-Rabin算法屬于概率性素數生成算法，在其素數判斷過程中可能會誤判，所以需要進一步驗證其理論上的不確定性在實際中體現為多少，即解決保證同一個BioKey每次都會確定生成同一個BioPrimes(即確定性)問題.

進行多次測試，將每次針對同一BioKey生成的BioPrimes'與第一次生成的BioPrimes對比，以表格形式統計記錄實驗結果(見表2)，探究其確定生成的概率.

由表2可知，通過把多次測試的數據與第一次生成的BioPrimes做對比，可認為在一定測試次數范圍內，同一BioKey確定生成同一BioPrimes的概率為100%，即認為采用Miller-Rabin算法(isprime函數)作為素性檢測算法生成BioPrimes滿足確定性. 與128 bits BioKey相比，第一次生成的BioPrimes長度變為512 bits，但是該方法并沒有改變其隨機特性，BioPrimes依然是隨機數.

表2 多次測試統計結果

3.3 生物大素數可用性驗證實驗

上述實驗中，若超出測試范圍，BioPrimes的確定生成概率可能達不到100%，本文通過哈希值對比對其做了可用性設計，以保證即使BioPrimes的確定生成概率不為100%，它也可以用于生成BioRSA公私鑰對. 在注冊與驗證階段得到的哈希值如表3所示.

表3 注冊與驗證階段哈希值對比

Tab.3 Comparison of the hash value of registration and verification phase

名稱注冊階段驗證階段BioKey哈希值da73b78f7df87397d79089025216c118066db51ada73b78f7df87397d79089025216c118066db51aBioPrimes哈希值1bab53e18743f29a42e44c2944f7a3839e7128cd2bab53e18743f29a42e44c2944f7a3839e7128cd2BioPrimes哈希值25cd40a56a505eb58951b17be8d412e3a034363315cd40a56a505eb58951b17be8d412e3a03436331

注：注冊階段和驗證階段的運行時間分別為1.920和1.561 s

從表3可以看出，注冊與驗證階段BioKey的哈希值相等，說明在驗證階段恢復出的BioKey與注冊時生成的BioKey完全相同. 通過對比表3中注冊階段與驗證階段生成的BioPrimes的哈希值，發現它們各自相等，說明生成的BioPrimes可用于生成BioRSA公私鑰對. 注冊階段與驗證階段的運行時間均不到2 s，說明本文所提方法行之有效. 另一方面，基于哈希算法和對稱加密算法的安全性，表3中的這3個哈希值以及注冊階段得到的幫助數據可以安全公開，同時也避免了文獻[12]中存在的把映射表存儲在智能卡引起的存儲容量問題.

以上結果表明，基于BioKey能夠生成滿足隨機性、確定性和可用性要求的BioRSA公私鑰對應用于生物證書中，本文提出的生物證書密鑰生成算法是有實用價值的.

4 結 語

通過研究生物特征密鑰應用到公鑰數字證書的趨勢，針對生物特征密鑰BioKey的長度無法滿足基于時間復雜度的RSA算法對素數的要求的問題，提出一種生物證書密鑰生成算法. 通過哈希算法、對稱加密算法和大素數生成方法，128 bits生物特征密鑰BioKey能夠生成512 bits生物大素數BioPrimes，進而生成BioRSA公私鑰對，最終可應用于生物證書中. 基于VC6.0和MIRACL大數庫實驗選擇合適的素數生成算法，并對BioPrimes做確定性和可用性驗證與評估. 本文所提方法簡單、易實現，滿足RSA算法安全性的實際應用需求，實現了從BioKey到BioRSA的映射，為生物特征密鑰應用到數字證書提供了極大的便利.

[1] LAKAHMI A J, KIRAN P S. PKI key generation based on multimodal biometrics[J]. International Journal OfComputers & Communications, 2012, 1(1): 9-16.

[2] KALAMA A E, IBJAOUN S, OUAHMAN A A. Biometric authentication systems based on hand pattern vein, digital certificate and smart cards[C]// Security Days, 2013 National. Rabat: IEEE, 2013: 1-8.

[3] WANG W, LU Y, FANG Z. Biometric template protection based on biometric certificate and fuzzy fingerprint vault[C]// Advanced Data Mining and Applications. Hangzhou: Springer Berlin Heidelberg, 2013: 241-252.

[4] CHUNG Y, MOON K, LEE H W. Biometric certificate based biometric digital key generation with protection mechanism[C]// Frontiers in the Convergence of Bioscience and Information Technologies. Washington DC: IEEE Computer Society, 2007: 709-714.

[5]李超, 辛陽, 紐心忻, 等. 一種基于生物證書的身份認證方案[J]. 計算機工程, 2007, 33(20): 159-161.

LI Chao, XIN Yang, NIU Xinxin, et al. Identity Authentication Scheme Based on Biometric Certificate[J]. computer engineering, 2007, 33(20): 159-161.

[6]辛陽, 魏景芝, 李超, 等. 基于PKI和PMI的生物認證系統研究[J]. 電子與信息學報, 2008, 30(01): 1-5.

XIN Yang, WEI Jingzhi, LI Chao, et al. Research on the Telebiometric Authentication System Based on PKI and PMI[J]. Journal of Electronics and Information Technology, 2008, 30(01): 1-5.

[7]陳熙. 鑒別生物特征提取及密鑰生成研究[D]. 成都:西南交通大學, 2011.

CHEN Xi. Research on discriminative biometrics feature extraction and key generation[D]. Chengdu:Southwest Jiaotong University, 2011.

[8] RATHGEB C, UHL A. A survey on biometric cryptosystems andcancelable biometrics[J]. EURASIP Journal on Information Security, 2011, 3(1): 1-25.

[9] NANDAKUMAR K, JAIN A K, PANKANTI S. Fingerprint-based fuzzy vault:Implementation and performance[J]. IEEE Transactions on Information Forensics and Security, 2007, 2(4): 744-757.

[10]ESKANDER G S, SABOURIN R, GRANGER E. A dissimilarity-based approach for biometric fuzzy vaults-application to handwritten signature images[C]// New Trends in Image Analysis and Processing-ICIAP 2013. Naples: ICIAP 2013 International Workshops, 2013: 95-102.

[11]劉新星, 鄒瀟湘, 譚建龍. 大數因子分解算法綜述[J]. 計算機應用研究, 2014, 31(11): 3201-3207.

LIU Xinxing, ZOU Xiaoxiang, TAN Jianlong. Survey of large integer factorization algorithms[J]. Application Research of Computers, 2014, 31(11): 3201-3207.

[12]CONTI V, VITABILE S, SORBELLO F. Fingerprint traits and RSA algorithm fusion technique[C]// Complex, Intelligent and Software Intensive Systems (CISIS). Palermo: IEEE, 2012: 351-356.

[13]RSA(cryptosystem) [EB/OL].

[2014.11]. http://en.wikipedia.org/wiki/RSA_(cryptosystem).

[14]AGRAWAL M, KAYAL K, SAXENA N. Primes is in P[J]. Annals of Mathematics, 2004, 160(2): 781-793.

[15]龍建超. 公鑰算法中大素數生成方法的研究與改進[D]. 昆明: 云南大學, 2014.

LONG Jianchao. Research and improvement on the method of generating large prime number in public key algorithm[D]. Kunming: Yunnan University, 2014.

[16]STALLINGS W.密碼編碼學與網絡安全:原理與實踐[M]. 王張宜, 楊敏, 杜瑞穎, 等, 譯. 北京: 電子工業出版社, 2012: 104-131, 236-257.

STALLINGS W. Cryptography and NetworkSecurtiy: Principles and Practice[M]. Bei Jing: Electronic Industry Press, 2012: 104-131, 236-257.

[17]NIST SP800-22. A statistical test suite for random and pseudorandom number generators for cryptographic applications[S]. Gaithersburg: ITLB, 2001.

(編輯 王小唯 苗秀芝)

Biometric certificate key generation algorithm

WANG Jinhai, WEI Ning, CUI Jun, LI Xueyan, LI Xiuyan

(School of Electronic and Information Engineering, Tianjin Polytechnic University, Tianjin 300387, China)

The RSA public and private keys of biometric certificate can be generated from biometric key which can be seen as random numbers.However, the size of biometric key is shorter than the RSA public and private keys. To overcome this limitation, a biometric certificate key generation algorithm is proposed. In this method, the biometric primes is generated by the combination of symmetric key encryption algorithm and prime generation algorithm, in addition, the hashing algorithm is used to ensure the feasibility of the biometric primes. The generated biometric primes are safe and usable so that they can be applied to generate the RSA public and private keys of biometric certificate. Experimental results using VC6.0 and MIRACL show that the proposed method not only is feasible, but also has practical application value.

biometric encryption; biometric certificate; biometric key; RSA; big primes

10.11918/j.issn.0367-6234.2016.11.014

2015-06-29

天津市高等學校科技發展基金計劃項目(20140805)

王金海(1966—),男,博士,教授

崔 軍,cuijunlq@126.com

TP309.2

A

0367-6234(2016)11-0090-06