kentzhang-geek
commented
2 years ago 好复杂，先mark
Open AlexiaChen opened 4 years ago
kentzhang-geek
commented
2 years ago 好复杂，先mark
ouzhsh-GZHU
commented
1 year ago 太强了 受益匪浅 虽然一些地方自己没理解
doutv
commented
1 year ago 深入浅出，看一遍文章已经理解了椭圆曲线密码学的idea
从群环域到椭圆曲线密码学
从集合到群
首先还是从集合说起吧。
最早的时候，我记得我们应该是在初中的时候就引入集合的概念了。我们知道很多种关于数字的集合（以下字母均为大写字母）：
从小学到高中，我们都直接或间接地一直在学习数字的集合，学习加减乘除等运算。换个角度，如果我们把这些运算引入集合会不会发现有趣的性质呢？大家有没有想过？
设集合G，然后我们定义有一个*这个二元运算（注意，这个运算不一定是乘法，也不一定是加法，它表示一个二元运算，仅此而已）。对于集合的任意元素a，b，都有以下关系成立：
此时，我们称： 关于运算*， 集合G封闭。 （封闭有些时候也称闭包closure）
从集合出发，加入二元运算，从而定义了群的概念，对于某二元运算*, 单单具有封闭性的集合叫原群（magma）。
如果该运算还具有结合律，也就是不拘泥于运算的顺序：
如果对于运算 * ，具有封闭性，结合律的集合称为半群（semi-group）。
如果对于运算 *, 满足以下性质：
此时我们称元素e是在集合G下运算*中的单位元。
举个例子， 对于集合Z，在运算 + （加法）里单位元就是0,但是在运算 × （乘法）里单位元是1。
如果对于运算 *, 具有封闭性，结合律和单位元的集合称为幺半群（monoid）。哈哈，看到这里，如果对于Haskell等函数式语言比较熟悉的人是不是经常听过单子（monad）这种概念？他们确实是有关的，这里不打算延伸，感兴趣请看《我所理解的monad(1)：半群(semigroup)与幺半群(monoid)》。
如果对于运算 *, 满足以下性质：
此时我们称元素b是关于运算*的a的逆元。
举个例子，对于集合R，关于运算 + （加法）里，4的逆元就是-4,但是在运算 × （乘法）里4的逆元是1/4。
这么一来，如果对于运算 *, 具有封闭性，结合律，单位元，逆元就称为群（group）。
所以引出了群的定义（公理），将满足以下性质的集合G称为群：
阿贝尔群
阿贝尔群是群中的特殊存在，它对群的概念又加上了特殊的限制，也就是在集合G上，对于运算*, 任意元都满足交换律，那么就称为阿贝尔群：
阿贝尔群与普通群的区别就在于是否满足交换律。阿贝尔群的公理如下：
当然，阿贝尔群又称为交换群，纯数学专业可能会有开设《交换群论》这样的深入点的专业课。
从群到环
环（Ring）又在阿贝尔群的基础上，加入了另一种二元运算，暂且这里叫做乘法二元运算吧，这个乘法与初等代数不大一样。加法运算也与初等代数不大一样。
所以环就是二种不同的二元运算作用在集合G上，并满足以下性质：
关于运算 + （加法）：
关于运算 × （乘法）：
关于运算 + 和 × ：
如果细心的人仔细看环的公理，并对比之前阿贝尔群的公理，其实会发现：
交换环
交换环就是环关于乘法运算上，所有元素满足交换律：
关于运算 + （加法）：
关于运算 × （乘法）：
关于运算 + 和 × ：
剩余类环
我们举个例子，整数集合Z关于加法和乘法构成环，我们把这个环称为整数环，如果我们把mod运算考虑进加法和乘法运算的话，那么就会变成这样（设m为某个常数）：
那么这些运算的结果集合也构成了环： Z/mZ {0,1,2,3,4 ... m - 1}。这个环我们称为剩余类环，所以可以把Z和Z/mZ同等看待。
这两种环都满足换的公理，但是，这两种环还是不大相同，Z就像数轴上排列的点，Z/mZ类似于时钟的表盘构成的圆环; Z是无限集合， Z/mZ是有限的集合; Z具有无限性，Z/mZ具体周期性，集合大小被限制在了某个范围。
只要从环中推导出某个定理，那么这个定理一定适用与Z，也同样适用于Z/mZ。这就是抽象代数的魅力，哈哈，这样是不是mod运算有点类似于化简，归整？ 把无限变成有限，将无限宇宙尽收掌心，好利于研究或计算啊。这时候我想起了霍金写的《果壳中的宇宙》。
从环到域
从环（特指交换环）的公理来看，似乎关于乘法运算上与加法运算对比还缺少一个特性： 关于乘法的逆元。 也就是说，环里不一定能进行除法运算，除法运算本质上就是乘法逆元。
说到这里就可以看到，如果一个环关于乘法上，每个非零的元素都要有乘法逆元（非零是因为0不能作除数），那么就可以把这个环称为域（Field）。
哈哈，我们终于从群开始慢慢过渡到了域。
现在来回顾一下，对于群而言，集合中只能定义一种二元运算，对环来说，定义了两种二元运算，而对于域是定义了三种二元运算吗？ 不是的。
如果你仔细想想加法和乘法的相反运算都是通过逆元来定义的，那么你就清楚了。存在加法和关于加法上的逆元就能进行减法运算，同理，存在乘法和关于乘法上的逆元（除0以外）就能进行除法运算。所以关于乘法是否存在逆元就是环（交换环）和域的唯一区别。
域的公理自然而然就是这样了：
关于运算 + （加法）：
关于运算 × （乘法）：
关于运算 + 和 × ：
由此可见，域是一种能够进行加减乘除的代数结构，是集合与四则运算的推广。当然，还有一种叫格（lattice）的代数结构，它目前被用在了抗量子算法的密码学领域（基于格的密码学），还有如果你涉及程序语言理论方面的研究，也会用到格的概念。这里不打算深究，因为文章后面的话题暂时似乎是用不到格的概念。
回顾下之前我们提到的整数环Z，整数集合Z是可以构成环的，但是整数环不能构成整数域（逆元不属于整数集合），但是整数环加入除法（乘法逆元），能够构成有理数域。
考虑整数集合Z {... -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5}, 它构成一个整数环Z，我们回到剩余类环的概念，既然整数环是无限的，那么我们就来研究有限的剩余类环吧，反正是一样的，它也是环，对吧。剩余类环Z/mZ是对运算结果加入了mod操作。那我们就来测试一下（设m为5）：
那么剩余类环Z/mZ {0, 1, 2, 3, 4}
3 + 4 mod 5 = 2
1 × 3 mod 5 = 3
这里例子中为什么没有零？注意，之前提到过，除0以外的任何元素才有乘法逆元，这样才是域。这点要一定记住。
因为 (3 + 4) × 2 = 3 × 2 + 4 × 2 满足分配律
（3 + 4 mod 5）× 2 mod 5 = 4 mod 5 = 4
3 × 2 mod 5 + 4 × 2 mod 5 = 1 + 3 = 4
(3 + 4) × 2 = 3 × 2 + 4 × 2 = 14 mod 5 = 4
经过以上运算的结果得知，在m = 5的时候，剩余类环Z/mZ是域，因为满足域公理。
那么这样说来，对于剩余类环Z/mZ就一定是域吗？不是的，不信你可以用m = 6来做运算看看，最后结果就不是域。慢慢经过你的m测试越来越多，你会发现，居然要m是质数（素数）的情况下，剩余类环Z/mZ才是域。m = 质数的情况下，剩余类环这个域也被称为有限域。记作：
设p是质数，m = p
如果把剩余类环看作是整数的微缩模型，那么用质数p构造出的有限域Fp也可以说是有理数的微缩模型吧。这个有理数域的微缩模型被限定在了p内，并且有限域都是整数！ 能够化简到如此简单，数学真的很美妙，此时我的眼眶是湿润的。
这时候你就可以想象下，在平滑无限细分的有理数域把它化简到有限域Fp，那么这个离散化的过程最终的成果就是，计算机就可以处理有限并且离散的数据了，因为最开始，计算机是不能精确求光滑无限细分的问题的
有限域，这个概念，慢慢会出现在椭圆曲线密码学中。接下来我们就开始接触椭圆曲线密码学吧。
椭圆曲线密码学
椭圆曲线
其实椭圆曲线是非欧几何下引伸出来的一种几何。大家都知道在欧式几何里面平面上的两条平行线不相交吧？如果修改欧几里德第五公设（过直线外一点，有且仅有一条与该直线的平行线），那么就可以导出了非欧几何。非欧几何大概有两种：
在非欧几何的研究中，可以导出很多更加有趣的几何性质。
比如：
理解了黎曼几何，那么就理解了黎曼面上看似平行的平行线其实是会有交点的。可以理解为相交在很远很远的地方，即定义了平行线相交于无穷远点（point at infinity）。
好了，这样我们假设在欧几里德平面上画一条直线A，我们想像一下，我们为直线A添加一个无穷远点P，那么我们得到一个扩大的直线（直线A的有穷点和无穷远点P构成），这个直线专业点的叫法叫射影直线（projective line），也称一维射影空间。然后我们在该平面上画一条直线B，它平行于A，我们假设这条线B与A相交于无穷远点P。（因为欧几里德平面的平行线是不可能有交点的，所以只能用无限的思维假设AB两条平行线在无穷远处相交于点P）
这样我们试着导出了以下三个性质：
那么，根据以上三个性质，我们定义了射影平面：所有的欧式平常直线和那一条无穷远直线构成了射影平面。也可以说，所有平常点与所有无穷远点构成了射影平面，还或者可以说，所有的射影直线构成了射影平面，本质都是一样的
哈哈，小学大家都知道，点构成线，线构成了面，面构成体，是吧。
因为在欧式平面上的平行线都有相同的无穷远点，不同的线又有不同的无穷远点，无穷远点又构成一条无穷远直线，所以射影平面上的任何一点都可以用三维的齐次坐标（X，Y，Z）表示，其中X，Y，Z不能全为0。
其中
这样我们就可以根据以上的坐标表示，把欧式平面上的点投影到射影平面中去。
例如，把一个欧式平面上的点（x,y）,令 x = X/Z， y = Y/Z, Z != 0, 则投影到射影平面上的点就是（X，Y，Z）。 用具体数字代换进去就是，点（1,2）投影到射影平面的点就是（Z，2Z，Z），所以，诸如(1,2,1),(2,4,2)等这样形式的坐标表示是点，在射影平面内都算同一个点。
这时候关键的人物上场了，就是我们期待已久的椭圆曲线，它的定义就是：
该方程的表示是（注意，是三元方程）：
该方程可以归整到欧式二维平面的方程表示形式：
其中a,b为常数系数，以下是a，b不同的取值，表现的椭圆曲线的欧式二维图像：
所以可以看到，椭圆曲线并不是椭圆形，这个是有历史原因的，因为椭圆曲线方程与求椭圆弧长的椭圆积分的反函数很像。
到这里大部分网络上会直接把上面的方程写出来，没有讲述过多的来源和发展历史。所以就以为椭圆曲线是一个二维的东西，实际上不是。因为投影的关系，我们可以降维到用二维的图像来研究它。
还有一个要注意的一点就是，椭圆曲线是非奇异的，也就是是光滑的，也就是各个分量的偏导数不能全为0。而且欧式二维平面的椭圆曲线因为有y^2项，所以一定关于x轴对称的，这个性质之后会用得到。
椭圆曲线上的运算
之前我们看到，椭圆曲线那么奇怪，歪瓜咧枣的线条是怎样跟密码学里关联上了？曲线上的这些点有什么联系呢？ 依靠点与点之间的心灵感应吗？ 哈哈，这里开个玩笑。
回顾下之前我们学的关于群的部分，我们要定义个点与点之间的的二元加法运算，这个运算在曲线上的点的集合上构成一个阿贝尔群。所以就涉及到怎样设计这个二元加法运算满足阿贝尔群公理就是个问题，跟初等代数的加法不一样哈。
那么设两个在椭圆曲线上的点P，点Q，那么P + Q就是连接PQ两点作直线，相交于椭圆曲线于一个点R’，那么过交点R‘作与x轴的垂线并延长再次与椭圆曲线相交于一个点R，那么P + Q = R。也就是点R’与点R关于曲线的x轴对称。
以下就是椭圆曲线上P + Q = R的加法运算的图像（网络上很多，随便找的）：
根据上图，你可以在草稿纸上画，第一眼就可以看出来满足交换律， P + Q = Q + P = R，
然后你在设一个点K，然后再画直线，你会发现（P + Q） + K = P + （ Q + K）也满足结合律。
按照上面的定义，前提假设是P ！= Q，没法解释 P = Q 也就是P，Q两点重合的情况下，无法过两点作一条直线，这时候的加法运算是怎么定义的呢？其实只要过两点的重合点画出该点在椭圆曲线上的切线就可以了，然后规则与上一个图例是一样的：
上图就定义了P + P = 2P = R，这样的运算称为椭圆曲线上的二倍运算。
此外，如果我们将某一点A关于x轴对称位置的点定义为-A，这样的运算称为椭圆曲线上的正负取反运算，如下图：
上图就定义了类似我们印象中的负数，好了，如果我们将A和-A相加会怎样呢？ 上图也说明了A+（-A）的情况，就是过这两点作一条直线，这条直线是与y轴平行的，唉？不对啊，这条直线与椭圆曲线没有第三个交点了啊？ 其实不是的，因为椭圆曲线实际上并不是欧式二维平面的东西，它来自于非欧几何中的黎曼几何（黎曼球面），二维平面也展示不出来交点，我们就认为过点A和-A的这条直线与椭圆曲线相交在无穷远点，这个无穷远点我们一般记作O。所以就定义了 A + （-A） = O 。
好了，至此为止，我们对椭圆曲线上的点（包括无穷远点）的加法运算进行了定义，细心的人会发现，这个在椭圆曲线的点集和无穷远点点集上定义的加法运算满足了之前阿贝尔群（交换群）的公理， 无穷远点O就是单位元，任意一点A的逆元就是-A，并满足交换律，结合律。完美啊，perfect。
曲线上的运算规则已经清晰，当给定椭圆曲线方程及点的坐标时，我们就可以用坐标进行加，减，倍乘运算。比如，给定曲线上的一个点G（基点，base point），我们可以求2G，3G。其中3G = G + 2G，以此类推。也就是说，当给定G点时，已知标量k，求点kG（G的k倍）的问题并不困难。但反过来，已知点kG求标量k则非常困难。这就是椭圆曲线密码学中所利用的“椭圆曲线上的离散对数问题”，英文简称也就是所谓的ECDLP。
通过以上解释，已知G点的情况下，其实标量k也可以看作是私钥，kG看作公钥。从私钥计算公钥很简单，但是根据公钥推私钥，几乎不可能。这就是非对称的密钥对。
椭圆曲线上的离散对数问题
ECC利用了ECDLP的复杂度，RSA利用了质因数分解的复杂度，其本质都是利用了计算困难的问题，这深入的话题，研究计算理论，计算复杂度的学者会更有了解。
利用有限域这个工具对椭圆曲线进行离散化
椭圆曲线要形成光滑的曲线，其点的坐标（x，y）都必须是实数，即实数域R上的椭圆曲线。实数域R的椭圆曲线不合适用在密码学当中，计算机擅长于处理有限，并且离散的整数数据，所以要用在有限域Fp上的椭圆曲线（p为素数）。所以点坐标（x，y）这些都在有限域下了。更直观一点的话，就是在有限域限定的整数下来进行点的坐标运算，并且将结果除以p求余数。
例如： y^2 = x^3 + x + 1 (mod 23) 就是位于有限域F（23）上。也就是说对于在有限域F（23）下的任意一点（x，y），对于方程左侧的y^2的结果mod 23 与右侧的x^3 + x + 1的结果mod 23的结果相等。
上面的例子给定的素数p是23,这个素数很小，构成的椭圆曲线在有限域上的离散点的数量太少，所以在这个有限域上的ECDLP不难解，但是当素数p非常大的时候，要解这个问题就非常困难了，通常工业级的椭圆曲线的密码算法库给定的素数p都非常大。
以NIST推荐的一种椭圆曲线Curve P-521为例，其质数p就是下面这个长达157位（十进制位）的数。
当然，为了提高计算效率，NIST推荐p的值使用梅森素数（或伪梅森素数），例如，在椭圆曲线P-256中，p = 2^156 - 2^224 + 2^192 + 2^96 - 1。
梅森素数目前仅发现51个。梅森数是指2^p - 1这类形式的数，其中p是素数，如果2^p - 1刚好也是素数，那么2^p - 1这个数就是梅森素数。梅森素数很少，梅森数越大，梅森素数就越难出现。
到现在，终于知道为什么人类一直在致力于发现新的素数了吧，其实素数是很有价值的，对科学。当然，也不尽然，因为我看了相关专业的人士评价，其实素数的发现，也仅仅集中在密码学领域有用途，其他方面素数价值并不是很大，人类致力于探寻也只是好奇驱使而已。有兴趣的可以看一看这个世界性的分布式网格计算项目GIMPS，该项目就是利用世界上计算机的闲置资源来计算并发现更大的素数。
有限域下的椭圆曲线
对于曲线y^2 = x^3 + x + 1在有限域F（23）下的椭圆曲线上的点（x，y）的坐标分布与顺序都是杂乱无章的。如下图：
设给定点P（3,10）关于P点的标量乘k（1-27）都是毫无规律的。
对于给定点P，那么P点的逆元-P（3,13），刚好27P的坐标就是（3,13），那么28P = 27P + P = -P + P = O （无穷远点）。如果满足这样的关系就称为P（3,10）的阶就是28。
这样就给出了一个关于在有限域椭圆曲线上的点阶的定义：
这个阶的作用在生成私钥的时候会用到，设曲线上的点G（base point,也称生成元），生成私钥k，那么公钥就是kG，其中k < n，且nG = O，也就是说，私钥k要小于G点的阶数n。
细心的人又会发现了，这个以生成元G点开始，假设G点的阶为n，那么由G生成的有限循环子群为：{O， G， 2G， 3G，..., （n-1）G}。
还不明白的话，又以上图举例：
往下类推
你会发现，无论是多少倍的G，都会被循环分解限定在其G点生成的循环子群内。
椭圆曲线点的坐标运算
设点P（x1,y1）,点Q(x2,y2)的坐标，点R（x3,y3），那么计算R点的代换公式分以下几种情况：
若P为无穷点（单位元），即P = O，此时R = P + Q = O + Q = Q；若Q为无穷点，即Q = O，此时R = P + Q = P + O = P；若P和Q都为无穷点，即 P= Q = O，则 R= P + Q = O + O = O。
若 x1 = x2而 y1 = -y2，此时称Q点为P点的逆元，记为P = -Q = -P，且R = P + Q = O。（也就是P，Q两点关于x轴对称）
若x1 = x2且y1 = y2，即P = Q，此时R = P + Q = 2P = 2Q，其中
上图的lambda是值是椭圆方程等式两边同时求导，这样就是当前切点的斜率
上图的lambda就是过两点求直线斜率的公式了。
以上公式给出来了，代码应该会写了吧，这里就不写了，因为椭圆曲线的坐标加法运算要在有限域Fp下进行，所以上面的公式后面都得mod p。
比如:
lambda = ((3*x1^2 + a) / 2*y1) mod p
x3 = (lambda^2 - 2*x1) mod p
y3 = (lambda*(x1 - x3) - y1) mod p
如果你细心观察上面的运算公式，你会发现lambda的值可能在计算机下会有错误，这种错误就是除数和被除数之前可能并不是一个整除关系的时候，得到的可能是0,或者小数，而有限域下，是不可能有小数存在的，这样计算会有错误。
比如 a = 3, b = 4, p = 7, lambda = （3 / 4） mod 7的计算结果就会有问题，3/4并不是一个整除关系，如果这样计算，计算机最后计算的lambda结果就是0。所以需要把除发转化到乘法逆元，（3 / 4） mod 7 = （3 * 4的逆元） mod 7。
在mod运算下，计算乘法逆元最朴素的方案是用扩展欧几里德算法去求。但是求逆运算性能贼慢，优化方法有很多， 主要思路都是尽量避免求逆，一个是降低总计算步骤中的求逆次数，一个是转换椭圆曲线的坐标系直接避免求逆。这里深入的暂时不介绍，网上论文很多，比如： 《GF（3^n）下的椭圆曲线快速算法研究》,这篇论文是北航的，主要是降低求逆次数，对于kG点，其中标量k需要满足3^n的形式，并且对于椭圆方程y^2 = x^3 + a*x + b中的a,b系数也限定在有限域F（3^n）的形式。
就拿普通的点加运算来说，注意看P ！= Q的点加公式，lambda计算上是1次逆运算，1次乘法运算，x3的计算上又是1次平方运算，y3的计算上是1次乘法运算，当然，公式中的加减法的运算开销可以忽略不计，关键就是以上的三种运算，逆运算，平方运算，乘法运算开销最大，其中1次逆运算更是相当于1次乘法运算开销的10倍。
下面来举个例子就知道了，为了方面直观,直接a，b满足整除关系就好了：
（4 / 2） mod 7 = 2
上式可以转换为 (4 inverse(2，7)) mod 7 = (4 4) mod 7 = 16 mod 7 = 2
其中inverse(2，7)是求2在模7运算下的乘法逆元，我用python计算的，结果为4。可以看出，转化为乘法逆元，其结果是一样的，最终都是等于2。
至此为止，不考虑运算性能的话，只要求逆搞定了，那么椭圆曲线上的所有运算都可以根据公式搞定了。P + Q， kP = P + （k - 1）P， 2P = P + P，3P = 2P + P。反正点的标量乘法，最终都可以退化成点加法。
这里注意哈，这里的乘法逆元跟曲线上的点的加法逆元不一样！
比如设素数域F（23）的椭圆曲线上的点P（3，10），那么点P的逆元-P就是（3, -10 mod 23），-P的坐标就是（3, 13）。但是10在模23下的乘法逆元inverse(10,23)的值是7。这是完全不同的两个运算，别搞错了。
椭圆曲线的Diffie-Hellman密钥交换（ECDH）
我们上一小节知道了利用椭圆曲线求密钥对的方式，那么接下来看看更具体的应用。比如利用椭圆曲线进行DH交换。这个流程大致与朴素的DH交换的流程相同。
相对地，椭圆曲线DH交换利用的是：
以密码学流行的Alice和Bob对话的例子，假设，Alice和Bob需要共享一个对称密码的密钥，然而，双方之间的通讯线路已经被窃听者Eve窃听，这时候就可以利用ECDH来进行安全的密钥交换。
ECDH的流程大致是以下顺序：
简单来说，就是ECDH就是利用双方共同的G点，各自生成自己的密钥对，然后进行公钥交换，然后收到对方的公钥再次利用自己的私钥做椭圆曲线上的标量乘法。所得到的点是同一个点。这个结果点就是共享密钥。
Eve窃听到的数据只有G，aG，bG，所以无法求出a，b，自然也无法求abG这个共享密钥。
但是严格意义上来说，椭圆曲线上的的DLP只能证明已知G，aG，bG难以求a，b。但不能证明已知G，aG，bG难以求abG。所以后者是有另外的论文证明的，反而不是椭圆曲线的DLP证明的。
所以，ECDH是安全的，别担心。
在工业实践中，往往Alice Bob的每次通信都需要更换随机数a，b，这样即便在某个时间点通信的机密被破解，由于每次通信使用的共享密钥不同，也无需担心通信内容被破解。这样的特性称为前向安全性（Forward Secrecy，FS）或完全前向安全性（Perfect Forward Secrecy，PFS）。比如，SSL/TLS使用椭圆曲线密码时，选择ECDHE_ECDSA和ECDHE_RSA密钥交换算法都可以获得这特性。
如果细心的人可以发现，ECDH无法防止中间人攻击，比如Eve不仅仅是窃听通信，而是冒充代替Bob。冒充问题其实可以用之后的数字签名解决。
椭圆曲线ElGamal密码
好了，由上一节Alice Bob都生成了共享密钥abG，接下来就要用abG这个密钥加密通信的message了。
假设，Alice要向Bob发送一条Message，Alice可以将自己要发送的Message用椭圆曲线上的一个点M表示（实际上Message是编码成该点的x坐标，这样点M的y坐标也知道了）。
椭圆曲线的数字签名算法（ECDSA）
大家都知道利用非对称密钥对可以进行数字签名，所以是可以利用椭圆曲线密码进行数字签名的。这样的签名方案是ECDSA。
假设，Alice要对消息m加上数字签名，而Bob需要验证该签名。（注，以下写着计算这个关键词的其实都是以mod p的运算，毕竟是有限域下的椭圆曲线）
(h / s)G + (x / s)(aG) => ((h + ax) / s)G => 代换s： (r(h + ax) / (h + ax))G => rG
由上述的推导过程可发现，如果计算的结果与rG一致，那么验签成功，反之失败。
这个过程中，攻击者Eve不知打Alice的私钥a，所以无法计算出合法的s，即便对于同一条消息m，只要改变随机数r，所得到的数字签名也会改变。
总结
本文只给出了ECC的线性知识的思路，包括从哪里到哪里，但是没有涉及算法优化等细节。有机会我再研究研究，并再写个文章分享出来吧。：）