日期：
来源：山石网科安全技术研究院收集编辑：V
6.4 Elliptic Curve Cryptography
How Hard Is the ECDLP
我们在 5.4 一节介绍的碰撞方法可以在所有的群中使用。例如在椭圆曲线 。那么为了解出椭圆曲线下的离散对数问题： ，Eve 随机选择 1 至 之间的整数 和 ，并构造两个列表。当他在两个列表中发现相同元素（碰撞）时，她就能解出 ，因为 那么有 。如我们在 5.4 一节所述，当 是一个稍大于 的数，，此时我们有很大的概率找到碰撞。这样最基础的算法需要大量的存储空间，不过我们也不难在椭圆曲线上运用 Pollard’s 这样几乎不需要额外存储空间的算法。但不论如何，我们都是有算法可以在 步内解决椭圆曲线 上的 ECDLP 的。前面我们已经介绍过很多更快速的解决 中的离散对数问题，如 3.8 一节介绍的 index calculus 算法仅有亚指数的复杂度，即复杂度是 。而我们之所以在密码学中使用椭圆曲线就是因为在椭圆曲线的代数结构中目前还没有发现诸如 index calculus 的解决 ECDLP 的快速算法。下面这一事实非常重要，值得强调目前已知最快的解决 下 ECDLP 的算法大约需要 步因此，ECDLP 要比 DLP 困难。不过回想一下，在 DLP 中有一些素数 会使得 DLP 问题变得非常容易，比如当 是一系列小素数的乘积的时候，那么使用 Pohlig-Hellman 算法就能够快速的解出DLP，所以相应的，也有一些椭圆曲线和素数会使得 下 ECDLP 变得相对容易。我们将在 6.9.1 一节中讨论这些在构建安全的密码学系统时需要避免的特殊的情况。Elliptic Curve Cryptography
终于到了将椭圆曲线应用于密码学的时候了。我们将从最简单的 Diffie–Hellman 密钥交换开始，它只需要用椭圆曲线 的离散对数问题代替有限域 的离散对数问题。然后，我们将描述 Elganam 公钥密码系统和数字签名（DSA）在椭圆曲线下的变种。6.4.1 Elliptic Diffie–Hellman Key Exchange
首先 ，Alice 和 Bob 先协商确定一条曲线 和曲线上的一个点 。Alice 选择一个秘密整数 ，Bob 也选择一个秘密整数 ，然后他们分别计算接着他们互换 。Alice 使用她的秘密整数计算 ，Bob 同样计算 ，此时他们都拥有了共享密钥：。后续他们就可以将这个共享密钥用于对称密码系统中。表 6.5 总结了椭圆曲线下的 Diffie-Hellman 密钥交换。例 6.19 Alice 和 Bob 都选择使用以下的素数、椭圆曲线、点Alice 和 Bob 选择各自的秘密整数 ，然后他们分别计算Alice 将 发送给 Bob， Bob 将 发送给 Alice，最后他们分别计算Bob 和 Alice 都计算出了 ，接着他们会丢弃 坐标的值，使用值 作为最后真正的共享密钥值。那么对于 Eve 来说，想要获得这个共享密钥值，一种方法就是解决 ECDLP 问题，这样他就可以获取 ，然后计算 。当然，也有可能存在某个方法 Eve 不需要解决 ECDLP 问题就能够获取密钥值。定义 设 为有限域上的椭圆曲线，并有点 。那么 Elliptic Curve Diffie–Hellman Problem 即为根据已知的 计算值 。注 6.20 椭圆曲线的 Diffle-Hellman 密钥交换需要 Alice 和 Bob 交换曲线上的点。曲线上的一个点 包含两个坐标 ，其中 时有限域 上的元素，所以 Alice 就需要给 Bob 发送两个数字。然而，这两个数字并不是相互独立的，他们之间有如下关系