DNA密码与DNA计算及应用

霍家佳,张文政

(中国电子科技集团有限公司第30研究所，保密通信重点实验室, 成都 610041)

0 引 言

密码学是用于保护数据安全的工具，从古老的凯撒密码到现代密码学，已经两千多年了。脱氧核糖核酸(DNA)是生物遗传物质，携带生命的遗传信息，自从Watson和Crick在1953年发现DNA之后，人们发现和发展了许多操作DNA的方法，同时也发现了DNA计算具有某些电子计算机无可比拟和替代的优越性。密码学和遗传学原本是毫不相关的两个学科。然而，随着现代科技的发展，近年来密码学和DNA开始走到了一起，并且关系越来越密切。

1994年美国南加州大学的Adleman[1]成功地完成了用DNA计算来解决一个NP完全问题的实验，从而开创了DNA计算研究的新纪元。自此以后，越来越多的目光集中到对这门新兴学科的研究上来，其中包括了不少计算机专家和密码学界的知名人士，他们开始关注DNA计算对密码学及信息安全的影响，开始思考能否在DNA的领域里开辟密码的新天地。

1 DNA密码

DNA密码是新生的密码技术，是传统密码技术的潜在替代途径之一，其特点是以DNA为信息载体，以现代生物学技术为实现工具，挖掘DNA固有的高存储密度、高并行性等优点，实现加密、认证、签名等密码学功能。

1.1 DNA隐写术

隐写术是将通常未加密的文本或者图形完全地隐藏在其它的通过电子传输的文本或者图形中的一种加密方式。15世纪人们就提出了撘词鯏，随后隐写术就大量出现在各种保密通信中。在隐写术加密中，携带秘密信息的载体的数量越大，攻击者从这些载体中恢复出秘密信息的难度就越大。因此，为了提高隐写术的安全性，需要大量的高密度的载体，而DNA的特性正好符合这一要求。1999年，Celland等人在“Nature”杂志发表论文[2]，他们把著名的“June 6 Invasion：Normandy”隐藏在DNA微点中，提出了世界上第一个利用DNA实现信息保密的方法。信息写入的方式是合成具有特定引物的DNA序列，解密的方式是利用PCR扩增之后测序。

经过多年的研究，DNA隐写术可以分成两种加密方式[3]。

第一种是明文串的加密，将明文串与其它DNA串混合在一起进行加密，这样能够防止通过排序读出明文串。其它的这些DNA分子串，称做伪串。为了确保该方法的安全性，伪串应该同消息串具有相同的组成形式。解密的时候需要确认附着在明文消息上的唯一的识别序列(即密钥序列)。这个序列可以在串的终端，正常情况下位于起始序列的位置。因此，解密时通过使用相应的密钥序列作为PCR反应的引物来读出明文消息。这种技术的安全性需要保证伪串的随机性或者使得所有的DNA串的出现具有相同的频率。

第二种加密技术是图形明文的加密，是将明文串和大量的包含相同密钥序列的伪串混合加密。在这种方式下，密钥序列再也不具有用作解密过程的唯一特性。取而代之，解密的密钥是加密使用的整个伪串池。通过读出伪串池和加密池(包括伪串池和明文串)可以生成两个不同的凝胶成像图。再通过数字图像的处理技术，对这两个凝胶成像图作图形化的相减处理，就能得到原始的明文串的序列。

图形解密可以被视为一个独立的密码系统。如果作为密钥的伪串池只使用一次，这个系统同第一种方式一样安全。但是，如果多次使用同一个伪串池，攻击者就会通过对所有的凝胶成像图进行数字图像处理获得越来越多的密钥消息。

1.2 DNA密码系统

目前利用DNA本身的特性构建的密码系统大致分为两种方式，一种是采用DNA数据库作为密码本构建一次一密的DNA密码系统[4]，另一种是利用生物学中的困难问题构建全新的DNA密码系统。

(1)使用替代的一次一密系统

一个替代的一次一密系统是使用一个明文二进制消息和一张随机映射到密文的表。输入的长度为n的DNA串被分割成为具有固定长度的明文串。表的作用就是将所有具有固定长度的可能的明文串映射到相对应的密文串，而且使得其逆映射唯一。加密是将每个明文DNA字替换成相对应的DNA密文字。这种映射是通过使用一个包含了许多片断的长的DNA密码本来实现的。其中，每个片断都代表了一个单独的明文字同密文字的映射。明文字是作为绑结引物的杂交点，接着被扩展生成明密文字对。然后分离明密文字对，删除明文部分得到密文消息。一个理想的一次一密库应该包含大量的一次一密本，能够提供从明文字到密文字的具有良好的唯一性、随机性的映射。

(2)使用异或的一次一密系统

Vernam 密码是使用R个均一分布的随机比特构成的序列S作为一次一密本。S的一个副本保存在发送者和接收者处。L为S的还没有用于加密消息的比特数目。初始的L=R。两个二进制输入的异或操作是当它们相同时值为0，否则值为1。当发送一个长度为n

为了用DNA实现这个算法，需要完成明文消息的加密、一次一密本的创建和DNA的异或操作的方法。目前，用DNA实现二进制加法和异或已经有很多方法。在许多相关文献中，先后涉及到比特加法，并行操作以及DNA瓦状结构。

(3)基于生物困难问题的密码系统

该系统由卢明欣、来学嘉等人提出在[5,6]，依赖于一个生物学困难问题：对DNA 芯片(微阵列)上仅核苷酸排列不同的未知混合DNA(PNA)探针的信息进行完全精确测序破译是困难的。这意味着攻击者不仅要知道芯片上每个点中DNA 探针的种类, 而且要知道每一种探针的准确数量。在此基础上构建了两种算法：基于DNA技术的对称加密算法(DNASC)和基于DNA技术的非对称加密算法(DNA-PKC)。由于DNA密码使用DNA链或DNA芯片作为存储媒介，基于DNA的高存储密度，DNA密码在构造对数据存储容量有需求的安全体制时，相对传统密码将具有明显优势。同时，由于该密码系统依赖于生物学困难问题，这又提供了另一种安全保障机制，其对量子计算机等超级计算机的攻击是免疫的。

1.3 DNA与认证

现在，DNA分子较为广泛地应用在认证领域，生物认证技术也经历了一个突飞猛进的发展过程，这也是DNA隐写术的一个应用。现代分子技术将DNA串植入不同的物质和材料，作为防伪标记的手段。近年在国内外就有利用DNA做为密码防伪的报告并有DNA加密墨水推出，用于签名。台湾发明了世界上第一台DNA认证的芯片，通过类似于身份卡和信用卡的读卡器来识别，芯片内部合成的DNA能够生成只有公司成员才能够察觉和识别的DNA信号。这些日新月异的技术发展，让人更清晰地意识到DNA生物分子技术的潜力，为进一步的推广应用奠定了基础。

2 DNA计算应用

DNA计算首先起源于1994年Adleman的开创性工作，他利用实验证实了作为承载生命遗传密码的DNA双螺旋分子可以用来实现计算。利用DNA计算具有大存储量、低能量消耗及高度的并行性的特点，结合信息安全的要求，专家们提出了其在信息技术领域的很多应用。

2.1 DNA计算解决NP完全问题

众所周知，现代密码学里面涉及的一个重要的部分是对NP完全问题的研究和解决，历来就成为众多学者研究讨论的热点和难点。1994年，美国的Adleman博士在实验室里成功地用现代分子生物技术，即DNA计算的方法解决了一个著名的NP完全问题——哈密尔顿路径问题(HPP)。他花费了近一个星期的时间，对七个顶点的HPP作了仿真实验并且得到了正确的结果，如图1所示。

图1 七个节点的有向图

Adleman的实现步骤大致如下：

(1)对各个顶点、有向边进行DNA编码，建立数据池；

(2)搜索出所有表示从顶点0开始到顶点6结束的路径的DNA编码串；

(3)在上一步的基础上，搜索出具有6个边的路径集(按DNA链的长度分离)；

(4)再依次从各个顶点搜索，找出不重复边的路径集；

(5)通过电泳分离，找出符合条件的路径，即是问题的解；

采用类似的方法，学者和专家们拓展了思路，先后解决了更多的NP完全问题。例如，1995年Lipton解决了可满足性问题；1997年，Ouyang等人解决了最大团问题。他们用DNA分子计算技术解决诸如此类NP问题有一个总体的思想，就是首先建立一个解空间的数据池，然后用穷举搜索的方法，充分利用了生物计算的巨大并行性，逐步筛选，最后找出问题的解。

2.2 基于DNA技术的密码分析

DES(数据加密标准)是迄今为止世界上最为广泛使用和流行的一种分组密码算法，其对于推动密码理论的发展和应用起了不可忽视的作用，对于掌握分组密码的基本理论、设计思想及实际应用仍然有着重要的参考价值。

1996年，Adleman等人提出了用DNA计算来破译DES的一种新思想[7]，将人们的眼光真真正正地吸引到利用分子计算机无可比拟的优越性来分析和破译现代的密码体制上来。用DNA计算的方法破译DES的总体思想是：给定一个明密文对(M0，E0)，攻击者Eve的目的就是找到唯一的k0，使得k0能够将明文M0映射成为密文E0。首先定义如下的函数：g(k)=DES(M0，k0)，其中DES()表示DES加密的过程。函数g(k)将一个56比特的密钥映射成为64 bit的密文，Eve就是想寻找满足g(k)=E0的k。用DNA分子来实现，则需要建立一个数据池Tg，使得Tg包含所有的代表256种可能的密文值对[k，DES(M0，k)]的DNA分子。然后通过提取使得DES(M0，k)=E0的分子找出相应的k值。

在整个过程中，最耗时耗力的部分是对溶液Tg的建立，这一步骤在实验室里大约需要4周的工作。但是一旦Tg建立以后，Eve就可以迅速地破译该密码系统。一般来说，一升水最多可以容纳1017个DNA分子。由于256<1017，可以看出在一升水中就可以完成上面的计算。如果是选择明文攻击，则Eve可以在一天内就破译DES。

对DES的破译方法同样适用于其它密钥长度小于64比特的密码系统。一旦分子计算机取代传统的电子计算机，现有的许多密码系统都面临着破译的危险。

2.3 DNA计算机

DNA计算机的设想是从Adleman的实验开始的，生物计算机目前尚处在理论和实验研究阶段，生物与数学的一些相似性使人们意识到可以利用生物过程来模拟数学过程，更确切地说是，DNA链可用于表示信息，酶可用于模拟简单的运算。这种分子作为一种超级计算机装置的吸引力在于其已经得到证实的存储大量信息的能力——事实上复制生命所需的全部指令都存储在DNA中。尽管这种化学物质不会在短期内取代个人计算机，但是科学家们已经有不少研究成果证明这些满载信息的分子可以通过怎样的方式在未来的计算机中执行计算任务[8，9]。和普通计算机比，其优点是体积小，但存储的信息量却很大，1 g DNA所能存储的信息量可与1万亿张CD光盘相当，远大于现有的计算机存储芯片和其他存储介质[10]。虽然DNA计算机尚有一些技术问题没有解决，但已成为未来的可替代电子计算机技术的一种可选方案，有着广阔的发展前景。

2.4 DNA与软计算

软计算主要包括模糊逻辑推理、神经网络理论、概率推理、遗传算法、混沌系统和人工免疫系统等，这些计算智能技术一直是当前智能科学领域的研究热点，且已被广泛应用于各个领域，包括信息安全领域。目前，软计算中智能技术的理论研究只是对生物系统的简单模拟，专家们近年来开始研究基于DNA在遗传处理系统中的控制作用，开发新型的基于人工DNA模型的计算智能来解决一些科学与实践的问题。如一些学者提出了基于DNA机理的改进的遗传算法、基于DNA编码方法的遗传算法及用于搜索DNA进化计算中好的DNA译码算法等。

3 结语和展望

关于DNA计算的研究目前已经取得了不少令人兴奋的成果，在国际上掀起了一场DNA计算的热潮。人们对DNA计算的前景充满信心，而密码学领域里越来越多的学者和专家也投入到DNA计算的研究中来。一方面，他们充分分析了分子计算这种工具的优越性和对现行密码体制的影响，考虑了如何利用这种工具去改进和更新现行的密码体制。另一方面，也发掘了全新的DNA 密码，使其在应用协议与安全性方面都和传统密码体制有很大不同。对未来的DNA密码和DNA计算在信息安全领域中的应用大致可以在如下的方向发展：

(1)继续探索其它新的DNA计算及模型，探索用DNA计算解决其它NP完全问题的新方法；

(2)研究DNA算法对现有公钥密码和公钥技术的影响；

(3)分析在DNA计算条件下现行密码算法的新的安全度量指标，研究DNA计算对部分密码系统的有效攻击和破译方法；

(4)继续深化DNA隐写术的加解密的方法，拓宽其推广应用的局面；

(5)探索DNA计算与各种软科学的结合和集成，例如与混沌数字水印技术的组合认证，可以大大增强敏感信息的安全性，从而有效的保护数字化信息产品;

(6)开发适合于生物分子计算的求解工具和程序，将DNA计算模型化，研制出可以利用的DNA计算的芯片;

(7)以开发能抗量子计算和生物计算的新密码为目标，进一步分析和研究DNA密码的构建方式，探讨更安全更高效的密码新模型。

总之，虽然DNA密码和DNA计算在信息安全中的应用仍处于起步阶段，但是其巨大的发展潜力和广阔的应用前景已经逐渐显现出来，等待着人们更加深入地研究和探索。

[1] ADLEMAN L M.Molecular Computation of Solutions to Combinatorial Problems[J].Science,1994，266(11):1 021-1 024.

[2] CLELLAND C T,RISCA V,BANCROFT C.Hiding Messages in DNA Microdots[J].Nature,1999,399:533-534.

[3] LEIER A,RICHTER C,BANZHAFW,RAUHEH.Cryptography with DNA binary strands[B].Biosystems,2000,57(1):13-22.

[4] GEHANI A,LABEAN T H,REIF J H.1999.DNA-based Cryptography[Z].5th DIMACS Workshop on DNA Based Computers,MIT,June,1999.

[5] 卢明欣，来学嘉，肖国镇，等.基于DNA 技术的对称加密方法[J].中国科学，2007，37(2)：175-182.

[6] 来学嘉，卢明欣，秦磊，等.基于DNA技术的非对称加密与签名方法[J].中国科学，2010，40(2)：240-248.

[7] Dan Boneh,Christopher Dunworth,Richard J Lipton.Breaking DES Using a molecular computer[M]//DNA Based Computers,volume 27 of DIMACS:Series in Discrete Mathematics and Theoretical Computer Science，American Mathematical Society,1996.

[8] VAN N D,LANDWEBER L F.TOWARDS A Re-Programmable DNA Computer[J]J.of Natural Computing，2005，4(2)：163-175.

[9] 丁永生，李汪根，任立红.基于生物芯片的DNA计算——模型、算法及应用[M].北京：科学出版社，2011.

[10] SEIFE C.What are the limits of conventional computing?[J].Science,2005,309:96.