椭圆曲线加密(ECC)：域和离散对数
本文为本系列的第二篇文章，翻译自文章：
在之前的文章中我们了解到了为什么定义在实数上的椭圆曲线可以用于构建一个群。我可以定义一个关于点的加法规则：给定共线的三点，这三点的和为0，即P+Q+R=0。我们引出了利用几何学和代数方法的点求和计算方法。
之后还介绍标量积（nP=P+P+…+P）的方法，并找出一个快速计算标量累加的算法。
现在，我们准备将椭圆曲线的定义约束在有限域上而非之前的实数集合并分析有什么不同。
模p下的的整数域
有限域中元素数量为有限值，例如p为质数时，整数模p构成一个有限域（n (mod p)），通常记为，或者，这些符号在下文中将会见到。
在域中，我们将使用两个二元运算：加法（）和乘法（），这个两种运算都满足封闭性，交换律和结合律。对于这两个运算都存在唯一的单位元。当单位元和其他元素结合时，并不会改变那些元素，例如：在整数乘法中为单位元，因为任意整数都有，而加法中0为单位元，因为。在每个运算中，每个元素都存在唯一的逆元，逆元与逆元素是指一个可以取消另一给定元素运算的元素，一个元素与其逆元做计算等于单位元，例如：在整数域中的逆元为其倒数，因为。最后乘法对于加法满足分配率：。
整数模的集合由整数构成，并且加法和乘法为模条件下的乘法，我们以为例：
- 加法：
- 减法：
- 乘法：
- 加法逆元：
另外： - 乘法逆元：
另外：
如果都上述等式不熟悉，参见：https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic。
正如之前所论述的，整数模构成一个域并且满足上述所有性质，特别需要强调的是，为质数这一点特别重要！！例如在整数模4的集合下不构成一个域，因为2的乘法逆元不存在，即等式的方程无解。
模p下的除法
下面我们将定义在域下的椭圆曲线，但是咋这之前我们需要先弄清楚在域下的意义。由上文，很容易联想到的是，也就是除等于乘以的乘法逆元，或者说是的乘法逆元做连乘。通常的做法是，找到的乘法逆元然后与相乘。
利用扩展欧几里得算法可以快速的找到一个数的乘法逆元，其时间复杂度为（或者记为，此处k为输入的数据规模，也就是数据有多少位）。此处不讲解扩展欧几里得算法，有需要的可以自行百度或者谷歌。
定义在上的椭圆曲线
现在我们已经了解了将椭圆曲线约束在上的相关知识，结合上一篇文章所提及的，椭圆曲线的点集为：
我们可以得到定义在上的椭圆曲线的点集为：
此处的0任然是无穷远处，而，为定义在有限域上的点
椭圆曲线：当时的点集。注意对于大多数的x存在两个点与之对应并且关于对称。
点的加法
现在，我们需要对我们的加法定义进行一点点的变化以保证在域内的椭圆曲线加法仍然有意义。在实数域下，我们定义在共线的三点之和为0（）。我们可以仍然沿用这一定义，但是如何定义在域内的三点共线呢？
我们可以将三点共线表述为：存在一条连接这三个点的直线，不过在域内直线的定义有所不同。我们可以类比的认为在域内的直线是所有满足等式的点所构成的集合，其中为摸加法下的标准直线方程。
在椭圆曲线上的加法，其中，。注意，注意观察直线是如何在直线上"重复"出现并且连接各点的。
由如下我们已知的点加法的性质，我们可以得到一个加法群：
- (基于单位元的定义)
- 给定一个非零点Q，其逆元-Q与Q具有相同的横坐标以及相反的纵坐标，即。例如在上的点则
- (基于逆元的定义)
代数求和
计算点之间求和的等式实际上和上述的相同，唯一不同的是我们需要在每一个表达式后没加入对p取余()，因此，给定和我们可以通过如下等式计算
若，则斜率有如下等式
若则有
上述在有域内的等式与在实数域上的等式基本相同，这并不是巧合，实际上等式无论在有限域还是无限域上都适用（除了和）。需要证明这一群的这一法则通常需要涉及相当复杂的数理知识。
在这一问题的求解上，我们并没有定义一个几何学上的求解方法，这使得这一问题看上去有些古怪。比如在之前的实数域中计算的时候我们需要先找到椭圆曲线上点P处的斜率，但是在离散条件下，"斜率"已经么有意义了。我们当然可以用几何方法进行计算，但是纯粹的几何方法过于复杂且不实用。
这里是一个计算有限域上点加法的公式：https://andrea.corbellini.name/ecc/interactive/modk-add.html
椭圆曲线群的阶
我们之前已经论述了，定义在有限域上的椭圆曲线具有有限个点，但是具体有多少个点呢？首先，我们声明椭圆曲线群中点的数量为群的阶。穷举所有的点并验证是不可能的，因为这要求这需要的复杂度，当p很大时计算会十分困难。幸运的是，有一个快速计算阶数的算法：Schoof算法。我们并不需要详细的知道这个算法，我们需要知道的是，我们能够在多项式时间内计算出阶数。
https://en.wikipedia.org/wiki/Schoof%27s_algorithm
标量乘法和循环子群
与实数域相同，乘法被定义为：
我们可以使用加倍算法在步（或者说是步，k为n的长度）内完成计算。这里是一个计算标量乘法的工具：https://andrea.corbellini.name/ecc/interactive/modk-mul.html
定义在域内的椭圆曲线乘法有一个有趣的性质。以椭圆曲线和点为例，计算所有的数乘P的结果：
P的乘法只有5种结果并且不断循环重复出现。因此椭圆曲线上的标量乘法与模p条件下的加法具有相似性
- 0P=0
- 1P=(3,6)
- 2P=(80,10)
- 3P=(80,87)
- 4P=(3,91)
- 5P=0
- 6P=(3,6)
- 7P=(80,10)
- 8P=(80,87)
- 9P=(3,91)
- …
因此我们可以容易的得出以下两点：1、P的乘法只有5种结果，除此之外其他椭圆曲线上的点将不会出现。2、这些结果是循环出现的，我们可以写成
- 5kP=0
- (5k+1)P=(3,6)
- (5k+2)P=(80,10)
- (5k+3)P=(80,87)
- (5k+4)P=(3,91)
k为任意正整数，同时也可以写成，不仅如此我还可以立即验证这5个点在加法下满足封闭性，即：这5个点中任意求和的结果任然属于这5个点的集合，同样的，任意求和，不会得到其他椭圆曲线上的点。
不仅仅是，其他的点也有相似的封闭性特征。选取一个点有：
由上可知，P以及P的倍数的集合构成一个椭圆曲线定义下的循环子群。"子群"的意思是一个群所构成的集合的一个子集。"循环"的意思是元素循环出现，就像是之前的例子中那样。点P被称为循环子群的生成元。
循环子群是椭圆曲线加密加密和其他密码体系的基础，之后我们将会看到。
子群的阶
由P生成的循环子群的阶是多少呢？解答这个问题，我们不能使用Schoof的算法，因为这个算法仅仅作用于由椭圆曲线构成的群，而不是一个由P生成的子群。需要解答这个问题，我们需要先了解以下几点
- 我们之前定义"阶"为群中点的总数，这一定义依然有效，但是在循环子群中我们可以用另一个新的定义：最小的正整数n使得，则n为由P所生成的循环子群的阶。例如之前的例子中，子群由5个点构成且我们有
- P的阶数根据拉格朗日定理（群论）与椭圆曲线的阶有关，即子群的阶是其父群的一个因子。换句话说，若椭圆曲线的阶为N，其中一个子群的阶为n，则N可以被n整除
以上两点给了我们以下寻找P的阶数的方法：
- 用Schoof算法求出椭圆曲线的阶N
- N的所有因子
- 将N所有的因子n带入计算nP
- 最小的n使得nP=0的是子群的阶
例如曲线在上的阶为N=42，所以子群的阶可能为。若可以计算所以P所生成的子群的阶为7。在选择因子计算的时候记得从小的因子开始尝试而不是随机选择，如果随机选择，可能会花费很多时间且有可能误认为14为群的阶。
另一个例子：椭圆曲线为在上，阶为为一质数。所以子群的阶为或37。我们可以很容易的想到，当前仅当点在无限域中是才有n=1。当时子群包含所有椭圆曲线的点。
寻找基点
在椭圆曲线加密中，我们希望我们的子群有很高的阶数，所以我们通常会先选取一个椭圆曲线，然后计算它的阶（N）选择一个较大的子群阶（n）并最后计算一个合适的基点。也就是说，我们希望选取一个不错的子群的阶然后寻找一个基点，而不是反过来，那么应该怎么做？
拉格朗日算法指出，h=N/n永远是整数（因为n是N的因子），则h被成为子群的公因子。考虑到对于椭圆曲线上所有的点有，因为任意子群的阶都是N的因子，我们可以有下式：
现在假定n为一质数（下文会解释原因）,令，则G正好是阶为n的子群的基点（除非，此时阶为1）。
综上，我们有如下算法：
- 计算椭圆曲线的阶N
- 选择一个子群的阶n，n必须是N的因子且为质数。
- 计算公因子
- 选择椭圆曲线上一个随机的点P
- 计算
- 如果是0则返回第4步，否则G为子群的生成元，阶为n且公因子为h。
需要注意的是，当前仅当n为质数的时候上述算法有效，如果n不是质数，则G的阶可能是n的一个因子。
离散对数问题
现在讨论一个问题：如果我们已知点和，求使得。这个问题被称为离散对数问题，并且是公认的困难问题因为没有一个算法能够在多项式时间内使用计算机计算出答案，但是也没有数学证明有效的求解算法一定不存在。
这一问题与其他密码体系中（例如：DSA，Diffie-Hellman密钥交换和ElGamal算法）的对数离散对数问题相似。所不同的是，这些算法使用的是幂运算而不是标量乘法。他们的离散对数问题可以描述为：已知a和b求k使得。"离散"是因为这些问题都是在有限集合内进行求解，"对数"是因为这个问题与求对数相似。
椭圆曲线加密的特色在于，与现今使用的其他加密技术中的类似问题相比，椭圆曲线的离散对数问题似乎更难。这意味着我们使用更小的位宽就可以实现更加安全的加密。