基于DNA计算自组装模型的Diffie-Hellman算法破译

摘要

DNA自组装计算模型是近年来引人关注的计算模型,已有基于自组装模型的二进制加法、乘法以及有限域中的加法和乘法的讨论.文中利用DNA自组装模型设计的模乘系统,实现了素数p的本原根g连续乘方后模p的数的排列,从而可以在线性时间内求解离散对数,为破译Diffie-Hellman密钥交换算法提供了新的生物方法.该模乘系统使用了Θ(p)种自组装类型,组装的时间复杂度为Θ(p-1.系统最后组装结果提取出报告链后,经过PCR和凝胶电泳读取离散对数结果.该模型扩展了DNA自组装计算模型的应用,为求取离散对数提供了新思路.%Recent experiments have demonstrated that the simple binary arithmetic and logical operations can be computed by the self-assembly DNA tiles.This paper shows how the tile as-sembly process can be used to break Diffie-Hellman key exchange.In order to achieve this,the author used tile systems to construct the integers permutation from 1 to p-1 based on the truth systems can be read by the standard sequence-reading operation that uses a combination of PCR and gel electrophoresis.Through the processes of tile systems,we can pick out the discrete log-arithm result which is the secret key in the Diffie-Hellman algorithm.So the key exchange by Diffie-Hellman algorithm is unsafe.The system can be carried out in Θ(p-1 assembly time with Θ(p) tiles.The methods extend the applications of self-assembly model.