基于DNA計(jì)算自組裝模型的若干密碼問(wèn)題研究.pdf

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

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

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

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

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

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

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

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

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