生物密碼系統(tǒng)及面向密碼學(xué)問題的DNA計算研究.pdf

1、自Adleman在1994年首次提出了哈密爾頓路徑問題的DNA算法以來， DNA計算作為一種新型計算方法，目前在理論和實踐方面取得了若干初步成就。利用DNA反應(yīng)本質(zhì)的并行特性，DNA計算表現(xiàn)出巨大的并行運(yùn)算能力，在未來有很大的發(fā)展空間。
　　隨著DNA計算的發(fā)展，生物密碼體制亦成為密碼學(xué)研究的新領(lǐng)域。當(dāng)前傳統(tǒng)密碼體制的安全性多基于計算困難問題，如整數(shù)分解問題和離散對數(shù)問題，若在未來可找到這些問題的有效計算方法，相關(guān)密碼體制的安全性

2、將受到巨大威脅。而生物密碼體制安全性并不依賴于計算困難問題，因此并不受計算能力發(fā)展的影響，故而可作為傳統(tǒng)密碼體制的補(bǔ)充。
　　本文研究內(nèi)容分為兩方面，一是面向密碼學(xué)問題的DNA計算研究。離散對數(shù)問題在現(xiàn)代密碼學(xué)中扮演重要角色。Di?e-Hellman密鑰交換、ElGamal類加密和簽名等密碼體制的安全性都基于離散對數(shù)問題的計算困難性，若該問題在未來被攻破，則依賴該問題的密碼體制安全性都將受到威脅。我們利用DNA計算的并行運(yùn)算能力，

3、以Tile自組裝DNA計算模型為工具，設(shè)計離散對數(shù)問題的多項式時間DNA算法。同時，在相關(guān)子系統(tǒng)的設(shè)計上，比前人的方法有一定優(yōu)化。具體研究成果及創(chuàng)新性如下：
　　1-首次給出Tile自組裝模型下多項式時間非確定性離散對數(shù)算法。算法非確定性隨機(jī)選擇指數(shù)x，并行地計算ax mod p，并與y進(jìn)行比較，求解滿足ax≡y(mod p)的x。對于np位模數(shù)p，系統(tǒng)組裝時間為O(n3p)。此前的方法系統(tǒng)組裝時間為指數(shù)時間O(2np)，相比較之

4、下，本文的方法在組裝時間上有顯著改進(jìn)。
　　2-給出兩個Tile自組裝模型下乘法系統(tǒng)新的實現(xiàn)，系統(tǒng)所需Tile大小分別為24與16。相比起此前Brun提出的Tile集大小為28的乘法系統(tǒng)，本文提出的系統(tǒng)在Tile集大小上有所優(yōu)化。
　　3-首次給出Tile自組裝模型下直接求模運(yùn)算的系統(tǒng)：給定nA、nB位大小的整數(shù)A與B，系統(tǒng)直接計算A mod B。最壞情況組裝時間為Θ(nA(nA?nB))，最好情況組裝時間為Θ(nA)。相比

5、起此前用除法求余數(shù)的方法，本文所提出系統(tǒng)在組裝時間上有所優(yōu)化。當(dāng)nA遠(yuǎn)大于nB時，本系統(tǒng)的優(yōu)勢較為明顯。
　　4-針對此前的乘法系統(tǒng)無法在其他子系統(tǒng)最終配置上直接運(yùn)行的瓶頸，本文給出一種可在其他運(yùn)算模塊結(jié)果上進(jìn)行連續(xù)運(yùn)算的平方系統(tǒng)。故而在整個運(yùn)算過程中，無需中斷自組裝反應(yīng)便可進(jìn)行平方運(yùn)算。
　　5-此外，本文提出一種線性自組裝模減法算法，算法中實驗步驟為常數(shù)步。
　　本文研究工作的第二部分面向生物密碼體制。針對基于DN

6、A芯片的密碼體制進(jìn)行研究，探索其區(qū)別于傳統(tǒng)密碼體制的特殊性質(zhì)，并利用特殊性質(zhì)實現(xiàn)相關(guān)應(yīng)用。具體研究成果如下：
　　1-首次實現(xiàn)基于DNA芯片的公鑰密碼體制DNA-PKC并以實驗驗證。其安全性基于生物學(xué)困難問題“獲取DNA芯片微點上長度相同混合探針的精確信息困難”，并不獨依賴于計算困難問題，相比起傳統(tǒng)體制提供了另一層安全性。同時給出其特殊性質(zhì)“加解密鑰具有多對多關(guān)系”。
　　2-圍繞“加解密鑰具有多對多關(guān)系”這條特殊性質(zhì)展開，

7、首次給出基于DNA芯片的動態(tài)廣播加密方案DNA-DBE。相比起傳統(tǒng)廣播加密方案，DNA-DBE的優(yōu)勢在于密文和解密鑰的復(fù)雜度皆為常數(shù)，與用戶數(shù)無關(guān)。且具有后向安全性。
　　3-引出新性質(zhì)“不同的明文消息可以對應(yīng)相同的密文”，首次給出基于DNA芯片的信息隱藏方案DNA-IH。傳統(tǒng)信息隱藏方案中隱密消息嵌入載體后，將引起載體特征統(tǒng)計分布的變化。而DNA-IH中普通消息所對應(yīng)的芯片與嵌入隱密消息后所對應(yīng)的芯片完全一致，因而無法通過統(tǒng)計攻