基于整数格的短公钥、长私钥指数RSA算法的密码分析

公钥密码算法RSA是国际上最成功的密码体制之一，至今仍被广泛应用于各国政府，军队，商业等各行业。我们的研究内容就是对RSA算法进行密码分析，研究短公钥e(小于模长的一半)、长私钥d且满足一定条件下的攻击方法。基于整数格理论，提出一种有效算法求出私钥d和模N的因子，分析满足限制性条件的公钥和私钥在实际应用中存在的概率及各参数之间的关系。这包括研究整数格的基函数选取，小逆问题本身的变形以及试验结果和理论分析。二是从代数的角度进一步研究LLL算法以及由LLL算法得到的归约基各基的界和它们分量的界。三是研究N的因子分解问题，对于任意一个已知的RSA模N，研究如何构造公钥使得私钥满足我们的算法条件达到分解N，并将给出算法的实验与应用结果。解决RSA算法中短私钥，长公钥（与N等量级）不能破解的科学问题，我们得到的预期结果将会对RSA算法构成致命的或一定的威胁，使得更具有实际应用意义。

我们对RSA公钥密码算法中的短公钥e、长私钥d的情况进行了密码分析，取得了重要成果，完成了基金项目中预期的目标任务，取得了如下成果：（1）. 在公钥e和私钥d满足一定模关系的情况下，即d<N且公钥e在N的指数0.258到0.284范围内，我们能够破解RSA密码系统。并且分析了各参数之间的关系，在参数满足一定条件下时也能破解RSA密码系统，即我们把私钥推广到d=N的一般短公钥RSA系统。此外，我们分析了找到弱密钥的概率，对于给定的公钥（N,e）和私钥d，给出了找到满足参数范围内的不等式中的的概率表达式。（2）在一定的假设下，我们分析了找到弱密钥的各参数之间的关系，在参数范围内，找到满足关系的d的概率可以大大提高。（3）对Boneh-Durfee算法可破解的私钥的理论上界进行了研究。指出了边界估算存在误差。对于1024 bits 的 RSA 系统，边界修正为N的指数为0.277，且分析了公钥长度与私钥边界的关系。（4）. 我们对部分密钥泄露攻击进行了研究。1997年，Don Coppersmith在J.Cryptology发表了一篇文章，分析了部分密钥泄露攻击。 如果p或q的高位bit泄露，例如：p或q的长为N的四分之一长bits 泄露，那么可以分解N。我们对此进行了研究，获得了重要成果，即对于p或q的N的七分之一长bits 泄露，那么可以分解N，这大大缩短了p或q的长度要求。（5）我们进一步研究了一般多变量线性模方程的求解问题，提出了一种概率分析方法，能够对70个未知数以内的多变量线性模方程求出给定范围内的较短解。与现有的算法相比，该方法的效率和准确性都得到了明显改善。. 我们负责举办了两次密码学领域的学术交流，邀请了中国科学院数学所，高能物理研究所信息安全实验室，北京大学，总参三部，中办等相关人员进行了深入的学术交流。我们参加了总参三部主持的有关密码分析学术交流，并在会议上做了相关的报告。2012年在武汉举办的密码学年会上发表了我们的部分结果。. 我们培养了1名博士生和7名硕士生，发表了论文2篇，其中SCI论文1篇。内部论文2篇。还有部分重要成果将在后续发表（有些需要保密），由于数据量大，计算耗时，程序调式复杂，有些结果目前正在计算实验中。