20世纪70年代末，RSA的发明使大整数的因子分解问题变得突出，从而也产生了许多如 3.7 一节所述的改进因子分解方法。1984年，Hendrik Lenstra Jr 发出了一份手稿，描述了一种使用椭圆曲线的新因子分解方法。Lenstra算法《Factoring integers with elliptic curves》，本质上是对 Pollard’s p−1因子分解算法在椭圆曲线上的应用，其利用了 中的点的数量随着选择不同的椭圆曲线而变化的事实。我们将在 6.6 一节进行介绍。尽管对于密码学中的因子分解问题，Lenstra的算法不如筛选方法有效，但它有助于将椭圆曲线引入密码学界。
因子分解算法对密码学的重要性在于其可以被用来破坏 RSA 和其他类似的密码系统。1985年，Neal Koblitz和 Victor Miller 独立提出使用椭圆曲线创建密码系统。他们认为，椭圆曲线离散对数问题可能比模 下的经典离散对数问题更困难。因此，如第 6.4 节所述的使用椭圆曲线实现的 Diffie–Hellman 密钥交换和 Elgamal 公钥密码系统，仅需要比 RSA 更小的密钥，从而运行效率也更高。
Koblitz 和 Miller 都将他们的想法作为学术论文发表，但他们都没有追求椭圆曲线密码学在商业方面的应用。事实上，当时几乎没有关于 ECDLP 的研究，因此很难说 ECDLP 确实比经典 DLP 困难得多。然而，Scott Vanstone 和 Ron Mullin注意到了后来被称为椭圆曲线密码术（ECC）的潜力，他们于1985年创办了一家名为Certicom 的密码公司。他们与学术界和商界的其他研究人员一起推广 ECC，将其作为 RSA 和 Elgamal 的替代品。
但事情的发展并非一帆风顺。例如，在20世纪80年代末，各种密码学家提出使用所谓的超奇异椭圆曲线来提高效率，但在1990年，MOV算法（见第6.9.1节）表明，超奇异曲线很容易受到攻击。一些人认为这是整个 ECC 体制存在的问题，而另一些人则指出，RSA 也有必须避免的薄弱实例，例如，RSA 必须避免使用容易遭到 Pollard’s p−1方法攻击的数字。
ECC是否为RSA提供了一种安全有效的替代方案，这一纯粹的数学问题因存在商业和财务问题而蒙上了阴影。为了在商业上取得成功，加密方法必须标准化，以便在通信和银行等领域使用。RSA 最初处于领先地位，因为它是最早发明的，但 RSA 获得了专利，一些公司抵制由贸易组织或政府机构批准的标准：应该强制使用专利技术的想法。Elgamal 在1985年发明后，提供了一种免版税的替代品，因此许多标准将 Elgamal 指定为 RSA 的替代品。与此同时，ECC 的地位越来越高，但即使在1997年，也就是 ECC 推出十多年后，主要专家也仍然对 ECC 的安全性表示怀疑。
目前密码学领域的一个主要困境是，没有人知道它所基于的所谓难题的实际难度。目前，公钥密码系统的安全性取决于专家对整数分解和离散对数等问题的难度的看法和共识。可以说的是，“这样那样的问题已经被广泛研究了N年，这里有已知最快的解决方法。”基于因子分解的密码系统的支持者指出，从某种意义上说，人们自古以来就试图对数字进行因子分解；但事实上，现代因式分解理论需要高速计算设备，而且几乎都是在RSA发明之后开始发展。对椭圆曲线离散对数问题的认真研究始于 20 世纪 80 年代末，因此现代因子分解方法在 ECDLP 上有10–15年的起步时间。在第 7 章中，我们将描述公钥密码系统（NTRU，GGH），其安全性基于格理论中的某些难题。自19世纪以来，格已经被广泛研究，但现代计算算法的发明和分析要晚得多，是由 Lenstra, Lenstra, 和 Lov´asz 在20世纪80年代初的基础工作发起的。格在 20 世纪 80 年代作为密码分析的工具出现，在20世纪90年代作为创建密码系统的手段出现。
RSA是第一个公钥密码系统，由其发明人获得专利。密码学中的专利问题充满了争议。有人可能会说，从1983年到2000年的RSA专利要求用户支付许可费，从而阻碍了密码学的使用。然而，为了建立一家公司，发明家需要愿意冒资金风险的投资者，如果有独家产品可供选择，筹集资金也会容易得多。此外，RSA最初是“only game in town”，这意味着它自动受到了学术界的广泛审查，这有助于验证其安全性。
ECC的发明和最终的商业实现遵循了不同的路径。由于 Koblitz 和 Miller 都没有申请专利，ECC的基本思想变得可以免费供所有人使用。这导致 Certicom 和其他公司申请专利，从而改进了ECC的基本理念。其中一些改进是基于重要的新研究理念，而另一些则没有那么创新，几乎可以被定性为常规的家庭作业问题。不幸的是，美国专利商标局（USPTO）没有有效评估其收到的大量加密专利申请的专业知识。其结果是，即使假设所有已颁发的专利都能经受住法律挑战，市场上仍存在大量不确定性，即哪些版本的ECC是免费的，哪些版本需要许可证。
原文始发于微信公众号（山石网科安全技术研究院）：密码学 ｜ 6.5 公钥密码学的发展
