在第二章中我们讨论了在有限域 下的离散对数问题（DLP）。为了构造基于 下 DLP 的密码学系统，Alice 公开了两个值 ，她的秘密指数为满足下列同余式的
现在我们考虑一下 Alice 怎么在 下的 椭圆曲线 中做同样的事情。首先如果 Alice 把 看作是群 下的两个元素，那么离散对数问题则要求 Alice 的对手 Eve，找出满足下列式子的
有了这样的规则，那么看起来 Alice 也能够在椭圆曲线群 做同样的事情，她公开两个点 ，那么她的秘密值则是能够满足下列式子的
Eve 需要做的则是计算出 自加了多少次才能得到 。需要提醒的是这里的“加法”是 ，这比一般的加法要复杂的多，所以椭圆曲线下的离散对数也是特别难解决。
定义 设 是有限域 中的椭圆曲线，设 为 中的两个点，则 Elliptic Curve Discrete Logarithm Problem (ECDLP) 则为一个找到式子 中的 这样一个问题。通过类比 下的离散对数问题，我们将整数 表示为
注 6.14 我们对 定义其实不是特别准确。第一个问题是存在很多点 他不是 的倍数，在这样的情况下 则无意义。然而，为了在密码学中使用，Alice 首先会选择一个点 ，然后选择一个秘密值 ，计算并公开 ，所以在实际的算法中， 总是存在的，且为 Alice 的秘密值。
第二个问题是，如果存在一个 满足 ，那么是否会存在其他也满足该式子的值。为了解决这一点，我们首先注意到会存在一个正整数 满足 ，因为 是有限的，所以列表 不可能全都不同。因此存在一个整数 满足 ，我们设 ，那么最小的 则被成为 的阶（性质2.13告诉我们 的阶会整除 ） 因此如果 是 的阶，并且 是一个任意整数满足 ，那么 的解即为
这意味着 是 中的元素，即 是一个模 下的整数，其中 是 的阶。为了具体些，我们设 。然而将值定义在 的好处是使得椭圆曲线下的离散对数满足
类比一下普通的对数算法 和有限域 下的。事实上满足 6.4 的 下的离散对数算法意味着当群 映射到群 时，其遵循加法定律。我们称映射 为群同态（group homomorphism）。
例 6.15 考虑椭圆曲线
同样的，对于点 ，通过一些计算我们可以发现 ，所以
最后我们注意到， ，但是点 满足 ，因此点 的阶为 ，所以在 中只有一半的点是 的倍数。比如， 就是 中的一个点，但是它就不是 的倍数。
原文始发于微信公众号（山石网科安全技术研究院）：密码学 ｜ 6.3 椭圆曲线离散对数问题（ECDLP）
