【摘要】：自Adleman在1994年首次提出了哈密爾頓路徑問題的DNA算法以來,DNA計算作為一種新型計算方法,目前在理論和實踐方面取得了若干初步成就。利用DNA反應(yīng)本質(zhì)的并行特性,DNA計算表現(xiàn)出巨大的并行運算能力,在未來有很大的發(fā)展空間。隨著DNA計算的發(fā)展,生物密碼體制亦成為密碼學(xué)研究的新領(lǐng)域。當(dāng)前傳統(tǒng)密碼體制的安全性多基于計算困難問題,如整數(shù)分解問題和離散對數(shù)問題,若在未來可找到這些問題的有效計算方法,相關(guān)密碼體制的安全性將受到巨大威脅。而生物密碼體制安全性并不依賴于計算困難問題,因此并不受計算能力發(fā)展的影響,故而可作為傳統(tǒng)密碼體制的補充。本文研究內(nèi)容分為兩方面,一是面向密碼學(xué)問題的DNA計算研究。離散對數(shù)問題在現(xiàn)代密碼學(xué)中扮演重要角色。Di?e-Hellman密鑰交換、El Gamal類加密和簽名等密碼體制的安全性都基于離散對數(shù)問題的計算困難性,若該問題在未來被攻破,則依賴該問題的密碼體制安全性都將受到威脅。我們利用DNA計算的并行運算能力,以Tile自組裝DNA計算模型為工具,設(shè)計離散對數(shù)問題的多項式時間DNA算法。同時,在相關(guān)子系統(tǒng)的設(shè)計上,比前人的方法有一定優(yōu)化。具體研究成果及創(chuàng)新性如下:1-首次給出Tile自組裝模型下多項式時間非確定性離散對數(shù)算法。算法非確定性隨機選擇指數(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),相比較之下,本文的方法在組裝時間上有顯著改進(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自組裝模型下直接求模運算的系統(tǒng):給定nA、nB位大小的整數(shù)A與B,系統(tǒng)直接計算A mod B。最壞情況組裝時間為Θ(nA(nA-nB)),最好情況組裝時間為Θ(nA)。相比起此前用除法求余數(shù)的方法,本文所提出系統(tǒng)在組裝時間上有所優(yōu)化。當(dāng)nA遠(yuǎn)大于nB時,本系統(tǒng)的優(yōu)勢較為明顯。4-針對此前的乘法系統(tǒng)無法在其他子系統(tǒng)最終配置上直接運行的瓶頸,本文給出一種可在其他運算模塊結(jié)果上進(jìn)行連續(xù)運算的平方系統(tǒng)。故而在整個運算過程中,無需中斷自組裝反應(yīng)便可進(jìn)行平方運算。5-此外,本文提出一種線性自組裝模減法算法,算法中實驗步驟為常數(shù)步。本文研究工作的第二部分面向生物密碼體制。針對基于DNA芯片的密碼體制進(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ì)展開,首次給出基于DNA芯片的動態(tài)廣播加密方案DNA-DBE。相比起傳統(tǒng)廣播加密方案,DNADBE的優(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)計攻擊等手段檢測隱秘消息的存在性。
[Abstract]:Since Adleman introduced the DNA algorithm of Hamilton path problem for the first time in 1994, DNA computation has been a new computational method, and some preliminary achievements have been made in theory and practice. With the parallel character of the nature of DNA reaction, DNA calculation shows great parallel operation ability, and has great development space in the future. With the development of DNA computation, the biological cryptographic system has become a new field of cryptography research. At present, the security of traditional cryptographic system is based on computational difficulty, such as integer decomposition and discrete logarithm problem. If these problems can be found effectively in the future, the security of relevant cryptographic system will be greatly threatened. However, the security of the bio-password system is not dependent on computational difficulty, so it is not affected by the development of computing power, so it can be used as a supplement to the traditional password system. The content of this paper is divided into two aspects, one is the research of DNA computation facing cryptography. Discrete logarithm problem plays an important role in modern cryptography. The security of the cryptographic system such as Di? e-Hellman key exchange, El Gamal encryption and signature, etc., is based on the discrete logarithm problem. If this problem is to be solved in the future, the security of the cryptographic system that depends on the problem will be threatened. We use the parallel computing capability of DNA computation to design the polynomial time DNA algorithm of discrete logarithm problem using the Tile self-assembled DNA computing model as the tool. At the same time, in the design of the relevant subsystem, it is better than the previous methods. The specific research results and innovations are as follows: 1-The discrete logarithm algorithm of polynomial time under the Tile self-assembly model is presented for the first time. The non-deterministic random selection index x of the algorithm is used to calculate ax mod p in parallel and compare with y to solve x. For np bit modulus p for np bit modulus p, the system assembly time is O (n3p). In this paper, the assembly time of the method system is exponential time O (2p). Compared with the prior method, the method of this paper is greatly improved during assembly time. The new implementation of the multiplication system under two Tile self-assembly models is presented. The tile size of the system is 24 and 16, respectively. Compared with the multiplication system with the Tile set size of 28, the system proposed in this paper is optimized in the Tile set size. 3-The system for directly seeking the modulo arithmetic under the Tile self-assembly model is given in this paper. The system directly calculates the A mod B. The worst-case assembly time is A mod. Compared with the previous method for dividing the remainder by division, the proposed system has been optimized for assembly time. The advantage of this system is more obvious when it is much larger than that of nB. 4-Aiming at the bottleneck that the previous multiplication system can't run directly on the final configuration of other subsystems, this paper presents a square system which can be operated continuously on the result of other arithmetic modules. Therefore, in the whole operation process, the square operation can be carried out without interruption of self-assembly reaction. 5-In addition, a linear self-assembly modulo subtraction algorithm is proposed in this paper. The second part of this paper is facing the system of biocryptosystems. This paper studies the cryptosystem based on DNA chip, explores the special properties of the traditional cryptographic system, and makes use of special properties to realize the relevant application. The specific research results are as follows: 1-The DNA-PKC based on DNA chip is first realized and verified by experiments. Its safety is based on the 鈥淚t is difficult to obtain the exact information of the same hybrid probe on the micro-point of the DNA chip鈥，

本文編號：2303199