基于DNA自组装的EIGamal系统破译

自组装DNA计算在破译密码系统方面,具有传统计算机无法比拟的优势。采用DNA分子瓦编码信息,借助于分子瓦之间的粘性末端进行自组装,通过引入非确定性的指派型分子瓦,提出了用自组装DNA计算破译EIGamal公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA分子瓦,该算法可以并行地以高概率地破译EIGamal公钥密码系统。

Breaking the EIGamal Algorithm in the Tile Assembly Model

Computation by tile assembly model is an excellent way of executing parallel DNA computing where information is encoded in DNA tiles and thousands of tiles can be self-assembled via sticky end combination. This paper shows how the DNA self-assembly process can be used for breaking the EIGamal cryptography. A non-deterministic algorithmic is proposed to break efficiently the EIGamal cryptography. By creating thousands 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, creating solution in time polynomial with the input and high probability.