[。非對稱加密技術也被稱為公鑰密碼技術。與對稱加密不同，非對稱加密技術在加解密過程中使用的密鑰并不是相同的，這兩個密鑰分別為公鑰和私鑰，通常來講公鑰是根據私鑰進行生成的，不能通過公鑰來反推出私鑰。如果用公鑰對消息加密，只有用該公鑰對應的私鑰才能解密出原消息；同樣的，如果使用私有密鑰對一個消息進行加密，也只能通過該對密鑰的公開密鑰進行解密。非對稱加密的流程如圖2.2所示，故公鑰可作為公開信息進行管理維護，用戶只需將私鑰進行保密儲存，防止他人竊取即可。相對于對稱加密，其優點是公私鑰分開，可在不安全的信道中進行會話密鑰的協商，缺點就是在生成公私鑰對的速度較慢，加解密速度過慢。圖2.2非對稱加密模型3基于二次剩余密碼方案介紹3.1基于Paillier的改進數字簽名方案介紹文獻[16]根據文獻[7]所提出的基于函數F的加解密的思路，對Paillier的單向陷門置換進行了改進，通過將其陷門置換應用得到了一個改進以后的Paillier的數字簽名方案。該方案提高了Paillier在簽名產生和驗證的效率，對這兩方面都有所改進。該方案主要分為三個部分，分別為密鑰生成、簽名生成以及簽名驗證。下面為該方案的詳細介紹：密鑰生成部分：隨機選取兩個大素數x和y，且存在一個數n，使得n=xy，Carmichael函數（n）=lcm（x-1，y-1）（其中lcm（a，b）表示a和b的最小公倍數），而且b=modn。為了后續方便表示，以后都以代替（n）。此處g選取的值為1+n，除此之外，定義L函數為L（q）=。并選取一個Hash函數h，該函數為：。由此可知，（x，y）作為簽名者的私鑰，n作為簽名者的公鑰。簽名生成部分：先給定一個消息m，將m通過hash函數進行摘要計算生成h（m），然后通過生成的私鑰（x，y）或來生成對應的簽名（s1，s2），具體流程如下：s1生成過程：通過將計算出的h（m）經由L函數計算并與b相乘進行模n的結果即是s1：s1=bL（h（m））modns2生成過程：將計算出的h（m）以及s1通過除法運算再進行乘方運算進行模n的結果即是s2：s2=modn。簽名驗證部分：當簽名接收者接收到消息m和數字簽名（s1，s2）以后，便可通過驗證下面的等式來看是否接受簽名。若等式成立，驗簽成功，那么接受簽名，否則驗簽失敗，拒絕簽名。等式如下：h（m）=（1+s1n）s2bmodn3.2基于二次剩余的簽名方案介紹在不斷對Paillier的體制以及它的變體進行深入的學習和研究以后，在Paillier簽名方案改進的基礎之上，通過引入二次剩余定理相關問題對該方案的安全性進行改進，即在Blum-Williams函數模型下，構造出一個新的數字簽名方案。改進后的方案完善了已有的Paillier簽名方案的不足之處，除此之外，還解決了簽名方案中效率和安全性之間的問題，改進后的方案主要也分為三個部分，分別為密鑰生成、簽名生成和簽名驗證三個方面，具體方案如下所示：第一部分是密鑰生成部分，即選取兩個大素數x和y，其中x和y需滿足x3mod8，y7mod8，x和y的大小需接近，存在一個=lcm（x-1，y-1），且n=xy，=modn，L函數的定義為：L（q）=，函數h為md5，即通過md5對消息進行摘要計算。那么改進后簽名方案的私鑰為（x，y），公鑰為n。第二部分為密鑰生成部分，該部分主要分為6個步驟，首先給定一個消息m，簽名者可以按照下面的步驟來對消息進行簽名。步驟1：將消息m經由md5進行摘要計算得到對應的消息摘要h（m），接下來計算s的值：s=L（h（m））modn步驟2：首先應該驗證步驟1中所得到的s能否滿足s與n互素，即（s，n）=1，如果不滿足互素條件，那么可以通過引入隨機數以用于修改s的值（s加減隨機數），從而讓s、n互素。實際上，由文獻[18]可知，當n很大的時候，s與n不互素的概率可以忽略不計，當s與n互素之后，可以計算m，計算m的公式如下：0（）=1，即s的勒讓德符號為1。m=1（）=-1，即s的勒讓德符號為-1。步驟3：通過Jacobi相關的運算結果可以知道，（2s）modnJ，此時，m的計算公式如下：0（2smodn）qm=-1（2smodn）步驟4：計算s的值，其中d的值為，計算公式如下：s=（2s）modn步驟5：計算s，公式如下：s=modn步驟6：將消息m生成的對應簽名（m，m，s，s）用公鑰進行加密，將加密后的簽名和消息m以及公鑰n私鑰（x，y）一起發送給接收者。第三部分為簽名驗證部分，接收者接收到加密的簽名、消息m以及公鑰n私鑰（x，y）后，首先利用私鑰對簽名進行解密，然后根據解密后的簽名去驗證下列等式是否成立，如果等式成立，那么就接收簽名，等式不成立，就拒絕簽名，等式如下：h（m）=[1+]mod3.3基于二次剩余簽名方案特點簽名方案設計基于二次剩余定理及相關數論知識。在Paillier簽名方案基礎上引進了Blum-Williams函數，根據其是單向陷門置換從而構造出一個新的簽名方案，該方案在安全性和效率方面都有所提升。在安全性方面是基于大整數分解困難的前提下，是能夠抵抗各種已知的偽造攻擊的。即使獲得簽名，但根據解模合數n平方根困難性很難把求出來；即使能夠將偽造出來，但是想要等式成立還得計算出對應的m，由于hash函數的不可逆性，所以在計算上是不能得到m；除此之外，在生成簽名后還會對簽名進行加密，接收者收到的是加密后的簽名，需對簽名進行解密才可進行驗證。因此，從多個方面都可以表明方案安全性較高。本文簽名方案在效率方面也有所提升。在運算代價方面，與其他方案相比，減少了L函數和模冪的計算，增加了模乘運算，減少了計算量，具有明顯的計算優勢。在通信代價方面，本文方案只需要傳輸公開參數n，雖然簽名長度多了a、b兩個因子，但在n比較大的時候可以忽略不計，即簽名長度未發生變化。從這兩方面可以看出本文方案有較高的效率。4方案分析4.1正確性分析根據簽名的全過程我們可以推導出如下式子：h（m）=[1+]mod=[1+]mod且其中存在：（2s）modnJ，且n=xy，x3mod8，y7mod8，那么xy3mod4，因此可以分為以下兩種情況：當（2smodn）q時，此時m=0，由2.1.4定理3可得：（2s）=（-1）2smodn當（2smodn）時，此時m=1，由2.1.4定理3可得：是啥（2s）=n-2s=（-1）2smodn所以，上述等式可變化為：[1+]mod=[1+（-1）2s2(-1）n]mod=（1+sn）mod現在將s=modn代入，即可得到下列等式：h（m）=[1+]mod=（1+sn）mod綜上所述：如果存在有（m，m，s，s）能夠對消息m進行正確簽名，那么就一定存在一個值使得等式：[1+]mod=h（m）成立，所以我們的改進方案是正確的。4.2安全性分析因為在文獻[16]中所設計的簽名方案中，它的安全性是以RSA[n，n]的難解性為基礎的。在本文所設計的方案中，通過將二次剩余定理引入到原方案中，從而讓s的計算所依賴于大整數的分解難題，以此來完善文獻[16]中簽名方案的安全方面的不足。由于本文的簽名方案是將改進后的Paillier簽名方案和Rabin簽名方案進行融合后而形成的，所以本文的方案在原有方案的安全性上有很大的完善和提升，即本文簽名方案具有更高的安全性。又根據文獻[2]中的定理，即RSA[n，n]的問題可以歸結于Fact[n]上面。那么求解RSA[n，n]的難度是不會超過大整數的素因子分解問題的，又因為Rabin簽名方案已經證明了其安全性等價于大整數分解問題的困難性。所以，總的來說，本文所提出的數字簽名方案是以大整數分解難題為基礎來分析其安全性的。引理如果大整數分解問題是困難的，那么本文所提出的數字簽名方案是能夠抵抗適應性的選擇消息攻擊。證明過程：假設攻擊者想進行攻擊操作，那么他會向簽名者請求對消息m,m簽名，那么他會得到相對應的簽名q，q，即q=（r，s，a，b），q=（r，s，a，b），那么我們可以進行驗證從而得到如下等式：h（m）=[1+r2n]smodnh（m）=[1+r2n]smodn此時攻擊者可以通過上述等式從而得到下面的式子，如下所示：h（m）==這個時候，如果存在一個消息m’以及簽名r和s，而這些信息恰好被攻擊者所獲得，從而使得等式h（m’）=h（m）=[1+r2n]smodn成立，那么顯而易見，本文的數字簽名方案是不能夠抵抗適應性選擇消息攻擊的。而通過分析可以知道的是，要滿足上述等式，需選取t=modn，但是現在所選取的rZ則需要滿足下列等式：[1+r2n]=。又因為當n分解未知的情況下，對模合數n的平方根求解的困難性是和整數分解是一樣的。所以，當大整數分解問題是困難的時候，利用上面的式子去求解r也是很困難的，那么則證明了本文的數字簽名方案是安全的。就算攻擊者能夠得到或者偽造出相應的r，但是要讓等式h（m’）=h（m）=[1+r2n]smodn成立，還要找到對應的m’，這就要對hash函數進行求逆運算，很顯然在計算上這是不可行的。所以，只有成功分解出n以后才可以得到私鑰（x，y）。所以，根據上述描述，大整數分解困難問題是本文數字簽名方案安全性的基礎保障。同時以大整數分解為基礎，本文簽名方案還能抵抗各種已知的偽造攻擊，安全性有了很大的提升。4.3效率分析從方案的整體設計思路上看，如表4.1所示。本文方案與文獻［2］和文獻［16］都是基于公鑰加密構造的簽名，而文獻［19］中簽名方案則是構造了一種“等式關系”進行簽名。本文方案與文獻［2］和文獻［16］中簽名方案的安全性都基于數論中的困難問題，而文獻［19］中方案的安全性基于ＲSa-Paillier陷門函數為單向陷門置換。表4.1簽名方案設計思路比較方案陷門函數安全性基于公鑰加密的簽名文獻[2]RSA[n，n]可以文獻[16]RSA[n，n]可以文獻[19]E是單向陷門置換不可以本文方案Fact[n]可以運算代價的比較在運算代價上，本文從以下四個方面比較了三種簽名方案的效率，如表4.2所示。1－L表示1個L函數的運算。1－d(n)表示一個模n的除法運算。1－m(n)表示1個模n的乘法運算。1－E(n)表示1個模n的冪運算。在Paillier簽名產生過程中，L函數的計算量相對較大。由表2可知，文獻［16］中的方案之所以提高了Paillier簽名方案的效率，是因為其在L函數運算和模冪運算上的計算量都有所減少。而本文方案在不增加L函數運算的基礎上，出于安全性考慮，在文獻［16］方案的基礎上只增加了一次模冪運算，與安全的Paillier簽名方案相比，具有明顯的計算優勢。相應的，與文獻［16］中簽名方案相比，在簽名驗證過程中，本文方案也避免了計算量相對較大的模冪運算，只增加了一次模乘運算，而且在計算上明顯優于Paillier簽名方案。而文獻［19］中的方案由于利用的單向函數和構造方法的特殊性，簽名產生階段不需要L函數的運算，但是簽名驗證的運算代價與本文方案相同。表4.2簽名方案運算的代價簽名方案簽名產生簽名驗證文獻[2]2-L，1-d（n），1-m（n），2-E（n）2-E（）1-m（）文獻[16]1-L，1-d（n），1-m（n），1-E（n）1-E（）1-m（）文獻[19]1-E（）3-m（）1-E（）3-m（）本文方案1-L，1-d（n），1-m（n），2-E（n）1-E（）3-m（）通信的代價比較由于簽名者和簽名接收者之間傳輸的主要是公開參數和產生的簽名，因此通信代價考慮的是傳輸的公開參數的數據量和簽名的長度。在表4.3中，||表示Zn中元素的長度，||表示中元素的長度，||表示中的元素。如表3所示，在公開參數傳輸的數據量上，本文方案與文獻［16］中方案相同，只需要傳輸公開參數n，不需要傳輸g，與文獻［2］的方案相比，傳輸參數的數據量降低了，減少了帶寬。另外，本文的方案產生的簽名的長度僅僅比文獻［16］中方案增加了a和b兩個比特因子，而且由于簽名驗證方可以在驗證過程中計算出b，所以實際上只增加了一個比特因子，在n比較大時，可以忽略不計，因此兩方之間需要傳輸的簽名的長度基本沒有變化。由此可知，在通信代價上，本文方案與文獻［16］的方案基本相同，相較于Paillier簽名方案［2］都有所減少。而文獻［19］中簽名由三個部分組成，與本文方案相比，簽名長度較長，需要傳輸的數據量也較多。表4.3簽名方案通信代價的比較簽名方案公開參數簽名長度文獻[2]n，g+文獻[16]n+文獻[19]n，e，y3本文方案n+++5方案實現5.1實現環境本方案采用了Java語言進行進行實現，具體實現環境如表5.1所示：表5.1實現環境名稱類型版本操作系統Windows101903編輯器IDEA18.3編譯器JDK1.8.05.2主要流程本方案在改進的Paillier簽名方案的基礎上，并結合Rabin密碼方案，通過二次剩余定理，從而形成新的數字簽名方案，該方案主要分為三個部分：分別為生成密鑰、生成簽名和驗證簽名，具體流程如圖5.2所示：圖5.2簽名方案主要流程5.3重點函數詳解（1）密鑰生成部分①判斷是否為素數：publicstaticBigIntegerisprime(BigIntegernumber){BigIntegeri=newBigInteger("2");while(pareTo(number)==-1){if((number.remainder(i).compareTo(newBigInteger("0"))==0))break;elsei=i.add(newBigInteger("1"));}if(pareTo(number)==0)returnnewBigInteger("1");elsereturnnewBigInteger("0");}//②求逆運算：通過擴展的歐幾里得算法，進行遞歸，求得該數的逆，在求的結果時，也會用到擴展的歐幾里得算法求n的逆。publicstaticvoidexgcd(BigIntegera,BigIntegerb){BigIntegert;if(pareTo(newBigInteger("0"))==0){x=newBigInteger("1");y=newBigInteger("0");return;}exgcd(b,a.remainder(b));//遞歸運算t=x;x=y;y=t.subtract((a.divide(b).multiply(y)));}簽名生成部分①求s時要經過L函數L（q）=，在L函數計算時由于位數過大可能會導致結果輸出異常，于是在計算時，會加入一個循環，首先計算，再進行模計算；計算完畢后再與q相乘，模計算，這樣得到了，以此類推，一直計算到，循環結束，在后面中和中計算也是用相同的方法。這樣計算的好處則是將結果始終控制在一個較小的范圍，不至于數據太大從而出現異常，但存在的缺點是如果q和很大，則計算時間會比較長，以下是該過程的部分代碼：BigIntegertemp,S;BigIntegercount=newBigInteger("2");BigIntegermod=n.multiply(n);temp=(miu.multiply(miu)).mod(mod);//計算；while(pareTo(lamuda)<0){//進入循環，計算；temp=temp.multiply(miu);temp=temp.mod(mod);count=count.add(newBigInteger("1"));}②在的計算中有的計算，在計算時，采用的方法是遍歷，即求出從到模n的結果，把它們的結果組成一個集合，如果計算的結果是屬于該集合，那么值為零。在1到（n-1）的所有數里面，出去集合里面的數，所剩下的數組成的集合則為，若計算的結果是屬于集合中，那么的取值為1。BigIntegertemp=newBigInteger("2").pow(-a);BigIntegernumber=(temp.multiply(s)).mod(n);//計算得結果；BigIntegertemp1=null;//初始化；BigIntegeri=newBigInteger("1");do{temp1=(i.multiply(i)).mod(n);if(pareTo(temp1)==0){System.out.println("i="+i);return0;}i=i.add(newBigInteger("1"));}while(pareTo(n)<0);//計算、的結果，并與進行比較，得到的取值；return1;}5.4實現截圖①選取兩個素數x和y，x的取值為，y的取值為，他們分別滿足x3mod8，y7mod8，由此可以計算出n的大小，為，以及的大小。此時的私鑰為（x，y），公鑰為n，具體如圖5.3所示：圖5.3密鑰生成結果②此時輸入消息m為message，經由hash函數摘要以及L函數計算可以得到s的值，為，通過s可以計算出的值為，以此類推，環環相扣，計算出、、、的值，它們分別為，此時將消息m以及對應的簽名（，，，，）發給接收者，具體如圖5.4所示：圖5.4簽名生成過程③接收者收到消息m以及簽名以后則開始進行驗證，驗證等式是否成立，若成立則接收簽名，否則拒絕簽名。由于接收的數據通過公式計算出的結果和消息摘要的結果是一直的，那么是成功的，所以接受簽名，具體如圖5.55.6所示：圖5.5消息摘要結果圖5.6簽名驗證結果6結語盡管在學習過程中學了有關于二次剩余的相關內容，但也僅限于基礎知識和很少的應用，而基于二次剩余設計實現密碼方案還從來沒有接觸過，是非常陌生的，于是為了更好的完成畢業設計，我主要分為3步計劃進行。第一步則是進行理論知識的學習，這是方案設計的基礎。前期我主要是進行二次剩余理論的學習，學習相關的數論知識，了解它們相關的應用，尤其是在密碼學方面，同時我也了解到二次剩余理論在公鑰密碼體制中的重要性，與我們生活息息相關；由于是設計密碼方案，所以密碼學知識必不可少，于是我還重新溫習了密碼學的相關知識，了解了簽名相關流程；最終方案需要實現，所以編程學習必不可少，于是我便溫習java、c語言等相關編程語言知識，為后面方案實現打下基礎。第二步則是要進行方案的設計，由于之前一直未接觸過相關內容，所以不知道方案應該是什么樣的，于是便先去了解密碼方案的相關內容，密碼方案就是要實現加解密或者簽名等功能，根據功能不同也可以分為不同的方案。在了解到密碼方案相關知識，我又繼續查閱資料，查找現在已有的基于二次剩余的密碼方案，去學習現有的方案，為自己設計方案打下基礎。在學習完他們的方案以后，以及和指導老師協商，我根據改進的Paillier簽名方案以及Rabin密碼方案相結合，在此基礎上進行改進，在簽名過程中加入了另外的簽名元素，克服了Paillier方案效率和安全性不能兼顧的問題，并對方案進行了安全性分析和效率分析。第三步則是對密碼方案進行實現，我選擇用java進行密碼方案的實現，實現了密碼方案的功能，做到了能夠驗證簽名和拒絕簽名，只是礙于能力有限，所實現的數據位數還不夠大，我會在指導老師幫助下盡可能解決這個問題。參考文獻diffieW,Hellmanm.newdirectionsincryptography［J］.IEEETransactionsonInformationTheory，1976，22(6):644-654．Paillierp．public-keycryptosystemsbasedoncompositedegreeresiduosityclasses［C］//InternationalConferenceonTheoryandapplicationofCryptographicTechniques，Springer-Verlag，1999:223-238.damgrdI，Jurikm．ageneralisation，asimplicationandsomeapplicationsofPaillier＇sprobabilisticpublic-keysystem［C］//pKC’01proceedingsofthe4thInternationalWorkshoponpracticeandTheoryinpublicKeyCryptography:publicKeyCryptography．Springer-VerlagLondon，UK，2001:119-136.Catalanod，GennaroＲ，Howgrave-Grahamn，etal．Paillier’scryptosystemrevisited［C］//aCmConferenceonComputer＆CommunicationsSecurity，2002:206-214.Galindod，martynS，morillop，etal．apracticalpublicKeyCryptosystemfromPaillierandRabinSchemes［C］//InternationalWorkshoponTheoryandpracticeinpublicKeyCryptography:publicKeyCryptography．Springer-Verlag，1993:279-291.BressonE，Catalanod，pointchevald．asimplepublic-keycryptosystemwithadoubletrapdoordecryptionmechanismanditsapplications［J］．LecturenotesinComputerScience，2003，2894:37-54．姜正濤，劉建偉，秦波，等．加密|n|+kbit明文的高效公鑰概率加密體制［J］．北京航空航天大學學報，2008，34(1):43-46．姜正濤，劉建偉，王育民．Paillier-pointcheval公鑰概率加密體制的改進［J］．計算機工程，2008，34(3):38-39.manHa，WeiVK．Id-basedCryptographyfromCompositedegreeＲesiduosity［J］．IacrCryptologyEprintarchive，2004，2004.ZhouSujing，Lindongdai．aninterestingmemberId-basedgroupsignature［J］．Recentdevelopmentsinalgebra＆Relatedareas，2007，2007:279-302.WangZhiwei．anewconstructionoftheserver-aidedverificationsignaturescheme［J］.mathematicalandComputermodelling，2012，55(1-2):97-101.ChengZhen，ChiKaikai，Tianxianzhong，etal．Securenetworkcodingbasedonhomomorpuicsignatureagainstpollutionattacks［C］//2012IEEE2ndInternationalConferenceonCloudComputingandIntelligenceSystems，Hangzhou，2012:1092-1096.岳澤輪，韓益亮，楊曉元．基于Paillier公鑰密碼體制的簽密方案［J］．小型微型計算機系統，2013，34(10):2310-2314.Tingpy，HseuCH．asecurethresholdPaillierproxysignaturescheme［J］．JournalofZhejiangUniversityScienceC，2010，11(3):206-213.CaoZhengjun，LiuLihua．ThePaillier’s