DNA密码对比传统密码学与量子密码学的优势与不足.doc

DNA 密码对比传统密码学与量子密码学的优势与不足蒋 君 殷志祥（安徽理工大学理学院 安徽 淮南 232000）【摘要】DNA 密码是近年来伴随着 DNA 计算而出现的密码学新领域。 本文简要介绍了 DNA 密码学、传统密码学、量子密码学。 从三者的基本概念、理论基础、具体操作过程、安全依据和现阶段的发展成果以及不足着手，通过对比得出 DNA 密码学相较与传统密码学和量子密码学的优势和不足并分析存在问题的原因。 然后给出 DNA 密码学在实际运用中已经取得的成果和未来可能发展的方向。 最后做出展望提出结合三种密码学的优势建立新的混合型密码学体系的构想。【关键词】DNA 计算；DNA 密码；传统密码学；量子密码学The Advantages and Disadvantages of DNA Password in the Contrast to the Traditional Cryptography and Quantum Cryptography JIANG Jun YIN Zhi-xiang(School of Science, Anhui University of Science And Technology, Huainan Anhui, 232000)【Abstract】In recent years, DNA Password is a new cryptography field which appears with DNA calculation. This paper briefly introduces the DNA cryptography, Traditional cryptography and Quantum cryptography. From the basic concepts, theoretical founda- tions, concrete operation proc-esses, safety basis and the current development achievements and shortcomings of the three fields, this paper obtains DNA cryptographys advantages and disadvantages compared with traditional DNA cryptography and quantum cryptog- raphy and analyzes its causes. Then, thie paper shows theachievements of DNA cryptography in practical application and its future development direction Finally, it will make an outlook that a new mixed cryptography system can be created on the advantages of the three kinds of cryptography.【Key words】DNA computing; DNA cryptography; Traditional cryptography; Quantum cryptography0引言DNA 计算1-3是一门近几年才兴起的前沿学科，而密码学 则是作为用于保护数据安全的工具从古老的凯撒密码到现 代密码学逾期将近两千余年。 两个看似没有联系的学科在现 代技术下呈现越来越紧密的联系。密码学技术是信息安全技术的核心，主要由密码编码技 术和密码分析技术两个分支组成4-5。 传统经典密码学和在其 基础上发展起来的现代密码学 ， 其加密解密过 程 ， 以 及 安 全 性都是基于数学难题, 除一次一密外其他的密码系统都只具 有计算安全性， 如果攻击者有足够的计算能力 ， 就 可 以 破 译 这些密码。 但传统密码在算法和理论上都是相当成熟的。量子密码是一个全新的概念6，它依赖于物理学的理论基础作为密码的安全模式， 简单说就是基于单个光子和它们固有的量子属性来研究开发比较先进安全的全新密码系统7。 因 为量子系统在不干扰系统的情况下是不可能测定该系统的 量子状态的， 同时由 Heisenberg 测不准原理几乎可以保证， 量子密码学成为不可破译的密码。DNA 密码是近几年伴随着 DNA 计算的研究而出现的密 码学新领域。 其特点是以 DNA 为信息载体，以现代生物技术 为实现工具， 挖掘 DNA 固有的高储存密度和高并行性低消 耗等优点， 有很多人相信其将有可能与传统 密 码 学 ， 量 子 密 码学并列成为密码学的三大分支8-10。 但是要想与发展成熟的 传统密码和理论较完善的量子密码并驾齐驱还是要经过长 期的理论构架和实践操作， 现阶段学术界对 DNA 密码的研 究也在逐渐展开11-15。基金项目：本文得到国家自然科学基金（61170172，60873144， 61073102，60973050）资助。作者简介：蒋君，安徽理工大学理学院，硕士，主要研究方向为图与组合优化、DNA 计算。殷志祥，安徽理工大学理学院，教授，博士后，主要研究方向为图与组合优化、DNA 计算及蛋白质结构预测。现代密码学和量子密码学2）加密速度问题；3）卫星的吸收问题。11.1 密码学概念将一个加密系统采用的基本工作方式叫做密码体制。 构 成一个密码体制的两个基本要素是密码算法和密钥。 一个密 码体密码体制通常有五部分组成 ： 明文空间 U； 密文空间 L； 密钥空间 K，k=（Ke 是加密密钥，Kd 是解密密钥）； 加 密算法 E；解密算法 D。2DNA 密码2.1 DNA 密码学概念DNA 密码是密码学中新生的密码， 要了解 DNA 密码必 须先对 DNA 计算和 DNA 生物技术有一定的了解。由 Aldeman 在 1994 年首次利用现代分子技术， 提出并 解决了哈密顿路径问题的 DNA 计算方法， 并成功进行试验 后，DNA 算法被广泛运用与解决 NP 问题中。 这门学科解决 问题的过程可以简化叙述为：1）对于特定问题，将问题中的相关数据编码为 DNA 链。2） 在适宜的条件下 ， 将 1) 中 的 DNA 链的若干拷贝在溶 液中混合。 根据碱基配对原则，溶液中的短链将自组装结合 为长链。3）反应结束后，通过 PCR 扩增、磁珠分离等实验技术，筛 选出满足一定条件的反应结果，即为所求的问题结果。DNA 密码虽然是在 DNA 计算基础上诞生的， 但二者有 明显不同， 区别是：DNA 计算是用 DNA 技术解决数学难题， 而在 DNA 密码中，所谓的生物学难题却是用来作为 DNA 密 码系统的安全依据16-17。2.2 DNA 密码实现过程DNA 密码系统总体方案如下：步骤 A 密钥生成。 此步骤中生成由信息的发送者和接 收者分别掌握的加密钥和解密钥。 一般设计一段 DNA 序列 作为加密和解密信息的引物序列， 或将其设计成为由 Wat- son-Crick 互补配对的一对探针集合等。步骤 B 加密。 将要传送的明文信息制作成为密文，1）需 将明文信息进行数据预处理：选择编码方式将具体明文转化 成为数据信息。 本文使用 DNA 编码方式，将 DNA 核苷酸看 作是四进制编码，用三位核苷酸表示一个字母 ， 如字母 A 则 以 CGA 表示，字母 B 则有核苷酸序列 CCA 表示。 2）制作消 息序列：将由 1）制得的 DNA 消息序列前后各链接上有 20 个 核苷酸的 5和 3引物。步骤 C 信息传送。 用超声波把人类基因序列粉碎成为 长度为 50100 的核苷酸双链， 并变性成单链， 作为冗余的 DNA 使用，在将含有信息的 DNA 序列混杂到其中，喷到传送 载体上形成无色的微点， 在通过普通的非保密途径传送，由 于制作材料普片 ， 可以保证大规模使用 ， 增加了传送的成功 率。明文 mU，密钥 k=K，则加密 CEK （m）K，e解密 mEK （C）U。d1.2 现代密码学现代密码学是在经典密码学或称之为传统密码学的基 础 上 发 展 起 来 的 。 传统密码学基于 Non -Polynomial Time Complete (NP-C)问题之类的各种数学困难问题，但无论是经 典密码学还是现代密码学 ， 其安全性都依赖于 一 种 “ 智 慧 ”， 即尚未发现其安全缺陷便认为其是安全的。 为了打破“构建 方案、攻破方案”这一循环，现代密码学基于更严格和更科学 的基础。在现代密码学中发展完善且运用广泛的主要是：对称密 码、公钥密码等。1.3 量子密码学1.3.1 量子密码学概念用物理学知识开发出的不能被破获的新密码系统就叫 量子密码，由量子为信息载体，经由量子信道传送。 不同于基 于数学难题的传统密码 ， 量子密码是一个全新 的 概 念 ， 它 依 赖于物理学的理论 ， 特别是量子物理学作为密码的安全模 式，简言之就是基于单个光子和它们固有的量子属性来研究 开发的密码系统。量子密码学的实现过程量子密码的传送程序大致为：现在地面发射加密的量子 数据和信息， 再通过大气层发送量子信号 ， 然后由卫星接收 信号再并转发到地面的各个接受目标。1.3.3 量子密码学的优势量子密码学的安全性建立在量子物理学基础上，即使攻 击者拥有强大的计算能力也无法攻破对计算破解方法免疫 的量子密码。 物理法则保证了这个量子信道的安全性。量子密码的安全性是基于 Heisenberg 的测不准原理、量 子不可克隆原理和单光子不可分割性， 遵从物理学规律，是 无条件安全的。 在量子密码学中用光量子传递数据和信息， 如果被监听者插入或截取信息，攻击者不可能在未被发觉的 情况下破译密码，从而保证了密码使用的安全性。1.3.4 量子密码学的难题由量子密码学的实现过程可见，量子密码学的研究和使 用有一下难题需要解决：1.3.2步骤 D解密。 接收方和发送方共享编码方式和引物信息。 当接收方接收到含有消息 DNA 序列的传送载体后，提取微点中的 DNA， 用已有的引物对 DNA 微点中的消息序列进 行 PCR 扩增，再通过测序得出消息 DNA 序列。 再根据预先约 定的编码方式还原出明文2.3 DNA 密码当前面临的主要问题1）缺乏相关理论支持。 至今 DNA 密码还没有建立起相 应的理论，DNA 密码的实现模型是什么，安全依据在哪里，具 体应该如何实现等都尚未解决，也正是因为如此现阶段难以 产生适合使用的 DNA 密码方案。2）实现困难，代价高昂。 在已有的方案中，加密解密阶段 往往要人工合成消息 DNA 序列， 进行 PCR 扩增， 对 DNA 序 列经行测序等生物实验。 这必然要求在装备精良的生物实验 室进行，从而限制了 DNA 密码在实际操作中的使用。2.4 DNA 密码的优势DNA 密码的继传统密码和量子密码以后诞生，必然要有 其独特的区别和优势，如1） 利用 DNA 所具有的体积小的特征 ， 实现纳米级的存 储；2） 利用 DNA 的超大规模并行特性 ， 实现加密解密的快 速化；3）利用人类还不能破解但是可以使用的生物学难题，作 为 DNA 密码的安全依据11-12，以实现能够抵抗量子攻击的新 型密码系统；4）在实际运用方面，由于 DNA 密码对实时性要求不高， 但可以大规模进行数据加密、安全数据存储、身份认证、数字 签名和信息隐藏等密码学应用中可以有独特的发展；5）由于 DNA 微点不易被发现，就算密文被发现截取，也 不易对未知的 DNA 混合物进行测序， 所以消息序列不易被 发现，从而保证了安全性。2.5 DNA 密码的缺陷DNA 密码的不足可以分为：DNA 计算技术的发展不足； DNA 密码学运用上的先天缺陷 ；DNA 密码在实现上的困难 三个大方面：1）DNA 计算技术的发展不足首先， 目前所建立的每一种 DNA 计算模型只能解决一 类问题（以 NP-完全问题为主），而没有像电子计算机那样的 统一处理问题的模型，其距离通用性还有很大差距；其次，在已经建立的 DNA 计算模型中，大多数问题存在 着所谓的“解空间指数爆炸问题” ， 即随着问题规模的增大， 所需要的 DNA 分子数量成指数阶地剧增。 DNA 分子虽然体 积微小，但是可用的分子毕竟有限。再次， 一些模型中， 反应过程中需要人为参与反应步骤 过多，削减了 DNA 计算被大规模应用的可能性；最后，在目前的 DNA 计算实现运算模块现有成果中， 若想将反应结果投入下一次运算， 往往需要人为再处理加工后 才能进行下一步，无法自动进行。 这是限制目前 DNA 计算发 展的本质困难。2）DNA 密码学运用上的先天缺陷首先，不能代替传统密码学独立使用。 DNA 密码的设计不易改变，相当于一次一密，在反复利用上不够灵活。其次，DNA 计算技术的成果不能直接应用 到 DNA 密 码 学的设计和研发使用中。最后，DNA 编码直接影响到 DNA 密码的加密 解 密 过 程 的准确性和破译的难易程度。3）DNA 密码在实现上的困难由前文介绍可知 DNA 密码加密和解密的过程， 以及密 文密钥的设计，可见：首先，DNA 密码从设计到加密解密都需要在在一个设备 精良的生物实验室，耗费巨大代价高昂，不易普遍使用。其次，DNA 密码只能用物理方法传送。 特别是作为密文 的载体、 密钥的引物等， 而编码方式和生物条件等也可以通 过信息传送。 但现在使用的主要使用电子计算机而不是 DNA 计算机，但这又同时保证了在信息屏蔽时密码的使用。最后， 如何保证使用的载体不被破坏污染 ， 从 而 达 到 信 息传递的准确性。3DNA 密码对比传统密码和量子密码DNA 密码学、传统密码学、 量子密码学这三类密码学建 立在不同的学科基础上，从理论到实现方式再到安全依据均 不同。 由于本文主要探讨 DNA 密码的优劣， 下面就将 DNA 密码学与后两种一一对比。3.1 DNA 密码与传统密码的区别1） 理论基础方面， 传统密 码 学 是 基 于 Non-Polynomial Time Complete （NP-C） 问题之类的各种数学困难问题，DNA 密码学以 DNA 为信息载体以现代生物学技术为实现工具；2）传统密码以计算机芯片为存储媒介，DNA 密码以 DNA链或 DNA 芯片为存储媒介；3） 存储能力方 面 ， 传 统 媒 介 1g 硅 芯 片 可 存 储 16MB， 而1gDNA 可存储 108TB；4）传统密码以串行运算为主，而 DNA 密码在 DNA 并发 反应下具备并行运算能力；5）安全性方面， 传统密码多基于困难数学问题 ， 而 DNA密码的安全性还可以依赖于生物学困难问题。3.2 DNA 密码与量子密码学的区别1）理论基础方面 ， 量子密码学基于量子物理学 ，DNA 密 码基于现代分子生物学；2） 传送方面， 量子密码学由量子为信息载体 ， 经 由 量 子 信道传送，DNA 密码以 DNA 为载体，经由物理过程传送；3）安全性方面，量子密码学依据 Heisenberg 测不准原理 成为不可破译的密码，DNA 密码主要是以生物学技术的局限 性为安全依据。4DNA 密码实用性既然 DNA 密码不能取代传统密码成为现在可以独立的大规模使用的密码学， 那么作为完善和补益，DNA 密码在现阶段可以有以下尝试：1）DNA 密码可以储存传统密码学中一次一密乱码本；2）在公钥密码中可以用来构造陷门单向函数；3）目前已经在隐写术中取得成功的前例；4）由 DNA 的生物特性可以制成生物认证码；5）利用 DNA 的超高容量的储存密度以及其生物特性，可 以尝试解决我国庞大的居民身份管理系统， 并运用于身份识 别。3Karl L. DNA computing: Arrival of biological mathematics J. TheMathematical Intelligence, 1997, 19(2): 9-22.4冯登国，裴定一.密码学导引M.北京科学出版社,1999.5王育民,刘建伟.通信网的安全理论与技术M.西安:西安电子科技 大学出版社,1999.6张镇九.量子计算和通信加密M.武汉:华中师范大学出版社,2002.7量子计算和量子信息M.北京:清华大学出版社,2004.8Boneh D, Dunworth C, Lipton R J. Breaking DES using a molecular computetf M/DNA Based Computers. Providence USA: American Math-ematical Society, 1996: 37-659卢明欣,来学嘉, 肖国镇, 等基于 DNA 技术的对称加密方法J中国科学,2007,37(2):175-18210崔光照,秦利敏,王延峰,等DNA 计算中的信息安全技术J计算 机工程与应用,2007,43(20):139-14211Clelland, C. V. Risca, and C. Bancroft,Hiding messages in DNAmicrodotsJ. Nature, 1999, 399(6736): 533-534.12Leier, A., et al. Cryptography with DNA binary strands J. Biosys -tems, 2000, 57(1): 13-22.13Gehani, A., T. LaBean, and J. Reif. DNA based cryptography J. Aspects of Molecular Computing, 2004: 34-50.14Xiao, G., et al. New field of cryptography: DNA cryptography J.Chinese Science Bulletin, 2006, 51(12): 1413-1420.15Lu, M., et al. Symmetric-key cryptosystem with DNA technologyJ. Science in China Series F: Information Sciences, 2007, 50 (3): 324 -333.16Lai, X., et al. Asymmetric encryption and signature method with DNA technology J. SCIENCE CHINA Information Sciences, 2010, 53 (3): 506-514.17Leier A., Richter C., Banzhaf W., et al. Cryptography with DNAbinary strandsJ Biosystems, 2000, 57(1): 13-2218Kazuo T., Akimitsu O., lsao S Public -key system using DNA as one-way function for key distributionJ Biosystems, 2005, 81: 25-295DNA 密码的发展与展望由上文可见，DN