基于DNA技术的对称加密方法

基于DNA技术的对称加密方法摘要DNA密码是伴随DNA计算的研究而出现的密码学前沿领域。 文中结合现代基因工程技术和密码学技术设计了一个对称加密系统一 DNASC在DNAS（中，加密钥和解密钥是DNA探针，密文是特殊设计的DNA芯片。系统的安全性主要基于生物学困难问题而不是传统的计算问题，因而对未来的量子计算机的攻击免疫。 加密过程是制作特殊设计的 DNA芯片（微阵列），解密过程是进行芯片杂交。 在DNASC中,数以万亿计的DNA探针被方便地同时进行杂交并识别出来，从一定程度上体现了 DNA在超大规模并行计算和超高容量数据存储方面的巨大潜力。关键词对称加密DNA密码DNA计算近几年来，DNA所固有的超大规模并行性、超低的能量消耗和超高密度的存储容量被开发出来用于计算、数据储存以及密码学等领域。 DNA密码就是在这样的背景下诞生的。类似于量子密码，DNA密码是传统密码系统的潜在替代与补充， 但二者在实现技术上大不相同。DNA密码系统的安全性不依赖于计算困难问题， 因此不管未来的DNA计算机和量子计算机的计算能力有多么强大，DNA密码对这些计算机的攻击都是免疫的。并且，同量子密码相比，DNA密码更适用于安全的数据存储。新生的DNA密码在理论和实现上都远未成熟，有效的 DNA密码系统鲜见。这主要是因为下述原因：首先，当前的DNA技术主要处于试验阶段，缺乏可用于DNA密码中的成熟理论。其次，DNA密码涉及交叉学科，相关研究需要密码学家和生物学家的通力合作，而这两个领域在以往的研究中关联很少。另外，相关的核心技术如 （PCR）技术和DNA芯片技术以及自动[1]测序技术都是近年来才走向成熟。密码学家要完全理解这些技术，需要一定的时间。文中提出如下几点：首先，阻碍生物学发展的生物学困难问题在密码学中会有不同的用途，有可能用来构建新型的密码系统。本文提出了一个生物学困难问题，并根据当前的生物技术发展水平，对这个困难问题的难度进行了探讨。基于这个困难问题，提出了一个非确定性的对称加密系统一DNASCDNASC的安全性主要依赖于文中提出的生物学困难问题，对于[2]量子计算机等超级计算机的攻击是免疫的 。其次，DNASC勺加密是非确定性的，在一定程度上类似于一次一密，其随机化的过程是基于DNA计算的超大规模并行性。虽然DNA计算具有超大规模并行计算的潜力， 但是在实际应用中很难得到体现。 在DNASC勺解密过程中，数以万亿计的DNA探针被方便地同时进行杂交并识别出来， 在一定程度上体现了DNA在并行计算和超大规模数据存储方面的巨大潜力。 第三，已有的DNA密码系统多需要利用核苷酸直接编码，因而难以实现。本文中利用DNA芯片（微阵列）技术，提出了新的数据存储技术、新的编码技术以及新的数据读取技术， 因此，在加密阶段不再需要合成DNA序列，在解密阶段也[3]不再需要对DNA序列进行测序，这使得DNASC更容易实现。本文的目的并不是要提出一个马上就可以替代DES等加密系统的实用密码系统，而是展示DNA在密码学的应用中有巨大的发展潜力。未来，DNA密码有可能发展成为密码学的重要组成部分。1生物学困难问题传统密码学基于NP问题之类的各种数学困难问题。 量子密码基于测不准定理，测不准定理也可以认为是量子状态测定的困难问题。所以， DNA密码应该基于生物学困难问题。然[4]而，现代生物学主要还是基于实验的，并不像数学那样有大量精确的公式和完善的定理 。虽然在研究中发现了众多的生物学困难问题， 并且其中很多问题可能比密码学中常用的大整数分解问题等还要难以解决，但是，大多数生物学困难问题并不适用于实现密码系统， 而且，要找到一个适合于构建密码系统的生物学困难问题并不容易。 人们对计算复杂性问题已经有了相当深入的研究，而对生物学困难问题的难度还没有系统的研究过。 我们提出了下面一个生物学困难问题，论证了其难度，并利用这个生物学困难问题开发了一个密码系统。 这个生[5]物学困难问题的部分内容也是文献 中DNA言息隐藏方法的安全性依据。我们认为，“对DNA芯片（微阵列）上仅核苷酸排列不同的未知混合 DNA（PNA探针的信息进行完全精确测序破译是困难的”， 这意味着攻击者不仅要知道芯片上每个点中 DNA探针的种类，而且要知道每一种探针的准确数量， 这样的芯片在DNASC中称为加密芯片或者密文。相关的解释如下：首先，让我们看一下当前的 DNA测序技术和DNA克隆技术。现在有两种主要的测序方法:Maxam-Gilbert方法（也称为化学降解法）和Sanger的方法（也称为酶法）。这两种方法都[6]不适用于对DNA芯片上微量的未知混合序列进行测序 。Maxam-Gilbert方法需要相对较多的DNA样本，不能用于对芯片上微量的DNA分子进行有效测序。Sanger的方法要把引物退火到DNA莫板上来完成测序反应。如果对待测序的DNA莫板完全未知，最关键的用于测序的引物就无法合成，因此Sanger的方法不能直接用于对DNA芯片上的探针进行测序。有人也许会提出可以先把探针克隆以后再用 Maxam-Gilbert方法进行测序。然而，这个方法也难以奏效。在原位合成法制作的芯片中，通常只有不到 100万个探针，而在cDNA微阵列中，通常只有0.1-0.3ng的DNADNA克隆技术需要的DNA数量远多于芯片上的DNA[7]数量，所以难以进行有效的克隆，而且特殊的探针并不能用于克隆 。例如，类似于DNA分子的肽核酸（PNA）探针已经开始代替DNA探针用于制作微阵列。肽核酸（PNA）是DNA分子的类似物，其特点是DNA分子的戊糖链骨架被PNA的N（2-氨基乙基）-甘氨酸代替。PNA分子可以作为DNA分子的替代物在基因芯片等领域使用，但是不能被传统的 DNA克隆技术克隆。当前，几乎所有的DNA测序技术，包括最精确的质谱测序技术 （MS），都基于Sanger的方法。虽然近年来也提出了其他的方法作为 Sanger方法的替代，包括用酶消化核酸片段的MS方法，用DNA微阵列测序的方法等等，这些方法仍然处于发展阶段并且都具有自身的弱点。质谱方法测序的基本原理要求对目的 DNA分子质量的准确测定，从而对DNA羊品的纯度[8]要求极高，而实际应用效果并没有报道的那么理想 。DNA微阵列方法缺乏成熟的理论并且也有很多技术瓶颈。其次，相对于DNA测序技术中遇到的困难而言，制作更难以测序的特殊加密芯片是容易的。例如，可以在密码系统中使用仅仅是核苷酸排列顺序不同的微量混合探针， 现有的测序方法都无法对这种探针进行有效的测序，这是因为所有已知的测序方法都要求对DNA分子进行纯化与扩展。如果对这种混合探针预先进行纯化再测序， 也是难以实现的，这是因为对[9]这种混合探针的纯化非常困难 。Khodor和Gifford指出，对未知的仅核苷酸排列顺序不同的混合探针，即使是40mer的短序列，如果没有和目标探针同源的探针，利用先进的磁珠法来进行纯化，在理想条件下所能纯化出探针的上限值是 1%。并且，在使用混合探针的情形下，DNA芯片上的一个点表示0还是表示1，将不仅取决于这个点上的探针的种类，而且要取决于各种探针的比例。表示0的点和表示1的点可以具有相同的探针种类，所不同的只是各种探针的比例。在这种情形下，攻击者要想通过测序的方法破译本系统，他不仅要知道芯片上所有探针的种类，还要知道每种探针的准确数量。对混合探针测序已经如此困难了，要想精确测定混合探针中每种探针的数量，恐怕很多年以内都是难以实现的。最后，我们认为这个困难问题将持续很多年。一个原因是现有的生物学技术要解决这个问题还有非常远的距离。另外一个原因是生物技术的发展，也使得人们更容易制造更难以测序的芯片。例如，随着纳米技术的进步，人们正在尝试利用原子力显微技术 （AFM）在DNA[10]芯片的每个点上仅放置单个 DNA分子 。2加密流程现在，我们具体描述DNADSE这个系统的安全性主要依赖于第 1节描述的生物学困难问题。首先扩展密码系统的定义如下 ：假设发送者为Alice，她拥有加密钥KA指定的接收者为Bob，他拥有解密钥KBK=KB或者*KE）。Alice使用KA通过一个变换E把明文P装换成密文C。除非拥有KB从C得到P是困难的。我们称变换E为加密过程，C是密文。Bob收到密文C后，利用解密钥KB和密文C进行一个变换D得到明文P。这里，KA和KB以及C并不限于数字，还可以是量子或者 DNA等任意的材料、方法等等。 E和D也不仅仅限于[11]数学计算，而可以是任意的物理、化学、生物等过程 。系统的总体步骤如下：步骤A密钥生成。加密钥是一个特定探针的集合，解密钥是一个对应的互补探针的集合。杂交条件也可以作为解密钥的组成部分。发送者Alice从已有的实验中挑选探针作为加密钥。解密钥通过安全的途径传送给指定的接收者Bob。步骤B加密。Alice首先把明文转换成二进制矩阵，然后根据这个矩阵用加密钥制作DNA芯片。在没有解密钥的情况下，从芯片上读出明文是困难的，这类似于量子密码。量子密码是由于测不准原理难以测定量子状态， 而在DNASC中是由于DNA技术的局限性无法读取芯片上的特殊探针。在DNASC勺加密步骤中引入了随机化的过程， 这使得加密过程在一定程[12]度上类似于一次一密。步骤C解密。Bob使用解密钥和DNA芯片（密文）杂交从而得到杂交信号，这是一个生物过程而非数学计算。然后 Bob利用电子计算机进行一个信号处理过程得到明文。下面借助一个例子详细解释这个系统的细节：步骤1密钥生成。首先，我们要做一个 DNA杂交实验或者从一个已知的实验中挑选探针作为密钥（这个实验应该保密）。这里，我们使用一个已知的实验，这个实验并不是为了加密而设计的，我们只是利用这个实验演示一下加密系统。在实际中，应该如本文所述重新设计实验以获得更高的安全性。下面，我们将介绍这个已知的实验。在这个实验里，基因芯片的基因表达数据反映了酵母从无氧呼吸（发酵）到有氧呼吸的代谢转变的过程中基因转录谱的变化。代表已知的所有酵母基因的6400个cDNA探针被事先点样在基因芯片上， 而从上述两种代谢条件下的酵母体内提取的 RNA则用不同的荧光探针标记作为被检测探针和该芯片上的探针杂交，杂交的结果可以用来分析整个基因组的基因转录水平的变化。 具体地说就是从接种9小时后的酵母细胞(发酵状态)中抽取的RNA反转录获得的cDNA探针用绿色荧光分子Cy3标记，在杂交实验中作为参照系 ；而从接种后19小时的酵母细胞(有氧呼吸状态)制备的cDNA分子用红色荧光分子Cy5标记。杂交的结果可以用扫描荧光共聚焦显微镜观察并记录不同波长的荧光信号(红色和绿色荧光)。两种荧光的扫描图像可以经由软件进行整合分析来推断特定基因在两种呼吸模式转换时表达量的变化。 在由发酵到有氧呼吸的代谢状态转换的过程中，被诱导转录(转录水平提高)的基因的对应的点显示为红色， 反之为绿色，而基因表达水平几乎不变的基因则显示为黄色。文献中还提出重复的实验结果是基本保持不变[13]的，这使得DNA芯片能用于加密用途 。下面借用这个实验演示DNASC勺时候，所有带颜色的点看成一类，表示有明显的杂交反应，所有黑色的点看成一类，表示没有明显的杂交反应。第二，我们从这个实验中分别挑选探针作为加密钥和解密钥使用。我们把芯片上的所有候选探针(未标记)作为集合：，DNA汤中所有目标探针(已标记)作为集合〉。根据杂交结果和杂交条件，分别选择合理的标准 U和S用以挑选探针对。当然，集合 :中的探针并不需要分离出来。满足标准 S的探针对用于表示二进制数字 1，满足标准U的探针对用于表示数字0。集合3由表示0的子集-0和表示1的子集组成，注意到=叮J。这里，表示1的点满足标准(G6.Bkg-10000)(R6.Ratio乞0.33)或(G6.Bkg-10000)(R6.Ratio_0.33)或(G6.Bkg-8000) (R6.B_8000)(R6.Ratio_0.8) (R6.Ratio乞1.33)，表示0的点满足(G6.Bkg辽8000) (R6.B辽8000)，其余的点抛弃不用，其中G6和R6代表Cy3和Cy5标记的cDNA探针在芯片上杂交信号强度，而R6.Ratio就代表某个芯片上点的红色荧光信号[14]强度相对于绿色荧光信号的比值，而 Bkg则代表背景信号的强度值 []。探针集合■0 和‘作为加密钥，Ek=：0-•「。探针集合壽以及解密时的实验条件共同作为解密钥Dk。步骤2数据预处理。我们挑选爱因斯坦的名言"Imagination ismoreimportantthanknowledge”作为加密的明文。 首先要把这句话按照ASCII码的编码规则转换成二进制比特串，并用“00000000'填充，得到一个 21X24的矩阵。 G6步骤3加密。从二进制虚拟芯片上提取点制作新的芯片。集合 Cy3和、中的点被放置在玻璃或者硅芯片的对应位置上， 爱因斯坦的名言就加密在芯片上了。〉加密芯片可以通过公开的途径发送而不用担心安全问题， 只有指定的接收者拥有解密钥并且知道杂交条件从而能够解密。随机化密文：为了获得更高的安全性，要使用仅仅是核苷酸排列顺序不同的混合探针制作芯片，这样的芯片更难以测序， 另外每个点的探针组合可以有所变化， 最后的杂交结果随之在一定的范围内变化。 即使对同样的明文，在不同的加密过程中得到的密文(芯片)也不相同。在实用中，可以随机混合集合“中的探针放置到芯片上形成点表示 1，甚至还可以把-0中的适量探针加到这个点上。 类似的，可以随机混合-0中的探针放置到芯片上形成点表示0，并且可以把“中的适量探针加到这个点上。 这样，表示0的点和表示1的点甚至[15]可以拥有相同种类的探针，不同的只是各个点上不同种类的探针比例不同 。如果每个点上有1000万个探针，'-1和S各有2000种探针分别储存在试管中， 那就可以从-1中随机抽取800万个探针，从30中随机抽取200万个探针，混合后放置到芯片上形成点表示 1。类似的，可以从30中随机抽取800万个探针，从打中随机抽取200万个探针放置到芯片上形成点表示0。每个表示0或1的点上可能的探针组合种类为C2000 C2000 =55 1011165J8001999 J2001999一°・° 2理论上，即使把世界上所有的数据都用 DNA芯片上的点来表示，也可以做到每个点上的探针组合都不同， 这在一定程度上类似于一次一密。 事实上，从试管中抽取的DNA数量不是很精确的，总会带有一定的误差， 这种不规则误差正好增加了芯片上每个点探针组合的随机性，从而使得系统更加安全。 这样的芯片在杂交时，结果会产生一定的误差，但是因为我们在密钥生成阶段已经把所有的探针在同一个反应体系中进行过杂交， 所以很容易把误差控制在一个可接受的范围内。 此外，使用二进制编码方法也能够承受较大的误差。 在把杂交信号转换成二进制数字之后，还可以用纠错码或者检错码的方法来防止误差。 现有的采用点样法制作芯片的设备都是用纯化的探针制作芯片， 但是改变一下程序就可以使用混合探针制作芯片了。这种随机化的过程并不意味着每制作一个点就要把所有的加密探针都抽取一遍。 实用中只要把探针的组成部分改变一下， 就可以放到不同的点上， 相似的点可以随机放到芯片[16]上不同的位置上 。步骤4解密。解密的过程首先是杂交的过程。指定的接收者用解密钥和 DNA芯片（密文芯片）进行杂交。如上所述，杂交的结果是可重复的。 当同样的目的CDNA样本退火到芯片上的时候，将会得到类似于的杂交信号。步骤5数据后处理。得到所有的杂交信号后，可以看到解密芯片上包含亮度较高的彩色点以及亮度极低的黑色点，这些信号可以通过一个简单的信号处理过程转化成二进制矩阵。转换的规则是，解密芯片上亮度比较高的彩色点都对应二进制矩阵中的 1，亮度低的黑色点都对应二进制矩阵中的 0。然后，根据ASCII码的编码规则，把二进制矩阵转换成对应[17]的英文字母，爱因斯坦的名言就恢复出来3安全性和并行性DNASC具有两层安全性：第一层安全性是生物技术的局限性提供的，是该系统主要的安全依据。第二层安全性是计算问题，即使攻击者突破了第一层安全性，在没有解密钥的情形下，他还必须具有强大的计算能力和数据存储能力才能破译 DNASC3.1第一层安全性（生物学安全性）指定的接收者用解密钥中的探针和加密芯片 （密文）杂交，然后根据杂交信号恢复出明文。因为可能的密钥组成数量非常大，攻击者不可能碰巧猜出。在没有解密钥的情形下，攻击者要想得到芯片上的明文信息， 他或者是随便找些探针和芯片进行杂交， 根据杂交结果尝试找出解密钥，或者尝试得到芯片上的探针组成并分析出相应点的含义。如果一个攻击者随便选取一些 DNA汤和加密芯片（密文）进行杂交，由于他选取的DNA汤和解密钥大不相同，得到的杂交信号将会和利用解密钥得到的杂交信号有极大的不同。 通常，他选择的DNA汤很难和芯片上的探针有效杂交上， 因而只能得到一些很微弱并且杂乱的杂交信号，这样的信号对于解密几乎没有任何帮助。 事实上，即使攻击者得到了解密钥中的探针，如果不知道解密时的杂交条件，也会因为所得到的杂交结果有巨大的误差而难以正常[18]解密。如果攻击者想通过直接读取加密芯片的方法来恢复明文，需要对芯片上的每个点精确地测序。然而，加密芯片不是普通的芯片，缺乏有效的技术对特殊设计的加密芯片进行精确并且高效的测序，因而攻击者不可能成功，相关内容已在第一节中进行了论述。3.2第二层安全性（计算安全性）如果很多年以后可以在没有解密钥的情形下精确并且高效的识别出芯片上每个点的所有探针DNASC勺第一层安全性就被突破了， 但这并不意味着DNAS（就不安全了，编码技术提供了系统的第二层安全性。假设加密钥由2000种表示1的探针和2000种表示0的探针组成，即使这4000个探针20001202已知，可能的密钥组合为C4000=1.6610。如果明文是未压缩的英文单词，则其冗余度为3.2bits/字母，本加密系统的唯一解距离为 V=H（k）/”二=1249。为了验证一个密钥，最少需要比较芯片上 1249个点。如果每个点包含1000万个2007 10位长的寡核苷酸，就需要把1249110=1.24910个200位的四进制数和4000个200位的四进制数逐一对比。为了找出一个密钥，平均要进行 C2000/2=8.33101201次这样的计算，所需要的计算能力和存储空间都极大地超出了当前人类社会的极限。 事实上，攻击者并不知道表示0的探针和表示1的探针的种类数，因此，攻击者需要的计算量要更大。此外，采取一些简单的措施也可以增加所需要的计算量。例如，对明文进行压缩可以减小冗余度，[19]从而大大增加唯一解距离，相应的破译计算量也会大大增加3.3存储能力和计算能力虽然Adleman等人证明DNA计算具有惊人的并行计算潜力和数据存储潜力，但在实际应用中不易得到体现。DNAS（从一个方面展现了DNA计算在超大规模并行计算和超高容量的数据存储方面的巨大潜力。 假设在DNAS（中,加密钥由2000种表示1的探针和2000种表示0的探针组成，每个芯片上有 100万个点，每个点上有1000万个探针，每个探针的长度是200个核苷酸，这样的芯片可以做到只有几平方厘米大小，即使是数百个这样的芯片同时进行杂交，也只能算是小规模的实验。 解密过程可以看作一个计算的过程， 这个计算过程所需要的计算量是把11071106100=11015个200位的四进制数和4000个200位的四进制数逐一比较。对应的芯片上数据存储量为：芯片上的每个点包含的数据量为200 210000000=4109bits,一个芯片上所有的点包含的数据量为9 6 15410 110=410bit,100个这样的芯片的总面积虽然只有几百平方厘米，但包含的数据量为惊人的41015100=41017bits。4结束语文中提出了一个非确定对称 DNA加密系统。由于使用了 DNA芯片技术，该系统易于实现并且体现出DNA计算的超大规模并行性和超高密度的数据存储能力。 随着DNA芯片技术的快速发展，该系统的实现代价也会快速降低。在传统的密码系统中，除了一次一密外，其安全性均依赖于某些计算困难问题。 这些计算问题被认为是[1]困难的，但是并没有从理论上得到证实，这样的密码系统在量子计算机一[20]和DNA计算机的攻击下有可能是不安全的 。比较而言，DNA密码的安全性依赖于DNA技术中的“困难问题”，因而是对量子计算机和 DNA十算机的攻击免疫的。同时， DNAS（还具有某些特殊的性质譬如，系统的密文是特殊设计的芯片，因而难以非法复制，这使得 DNASC有潜在的广阔用途。当然，DNASC并不是一个完美的密码系统，它只是具有某些特殊的、能用于密码学用途的优点。更为重要的是，作为潜在的下一代信息处理技术， 有关DNA十算及其相关技术的研究正在取得一个又一个的突破。 本文提出的DNA密码系统，是在该领域的有益探索， 从一个方面揭示了DNA技术在信息科学领域的巨大应用潜力。参考文献Hazay.AutomataEvaluationandTextSearchProtocols[J].BioSystem.2010,116:49-64.M.Danziger,M.A.A.Henriques.ComputationalIntelligenceAppliedon[J].MultimediaToolsandApplications.2012,70(3):1439-51.XFang.DNA-Chip-Based InformationHidingScheme[J].CCIS472,pp.123—27,2014.梁超,杨静，张成.DNA密码研究现状及展望[J].信息网络安全,2015,(1):66-71.⑸徐素梅.DNA计算在DNA密码中的应用研究:(硕士学位论文).合肥：安徽理工大学，2013JohnS.Aunifiedviewofpolymer,dumbbell,andoligonucleotideDNAnearest-neighborthermodynamics.2013,116：49-64.牛莹,张勋．一种基于DNA序列运算的信息隐藏方案[J]轻工学报，2016,31(1)：61 －66．张勋才．基于DNA分子的信息安全技术研究综述[J].轻工学报,2016，31(1)： 67－74．韩栋.基于DNA微纳技术的信息隐藏算法与模型设计研究 :(硕士学位论文).郑州：郑州轻工业学院，2015王燕.基于DNA芯片和微点技术的信息安全算法研究 :(硕士学位论文).郑州：郑州轻工业学院，2015蒋君.基于DNA计算的DNA密码系统研究:(硕士学位论文).合肥：安徽理工大学，2013AnusudhaK,VenkateswaranN,ValarmathiJ.SecuredmedicalimagewatermarkingwithDNAcodec[J].MultimediaToolsandApplications.2016.ChavesJM,Vega-RodriguezMA.DNAstrandgenerationforDNAcomputingbyusingamulti-objectivedifferentialevolutionalgorithm[J].BioSystems.2014,116:49-64.Chaves-Go