论文部分内容阅读
RSA算法是一个广泛应用的公钥密码体制,在公钥密码学领域有着深远影响。随着格理论的发展与LLL算法的提出,基于格基约化技巧的密码分析技术逐渐成为研究公钥密码算法安全性的重要数学工具。针对RSA算法的格分析技术通过提炼密钥信息含有的代数关系,将安全性分析转化为在多项式时间内求解模方程或整方程的小根。在本文中,我们利用格分析技术和以其为基础的格优化分析技巧,重点关注RSA及其变体算法的安全性分析,拓展、改进并优化了前人的分析结果,同时提出新的问题并给出研究结果。本文的主要成果与创新点如下:1.针对小加密指数的标准RSA算法,我们应用线性化技巧求解三变量模方程得到了小指数攻击的新拓展分析结果。我们的方法克服了已有工作中小加密指数受限的不足之处,使得小解密指数攻击可适用于任意小加密指数情形。2.针对使用多对加解密指数对的PP-RSA变体算法,我们通过联立求解特定模方程组,应用指数优化技巧得到了小指数攻击的新拓展分析结果。我们的方法考虑了更多的加解密指数对,从而改进了之前的攻击结果。3.针对使用改性欧拉函数的MEQ-RSA变体算法,我们给出了小指数攻击的精确适用范围。我们分析了使用多对加解密指数对的情形,应用Minkowski和技巧求解模方程组,得到了小指数攻击的新拓展分析结果。4.针对存在素数差的MP-RSA变体算法,我们指出当素因子个数增多时模数分解攻击比小解密指数攻击更为有效。随后通过整方程方法与线性化技巧得到了优化分析结果,提高了素数差的不安全界。5.针对一般RSA模数的已知比特分解问题,通过求解特定形式的双变量整方程,我们给出了该问题的统一求解条件。该条件既可以覆盖之前所有已知结果,又能够进一步给出优化分析结果。6.提出隐式相关私钥分解问题并对其进行研究。隐式相关私钥分解问题可以看作隐式分解问题与部分私钥泄露攻击的混合模型。通过应用分裂技巧与线性化技巧,我们将私钥转化为多个更小未知变量的线性组合,随后求解模方程得到隐式信息的不安全界。该分析结果可以给隐式相关私钥的使用提供理论上的安全性要求。