谁能最简单的详解椭圆曲线算法，secp256k1 是如何生成公钥和私钥的？

quasiceo 2018-03-13

展开全文

简单且详细讲解椭圆曲线加密法原理，网上大多数写的是云里雾里，好让我们这个智力平平的众生能理解。

------------------------------------------------------------>
题主的问题是“最简单的详解椭圆曲线算法”，我理解为用最基础的数学知识来解释椭圆曲线密码。
实际上椭圆曲线密码是一种公钥密码算法，公钥密码算法最根本的原理是利用信息的不对称性：即掌握私钥的人在整个通信过程中掌握最多的信息【上（开）帝（图）视（可）角（耻）】，一切的运算对他而言都是没有秘密的。为了让别人能给自己发送加密的信息，私钥拥有者把信息的一部分公开披露，披露的信息记为公钥。显而易见，一个公钥密码算法安全的必要条件（非充分）是“由公钥不能反推出私钥”。
/* 先看一个栗子：
小明就读于小学二年级，会计算加法，但是不会计算除法。你是小明的怪蜀黍大强，你想出一道题给他做，让他虽然能理解题目意思但是做起来有难度：
强：“小明小明，过来，叔叔问你，1+1等于几？”
明：“叔叔的大学白念了吧，我幼儿园就会了，等于2。”
强：“那考你个难的，7+7等于几？”
明：“切，你当人家上课啃铅笔头，下课帮小红写作业都是白干的是吧。手指都不用数，等于14呗。”
强：“行，有叔叔当年的风采，那叔叔再问你，几个7相加等于56？”
明：“……”，默默掏出草稿纸、铅笔、手指头、脚趾头，进行了10分钟的深度计算:2个7等于14，3个7等于21，4个7等于28……。“叔叔,我算出来了，是8个，对不对？”
强：“好小子，叔叔就不信考不倒你。几个7相加等于864192？” 你心中默念，以小明的计算能力，要算到这个数恐怕得一年半载的。
明：“叔叔好厉害呀，我算不出来。”
//明天去考考小红看她会不会算几个7等于56，不会算我就交她，嘿嘿。”
*/
与上述例子相同的是，椭圆曲线密码也是一个基于加法阶数难求问题的密码方案。 对于椭圆曲线密码来讲，椭圆曲线的基点就是例子里面的7，而私钥就是基点的加法阶数（例子里面的8），公钥是基点（7）进行对应阶数的加法（8次）得到的结果（56）。
与上述例子不同的是，椭圆曲线密码里的加法建立在 “有限域上的二元三次曲线上的点”上，组成一个“有限加法循环群”。（好拗口的一句话。。）具体的说，这个加法的几何定义如下面两个图，两个点的加法结果是指这两点的连线和曲线的交点关于x轴的镜像。

图1：两个不同的点相加

图二：两个相同的点相加

看完这两幅图，默默思考1秒钟,你可能要问（炸）了（毛）：为啥要这么定义加法？我还是喜欢小明的那个加法题，不喜欢这个。
之所以这么定义，原因有两个：
（1）给你求逆向运算（由公钥计算私钥）的时候制造困难。要是像小明一样在整数群里做加法，恐怕这密码体制只能用来给小红写信。
（2）为了构造一个封闭的“较好的”代数结构，简化正向运算（由私钥计算公钥的运算）。要是单纯为了求解困难，那可以定义五光十色的加法，但是加法定义的随性将导致了运算的复杂。为了能用一些最基本的运算：比如结合律、比如减法，才这么定义让这些点构成一个群。

行了，有了加法以后，我们只需要考虑两件事：
（1）如何正向计算（由私钥计算公钥）：
确定椭圆曲线一个点作为基点P，由于所有的点构成一个有限群，那么基点P必然可以作为一个生成元生成一个子群。记这个子群的阶数为n，也就是说P点累加n次得到群的单位元（无穷远点），记做nP=0。（注意此处0只是一个代号，代指无穷远点，因为我们习惯了用0来表示加法单位元。）
正向计算的定义很简单，私钥为 $K\in [0,n)$ ; 基点为点;公钥点Q定义为个相加： $Q=\underset{K}{\widehat{\underbrace{P+P+\cdots +P)}}}$ （原谅我公式写不好）。

先说相加，最不济的算法就是直接相加K次，求解完毕，好一点的方法是使用二进制梯子来加，这样需要进行t次倍点（相同点相加）和t/2次点加（不同点相加），其中 $t=log_{2}K$ ：

当然还有更好的算法，比如说非相邻表示法（NAF）、窗口法等，此处不多说。

再说第二个问题，怎么用代数的方法求出两点相加。这恐怕得用一点高中数学了，此处直接上公式：
以域特征不等于2或3的定义在素数域GF(p)上曲线为例，曲线方程为： $y^{2}=x^{3}+ax^{2}+b$

从这两公式可以看到，要求点相加，只需要进行一些有限域的加减乘除即可。
事实上，加减乘除复杂度的关系如下：除法>乘法>加减。为了提高运算效率，往往在运算中把一个点的坐标保留分数的形式如： $(\frac{x}{z},\frac{y}{z})$ 。运算过程中一直保留分数，直到运算结束再做一次除法，回到有限域，这种算法叫做投影坐标。
有了投影坐标以后，一次正向计算（私钥求公钥）其实就是一系列的乘法、加法、减法。当然，此处的乘法、加法、减法都是素数域上的运算。为了快速计算素数域乘法(实际上就是模乘)，又诞生了一系列算法：蒙哥马利模乘算法，Barrett模乘算法等，都是通过预计算加快求模速度的算法。

（2）逆向计算（公钥反推私钥）有多难：
密码学家都既是大强也是小明，大强给小明出了题，必须让他算不出来，小明懂的东西一天天变多、计算速度一天天变快，大强的题也得一天天变复杂。
据本人的了解，目前由椭圆曲线公钥求解私钥的最有效算法复杂度为 $O(\sqrt{p})$ ,其中是阶数的最大素因子。当参数选的足够好让 $p>2^{160}$ 时，以目前的计算能力，攻破椭圆曲线是不现实的。
但是，小明哪天长大，谁知道呢？小明哪天有了（量子）计算器，怎么难倒他呢？
嗯，对，欢迎来到密码学。。

编辑于 2016-04-23

Chizhong Jin

那么说吧，假设这个世界上所有的人都会乘法，却没有人会除法。

那么在这个世界上会发生一些奇怪有趣的事情。

有一天张三挑出了两个数字，123，456。

由于张三会乘法，于是乎张三计算出了：

123 * 456 = 56088

于是张三告诉你：

123 * ??? = 56088

你是个天资卓绝的人，但是没办法，上天不允许你会除法，因此你没法知道张三说的???是什么。

当然了，别人也不知道，因为张三没有告诉其他人???是啥。

有一天，你打算告诉张三一个秘密，67。但是你又不想别人知道。于是聪明绝顶的你随手选了一个数字222。计算出：

123 * 222 = 27306

56088 * 222 + 67 = 12451603

然后你对张三说：

123 * ??? = 27306

56088 * ??? + x = 12451603

当然，你聪明绝顶，张三聪明秃顶，于是张三一寻思：

123 * ??? * 456 = 56088 * ???

这上下一减，x = 12451603 - 27306 * 456 = 67

哎妈呀，这x就这么被传递过来了。

如果我们把上面的过程写成数学公式的话，就是

G * k = K (G,K公开，k保密)

c1 = G * M

c2 = K * M + x (M随机选取，x为要加密的数字，M和x都保密)

x = c2 - c1 * k

= K * M + x - G * M * k

= G * M * k + x - G * M * k (消除左右两侧的G * M * k)

= x

当然了，事实上，这个世界上，谁都会除法，直接K / G就算出k了。

但是这个不打紧，我们把问题升级一下：

假设这个实际上所有人都会算指数，却没有人会算对数。

那么：

G ^ k = K

c1 = G ^ M

c2 = K ^ M * x

x = c2 / (c1 ^ k)

其实问题是完全一样，对于上面这个问题来说，其实就是需要3个运算：

一个任意定义的加法，需要满足： a + b + c + d .... 任意调换顺序后 c + a + d + b ... 结果一致

一个定义的减法，满足 a + b - b = a

一个定义的乘法： a * n = a + a + a + a ... // n个a相加

以及一个难以简单计算的除法：a * b / b = a

在我们举例的指数的例子里，其实我们就是把+定义为数值相乘，-定义为相除，*定义为数值自己乘自己n次。/本质是就是对数

但是其实要找到一组运算+ - *很简单，/却很难，这个事情并不容易。

一群大神们苦心搜索，终于找到一个诡异的加法运算:

哈哈哈，吓到了吧，上面长的像ru头的tmd竟然是椭圆曲线啊，妈蛋这和椭圆是哪门子亲戚啊？？？

其实这货的方程是 y^2 = x^3 + ax + b。（这也tmd的和椭圆搭不上亲戚啊，感情这是uncle-in-law啊。。。。）

至于大神们是如何证明这么诡异的加法运算满足交换律结合律就不是我等凡夫俗子所能回答的了哈。

发布于 2018-02-01

景辰

科技互联网

一文读懂比特币私钥、公钥、钱包地址的来历和关系

对比特币熟悉的朋友一定都知道，买卖比特币最后都是通过一个钱包地址来实现的，就像我们日常使用的银行卡卡号，我们随便找一个比特币的钱包地址，大家看一下：

1QCXRuoxWo5Bya9NxHaVBArBQYhatHJrU7

但是当谈到比特币的钱包地址是如何算出来的时候，可能就很少有人能够说清楚了。

下面，景辰通过实际计算，来给大家讲解一下比特币的钱包地址是怎么来的，公钥、私钥是怎么来的，以及他们三者之间的关系。

下面的过程你不一定懂得转换的原理，知道他们流转的过程就可以了。

众所周知，比特币是建立在数学加密学基础上的，而不是像银行卡那样是基于信用的，基于信用体系的银行卡卡号我们都熟悉，是我们在向银行申请银行卡的时候银行给随机发的，那么比特币的钱包地址是怎么来的呢？

在《比特币：一种点对点的电子现金系统》一文中，中本聪提到了用椭圆加密算法（ECDSA）来产生比特币的私钥和公钥。

基于椭圆加密的原理，由私钥是可以计算出公钥的，再由公钥经过一系列数字签名运算就会得到比特币钱包地址。

因为由公钥可以算出比特币地址，所以我们经常把公钥和比特币地址的说法相混淆，他们都是指的同一个概念，比特币钱包地址只是另一种格式的公钥，但是两者的外在表现形式是不一样的。

那么我们就可以梳理出一个脉络了：

私钥 —— 公钥 —— 比特币钱包地址

从比特币私钥得到我们日常转账所用的比特币钱包地址总共需要九个步骤，中间用到了SHA256加密、RIPEMD160加密和BASE58编码。

下面，我们以实际案例来模拟一下整个流程：

第一步：生成随机私钥

私钥是一个随机数，随机选取一个32字节的数，这个数的范围大小是介于1 ~ 0xFFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141之间的一个数，为了方便后面的计算，我们随机生成一个合法的私钥：

8F72F6B29E6E225A36B68DFE333C7CE5E55D83249D3D2CD6332671FA445C4DD3

第二步：椭圆曲线算公钥

生成了私钥之后，我们使用椭圆曲线加密算法（ECDSA-secp256k1）计算私钥所对应的非压缩公钥，生成的公钥共65字节，其中一个字节是0x04，其中32个字节是X坐标，另外32个字节是Y坐标：

公钥P.X：

06CCAE7536386DA2C5ADD428B099C7658814CA837F94FADE365D0EC6B1519385

公钥P.Y：

FF83EC5F2C0C8F016A32134589F7B9E97ACBFEFD2EF12A91FA622B38A1449EEB

第三步：计算公钥的SHA-256哈希值

将上述公钥地址拼合，得到标准地址：

0406CCAE7536386DA2C5ADD428B099C7658814CA837F94FADE365D0EC6B1519385FF83EC5F2C0C8F016A32134589F7B9E97ACBFEFD2EF12A91FA622B38A1449EEB

对齐进行SHA-256哈希计算，得到结果：

2572e5f4a8e77ddf5bb35b9e61c61f66455a4a24bcfd6cb190a8e8ff48fc097d

第四步：计算 RIPEMD-160哈希值

取上一步结果，进行RIPEMD-160计算，得到结果：

0b14f003d63ab31aef5fedde2b504699547dd1f6

第五步：加入地址版本号（比特币主网版本号“0x00”）

取上一步结果，在前面加上16进制的00，即：

000b14f003d63ab31aef5fedde2b504699547dd1f6

第六步：计算 SHA-256 哈希值

取上一步结果，进行SHA-256计算，可得：

ddc2270f93cc84cc6869dd373f3c340bbf5cb9a8f5559297cc9e5d947aab2536

然后，对以上结果再次计算 SHA-256 哈希值，得到：

869ac57b83ccf75ca9da8895823562fffb611e3c297d9c2d4612aeeb32850078

第七步：取上一步结果的前4个字节（8位十六进制）

869ac57b

第八步：把这4个字节加在第五步的结果后面

作为校验位，将这4个字节加载第五步的结果后面，这就是比特币地址的16进制形态了：

869ac57b000b14f003d63ab31aef5fedde2b504699547dd1f6

第九步：用Base58编码变换一下地址

对上一步的结果进行Base58编码，得到：

1QCXRuoxWo5Bya9NxHaVBArBQYhatHJrU7

这就是我们经常看到的传统意义上的比特币钱包地址了。

以上步骤可以简化为下图所示：

我们经常说的比特币公钥就是指的图中第二步所产生的结果，而HASH160指的是第四步RIPEMD160签名所产生的结果，由于RIPEMD也是一种HASH算法所以就统称为HASH160了，而我们常用的比特币地址就是经过BASE58编码后的结果。

编辑于 2017-07-22

呼呼然

都不是事儿～～

不好意思让大家久等了，最近太忙，现在添加一个例子。
首先写一下椭圆曲线加密的“和”值算法，这个算法是必须的也是核心，之后只需要将点带入计算就可以得到“和”值了。
假设曲线y^2=x^3+ax+b(mod p)上有两点P1(x1,y1)，P2(x2,y2),现在要计算P3(x3,y3)=P1+P2：
首先算法中需要一个辅助值m，其中满足
（1）P1！=P2时--->m=(y2-y1)*(x2-x1)^(-1) mod p;
（2）P1==P2时--->m=(3*x1^2+a)*(2*y1)^(-1) mod p;
那么现在就来计算x3和y3
x3=m^2-x1-x2 (mod p) ,y3=m(x1-x3)-y1 (mod p)
公式可能大家觉得有点复杂，那么现在就用实例来说明，假设p=5,a=2，那么就是有
y^2=x^3+2x+3 (mod 5)，取x=0,1,2,3,,4,带入计算，那么则有
x=0 ==> y^2=3 ==>(3<5) 无解;
x=1 ==> y^2=6=1 ==>y=1,4mod5; （根据映射）
x=2==> y^2=15=0 ==>y=0mod5;
x=3 ==> y^2=36=1 ==>y=1,4mod5;
x=4==> y^2=75=0 ==>y=0mod5;
所以现在就有点(1,1),(1,4),(2,0),(3,1),(3,4),(4,0),还有个无穷~
现在取P1=(1,4)，P2=(3,1),则P3=(1,4)+(3,1)
m=(1-4)/(3-1)=-3*2^(-1)======(特别注意！！！！！！！！！！！！！这里对2^(-1)的定义为x*2=1mod5,x为满足表达式的任意值。)
所以m=-3*3=1mod 5，x3=2mod5,y3=0mod5，故P3=(2,0)
也就是说，在曲线y^2=x^3+2x+3 (mod5)上，得到（1,4）+（3,1）=（2,0），也就是（2,0）也在曲线上。
先补充这么多，打的心好累。。。。
===========================================
忙完了先来大概写一下。椭圆曲线加密体制(Elliptic Curve Cryptography,ECC)所追求的是获得同样级别的安全性，而需要的二进制位较少。因此ECC体制的数学计算较之此前的加密算法更加复杂，其每个数学的操作代价也都更加昂贵。（近几年美国政府公开的加密标准基本都是基于ECC的）
不同于基于模运算的方法，ECC主要使用的是“和”值，这个“和”既有几何上的意义，又有算数上的解释。而椭圆曲线E就是某个具体函数的图形，然后看下图

其中P1和P2是一条直线与曲线相交通过这两点，该直线往往会与椭圆曲线在另一点处相交。如果上述条件成立，就将该交叉点围绕x轴做对称映射，获得对称点P3，此时得到了“和”值定义：
P3=P1+P2
（一定要知道这不是加法，而是几何上的“和”！！！）
并且这个式子中的“加”法是ECC中唯一需要的数学运算。
之后便是具体的运算了，从加密的角度看，我们希望处理的是离散的点集，因此要在椭圆曲线计算式上执行“mod P”运算。
手机码字很困难-_-||，先写到这里吧，有兴趣我再往后写。（后面的计算公式手机太难打出来了(´-ω-`)！）

编辑于 2016-04-26

张凡

大道至简

ECC可以看certicom公司的教程，浅显易懂，而且还有动态演示。

ECC Tutorial

编辑于 2017-07-09

黑照

计算机有关专业硕士

最简单的描述，
K=kG
作者重新定义了椭圆曲线的加法和乘法。并且保证不可逆。
之后通过一系列复杂的计算算出了公钥和加密算法。比如
y^2=Ax^3+Bx^2+Cx+D
然后Alice计算出来一个参数
(x1,y1) 告诉A,B,C,D到Bob,Bob对应的计算出来（x2,y2）
然后双方通讯，就可以使用公钥私钥对进行加解密了。
PS:对不起。具体细节我把书送给老师了。手头没有资料可以查
PS:开始了解这个算法的时候我也看了ECC加密算法入门介绍。到现在都不懂。我也不是数学系的。
PS:我很后悔当时没有把这个书上的东西记下来。现在只有一点皮毛的。那本书是《深入浅出密码学――常用加密技术原理与应用（安全技术经典译丛）》（美）帕尔，（美）佩尔茨尔　著，马小婷　译
PS：最后我很讨厌很简单的东西说的很复杂。在上面这本书大概几面纸加上最基础不超过两位数的算例就解决的问题，上面硬是讲的超级复杂。

发布于 2014-01-27

吴三牛

这个系列写的非常详细，且通俗易懂。

Elliptic Curve Cryptography: a gentle introduction

编辑于 2017-04-28

华桦

Trying to figure out everything.

http://mp.weixin.qq.com/s/jOcVk7olBDgBgoy56m5cxQ

莱迪思公众号一篇文章讲得蛮好的。

编辑于 2017-07-12

知乎用户

很多人第一次听说椭圆曲线密码算法（以下简称ECC）是由于比特币使用该算法做身份认证。而比特币选择的椭圆曲线是名为secp256k1的曲线。这个题目应该也是因此而提出来。

实际上ECC很早就渗透进我们的生活里面，比如很多使用HTTPS连接的网站就是用ECC做服务器身份认证和密钥交换的。

关于ECC的原理，可以参考我的另一个回答：

关于密码中的RSA算法和ecc(椭圆曲线)算法加密过程是怎样的?www.zhihu.com

这里主要介绍secp256k1的公钥和私钥是怎么生成的以及它们是怎么使用的。

secp256k1是一条用于密码学的椭圆曲线，它总共包含以下6个参数：

(p,a,b,G,n,h)

下面分别进行介绍。

首先是参数 a,b ，这里的a和b就是椭圆曲线方程 y^2=x^3+ax+b 中的a和b。也就是这两个参数决定了secp256k1所使用的椭圆曲线方程。secp256k1中它们的值分别是：

a = 0

b = 7

所以方程是 y^2=x^3+7 ，在实数域上画出来是这样的：

然后是参数。因为密码学上使用的椭圆曲线都是在有限域上定义的，对于secp256k1来说，它使用的有限域是 GF(p) ，也就是它的曲线方程实际上是 $y^2=x^3+7 \mod p$ 。的具体值是：

$p= 2^{256}−2^{32}−2^9−2^8−2^7−2^6−2^4−1$

然后是参数。是椭圆曲线上的一个点，称为基点。对于secp256k1，它的具体值是：

$G=(55066263022277343669578718895168534326250603453777594175500187360389116729240,\\ 32670510020758816978083085130507043184471273380659243275938904335757337482424)$

然后是参数。它是使得 nG=0 的最小正整数。

注意这里的乘法是指定义在曲线 $y^2=x^3+7 \mod p$ 上点的乘法，0是指曲线上的零点（无穷远点）。

具体值是：

$n= 2^{256} - 432420386565659656852420866394968145599$

最后是参数。一般取 h=1 。它是椭圆曲线群的阶跟由生成的子群的阶的比值。是设计secp256k1时使用的参数，在具体实现中使用这个参数主要是出于安全性考虑，忽略它不影响理解。

上面这些就是secp256k1曲线包含的参数及其意义。

下面介绍公钥和私钥是如何生成的。因为这里已经事先选定了secp256k1，所以步骤只有两步：