生物密码系统及面向密码学问题的DNA计算研究
发布时间：2018-10-31 18:44
【摘要】：自Adleman在1994年首次提出了哈密尔顿路径问题的DNA算法以来,DNA计算作为一种新型计算方法,目前在理论和实践方面取得了若干初步成就。利用DNA反应本质的并行特性,DNA计算表现出巨大的并行运算能力,在未来有很大的发展空间。随着DNA计算的发展,生物密码体制亦成为密码学研究的新领域。当前传统密码体制的安全性多基于计算困难问题,如整数分解问题和离散对数问题,若在未来可找到这些问题的有效计算方法,相关密码体制的安全性将受到巨大威胁。而生物密码体制安全性并不依赖于计算困难问题,因此并不受计算能力发展的影响,故而可作为传统密码体制的补充。本文研究内容分为两方面,一是面向密码学问题的DNA计算研究。离散对数问题在现代密码学中扮演重要角色。Di?e-Hellman密钥交换、El Gamal类加密和签名等密码体制的安全性都基于离散对数问题的计算困难性,若该问题在未来被攻破,则依赖该问题的密码体制安全性都将受到威胁。我们利用DNA计算的并行运算能力,以Tile自组装DNA计算模型为工具,设计离散对数问题的多项式时间DNA算法。同时,在相关子系统的设计上,比前人的方法有一定优化。具体研究成果及创新性如下:1-首次给出Tile自组装模型下多项式时间非确定性离散对数算法。算法非确定性随机选择指数x,并行地计算ax mod p,并与y进行比较,求解满足ax≡y(mod p)的x。对于np位模数p,系统组装时间为O(n3p)。此前的方法系统组装时间为指数时间O(2np),相比较之下,本文的方法在组装时间上有显著改进。2-给出两个Tile自组装模型下乘法系统新的实现,系统所需Tile大小分别为24与16。相比起此前Brun提出的Tile集大小为28的乘法系统,本文提出的系统在Tile集大小上有所优化。3-首次给出Tile自组装模型下直接求模运算的系统:给定nA、nB位大小的整数A与B,系统直接计算A mod B。最坏情况组装时间为Θ(nA(nA-nB)),最好情况组装时间为Θ(nA)。相比起此前用除法求余数的方法,本文所提出系统在组装时间上有所优化。当nA远大于nB时,本系统的优势较为明显。4-针对此前的乘法系统无法在其他子系统最终配置上直接运行的瓶颈,本文给出一种可在其他运算模块结果上进行连续运算的平方系统。故而在整个运算过程中,无需中断自组装反应便可进行平方运算。5-此外,本文提出一种线性自组装模减法算法,算法中实验步骤为常数步。本文研究工作的第二部分面向生物密码体制。针对基于DNA芯片的密码体制进行研究,探索其区别于传统密码体制的特殊性质,并利用特殊性质实现相关应用。具体研究成果如下:1-首次实现基于DNA芯片的公钥密码体制DNA-PKC并以实验验证。其安全性基于生物学困难问题“获取DNA芯片微点上长度相同混合探针的精确信息困难”,并不独依赖于计算困难问题,相比起传统体制提供了另一层安全性。同时给出其特殊性质“加解密钥具有多对多关系”。2-围绕“加解密钥具有多对多关系”这条特殊性质展开,首次给出基于DNA芯片的动态广播加密方案DNA-DBE。相比起传统广播加密方案,DNADBE的优势在于密文和解密钥的复杂度皆为常数,与用户数无关。且具有后向安全性。3-引出新性质“不同的明文消息可以对应相同的密文”,首次给出基于DNA芯片的信息隐藏方案DNA-IH。传统信息隐藏方案中隐密消息嵌入载体后,将引起载体特征统计分布的变化。而DNA-IH中普通消息所对应的芯片与嵌入隐密消息后所对应的芯片完全一致,因而无法通过统计攻击等手段检测隐秘消息的存在性。
[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
[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
本文链接：https://www.wllwen.com/kejilunwen/wltx/2303199.html
