下载掌阅APP，畅读海量书库
立即打开
RSA算法的核心是大整数分解。在过去数十年中，许多学者对该难题进行了研究，提出了诸如二次筛选法、椭圆曲线算法、数域筛选法等一系列的算法，在这个方向上做出了一些成绩。但是，从20世纪90年代至今，算法或架构上并没有跨越性的新突破。这是RSA算法成立的重要基础。在花费大量财力和物力、组织大规模计算能力的前提下，目前已有学者提出可以分解512位甚至是768位长度的大整数。有研究表明，分解算法每十年约能多提升100位的分解长度。到目前为止，分解1024位乃至更大的整数在工程实现上基本是不可能的。因此，RSA一般选择1024或2048位的大整数长度。
ElGamal利用的离散对数问题也是数学难题。如果在集合 Z p 中遍历地寻找密钥 d ，其复杂度为2 p 。ElGamal算法一般选择 p 为1024位或2048位，这意味着暴力破解基本是不可能的。离散对数也有相应的通用算法，例如Shanks算法和Pohling-Hellman算法等。研究表明，这些算法的计算复杂度不低于2 ( p /2) 。
在密钥长度相同的情况下，椭圆曲线的破解是最困难的。椭圆曲线的基本运算（求“和”是在曲线上做点的映射）比RSA和ElGamal复杂得多，因此一般认为密钥长度为160位的椭圆曲线算法和密钥长度为1024位的RSA/ElGamal算法安全性相当。实际中，常用的椭圆曲线算法密钥长度为256位。