生物密码系统及面向密码学问题的DNA计算研究

摘要

自Adleman在1994年首次提出了哈密尔顿路径问题的DNA算法以来， DNA计算作为一种新型计算方法，目前在理论和实践方面取得了若干初步成就。利用DNA反应本质的并行特性，DNA计算表现出巨大的并行运算能力，在未来有很大的发展空间。
　　随着DNA计算的发展，生物密码体制亦成为密码学研究的新领域。当前传统密码体制的安全性多基于计算困难问题，如整数分解问题和离散对数问题，若在未来可找到这些问题的有效计算方法，相关密码体制的安全性将受到巨大威胁。而生物密码体制安全性并不依赖于计算困难问题，因此并不受计算能力发展的影响，故而可作为传统密码体制的补充。
　　本文研究内容分为两方面，一是面向密码学问题的DNA计算研究。离散对数问题在现代密码学中扮演重要角色。Di?e-Hellman密钥交换、ElGamal类加密和签名等密码体制的安全性都基于离散对数问题的计算困难性，若该问题在未来被攻破，则依赖该问题的密码体制安全性都将受到威胁。我们利用DNA计算的并行运算能力，以Tile自组装DNA计算模型为工具，设计离散对数问题的多项式时间DNA算法。同时，在相关子系统的设计上，比前人的方法有一定优化。具体研究成果及创新性如下：
　　1-首次给出Tile自组装模型下多项式时间非确定性离散对数算法。算法非确定性随机选择指数x，并行地计算ax mod p，并与y进行比较，求解满足ax≡y(mod p)的x。对于np位模数p，系统组装时间为O(n3p)。此前的方法系统组装时间为指数时间O(2np)，相比较之下，本文的方法在组装时间上有显著改进。
　　2-给出两个Tile自组装模型下乘法系统新的实现，系统所需Tile大小分别为24与16。相比起此前Brun提出的Tile集大小为28的乘法系统，本文提出的系统在Tile集大小上有所优化。
　　3-首次给出Tile自组装模型下直接求模运算的系统：给定nA、nB位大小的整数A与B，系统直接计算A mod B。最坏情况组装时间为Θ(nA(nA?nB))，最好情况组装时间为Θ(nA)。相比起此前用除法求余数的方法，本文所提出系统在组装时间上有所优化。当nA远大于nB时，本系统的优势较为明显。
　　4-针对此前的乘法系统无法在其他子系统最终配置上直接运行的瓶颈，本文给出一种可在其他运算模块结果上进行连续运算的平方系统。故而在整个运算过程中，无需中断自组装反应便可进行平方运算。
　　5-此外，本文提出一种线性自组装模减法算法，算法中实验步骤为常数步。
　　本文研究工作的第二部分面向生物密码体制。针对基于DNA芯片的密码体制进行研究，探索其区别于传统密码体制的特殊性质，并利用特殊性质实现相关应用。具体研究成果如下：
　　1-首次实现基于DNA芯片的公钥密码体制DNA-PKC并以实验验证。其安全性基于生物学困难问题“获取DNA芯片微点上长度相同混合探针的精确信息困难”，并不独依赖于计算困难问题，相比起传统体制提供了另一层安全性。同时给出其特殊性质“加解密钥具有多对多关系”。
　　2-围绕“加解密钥具有多对多关系”这条特殊性质展开，首次给出基于DNA芯片的动态广播加密方案DNA-DBE。相比起传统广播加密方案，DNA-DBE的优势在于密文和解密钥的复杂度皆为常数，与用户数无关。且具有后向安全性。
　　3-引出新性质“不同的明文消息可以对应相同的密文”，首次给出基于DNA芯片的信息隐藏方案DNA-IH。传统信息隐藏方案中隐密消息嵌入载体后，将引起载体特征统计分布的变化。而DNA-IH中普通消息所对应的芯片与嵌入隐密消息后所对应的芯片完全一致，因而无法通过统计攻击等手段检测隐秘消息的存在性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 DNA计算

1.2 密码学的新领域：DNA密码

1.3 本文的组织安排和创新点

第二章 预备知识

2.1 DNA分子的构成方式与实验基础操作

2.2 DNA计算示例

2.3 Tile自组装模型定义

2.4 小结

第三章 基于线性自组装的DNA减法模运算

3.1 DNA减法算法原理

3.2 范例

3.3 算法的性质

3.4 本章小结

第四章 基于Tile自组装模型的乘法算法

4.1 序言

4.2 子系统

4.3 乘法系统

4.4 讨论

4.5 本章小结

第五章 基于Tile自组装模型的模运算算法

5.1 基础算法

5.2 子系统

5.3 模系统Smod

5.4 本章小结

第六章 基于Tile自组装模型的多项式时间离散对数算法

6.1 研究背景

6.2 基础算法

6.3 平方运算系统

6.4 模乘系统

6.5 验证系统

6.6 提取系统

6.7 离散对数系统

6.8 本章小结

第七章 基于DNA芯片的公钥密码体制

7.1 DNA芯片技术

7.2 生物学困难问题

7.3 非对称加密算法DNA-PKC

7.4 签名与验证

7.5 实现方法

7.6 讨论

7.7 本章小结

第八章 基于DNA芯片的动态广播加密系统

8.1 广播加密体制

8.2 系统构造

8.3 实验可行性

8.4 讨论

8.5 本章小结

第九章 基于DNA芯片的信息隐藏

9.1 方案的提出

9.2 方案构造

9.3 流程示例

9.4 讨论

9.5 本章小结

第十章 结论与未来研究方向

10.1 本文工作总结

10.2 未来的研究方向

10.3 小结

参考文献

致谢

攻读学位期间发表的学术论文目录

答辩决议书