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

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

【 关键词 】 自组装；DNA分子瓦；EIGamal算法

Breaking the EIGamal Algorithm in the Tile Assembly Model

Zheng Yan

（LuoHe Vocational College of Food HenanLuoHe 462000）

【 Abstract 】 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.

【 Keywords 】 self-assembly； DNA tile； EIGamal cryptography

1 引言

EIGamal算法既可用于数字签名又可用于加密，其安全性依赖于计算有限域上离散对数的难度。要产生一对密钥，首先选择一素数p，两个随机数g和x， g和x都小于p，然后计算Y=gx mod p公开密钥是y，g和p，g和p可由一组用户共享。私人密钥是x。

密码学算法是多种多样的，利用DNA 计算特有的高速并行性和高存储性，人们开始利用DNA 计算来实现密码分析和密码加密的技术。与此同时，生物技术获得了飞速的发展，尤其是人类基因组测序计划完成，容易产生大量互异的DNA序列，这诱发了人们利用生物技术的方法对信息进行加密的思想。DNA计算的代数运算、基于表面的DNA计算以及自组装DNA计算等方法已经在理论上解决了一些图论、网络、优化以及密码等问题。目前已有学者提出了基于DNA的加密和解密技术。

本文通过深入分析公钥密码系统地特点，给出基于自组装DNA计算的EIGamal公钥密码系统破译方案

2 EIGamal公钥密码系统

对消息M加密，首先要选择随机数k，只要k与p-1互素。然后计算：

a=gk mod p

b=ykM mod p

a和b是密文对。注意密文的大小是明文的两倍。

解密a和b时，计算：