基于DNA计算自组装模型的若干密码问题研究

论文摘要

密码分析和密码设计是信息安全领域最重要的组成部分，它的发展关系到国家安全、经济安全和金融安全等多个方面。现代密码系统的安全性是建立在密钥搜索的指数增长时间复杂度上，而新兴的DNA计算具有超大规模并行性、高密度存储和低能耗等特性，不仅对传统密码安全提出了挑战，同时也为海量信息存储提供了新的存储和加密模式。实验已经证明DNA分子自组装是一种自底向上进行纳米尺度计算的有效机制。1维和2维的自组装作为DNA计算的工具，其并行计算能力已经得到认可，并得到了大量的研究。已经证明1维线性自组装具有正则语言的计算能力，而二维自组装的计算能力是图灵等价的。基于这样的背景，本文以DNA计算中的Tile自组装模型为核心，密码问题为主要研究对象，对DNA计算Tile自组装模型在密码中的各种应用及其有效性进行了探索研究，设计并实现了基于DNA计算Tile自组装的密码系统和密码算法破译模型，定量分析了DNA计算用于密码分析和数据加密的有效性、时间复杂度、空间复杂度。本文主要创新内容如下：首先，实现了基于DNA计算的一次一密密码系统。本文针对DNA计算的并行性和海量存储能力，使用DNA计算中的Tile自组装模型设计实现一次一密密码系统，为海量数据信息的加密存储和传输提供了新的方法。该密码系统包括加密子系统、密文提取子系统、密钥计算子系统和解密子系统，这四个子系统组成了一个完整的密码系统。同时使用已有的生物技术，实现了秘密密钥的安全传输。所有的子系统的Tile类型复杂度为（?）（1），计算时间复杂度为（?）（n）。最后，对该一次一密密码系统的安全性进行了分析，表明基于Tile模型和生物技术实现的密码系统可以保证海量数据的存储和传输安全。第二，基于自组装模型的编程能力，设计了使用自组装模型破译Diffie-Hellman算法的方法。首先根据g mod p，g2 mod p，…，gp-1mod p得到的整数值构建计算Tile，完成整数排列的自组装Tile系统。这里p为素数，g为这个素数的原根。通过PCR和凝胶电泳，可以读出不同的整数对应的g的幂次，即g的离散对数值。通过这样的方法，可以威胁到Diffie—Hellman密钥交换的安全。整个系统使用（?）（p）种Tile类型和（?）（p）的组装时间来完成整数的排列。这个模型对于有限位数的Diffie-Hellman算法是有效的。但是由于Tile种类与输入位数线性相关，因此限制了破译Diffie-Hellman算法的规模。然后，本文利用DNA计算自组装模型的封装编程能力，设计了除法自组装模型，并且充分利用DNA计算分布式并行计算优势，在除法自组装模型中嵌入除数生成系统，构建了非确定性大数分解自组装模型，用于解决大数分解问题。该模型的Tile种类复杂度为（?）（1），时间复杂度为（?）（n2）。该DNA计算实验允许至少1018个除法自组装系统同时进行运算，这些除法系统具有相同的被除数，但是除数是系统随机生成，各不相同。为解决除法完成后商的检测问题，在非确定性大数分解自组装模型中嵌入了判别余数是否为零的判断系统，该系统能够在大量结果中标记出能够整除被除数的除数，通过标记提取出对应的除数和商，完成大数分解。最后分析了这个非确定性自组装Tile模型能成功搜索到目标除数的概率，并且证明了通过增大参加运算的DNA分子的量可以使该概率接近于1。以目前的生物技术，该模型完全可以解决256位的大数分解。进一步，利用自组装自底向上的编程能力和封装能力，设计实现了基于自组装模型的DES和3DES加密算法。通过对DES算法中的轮函数，包括置换、交换、异或等进行封装和巧妙级联，实现了轮函数的循环调用。为了可以使用已知明文-密文对攻击的方法实现DES算法的破译，在DES算法模型中嵌入了主密钥生成系统，利用自组装的并行计算能力可以同时随机生成各不相同的主密钥对已知明文进行加密。本文以简化DES（SDES）作为模版，详细解释了各个函数的设计思想和方法，然后扩展到标准DES和3DES算法上。在已有的加密算法模型上，嵌入主密钥生成系统，随机生成主密钥，利用DNA计算的并行性，使用已知明文-密文攻击方法破译SDES、DES和3DES。最后分析了生物技术的误差率与成功破译DES和3DES加密算法的关系。从结果可以看到，随着生物技术的进一步提高，误差率的减小，自组装模型完全可以使用已知明文-密文攻击方法成功破译DES和3DES算法。最后，利用DNA芯片并行计算和荧光显像的特性，使用DNA生物芯片技术、杂交和酶切构建了XOR函数，并且应用这个技术分析DES算法中S盒子的抗差分密码分析能力。利用荧光图像，可以快速有效地评估S盒子异或输出的统计分布，从而实现对S盒子的抗差分密码分析能力的判断，为改进DES安全性提供了依据。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 DNA计算的基本思想和特点
• 1.2 基于DNA计算的信息安全研究进展
• 1.3 DNA计算自组装模型
• 1.4 本文的创新之处
• 1.5 本文的研究内容
• 2 基于自组装模型的一次一密密码系统
• 2.1 一次一密算法（One-Time-Pads Cryptosystem）
• 2.2 基于DNA计算自组装模型的一次一密算法设计
• 2.3 密钥的安全共享
• 2.4 安全性分析
• 3 基于自组装模型的Diffie-Hellman算法破译
• 3.1 基于DNA计算自组装模型的整数排列算法
• 3.2 Diffie-Hellman算法破译模型
• 4 基于自组装模型的RSA密码破译
• 4.1 正整数除法的运算Tile设计
• 4.2 除法Tile自组装模型
• 4.3 RSA算法破译
• 5 基于DNA计算的DES密码破译
• 5.1 DES算法
• 5.2 使用自组装模型实现DES算法中的各个函数
• 5.3 SDES、DES和3DES的Tile自组装模型
• 5.4 构建模型的三个关键问题
• 5.5 主密钥的非确定性生成方法
• 5.6 误差分析
• 5.7 基于自组装模型的DES破译算法结论
• 5.8 基于DNA计算表面计算的S盒子差分分析
• 6 全文总结和研究展望
• 6.1 全文总结
• 6.2 研究展望
• 致谢
• 参考文献
• 附录1 攻读博士学位期间发表的论文目录
• 附录2 发表论文和学位论文的对应关系
• 附录3 攻读博士学位期间参加的项目