DNA計算在信息安全領(lǐng)域的影響與應(yīng)用*

文/陳智華 石曉龍 程 珍

1華中科技大學自動化學院 武漢 430074

2浙江工業(yè)大學計算機學院 杭州 310023

1 引言

DNA納米技術(shù)是利用DNA分子特性，如堿基配對特性、自組裝特性等，自底向上構(gòu)建出可操控的新型納米尺度聚集體或超分子結(jié)構(gòu)。DNA納米技術(shù)已被應(yīng)用到生物、醫(yī)學檢測、基因診療、新材料開發(fā)、環(huán)境監(jiān)測和DNA計算機等多個領(lǐng)域。IBM公司正在利用DNA納米技術(shù)研制新型芯片；在芯片上，電子線路間的距離將僅為6nm左右，遠低于目前45nm的標準。利用這種技術(shù)，IBM公司將研制出更小、更便宜的微處理器芯片。DNA分子也是塑造納米材料的理想素材，在構(gòu)建納米元件和納米尺度的醫(yī)學檢測芯片上有重要應(yīng)用。以DNA作為結(jié)構(gòu)模板，或是作為計算工具的DNA納米技術(shù)開拓了一個新興研究領(lǐng)域，具有廣闊的發(fā)展前景。

據(jù)不完全統(tǒng)計，近10年來，僅在Nature、Sci?ence等國際頂級期刊上發(fā)表的DNA自組裝、DNA納米結(jié)構(gòu)和材料的相關(guān)論文就超過100篇；最近3年，關(guān)于DNA存儲[1]、DNA三維“磚塊”[2,3]、DNA機器人[4]和DNA計算電路[5]等就有10多篇。2010年，DNA納米技術(shù)領(lǐng)域的奠基者、美國紐約大學的Seeman教授由于在DNA納米技術(shù)方面的突出貢獻獲得了納米領(lǐng)域的最高獎Kavli納米科學獎。

DNA分子由于其獨特的結(jié)構(gòu)與生物功能在信息存儲與分子運算方面具有天然優(yōu)勢。目前的數(shù)據(jù)存儲介質(zhì)中，硬盤十分昂貴，且需要不斷的電力供應(yīng)；而像磁帶這類“無需電力”的最佳存檔材料，10年內(nèi)也會逐漸損壞。DNA能安全地存儲信息，它記錄了地球上所有生命的歷史，而這個強大功能是其他技術(shù)難以匹敵的。研究人員表示，DNA數(shù)據(jù)存儲將是2023年解決大型數(shù)據(jù)存儲問題的方案之一，這將引起DNA信息存儲的信息安全問題的研究熱潮[1]。

DNA納米技術(shù)用于計算，形成了DNA計算的研究方向，拓展了“計算”的概念和“計算”的模式。在分子尺度上，“計算”可以是化學鍵的相互作用或分子結(jié)構(gòu)的改變。這種全新的存儲和計算模式的實現(xiàn)，對信息安全領(lǐng)域有多方面的影響。與傳統(tǒng)計算相比，DNA計算具有高度并行性，海量存儲能力、低耗能和存儲時間長的特性。DNA計算特有的高度并行計算能力，對傳統(tǒng)的信息安全算法是否造成威脅？而其作為信息存儲載體，其信息安全如何保障？下面就國內(nèi)外在這兩方面的研究現(xiàn)狀展開討論。

2 國內(nèi)外研究現(xiàn)狀及發(fā)展

DNA納米技術(shù)是新興的前沿交叉領(lǐng)域，宗旨是利用DNA分子卓越的自組裝和堿基配對能力，將其作為一種納米材料實現(xiàn)精確的自底向上的納米構(gòu)筑[6]。其具有最可預(yù)測和最可程序化的優(yōu)點，可以通過調(diào)節(jié)堿基的數(shù)量和序列來精確控制雙螺旋結(jié)構(gòu)的長度，實現(xiàn)程序化自組裝。利用DNA的各種特性，使其作為信息存儲和計算工具時，給信息安全領(lǐng)域帶來了非凡的影響。

2.1 DNA計算的發(fā)展

基于分子間相互作用的計算模型理論始于20世紀80年代中期Head提出剪切系統(tǒng)[7]；實驗開始于 1994年，Adleman使用DNA分子解決了一個哈密爾頓路問題[8]?，F(xiàn)在，每年關(guān)于生物分子計算[9]和非傳統(tǒng)計算[10]的科學會議上都會有許多新的分子計算模型產(chǎn)生。

分子自組裝是生物分子計算模型的核心原則。目前，自組裝并沒有一個嚴格的精確定義，其可以理解為單個的元素自組織構(gòu)成一個更大更復(fù)雜的結(jié)構(gòu)的過程。這種自組織行為發(fā)生的范圍可以從宇宙水平（如銀河系的形成）到分子和原子水平（如晶體的形成或者蛋白質(zhì)的折疊）。DNA以其固有的堿基配對特征及其可預(yù)測的雙螺旋形狀，非常適合于設(shè)計實現(xiàn)可預(yù)測和程序化的組裝過程?；贒NA自底向上的自組裝研究始于30年前[11]，吸引了全球范圍內(nèi)的至少60個實驗室進行相關(guān)研究。在過去的15年中，研究主要集中于尋找適用的算法和可編程的自組裝結(jié)構(gòu)進行分子信息處理。

DNA計算的自組裝模型使用的“DNA Tile”是一簇具有分支結(jié)構(gòu)的DNA交叉分子，每一個分支都有一個粘貼末端，可以與具有互補粘貼末端的“Tile”嵌套結(jié)合，逐步形成DNA分子網(wǎng)格結(jié)構(gòu)。具有可編程特性的自組裝計算模型，不但保持了DNA計算并行性的優(yōu)勢，而且計算過程無需人工干預(yù)，自動完成得出結(jié)果，其靈活的Tile設(shè)計方法提供了納米尺度的自底向上的編程方法。Tile自組裝模型已被證明是圖靈等價的[12,13]。自1998年以來，幾個成功的實驗證實了DNA自組裝的計算能力[14]。Labean等使用三交叉分子Tile完成四步累積異或運算[15]。2006年，可放大輸入信號的DNA邏輯門（SeeSaw Gate）被構(gòu)造出來[16]。隨后分子邏輯門級聯(lián)被用于模擬神經(jīng)網(wǎng)絡(luò)運算過程，成功實現(xiàn)了一種基于DNA計算的Hopefield網(wǎng)絡(luò)[5]。

Seeman教授1983年提出將分支的DNA結(jié)構(gòu)和DNA粘性末端相結(jié)合可以組裝出規(guī)整的二維陣列結(jié)構(gòu)[17]，這是首次公開闡明作為生命密碼載體的DNA可以當作一種化學物質(zhì)來構(gòu)建納米材料和納米結(jié)構(gòu)，開創(chuàng)了利用DNA設(shè)計各種DNA結(jié)構(gòu)模塊的先河。在此基礎(chǔ)上，可以利用分子間識別作用精確組裝DNA分子，形成各種特定納米結(jié)構(gòu)和功能分子納米器件。2000年，5種不同結(jié)構(gòu)的DX模塊問世[18]，可以形成比線性DNA分子復(fù)雜的結(jié)構(gòu)，如二維環(huán)形、平面格子和三維籠狀結(jié)構(gòu)等。2003年，利用DNA自組裝技術(shù)構(gòu)造納米級高可導(dǎo)通的金屬導(dǎo)線的文獻在Science上首次發(fā)表，該文被引用超過1300次[19]。2005年，含有4個雙螺旋區(qū)域的自組裝模塊被設(shè)計出來，模塊之間通過黏貼末端的相互作用進一步組裝得到具有較小孔洞面積和較高DNA面密度的二維平面結(jié)構(gòu)[20]。同年，一種含有6個DNA雙螺旋的交叉結(jié)組裝模塊誕生，并基于合理的結(jié)構(gòu)設(shè)計得到DNA納米管和二維陣列結(jié)構(gòu)[21]。2012年底，美國哈佛大學維斯生物工程研究院的研究人員設(shè)計實現(xiàn)了類似“樂高”玩具的DNA“磚塊”（圖1），造出了102種復(fù)雜三維納米結(jié)構(gòu)，充分利用了DNA自組裝可編程的特性。這些可拼插的DNA“磚塊”將作為納米技術(shù)中的結(jié)構(gòu)建材、計算器件，將帶來巨大的醫(yī)療價值以及非醫(yī)療方面的應(yīng)用[2]。

圖1 Peng Yin研究組實現(xiàn)的“樂高”結(jié)構(gòu)的DNA磚塊

DNA折紙術(shù)是近年來提出的一種全新的DNA自組裝方法，被譽為DNA納米技術(shù)領(lǐng)域的一個重要里程碑[22]。理論上，DNA折紙術(shù)可以用DNA分子設(shè)計任意形狀的圖形和三維結(jié)構(gòu)，并且由于每條起固定作用的短鏈具有序列特異性，在所得圖案表面每個固定鏈處均可精確尋址。DNA折紙術(shù)相比DNATile自組裝最大優(yōu)勢在于組裝產(chǎn)物的復(fù)雜度得到很大提高，折紙術(shù)的可尋址像素點數(shù)目比DNATile自組裝至少高10倍[23]。折紙術(shù)構(gòu)建形狀的研究工作很豐富，獲得了各種平面圖形[24,25]及多種組合圖形[26]。2009年，三維折紙術(shù)開始展開研究，構(gòu)造出了DNA空心盒子和棱柱[27-29]，隨后更多復(fù)雜結(jié)構(gòu)體構(gòu)造成功，包括空心四面體和“蜂窩褶狀模型”等[30,31]，此結(jié)果被LaBean教授在Nature雜志撰文將此譽為DNA納米技術(shù)領(lǐng)域的又一個里程碑[32]。2011年復(fù)雜的曲面也能成功構(gòu)造出來，如精美的花瓶也能用DNA納米技術(shù)實現(xiàn)（圖2）[3]。

圖2 Yan Hao利用折紙術(shù)構(gòu)建精美的花瓶

2000年，“DNA燃料”的概念引入DNA納米技術(shù)中實現(xiàn)了僅依靠DNA鏈的狀態(tài)轉(zhuǎn)化[33]。這樣具有動力特性的DNA納米結(jié)構(gòu)，通過一系列的狀態(tài)轉(zhuǎn)換可實現(xiàn)某些特定功能，被統(tǒng)稱為DNA納米裝置。各種DNA納米裝置隨后問世，如可以切換構(gòu)象狀態(tài)的分子開關(guān)[34]，產(chǎn)生開合操作的分子鑷[35]，能循環(huán)轉(zhuǎn)動的分子馬達、分子齒輪、步進定向行走的納米行走器、可尋址行走的“蜘蛛俠”（圖3）等[36-38]。2012年構(gòu)建了木桶狀DNA納米機器，可實現(xiàn)靶標送藥（圖4）[4]?；贒NA分子的納米裝置的優(yōu)勢在于其高度的可設(shè)計性以及組裝、復(fù)制和再加工的容易性。

2013年，歐洲生物信息學研究所（EMBL-EBI）的研究人員創(chuàng)造出一種用DNA（能保存上萬年的材料）形式來存儲數(shù)據(jù)的方法，它能夠在約一杯量的DNA中儲存至少1億個小時的高清視頻[1]。驗證了DNA作為存儲介質(zhì)的可能。

圖3 分子機器人“蜘蛛俠”

圖4 可殺死癌細胞的DNA納米機器人

DNA多樣化的結(jié)構(gòu)和越來越精確的可控性，為DNA計算的發(fā)展提供了更為豐富的模式和技術(shù)實現(xiàn)方法。受DNA計算的存儲和并行特性啟發(fā)，人們開始研究DNA計算在信息安全領(lǐng)域的影響和發(fā)展。

2.2 傳統(tǒng)密碼破譯的國內(nèi)外研究現(xiàn)狀

傳統(tǒng)的加密技術(shù)比較有代表性的是數(shù)據(jù)加密標準DES體制，高級加密標準（AES）和公開密鑰密碼體制（RSA）。

DES算法的密鑰為56bits，所以試驗每一個密鑰的強力攻擊平均需要計算255次加密之后才能求出正確的密鑰。由于加密過程中的對稱性，只需要計算254次加密。在因特網(wǎng)的超強計算能力面前，DES顯得非常脆弱。

1998年，由美國電子前沿基金會（EFF）牽頭，密碼研究所和高級無線電技術(shù)公司參與設(shè)計建造了DES破譯機。該破譯機可用二天多時間破譯一份DES加密的密文，而整個破譯機的研制經(jīng)費不到25萬美元。它采用的破譯方法是強破譯攻擊法，破譯機正好用56個小時找出了一個56bits的密鑰，該方法是針對特定的加密算法設(shè)計出相應(yīng)的硬件來對算法密鑰空間進行窮舉搜索[39]。因此，在實際使用中，要加大密鑰的長度。

早在1997年，國家標準和技術(shù)研究所（NIST）宣布，需要為DES（很容易受到蠻力攻擊）尋找新的接替者。根據(jù)NIST的定義，這種新的、非機密、公開披露的加密算法稱為高級加密標準（AES）。AES由3個分組密碼組成：AES-128、AES-192和 AES-256，具有軟件和硬件實現(xiàn)技術(shù)，而且速度快。雖然沒有人成功地破解全部的AES，各類研究人員已經(jīng)公布了針對AES減round版的攻擊。目前，對AES最有效的攻擊（不考慮相關(guān)密鑰攻擊）是對它的積分密碼分析[40]，對AES-128可攻擊到7輪，對AES-192和AES-256可攻擊到8輪。

RSA公鑰密碼體制的廣泛使用，極大地刺激了大整數(shù)分解方法的研究。針對RSA最流行的攻擊一般是基于大數(shù)因數(shù)分解。1999年，RSA-155（512bits）被成功分解，花了5個月時間（約8000 MIPS年）和224 CPU hours在一臺有3.2Gb中央內(nèi)存的Cray C916計算機上完成。2002年，RSA-158也被成功因數(shù)分解。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分布式計算技術(shù)和量子計算機理論日趨成熟的條件下，RSA加密安全性受到了挑戰(zhàn)。2009年12月12日，Aoki等人成功分解了RSA-768（768bits,232digits）[41]。這一事件威脅了現(xiàn)通行的1024-bit密鑰的安全性，普遍認為用戶應(yīng)盡快升級到2048-bit或以上。

針對RSA公鑰密碼體制，量子分解算法是1995年美國科學家皮特·休爾（Peter Shor）提出來的，是迄今量子計算領(lǐng)域最著名的算法[42]。它利用量子計算的并行性可以快速分解出大數(shù)的質(zhì)因子，使得量子計算機將很容易破解目前廣泛使用的密碼。因此，Shor算法的提出迅速引起了世界各國對量子計算的研究的高度關(guān)注。潘建偉等與英國牛津大學同事合作，在國際上首次用光子比特，也是首次用真正的純態(tài)量子系統(tǒng)，實驗演示了關(guān)鍵性的Shor算法，實現(xiàn)了15=3×5這一質(zhì)因子分解，并且確認了量子計算中多態(tài)純糾纏的存在，驗證了量子加速的根源問題。當前，量子密碼術(shù)實用還有相當一段距離，但是英國電信的試驗系統(tǒng)的成功充分說明了這一技術(shù)的進展是如何迅速。一旦在長距離的傳統(tǒng)光纖信道上實現(xiàn)量子密鑰的傳輸，則量子密碼在技術(shù)上及成本上完全壓倒經(jīng)典的密碼技術(shù)。

為了克服傳統(tǒng)計算機在求解若干密碼問題時出現(xiàn)存儲量與運算速度上的不足，我們將借生物計算中新興的計算模式——自組裝DNA計算提出可行和有效的方案進行密碼破譯。理論已證明二維自組裝模型有通用計算能力，是圖靈通用的。在此基礎(chǔ)上，利用自組裝DNA計算的強大并行計算的特性，可知算法自組裝模型進行密碼系統(tǒng)的破譯具有理論上的可能性，將對信息安全領(lǐng)域研究探索新的途徑并提供技術(shù)支撐。

2.3 DNA計算對傳統(tǒng)信息安全領(lǐng)域的影響

基于DNA計算的特性，科學家研究討論了其可能對傳統(tǒng)密碼算法可能的威脅。

2.3.1 數(shù)據(jù)加密標準算法

理查德·利普頓（Richard Lipton）和丹·波恩（Dan Boneh）最早在這一領(lǐng)域進行了研究。1996年他們給出了使用分子計算機破譯數(shù)據(jù)加密標準的方法[43]，所采用的是比較直接而樸素的方法——明文密文對破譯法。該方法首先建立在對二進制串進行適當編碼的基礎(chǔ)上，創(chuàng)建編碼各種密鑰的DNA初始溶液，分別粘貼已知的明文鏈后再進行16輪的加密運算，最后通過搜索找到密鑰。在此基礎(chǔ)上，阿德爾曼等人又給出了使用sticker模型破譯數(shù)據(jù)加密標準的方法[44]，這種模型主要使用DNA分子記憶鏈和粘貼來進行計算。該方法仍然采用了明文密文對破譯法。其設(shè)計的數(shù)據(jù)加密標準分子算法是在粘貼機上執(zhí)行的。

2.3.2 RSA算法

張云龍（Weng-Long Chang，音譯）和郭敏意（Minyi Guo，音譯）等人利用DNA計算設(shè)計了整數(shù)因式分解的方法，從而可以破解RSA算法[45]。為分解2個大素數(shù)的乘積，所需的試管數(shù)隨素數(shù)位數(shù)呈線性增加，而需要的DNA分子數(shù)卻呈指數(shù)增長，生物運算的數(shù)目為多項式增長。由此推算，當分解1000位的大數(shù)時，需要的DNA溶液體積約為2.5×10131升，這是不可能獲得的質(zhì)量?？梢娺@種算法對RSA不能造成威脅。

比弗（Beaver[46]）等人借助阿德爾曼的思想將大數(shù)分解問題轉(zhuǎn)化為哈密爾頓（Hamiltonian）路徑問題，分析出1000位的RSA模的復(fù)雜度問題至少需要106個頂點數(shù)。據(jù)保守估計，求解該哈密爾頓路徑問題所需溶液的體積遠遠大于1020萬升，因此也不可行。

布魯恩（Brun）于2007年提出了基于DNA瓦自組裝的加法和乘法模型[47]。同年，布魯恩在上述工作基礎(chǔ)上，提出基于DNA瓦自組裝的非確定性整數(shù)分解模型[48]。該算法的基本思想是：建立非確定性猜測因子系統(tǒng)。該子系統(tǒng)能非確定性地選擇2個數(shù)，然后通過乘法子系統(tǒng)，得到這2個數(shù)的乘積，同時通過比較子系統(tǒng)，將其與輸入數(shù)進行比較，如果與輸入數(shù)符合，即找到了該數(shù)分解的因子。文獻所提方案需要的DNA瓦種類和誤差精度要求，超出了目前分子實驗技術(shù)水平，僅僅具有理論參考價值。

2.3.3 破譯背包密碼

背包問題（Knapsack Problem，KP）是運籌學中一個典型的優(yōu)化難題，在預(yù)算控制、項目選擇、材料切割和貨物裝載等實踐中有重要應(yīng)用，也常常作為其他問題的子問題加以研究。石曉龍[49]嘗試利用DNA分子計算方法求解整數(shù)背包問題，首先設(shè)計分子運算篩選出所有可能解，然后在所有可能解中搜索最優(yōu)解，優(yōu)化的目標為在所有可能解中搜索價值最大的解。在設(shè)計最優(yōu)解的搜索計算中，可以充分利用DNA計算的并行特點，將帶有同位素標記的DNA探針同上一步反應(yīng)結(jié)果進行雜交，以此來實現(xiàn)最優(yōu)解的搜索。隨后，戴爾米拉金（Darehmiraki）和尼赫（Nehi）[50]利用DNA計算的高度并行性在試管中求解0-1背包問題。通過巧妙的編碼技術(shù)，他們將所求解的問題映射成DNA序列集合，在試管中形成初始解空間，利用分離合并等生物技術(shù)，刪除不滿足約束條件的不可行解所對應(yīng)的DNA鏈，并求出每條可行解鏈所對應(yīng)的目標函數(shù)值，經(jīng)比較得到最優(yōu)解所對應(yīng)的DNA鏈。以上文獻給出的也是理論分析，沒有實驗驗證。

目前已有的背包問題DNA計算的研究都是基于粘帖模型的，通過結(jié)合生物芯片技術(shù)，實現(xiàn)可行解的提取和最優(yōu)解的選擇。

2.3.4 破譯NTRU密碼系統(tǒng)

NTRU被認為是21世紀最有前途的公鑰密碼體制，以速度快、安全性強等優(yōu)點被廣泛應(yīng)用于數(shù)據(jù)加密、數(shù)字簽名等領(lǐng)域。佩爾蒂埃（Pelletier）借助自組裝的思想，通過定義相應(yīng)的三維瓦結(jié)構(gòu)，實現(xiàn)NTRU中所需卷積計算。利用暴力破解的方法，對所有可能的密鑰進行卷積計算，根據(jù)NTRU的特點找到密鑰。但是，由于該方案中的“瓦”尚未設(shè)計成功，因此只能從理論上說明其可行性。文獻[51]提出了另一種用自組裝DNA計算破譯NTRU公鑰密碼系統(tǒng)的非確定性算法。

2.3.5 破譯Diffie-Hellman密鑰交換算法

Diffie-Hellman密鑰交換算法既是最初的公鑰密碼思想，又是當前人們使用較多的一種重要機制，許多商業(yè)產(chǎn)品也使用了這種密鑰交換技術(shù)。Diffie-Hellman密鑰交換算法的目的是使兩個用戶能安全地交換共享的密鑰，以便用戶能在后續(xù)的通信中用該密鑰對消息加密。Diffie-Hellman密鑰交換的安全性建立在下述事實之上：求關(guān)于素數(shù)的模冪運算相對容易，而計算離散對數(shù)卻非常困難；對于大素數(shù)，求離散對數(shù)被認為是不可行的。2012年，文獻[52]設(shè)計了基于自組裝模型破譯Diffie-Hellman密鑰交換算法的方法，該算法給出了自組裝模型求解有限域GF（p）（p為素數(shù)）上的模乘運算和模冪運算，在此基礎(chǔ)上，充分利用算法自組裝系統(tǒng)的強大并行性計算能力，提出了自組裝算法執(zhí)行有限域GF（p）上的離散對數(shù)問題，即可得到其中一個用戶的私鑰，通過PCR和凝膠電泳技術(shù)等生物操作來讀取自組裝體增長后的代表該用戶私鑰的最終結(jié)果，再通過模冪運算即可得到用戶雙方的會話密鑰，進而破譯Diffie-Hellman密鑰交換算法，且可證明在很多并行的自組裝體執(zhí)行運算過程中尋找成功解的概率可以趨近于1。通過這樣的方法，可以威脅到Diffie-Hellman密鑰交換的安全。

2.3.6 破譯橢圓曲線Diffie-Hellman密鑰交換算法

橢圓曲線密碼系統(tǒng)是Koblitz和Millef于1985年在各自開發(fā)的公鑰加密算法中提出的[53]，它是用橢圓曲線有限群代替基于有限域上離散對數(shù)問題公鑰密碼中的有限循環(huán)群所得到的一類密碼體制?；跈E圓曲線密碼體制本身的優(yōu)點，這種密碼體制逐步成為密碼學中的重要分支，特別是移動通信安全方面的應(yīng)用更是加快了這一趨勢。橢圓曲線密碼的優(yōu)勢逐漸凸顯出來，它具有的巨大的商業(yè)價值以及軍事價值正在為越來越多的人所關(guān)注。

文獻[54]給出了基于DNA計算模型求解橢圓曲線離散對數(shù)的算法。根據(jù)有限域GF（2n）乘法逆元和除法運算的相對復(fù)雜性，文獻[55]利用自組裝模型有效求解有限域GF（2n）乘法逆元和除法運算的DNATile自組裝模型。用該模型可在多項式的時間內(nèi)用常量個Tile類型計算該域乘法逆元和除法運算。該研究成果是橢圓曲線Diffie-Hellman密鑰交換算法密碼分析工作的重要基礎(chǔ)。

以上模型都使用了DNA計算這種全新的計算模式，隨著計算量的增加，現(xiàn)有的DNA計算模型的時間復(fù)雜度并不顯著增加，而其空間復(fù)雜度卻顯著增加。因此，丹·波恩等人的方法只能攻破64位以下對稱密碼系統(tǒng)。

以上的文獻都只是從理論上討論了DNA計算對傳統(tǒng)密碼算法的威脅，并沒有實驗驗證。這也凸顯出DNA計算在進行大量復(fù)雜計算存在的問題，一個是誤差隨著實驗進行被傳遞放大，一個是需要的DNA分子隨著計算規(guī)模呈現(xiàn)指數(shù)增長。因此，就目前來看，DNA計算還不能對傳統(tǒng)加密算法構(gòu)成實質(zhì)性威脅。

2.4 DNA作為信息存儲載體的信息安全

既然DNA可以作為信息存儲介質(zhì)，存儲在此介質(zhì)上的信息安全如何保障？數(shù)據(jù)的保密性、完整性和不可否定性等方面，具體在DNA存儲中如何實施？就此，也有不少文獻研究了相關(guān)的算法和方案，也有相關(guān)的實驗驗證。

2.4.1 一次一密

美國杜克大學的阿詩士·杰哈尼（Ashish Gehani）和托馬斯·拉賓（Thomas H.Labean）等人提出了一種基于一次性密碼本的DNA加密和解密方法[56]。他們設(shè)計了兩種DNA序列的一次一密加密方法：一種是映射替代法，根據(jù)定義的映射表將固定長度的DNA明文序列單元替換成對應(yīng)的DNA密文序列；另一種是DNA芯片異或法，采用光刻技術(shù)和熒光標記技術(shù)進行DNA明文序列與密碼本序列的異或操作。

陳杰（Jie Chen，音譯）等提出了基于DNA計算的分子密碼設(shè)計[57]。作者利用DNA引物擴增反應(yīng)進行模2加法運算，以及利用DNA計算的并行性實現(xiàn)一次性密碼本（one-time-pads）的加密和解密。

2010年，有文獻提出利用DNA自組裝的自然過程實現(xiàn)真正的隨機密鑰的產(chǎn)生，從而利用DNA自組裝實現(xiàn)（OTP）加密[58]。

以上方案給出的也是理論分析和仿真分析，沒有具體實驗驗證。

2.4.2 聚合酶鏈式反應(yīng)（PCR①Polymerase chain reaction，聚合酶鏈式反應(yīng)）引物作為密鑰

安德烈·萊爾（Andre Leier）等人提出了使用DNA二元串②是指使用DNA片段進行編碼表示的固定長度的二進制數(shù)字串進行加密和解密的方法[59]。該方法利用聚合酶鏈式反應(yīng)必須要有正確成對引物的特點，基于DNA二元串對信息進行編碼，然后將其和大量相似DNA二元串混雜在一起，只有知道正確的引物的發(fā)送方和接收方能從聚合酶鏈式反應(yīng)中讀出消息。該方法類似于信息隱藏技術(shù)，其整體方案也符合常規(guī)密碼模型。另一種方法是利用凝膠電泳的圖形進行加密解密。其解密的思路是，當包含信息的DNA串和不包含信息的串混淆在一起時，除了發(fā)送雙方都需知道正確的混淆串，還要將上述兩種串同時進行聚合酶鏈式反應(yīng)，然后將得到的凝膠電泳圖形相減，最終獲得所包含的信息。此方法結(jié)合第一種方法，可以組成分子校驗碼，若發(fā)現(xiàn)混淆溶液的凝膠圖像發(fā)生了明顯變化，則說明這次信息交換過程中信息溶液受到了攻擊。該文獻給出了密鑰產(chǎn)生的實驗演示，沒有完整的實驗過程。

田中（K.Tanaka）等人設(shè)計了一個使用DNA計算作為陷門函數(shù)的密鑰共享協(xié)議[60]，并且用實驗證明了其可行性，只有擁有接收者和發(fā)送者的正確引物，才能擴增復(fù)制出正確的消息。該協(xié)議的安全性受到生物技術(shù)的保障。

2.4.3 對語言進行加密

在文獻[61]中，討論了以單詞、音節(jié)或者字母為單位對某種語言進行DNA加密的技術(shù)，特別分析了DNA編碼、數(shù)據(jù)壓縮和錯誤檢測等問題，提出合成需要的DNA長鏈是DNA存儲和加密等數(shù)據(jù)處理在技術(shù)實現(xiàn)上普遍存在的困難。

2.4.4 利用DNA探針進行對稱加密

在該研究中，對稱密鑰加密系統(tǒng)是通過應(yīng)用DNA探針技術(shù)、生物芯片和雜交實現(xiàn)加密解密的[62]。信息的加密和解密的密鑰由DNA探針形成，而其密文嵌入在一個專門設(shè)計的DNA芯片（微陣列）中。該系統(tǒng)的安全性主要來源于生化反應(yīng)的條件和探針檢測的困難，而不是傳統(tǒng)的計算復(fù)雜性。其具體算法并沒有進行實驗驗證，而是借用了已發(fā)表的生物實驗方法[63]。

2.4.5 非對稱加密和簽名技術(shù)

在DNA探針對稱加密算法的基礎(chǔ)上，提出非對稱加密和簽名技術(shù)[64]。類似于傳統(tǒng)的公鑰密碼學，提出的方案使用一對密鑰，公有密鑰加密和私有密鑰簽名。其實驗基礎(chǔ)也是基于文獻[60]，并沒有進行完整實驗驗證。

2.4.6 基于DNA計算的信息隱藏方法

DNA隱寫術(shù)的原理是，利用大量的無關(guān)信息隱藏加密后的DNA信息，使得攻擊者難以確定正確的DNA片斷。只有正確的接收者才能根據(jù)事前雙方約定的信息找到正確的DNA片斷，并獲取隱藏于其中的信息。美國紐約市立大學西奈山醫(yī)學院的班克羅夫特（C.Bancroft）等人首先實現(xiàn)相關(guān)實驗。他們將一條二戰(zhàn)中的著名信息進行DNA隱寫，并將其成功地提取出來[65]。盧明欣等人對采用這種方法的信息隱藏技術(shù)進行了安全性分析，并提出改進的方法[66]。文獻[15]引入一個可逆對比映射實現(xiàn)DNA可逆信息隱藏。文獻[16]提出了3個基于DNA序列的信息隱藏方法。該方法主要利用DNA計算的高密度特性，以生物技術(shù)作為安全保證，沒有涉及復(fù)雜的數(shù)學運算。

2.4.7 DNA認證

DNA認證方法能夠十分準確地認證生物個體的身份，并已廣泛應(yīng)用于司法、金融等領(lǐng)域。DNA鑒別技術(shù)的理論基礎(chǔ)是生物個體DNA序列的特殊性，且親緣關(guān)系較近的生物體DNA序列具有相似性。在2000年DNA認證技術(shù)就應(yīng)用于奧運紀念商品的認證商標中。已有相關(guān)研究利用DNA加密算法進行基于DNA的水印技術(shù)，此技術(shù)可使DNA水印不但可以印刷在物品上，甚至可以植入活體中[67]，然后通過辨認DNA認證信息來驗證用戶身份或版權(quán)信息。

3 前景與展望

DNA作為已知的生命遺傳信息存儲介質(zhì)至少有35億年以上歷史，其分子結(jié)構(gòu)、密度和壽命，天然適用于信息存儲和計算，同時利用DNA分子進行的計算可以具有分子計算的極大并行性優(yōu)勢。

DNA計算及DNA納米技術(shù)研究受到各國政府的高度重視。美國白宮科技部于2011年2月發(fā)布“美國2011納米技術(shù)發(fā)展戰(zhàn)略（NNI）”，該計劃旨在協(xié)調(diào)美國納米技術(shù)的整體研發(fā)，增強整個美國在納米尺度上的科學研究合作力度，確保美國在納米技術(shù)、工程技術(shù)方面的世界領(lǐng)先地位[68]。德國聯(lián)邦教育與研究部也于2011年制定了“納米技術(shù)行動計劃2015”，這是德國政府在高科技戰(zhàn)略框架下針對納米領(lǐng)域施政的一個共同綱領(lǐng)。俄國政府于2010年納米技術(shù)國際論壇上明確指出，納米技術(shù)是未來經(jīng)濟的領(lǐng)軍力量，表示將打造真正意義上的納米產(chǎn)業(yè)，以便到2015年使國家的納米行業(yè)總產(chǎn)值達到近333億美元[69]。由英國皇家化學會自2010年發(fā)起的“納米科學的挑戰(zhàn)——化學科學前沿國際研討會”至今已開展8屆，會議主要以納米醫(yī)學包括藥物的納米級封裝和體內(nèi)投送、納米材料的定向組裝、納米器件制作與納米機器等為研究內(nèi)容[70]。

基于DNA自組裝的傳感器很小，可以在細胞內(nèi)工作，具有快速、敏感和特異性高的優(yōu)點，其納米結(jié)構(gòu)的控制精度達原子級[71]。DNA納米技術(shù)的應(yīng)用前景非常誘人，但目前其基礎(chǔ)理論、技術(shù)和方法仍然存在很多問題待解決，比如作為信息處理單元，其讀寫成本高，處理時間長；作為結(jié)構(gòu)構(gòu)建單元，其設(shè)計復(fù)雜，穩(wěn)定性和與生物兼容性沒有量化的方法衡量；作為納米機器人，其行為笨拙，無法交流，無法處理復(fù)雜任務(wù)，也不能在活體中存活。

在我國開展DNA計算及DNA納米技術(shù)的基礎(chǔ)理論及應(yīng)用研究將在未來幾十年內(nèi)提高中國在DNA計算理論及DNA納米技術(shù)應(yīng)用領(lǐng)域的國際地位，在這一新興領(lǐng)域迎頭趕上并獲得一大批原創(chuàng)性成果。數(shù)據(jù)顯示，2007年以來，中國已成為biosensor and bioelectronics雜志發(fā)表論文最多、下載文獻量最大的國家。在2010—2011年度出版、引用率排名前50的研究論文中，有32篇論文來自中國。

具體到信息安全領(lǐng)域，目前基于DNA計算的加密是建立在生化反應(yīng)的特殊條件、檢測困難或特殊結(jié)構(gòu)等基礎(chǔ)上的，而不是計算復(fù)雜度上。如果結(jié)合傳統(tǒng)加密算法，配合計算復(fù)雜性的生化實現(xiàn)，則DNA加密信息更加安全可靠。因為其數(shù)據(jù)不但受到生物反應(yīng)困難的保護，還受到計算復(fù)雜度的安全保護。在基于DNA納米技術(shù)的信息安全應(yīng)用和研究中，有許多問題有待解決。例如，如何利用DNA自組裝設(shè)計各種剛性結(jié)構(gòu)及合理控制自組裝過程，減少功能對DNA分子瓦種類的依賴；如何對信息進行編碼，實現(xiàn)信息處理過程中系統(tǒng)具有一定的容錯和糾錯能力；如何利用DNA自組裝和折紙術(shù)，從結(jié)構(gòu)上實現(xiàn)DNA分子計算單元的封裝，隱藏具體數(shù)據(jù)格式和處理方式；DNA信息安全體系缺乏理論和算法的支持。

當前，DNA分子計算相關(guān)的DNA納米技術(shù)正在迅速發(fā)展，DNA計算相關(guān)研究的成果越來越豐富，有越來越多的實現(xiàn)方法。隨著DNA分子納米技術(shù)在信息存儲和處理領(lǐng)域應(yīng)用的拓展，利用DNA進行的分子級別信息安全問題研究將吸引更多研究人員的注意和興趣?，F(xiàn)在制約DNA計算研究的還是DNA納米技術(shù)與成本問題，目前大量進行DNA分子測序和合成仍然較為昂貴，但DNA納米技術(shù)的快速發(fā)展，使得這些費用正在迅速降低。DNA納米技術(shù)的迅猛發(fā)展正在并將為基于DNA的分子計算及其在信息安全和存儲領(lǐng)域的應(yīng)用帶來翻天覆地的變化。

1 Goldman N,Bertone P,Chen S et al.Towards practical,high-ca-pacity,low-maintenance information storage in synthesized DNA.Nature,2013,doi:10.1038/nature 11875.

2 Ke Y,Ong L L,Shih W M et al.Three-dimensional structures self-assembled from DNAbricks.Science,2012,6111（338）:1177-1183.

3 Han D,Pal S,Nangreave J et al.DNAorigami with complex curvatures in three-dimensional space.Science,2011,6027（332）:342-346.

4 Douglas S M,Bachelet I,Church G M.Alogic-gated nanorobot for targeted transport of molecular payloads.Science,2012,6070（335）:831-834.

5 Qian L,Winfree E.Scaling up digital circuit computation with DNAstrand displacement cascades.Science,2011,6034（332）:1196-1201.

6 Fu T J,Seeman N C.DNAdouble-crossover molecules.Biochemistry,1993,32:3211-3220.

7 Head T.Formal language theory and DNA:an analysis of the generative capacity of specific recombinant behaviours.Bull.Math.Biol.,1987,49:737-759.

8 Adleman L.Molecular computation of solutions of combinatorial problems.Science,1994,266:1021-1024.

9 International Conference on DNA-based computing and molecular programming（annual meetings）.http://www.dna-computing.org/.

10 International Conference Series.Unconventional computing and natural computing（annual meetings）.http://www.cs.auckland.ac.nz/CDMTCS//conferences/uc/uc.html.

11 Seeman N C.DNAjunctions and lattices.J.Theor.Biol.,1982,99:237-247.

12 Adleman L,Kari J,Kari L et al.On the decidability of self-assembly of infinite ribbons.In Proceedings of the 43rdAnnual IEEE Symposium on Foundations of Computer Science（FOCS02）,November 2002,530-537,Ottawa,Ontario,Canada.

13 Winfree E.Algorithmic self-assembly of DNA.PhD thesis,June 1998,California Institute of Technology,Pasadena,CA,USA.

14 Winfree E,Liu F,Wenzler LAet al.Design and self-assembly of two-dimensional DNAcrystals.Nature,1998,394:539-544.

15 Mao C,LaBean T H,Reif J H et al.Logical computation using algorithmic self-assembly of DNAtriple-crossover molecules.Nature,2000,407:493-496.

16 Seelig G,Soloveichik D,Zhang D Y et al.Enzyme-free nucleic acid logic circuits.Science,2006,5805（314）：1585-1588.

17 Seeman N C,Kallenbach N R.Design of immobile nucleic acid junctions.Biophys.J,1983,44:201-209.

18 LaBean T H,Yan H,Kopatsch J et al.Construction,analysis,ligation,and self-assembly of DNAtriple crossover complexes.JAm Chem Soc.,2000,122:1848-1860.

19 Yan H,Park S H,Finkelstein G et al.DNA-templated self-assembly of protein arrays and highly conductive nanowires.Science,2003,5641（301）:1882-1884.

20 Reishus D,Shaw B,Brun Y et al.Self-assembly of DNA double-double crossover complexes into high density,doubly connected,planar structures.JAm Chem Soc.,2005,127:17590-17591.

21 Mathieu F,Liao S P,Kopatsch J et al.Six-helix bundles designed from DNA.Nano Lett.,2005,5:661-665.

22 Rothemund PW K.Folding DNAto create nanoscale shapes and patterns.Nature,2006,440:297-302.

23 Um S H,Lee J B,Park N et al.Enzyme-catalysed assembly of DNAhydrogel.Nat Mater.,2006,5:797-801.

24 Douglas S M,Chou J J,Shih W M.DNA-nanotube-induced alignment of membrane proteins for NMR structure determination.Proc NatlAcad Sci USA,2007,104:6644-6648.

25 Voigt N V,Torring T,RotaruAet al.Single-molecule chemical reactions on DNAorigami.Nat Nanotechnol,2010,5:200-203.

26 Andersen E S,Dong M,Nielsen M M et al.DNAorigami design of dolphin-shaped structures with flexible tails.ACS Nano.,2008,2:1213-1218.

27 Andersen E S,Dong M,Nielsen M M et al.Self-assembly of nanoscale DNAbox with a controllable Lid.Nature,2009,459:73-76.

28 KuzuyaA,Komiyama M.Design and construction of a boxshaped 3D-DNAorigami.Chem Commun.,2009,4182-4184.

29 Endo M,Hidaka K,Kato T et al.DNAprism structures constructed by folding of multiple rectangular arms.JAm Chem Soc.,2009,131:15570-15571.

30 Ke Y,Sharma J,Liu M et al.Scaffolded DNAorigami of a DNA tetrahedron molecular container.Nano Lett.,2009,9:2445-2447.

31 Douglas S M,Dietz H,Liedl T et al.Self-assembly of DNAinto nanoscale three-dimensional shapes.Nature,2009,459:414-418.

32 LaBean T H.Nanotechnology:another dimension for DNAart.Nature,2009,459:331-332.

33 Yurke B,TurberfieldA,MillsAet al.ADNA-fuelled molecular machine made of DNA.Nature,2000,406（6796）:605-608.

34 Sekiguchi H,Komiya K,Kiga D et al.Adesign and feasibility study of reactions comprising DNAmolecular machine that walks autonomously by using a restriction enzyme.Natural Computing,2008,7（3）:303-315.

35 Bath J,Green S,TurberfieldA.Afree-running DNAmotor powered by a nicking enzyme.Angewandte Chemie International Edition,2005,44（28）:4358-4361.

36 Chen Y,Wang M,Mao C.An autonomous DNAnanomotor powered by a DNAenzyme.Angewandte Chemie International Edition,2004,43（27）:3554-3557.

37 Yin P,Choi H,Calvert C et al.Programming biomolecular self-assembly pathways.Nature,2008,451（7176）:318-322.

38 Lund K,ManzoAJ,Dabby N et al.Molecular robots guided by prescriptive landscapes.Nature,2010,465:206-210.

39 Rothke B.DES Is Dead!Long Live???.Information System Security,1998,（Spring）:57-60.

40 Ferguson N,Kelsey J,Lucks S et al.Improved cryptanalysis of Rijindael.Proceedings of Fast Software Encryption-FSE’00.LNCS 1978,Spring-Verlag,2000:213-230.

41 Kleinjung T,Aoki K,Franke J et al.Factorization of a 768-Bit RSAmodulus.Advances in Cryptology-CRYPTO.Lecture Notes in Computer Science,2010,6223:333-350.

42 Shor PW.Polynomial-time algorithm for prime factorization and discrete logarithms on a quantum computer.SIAM Journal on Computing,1995,26（5）:1484-1509.

43 Lipton R,Boneh D.Breaking DES using a molecular computer.DIMACS Series in Discrete Mathematics and Theoretical computer science,1996,27:37-58.

44 Adleman L,Rothemund P,Sam R et al.On applying molecular computation to the data encryption standard.Journal of Computational Biology,1999,6（1）:53-63.

45 Chang W L,Guo M Y,Ho M S.Fast parallel molecular algorithms for DNA-based computation:factoring integers.IEEE Transactions on NanoBioscience,2005,2（4）:149-163.

46 Beaver D.Factoring:the DNAsolution.Asia crypt’,1994,419-423.

47 Brun Y.Arithmetic computation in the tile assembly model:addition and multiplication.Theoretical Computer Science,2006,378:17-31.

48 Brun Y.Nondeterministic polynomial time factoring in the tile assembly model.Theoretical Computer Science,2008,395（1）:3-23.

49 石曉龍,許進.DNA計算與背包問題.計算機工程與應(yīng)用,2003,27:44-52.

50 Darehmiraki M,Nehi H M.Molecular solution to the 0-1 knapsack problem based on DNAcomputing.Applied Mathematics and Computation,2007,187:1033-1037.

51 張勛才.基于自組裝DNA計算的NTRU密碼系統(tǒng)破譯方案.計算機學報,2008,31（12）:2129-2137.

52 Cheng Z.NondeterministicAlgorithm for breaking Diffie-Hellman key exchange using self-assembly of DNAtiles.International Journal of Computers,Communication and Control,2012,7：616-630.

53 Koblitz N.Elliptic curve cryptosystems.Mathematics of Computation,1987,48:203-209.

54 Li K L,Zou S T,Xu J.Fast parallel molecular algorithms for DNA-based computation:solving the elliptic curve discrete logarithm problem over GF（2n）.Journal of Biomedicine and Bio-technology,2008,2008（1）:1-10.

55 Cheng Z.Arithmetic computation of multiplicative inversion and division in GF（2n）using self-assembly of DNA tiles.Journal of Computational and Theoretical Nanoscience,2012,9（3）:336-346.

56 GehaniA,LaBean T H,Reif J H.DNA-based cryptography,in Dimacs Series In Discrete Mathematics&Theoretical Computer Science,2000,54:233-251.

57 Chen J.ADNA-based biomolecular cryptography design.In Proceedings of the 2003 International Symposium on Circuits and Systems,2003,822-825.

58 Miki H,Hiroaki K,Kazuhiro O.Design of true random one-time pads in DNAXOR cryptosystem.IWNC,PICT 2,2010,174-183.

59 LeierA,Richter C,Banzhaf W et al.Cryptography with DNAbinary strands.Biosystems,2000,57:13-22.

60 Tanaka K,OkamotoaA,Saito I.Public-key system using DNAas a one-way function for key distribution.BioSystems,2005,81:25-29.

61 Jonathan P L.Long-term data storage in DNA.TRENDS in Biotechnology,2001,19（7）:247-250.

62 Lu M X,Lai X J,Xiao G Z et al.Symmetric-key cryptosystem with DNAtechnology.Sci China Ser F-Inf Sci,2007,50（3）:324-333.

63 DeRisi J L,Iyer V R,Brown P O.Exploring the metabolic and genetic control of gene expression on a genomic scale.Science,1997,278:680-686.

64 Lai X J,Lu M X,Qin L et al.Asymmetric encryption and signature method with DNAtechnology.Information Sciences,2010,53（3）:506-514.

65 Clelland C T,Risca V,Bancroft C.Hiding messages in DNAmicrodots.Nature,1999,399:533-534.

66 盧明欣,傅曉彤,秦磊等.DNA信息隱藏方法的安全性分析和保密增強方法.西安電子科技大學學報（自然科學版）,2006,33（3）:448-452.

67 Dominik H,Angelika B.DNA-based watermarks using the DNA-crypt algorithm.BMC Bioinformatics,2007,8:176.

68 http://www.bioon.com/trends/news/481704.shtml.

69 http://www.bioon.com/trends/news/471714.shtml.

70 http://meeting.sciencenet.cn/cinfo.aspx?cid=2748.

71 Wengel J.Nucleic acid nanotechnology-towards angstrom-scale engineering.Organic and Biomolecular Chemistry,2004,2:277-280.