有限自动机公钥密码的研究与实现

论文摘要

有限自动机公钥密码(FAPKC)是我国学者提出的一种基于有限自动机可逆性理论的公钥密码体制，是国际上第一个时序公钥密码体制。由于只涉及逻辑运算，与其他主流的公钥密码体制相比，其具有实现简单、运算速度较快的优势，自提出以后，受到了密码学界广泛关注。迄今为止，已经有6种以上基于有限自动机理论的公钥算法被提出。同时随着有限自动机理论的发展，FAPKC也面临着更深入的分析和应用。有限自动机公钥密码在发展过程中，其算法从最早提出的FAPKCO发展到最新的FAPKC3及其变型FAPKC4；目前已知针对FAPKC的攻击和分析方法有：约化梯阵攻击、线性R_aR_b攻击、随机搜索攻击等。本文对这几种算法变型及密码分析成果进行了全面的总结。本文的主要工作有以下几点：一、从随机搜索攻击的角度出发，对FAPKC3的安全性进行了分析，用约化梯阵方法对自动机方程进行线性解析，基于等价的线性RaRb变换，提出了攻击算法RSS，估算了成功率的下界，该攻击算法比以往的搜索算法具有更高的搜索成功率和普适性。二、分析了采用传统的“向量与”非线性算子在抵抗随机搜索攻击方面的弊端，使用Meskanen的“上三角矩阵”构造法生成非线性分量自动机，给出了新的非线性算子构造。同时对改进的密钥生成方法进行了算法的软件仿真和分析；该算法保持原来有限自动机公钥密码算法的安全性，同时实现更简单。本文最后讨论了尚未解决的问题和展望了未来进一步的工作。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 公钥密码学基本理论
• 1.2 有限自动机公钥密码的研究
• 1.3 本文研究内容与结构
• 第2章 有限自动机可逆性理论
• 2.1 基本概念
• 2.2 复合有限自动机
• 2.3 有限自动机的可逆性
• aR_b变换'>2.4 R_aR_b变换
• 第3章 有限自动机公钥密码体制
• 3.1 FAPKC0
• 3.1.1 FAPKC0的密钥生成
• 3.1.2 FAPKC0的加解密
• 3.1.3 FAPKC0的签名
• 3.2 FAPKC1与FAPKC2
• 3.2.1 FAPKC1
• 3.2.2 FAPKC2与基于身份的密码体制
• 3.3 FAPKC3及其变型
• 3.3.1 FAPKC3的密钥生成
• 3.3.2 FAPKC3的加解密
• 3.3.3 FAPKC3的签名
• 3.3.4 FAPKC4简介
• 第4章 FAPKC的密码分析
• 4.1 FAPKC0及其变型的破译
• 1攻击'>4.1.1 PAL₁攻击
• +攻击'>4.1.2 AτM及AτM⁺攻击
• 4.2 FAPKC3的密码分析
• 4.2.1 约化梯阵方法
• 4.2.2 非线性核攻击
• aR_b攻击与线性R_aR_b变换筛'>4.2.3 线性R_aR_b攻击与线性R_aR_b变换筛
• 第5章 FAPKC3的搜索攻击分析与改进算法
• 5.1 FAPKC3的搜索攻击分析
• 5.1.1 符号与一些结果
• 5.1.2 随机搜索算法及讨论
• 5.2 改进的密钥生成算法
• 5.2.1 "上三角矩阵"算法
• 5.2.2 非线性算子的构造
• 5.2.3 算法的安全性讨论
• 5.3 算法的软件实现
• 总结与展望
• 全文总结
• 进一步的工作
• 致谢
• 参考文献
• 附录:算法实现部分源代码
• 攻读硕士学位期间发表的论文