EIGamal算法既可用于數(shù)字簽名又可用于加密，其安全性依賴于計(jì)算有限域上離散對(duì)數(shù)的難度。要產(chǎn)生一對(duì)密鑰，首先選擇一素?cái)?shù)p，兩個(gè)隨機(jī)數(shù)g和x，g和x都小于p，然后計(jì)算Y=gxmodp公開(kāi)密鑰是y，g和p，g和p可由一組用戶共享。私人密鑰是x。

　　【摘要】自組裝DNA計(jì)算在破譯密碼系統(tǒng)方面，具有傳統(tǒng)計(jì)算機(jī)無(wú)法比擬的優(yōu)勢(shì)。采用DNA分子瓦編碼信息，借助于分子瓦之間的粘性末端進(jìn)行自組裝，通過(guò)引入非確定性的指派型分子瓦，提出了用自組裝DNA計(jì)算破譯EIGamal公鑰密碼系統(tǒng)的非確定性算法。通過(guò)創(chuàng)建數(shù)以億計(jì)的參與計(jì)算的DNA分子瓦，該算法可以并行地以高概率地破譯EIGamal公鑰密碼系統(tǒng)。

　　【關(guān)鍵詞】自組裝,DNA分子瓦,EIGamal算法

　　1引言

　　密碼學(xué)算法是多種多樣的，利用DNA計(jì)算特有的高速并行性和高存儲(chǔ)性，人們開(kāi)始利用DNA計(jì)算來(lái)實(shí)現(xiàn)密碼分析和密碼加密的技術(shù)。與此同時(shí)，生物技術(shù)獲得了飛速的發(fā)展，尤其是人類基因組測(cè)序計(jì)劃完成，容易產(chǎn)生大量互異的DNA序列，這誘發(fā)了人們利用生物技術(shù)的方法對(duì)信息進(jìn)行加密的思想。DNA計(jì)算的代數(shù)運(yùn)算、基于表面的DNA計(jì)算以及自組裝DNA計(jì)算等方法已經(jīng)在理論上解決了一些圖論、網(wǎng)絡(luò)、優(yōu)化以及密碼等問(wèn)題。目前已有學(xué)者提出了基于DNA的加密和解密技術(shù)。

　　本文通過(guò)深入分析公鑰密碼系統(tǒng)地特點(diǎn)，給出基于自組裝DNA計(jì)算的EIGamal公鑰密碼系統(tǒng)破譯方案

　　2EIGamal公鑰密碼系統(tǒng)

　　對(duì)消息M加密，首先要選擇隨機(jī)數(shù)k，只要k與p-1互素。然后計(jì)算：

　　a=gkmodp

　　b=ykMmodp

　　a和b是密文對(duì)。注意密文的大小是明文的兩倍。

　　解密a和b時(shí)，計(jì)算：

　　M=b/ax（modp）

　　因?yàn)閍x=gkxmodp以及b/ax=ykM/ax=gxkM/gxk=Mmodp都成立，除了y是密鑰的一部分以及加密是和yk相乘得來(lái)。

　　EIGamal加密：

　　公開(kāi)密鑰p：素?cái)?shù)（可由一組用戶共享）

　　gy=gx（modp）

　　私人密鑰x

　　加密k：隨機(jī)選擇，與p-1互素

　　a（密文）=gkmodp

　　b（密文）=ykMmodp

　　解密M（明文）=b/ax（modp）

　　為了攻破EIGamal公鑰密碼系統(tǒng)直接的方法是計(jì)算離散對(duì)數(shù)。當(dāng)所有的因子都是小素?cái)?shù)時(shí)可以采用Pohlig-Hellman算法。此外可以仿照因子分解算法引入因子庫(kù)，先計(jì)算因子庫(kù)中素?cái)?shù)的離散對(duì)數(shù)，然后計(jì)算期望元素的離散對(duì)數(shù)，這就是目前最有效的指標(biāo)計(jì)算方法。

　　DNA自組裝計(jì)算模型是今年來(lái)引人關(guān)注的計(jì)算模型，已有基于自組裝模型的二進(jìn)制加法、乘法、減法和除法。本文利用DNA自組裝系統(tǒng)實(shí)現(xiàn)了素?cái)?shù)p的本原根g連續(xù)乘法后于p求模的過(guò)程，進(jìn)而應(yīng)用于破譯EIGamal公鑰密碼系統(tǒng)。通過(guò)PCR和凝膠電泳技術(shù)，我們可以得到g的冪次，進(jìn)而通過(guò)減法求模。本模型擴(kuò)展了DNA自組裝計(jì)算模型的應(yīng)用，為求取離散對(duì)數(shù)提供了新思路。

　　3基于DNA自組裝模型的離散對(duì)數(shù)求取系統(tǒng)

　　瓦片自組裝模型是建立在一個(gè)方形晶體格上的分子自組裝模型，是王氏分子瓦理論的延伸，是包括了特殊生長(zhǎng)機(jī)制的分子自組裝模型。這個(gè)模型提供了全新的機(jī)制用于解決數(shù)學(xué)和優(yōu)化組合中的問(wèn)題。3.1指數(shù)函數(shù)系統(tǒng)

　　基于DNA自組裝模型的整數(shù)模乘排列瓦片系統(tǒng)，其中，S1為整數(shù)模乘排列所使用的所有分子瓦集合，這個(gè)系統(tǒng)的粘貼強(qiáng)度函數(shù)相等，g=1。令這個(gè)系統(tǒng)=2，即當(dāng)一個(gè)瓦片的鄰域粘貼強(qiáng)度之和等于或者大于2，瓦片才能穩(wěn)定地粘結(jié)到已有的集合上。

　　系統(tǒng)S1是由YuriyBrun提出的乘法系統(tǒng)中延伸而來(lái)，使用了28種不同類型的瓦片。著寫瓦片都含有兩個(gè)輸入端（一般為瓦片的東和南兩個(gè)方向），還有兩個(gè)輸出端（一般為瓦片的西和北兩個(gè)方向）。在我們的指數(shù)系統(tǒng)中包括了24種計(jì)算瓦片和4種藍(lán)色瓦片來(lái)開(kāi)始計(jì)算，如圖1所示。

　　讓S1={0，1，00，01，10，11，20，21}，g=1，=2，分子瓦片集的定義如圖2所示，種子瓦和種子結(jié)構(gòu)的設(shè)計(jì)如圖1所示。這樣，系統(tǒng)可以用于計(jì)算函數(shù)y=gx

　　顯然，如果b=Σibi2i，bi∈{0，1}，這里第i位是bi，那么ab可以被寫為ab=Σibia2i.那么可以對(duì)b的每一位分別相乘，然后再把結(jié)果相加。因?yàn)槎�進(jìn)制乘法比較簡(jiǎn)單，所以瓦片的設(shè)計(jì)也較為簡(jiǎn)單，瓦片的信息從左邊演算從右邊得到，剩下的事情就是把兩兩相乘的和相加。系統(tǒng)應(yīng)該將n個(gè)數(shù)相加，與兩位數(shù)的相加不同，可以想象每一行上新加一個(gè)新的數(shù)字，并且向最后結(jié)果處傳送。我們讓兩種不同作用的瓦片相夾產(chǎn)生出新的瓦片集將每一行的結(jié)果傳遞到最后。

　　圖1顯示的系統(tǒng)S1的的種子結(jié)構(gòu)的建立，這里我們讓g=000112。輸入g如圖中所示被編碼在最下面一行和最右邊一列上。這是有四個(gè)藍(lán)色的瓦片（如圖2所示）來(lái)處理數(shù)和完成剛開(kāi)始一行的計(jì)算。這些瓦片是必需的，因?yàn)樽钌俚妮斎胛粦?yīng)為20而且要求沒(méi)有左轉(zhuǎn)移。紅色的瓦片的輸入端含有0。這些瓦片都有左轉(zhuǎn)移，但是沒(méi)有增加總和的能力。綠色和黃色瓦片的輸入端都含有1，其中，黃色瓦片的轉(zhuǎn)移位是0而綠色瓦片的轉(zhuǎn)移位是1。每個(gè)瓦片，除了粘性末端外還有兩個(gè)信息標(biāo)示：下面的信息表示的是2ia的值而上面的信息表示的是目前為止的總和。最上面一行的上面的信息是問(wèn)題的結(jié)果。

　　在種子結(jié)構(gòu)中，如圖所示有六種瓦片{0，1，00，01，CT，Str}。注意到在計(jì)算開(kāi)始的時(shí)候，只有一個(gè)瓦片能與種子結(jié)構(gòu)結(jié)合，因?yàn)�？�?2而且此時(shí)只有一個(gè)夾角。我們使用瓦片“CT”來(lái)使乘法一直進(jìn)行下去，使用瓦片“Str”用來(lái)開(kāi)始下一個(gè)部分中的減法。如圖3中的那樣，在（x，5）行計(jì)算的結(jié)果被四種特殊的瓦片讀出。

　　圖3函數(shù)y=gx的組裝結(jié)果，在（0，5）行設(shè)計(jì)為“CT”，我們?cè)O(shè)計(jì)了讀取瓦片，讀出北側(cè)右邊的結(jié)果，就是我們的乘法結(jié)果，CT使乘法繼續(xù)重復(fù)下去；同樣地，在行（0，10）=str，同樣先使用讀取瓦片讀出乘法的結(jié)果，然后開(kāi)始求模的過(guò)程。乘法重復(fù)的次數(shù)就是我們要求的函數(shù)的解x。

　　3.2求模系統(tǒng)

　　為了求解方程y=gxmodp中的x，我們首先對(duì)gx進(jìn)行計(jì)算。由于x是未知的，所以在上一步中我們進(jìn)行盡可能多的指數(shù)計(jì)算。然后我們對(duì)指數(shù)計(jì)算的結(jié)果對(duì)p求模，其結(jié)果就是y，我們從組裝的結(jié)果中提取到正確的y值，然后找出指數(shù)計(jì)算的次數(shù)，就是我們要求的離散對(duì)數(shù)的值x.在求模系統(tǒng)中，我們利用的是張的減法運(yùn)算，對(duì)指數(shù)運(yùn)算的結(jié)果進(jìn)行連續(xù)的減法運(yùn)算，能得到y(tǒng)的組裝就是我們期望的組裝結(jié)果，我們可以從中讀取y、g和我們需要的x值。

　　在指數(shù)系統(tǒng)的結(jié)果中，我們得到的是盡可能多的gx的值，如圖3所示，為了利用張的減法系統(tǒng)進(jìn)行減法的計(jì)算，我們先要將gx的值和p的值合并到同一瓦片上。其中合并系統(tǒng)的瓦片和張?jiān)O(shè)計(jì)的減法瓦片如圖4所示。

　　讓S2={11，10，01，00，0，1，+}，g=1，？子=2，分子瓦片集的定義如圖4（a）所示，這樣，系統(tǒng)可以自組裝成為如圖5中的結(jié)構(gòu)，而且組裝的時(shí)間為（1）。

　　這里，我們使用14種瓦片將兩個(gè)n位數(shù)相結(jié)合。很容易設(shè)計(jì)出一個(gè)瓦片系統(tǒng)找出第i行第i個(gè)位置。這個(gè)系統(tǒng)的主要目的是將兩個(gè)數(shù)結(jié)合在一起，然后在頂端顯示出結(jié)果。S2系統(tǒng)有兩種瓦片（如圖）淺紫色和深紫色，其中淺紫色瓦片的作用是將信息向上傳遞而深紫色瓦片的作用是將兩個(gè)數(shù)合并在一個(gè)瓦片上。像前面一樣，在種子結(jié)構(gòu)中，輸入中的一個(gè)數(shù)被編碼在下方，另一個(gè)數(shù)被編碼在最右一列上。

　　讓S3={0，1，00，01，10，11}，g=1，？子=2，分子瓦片集的定義如圖4（b）所示，這樣，系統(tǒng)可以自組裝成為獨(dú)一無(wú)的結(jié)構(gòu)，而且組裝的時(shí)間為（1）。

　　考慮這個(gè)分子瓦系統(tǒng)S3，顯然在（-1，0）位置上只有一個(gè)瓦片能夠結(jié)合上。以此類推下去，由于？子=2，而bdS（t），bdE（t）又是獨(dú)一無(wú)二的，所以瓦片的組裝應(yīng)該是獨(dú)特的。這個(gè)減法系統(tǒng)的操作邏輯是相同的，包括系統(tǒng)的輸入和輸出。在DNA瓦片系統(tǒng)模型中，每個(gè)瓦片都要從東側(cè)和南側(cè)輸入信息，從北側(cè)和西側(cè)輸出信息。

　　4結(jié)束語(yǔ)

　　在這篇文章中，我們嘗試用DNA瓦片建立模型，用自組裝攻破EIGamal公鑰密碼系統(tǒng)。在這個(gè)系統(tǒng)中我們使用了48種不同類型的分子瓦。按上所述，第一個(gè)子系統(tǒng)使用了33種不同類型的分子瓦，第二個(gè)子系統(tǒng)則使用了5種不同類型的分子瓦，而第三個(gè)子系統(tǒng)使用了8種不同類型的分子瓦。這時(shí)，我們可以說(shuō)這個(gè)系統(tǒng)的瓦片種類與輸入呈（1）線性關(guān)系。這就使解決EIGamal公鑰密碼系統(tǒng)成為可能。

　　這個(gè)系統(tǒng)的先進(jìn)性依賴于它的自組裝能力。我們需要做的是控制系統(tǒng)作用時(shí)的溫度和濃度。可以說(shuō)自組裝系統(tǒng)在分子計(jì)算方面有超強(qiáng)的控制力，而早期的實(shí)驗(yàn)和現(xiàn)在的理論研究都表明自組裝有更加廣闊的前景。

　　參考文獻(xiàn)

　　[1]A.W.OliverPelletier，“Algorithmicself-assemblyofdnatilesanditsapplicationtocryptanalysis，”inProceedubgsoftheGECCO-2002，NewYork，USA，2002，pp.139-146.[2]J.-M.Lehn，“Sopramolecularchemistry，”Science，pp.1762-1763，1993（260）.

　　[3]L.M.Adleman，“Combinatorialoptimizationproblemsinself-assembly，”inProceedingsoftheAnnualACMSymposiumonTheoryofComputing（STOC），Montreal，Canada，2002，pp.23-32.

　　[4]D.C.C.H.G.H.T.F.K.J.R.N.E.R.G.J.S.R.W.HaroldAbelson，DonAllen，“Amorphouscomputing，”CommunicationsoftheACM，vol.43，pp.74-82，2002.

　　[5]Y.Brun，“Arithmeticcomputationinthetileassemblymodel：Additionandmultiplication，”TheoreticalComputerScience378（1），pp.17-31，June2007.

　　[6]——，“Nondeterministicpolynomialtimefactoringinthetileassemblymodel，”TheoreticalComputerScience395（1），pp.3-23，2008.

　　[7]——，“Solvingnp-completeproblemsinthetileassemblymodel，”TheoreticalComputerScience395（1），pp.31-46，2008.

　　[8]Z.C.J.X.G.C.XuncaiZhang，YanfengWang，“Arithmeticcomputationusingself-assemblyofdnatiles：subtractionanddivision，”NaturalScience，vol.19，pp.377-388，2009

　　[9]G.R.ErikWinfree，TonyEng，“Stringtilemodelsfordnacomputingbyself-assembly，”inProceedingsofthe6thInternationalWorkshoponDNA-basedComputers，Leiden，TheNetherlands，2000，pp.65-84.

　　[10]E.Winfree，“Algorithmicself-assemblyofdna，”Ph.D.dissertation，CaliforniaInstituteofTechnology，PasadenaCA，1998.

　　[11]N.C.Seeman，“Dnananotechnology：Noveldnaconstructions，”AnnualReviewofBiophysicsandBiomolecularStructure，vol.27，pp.225-248，1998.

　　[12]C.Mao，W.Sun，andN.C.Seeman，“DesignedtwodimensionalDNAhollidayjunctionarraysvisualizedbyatomicforcemicroscopy，”J.Am.Chem.Soc.，vol.121，pp.5437-5443，1999.

　　[13]C.Mao，T.H.LaBean，J.H.Reif，andN.C.Seeman，“Logicalcomputationusingalgorithmicself-assemblyofDNAtriplecrossovermolecules，”Nature，vol.407，pp.493-496，2000.

---

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/jisuanjiyingyonglw/32421.html