霍家佳,張文政

(中國(guó)電子科技集團(tuán)有限公司第30研究所，保密通信重點(diǎn)實(shí)驗(yàn)室, 成都 610041)

0 引 言

密碼學(xué)是用于保護(hù)數(shù)據(jù)安全的工具，從古老的凱撒密碼到現(xiàn)代密碼學(xué)，已經(jīng)兩千多年了。脫氧核糖核酸(DNA)是生物遺傳物質(zhì)，攜帶生命的遺傳信息，自從Watson和Crick在1953年發(fā)現(xiàn)DNA之后，人們發(fā)現(xiàn)和發(fā)展了許多操作DNA的方法，同時(shí)也發(fā)現(xiàn)了DNA計(jì)算具有某些電子計(jì)算機(jī)無(wú)可比擬和替代的優(yōu)越性。密碼學(xué)和遺傳學(xué)原本是毫不相關(guān)的兩個(gè)學(xué)科。然而，隨著現(xiàn)代科技的發(fā)展，近年來(lái)密碼學(xué)和DNA開(kāi)始走到了一起，并且關(guān)系越來(lái)越密切。

1994年美國(guó)南加州大學(xué)的Adleman[1]成功地完成了用DNA計(jì)算來(lái)解決一個(gè)NP完全問(wèn)題的實(shí)驗(yàn)，從而開(kāi)創(chuàng)了DNA計(jì)算研究的新紀(jì)元。自此以后，越來(lái)越多的目光集中到對(duì)這門(mén)新興學(xué)科的研究上來(lái)，其中包括了不少計(jì)算機(jī)專(zhuān)家和密碼學(xué)界的知名人士，他們開(kāi)始關(guān)注DNA計(jì)算對(duì)密碼學(xué)及信息安全的影響，開(kāi)始思考能否在DNA的領(lǐng)域里開(kāi)辟密碼的新天地。

1 DNA密碼

DNA密碼是新生的密碼技術(shù)，是傳統(tǒng)密碼技術(shù)的潛在替代途徑之一，其特點(diǎn)是以DNA為信息載體，以現(xiàn)代生物學(xué)技術(shù)為實(shí)現(xiàn)工具，挖掘DNA固有的高存儲(chǔ)密度、高并行性等優(yōu)點(diǎn)，實(shí)現(xiàn)加密、認(rèn)證、簽名等密碼學(xué)功能。

1.1 DNA隱寫(xiě)術(shù)

隱寫(xiě)術(shù)是將通常未加密的文本或者圖形完全地隱藏在其它的通過(guò)電子傳輸?shù)奈谋净蛘邎D形中的一種加密方式。15世紀(jì)人們就提出了撘詞鯏，隨后隱寫(xiě)術(shù)就大量出現(xiàn)在各種保密通信中。在隱寫(xiě)術(shù)加密中，攜帶秘密信息的載體的數(shù)量越大，攻擊者從這些載體中恢復(fù)出秘密信息的難度就越大。因此，為了提高隱寫(xiě)術(shù)的安全性，需要大量的高密度的載體，而DNA的特性正好符合這一要求。1999年，Celland等人在“Nature”雜志發(fā)表論文[2]，他們把著名的“June 6 Invasion：Normandy”隱藏在DNA微點(diǎn)中，提出了世界上第一個(gè)利用DNA實(shí)現(xiàn)信息保密的方法。信息寫(xiě)入的方式是合成具有特定引物的DNA序列，解密的方式是利用PCR擴(kuò)增之后測(cè)序。

經(jīng)過(guò)多年的研究，DNA隱寫(xiě)術(shù)可以分成兩種加密方式[3]。

第一種是明文串的加密，將明文串與其它DNA串混合在一起進(jìn)行加密，這樣能夠防止通過(guò)排序讀出明文串。其它的這些DNA分子串，稱(chēng)做偽串。為了確保該方法的安全性，偽串應(yīng)該同消息串具有相同的組成形式。解密的時(shí)候需要確認(rèn)附著在明文消息上的唯一的識(shí)別序列(即密鑰序列)。這個(gè)序列可以在串的終端，正常情況下位于起始序列的位置。因此，解密時(shí)通過(guò)使用相應(yīng)的密鑰序列作為PCR反應(yīng)的引物來(lái)讀出明文消息。這種技術(shù)的安全性需要保證偽串的隨機(jī)性或者使得所有的DNA串的出現(xiàn)具有相同的頻率。

第二種加密技術(shù)是圖形明文的加密，是將明文串和大量的包含相同密鑰序列的偽串混合加密。在這種方式下，密鑰序列再也不具有用作解密過(guò)程的唯一特性。取而代之，解密的密鑰是加密使用的整個(gè)偽串池。通過(guò)讀出偽串池和加密池(包括偽串池和明文串)可以生成兩個(gè)不同的凝膠成像圖。再通過(guò)數(shù)字圖像的處理技術(shù)，對(duì)這兩個(gè)凝膠成像圖作圖形化的相減處理，就能得到原始的明文串的序列。

圖形解密可以被視為一個(gè)獨(dú)立的密碼系統(tǒng)。如果作為密鑰的偽串池只使用一次，這個(gè)系統(tǒng)同第一種方式一樣安全。但是，如果多次使用同一個(gè)偽串池，攻擊者就會(huì)通過(guò)對(duì)所有的凝膠成像圖進(jìn)行數(shù)字圖像處理獲得越來(lái)越多的密鑰消息。

1.2 DNA密碼系統(tǒng)

目前利用DNA本身的特性構(gòu)建的密碼系統(tǒng)大致分為兩種方式，一種是采用DNA數(shù)據(jù)庫(kù)作為密碼本構(gòu)建一次一密的DNA密碼系統(tǒng)[4]，另一種是利用生物學(xué)中的困難問(wèn)題構(gòu)建全新的DNA密碼系統(tǒng)。

(1)使用替代的一次一密系統(tǒng)

一個(gè)替代的一次一密系統(tǒng)是使用一個(gè)明文二進(jìn)制消息和一張隨機(jī)映射到密文的表。輸入的長(zhǎng)度為n的DNA串被分割成為具有固定長(zhǎng)度的明文串。表的作用就是將所有具有固定長(zhǎng)度的可能的明文串映射到相對(duì)應(yīng)的密文串，而且使得其逆映射唯一。加密是將每個(gè)明文DNA字替換成相對(duì)應(yīng)的DNA密文字。這種映射是通過(guò)使用一個(gè)包含了許多片斷的長(zhǎng)的DNA密碼本來(lái)實(shí)現(xiàn)的。其中，每個(gè)片斷都代表了一個(gè)單獨(dú)的明文字同密文字的映射。明文字是作為綁結(jié)引物的雜交點(diǎn)，接著被擴(kuò)展生成明密文字對(duì)。然后分離明密文字對(duì)，刪除明文部分得到密文消息。一個(gè)理想的一次一密庫(kù)應(yīng)該包含大量的一次一密本，能夠提供從明文字到密文字的具有良好的唯一性、隨機(jī)性的映射。

(2)使用異或的一次一密系統(tǒng)

Vernam 密碼是使用R個(gè)均一分布的隨機(jī)比特構(gòu)成的序列S作為一次一密本。S的一個(gè)副本保存在發(fā)送者和接收者處。L為S的還沒(méi)有用于加密消息的比特?cái)?shù)目。初始的L=R。兩個(gè)二進(jìn)制輸入的異或操作是當(dāng)它們相同時(shí)值為0，否則值為1。當(dāng)發(fā)送一個(gè)長(zhǎng)度為n

為了用DNA實(shí)現(xiàn)這個(gè)算法，需要完成明文消息的加密、一次一密本的創(chuàng)建和DNA的異或操作的方法。目前，用DNA實(shí)現(xiàn)二進(jìn)制加法和異或已經(jīng)有很多方法。在許多相關(guān)文獻(xiàn)中，先后涉及到比特加法，并行操作以及DNA瓦狀結(jié)構(gòu)。

(3)基于生物困難問(wèn)題的密碼系統(tǒng)

該系統(tǒng)由盧明欣、來(lái)學(xué)嘉等人提出在[5,6]，依賴(lài)于一個(gè)生物學(xué)困難問(wèn)題：對(duì)DNA 芯片(微陣列)上僅核苷酸排列不同的未知混合DNA(PNA)探針的信息進(jìn)行完全精確測(cè)序破譯是困難的。這意味著攻擊者不僅要知道芯片上每個(gè)點(diǎn)中DNA 探針的種類(lèi), 而且要知道每一種探針的準(zhǔn)確數(shù)量。在此基礎(chǔ)上構(gòu)建了兩種算法：基于DNA技術(shù)的對(duì)稱(chēng)加密算法(DNASC)和基于DNA技術(shù)的非對(duì)稱(chēng)加密算法(DNA-PKC)。由于DNA密碼使用DNA鏈或DNA芯片作為存儲(chǔ)媒介，基于DNA的高存儲(chǔ)密度，DNA密碼在構(gòu)造對(duì)數(shù)據(jù)存儲(chǔ)容量有需求的安全體制時(shí)，相對(duì)傳統(tǒng)密碼將具有明顯優(yōu)勢(shì)。同時(shí)，由于該密碼系統(tǒng)依賴(lài)于生物學(xué)困難問(wèn)題，這又提供了另一種安全保障機(jī)制，其對(duì)量子計(jì)算機(jī)等超級(jí)計(jì)算機(jī)的攻擊是免疫的。

1.3 DNA與認(rèn)證

現(xiàn)在，DNA分子較為廣泛地應(yīng)用在認(rèn)證領(lǐng)域，生物認(rèn)證技術(shù)也經(jīng)歷了一個(gè)突飛猛進(jìn)的發(fā)展過(guò)程，這也是DNA隱寫(xiě)術(shù)的一個(gè)應(yīng)用?，F(xiàn)代分子技術(shù)將DNA串植入不同的物質(zhì)和材料，作為防偽標(biāo)記的手段。近年在國(guó)內(nèi)外就有利用DNA做為密碼防偽的報(bào)告并有DNA加密墨水推出，用于簽名。臺(tái)灣發(fā)明了世界上第一臺(tái)DNA認(rèn)證的芯片，通過(guò)類(lèi)似于身份卡和信用卡的讀卡器來(lái)識(shí)別，芯片內(nèi)部合成的DNA能夠生成只有公司成員才能夠察覺(jué)和識(shí)別的DNA信號(hào)。這些日新月異的技術(shù)發(fā)展，讓人更清晰地意識(shí)到DNA生物分子技術(shù)的潛力，為進(jìn)一步的推廣應(yīng)用奠定了基礎(chǔ)。

2 DNA計(jì)算應(yīng)用

DNA計(jì)算首先起源于1994年Adleman的開(kāi)創(chuàng)性工作，他利用實(shí)驗(yàn)證實(shí)了作為承載生命遺傳密碼的DNA雙螺旋分子可以用來(lái)實(shí)現(xiàn)計(jì)算。利用DNA計(jì)算具有大存儲(chǔ)量、低能量消耗及高度的并行性的特點(diǎn)，結(jié)合信息安全的要求，專(zhuān)家們提出了其在信息技術(shù)領(lǐng)域的很多應(yīng)用。

2.1 DNA計(jì)算解決NP完全問(wèn)題

眾所周知，現(xiàn)代密碼學(xué)里面涉及的一個(gè)重要的部分是對(duì)NP完全問(wèn)題的研究和解決，歷來(lái)就成為眾多學(xué)者研究討論的熱點(diǎn)和難點(diǎn)。1994年，美國(guó)的Adleman博士在實(shí)驗(yàn)室里成功地用現(xiàn)代分子生物技術(shù)，即DNA計(jì)算的方法解決了一個(gè)著名的NP完全問(wèn)題——哈密爾頓路徑問(wèn)題(HPP)。他花費(fèi)了近一個(gè)星期的時(shí)間，對(duì)七個(gè)頂點(diǎn)的HPP作了仿真實(shí)驗(yàn)并且得到了正確的結(jié)果，如圖1所示。

圖1 七個(gè)節(jié)點(diǎn)的有向圖

Adleman的實(shí)現(xiàn)步驟大致如下：

(1)對(duì)各個(gè)頂點(diǎn)、有向邊進(jìn)行DNA編碼，建立數(shù)據(jù)池；

(2)搜索出所有表示從頂點(diǎn)0開(kāi)始到頂點(diǎn)6結(jié)束的路徑的DNA編碼串；

(3)在上一步的基礎(chǔ)上，搜索出具有6個(gè)邊的路徑集(按DNA鏈的長(zhǎng)度分離)；

(4)再依次從各個(gè)頂點(diǎn)搜索，找出不重復(fù)邊的路徑集；

(5)通過(guò)電泳分離，找出符合條件的路徑，即是問(wèn)題的解；

采用類(lèi)似的方法，學(xué)者和專(zhuān)家們拓展了思路，先后解決了更多的NP完全問(wèn)題。例如，1995年Lipton解決了可滿(mǎn)足性問(wèn)題；1997年，Ouyang等人解決了最大團(tuán)問(wèn)題。他們用DNA分子計(jì)算技術(shù)解決諸如此類(lèi)NP問(wèn)題有一個(gè)總體的思想，就是首先建立一個(gè)解空間的數(shù)據(jù)池，然后用窮舉搜索的方法，充分利用了生物計(jì)算的巨大并行性，逐步篩選，最后找出問(wèn)題的解。

2.2 基于DNA技術(shù)的密碼分析

DES(數(shù)據(jù)加密標(biāo)準(zhǔn))是迄今為止世界上最為廣泛使用和流行的一種分組密碼算法，其對(duì)于推動(dòng)密碼理論的發(fā)展和應(yīng)用起了不可忽視的作用，對(duì)于掌握分組密碼的基本理論、設(shè)計(jì)思想及實(shí)際應(yīng)用仍然有著重要的參考價(jià)值。

1996年，Adleman等人提出了用DNA計(jì)算來(lái)破譯DES的一種新思想[7]，將人們的眼光真真正正地吸引到利用分子計(jì)算機(jī)無(wú)可比擬的優(yōu)越性來(lái)分析和破譯現(xiàn)代的密碼體制上來(lái)。用DNA計(jì)算的方法破譯DES的總體思想是：給定一個(gè)明密文對(duì)(M0，E0)，攻擊者Eve的目的就是找到唯一的k0，使得k0能夠?qū)⒚魑腗0映射成為密文E0。首先定義如下的函數(shù)：g(k)=DES(M0，k0)，其中DES()表示DES加密的過(guò)程。函數(shù)g(k)將一個(gè)56比特的密鑰映射成為64 bit的密文，Eve就是想尋找滿(mǎn)足g(k)=E0的k。用DNA分子來(lái)實(shí)現(xiàn)，則需要建立一個(gè)數(shù)據(jù)池Tg，使得Tg包含所有的代表256種可能的密文值對(duì)[k，DES(M0，k)]的DNA分子。然后通過(guò)提取使得DES(M0，k)=E0的分子找出相應(yīng)的k值。

在整個(gè)過(guò)程中，最耗時(shí)耗力的部分是對(duì)溶液Tg的建立，這一步驟在實(shí)驗(yàn)室里大約需要4周的工作。但是一旦Tg建立以后，Eve就可以迅速地破譯該密碼系統(tǒng)。一般來(lái)說(shuō)，一升水最多可以容納1017個(gè)DNA分子。由于256<1017，可以看出在一升水中就可以完成上面的計(jì)算。如果是選擇明文攻擊，則Eve可以在一天內(nèi)就破譯DES。

對(duì)DES的破譯方法同樣適用于其它密鑰長(zhǎng)度小于64比特的密碼系統(tǒng)。一旦分子計(jì)算機(jī)取代傳統(tǒng)的電子計(jì)算機(jī)，現(xiàn)有的許多密碼系統(tǒng)都面臨著破譯的危險(xiǎn)。

2.3 DNA計(jì)算機(jī)

DNA計(jì)算機(jī)的設(shè)想是從Adleman的實(shí)驗(yàn)開(kāi)始的，生物計(jì)算機(jī)目前尚處在理論和實(shí)驗(yàn)研究階段，生物與數(shù)學(xué)的一些相似性使人們意識(shí)到可以利用生物過(guò)程來(lái)模擬數(shù)學(xué)過(guò)程，更確切地說(shuō)是，DNA鏈可用于表示信息，酶可用于模擬簡(jiǎn)單的運(yùn)算。這種分子作為一種超級(jí)計(jì)算機(jī)裝置的吸引力在于其已經(jīng)得到證實(shí)的存儲(chǔ)大量信息的能力——事實(shí)上復(fù)制生命所需的全部指令都存儲(chǔ)在DNA中。盡管這種化學(xué)物質(zhì)不會(huì)在短期內(nèi)取代個(gè)人計(jì)算機(jī)，但是科學(xué)家們已經(jīng)有不少研究成果證明這些滿(mǎn)載信息的分子可以通過(guò)怎樣的方式在未來(lái)的計(jì)算機(jī)中執(zhí)行計(jì)算任務(wù)[8，9]。和普通計(jì)算機(jī)比，其優(yōu)點(diǎn)是體積小，但存儲(chǔ)的信息量卻很大，1 g DNA所能存儲(chǔ)的信息量可與1萬(wàn)億張CD光盤(pán)相當(dāng)，遠(yuǎn)大于現(xiàn)有的計(jì)算機(jī)存儲(chǔ)芯片和其他存儲(chǔ)介質(zhì)[10]。雖然DNA計(jì)算機(jī)尚有一些技術(shù)問(wèn)題沒(méi)有解決，但已成為未來(lái)的可替代電子計(jì)算機(jī)技術(shù)的一種可選方案，有著廣闊的發(fā)展前景。

2.4 DNA與軟計(jì)算

軟計(jì)算主要包括模糊邏輯推理、神經(jīng)網(wǎng)絡(luò)理論、概率推理、遺傳算法、混沌系統(tǒng)和人工免疫系統(tǒng)等，這些計(jì)算智能技術(shù)一直是當(dāng)前智能科學(xué)領(lǐng)域的研究熱點(diǎn)，且已被廣泛應(yīng)用于各個(gè)領(lǐng)域，包括信息安全領(lǐng)域。目前，軟計(jì)算中智能技術(shù)的理論研究只是對(duì)生物系統(tǒng)的簡(jiǎn)單模擬，專(zhuān)家們近年來(lái)開(kāi)始研究基于DNA在遺傳處理系統(tǒng)中的控制作用，開(kāi)發(fā)新型的基于人工DNA模型的計(jì)算智能來(lái)解決一些科學(xué)與實(shí)踐的問(wèn)題。如一些學(xué)者提出了基于DNA機(jī)理的改進(jìn)的遺傳算法、基于DNA編碼方法的遺傳算法及用于搜索DNA進(jìn)化計(jì)算中好的DNA譯碼算法等。

3 結(jié)語(yǔ)和展望

關(guān)于DNA計(jì)算的研究目前已經(jīng)取得了不少令人興奮的成果，在國(guó)際上掀起了一場(chǎng)DNA計(jì)算的熱潮。人們對(duì)DNA計(jì)算的前景充滿(mǎn)信心，而密碼學(xué)領(lǐng)域里越來(lái)越多的學(xué)者和專(zhuān)家也投入到DNA計(jì)算的研究中來(lái)。一方面，他們充分分析了分子計(jì)算這種工具的優(yōu)越性和對(duì)現(xiàn)行密碼體制的影響，考慮了如何利用這種工具去改進(jìn)和更新現(xiàn)行的密碼體制。另一方面，也發(fā)掘了全新的DNA 密碼，使其在應(yīng)用協(xié)議與安全性方面都和傳統(tǒng)密碼體制有很大不同。對(duì)未來(lái)的DNA密碼和DNA計(jì)算在信息安全領(lǐng)域中的應(yīng)用大致可以在如下的方向發(fā)展：

(1)繼續(xù)探索其它新的DNA計(jì)算及模型，探索用DNA計(jì)算解決其它NP完全問(wèn)題的新方法；

(2)研究DNA算法對(duì)現(xiàn)有公鑰密碼和公鑰技術(shù)的影響；

(3)分析在DNA計(jì)算條件下現(xiàn)行密碼算法的新的安全度量指標(biāo)，研究DNA計(jì)算對(duì)部分密碼系統(tǒng)的有效攻擊和破譯方法；

(4)繼續(xù)深化DNA隱寫(xiě)術(shù)的加解密的方法，拓寬其推廣應(yīng)用的局面；

(5)探索DNA計(jì)算與各種軟科學(xué)的結(jié)合和集成，例如與混沌數(shù)字水印技術(shù)的組合認(rèn)證，可以大大增強(qiáng)敏感信息的安全性，從而有效的保護(hù)數(shù)字化信息產(chǎn)品;

(6)開(kāi)發(fā)適合于生物分子計(jì)算的求解工具和程序，將DNA計(jì)算模型化，研制出可以利用的DNA計(jì)算的芯片;

(7)以開(kāi)發(fā)能抗量子計(jì)算和生物計(jì)算的新密碼為目標(biāo)，進(jìn)一步分析和研究DNA密碼的構(gòu)建方式，探討更安全更高效的密碼新模型。

總之，雖然DNA密碼和DNA計(jì)算在信息安全中的應(yīng)用仍處于起步階段，但是其巨大的發(fā)展?jié)摿蛷V闊的應(yīng)用前景已經(jīng)逐漸顯現(xiàn)出來(lái)，等待著人們更加深入地研究和探索。

[1] ADLEMAN L M.Molecular Computation of Solutions to Combinatorial Problems[J].Science,1994，266(11):1 021-1 024.

[2] CLELLAND C T,RISCA V,BANCROFT C.Hiding Messages in DNA Microdots[J].Nature,1999,399:533-534.

[3] LEIER A,RICHTER C,BANZHAFW,RAUHEH.Cryptography with DNA binary strands[B].Biosystems,2000,57(1):13-22.

[4] GEHANI A,LABEAN T H,REIF J H.1999.DNA-based Cryptography[Z].5th DIMACS Workshop on DNA Based Computers,MIT,June,1999.

[5] 盧明欣，來(lái)學(xué)嘉，肖國(guó)鎮(zhèn)，等.基于DNA 技術(shù)的對(duì)稱(chēng)加密方法[J].中國(guó)科學(xué)，2007，37(2)：175-182.

[6] 來(lái)學(xué)嘉，盧明欣，秦磊，等.基于DNA技術(shù)的非對(duì)稱(chēng)加密與簽名方法[J].中國(guó)科學(xué)，2010，40(2)：240-248.

[7] Dan Boneh,Christopher Dunworth,Richard J Lipton.Breaking DES Using a molecular computer[M]//DNA Based Computers,volume 27 of DIMACS:Series in Discrete Mathematics and Theoretical Computer Science，American Mathematical Society,1996.

[8] VAN N D,LANDWEBER L F.TOWARDS A Re-Programmable DNA Computer[J]J.of Natural Computing，2005，4(2)：163-175.

[9] 丁永生，李汪根，任立紅.基于生物芯片的DNA計(jì)算——模型、算法及應(yīng)用[M].北京：科學(xué)出版社，2011.

[10] SEIFE C.What are the limits of conventional computing?[J].Science,2005,309:96.