基于Chebyshev多项式的公钥密码算法安全性及猫映射周期分布分析

摘要

本论文讨论两个问题：第一，分析NZ上基于Chebyshev多项式的公钥密码算法的安全性；第二，分析猫映射的周期分布，该问题直接来源于第一个问题的深入研究。
　　对于第一个问题，本论文通过NZ上一维线性递归序列对该密码算法进行建模，分析了Chebyshev多项式迭代序列的周期分布。研究结果表明：若密码算法的参数选择不合适，对于素数N以及一般的合数N，该序列都存在较小的周期。较小的周期意味着该算法存在安全弱点，基于此，本论文给出了对该算法的一种穷举攻击，该攻击可以发现等效的私钥，即该密码算法被攻破。为有效地防止这种攻击，本论文建议了一些合适的参数选择方法，在合适的参数下，证明了该密码算法在选择明文攻击下的安全性介于离散对数问题（DL）及计算Diffie-Hellman问题（CDH）之间。同时，本论文对该算法进行了一些改进，使得该算法可以应用于真实的世界，但改进后的算法在IND-CCA2下的安全性是今后待解决的问题。
　　对于第二个问题，本论文通过NZ上二维线性递归序列对猫映射迭代进行建模，将猫映射周期分布问题规约为其迭代序列的周期分布问题，进一步将该问题规约为其最小多项式的周期分布问题。首先，对于一般的合数N，本论文讨论了其周期结构，研究结果表明其周期为猫映射在其素数分解的因子上周期的最小公倍数。然后，本论文分析了N为素数、2eN=及Npp=>为素数时猫映射的周期分布，e,3获得了精确的解析解。N为素数时解决方法的核心是将有限域上多项式的周期分布分析规约为其根的阶的分布分析；2eN=时解决方法的核心是将Galois环上多项式的周期规约为有限域上该多项式的周期，然后通过Hensel提升将有限域上的结果提升至Galois环，进而得出周期分布结果；Npp=>时解决方法的核心是将e,3Galois环上多项式的周期分布分析规约为其根的阶的分布分析；后两种情况较复杂，且周期分布问题不总能规约到多项式的周期分布分析。此时，本论文将猫映射矩阵进行p进制展开，然后利用Hensel提升得出了较满意的结果。至此，猫映射周期分布的核心问题获得了圆满的解决。
　　对于上述两个问题，本论文都得出了较为深刻的结果。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 研究背景、意义及内容

1.2 当前研究概况

1.3 论文组织

2 基础知识

2.1 基本符号

2.2 基于Chebyshev多项式的公钥密码算法

2.3 猫映射

2.4 有限域上线性递归序列相关理论

2.5 总结及注记

3 基于Chebyshev多项式的公钥密码算法安全性分析

3.1 基本思想

3.2 N为素数时基于Chebyshev多项式的公钥密码算法安全性分析

3.3 N为合数时基于Chebyshev多项式的公钥密码算法安全性分析

3.4基于Chebyshev多项式的公钥密码算法的改进

3.5 总结及注记

4 猫映射周期分布分析

4.1 问题定义及解决方案

4.2 N为素数时周期分布分析

4.3 N ? 时周期分布分析2e

4.4 N p? 时周期分布分析e

4.5 总结及注记

5 论文总结及进一步的工作

5.1 本论文的贡献

5.2 进一步的工作

致谢

参考文献

附 录

A. 作者在攻读学位期间发表的论文目录：

B. 作者在攻读学位期间取得的科研成果目录：