他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)椭圆曲线算法：入门（1） - 简书
椭圆曲线算法：入门（1）
很多人都听说过加密算法，包括ECC、ECDH或者ECDSA。ECC是Elliptic Curve Cryptography的缩写，就是椭圆加密算法，ECDH和ECDSA是ECC的不同实现。
椭圆加密算法的应用范围很广，主要的三个技术 、以及 都在使用它，更别提以及其他加密数字货币了。
在椭圆加密算法流行之前，绝大多数的公钥加密算法都是基于RSA、DSA以及DH这些基于模运算的替代加密系统。这些加密算法在今天依然占据非常重要的位置。然而，尽管ECC背后的这些算法很容易理解而且广泛使用，但是对于绝大多数人来说，这些算法是一个谜团。
接下来的一系列文章：椭圆加密算法（从入门到放弃），我将对该算法做一个详细介绍。我的目标并不是要彻底解释清楚以及证明背后的数学原理，而是做一个介绍，讲清楚：简要解释ECC，以及为什么ECC被认为是安全的。同时，也会给出模拟操作的例子以及脚本帮助你更加理解。
接下来的几篇文章会涉及到：
实数下的椭圆曲线以及群公理（就是这篇文章啦）
有限域下的椭圆曲线以及离散数学
密钥对加解密以及两种椭圆加密算法：ECDH和ECDSA
破解ECC的安全性算法，以及同RSA的比较
笔者假设阅读这篇文章的读者已经对以下几个概念并不陌生：集合论、几何学、模运算，并且对对称加密和非对称加密有了一些了解。最后，在加密学里面，对于什么是“简单”的问题，什么是“困难”的问题有个清晰的认知。
首先：什么是椭圆曲线？Wolfram MathWorld给出了个准确非凡的定义。但对于目前的我们来说，椭圆曲线可以暂时简单的理解为描述了特定点的集合的公式：
该公式在椭圆曲线里面称为*Weierstrass normal form*
该条件是为了限制不出现 [singular curves](https://en.wikipedia.org/wiki/Singularity_(mathematics))
以下是a和b参数的变化对应的图形的示例：
b=1，a取值范围从2到-3
特殊曲线：左边参数是a=b=0，右边参数是a=-3，b=2.这两条都不是符合标准的曲线
a和b的取值变化决定了曲线在坐标系上的不同形状。从图中可以看到，椭圆曲线是相对X轴对称。
为了达到我们的目的，我们还要定义一个（也可以成为理想点），从现在开始，我们以符号0，也就是零表示该点。
把上面几个点结合起来，我们的椭圆曲线公式就变成了
群(Groups)
数学上，群(Groups)指的是我们定义了二元操作“运算”并且用符号+表示的一个集合。假定我们要操作的群用 G表示，那么我们在这个群上面要定义的“运算”必须符合以下几个属性：
闭包。如果a和b都是G的成员，那么a+b也是G的成员。
组合性。(a+b)+c=a+(b+c)
单位元。存在确切的一个值，称之为单位元，0可以保证该等式成立 a+0=0+a=a
逆元。每个成员都有一个相反数：对于任意值a必定存在b使得a+b=0
如果加上第五条这要求：
交换性a+b=b+a
这样的群我们称之为 。
根据以上的定义，我们很容易得知，整数集合 Z 是一个群，也可以称之为
。自然数集合
N 却不是一个群，因为不符合第四个属性（自然数都是整数，不存在a+b=0）。
根据组的这四个属性，我们很容易可以推导出其他属性。比如：第三个属性的确切的值0是唯一的；相反数也是唯一的，也就意味着a+b=0，a的相反数b也是唯一的。这些属性有助于我们接下去的数学逻辑推理。
椭圆曲线里的群公理
如上文所说，我们可以基于椭圆曲线定义一个群。特别要指出的是：
群里的元素都在椭圆曲线上
椭圆上的单位元指的是无限远点
椭圆上的点P的逆元与P关于X轴轴对称
定义+运算：给定三个非零的点 P，Q和R，则P+Q+R=0（无限远点）成立
P+Q+R=0（无限远点）
注意：最后一条公理里，给出了三个点，但是没有限定顺序，也就意味着P+(Q+R)=Q+(P+R)=R+(P+Q)=?=0。这就充分表明了，这里定义的+运算符符合群公理的组合性和交换性，也就意味着椭圆曲线符合阿贝尔群。
到目前为止，一切都推理挺顺利的，对吧。那么问题来了，我们要如何计算两个任意点之和呢？
几何学上的加法
因为椭圆曲线是阿贝尔群，所以公式P+Q+R=0
以及 P+Q=-R成立。根据这些公式，我们可以从几何学的角度去计算点P+点Q的值：在椭圆曲线上画出点P和点Q，连直线穿过P和Q，该直线会与椭圆曲线相较于第三个点，称之为R。根据R取得R的逆元-R，P+Q=-R。
运用几何学的方法很容易得到我们要的结果，但是我们需要再对一些更精确的解释。特别是有一些问题需要考虑：
如果P=0或者Q=0(0是无穷远点)呢？我们当然无法画出该直线，因为无穷远点无法体现在直角坐标系里。但是既然已经定义了无穷远点0，那么对于任意给定的P或者Q，P+0=P以及0+Q=Q都是成立的。
如果P=-Q呢？这种情况下该直线是与X轴是垂直的，并且不会与椭圆曲线相交于第三个点。 根据公理，P就是Q的逆元，P+Q=P+(-P)=0。
如果P=Q呢？这种情况下，存在无数条线穿过这个点。这里要用到极限的思维。假设线上有另外一个点Q1，让Q1不断靠近P，会怎么样？
随着两个点的不断靠近，最终产生的线跟椭圆曲线是切线关系
随着Q1不断靠近P，最终Q1无限靠近P，产生了一条直线与椭圆曲线相切。那么可以得到 P+P=-R, 在这里R就是该直线与椭圆曲线的另外一个交点。
如果P≠Q，但是不存在第三个交点R呢？这种情况和上一个情况很类似。实际上，这种情况下该直线跟椭圆曲线是相切的关系。
假设P就是相切的点。在上一个情况里，有该等式P+P=-Q。而在这里变成了P+Q=-P。另一方面，如果Q是相切的点，那么P+Q=-Q。
我们需要了解的几何学只是已经差不多涵盖了所有情况了。只要给我们笔和尺子，我们就能在椭圆曲线上执行加法。如果有兴趣，可以到计算椭圆曲线上的加法
代数上的加法
要计算点的加法的话，我们必须把前面的几何学的讨论转到代数上的讨论。最直接的方法是把上面的公理用代数上的公式表示出来，但是这件事情会很乏味而且需要解决一些三次方程。所以在这里我就只给出结果吧。
首先，声明下我们暂时不讨论一些特殊情况。比如我们已经知道了P+(-P)=0，P+0=0+P=P，所以，接下去我们不考虑这两种情况。我们考虑的是 非0，非对称的点 P和Q，如下图
[声明下，因为编辑器的问题，下文中将用P=(xP,yP)(P是下标)来表示这种等式，否则一直贴图排版很累]
如果xP≠xQ(P和Q是下标)，那么该直线的斜率是：
该直线与椭圆曲线相交的第三个点R(xR,yR)(R是下标)：
或者也可以写成：
特别强调一下
(xP,yP)+(xQ,yQ)=(xR,-yR)（P，Q，R都是下标）。
如果要检查结果是否正确，我们需要检查R是否在椭圆曲线上，以及P，Q和R是否都在直线上。检查这些点是否在直线上是显而易见的，然而检查R是否属于椭圆曲线并不是，因为我们不得不解决一个一点都不有趣的三次方程问题。
考虑这么一个例子：根据我们给出的，给定的P=（1，2）和Q=（3，4）都在曲线上y2=x3-7x+10（y的2次方，x的3次方），那么P+?Q=-R=（-3，2）。反过来去根据我们前面的公式验证该结果是否正确：
验证正确！
注意，即使P或者Q是切点，该等式依然成立。拿P=(-1,4) Q=(1,2)尝试下：
得到的结果是P+Q=(1,-2)，该结果与用该工具计算是一样的。
另一种情况P=Q则需要另外处理了：关于xR以及yR的公式是一样的，但是针对直线的斜率必须用另外的方式处理：
注意，该公式是由一下公式推导出来的：
为了证明该公式的正确性，有必要验证R是否属于椭圆曲线上，以及P和R连成的直线与椭圆曲线有且仅有2个交点。但是在这里，我们不作证明，先做个测试：P=Q=(1,2)
所以得出 P+P=-R=(-1, -4)。
除了加法之外，我们定义另外一个运算：标量乘法：
在这里n是一个自然数。嗯，我写了个用来玩标量乘法，有兴趣点击去试试吧。
该公式看起来计算nP需要计算n次加法。如果n是k个二进制位，那么该算法复杂度是O(2k)（2的k次方），计算量有点大。但是其实存在更快速的方案。
其中一个就是先做倍数再做加法。要了解基本原理还是直接看例子会比较快。假设n=151，其对应的二进制是。而该二进制数字可以转化为：
所以我们可以这么写：
所以，该运算过程是这样的：
取P的2倍，得到2P
把2P再取2倍，得到4P
4P加上2P加上P
4P再取2倍，得到8P
不取8P做运算
8P取2倍，得到16P
16P加上4P加上2P加上P
最终，要得到151P我们只是做了一些简单的倍数以及加法。
如果还是不清楚，可以看看下面的Python代码
def bits(n):
Generates the binary digits of n, starting
from the least significant bit.
bits(151) -& 1, 1, 1, 0, 1, 0, 0, 1
yield n & 1
def double_and_add(n, x):
Returns the result of n * x, computed using
the double and add algorithm.
result = 0
addend = x
for bit in bits(n):
if bit == 1:
result += addend
addend *= 2
return result
如果倍数和加法都是复杂度为O(1)的运算，那么该算法的复杂度就是O(log n)（或者O(k)）（考虑到k个bit的长度）。依然比O(n)的复杂度要好。
给定n和P，我们运算Q=nP至少需要一个多项式时间。但是如果反过来呢？如果我们知道Q和P，要反过来得到n呢？该问题被认为是对数问题。为了与其他加密算法保持一致性，我们称该问题为“对数”问题而非“除法”。
我并不清楚什么是“简单”的问题，但是从，很容易看出一些规则。举个例子，假设该曲线是
y2=x3-3x+1（y的2次方，x的3次方），P点是（0，1）。我们很容易验证得到，如果n是奇数，nP是在左半边坐标轴里，如果n是偶数，nP在右半边坐标轴里。如果做更多实验，甚至发现更多规则，最终可以写出算法让我们计算曲线可以更高效。
但是还有个算法问题：离散数学问题。在下篇文章里，我们会讨论如果我们减少椭圆曲线的域，标量乘法依然是个“简单”的数学问题，然而离散数学变成一个“困难”的数学问题。这种二元性就是椭圆加密算法的核心。
下篇文章，下周见。
注：该文章翻译自，如果有翻译不当的地方，请指正。
多年区块链行业研究者，首个装饰行业ERP完整解决方案提供者。连续创业者。曾任社交产品技术负责人，现任区块链产品技术负责人。
微信公众号：dreamcatcherfly
个人微信：shen_sens
参加比特币源码研读班后首次写作，看到前辈black写的有关密钥，地址写的很好了，就选了他没有写的椭圆曲线，斗胆写这一篇。 在密码学上有两种加密方式，分别是对称密钥加密和非对称密钥加密。 对称加密：加密和解密使用的同样的密钥。 非对称加密：加密和解密是使用的不同的密钥。 二战...
用两张图告诉你，为什么你的 App 会卡顿? - Android - 掘金Cover 有什么料？ 从这篇文章中你能获得这些料： 知道setContentView()之后发生了什么？ ... Android 获取 View 宽高的常用正确方式，避免为零 - 掘金相信有很多朋友...
用两张图告诉你，为什么你的 App 会卡顿? - Android - 掘金 Cover 有什么料？ 从这篇文章中你能获得这些料： 知道setContentView()之后发生了什么？ ... Android 获取 View 宽高的常用正确方式，避免为零 - 掘金 相信有很多...
这篇文章主要讲述在Mobile BI(移动商务智能)开发过程中，在网络通信、数据存储、登录验证这几个方面涉及的加密算法。 文章的具体内容包括：序言，对称密钥加密（分组密码、DES、3DES、AES），非对称密钥加密（RSA、ECC、数字签名），消息摘要算法（MD5、SHA、...
姓名：李浩然 学号： 转自：http://blog.csdn.net/Dreaming_My_Dreams/article/details/（有删改） 【嵌牛导读】：RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知...
去年翻译了三本书，《极简》是最先出版上市的，这本书的作者是现代最有影响力的极简运动倡导者之一，美国人乔舒亚o贝克尔（Joshua Becker），他用平实的语言向读者呈现出一种全新的生活方式、思维方式，倡导大家找出自己生命中的“重中之重”，拥有真正丰盈而幸福的人生。 文章开...
主持人：雪漠老师，社会上有很多诱惑，比如美食诱惑、物质诱惑、美色诱惑、金钱诱惑等等。我们该怎么面对这些诱惑，怎么战胜自己呢？ 雪漠：今天中午，袁总请我和一些朋友吃饭，饭菜非常丰盛，就像世界上的所有诱惑一样。我在品尝那一道道美味时，觉得非常好，也会多吃一点。但来到这里时，我会...
版权声明 作者：师北宸 本文发自微信公共帐号：digital_meme （数字弥母） 无需授权即可转载，转载请保留以上版权声明 过去一年，在「在行」上有将近100人约我「如何通过写作打造个人品牌」的话题，即使我现在已经将价格上调到1999元/小时来调节需求，每周仍有几位学员...
这是一部关于梦想的电影。看完电影的我，现在在想，是谁的梦想？是爸爸通过女儿实现了他自私的梦想，还是女儿实现了女儿自己的梦想？看到最后这些似乎合成了一个共同的梦想。这也是我随着故事的发展与思考，态度上发生的转变。不止单一一个层面的电影，我觉得是好电影，它更接近真实的生活。 一...
其实这句话，应该在很多场合都听过，而我有这样的体会，是昨天。 昨天在参加汕头市新春长跑十公里的时候，我跑出了自己最好的配速成绩——4'47''分钟/公里，平时自己不曾跑过这么快。我分析了下，让我配速增加的因素有三： 1、我并没有跟大部分人一样，开跑就冲。熟悉长跑的就知道，长...过作于,则,根据平行截割定理,得,由垂直弦的半径平分弦,最后的出结论.连接,由题的条件可得出,进而求出,由切割线定理即可得出结论.总结和,可以知道结论不变.
结论为.证明:过作于,则,,根据平行截割定理,得,又,;结论为.证明:连接,是切线,是圆心,.又,,,,.由,由切割线定理得,.在某些几何图形中,平行移动某条直线,有些几何关系保持不变.
本题考查的知识面很广,涉及切线的性质,切割线定理,要仔细审题.
3935@@3@@@@切线的性质@@@@@@260@@Math@@Junior@@$260@@2@@@@圆@@@@@@52@@Math@@Junior@@$52@@1@@@@图形的性质@@@@@@7@@Math@@Junior@@$7@@0@@@@初中数学@@@@@@-1@@Math@@Junior@@$3940@@3@@@@切割线定理@@@@@@260@@Math@@Junior@@$260@@2@@@@圆@@@@@@52@@Math@@Junior@@$52@@1@@@@图形的性质@@@@@@7@@Math@@Junior@@$7@@0@@@@初中数学@@@@@@-1@@Math@@Junior@@
@@52@@7##@@52@@7
第一大题，第11小题
第三大题，第10小题
第一大题，第1小题
求解答 学习搜索引擎 | 关于图形变化的探讨:(1)\textcircled{1}例题1.如图1,AB是圆O的直径,直线l与圆O有一个公共点C,过A,B分别作l的垂线,垂足为E,F,则EC=CF.\textcircled{2}上题中,当直线l向上平行移动时,与圆O有了两个交点{{C}_{1}},{{C}_{2}},其它条件不变,如图2,经过推证,我们会得到与原题相应的结论:E{{C}_{1}}={{C}_{2}}F.\textcircled{3}把直线1继续向上平行移动,使弦{{C}_{1}}{{C}_{2}}与AB交于点P(P不与A,B重合).在其它条件不变的情况下,请你在图3的圆中将变化后的图形画出来,标好对应的字母,并写出与\textcircled{1}\textcircled{2}相应的结论等式.判断你写的结论是否成立,若不成立,说明理由,若成立,给以证明.结论___.证明结论成立或说明不成立的理由(2)\textcircled{1}例题2.如图4,BC是圆O的直径.直线1是过C点的切线.N是圆O上一点,直线BN交1于点M.过N点的切线交1于点P,则P{{M}^{2}}=P{{C}^{2}}.\textcircled{2}把例题2中的直线1向上平行移动,使之与圆O相交,且与直线BN交于B,N两点之间.其它条件仍然不变,请你利用图5的圆把变化后的图形画出来,标好相应的字母,并写出与\textcircled{1}相应的结论等积式,判断你写的结论是否成立,若不成立,说明理由,若成立,给以证明.结论___.证明结论成立或说明不成立的理由:(3)总结:请你通过(1),(2)的事实,用简练的语言,总结出某些几何图形的一个变化规律___.椭圆曲线密码学简介 | 巴比特
椭圆曲线密码学简介
知道什么是公钥密码学的人可能已经听说过ECC、ECDH或是ECDSA。第一个术语是椭圆曲线密码学（Elliptic Curve Cryptography） 的缩写，后两个是基于它的算法名称。
如今，我们可以在、和中见到椭圆曲线加密系统，这是现代网络和IT世界所依赖的三种主要技术。比特币和其他加密货币就更不用说了。
在ECC流行起来之前，几乎所有的公钥算法都是基于RSA、DSA和DH ———— 基于模运算的可选加密系统。RSA及其友类算法在当前仍非常重要，经常与ECC一并使用。不过，RSA及其友类算法背后的原理很容易解释，因而被广泛理解，一些简单的实现也可以很容易编写出来；但ECC的实现基础对于大多数人来说仍很神秘。
通过一系列的博文，我打算用一个通俗的方式介绍椭圆曲线密码学。我的目标不是提供ECC完整和详细的指导（网上有这方面的充足信息），而是简单概述“ECC是什么、为什么它被认为是安全的”，避免把时间浪费在长篇的数学证明和恼人的实现细节上。我还将提供一些辅助示例以及可视化图形工具和脚本给大家使用。
具体来说，我将触及以下主题：
1. 基于实数域的椭圆曲线和群公理（本文中涉及）
2. 基于有限域的椭圆曲线和离散对数问题
3. 密钥对的生成以及两个ECC算法：ECDH和ECDSA
4. 破坏ECC安全性的算法，并与RSA作对比
为了能够理解本文所述的内容，你需要了解集（set)理论、几何、模运算等基本概念，并大致知道对称式和非对称式加密。此外，你需要清楚的知道什么是“易解”问题，什么是“难解”问题，以及它们在密码学中的角色。
准备好了吗？开始！
首先，什么是椭圆曲线？ 线上数学百科全书给出了一个极好并完整的。不过，针对我们的学习目的，椭圆曲线将简化为用下面这个等式所描述的点的集合：
其中， 4a3 + 27b2 ≠ 0 (这是为了排除)。上面的等式称为椭圆曲线的魏尔斯特拉斯范式（ Weierstrass normal form）
不同的椭圆曲线的不同形状 (b = 1, a 取值由 2 变化至 -3).
奇点类型: 左侧, 带一个尖角的曲线 (y2 = x3)。右侧, 带一个自交叉的曲线 (y2 = x3 – 3x + 2). 这两种都不是有效的椭圆曲线。
根据a和b的值，椭圆曲线在平面上可以呈现不同形状。可以很容易看出并验证： 椭圆曲线是关于x-轴对称的。为了实现我们的目标，我们还需要把一个无穷远点（亦称之为理想点) 视为椭圆曲线的一部分。从现在开始，我们将用符号0（零）来代表无穷远点。
如果我们想显式地将无穷远点纳入考虑，我们可以按如下的方式细化椭圆曲线的定义：
数学中的“群”是一个由我们定义了一种二元运算的集合，二元运算我们称之为“加法”，并用符号“+”来表示。为了让一个集合G成为群，必须定义加法运算并使之具有以下四个特性：
1. 封闭性：如果a和b是集合G中的元素，那么（a + b)也是集合G中的元素。
2. 结合律：(a + b) + c = a + (b + c);
3. 存在单位元0，使得a + 0 = 0 + a =a;
4. 每个元素都有逆元，即：对于任意a，存在b，使得a + b = 0.
如果我们增加第5个条件：
5. 交换律： a + b = b + a
那么，称这个群为阿贝尔（abelian)群。
配上通常概念的加法时，整数的集合Z就是一个群（同时还是个阿贝尔群）。而自然数的集合（N）就不是群，因为它不满足第4个特性。
“群”很有用，因为一旦我们证明它具备上述4个特性，那么我们就可以自由地获取到一些其他特性。比如：单位元是唯一的；此外，逆元也是唯一的，即：对于每一个a，存在唯一的一个b，使得a + b = 0 （我们可以将b写成-a）。后面我们会发现，群的这些特性以及其他存在的事实，或者直接或者间接，对于我们来说非常重要。
椭圆曲线的群公理
我们可以定义一个基于椭圆曲线的群。如下：
o 群中的元素是一条椭圆曲线上的点;
o 单位元为无穷远点O;
o 点P的逆元是其关于x-轴的对称点;
o 加法，满足以下规则: 对于3个处在同一直线上的非零点 P, Q 和 R, 它们的和 P + Q + R = 0.
同一直线上的三个点之和等于0.
注意一下最后一个规则，我们需要的只是三个点同线，与点的次序无关。这意味着，如果P、Q和R同线，那么P + (Q + R) = Q + (P + R) = R + (P + Q) = o o o = 0. 这样，我们直观地证明了我们的“+”运算既满足结合律也满足交换律：我们创建了一个阿贝尔群。
到目前还很不错。但我们如何实际计算任意两点之和呢？
得益于我们使用的是一个阿贝尔群，我们可以把 P + Q + R = 0 写成P + Q = –R。方程的这一形式，让我们可以推导出计算两点P和Q之和的几何方法：画一条过P和Q点的直线，这条直线与曲线相交得到第3个点R（这一事实意味着P、Q、R必然共线）。如果我们获取了该点的逆元-R，那么我们就得到了P + Q的结果。
过P和Q画一条直线。该直线与曲线相交与第3点R。与之对称的点-R即为P+Q 的结果
这种几何方法可以成立，但还需一些改进。特别是，我们需要回答以下几个问题：
o 当P = 0或Q = 0时怎么办? 显然，我们无法画任何直线（0点不在xy-平面上）。不过，由于我们定义了0点为单位元，所以，对于任意P和任意Q，都有：P + 0 = P ， 0 + Q = Q
o 当P= –Q时怎么办? 这种情况下，通过两点的直线是一条垂线，与曲线不会有第三个交点。不过，由于P是Q的逆元，那么由逆元的定义可知P + Q = P + (-P) = 0 .
o 当P= Q时怎么办? 这种情况下，经过该点的直线有无数条。事情开始有点复杂了。不过，先想像一个点 Q’ ≠ P。如果我们令Q’ 向P逼近，越来越靠近P会怎么样？
随着两个点越来越接近，过这两点的直线最终变成了曲线的切线
随着Q’ 趋向P, 过P和Q’ 的直线最终成为曲线的切线。看到这一点，我们可以定义 P + P = –R, 其中R是过P点的切线与曲线的交点。
o 当P ≠ Q，但找不到第三个点R时怎么办? 这种情况和上面那个非常类似。实际上，这是因为过P和Q的直线与曲线相切。
如果直线与曲线只有两个交点，那么该直线为曲线的切线。可以很容易地看出，两点相加的结果是其中一点的对称点
o 假设P是切点，在上一情况中，我们已经得出P + P = –Q. 等式现在变为 P + Q = –P。 如果Q 是切点，正确的等式应为 P + Q = –Q.
现在，用几何方法可以完全覆盖所有情况了。用一支铅笔和一把尺，我们可以做任意椭圆曲线上所有点的加法运算。如果你想试试，请到 HTML5/JavaScript visual tool 看一下，这是我建的一个工具，用来计算椭圆曲线的加法!
如果我们想把点的加法运算计算机来完成，那么需要将几何方法转化为代数方法。将上面描述的规则转换为一组公式看似简单，实际上是非常繁琐的，因为需要求解三次方程。因此，这里我只通报结果。
首先，先抛开最恼人的极端情况。我们已经知道P + (-P) = 0, 还知道P + 0 = 0 + P = P。所以，在我们的公式中 ，我们将避免这两种情况，只考虑两个非零、非对称点 P = (xP, yP) 和Q = (xQ, yQ).
如果 P 和 Q 不相同， (xP ≠ xQ), 过这两点的直线斜率为:
该直线与椭圆曲线交于第三点 R = (xR, yR):
或是, 等价形式:
因此，(xP, yP) + (xQ, yQ) = (xR, –yR) (注意正负号，记住P + Q = –R).
如果我们想检查这一结果是否正确，我们将不得不检查R是否在曲线上，同时P、Q、Q是共线。检查点是否共线轻而易举，但检查R是否在曲线上就不容易了，因为需要求解三次方程，这可不是什么好玩的事儿。
不过，我们可以用一个例子来试一下：根据 可视化工具的计算， 当 P = (1, 2) 、Q = (3, 4) ，椭圆曲线 y2 = x3 – 7x + 10, 两点之和 P + Q = –R = (-3, 2). 让我们看一下与我们的公式是否一致:
好的，正确!
注意上面的公式即使在其中一个点P或Q是切点的情况下也成立。让我们试一下P = (-1, 4) 、 Q = (1, 2).
我们计算出 P + Q = (1, -2), 与使用 可视化工具计算出的结果相同。
P = Q 的情况需要做点不同的处理：方程中 xR 和 yR 相同, 由于 xP = xQ, 我们必须使用不同的公式来计算斜率：
注意，我们可以料到，m的表达式实际是下面这个函数的一阶导数:
为了证明结果的有效性，只要检查R是否在曲线上，以及P和R在曲线上只有两个交点就足够了。但同样，我们不去证明这一事实，而是试算一个例子: P = Q = (1, 2).
公式计算出 P + P = –R = (-1, -4).正确!
尽管推导过程真的是极其繁琐，不过最后的公式还是很简洁。这要感谢魏尔斯特拉斯范式：要是没有这一范式，最后的公式会真的又长又复杂。
在加法之外，我们还可以定义另一种运算：标量乘法，即：
nP，其中n为自然数。我为标量乘法也写了个 可视化工具 ，如果你想试算时可以使用。
用这种形式表示时，计算nP似乎需要n次加法运算。如果n有k个二进制位，那么算法的时间复杂度将为O（2^k)，这真不是很好。不过存在一些更快的算法。
其中一种是“加倍（double)与相加（add)”算法。
计算的原理可以用一个例子来更好地解释。取n = 151。它的二进制表示形式为 。这一二进制表示形式可以转换为一系列2的幂之和。
(取n的 每个二进制位上的数字，并用它乘以一个2的幂.)
用这种方法，我们可以将n这样写:
“加倍（double)与相加（add)”算法需要这样做:
o 加倍，得到2P.
o 2P与P相加(为了得到 21P + 20P).
o 加倍 2P，得到22 P.
o 与前一结果相加 (得到 22P + 21P + 20P).
o 加倍 22P，得到23P.
o 对23P不做任何操作.
o 加倍23P，得到24P.
o 与前一结果相加 (得到 24P + 22P + 21P + 20P).
最后，我们可以计算151 o P ，只需7次“加倍”运算和4次“相加”运算。
如果还不够清楚，这里有一个实现该算法的python代码段：
如果“加倍”和“相加”操作复杂度均为O(1),那么 该算法的时间复杂度为O(log n) (或是O(k)，如果我们考虑的是二进制位的长度），这相当不错。比最初O(n)的算法肯定要好得多。
给定n和P, 我们现在至少有一个多项式时间算法来计算Q = nP。不过，逆运算需要计算多少轮呢？如果已知Q和P，我们想求解n会怎么样？这一问题被称为对数问题。我们称之为“对数”而不是“除法”是为了与其他加密系统（在术语上）保持统一（那些系统中，不称“乘法”，而称“幂”）。
我不知道任何关于对数问题的“易解”算法，不过，通过摆弄乘法 ，很容易发现一些模式。例如，对于曲线 y2 = x3 – 3x + 1和点 P = (0, 1). 我们可以立即验证出, 如果n为奇数，nP在曲线的左半面，如果n为偶数，nP在曲线的右半面。如果我们尝试更多次，我们或许可以找出更多的模式，最终可以让我们写出一个算法来高效计算那条曲线的对数问题。
不过，对数问题有一个变体：离散对数问题。在下一篇博文中，我们将看到，当我们对椭圆曲线的域进行缩减后，标量乘法仍旧”易解“，而离散对数问题成为了”难解”问题。这种双重性是椭圆曲线密码学的关键基石。
补充一下 公式 Xr =
m ^2 – Xp – Qq 是怎么推导出的：
关于三次方程的求解过程，此处不再赘述。有兴趣的可以看一下这个视频：https://www.youtube.com/watch?v=7leAwQHVvz0
求解后，得到三个根：
单独求任何一个根都很麻烦，不过，如果把三个根相加会发现：x1 + x2 + x3 刚好等于 -b，也就是只与其中二次方项的系数b有关。
由于我们已经知道曲线上的两个点Xp和Xq了，那么求Xr就有了简单方法：
由直线方程可知：(y – y1) = m (x – x1)， y = m(x – x1) + y1。 ……(1)
将（1）代入到椭圆方程 y2 = x3 + ax + b ……(2)
得到： [m(x - x1) + y1] 2 = x3
+ ax + b …….(3)
通过判别式判断出这个三次方程有三个解，所以（3）也可以改写成下面的形式
（x – x1) (x – x2)(x – x3) = 0 ……..(4)
根据前面的推导，可知这个三次方程的三个根之和等于左边这个二次方项的系数。
由（3）式可知，其中二次方项的系数为m2，所以 x1 + x2 + x3 = m2.
解得第三个点 x3 =m2 – x1 – x2
m2 – Xp – Qq
———————————————————————————
作者：ANDREA CORBELLINI
译者：chehw (htc.)
BTC地址：1CHEp8QzFtfvwXrreoeA6wmKc7cudWD3kv
责编：printemps
稿源（译）：
版权声明：
作者保留权利。文章为作者独立观点，不代表巴比特立场。
您需要登录后才可以回复
为何不去吧下一篇最关键的部分翻译一下啊大神
感谢译者，但是文章还没到讲密码学本身的部分，一直在说数学基础，，，，戛然而止，在下一篇文章中才提到了密码学本身，使得标题显得有点文不对题。
我在想，能看懂吗，挑战吧
椭圆曲线密码学简介 – 知道什么是公钥密码学的人可能已经听说过ECC、ECDH或是ECDSA。第一个术语是椭圆曲线密码学（Elliptic Curve Cryptography） 的缩写，后两个是基于它的算法名称。http://t.cn/RLx6NX9
该直线与椭圆曲线交于第三点 R = (xR, yR):
xR = m ^ 2 – xP – xQ
这个公式怎么来的？
解三次方程非常复杂，要想说清楚，需要的文字恐怕比原文还要长。
可以直接套用已知的定理：
由直线方程可知：(y – y1) = m (x – x1)， y = m(x – x1) + y1。 ……(1)
将（1）代入到椭圆方程 y^2 = x^3 + ax + b
……(2)
得到： [m(x - x1) + y1]^2 = x^3 + ax + b
…….(3)
通过判别式判断出这个三次方程有三个解，所以（3）也可以改写成下面的形式
（x – x1) (x – x2)(x – x3) = 0
……..(4)
还有一个已知定理是: 这个三次方程的三个根之和等于其中二次方项的系数。（别问我怎么推导出来的，我觉得推导过程已经超出了地球人的思维）
由（3）式可知，其中二次方项的系数为m^2，所以 x1 + x2 + x3 = m ^2.
解得第三个点 x3 = m^2 – x1 – x2
这是我年内看到最好的文章！
//@潦源: 转发微博
回复@TOMMYTP先生:文章下面有作者的打赏地址哦
//@疯狂-BTC:转发微博
很不错的翻译，赞一个。
好，空了仔细研读一番
8比特应该改成微博长文，给大家打赏机会。
顶这个翻译也好厉害。