基于改进Coppersmith算法的RSA安全性分析

发布时间：2020-06-15 23:58

【摘要】：RSA作为一种成熟的公钥密码体制,不仅能够用于加密,同时还能用于签名,在提出后的四十年时间里,被广泛应用于金融、通信、互联网应用、电子商务等领域。LLL算法是由A.K.Lenstra、H.W.Lenstra和L.Lovasz于1982年提出的一种在多项式时间内求格的近似最短向量的算法。1996年,Coppersmith发现可以利用LLL算法解决RSA安全性分析的问题,之后各种相关算法被应用于RSA的研究,取得了大量的成果。基于现有求解多变元多项式方程小根的思想,提出一种改进的方法。首先利用Coppersmith方法的推广求出与待求解多项式具有相同根的多项式,再构造包含已有多项式信息的格,利用LLL格基约化算法,寻找与已有多项式算术独立并且具有相同根的多项式,最后利用结式的方法求解多项式的小根。针对RSA在对称加密体系中用于密钥交换的应用场景,分析了模板消息攻击,将问题转化为求解多变元多项式模方程在满足一定条件下的小根的问题,使用Coppersmith求解单变元模方程方法的推广,结合LLL算法,求解出消息的未知部分。针对小解密指数攻击,构建数学模型,将问题转化为求解一种形式较为简单的三变元多项式在整数域上的小根的问题,利用改进的算法,求解出多项式的小根,通过分析求解过程,归纳出使用该方法攻击RSA模型需要满足的条件。实验表明,在现有的PC机的硬件条件下,对于模数为1024bit并且解密指数足够小的RSA模型,使用上述改进的求解多变元多项式方程小根的方法,能够在极短的时间内攻破RSA模型。
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TN918

【参考文献】