DNA計(jì)算在密碼學(xué)上的應(yīng)用

《DNA計(jì)算在密碼學(xué)上的應(yīng)用》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、effectininformationfieldinthefuture．摘要Keyword：DNAcomputation；cryptology；knapsackproblem；dichotomy獨(dú)創(chuàng)性聲明本人聲明所呈交的論文是我個人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得北京工業(yè)大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書而使用過的材料。與我～同工作的同志對本研究所做的任何貢獻(xiàn)均已在論文中作了明確的說明并表示了謝意。簽名蛆同期：彬．，關(guān)于論文使用授權(quán)的說明本人完全了解北京工業(yè)大

2、學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留送交論文的復(fù)印件，允許論文被查閱和借閱；學(xué)校可以公布論文的全部或部分內(nèi)容，可以采用影印、縮印或其他復(fù)制手段保存論文。(保密的論文在解密后應(yīng)遵守此規(guī)定)躲塑恥翩虢仫經(jīng)同期醴絲夕第l章緒論第1章緒論1。1DNA計(jì)算的發(fā)展以及研究現(xiàn)狀隨著現(xiàn)代計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展，人們一直在追求一種計(jì)算速度更快、體積更小的計(jì)算機(jī)。1956年，理查德·馮紐曼就曾經(jīng)充滿幻想的描述了構(gòu)建一臺“亞顯微”計(jì)算機(jī)的可能性。目前，盡管計(jì)算機(jī)在提高計(jì)算的速度、容量和性能上已經(jīng)取得了巨大的進(jìn)步，但“亞顯微”計(jì)算機(jī)的目標(biāo)還遠(yuǎn)遠(yuǎn)沒有實(shí)現(xiàn)，不少計(jì)算科學(xué)的研究者難在這些方面

3、進(jìn)行著不懈的努力，并取得了一些初步的成果，影響了計(jì)算科學(xué)的發(fā)展。1994年，美國南加州大學(xué)的Adleman教授在Science上發(fā)表了第一篇DNA計(jì)算的論文【Il，解決了NP問題的一有向哈密頓路徑問題，開創(chuàng)了計(jì)算科學(xué)的一個新領(lǐng)域。DNA計(jì)算的研究屬于生物、化學(xué)、數(shù)學(xué)等學(xué)科的一個交叉領(lǐng)域，其研究內(nèi)容所涉及的范圍很廣。很快DNA計(jì)算吸引了大量的計(jì)算機(jī)、數(shù)學(xué)、生物學(xué)以及化學(xué)研究者的目光，越來越多的研究者投身到這一研究領(lǐng)域中。在Adleman等人的工作的基礎(chǔ)上，最近幾年里在這門學(xué)科上不斷出現(xiàn)許多創(chuàng)新成果，人們正逐漸發(fā)現(xiàn)DNA計(jì)算的內(nèi)在規(guī)則，創(chuàng)造出一些DNA計(jì)算的方法和模型。DNA

4、計(jì)算的～些代數(shù)運(yùn)算、基于表面的DNA計(jì)算以及DNA自裝配計(jì)算等方法可用于在理論上解決一些圖論、網(wǎng)絡(luò)、優(yōu)化以及密碼等問題。邏輯和算術(shù)運(yùn)算是DNA計(jì)算中一個很重要性的研究問題，1995年，Beaver提出了用DNA分子插入和缺失的方法[401，來實(shí)現(xiàn)DNA計(jì)算機(jī)的邏輯和算術(shù)運(yùn)算[4”。96年Guamieril6j等人實(shí)現(xiàn)了用DNA計(jì)算來作加法。1999年，JohnS．Olilver提出了矩陣乘法的DNA計(jì)算方法【7’叭。后來Boneh等人用動態(tài)規(guī)劃方法解決了圖可達(dá)性的背包問題f91；Leete等人解決了符號決定性問題1101；N。Jonoska等人解決了道路染色問題?l；以及

5、超標(biāo)量計(jì)算機(jī)代數(shù)問題【121等等。在神經(jīng)網(wǎng)絡(luò)方面，貝爾實(shí)驗(yàn)室的A．P．Mills，Jr．B．Yurke，PM．Platzman．提出了模擬神經(jīng)網(wǎng)絡(luò)模型的DNA計(jì)算方法1131。DNA計(jì)算的表面基方法1421是在1996年提出的，它的優(yōu)越性在于能夠方便地實(shí)現(xiàn)自動操作。2000年Nature刊載了Qin曲uaLiu的文章㈣，標(biāo)志著表面上的DNA計(jì)算正在逐步完善，現(xiàn)在DNA計(jì)算的表面基方法越來越得到廣泛的應(yīng)用。北京J=業(yè)大學(xué)理學(xué)碩士學(xué)位論文DNA自裝配計(jì)算方法是DNA計(jì)算的一種重要方法，Winfree對DNA自裝配計(jì)算的發(fā)展作出了重要貢獻(xiàn)，他的關(guān)于二維DNA格的設(shè)計(jì)和自裝配的論

6、文12】奠定了自裝配計(jì)算方法的基礎(chǔ)，后來自裝配計(jì)算成為DNA計(jì)算一個重要的計(jì)算方法，ChengdeMao等人的論文用DNA三螺旋分子的自裝配來實(shí)現(xiàn)加法和邏輯異或運(yùn)算【3l'AshishGehani和tHLabean等人把這種方法用于密碼學(xué)領(lǐng)域，提出了一種基于一次性密碼本的DNA加密和解密方法【4l。日本的KensakuSakamoto等人提出的發(fā)卡狀計(jì)算模型解決可滿足性問題【5】，也是建立在分子自裝配的基礎(chǔ)上的。由于DNA計(jì)算的高度并行性和DNA的密集的儲存信息的能力，這使得DNA計(jì)算非常適合解決密碼問題，Lipton和DanBoneh最早在這一領(lǐng)域進(jìn)行了研究，96年他們

7、給出了使用分子計(jì)算機(jī)破譯DES的方法[341，在此基礎(chǔ)上Adleman等人又給出了使用sticker模型破譯DES的方法【361，AshishGehani和T．H．Labean等人提出了一種基于一次性密碼本的DNA加密和解密方法14I，此外AndreLeier等人還給出了使用DNA二進(jìn)制串進(jìn)行加密和解密的方法【4"。DNA計(jì)算在密碼學(xué)上的應(yīng)用必然對信息領(lǐng)域的發(fā)展產(chǎn)生巨大影響。我們也把目光投向了密碼學(xué)上背包公鑰密碼體制中背包密碼的破譯問題，并且找到了兩種解決背包問題的有效算法，特別是二分法能較好地降低計(jì)算的時(shí)間和空間復(fù)雜度。DN