几类快速公钥密码的设计与分析

论文摘要

传统的公钥密码算法速度比较慢，这制约了公钥密码的广泛应用。国内外密码学界都在加强快速密码算法的研制与开发，以便使公钥密码能够应用到更广泛的环境中。在快速公钥密码这一研究领域，本文取得了如下成果： （1）找到了一类新的易解背包问题，并用此问题构造了一个背包型加密算法。该算法是第一个基于背包问题的概率加密方案。证明了该算法能够抵抗低密度攻击和联立丢番图逼近攻击等。而且该算法的加解密计算复杂度是二次的。 （2）找到了RSA公钥密码算法的一类弱密钥，指出如果RSA数的两个素因子的比值能够被一个小分数有效逼近的话，则RSA数是容易分解的。 （3）使用中国剩余定理构造了一个快速公钥加密算法，证明了攻击者重构陷门信息等价于求解两个数论困难问题，即整数分解和联立丢番图逼近问题。 （4）对RSA问题进行了推广，提出了广义RSA问题，给出了广义RSA问题与RSA问题之间的联系。并用此问题构造了一个具有双重陷门解密机制的公钥密码算法GRSA。证明了GRSA是单向的当且仅当广义RSA计算问题是困难的，GRSA是选择明文攻击下语义安全的当且仅当广义RSA判定问题是困难的。 （5）构造了一个安全性基于两个数学困难问题的公钥密码算法，该算法的安全性同时基于整数分解和联立丢番图逼近困难问题，而且该密码算法的加解密计算复杂度是二次的。 （6）使用矩阵环上的一个特殊的组合问题构造了一个公钥加密算法，其安全性与整数分解问题有关，但并不直接依赖于整数分解问题，而是依赖于一类特殊的矩阵组合问题。 （7）从辫群上求根问题的困难性出发构造了一个数字签名方案，证明了攻击者能够成功地伪造一个签名当且仅当他能够求解辫群上的求根问题。而且从该数字签名方案出发构造了一个基于身份的数字签名方案。 （8）对公钥密码算法Naccache-Stern进行了安全性分析，指出该算法的解密可以看作一个群分解问题，并说明了该攻击算法攻击成功的概率依赖于把一个随机的自然数转化成一个光滑数的概率。 （9）对2000年ACISP会议上的一个快速公钥密码算法进行了安全性分析，给出了该算法的安全性与联立丢番图逼近问题以及格上的最小向量问题之间的关系。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 公钥密码学的现状
• 1.1.1 关于主流公钥密码的几点事实
• 1.1.2 公钥密码学的研究热点
• 1.2 快速公钥密码的发展现状
• 1.2.1 影响公钥密码算法效率的几个因素
• 1.2.2 快速公钥密码的发展现状
• 1.3 关于可证明安全性的几点注解
• 1.4 内容安排及主要结果
• 1.5 符号说明
• 1.5.1 符号
• 1.5.2 几点说明
• 第二章 概率陷门背包
• 2.1 引言
• 2.2 预备知识
• 2.2.1 格
• 2.2.2 背包密度
• 2.2.3 低密度子集和攻击
• 2.2.4 联立丢番图逼近
• 2.3 一类新的易解背包问题
• 2.3.1 一个易解的紧凑背包问题
• 2.3.2 联立紧凑背包问题的推广
• 2.4 背包型概率加密算法
• 2.4.1 密钥生成算法
• 2.4.2 加密算法
• 2.4.3 解密算法
• 2.4.4 几点注解
• 2.4.5 一个实际的应用方案
• 2.5 参数选取和性能分析
• 2.5.1 参数选取
• 2.5.2 关于密钥生成
• 2.5.3 计算复杂度
• 2.5.4 信息率
• 2.6 安全性分析
• 2.6.1 关于求解Cracking问题
• 2.6.2 关于求解Trapdoor问题
• 2.6.3 关于生成最困难的背包问题
• 2.7 本章小结
• 第三章 整数分解及其在快速公钥密码中的应用
• 3.1 RSA的新的弱密钥
• 3.1.1 引言
• 3.1.2 一个新的分解RSA数的特适算法
• 3.1.3 分解RSA数
• 3.1.4 RSA的新的弱密钥
• 3.2 使用中国剩余定理构造的快速公钥加密算法
• 3.2.1 公钥体制描述
• 3.2.2 参数说明及性能分析
• 3.2.3 安全性分析
• 3.3 具有双重解密机制的可证明安全的公钥密码算法
• 3.3.1 引言
• 3.3.2 广义RSA问题
• 3.3.3 GRSA公钥密码算法
• 3.3.4 GRSA的可证明安全性
• 3.3.5 参数说明
• 3.3.6 几点注解
• 3.4 一个基于整数分解和联立丢番图逼近问题的公钥密码算法
• 3.4.1 引言
• 3.4.2 公钥密码算法描述
• 3.4.3 性能分析
• 3.4.4 安全性分析
• 3.5 本章小结
• 第四章 组合代数公钥密码算法
• 4.1 引言
• 4.2 组合矩阵公钥密码算法
• 4.2.1 算法描述
• 4.2.2 参数选取
• 4.2.3 性能分析
• 4.2.4 比较
• 4.2.5 安全性讨论
• 4.3 基于辫群上的求根问题的数字签名算法
• 4.3.1 辫群
• 4.3.2 一个传统的数字签名算法
• 4.3.3 一个基于身份的数字签名算法
• 4.3.4 安全性分析
• 4.4 本章小结
• 第五章 两个快速公钥密码算法的安全性分析
• 5.1 公钥密码Naccache-Stern的安全性分析
• 5.1.1 引言
• 5.1.2 攻击算法
• 5.1.3 关于攻击算法的几点注解
• 5.2 对一个快速公钥密码算法的丢番图逼近攻击
• 5.2.1 引言
• 5.2.2 方案描述
• 5.2.3 格攻击
• 5.2.4 联立丢番图逼近攻击
• 5.2.5 两种攻击方法的比较
• 5.2.6 几点注解
• 5.3 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间的研究成果