基于大數(shù)分解的一次性身份識(shí)別協(xié)議

李 濱

(成都師范學(xué)院 數(shù)學(xué)系 四川 成都 611130)

?

基于大數(shù)分解的一次性身份識(shí)別協(xié)議

李 濱

(成都師范學(xué)院 數(shù)學(xué)系 四川 成都 611130)

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

大數(shù)分解； 身份識(shí)別； 不定方程； 詢問與應(yīng)答； 協(xié)議

0 引言

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

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

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

1 預(yù)備知識(shí)

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

a1x1+ a2x2+…+ anxn=M,

(1)

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

的解相同.

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

可以驗(yàn)證

(2)

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

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

a1x1+a2x2+…+anxn≡1 mod N

(3)

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

由引理1可知不定方程

使之滿足0≤xi

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

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

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

2 身份識(shí)別協(xié)議

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

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

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

第1步： 用戶P隨機(jī)地選擇一個(gè)秘密整數(shù)w，使得0N,計(jì)算a=w2mod N，并將a發(fā)送給驗(yàn)證者V.

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

第3步： 用戶P計(jì)算bi=wvieimod N, 1≤i≤s，并將bi發(fā)送給驗(yàn)證者V.

第4步： 驗(yàn)證者V計(jì)算

驗(yàn)證：若c=a，則驗(yàn)證者V接受用戶P的身份證明.下面通過一個(gè)例子來演示一下該身份識(shí)別協(xié)議的實(shí)現(xiàn)過程.

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

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

構(gòu)造同余方程

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

由定理1結(jié)合(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)作為自己的公開身份證，并隨機(jī)地選擇秘密數(shù)w=1 145，計(jì)算

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

將a=1 182發(fā)送給驗(yàn)證者V.驗(yàn)證者隨機(jī)選取5個(gè)整數(shù)組成的序列

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

發(fā)送給用戶P.

用戶P計(jì)算

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

(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可以看出該協(xié)議易于實(shí)現(xiàn)，需要說明的是，在實(shí)際的協(xié)議應(yīng)用中，出于安全考慮，大素?cái)?shù)p和q都應(yīng)在100位數(shù)以上，然而此例僅僅展示該協(xié)議的實(shí)現(xiàn)過程，為了便于計(jì)算，把相關(guān)的數(shù)據(jù)都取得較小.

3 協(xié)議的性能分析

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

證明 1)完備性.

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

2)正確性.

可以看出，在該協(xié)議中，當(dāng)?shù)?步用戶P計(jì)算bi所采用的ei值與第4步驗(yàn)證者V所采用的ei值相等時(shí)，驗(yàn)證結(jié)果總是能使c=a成立.反之，當(dāng)?shù)?步用戶P計(jì)算bi所采用的ei值與第4步驗(yàn)證者V計(jì)算c所采用的ei值不相等時(shí)，驗(yàn)證結(jié)果就不能使c=a成立.

3)安全性.

4)零知識(shí)性.

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

4 結(jié)束語

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

本協(xié)議是一個(gè)一次性身份識(shí)別協(xié)議，通過一輪“詢問與應(yīng)答”就能達(dá)到其他身份識(shí)別協(xié)議多輪“詢問與應(yīng)答”的效果，既符合現(xiàn)實(shí)中身份識(shí)別的實(shí)際要求，又節(jié)約了系統(tǒng)的開銷，并且提高了辦事效率，同時(shí)還能避免攻擊者對(duì)該協(xié)議的重發(fā)攻擊和交錯(cuò)攻擊.

[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]鄧冰娜，王煜，劉宇. 一種應(yīng)用于博客的垃圾評(píng)論識(shí)別方法[J]. 鄭州大學(xué)學(xué)報(bào)：理學(xué)版，2011, 43(1):65-69.

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

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

[14]王小云，王明強(qiáng)，孟憲萌. 公鑰密碼學(xué)的數(shù)學(xué)基礎(chǔ)[M]. 北京：科學(xué)出版社，2013：130-135.

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

(責(zé)任編輯：孔 薇)

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

四川省教育廳科研基金資助重點(diǎn)項(xiàng)目，編號(hào)12ZB276.

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

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

TP391

A

1671-6841(2015)03-0049-06

10.3969/j.issn.1671-6841.2015.03.009