基于DNA計算自組裝模型的若干密碼問題研究.pdf

1、密碼分析和密碼設計是信息安全領域最重要的組成部分，它的發(fā)展關(guān)系到國家安全、經(jīng)濟安全和金融安全等多個方面?，F(xiàn)代密碼系統(tǒng)的安全性是建立在密鑰搜索的指數(shù)增長時間復雜度上，而新興的DNA計算具有超大規(guī)模并行性、高密度存儲和低能耗等特性，不僅對傳統(tǒng)密碼安全提出了挑戰(zhàn)，同時也為海量信息存儲提供了新的存儲和加密模式。實驗已經(jīng)證明DNA分子自組裝是一種自底向上進行納米尺度計算的有效機制。1維和2維的自組裝作為。DNA計算的工具，其并行計算能力已經(jīng)得到認

2、可，并得到了大量的研究。已經(jīng)證明1維線性自組裝具有正則語言的計算能力，而二維自組裝的計算能力是圖靈等價的。
　　 基于這樣的背景，本文以DNA計算中的Tile字組裝模型為核心，密碼問題為主要研究對象，對DNA計算Tile自組裝模型在密碼中的各種應用及其有效性進行了探索研究，設計并實現(xiàn)了基于。DNA計算Tile自組裝的密碼系統(tǒng)和密碼算法破譯模型，定量分析了DNA計算用于密碼分析和數(shù)據(jù)加密的有效性、時間復雜度、空間復雜度。
　

3、　 本文主要創(chuàng)新內(nèi)容如下：
　　 首先，實現(xiàn)了基于DNA計算的一次一密密碼系統(tǒng)。本文針對DNA計算的并行性和海量存儲能力，使用DNA計算中的Tile自組裝模型設計實現(xiàn)一次一密密碼系統(tǒng)，為海量數(shù)據(jù)信息的加密存儲和傳輸提供了新的方法。該密碼系統(tǒng)包括加密子系統(tǒng)、密文提取子系統(tǒng)、密鑰計算子系統(tǒng)和解密子系統(tǒng)，這四個子系統(tǒng)組成了一個完整的密碼系統(tǒng)。同時使用已有的生物技術(shù)，實現(xiàn)了秘密密鑰的安全傳輸。所有的子系統(tǒng)的Tile類型復雜度為(I)(

4、1)，計算時間復雜度為(I)(n)。最后，對該一次一密密碼系統(tǒng)的安全性進行了分析，表明基于Tile模型和生物技術(shù)實現(xiàn)的密碼系統(tǒng)可以保證海量數(shù)據(jù)的存儲和傳輸安全。
　　 第二，基于自組裝模型的編程能力，設計了使用自組裝模型破譯Diffie-Hellman算法的方法。首先根據(jù)g modp，g2 mod p,…，gp-1 mod p得到的整數(shù)值構(gòu)建計算Tile，完成整數(shù)排列的自組裝Tile系統(tǒng)。這里p為素數(shù)，g為這個素數(shù)的原根。通過P

5、CR和凝膠電泳，可以讀出不同的整數(shù)對應的g的冪次，即g的離散對數(shù)值。通過這樣的方法，可以威脅到Diffie-Hellman密鑰交換的安全。整個系統(tǒng)使用(I)(p)種Tile類型和(I)(p)的組裝時間來完成整數(shù)的排列。這個模型對于有限位數(shù)的Difile-Hellman算法是有效的。但是由于Tile種類與輸入位數(shù)線性相關(guān)，因此限制了破譯Diffie-Hellman算法的規(guī)模。
　　 然后，本文利用DNA計算自組裝模型的封裝編程能力

6、，設計了除法自組裝模型，并且充分利用DNA計算分布式并行計算優(yōu)勢，在除法自組裝模型中嵌入除數(shù)生成系統(tǒng)，構(gòu)建了非確定性大數(shù)分解自組裝模型，用于解決大數(shù)分解問題。該模型的Tile種類復雜度為(I)(1)，時間復雜度為(I)(n2)。該DNA計算實驗允許至少1018個除法自組裝系統(tǒng)同時進行運算，這些除法系統(tǒng)具有相同的被除數(shù)，但是除數(shù)是系統(tǒng)隨機生成，各不相同。為解決除法完成后商的檢測問題，在非確定性大數(shù)分解自組裝模型中嵌入了判別余數(shù)是否為零的判

7、斷系統(tǒng)，該系統(tǒng)能夠在大量結(jié)果中標記出能夠整除被除數(shù)的除數(shù)，通過標記提取出對應的除數(shù)和商，完成大數(shù)分解。最后分析了這個非確定性自組裝Tile模型能成功搜索到目標除數(shù)的概率，并且證明了通過增大參加運算的DNA分子的量可以使該概率接近于1。以目前的生物技術(shù)，該模型完全可以解決256位的大數(shù)分解。
　　 進一步，利用自組裝自底向上的編程能力和封裝能力，設計實現(xiàn)了基于自組裝模型的DES和3DES加密算法。通過對DES算法中的輪函數(shù)，包括置

8、換、交換、異或等進行封裝和巧妙級聯(lián)，實現(xiàn)了輪函數(shù)的循環(huán)調(diào)用。為了可以使用已知明文-密文對攻擊的方法實現(xiàn)DES算法的破譯，在DES算法模型中嵌入了主密鑰生成系統(tǒng)，利用自組裝的并行計算能力可以同時隨機生成各不相同的主密鑰對已知明文進行加密。本文以簡化DES(SDES)作為模版，詳細解釋了各個函數(shù)的設計思想和方法，然后擴展到標準DES和3DES算法上。在已有的加密算法模型上，嵌入主密鑰生成系統(tǒng)，隨機生成主密鑰，利用DNA計算的并行性，使用已知

9、明文-密文攻擊方法破譯SDES、DES和3DES。最后分析了生物技術(shù)的誤差率與成功破譯DES和3DES加密算法的關(guān)系。從結(jié)果可以看到，隨著生物技術(shù)的進一步提高，誤差率的減小，自組裝模型完全可以使用已知明文一密文攻擊方法成功破譯DES和3DES算法。
　　 最后，利用DNA芯片并行計算和熒光顯像的特性，使用DNA生物芯片技術(shù)、雜交和酶切構(gòu)建了XOR函數(shù)，并且應用這個技術(shù)分析DES算法中S盒子的抗差分密碼分析能力。利用熒光圖像，可以