椭圆曲线基本介绍

椭圆曲线的公式，跟高中的椭圆曲线的公式不太一样，样子长得也不太一样, 我们高中数学的椭圆曲线长得是这个样子的：

$ax^2+by^2=c$

我们习惯的椭圆长得是这个样子的：

经典椭圆曲线

在密码学中，椭圆曲线公式为

$y^2=x^3+ax+b \qquad mod \quad p$

样子长得是这样的：

secp256k1

为什么这样子的曲线也叫椭圆曲线呢？严格意义上来说我们高中学到的曲线是椭圆曲线的一种退化情形 $^{[1]}$ ，密码学上的椭圆曲线也是标准椭圆曲线的退化情形。

密码学上的椭圆曲线

密码学上，椭圆曲线的基本形式为：
$y^2=x^3+ax+b \qquad mod \quad p$

a，b的值根据不同的标准不一样，例如我们常用的secp256k1的a=0， b=7. 曲线退化为：
$y^2=x^3+7 \qquad mod \quad p$

在密码学中，椭圆曲线的基本性质如下：

数字的计算由以上公式来描述
x，y都是整数
x，y的范围为 $x\in (0,p), y\in (0,p)$

第一点比较容易了解，但是第二点比较困惑，因为满足上述的公式的整数实在是太少了，例如， $x=1, y=\sqrt8$ , 这就不是整数，难道在椭圆曲线上这个点就不能用？p又是什么？为什么会有p？ p为什么是素数？

模运算

模运算大家都不陌生，在很多的语言中模运算为, 以Python 为例：

number = 10
mod_num = number % 2

但是我们了解的模运算大部分就到此为止了，我们只是在hash 表中，或者是判断奇偶数的时候会使用模运算。但是模运算远远不止这些：

模运算的定义

以下的定义来自于百度百科，也是来自于小学二年级的课本：
给定一个正整数 $p$ , 任意一个正整数 $n$ ，使得 $n=kp+r$ ，其中： $k,r$ 是整数， $0\leq r<p$ , k为除数， r为商
模运算支持四则运算以及乘方，开方，逆元等运算，运算规则具体参见百度百科模运算。乘方，开方运算以及逆元运算我们需要提及一下，后面的运算中我们会使用这几种运算。

模运算中的乘方

根据模运算的规则：
$(a*b)\mod p=((a\mod p)*(b\mod p))\mod p$
推广到乘方运算：
$(a^n)\mod p= \prod_{i=1}^n(a\mod p) \mod p=(a\mod p) ^n \mod p$

模运算中的开方运算

模运算的开方，并非直接求救，而是来自于开方的本质，开方是什么？
$y=x^2$
开方的本质是乘方的逆运算。
在模运算上：
$y \mod p=x^2 \mod p$
假设我们y=5， p=11，求x： 5 %11 = 5，这个很难求，我们可以用穷举法得出答案：7。

模运算中的加法逆元与乘法逆元

在模运算中定义加法逆元为：
$w+z=0 \mod p$
乘法逆元为：
$w\times z=1 \mod p$
逆元乘法以及加法的在公式上比较容易理解，但是在具体数字上，跟我们的理解还是大相径庭，下面是p=8的加法逆元与乘法逆

$w$	0	1	2	3	4	5	6	7
$-w$	0	7	6	5	4	3	2	1
$w^{-1}$	-	1	-	3	-	5	-	7

逆元有什么用呢？其实逆元是用于除法运算的。小学的时候老师都会教：除于一个分数就等于乘以该分数的倒数(分数的倒数就是该分数的乘法逆元)。所以要想除于某个数，可以乘以该数的逆元。

有限域

在数学中，有限域（英语：finite field）或伽罗瓦域（英语：Galois field，为纪念埃瓦里斯特·伽罗瓦命名）是包含有限个元素的域。与其他域一样，有限域是进行加减乘除运算都有定义并且满足特定规则的集合。有限域最常见的例子是当 p 为素数时，整数对 p 取模。

有限域中元素的个数称为有限域的阶。每个有限域的阶必为素数的幂，即有限域的阶可表示为pⁿ（p是素数、n是正整数），该有限域通常称为Galois域(Galois Fields)，记为GF(pⁿ)。

我们在上述定义中用到了：素数p，GF(pⁿ) 的阶n。这两个也是在常用的密码学中都会定义的。例如对于secp256k1来说：
$p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F$
$n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141$

上面说的还是太抽象？我们举个例子来说明：首先定义一个素数p，例如，我们定义素数为7， n=1, 则一个有限域为：
$GF(p^n)=\{0,1,2,3,4,5,6\}$

有限域运算性质

为什么是素数？

我们需要回答为什么是素数的问题。我们不使用数学证明的形式完成，而是通过一个小例子说明为什么是素数。
我们知道，有限域的所有元素（0除外）都存在加法逆元与乘法逆元，我们以p=7与p=8来看二者的逆元：
当p=7时：

$w$	0	1	2	3	4	5	6
$-w$	0	6	5	4	3	2	1
$w^{-1}$	-	1	4	5	2	3	6

当p=8时：

$w$	0	1	2	3	4	5	6	7
$-w$	0	7	6	5	4	3	2	1
$w^{-1}$	-	1	-	3	-	5	-	7

我们发现当p为非素数时，有限域中很多元素都不存在逆元。

有限域求逆元

扩展欧几里得算法

有限域的作用

在密码学中，有限域到底起到什么作用呢？
有限域是密码学的运算域，所有的密码学中的运算都在有限域中完成。例如在EC中的私钥： $x\in GF(p)$

有限域上的椭圆曲线

在上节我们提到椭圆曲线在密码学中的有三个要素，其中要素2为：横坐标与纵坐标都是整数。这一点可以理解为：横坐标与纵坐标都在有限域中。 Mordell证明了整体域上的椭圆曲线是有限生成交换群。具体的证明我们没有必要搞懂，但是我们需要理解其含义。

椭圆曲线的几何意义

首先我们排除误解, 在很多文献中的椭圆曲线的ADD 并不是实数域上的Add，而是在有限域上的Add。如下图所示：

几何意义上误解椭圆曲线

如图所示，在实数域中上图中显然以下公式不成立：

那么如何在几何上理解椭圆曲线呢？在几何意义上，椭圆曲线确实满足上述公式，但是在上述公式中各个点并不是实数意义上的点，而是在有限域上的点。以上的公式理解仅仅限于几何意义上的理解，而不是计算意义上的理解。
那么上述的几何就没有意义了吗？不是，我们根据椭圆曲线在计算响应的坐标时，还是根据其几何意义上的来计算，通过域的形式来理解。

有限域的意义是：任何有限域中的两个点和和都在有限域中。这也是有限域的闭运算之一。

椭圆曲线的几何计算

椭圆曲线的两个点 $P(x_p,y_p)$ ， $Q(x_q,y_q)$ ，P，Q不为加法逆元, 过这两个点做直线，与椭圆曲线相较于 $R(x_r,y_r)$ 点。根据几何意义，有如下公式：
$\begin{cases} x_r=k^2-x_p-x_q \\ y_r=k(x_p-x_q)-y_p \end{cases} 其中， k=\frac {y_p-y_q}{x_p-x_q}, 也就是斜率$

如果 $x_p=x_q$ , 由于P，Q不为加法逆元，也就是两点相同，两点相同时，上述公式不能计算，我们约定为过P点做切线，斜率变为：
$k=\frac{3x_p^2+a}{2y_p}$

有限域上的椭圆曲线

在有限域上，上述几何意义的算式依然成立，不过要少做变化：
$\begin{cases} x_r=k^2-x_p-x_q \mod p\\ y_r=k(x_p-x_q)-y_p \mod p \end{cases}$
我们将斜率也做一下区分：
$\begin{cases} k=\frac {y_p-y_q}{x_p-x_q} \mod p \quad (P \neq Q)\\ k=\frac{3x_p^2+a}{2y_p} \mod p \quad (P=Q) \end{cases}$
做了这个之后，穷举所有点之后，我们便得到了有限域上的椭圆曲线。让我们来看一下有限域上的椭圆曲线是什么样子（平行于y轴的范围怎么处理？记得之前处理过但是总是找不到原来的处理方式）：

有限域.png

有几个规律我们需要点出：

所有的点都在一个有限域中。
所有的点是关于y=12 对称，这一点对于理解以后的PK是33bytes非常有帮助。
-点带有一定的随机性

上图的随机性是来自于模运算，几乎所有的加密的随机性都来自于模运算。

密码学中的椭圆曲线

在密码学中，椭圆曲线的使用有如下约定：

G点是椭圆曲线上的一个点，曲线上所有的点都是从G点通过有限域上的ADD运算计算而来。
密码学中的私钥为有限域中一个不为0的整数。
公钥是椭圆曲线上的一个点。

相信上述的约定已经回答了大多数人的困惑：椭圆曲线公钥与私钥的与椭圆曲线的关系。
$P=sG, s是私钥， P是公钥$

私钥计算公钥的效率

根据上述公式， $P=sG$ ，是否在工程上可以快速计算（ssh -genkey的效率）?

$P = sG = \underbrace{G+ \ldots +G}_{\rm s} = \underbrace{G+ \ldots +G}_{\rm \frac{s}{2}} + \underbrace{G+ \ldots +G}_{\rm \frac{s}{2}}$
看到这个公式，相信就会有很多人知道算法的复杂度：o（logn）

为什么公钥可以公开而私钥不会被泄露

在上述公式中，P可以公开，而s需要保密，一个问题随之而来， P公开之后，s不怕被泄露吗？
$s=\frac {P}{G}$
由于G是公开的，我们是不是科技计算出G的逆元，然后计算 $P*G^{-1}$ 呢？很遗憾，目前没有很好的算法计算 $P*G^{-1}$ 。

介绍完椭圆曲线，我们看一下《Schnorr签名介绍》

椭圆曲线101

椭圆曲线101

椭圆曲线基本介绍

密码学上的椭圆曲线

模运算

模运算的定义

模运算中的乘方

模运算中的开方运算

模运算中的加法逆元与乘法逆元

有限域

有限域运算性质

为什么是素数？

有限域求逆元

有限域的作用

有限域上的椭圆曲线

椭圆曲线的几何意义

椭圆曲线的几何计算

有限域上的椭圆曲线

密码学中的椭圆曲线

私钥计算公钥的效率

为什么公钥可以公开而私钥不会被泄露

推荐阅读更多精彩内容