DNA计算及密码学应用

This project focuses on the research of DNA computing in the framework of cryptography and its impact on conventional cryptosystem. Existing DNA algorithms could not be applied directly in cryptosystem or cryptanalysis, since the combination of such algorithms cannot be applied continuously without interruption. This project aims to overcome this barrier and develop DNA algorithms for modular multiplication, great common divisor and discrete logarithm. Other than using molecular biological methods to simulate the procedure of conventional algorithms (Shanks, Pollig-Hellman, etc.), we will use a completely different approach to design the algorithm, thus the algorithm would coincide with the characteristic of DNA reaction and take full advantage of its massive parallelism. We will also compare our discrete logarithm DNA algorithm with the conventional algorithms and analyze its impact on conventional cryptosystem...Due to the importance of discrete-logarithm in cryptography, the research of this project will provide theoretical basis of the crypto-analysis in new computing model. Moreover, this research could also have a positive impact on both cryptography and biology.

本项目研究面向密码学问题的DNA计算算法，并分析其对传统密码体制的影响。由于现有基础计算模块的DNA算法难以进行连续运算，故不能直接应用于密码系统与密码分析。本课题将对这一现状进行研究，解决现有DNA计算不能进行连续运算的关键问题，并设计模乘、最大公约数与离散对数的DNA算法。.本项目所研究的离散对数DNA算法并非传统算法（如Shanks，Pollig-Hellman等）的生物模拟，而是另外设计一套符合生物特性的计算流程，并充分利用DNA的大规模并行优势。在此基础上，本项目将分析DNA离散对数算法与传统算法的性能差异，并分析其对传统密码体制安全性的影响。 .由于离散对数问题是密码学中的关键问题，本项目的研究结果将对新型计算模式下的密码学研究提供重要的理论依据。同时，本项目的研究也将对密码学和生物学的学科发展产生积极的影响。

本项目的研究分为两个方面，一是面向密码学问题的DNA计算研究，二是基于DNA芯片的密码体制研究。具体工作总结如下：.一．在DNA计算方面，首次给出了Tile 自组装模型下多项式时间离散对数算法。具体成果有：..(1)以自组装DNA 计算模型为研究工具，给出线性自组装模型下的减法算法。..(2) 在二维Tile 自组装模型下，提出两个新型的乘法系统。相比较于原有.的乘法系统，本文所提出的两个系统在Tile 集大小上均有所优化。..(3) 给出Tile 自组装模型下的模运算算法。这是Tile 模型下直接解决模运.算算法的首次实现。相比起运用除法系统求余数的方法，本文所提出的直接求.模的算法在组装时间上有所优化。..(4) 对于乘法系统无法连续运算的缺陷，给出一种可在其他计算模块结果.上进行连续运算的平方算法，使得在运算中无需中断组装过程。..(5) 在平方算法基础上，结合乘法系统、模系统，实现可连续运算的模指.数算法。..利用非确定性算法，首次给出Tile 自组装模型下多项式时间离散对数算法。..二．密码体制研究方面的主要成果：..(6) 探讨DNA芯片密码体制区别于传统密码体制和普通DNA密码体制之处，总结DNA芯片密码体制的特殊性质：同一加密钥可对应多种解密钥，反之亦然。..(7) 在该特性基础上，首次实现基于DNA 芯片的面向群组加密体制：动态.广播加密体制DNA-DBE。相比起传统广播加密方案，DNA-DBE的优势在于：.-对于用户个数，本体制中解密钥与密文的规模都是常数；.-用户可动态地加入系统，无需改变此前用户的解密钥。.-我们的系统具有后向安全性，而传统动态私钥广播加密体制[Delerablee07]并不具有该特性。..(8) 根据加解密钥的多对多关系，利用DNA 芯片密码体制新性质“不同明文可对应于相同密文”，在此基础上首次实现基于DNA 芯片的信息隐藏方案DNA-IH。基于DNA芯片的信息隐藏方案