（运筹学与控制论专业论文）dna计算在密码学上的应用.pdf

摘要 摘要 d n a 计算属于生物、化学、数学以及计算机等学科的个交叉领域，其研 究内容所涉及的范围很广。自从a d l e m a n 教授开创了这一新的计算领域以来， d n a 计算的一些思想和方法被广泛地应用于解决一些图论、网络、优化等问题。 由于d n a 计算的高度并行性和d n a 的密集的储存信息的能力，这使得d n a 计 算也非常适合解决密码问题，目前d n a 计算在密码学上的应用主要包括一次一 密加密体制和d e s 等方面。 我们研究的目的是继续探索d n a 计算在密码学上更为广泛的应用，研究的 主要内容涉及到密码学上的背包公钥密码体制，详细内容包括两个方面，一方面 是研究公钥( 单射背包向量) 的特点，另一方面是研究利用d n a 计算的方法来 解决背包公钥密码体制中背包密码的破译问题。 背包问题是一个n p 完全问题，目前还没有解决这一问题的非常有效的方法。 在研究过程中，我们首先通过对背包公钥密码体制的理解，考察公钥的特点，探 求背包问题解的唯一性条件。在探索利用d n a 计算来破译背包密码的过程中， 我们广泛收集并阅读了当前有关d n a 计算解决密码问题和有关解决背包问题的 文献，对其中的一些d n a 计算方法和解决背包问题的方法进行全面地理解、归 纳，从而提出两种新的计算方法，第一种方法的优点是在一定程度上可以降低空 间复杂度。第二种方法是通过对第种方法的改进来执行二分法，有效地降低了 时间复杂度和空间复杂度。 虽然当前d n a 计算用于密码学的领域还比较有限，并且有些d n a 计算方 法和计算模型在实验条件下还难以实现，但是这种并行的计算方法为解决密码问 题提供了一种新的思路，必然会对信息领域的发展产生重大影响。 关键词：d n a 计算；密码学；背包问题；二分法 北京工业大学理学硕士学位论文 a b s t r a c t d n a c o m p u t a t i o nf a l l s i n t oac r o s sf i e l do fb i o c h e m i s t r ym a t h e m a t i c sa n d c o m p u t e r , i tc o v e r sa ne x t e n s i v er a n g e a f t e rp r o f e s s o ra d l e m a ni n i t i a t e dt h i sn e w c a l c u l a t i v ef i e l d ，t h em e t h o do fd n a c o m p u t a t i o nc a nw i d e l yb eu s e dt os o l v es o m e p r o b l e mo fc h a r tn e t w o r ka n do p t i m i z e d n ac o m p u t a t i o nc a ns o l v es o m ec i p h e r p r o b l e mb e c a u s eo f i t s h i g h l yp a r a l l e lc o m p u t a t i o na n dt h e d e n s ed e p o s i t e d i n f o r m a t i o no fd n a ，t h ep r e s e n ta p p l i c a t i o no fd n a c o m p u t a t i o nm a i n l yb ei n v o l v e d i no n e t i m ep a d c i p h e r s y s t e ma n dd a t ae n c r y p t i o ns t a n d a r d ( d e s ) w ec o n t i n u et o e x p l o r et h ee x t e n s i v ea p p l i c a t i o no fd n ac o m p u t a t i o ni n c r y p t o l o g yi no u rr e s e a r c h ，o u rr e s e a r c hb ei n v o l v e di nk n a p s a c k t y p ep u b l i ck e y c r y p t o s y s t e m t h ed e t a i l c o n t e n tc o n t a i nt w oa s p e c t s ，o n ea s p e c ti st of t d dt h e c h a r a c t e ro ft h ep u b i ck e y t h eo t h e ri st ou s ed n a c o m p u t a t i o nt os o l v et h ep r o b l e m o f b r e a k i n gt h ek n a p s a c kc o d e s k n a p s a c kp r o b l e mi saf a m o u sn p cp r o b l e m ，t h e r ei sn oe f f e c t i v em e t h o dt o s o l v et h i sq u e s t i o na tp r e s e n t w ef i r s ts e e ka b o u tt h ec h a r a c t e r i s t i co ft h e p u b l i c - k e y b yt h ec o m p r e h e n s i o no ft h ek n a p s a c k - t y p ep u b l i ck e yc r y p t o s y s t e mi nt h ep r o c e s so f r e s e a r c h ，t h e nt r yt of i n dt h es i n g l ea n s w e rc o n d i t i o no ft h ek n a p s a c kp r o b l e m w e e x t e n s i v e l yc o l l e c t e da n dr e a ds o m ew r i t i n g st h a tr e l a t et ob r e a k i n gc i p h e rp r o b l e m u s i n gd n ac o m p u t a t i o na n ds o l v i n gk n a p s a c kp r o b l e mi nt h ep r o c e s so fs e e k i n g a f t e rt h em e t h o dt ob r e a kk n a p s a c kc o d e s ，a n dw eg o te x t e n s i v e l yc o m p r e h e n s i o n a b o u tt h em e t h o do ft h ed n a c o m p u t a t i o na n ds o v l i n gk n a p s a c kp r o b l e m ，t h e nw e b r o u g h tf o r w o r dt w on e wm e t h o d ，t h em e r i to ft h ef i r s to n ei st h a ti tc a nr e d u c et h e s p a c ec o m p l e x i t yd e g r e e t h eo t h e ro n ea m e l i o r a t e st h ef i r s to n ea n dp e r f o r m s d i c h o t o m y , s oi tc a ne f f e c t i v e l yr e d u c et h et i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t yo f t h ec o m p u t a t i o n t h o u g ht h ea p p l i c a t i o no fd n ac o m p u t a t i o ni nc r y p t o l o g y i sr e l a t i v l yf i n i t e a n ds o m ed n a c o m p u t i n gm e t h o da n dm o d e l sc a nn o tb eu s e di nl a b ，t h i s p a r a l l e l c o m p u t i n gm e t h o dp r o p o s e san e wm e t h o do fc o m p u t a t i o n ，i tw i l lb r i n ga ni m p o r t a n t e f f e c ti ni n f o r m a t i o nf i e l di nt h ef u t u r e 摘要 k e yw o r d ：d n ac o m p u t a t i o n ；c r y p t o l o g y ；k n a p s a c kp r o b l e m ；d i c h o t o m y 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名蛆同期：彬， 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲塑耻翩虢仫经同期醴丝夕 第l 章绪论 第1 章绪论 1 。1 d n a 计算的发展以及研究现状 随着现代计算机科学技术的发展，人们一直在追求一种计算速度更快、体积 更小的计算机。1 9 5 6 年，理查德冯纽曼就曾经充满幻想的描述了构建一台“亚 显微”计算机的可能性。目前，尽管计算机在提高计算的速度、容量和性能上已 经取得了巨大的进步，但“亚显微”计算机的目标还远远没有实现，不少计算科 学的研究者难在这些方面进行着不懈的努力，并取得了一些初步的成果，影响了 计算科学的发展。 1 9 9 4 年，美国南加州大学的a d l e m a n 教授在s c i e n c e 上发表了第一篇d n a 计算的论文【i l ，解决了n p 问题的一有向哈密顿路径问题，开创了计算科学的一 个新领域。d n a 计算的研究属于生物、化学、数学等学科的一个交叉领域，其 研究内容所涉及的范围很广。很快d n a 计算吸引了大量的计算机、数学、生物 学以及化学研究者的目光，越来越多的研究者投身到这一研究领域中。在 a d l e m a n 等人的工作的基础上，最近几年里在这门学科上不断出现许多创新成 果，人们正逐渐发现d n a 计算的内在规则，创造出一些d n a 计算的方法和模 型。d n a 计算的些代数运算、基于表面的d n a 计算以及d n a 自装配计算等 方法可用于在理论上解决一些图论、网络、优化以及密码等问题。 逻辑和算术运算是d n a 计算中一个很重要性的研究问题，1 9 9 5 年，b e a v e r 提出了用d n a 分子插入和缺失的方法 4 0 1 ，来实现d n a 计算机的逻辑和算术运算 4 ”。9 6 年g u a m i e r i l 6 j 等人实现了用d n a 计算来作加法。1 9 9 9 年，j o h n s o l i l v e r 提出了矩阵乘法的d n a 计算方法【7 叭。后来b o n e h 等人用动态规划方法解决了图 可达性的背包问题f 9 1 ；l e e t e 等人解决了符号决定性问题1 1 0 1 ；n 。j o n o s k a 等人解决 了道路染色问题l ；以及超标量计算机代数问题【1 2 1 等等。在神经网络方面，贝尔 实验室的a p m i l l s ，j r b y u r k e ，pm p l a t z m a n 提出了模拟神经网络模型的d n a 计算方法1 1 3 1 。 d n a 计算的表面基方法1 4 2 1 是在1 9 9 6 年提出的，它的优越性在于能够方便地 实现自动操作。2 0 0 0 年n a t u r e 刊载了q i n 曲u al i u 的文章，标志着表面上的d n a 计算正在逐步完善，现在d n a 计算的表面基方法越来越得到广泛的应用。 北京j = 业大学理学硕士学位论文 d n a 自装配计算方法是d n a 计算的一种重要方法，w i n f r e e 对d n a 自装配 计算的发展作出了重要贡献，他的关于二维d n a 格的设计和自装配的论文1 2 】奠定 了自装配计算方法的基础，后来自装配计算成为d n a 计算一个重要的计算方法， c h e n g d em a o 等人的论文用d n a 三螺旋分子的自装配来实现加法和逻辑异或运 算【3 l a s h i s hg e h a n i 和t h l a b e a n 等人把这种方法用于密码学领域，提出了一 种基于一次性密码本的d n a 加密和解密方法【4 l 。日本的k e n s a k us a k a m o t o 等人 提出的发卡状计算模型解决可满足性问题【5 】，也是建立在分子自装配的基础上的。 由于d n a 计算的高度并行性和d n a 的密集的储存信息的能力，这使得d n a 计算非常适合解决密码问题，l i p t o n 和d a nb o n e h 最早在这一领域进行了研究，9 6 年他们给出了使用分子计算机破译d e s 的方法 3 4 1 ，在此基础上a d l e m a n 等人又给 出了使用s t i c k e r 模型破译d e s 的方法【3 6 1 ，a s h i s hg e h a n i 和t h l a b e a n 等人提出 了一种基于一次性密码本的d n a 加密和解密方法1 4 i ，此外a n d r el e i e r 等人还给出 了使用d n a 二进制串进行加密和解密的方法【4 。d n a 计算在密码学上的应用必 然对信息领域的发展产生巨大影响。我们也把目光投向了密码学上背包公钥密码体 制中背包密码的破译问题，并且找到了两种解决背包问题的有效算法，特别是二分 法能较好地降低计算的时间和空间复杂度。 d n a 计算的高度并行性使得d n a 计算在解决n p 问题方面具有很大的优越 性，只需在多项式时间内就可以解决这类问题。1 9 9 5 年l i p t o n 3 9 1 也在s c i e n c e 上发 表了文章，进一步论证了d n a 计算可解决完全性问题。a d l e m a n 等人的工作已经 成功地可以解决2 0 个变量的3 - s a t 问慰1 5 】。现在已有很多科学研究者研究出了许 多的d n a 计算方法，解决了很多的n p 问题。我们的研究实际上也是解决一个著 名n p 完全问题一背包问题，再一次证明了d n a 计算解决n p 问题的高度有效性。 1 2d n a 计算的方法 d n a 计算解决问题的基本思想是：利用d n a 的双螺旋结构和碱基互补配 对原则，把所要运算的对象编码成d n a 分子链，在生物酶的作用下，按照一定 逻辑运算规则利用d n a 重组技术作用于试管中的d n a 链，生成各种数据库， 试管中的不同d n a 链对应着相应的结果值，最后利用分子生物技术获得运算结 果i l ，从而使问题得到解决。 d n a 计算在本质上是利用d n a 重组技术，它是在现代分子生物技术的基础 第1 章绪论 上发展起来的，为了利用d n a 分子完成给定的任务，我们必须借助对d n a 分 予的各种操作技术。经常用到的生物操作技术主要有以下几种【1 7 1 8 捌： ( i ) 合成：使游离的碱基形成寡核苷酸的过程。可以用一台机器将寡核苷酸 按一定的次序合成，得到某一期望长度的链。 ( 2 1 混合：把2 支试管中含不同核苷酸的溶液混合，得到一混合体。 ( 3 ) 链接：两条带有粘头的d n a 链在连接酶的作用下，按w a s t o n c r i c k 互补 配对原则将互补部分连接在一起的过程。 ( 4 ) 剪切：利用特定的限制性内切酶在d n a 双链的某个位置切断形成带有 粘头的两条链的过程。 ( 5 ) 退火和溶解：这是两个完全互逆的过程，退火是指两条互补的d n a 单链 在温度逐渐降低的条件下，合成一条双链的过程：溶解是一条d n a 双链在温度 升高时，分解为两条互补的单链的过程。 ( 6 ) 复制( 放大) ：通过聚合酶链反应( p c r ) 将d n a 串复制。p c r 是基因工程中 的一种i n v i t r o 手段它包含了一系列温度循环的重复，每一循环由三个阶段组 成：模板d n a 的变性分解成单链；然后冷却使引物与寡聚核苷酸的模板进行复 合，最后由d n a 聚合酶使引物延伸。每一个反应循环都使目标d n a 分子的数 量加倍，反映呈现指数级增长。 ( 7 ) 提取：将含有特定d n a 短链的分子提出来，这要通过将特定短链的互补 链吸附在小磁珠上，然后用磁铁将小磁珠吸出来的过程。 ( 8 ) 延长：这过程需要一条已知单链模板和条已存在的、并已与模板的 一小段匹配的引物d n a 序列，要延长的d n a 序列根据模板给出的序列结构， 在聚合酶的作用下由5 端到3 端的方向不断延伸。 ( 9 ) 缩短：通过外切核酸酶从d n a 分子的末端去掉一个核苷酸而缩短d n a 分子。 ( 1 0 ) 电泳分离：将d n a 分子置于有凝胶的电场中，由于d n a 分子带负电， 在电场中会向正极移动，长度大的分子链受到凝胶的阻力大，移动速度慢，因此 可用此技术去获取一定长度的d n a 分子链，也可区分不同长度的d n a 分子。 ( 1 1 ) 杂交分离：是早期d n a 计算模型的极为重要的操作，可以提取包含特 定短序列的所有单链。 北京工业大学理学硕士学位论文 d n a 计算具有高度并行性、大容量、低能耗的特性，这是目前的计算机所 无法比拟和替代的，d n a 计算能解决许多目前的计算机难以解决的问题，在很 多领域将会有羞广泛的应用。 1 3 研究内容和意义 由于d n a 计算具有高度的并行性以及d n a 具有密集的储存信息的能力， 这使得d n a 计算非常适用于解决密码问题，因此我们研究的主要内容是利用 d n a 计算解决背包公钥密码体制中背包密码的破译问题。 背包问题就是试图在n 个正整数组成的集合a 中找出若干个元素使它们的 和为给定的正整数b 。背包问题是一个n p 完全问题，解决此类问题的时间复杂 度随着h 的增加迅速( 成指数级) 增长，所用的时间很快的增加，使得问题不能 在多项式时间内有效的解决。 背包问题吸引了不少研究者的目光，但目前的研究进展缓慢，没有非常有效 的解决方法。e r i cb b a u m 和d a nb o n e h 等人将背包问题转化为图可达问题，提 出了应用动态规划的方法【9 i ，在d n a 计算机上执行宽度优先搜索算法 2 4 1 来解决 背包问题的思想，但这种算法只能解决相应的图为e 平衡图的特殊的背包问题。 2 0 0 4 年台湾的w e n g - l o n gc h a n g 等人【2 5 1 提出了利用a d l e m a n - l i p t o n 模型解决 背包问题的方法。但这种算法仍然是一种穷举的蛮力算法，具有较高的空间复杂 度。 背包公钥密码体制就是利用解决这一n p 完全问题的困难性而产生的，它是 密码学上的第一个公钥体制3 2 1 ，信息接收者选择一超递增的背包向量作为其私 钥，并将其伪装成一般的背包向量a 作为其公钥，信息发送者利用公钥爿向接 收者传送密文b ，攻击者相当于解决一背包问题来破译背包密码。 背包公钥密码体制中背包问题的唯一的一个解都对应彳的一个特定的子集， 从而对应着唯一确定的明文。我们的目的一方面是研究公钥所具备的特点，探求 背包问题有唯解的条件。另一方面是找到两种解决背包问题的d n a 计算方法， 特别是二分法可以有效地破译背包密码且具有较好的时间和空间复杂度。 1 4 本童小结 d n a 计算是一门新兴的交叉学科，在很多领域都有着潜在的应用。本章首 先对课题的知识背景作以介绍，阐述了d n a 计算的发展及计算方法，然后对和 第1 章绪论 本人研究内容有关的背包问题以及背包公钥密码体制作以介绍，并对研究的内 容、意义等方面也做了介绍。 北京工业大学理学硕士学位论文 第二章d n a 计算解决密码问题综述 2 1 以一次一密为基础的加密方法 2 1 1 预备知识 一次密密码本4 。2 q 加密使用密码本中的随机数据将明文转化成密文。密码 本起到密钥集的作用，密码本中的数据最多只能用一次。否则将泄露有关明文的 一些信息，增加猜到信息的效率，因此以d n a 链的形式集合个大的一次密码 本应秘密创建并且可在发送者和接收者之间通过安全信道进行传送。一次一密密 码本系统是已知的唯一绝对不可破的密码系统。以一次密码本为基础的加密方 法主要有两种：使用代换的d n a 密码系统以及以一次密码本为基础的d n a 异 或运算。 对数据进行加密的单钥加密体制系统【2 明见图2 1 图2 - l 单钥加密体制系统 f i g u r e2 - 1o n e - k e yc r y p t o s y s t e m 2 1 2 使用代换的d n a 密码系统 一次密码本代换系统使用明文信息和一次密码本中的一次一密笺( 密钥) ，明 文链的长度为n ，一个理想的一次密码本应包含大量的密钥并且每个密钥都不同 地、随机地把明文字母写成密文字母，构建密钥的方法见图2 2 。 第2 章d n a 计算解决密码问题综述 可重复单位的组成：( a ) 来自一套密码字母集的序列字母c ( b ) 来自明文字 母的序列字母p i( c ) 聚合酶“终止”序列。 每个序列对i ，都独特地把明文字母和密文字母联系起来。表示序列 p 。的链 是相应于字母p 。的补链，它可以用作聚合酶引物并且可以通过附加密文字母c 的补链而被延伸。终止序列可以阻止d n a 链的延伸超过配对密文字母的界限。 o n e - n m ep a d r e p e a t i n gu n i t j 广- p i 图2 - 2 一次密密码本d n a 序列 f i g u r e2 - 2o n e t i m ep a dc o d e b o o kd n as e q u e n c e 密钥链使用这种方法构建使得密码本中的每条链确定一组特殊的字母对，规 定一套明文字母到密文字母的的个代换表。每个重复单元指定一个书写对，在 密钥链上密码字母和明文字母的使用不能多于一次。因此给定一个密码字母c i 可以保证它只将单个明文字母p i 改写。 一次密码本的整个的构建过程可被重复为准备大量的不同的密钥链。构建一 次密码本可以通过使用以前的基因文库构建工程和d n a 计算中的d n a 字母编 码方法的部分集合程序来实现。一种方法是化学合成各种部分序列然后在溶液中 随机地集合成各种密码笺。另一种方法是使用d n a 芯片，d n a 芯片有一个固 定的d n a 链微阵，使得大量相同的单个序列聚集在一个微观像素里。d n a 芯片 的微阵在光学上是可编址的，光的指导合成使得d n a 的化学合成可以并行在成 千上万的位置进行。 加密时先将长度为n 的明文链分成固定长度的明文字母链，使用这些明文字 母的补链分别和一次密码笺上的对应的明文字母链杂交，而后作为引物进行延 伸，这就形成了明文- 密文对，然后再分离明文密文对，去掉明文部分并将密文 进行顺序标识( 解密者可以知道字母的加密顺序) ，最后将密文集中通过公开信 道发送给接收者即可，接收者使用已有的同样的一次密码本用同样的方法可将密 北京工业大学理学硕士学位论文 文恢复为明文。 g e h a n i 和l a b e a n 等人描述了在一个芯片上使用d n a 微阵能以2 维图像记 录的形式对输入输出的数据进行加密和解密的系统，这个系统包括：一个需被加 密的数据集( 图像) ，一个带有非移动性的d n a 链的芯片和一个上面所述的一 次一密密码本。图3 中退火的d n a 是相应于由上面所述的由一个随机代换密码 所准备的字母对链。非移动性的d n a 链根据现在使用的技术被放在芯片的玻璃 底层的序列可编址的方格内。( 见图2 3 ) 密文明文字母对链退火到非移动的链 上。被退火的链在5 端包含一个荧光标识( 在图中用表示) 。下面分别是明文 字母的补链( 未补的部分) 和密码字母的补链( 已补的部分) ，在两个字母间是 一个碱基类似物( 图中自盒) ，它可以断开核苷酸的骨架。 a m 目ni ，n a ， d n 图2 - 3d n a 芯片的构成 f i g u r e2 - 3c o m p o n e n t so f t h ed n ac h i p 对于加密开始于一个带有取自于密码词汇序列的d n a 芯片。图2 5 给出了 加密和解密的一步步的程序，这个程序可分三步来完成： 第一步，由一个一次密码本所准备的带有荧光标识的字母对链在带有和它们3 端互补的像素被退火到芯片。 第二步，通过使用透明和不透明的区域将信息( 图2 - 4 a 组) 转化成一个遮掩图 像。随着遮掩保护芯片的发光，透明区域的退火的核苷酸在图像不稳定的区域分 裂，5 。端和被退火的3 端分离并在溶液中收集。这个试管中的荧光标识的链是 被加密的信息。不透明地方下面已退火的短链不受发光的影响并随后被从芯片上 冲洗掉丢弃。如果被加密信息的短链被重新退火到一个不同的d n a 芯片上，他 们会退火到不同的地方，信息就不可读( 图2 4 b 组) 。如果使用一个和编码芯片 相同的芯片并且5 端( 密码字母) 和3 短( 明文字母) 的序列是分离的，就不 会发生捆绑且b 组中的芯片就会完全变黑。 第2 章d n a 计算解决密码问题综述 第三步，5 部分在它们的5 端仍被荧光标识，它们被收集并作为加密信息被传 送。 通过使用与加密过程中用的相同的一次密码本和d n a 芯片一个信息可以被 解密，首先通过把适当的密码字母贴到每个明文字母上重建字母对链，这可以通 过使用转换链作为引物，一次密码作为模板利用引物延伸或非对称p c r 来完成。 链被缚到一次一密笺的适当位置并且被接上适当密码。注意在解密过程中荧光标 识仍然需要，但是图像变化的碱基不在需要也不再出现，解密的最后一步涉及到 把改变过的字母对链缚到d n a 芯片上并使用荧光显微镜读出信息。 图2 4a 信息 f i g u r e 2 4 a ： m e s s a g e i 一 i l i l i h - - 一 b 加密信息c 解密 b ：e n c r y p t e d m e s s a g ec ：d e c r y p t e d m e s s a g e 口q n m d 一 i ；i ；i l 一m j 黜 t j 一- u i i l l l d d 嚣高= o 图2 - 5 加密和解密的一步步的程序 f i g u r e 2 5s t e pb ys t e pp r o c e d u r e sf o re n e r y p t i o na n dd e c r y p t i o n 9 羞 北京一亡业大学理学硕士学位论文 21 3 以一次密码本为基础的d n a 异或运算 v e m a m e 密码2 9 1 是由1 1 位的二进制密钥k 对n 位的二进制明文m 通过异或 运算加密而成，k 可事先在发送者和接收者之间传送，当长为n 二进制明文信息 m 需被传送时，m 的每一位m 。和k 的每一位k j 进干亍异或运算产生加密位c i = m i 毋k i ( i = l 2 n ) ，被使用的k 的n 位在密码源中被毁掉而密码序列c = ( c i ，c 。) 被发往目的地。接收者使用相同的方法利用相同的密钥k 可将密码序列恢复为 明文m 。g e h a n i 和l a b e a n 等人提出利用d n a 自装配【2 1 2 2 , 2 3 3 0 , 3 1 来执行异或运 算产生v e m a m 密码的方法，用d n a 来执行这种算法( 见图2 6 ) 需要以下三个步 骤： a 呻啦i 姗i l l g h i , h ：，b 一k 抽 l r 呻鼬峄4 i - a ： “d 吨o r - j 图2 - 6 利用碘f a 瓦片计算异或运算 f i g u r e2 - 6x o rc o m p u t a f i o nb yt h eu s eo f d n at i l e s ( 1 ) 编码一条n 位的二进制明文信息m ，对于m 的每一数位m i ，使用一个 d n a 瓦片口，进行编码，d n a 瓦片是多链聚合体，它包括两条或更多的双螺旋结 构这些瓦片可以线性地组织到一起形成一个序列a l a ：一a 。，它可以用于对二 进制输入m 进行异或运算的一条骨架链。 ( 2 ) 创造一个d n a 一次密码本。根据随机的输入创建一次密码笺序列 d “埘：作为输入骨架的另一部分。许多口“以：形式的骨架链最初已创建， 可以使用p c r 或一些合适的技术进行复制，然后事先在初始处和目标处进行分 1 0 第2 章d n a 计算解决密码问题综述 离和储存。当在初始处进行加密时，通过使用发送者和接收者都知道的相应于某 一特定骨架的前缀索引标签使得被使用的特定骨架被作以标记和传输。这样两条 骨架就形成了具有特定结构的输入组织，结构的输入部分在图2 - 6 中表示出。输 入组织中的每对瓦片间形成一个狭孔用于连接一个输出瓦片。通过采用配对的粘 头末端，输出瓦片连接成适当的连接狭缝。 ( 3 ) 实现d n a 异或运算。最后使用加法链接酶产生一个经过整个组织的报告 链r = a l a 2 埘。口：口口：b i b 2 一“( b ，= a ，o 口：，f = 1 , 2 川) 。这条链可以通 过先熔解链间的氢键然后再胶体提纯进行提取。它包含了所有线性连接的明文信 息、加密密钥和密文。通过使用包含一个限制点的标识序列。使用一个相应的内 切酶可以切除密文，然后根据密文的长度对密文进行分离( 它的长度为剩余序列 的一半) ，接着就可以以密集的形式储存并发送到目的地。 因为异或运算是逆向的，运用相同的密钥通过使用与加密相似程序可以将密 文恢复为原来的明文。如果加密者每次随机地使用一个密钥加密则v e m a m e 密 码在理论上是不可破的，但这需要较大地密钥空间，这为密钥的管理带来一定的 难度。因此加密者在加密过程中容易重复使用同一密钥，这是个致命的错误， 容易受到攻击。 2 2 数据加密标准( d e s ) d e s l 2 8 , 3 3 是一个广泛应用的分组对称数据加密系统，每次用5 6 位的二进制 密钥k 将6 4 位的二进制明文m 加密成6 4 位的二进制密文e ，e 的计算可通过图 2 - 7 的线路进行。线路共有1 6 轮构成，输入的5 6 位密钥k 在左边，m h 表示m 的最高3 2 位，m l 表示m 的最低3 2 位。p - b o x 是变换输入信息数位的装置，s - b o x 比较复杂，它将4 8 位的输入转化成8 组6 位的信息输入，每一组经过一个查阅 表计算并输出4 位的信息。因此d e s 线路每一轮的计算包括一个4 8 位的异或运 算、一个s - b o x 和一个3 2 位的异或运算。解密线路与加密线路类似，两种线路 的区别在于p b o x d e s 的加密路线图见图2 7 。 2 3l ip t o n 等人破译d e s 的d n a 算法 由于d n a 计算具有很强的并行计算能力，这使得它特别适用于攻击密码中 北京工业大学理学硕士学位论文 的密钥搜索。l i p t o n t 3 4 1 等人最先利用d n a 计算对破译d e s 的方法进行研究t 他 所采用的是比较直接而朴素的方法明文密文对破译法，即假设密码攻击者在 已知一明文密文对的情况下找到密钥信息，从而根据该密钥了解其它的明文信 息。 l i p t o n 等人破译d e s 的方法首先建立在对二进制串进行适当编码的基础 上，创建编码各种密钥的d n a 初始溶液，分别粘贴已知的明文链后再进行1 6 轮的加密运算，最后通过搜索找到密钥。下面就这些方法予以详细地介绍。 图2 7d e s 线路 f i g u r e2 - 7d e sc i r c u i t 爰 瓤 鹭 趣 l，。，。l1。，：l，。，：一，。，】l|li 第2 章d n a 计算解决密码问题综述 2 3 1 二进制串的编码与操作 设二进制串x = x i x ：屯j ，对每个数位及其值用不同的3 0 - m e r ( 3 0 个碱基) 进行编码如b 。( o ) 表示对第i 位是0 进行编码。只是3 0 - m e t 用于连续数位之间 的间隔。 则所有的二进制串x o ，1 4 可表示为： $ 晶占，( 薯) s 岛( 工：) s ：只一且( 矗) 最。这里所有e ( ) 和墨都是不同的且每两 条位链不能包含较长的共同部分，以防止创建表示各种密钥的d n a 初始溶液时 错误地连接。 从溶液丁中提取表示第f 位是l 的二进制链，也就是提取包含b ( 1 ) s 的d n a 链，可表示为e x t r a c t ( r ，x 。= 1 ) ，同样e x t r a c t ( 7 1 ，工。x = 1 0 ) 可提取包含形如 r 。( 1 0 ) = e ( 1 ) s bl ( o ) s 。的链。 2 3 2 破译d e s 的过程 2 3 2 1 创建初始溶液 利用图2 - 8 分三步创建含有相应于从晶到s 。的2 “个对密钥编码的d n a 链 的溶液。 第一步，图中每个顶点表示长度为3 0 的字母。一个顶点v 用巧一表示，巧表示 左边1 5 个字母，n 表示右边1 5 个字母。 图2 - 8 初始化圈 f i g u r e2 - 8i n i t i a l i z a t i o ng r a p h 第二步，对每个顶点v 创建试管包含链个_ 一，对有向边界( ”，v ) 创建试管包含链 北京工业大学理学硕士学位论文 上u ，_ ，对于端点创建试管包含链上( 岛) s n , i , ( s ，6 ) ， 第三步，混合所有试管中的溶液让d n a 链连接，从混合液中提取包含的链， 记为爿，在从一中提取包含s ，。的链，这样就可得到从s 到s 。的各种d n a 链a 2 3 22 创建完初始溶液然后将已知的明文链粘贴到各密钥链上，并进行以下的 d e s 线路的有关运算。 1 异或运算： 假如我们要计算当前溶液中的第i 位和第_ ，位的异或运算，一般地需将 x ，o x ，粘贴到表示工的d n a 链上。操作的第一步是将溶液分成两种溶液t o 、五， 瓦包含的d n a 链满足x 。o x ，= 0 ，瓦包含的d n a 链满足z ，o x ，= l ，第二步再 将值分别粘贴到瓦、i 中的d n a 链上。 定义：x ，o x j = ( 工，+ 工j ) ( j l + 一) ；x ，o x ，= ( i ，+ x j ) ( x ，+ i ) ( 1 ) s e tt ”= e x t r a c t ( t ，x 。= 1 d ，x ，= 1 ) a n dt0 1 = e x t r a c t ( t ，z = o o rx j = 1 ) ( 2 ) s e t t l = e x t r a c t ( t 1 1 ，x 。= 0 0 rx = o ) a n dt o = e x t r a c t ( t 叫，x 。= l o r 上，= o ) 这个步骤需要4 次提取，如果并行进行两次提取，则整个程序就可两步完成， 因此一个异或运算需要两步提取一步粘贴。 2 每次计算三个异或运算： 如果每次可以进行3 2 个提取，则可分两步计算三个异或运算，需要计算的 是两组三个连续的数x 、x 。、x 。和x ，、。川、x j * 2 需要粘贴到d n a 链上的是 x 。o x ，、工川o x 川和z 十2o x j + 2 定义：z ( z l z 2 乃) = z i z 2 ( z l o ：2 0 毛) o ，1 ) 3 一般的，根据所粘贴的值将溶液t 分成8 种溶液。，五，所依据的原理为： 对任意a i 口2 吧 o ，l r 有：x i 屯o h y 2 y 3 = a i 口2 吩铮j2 1 2 2 0 ，1 2 使 ( x t x 2 x 3 = z ( z l z 2 b ) o r y l y 2 ) ， = z ( z l z 2 0 ) ) a n d ( x l 工2 x 3 = a o z ( z l z 2 b ) o r y l y 2 y 3 = a o z ( z l z 2 0 ) ) ， 其中b = a 1o 口2o a ： 第2 章d n a 计算解决密码问题综述 具体过程可以分为如下几步： ( 1 ) 对每个z 。z ：毛 o ，l r t 。二2 h - - e x t r a c t ( t ，工。工。+ l x ，+ 2 = z ( z i z 2 2 3 ) o r x j x j + 1 x j + 2 = z ( z i z 2 0 ” 这一步共需8 次提取。 ( 2 ) 对每一z t z ： 0 ，l 2 和口= a t 口2 口3 o ，1 r 疋￥。卜e x t r a c t ( t ：而6 ，x ，一+ l x j 十2 = a o z ( z l z 2 b ) o r x j x j + i x ，+ 2 = a g z ( z l 三2 0 ) ) 其中6 = i o a 2o 口；，这一步需要3 2 次提取。 ( 3 ) 对所有的d o ，l r ，作l 卜l0 0u t u l 邶u 瓦 对每个日= a t a 2 a 3 0 ，1 3 ，将q 口2 吒粘贴到t 中的d n a 链上。 3 计算查阅表 一个查阅表就是一个函数， 0 ，l 6 寸 o ，1 ) 4 ，每轮共8 个表，每个表共有1 6 个值，将6 位二进制串转化成4 位二进制串具体计算方法见表2 1 表2 - 1 查阅表的计算 t a b l e 2 1c o m p u t a t i o no f t h e l o o k u pt a b l o 一x 2x 3x 4 屯 二迸制输入 l l u“1 。 l o123 4 567891 01 11 21 31 41 5 o1 441 3121 51 1831 061 2 5 9o7 1o1 5741 421 311 061 21 19538 2 2 4 l 1 4 8 1 3 6 1 l 1 51 29731 05o 3 1 5 1 2 8 2 4 9l 7 5 l l 31 41 0o61 3 2 十进制数字 00l0 】二进制输出 具体操作步骤如下： ( 1 ) 根据需要粘贴的值将溶液分成瓦，正，正，1 6 份，需要进行提取操作 北京工业大学理学硕士学位论文 r + - - e x t r a c t ( t ，厂( x ) 2 ，) ( 2 ) 对每个产o ，1 5 ，将表示，的4 位二进制链粘贴到l 中的d n a 链上。 d n a 链的不断粘贴使得链不断加长，因此在每一轮计算结束时有必要将链 用不到的部分去掉，必须保留的是5 6 位的密钥k 和从上一轮传递下来的6 4 位 的信息，对于形如0 k j p 的链( 其中k 为5 6 位，为无用部分，户为6 4 位) ， 我们可以除去，在粘贴j p 时，可将p 放在与k 相邻的位景，则在每一轮计算结 束时d n a 具有形式0 尸u ，然后用内切酶切去，在下一轮开始时d n a 链具 有形式士p k 。 23 2 3 找到加密密钥破译d e s 攻击者在已知一明文密文对( m 。，) 的情况下，利用d e s ，对于给定的明文 m 。，可以使用各种k o ，l 广对吖。进行加密，创立溶液d e s ( m 。，足) ，它包含 如下形式的d n a 链0s r ( k ) r ，( d e s ( m o ，k ) ) ，溶液中每条d n a 链表示对某一 密钥世编码并使用k 对m 。进行加密。然后攻击者从溶液d e s ( m 。，k ) 中提取包 含土r ，( 乓) 的链，其中= d e s ( m 。，k 。) ，所提取的链对( 芷。，e 。) 进行编码， 从提取的链中找到密钥k 。，根据k 。可以破译其它的明文信息。 l i p t o n 等人所提出的用分子计算机破译d e