基于大數分解的一次性身份識別協議

李 濱

(成都師范學院 數學系 四川 成都 611130)

?

基于大數分解的一次性身份識別協議

李 濱

(成都師范學院 數學系 四川 成都 611130)

針對現有的身份識別協議效率不高的問題，利用大數分解的困難性和多元一次同余不定方程解的結構形式，構造了隨機“詢問與應答”的一個四步交互式身份識別協議.該協議符合身份證明系統的完備性、正確性、安全性和零知識性的要求，既沒有被附加任何復雜性假設和用戶的計算能力假設，又能做到對用戶身份的一次性識別.

大數分解； 身份識別； 不定方程； 詢問與應答； 協議

0 引言

身份識別是指用戶向認證系統出示自己身份并證明其身份真實性或可信性的過程，通常是獲得系統服務所必需的第一道關卡.在很多情況下，都需要認證系統對用戶的身份進行證明.在認證系統中，用戶的身份可以用三種形式來唯一識別：一是所知道的，如口令，即個人身份識別號；二是所擁有的，如智能卡、身份證等；三是所具有的生物特征，如指紋、聲音等.利用密碼學的方法進行身份識別，大多采用第一種方式，即用戶通過出示自己掌握的某個秘密信息來證實身份.這種方式的缺點是敵手或不誠實的驗證方可使用用戶的身份信息來冒充用戶從事非法活動.因此要求在證實身份的過程中，用戶的秘密信息不能泄露.解決這個問題的辦法就是利用零知識證明技術.

零知識證明[1]也是一種協議，這種協議的一方稱為證明者P，它試圖使被稱為驗證者V的另一方相信某個論斷是正確的，但不向驗證者提供任何有用的信息.零知識證明是交互式的，也就是證明者P和驗證者V之間必須進行雙向對話，才能實現零知識性，因而又稱之為交互證明.交互證明是由P產生證明、V驗證證明的有效性來實現，因此參與交互證明的雙方之間通過某種信道的通信是必需的.利用交互證明方法做用戶身份識別時，用戶即為證明者，用戶經過交互方式與驗證者對話，設法讓驗證者相信他知曉某一秘密，而無需將此秘密傳輸給驗證者，如此一來，交互式用戶身份識別方法便無懼于被敵手竊聽的威脅了.針對一般交互式用戶身份識別協議，都必須滿足以下要求：① 完備性：如果用戶與驗證者雙方都是誠實的協議執行者，用戶知道某一秘密，那么有非常大的概率，驗證者將接受用戶的身份.② 正確性：如果用戶能以一定的概率使驗證者相信他的證明，那么用戶知道相應的秘密.③ 安全性：如果用戶根本不知道與用戶名字相關的密鑰，且驗證者是誠實的，那么有非常大的概率，驗證者將拒絕接受用戶的身份.④ 零知識性：如果用戶是誠實的，那么不論協議進行多少次以及不論任何人(包括驗證者)都無法從協議中推出用戶的密鑰，并且無法冒充用戶的身份.

Fiat等[2]在1987年基于零知識證明的思想提出了一種鑒別和簽名方案，兩年后改進成為身份的零知識證明[3]，這就是最著名的FFS身份識別協議.Dwork等[4]和Goldwasser等[5]對這個身份識別協議進行了進一步的研究，提出了該協議存在可證明結論的局限性.Schnorr[6]在1991年提出了一種計算量、通信量均較少，且特別適用于智能卡上的用戶身份識別協議，其安全性建立在計算離散對數問題的困難性之上，它融合了多種方案的思想，在許多國家都申請了專利.近年來人們在與身份認證協議有關的研究方面取得了較為豐碩的成果[7-12].以上提到的身份識別協議的交互證明過程都要由若干輪組成，在每一輪，驗證者都向證明者發出一個詢問，證明者向驗證者做出一個應答，執行完所有輪后，驗證者根據證明者是否在每一輪對自己發出的詢問都能正確應答，來判定證明者的身份是否有效.多輪的身份識別協議顯然降低了驗證的效率.作者基于大數分解的一次性身份識別協議，只需一輪“詢問與應答”就能達到以上協議多輪的效果，因而更為實用.

1 預備知識

考慮如下n(n≥2)元一次不定方程：

a1x1+ a2x2+…+ anxn=M,

(1)

其中，M,a1,a2,…,an是不為零的整數系數.設gcd(a1,a2,…,an)=dn，可得引理1.

的解相同.

如果設gcd(a1,a2,…,ai)=di(2≤i≤n)，那么存在整數ξ1,ξ2,…,ξn和η1,η2,…,ηn-1，滿足：

可以驗證

(2)

為不定方程(1)的一個特解.

定理1 設ai(1≤i≤n)，N為正整數且N≠1，若gcd(dn,N)=1,則同余方程

a1x1+a2x2+…+anxn≡1 mod N

(3)

存在整數解xi(1≤i≤n)滿足0≤xi≤N.

由引理1可知不定方程

使之滿足0≤xi

設p, q是兩個不同的大素數，N=pq, a是w的模N二次剩余，f(w,b)是w和b的整函數，即滿足：

a=w2mod N, f(w,b)=0 mod N.

可以看出，要想計算b就必須先計算出w，而要想計算w又必須求解二次同余方程w2mod N=a.如果把N和a公開，將p, q, w, b保密.那么求解二次同余方程w2mod N=a與分解N的素因子兩者的困難性是等價的.也就是僅知道N和a，不知道w而計算b同不知道p和q而計算w同樣困難.因此，證明者P以b作為自己的秘密數，通過交互證明協議，如果證明者P向驗證者V證明自己的確知道b，那他便向V證明了自己的身份的確是P.

2 身份識別協議

本協議的安全性依賴于計算模N平方根的困難性，這等價于大數分解的困難性.首先，假定存在一個可信任的密鑰認證中心KAC，該中心的唯一作用就是秘密地選取兩個模4與3同余的大數p和q，再將其乘積N公布為所有用戶的模.用戶P的身份信息產生過程如下：

3)公開ui(1≤i≤s)，將PI(P)=(u1,u2,…,us)作為用戶P的公開身份證.

這樣，驗證者V知道N和用戶P的公開身份證PI (P).用戶P想要驗證者V相信他知道I(P)而不泄露它，為了達到這一點，P和V執行的“詢問與應答”步驟如下：

第1步： 用戶P隨機地選擇一個秘密整數w，使得0N,計算a=w2mod N，并將a發送給驗證者V.

第2步： 驗證者V任選s個整數ei，滿足1≤ei≤2t，1≤i≤s，這里t 為安全參數(一般取t =10),并將ei發送給用戶P.

第3步： 用戶P計算bi=wvieimod N, 1≤i≤s，并將bi發送給驗證者V.

第4步： 驗證者V計算

驗證：若c=a，則驗證者V接受用戶P的身份證明.下面通過一個例子來演示一下該身份識別協議的實現過程.

例1 可信中心KAC選取p=31，q=47，則N=pq=1 457，公開N作為模.

用戶P選取秘密身份信息I(P)=(v1,v2,v3,v4,v5)=(123,67,59,117,85)，計算

構造同余方程

559u1+118u2+567u3+576u4+1 397u5=1 mod 1 457.

由定理1結合(2)式可得此方程在Zn上的解為

u1=1 105，u2=57，u3=1 350，u4=61，u5=1.

用戶P將PI(P)=(u1,u2,u3,u4,u5)=(1 105,57,1 350,61,1)作為自己的公開身份證，并隨機地選擇秘密數w=1 145，計算

a=w2mod N=1 1452mod 1 457=1 182.

將a=1 182發送給驗證者V.驗證者隨機選取5個整數組成的序列

(e1,e2,e3,e4,e5)=(23,140,19,51,108),

發送給用戶P.

用戶P計算

將序列(b1,b2,b3,b4,b5)=(294,553,1 385,342,302)傳送給驗證者V.驗證者V進行如下計算：

(2942×1 105×1 132+5532×57×283+1 3852×1 350×448+

3422×61×661+3022×1×1 275) mod 1 457=1 182.

由于c=a，因此V接收P的身份證明.

從例1可以看出該協議易于實現，需要說明的是，在實際的協議應用中，出于安全考慮，大素數p和q都應在100位數以上，然而此例僅僅展示該協議的實現過程，為了便于計算，把相關的數據都取得較小.

3 協議的性能分析

定理2 該協議滿足交互式身份識別協議的完備性、正確性、安全性和零知識性的要求.

證明 1)完備性.

如果用戶P和驗證者V遵守該協議且P知道I(P)，則在第3步中應答bi=wvieimod N,bi一定包含w的模N二次剩余a；在該協議的第4步，V通過驗證P的應答接收P的身份證明，所以該協議滿足完備性.

2)正確性.

可以看出，在該協議中，當第3步用戶P計算bi所采用的ei值與第4步驗證者V所采用的ei值相等時，驗證結果總是能使c=a成立.反之，當第3步用戶P計算bi所采用的ei值與第4步驗證者V計算c所采用的ei值不相等時，驗證結果就不能使c=a成立.

3)安全性.

4)零知識性.

用戶P沒有提交他的秘密身份證，也沒有向V證明他的公開身份證的合法性，而是向V顯示擁有關于他的秘密身份證的知識來證明其公開身份證的合法性.在協議的第1步P發送給V的信息僅為P知道a的平方根w這一事實，并沒有泄露a的平方根w，V要想通過a獲取w，就必須對N進行大數分解，這在計算上是不可能的.在協議的第2步V的詢問ei是從1～2t的整數中選取的，V沒有機會產生其他信息.在協議的第3步的bi中P的秘密身份證I(P)是與P所選的一個隨機數w混合計算，因而V無法從bi中獲得I(P).綜上所述，該協議滿足零知識性.

4 結束語

本協議中秘密身份證的安全保密依賴于大數N因子分解的困難性，已知PI(P)想要求I(P)和求a的平方根w，都涉及到大數分解問題.關于大數分解問題，1994年4月底，由貝爾公司Lenstra領導的小組，大約600多人利用1 600臺計算機聯網，計算8個月后終于分解了長度為129位的大整數.最新記錄是1999年，一個由292臺計算機組成的分布式計算機網絡，花了5.2個月時間完成了對一個155位的十進制大整數的素因子分解.數學家Simmons等[13]估計分解x+10位數的困難度大約是分解x位數的10倍.目前因子分解速度最快的方法，其時間復雜性函數[14]為exp(sqrt(ln(n)lnln(n))).Rivest等[15]建議取p和q為100位十進制數(≈2332)，這樣N為200位十進制數，要分解200位的十進制數，每秒運算107次的超高速電子計算機也要108年.

本協議是一個一次性身份識別協議，通過一輪“詢問與應答”就能達到其他身份識別協議多輪“詢問與應答”的效果，既符合現實中身份識別的實際要求，又節約了系統的開銷，并且提高了辦事效率，同時還能避免攻擊者對該協議的重發攻擊和交錯攻擊.

[1]GoldwasserS,MicaliS,YaoAC.Strongsignatureschemes[C]//Proceedingsof15thAnnualACMSymposiumonTheoryofComputing.NewYork, 1983:431-439.

[2]FiatA,ShamirA.Howtoproveyourself:practicalsolutionstoidentificationandsignatureproblems[C]//ProceedingsonAdvancesinCryptology.Berlin,1987:186-194.

[3]FeigeU,FiatA,ShamirA.Zero-knowledgeproofsofidentity[J] .JournalofCryptology, 1988, 1(2):77-94.

[4]DworkC,NaorM,ReingoldO.Magicfunctions[J].JournaloftheACM, 2003, 50(6):852-921.

[5]GoldwasserS,TaumanY.OnthesecurityoftheFiat-Shamirparadigm[C]//Proceedingsof44thAnnualIEEESymposiumonFoundationsofComputerScience.NewYork, 2003: 102-115.

[6]SchnorrCP.Efficientsignaturegenerationbysmartcards[J].JournalofCryptology, 1991, 4(3):161-174.

[7]BonehD,BoyenX.ShortsignaturewithoutrandomoraclesandtheSDHassumptioninbilineargroups[J].JournalofCryptology, 2008, 21(2):149-177.

[8]HaitnerI.Aparallelrepetitiontheoremforanyinteractiveargument[C]//Proceedingsof50thAnnualIEEESymposiumonFoundationofComputerScience.NewYork, 2009:241-250.

[9]DingNing,GuDawu.Precisebounded-concurrentzero-knowledgeproofsforNP[J].ScienceChina:InformationSciences, 2010, 53(9):1738-1752.

[10]ZaveruchaGM,StinsonDR.Shortone-timesignatures[J].AdvancesinMathematicsofCommunications, 2011, 5(3):473-488.

[11]鄧冰娜，王煜，劉宇. 一種應用于博客的垃圾評論識別方法[J]. 鄭州大學學報：理學版，2011, 43(1):65-69.

[12]王杰，耿麗紅，朱曉東.一種改進的HMM/RBF情感語音識別方法[J]. 鄭州大學學報：理學版，2012，44(4):68-72.

[13]SimmonsGJ,NorrisMJ.PreliminarycommentsontheM.I.T.public-keycryptosystem[J].Cryptologia, 1977, 1(4):406-414.

[14]王小云，王明強，孟憲萌. 公鑰密碼學的數學基礎[M]. 北京：科學出版社，2013：130-135.

[15]RivestRL,ShamirA,AdlemanLM.Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems[J].CommunicationsoftheACM, 1978, 21(2):120-126.

(責任編輯：孔 薇)

One-time Identification Protocol Based on Large Numbers Factorization

LI Bin

(DepartmentofMathematics,ChengduNormalUniversity,Chengdu611130,China)

In order to deal with the inefficient problem of the existing identification protocol, a four-step interactive identification protocol was constructed by using the difficulty of large numbers factorization and the solution constitutional formula of multivariate linear coresidual indeterminate equation. Any complexity assumption and power of prover was not relied on and any random challenge-response could be accomplished in the protocol. Some conditions of the interactive identification proof systems such as completeness and correctness as well as security and zero-knowledge were possessed by the protocol. Moreover, identification of user could be finished at one time.

large number factorization; identification; indeterminate equation; challenge and response；protocol

2015-01-12

四川省教育廳科研基金資助重點項目，編號12ZB276.

李濱(1963-)，男，四川富順人，副教授，碩士，主要從事密碼學研究，E-mail:1145398209@qq.com.

李濱.基于大數分解的一次性身份識別協議[J].鄭州大學學報:理學版，2015,47(3)：49-54.

TP391

A

1671-6841(2015)03-0049-06

10.3969/j.issn.1671-6841.2015.03.009