分布式计算环境下大整数分解的研究

摘要

大整数分解问题历来是数学家们关注的热点问题。随着信息技术的飞速发展，以RSA为代表的公钥密码体制得到了广泛的应用。RSA的安全性基于大整数分解是困难的这一命题，即：找到两个大素数并计算它们的乘积是容易的，而知道这个乘积逆向求它的因子是困难的。 随着计算机硬件水平的提高和分解算法的发展，大整数分解的速度得到了极大提高。因此，在过去的十年中，RSA的密钥长度从512位提高到1024位，对于长久保存的信息则要求使用2048位。此外，分布式计算技术的发展也极大的推动了分解能力的提高。其中，作为分布式计算技术的典型代表，由Ian Foster博士在上个世纪90年代提出的网格计算代表了计算机分布式技术的发展水平。 本文以大整数分解算法和网格计算技术的研究为基础，对多个多项式的二次筛法（MPQS）的分布式实现技术进行了重点研究。针对算法实现过程中的小乘因子选取、分解参数的选取、多项式的生成等问题，进行了深入的分析和讨论；通过对参数及结果传递的各种方案比较，结合网格计算和MPQS的特点，提出了自己的解决方案，并给出了具体实现。 从实现的结果可以看出，该分布式实现方案在筛法部分获得了比较好的并行性，达到了预期的效果。本文工作也进一步说明，作为密码分析的有利工具，分布式计算技术的发展也为密码设计提出了更大的挑战，提高密码算法的安全强度迫在眉睫。