摘要
自组装DNA计算在解决NP问题,尤其在破译密码系统方面,具有传统计算机无法比拟的优势.文中提出了一种用自组装DNA计算破译NTRU公钥密码系统的方法.针对NTRU密码系统的特点,采用DNA瓦片编码信息,借助于瓦片间的粘性末端进行自组装,给出了求解多项式卷积运算的实现方案.在此基础上,通过引入非确定性的指派瓦片,提出了一种破译NTRU系统的非确定性算法.通过创建数以亿计的参与计算的DNA瓦片,该算法可以并行地测试每个可能的密钥,以高概率地输出正确密钥.该方法最大的优点是充分利用了DNA瓦片具有的海量存储能力、生化反应的巨大并行性以及组装的自发有序性.理论分析表明,该方法具有一定的可行性.
Computation by self-assembly of DNA is an efficient method of executing parallel DNA computing where information is encoded in DNA tiles and a large number of tiles can be self-assembled via sticky end associations. This paper shows how the DNA self-assembly process can be used for breaking the NTRU public key cryptosystem. In order to achieve this, a method for implementing the cyclic convolution product of two polynomials using self-assembled DNA computing is expounded. Then, a non-deterministic algorithmic is provided to break efficiently the NTRU public key cryptosystem. By creating billions of billions of copies of the participating DNA tiles, the algorithmic will run in parallel on all possible private keys. The computation takes advantage of non-determinism, but theoretically, each of the non-deterministic paths is executed in parallel, yielding the solution in time polynomial in the size of the input, with high probability. It presents clear evidence of the ability of molecular computing to perform complicated mathematical operations.
出处
《计算机学报》
EI
CSCD
北大核心
2008年第12期2129-2137,共9页
Chinese Journal of Computers
基金
国家自然科学基金(60533010,60803113,60773122)
国家"八六三"高技术研究发展计划项目基金(2006AA01Z104)资助
