量子计算是利用量子力学原理和计算机科学进行计算的计算模式,它利用量子系统的叠加性,纠缠性和相干性等实现量子的并行计算.由于量子计算的独特性,使得它逐渐引起数学家,物理学家,计算机科学家们的广泛关注.量子算法的提出给现有的公钥密码体制带来了严峻挑战.目前对密码学最具威胁的两类量子算法是Shor算法和Grover搜索算法.Shor算法能够在多项式时间内求解整数分解问题和离散对数问题,这使得当前应用广泛的RSA,ElGamal和ECC等公钥密码体制在量子计算环境下不再安全;Grover搜索算法是一种通用的量子搜索算法,为一大类搜索问题的解决提供了平方根加速,相当于将密钥长度减半,从而威胁到现有的密码体制.公钥密码体制在量子计算环境下的安全性分析无论是在理论上还是实际应用中都具有重大研究意义,特别是广泛使用的RSA,ElGamal和ECC等公钥密码体制的安全性更值得我们深入研究.现代公钥密码体制是基于计算数论中的困难问题设计的,而整数分解问题是计算数论中的重要困难问题.如今广泛用于电子银行、网络等领域的RSA公钥密码体制的安全性正是基于整数分解的难解性设计的.之所以RSA密码体制难以破译,就是因为它所依赖的整数分解问题不能快速解决.本文针对RSA公钥密码体制的特点,分别基于方程求解,相位估计,不动点性质以及密文周期函数提出攻击RSA的量子算法,主要的研究内容和成果包括:(1)提出基于方程求解与相位估计攻击RSA的量子算法.经典的因子分解算法是通过求解同余方程α2≡β2(mod n)实现的.据查证,目前还没有求解此方程的量子算法,故本文试图从量子计算的角度提出解决此同余方程的量子算法4.该算法是对经典求解同余方程α2≡β2(mod n)的量子化实现.虽然该算法的计算复杂性是亚指数的,但这是第一个求解同余方程的量子算法,且算法的成功概率接近于1.为进一步降低时间复杂度,本文从非因子分解角度出发,基于量子傅里叶逆变换和相位估计,给出算法5.同Shor算法相比,算法5不需要分解n,从RSA密文C直接恢复出明文M,具有多项式时间复杂度,且成功概率高于Shor算法攻击RSA的成功概率,同时不必要满足密文的阶为偶数的限制.(2)提出基于不动点攻击RSA的量子算法.基于RSA不动点的性质,利用量子计算技巧将不动点攻击问题转化为求函数周期问题.基于量子傅里叶逆变换和相位估计,提出一个新的攻击RSA的量子算法.分析表明新提出的算法不通过因子分解直接从密文中恢复出明文,且算法的成功概率高于Shor算法攻击RSA的成功概率.(3)提出基于密文周期攻击RSA的量子算法.基于密文函数f(x)= Cx(mod n)的周期性,利用量子傅里叶变换求得的RSA密文函数f(x = Cx(mod n)的周期r.再结合数论相关知识,就能恢复出RSA明文M.在此避开了元素的阶为偶数和因子是n的平凡因子,给出一个对抗RSA密码体制的唯密文攻击,新算法的成功概率高于Shor算法攻击RSA的成功概率.