Digd0g's Blog

有限域上的椭圆曲线点群与椭圆曲线密码算术

发表于 更新于 分类于 ，
本文字数： 4.2k 阅读时长 ≈ 15 分钟
       
-------------已经到底啦！-------------
 

椭圆曲线密码的出现代表：可以使用比RSA短的多的密钥得到相同的安全性，减少处理负荷。

椭圆曲线方程

椭圆曲线的形状并不是椭圆的。只是因为椭圆曲线的描述方程，类似于计算椭圆周长的方程
$$
y^2=x^3+ax+b
$$

椭圆曲线在射影平面上需要满足Weierstrass 方程
$$
y^2z+a_1xyz+a_3yz^2 = x^3+a_2x^2z+a_4xz^2+a_6z^3是Weierstrass方程（维尔斯特拉斯，Karl Theodor Wilhelm Weierstrass,1815-1897），是一个齐次方程。
$$
从曲线图我们得知椭圆曲线关于x轴对称(有时也不一定)并且定义中还包含一个称为**无穷远点或者零点的元素，极为O

P+Q= -R，可以这么理解：这条曲线上的所有点构成了一个Abel群，群的性质中有一条，任意两点之和还在这个这个群里面；在曲线图形上的体现就是，任意两点的连线与曲线的另一个交点的镜像是这两个点的和。

椭圆曲线是光滑的，所以椭圆曲线上的平常点都有切线。而切线最重要的一个参数就是斜率k

Proof
$$
求椭圆曲线方程y^2+a_1xy+a^3y=x^3+a_2x^2+a_4x+a_6上，平常点A(x,y)的切线的斜率k。
$$

$$
解：令F(x,y)= y^2+a_1xy+a^3y-x^3-a_2x^2-a_4x-a_6
\求偏导数:
F_x(x,y)= a_1y-3x^2-2a_2x-a_4
\ F_y(x,y)= 2y+a_1x +a_3
\ 则导数为：f’(x)=-F_x(x,y)/F_y(x,y)=-( a_1y-3x^2-2a_2x-a_4)/(2y+a_1x +a_3)
= (3x^2+2a_2x+a_4-a_1y) /(2y+a_1x +a_3)
\ 所以k=(3x^2+2a_2x+a_4-a_1y) /(2y+a_1x +a_3)
$$

椭圆曲线的加法运算

定义：如果其上的3个点位于同一直线上，那么它们的和为O

  1. O为加法单位元，对椭圆曲线上任一点P，都存在P+O=P
  2. 设P1=(x,y)是椭圆曲线上一点，则加法逆元定义为P2=-P1=(x,-y)
  3. 在P点做椭圆曲线的一条切线，设切线与椭圆曲线交于S，定义3P=P+P+P=2P+P

有限域上的椭圆曲线

椭圆曲线是定义在实数域上的，实数是连续的，进而导致了曲线的连续。因此，把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上，这样才能用于加密。

关于有限域的定义请看我的这一篇博客
$$
y^2=x^3+ax+b(a,b\in GF(p),\quad4a^3+27b^2\neq0)
$$

$$
E_p(a,b)上的加法定义如下:设P,Q\in E_p(a,b)
$$

  1. 若P=O，则P+Q=Q；否则若Q=O，P+Q=P

  2. $$
    若x_1=x_2,且y_1=-y_2,则P+Q=O
    $$

  3. $$
    记\quad \lambda=\begin{cases} \frac {y_2-y_1}{x_2-x_1}, & P \neq Q \ \frac {3x_1^2
    +a}{2y_1}, & P = Q \end{cases}
    $$

$$
x_3=\lambda^2-x_1-x_2, \quad y_3=\lambda(x_1-x_3)-y_1 \quad —> \quad P+Q=(x_3,y_3)
$$

Sage建立一个椭圆曲线

1
2
3
4
E = EllipticCurve(GF(23), [1, 1])
show(E)
E.plot()

枚举该曲线上所有的点

1
2
3
E = EllipticCurve(GF(23), [1, 1])
E.points()
#[(0 : 1 : 0), (0 : 1 : 1), (0 : 22 : 1), (1 : 7 : 1), (1 : 16 : 1), (3 : 10 : 1), (3 : 13 : 1), (4 : 0 : 1), (5 : 4 : 1), (5 : 19 : 1), (6 : 4 : 1), (6 : 19 : 1), (7 : 11 : 1), (7 : 12 : 1), (9 : 7 : 1), (9 : 16 : 1), (11 : 3 : 1), (11 : 20 : 1), (12 : 4 : 1), (12 : 19 : 1), (13 : 7 : 1), (13 : 16 : 1), (17 : 3 : 1), (17 : 20 : 1), (18 : 3 : 1), (18 : 20 : 1), (19 : 5 : 1), (19 : 18 : 1)]

$$
有限域F_{23}上的椭圆曲线的点集F：y^2=x^3+x+1
$$

0，1 0，22 1，7 1，16 3，10 3，13 4，0 5，4 5，19
6，4 6，19 7，11 7，12 9，7 9，16 11，3 11，20 12，4
12，19 13，7 13，16 17，3 17，20 18，3 18，20 19，5 19，18

$$
由E_p(a,b)的产生方式知道，-P也是E_p(a,b)上的一个点；令P=(13,7)\in E_{23}(1,1),-P=(13,-7)且由有限域知，-7mod23 \equiv16,\quad \therefore-P=(13,16)存在与该表中
$$

1
2
3
4
#有限域椭圆曲线上进行加法
E = EllipticCurve(GF(23), [1, 1])
print(E(0, 22) + E(1, 7))
#(17 : 3 : 1)

$$
以E_{23}(1,1)为例，P(0,22),Q(1,7),则P+Q=?
$$

$$
【Proof】\lambda= \frac {7-22}{1}=-15\equiv 8mod23;
\quad x_3=8^2-0-1\equiv63\equiv17mod23;
\quad y_3=8(0-17)-22\equiv-158\equiv3mod23
$$

和sage算出来的一样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# ECC在Fp域上加法、倍乘运算

# 求value在Fp域的逆——用于分数求逆
def get_inverse(value, p):
    for i in range(1, p):
        if (i * value) % p == 1:
            return i
    return -1

# 求最大公约数——用于约分化简
def get_gcd(x, y):
    if y == 0:
        return x
    else:
        return get_gcd(y, x % y)  

#calculat P+Q
def calculate_p_q(x1,y1,x2,y2,a,b,p):
    flag = 1  # 控制符号位
    
    if x1 == x2 and y1 == y2:  # 若P = Q，则k=[(3x1^2+a)/2y1]mod p
        member = 3 * (x1 ** 2) + a  # 计算分子
        denominator = 2 * y1        # 计算分母

    else: # 若P≠Q，则k=(y2-y1)/(x2-x1) mod p
        member = y2 - y1
        denominator = x2 - x1 
        if member* denominator < 0:
            flag = 0
            member = abs(member)
            denominator = abs(denominator)
    
    # 将分子和分母化为最简
    gcd_value = get_gcd(member, denominator)
    member = member // gcd_value
    denominator = denominator // gcd_value

    # 求分母的逆元    
    inverse_value = get_inverse(denominator, p)
    k = (member * inverse_value)
    if flag == 0:
        k = -k
    k = k % p

    # 计算x3,y3
    """
        x3≡k^2-x1-x2(mod p)
        y3≡k(x1-x3)-y1(mod p)
    """
    x3 = (k ** 2 - x1 - x2) % p
    y3 = (k * (x1 - x3) - y1) % p
    return [x3,y3]
    
#calculat nP
def calculate_np(p_x, p_y,a,b,p,t):
    tem_x = p_x
    tem_y = p_y
    times=t
    for i in range (1,t):
         p_value = calculate_p_q(tem_x,tem_y, p_x, p_y,a,b,p)
         tem_x = p_value[0]
         tem_y = p_value[1]
    return p_value
        
# F：y^2=x^3+x+1(mod 23)
#a, b, p = 1, 1, 23

#calculat P+Q, p=(3,10) q=(9,7)
print(calculate_p_q(3,10,9,7,1,1,23))
 
 #calculat 20P, p=(3,10)
print(calculate_np(3,10,1,1,23,20))

有限域上椭圆曲线离散对数问题

$$
设E是有限域F_p上的椭圆曲线，P,Q\in E(F_p)，典型的就是给定P和nP，求出n的值；记作n=log_p(Q),并称 p是以 Q为底 的椭圆曲线离散对数。
$$

$$
设F_{73}上的椭圆曲线：E:y^2=x^3+8x+7\quad P=(32,53) \quad Q(39, 17),计算得知Q=11P,于是log_p(Q)=11
$$

1
2
3
4
5
6
E = EllipticCurve(GF(73), [8, 7])
P = E(32, 53)
Q = E(39, 17)

P.discrete_log(Q)
# 11
1
2
3
4
5
6
7
Jarvis OJ: 简单ECC概念
已知椭圆曲线加密 Ep(a,b) 参数为 p = 15424654874903,
a = 16546484, b = 4548674875, G(6478678675,5636379357093)
私钥为 k = 546768，求公钥 K(x,y)
提示：K=kG

注：题目来源XUSTCTF2016
1
2
3
4
5
6
#sage:
E = EllipticCurve(GF(15424654874903), [16546484, 4548674875])
G = E(6478678675,5636379357093)
K=546768*G
K.xy()
#(x,y)(13957031351290, 5520194834100)

椭圆曲线加密

根据加法法则，计算K很容易但反过来，给定K和G，求k就非常困难。因为实际使用中的ECC原则上把p取得相当大，n也相当大，要把n个解点逐一算出来列成上表是不可能的。这就是椭圆曲线加密算法的数学依据 。

点G称为基点（base point）
k ( k < n ) k(k<n) k(k<n)为私有密钥（private key）
K为公开密钥（public key)

下面是利用椭圆曲线进行加密通信的过程：

  1. 用户A选定一条椭圆曲线Ep(a,b)，并取椭圆曲线上一点，作为基点G。

  2. 用户A选择一个私有密钥k，并生成公开密钥K=kG。

  3. 用户A将Ep(a,b)和点K，G传给用户B。

  4. 用户B接到信息后 ，将待传输的明文编码到Ep(a,b)上一点M（编码方法很多，这里不作讨论），并产生一个随机整数r（r<n）

  5. 用户B计算点
    $$
    C_1 = M + r K \quad C_2 = r G
    $$

  6. 用户B将 C 1 、 C 2 传给用户A。

  7. 用户A接到信息后，计算
    $$
    C_1-kC_2 结果就是点M。再对点M进行解码就可以得到明文。
    因为 C_1 − k C_2 = M + r K − k ( r G ) = M + r k G − k r G =M
    $$

p越大安全性越好，但会导致计算速度变慢

优点 缺点
安全性能更高：160位ECC与1024位RSA、DSA有相同的安全强度 设计困难，实现复杂
处理速度更快：在私钥的处理速度上，ECC远 比RSA、DSA快得多 如果序列号设计过短，那么安全性并没有想象中的完善
带宽要求更低
存储空间更小：ECC的密钥尺寸和系统参数与RSA、DSA相比要小得多

椭圆曲线应用

ECDLP

​ 有限域上椭圆曲线用于建立公钥密码系统，其安全性基于椭圆曲线上有理点加法群离散对数问题（ECDLP）的难解性。目前一般椭圆曲线上的离散对数问题还没有有效的计算方法，而这也是现代密码学中最具挑战性的问题之一。ECDLP 可简要描述为：已知 G 为曲线上的加法子群且 G 的群阶为大素数 r，P 为 G 的生成元。随机选取 G 中元素 R，计算正整数 k 使得𝑅 = [𝑘]𝑃，或者表示为 𝑘 = 𝑙𝑜𝑔p𝑅。目前计算该问题的方法主要包括通用算法和特殊算法

​ 那么针对离散对数，因为有限域中的离散对数问题还可用亚指数时间的指标演算法求解，而一般的 ECDLP 目前没有亚指数时间的求解算法，故而它被认为比有限域乘法群中的离散对数问题更加难以求解。

​ 所以现在ECC上的离散对数常见算法主要有大步-小步法、 Pollard’s rho 算法等，而且当参数设定不当时，ECDLP也会存在一定的漏洞，此时MOV 攻击可以利用双线性对将 ECDLP 求解转为有限域中乘法群的 DLP 求解

​ 如果选择的椭圆曲线有理点的阶等于一些小素数因 子的乘积, 那可以用 Pholig-Hellman 算法来求解相应的 ECDLP

通用算法：Pollard’s rho 算法（是一种用于分解质因数的算法），Pollard’s kangaroo 算法，以及大步小步法（BSGS）等均可用于求解一般有限群上的离散对数问题。目前在一般情况下，计算 ECDLP 也只有通用算法奏效，其时间复杂度为Ｏ（√𝑟）。2009 年 Bailey 等人针对 Certicom 公司提出的 ECC 挑战利用 Pollard’s Rho 算法计算ECC2K-130 上的 ECDLP

特殊算法：在一些特殊曲线上，可以将 ECDLP 转化到其他群上的离散对数问题弱化其难解性，已有研究主要包括：

  1. ***将 ECDLP 约化到有限域上的离散对数问题(DLP)**。如 SSSA 攻击 将异常椭圆曲线(有理点群阶等于有限域大小)上的 ECDLP 约化到有限域加法群的 DLP，MOV 攻击*则利用椭圆曲线上的双线性映射将定义在有限域𝐹_p上的ECDLP，归约到有限域𝐹pk乘法群上的离散对数问题，此方法在嵌入次数 k 较小时有效。

  2. 利用 Weil 下降等技术将椭圆曲线上的有理点群转化为另一类几何对象 (如超椭圆曲线上 Jacobian 或高维 Abel 簇)，将 ECDLP 复杂性减弱（目前高亏格 HECDLP 存在比通用算法更有效的算法）

举个例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#题目来源自第四届（2019）全国高校密码数学挑战赛赛题一-ECDLP.pdf
椭圆曲线参数形式为
E/F_p: y^2=x^3+ax+b,n:=#E(F_p ),P∈E(F_p),r:=order(P),R∈<P>.
求解k,1≤k≤r,s.t.R=[k]P.

第一类曲线参数：
(1)  p:= 211108170305887; a:=0;b:=7;n:=p;r:=p;
P:=( 47815642535808, 116240163507508);
R:=( 77983503452527, 143728424564583);

(2) p:= 13835058061724614657; a:=0;b:=20;n:=p;r:=p;
P:=( 616859655854051956, 12065166484289278801);
R:=( 5170466145333976578, 7139090565738339416);

(3) p:=906694364778591846139117; a:=0; b:=2;n:=p;r:=p;
P:=(475325122433864976165476 ,666857317692667708141096 );
R:=(519814743429987512024682, 392414632044199857512746);

(4) p:= 59421121885714719481295537269; a:=0;b:=10;n:=p;r:=p;
P:=(17547290159953212409742744311, 23276625757393135830641872446);
R:=(22782721588122522786532109807, 29566916200346945584248955766);

(5) p:=3894222643901127098494944603540019; a:=0; b:=2;n:=p;r:=p;
P:=(3474281736844926688615305014567004, 3343311742974261537268420184037101);
R:=(46006664812763786791056435590121, 1631023347800240287678172773820495);

(6) p:= 255211775190703851000955237173238443091; 
a:=0;b:=32;n:=p;r:=p;
P:=(82054120567654459070422632716611948091,
208358019881453692582450632924824868211);
R:=(54625405255845450735684923869953661538,
82751760415032967427013207973543496169);

(7) p:=16725558898897967356385545845388318567564081; 
a:=0; b:=39;n:=p;r:=p;
P:=(15866255640827385375149316462253403735143979, 13637900016555731147592334085022810288787804);
R:=(1641844846280313158776293444944029290477363, 1916339757694211104728115095781816602417918);

(8) p:= 1096126227998177188652856107362412783873814431647; 
a:=0;b:=5;n:=p;r:=p;
P:= (83173790821618364013911485269418053634749973470, 331912486564013055335956381322549180967694844964);
R:=(163008382252281273947629676562612579052560281605, 50645003441262331054159546612247657430098333396);

第二类曲线参数：
(9) p:= 140737488356467; a:=1;b:=0;
n:= 140737488356468; r:= 35184372089117;
P:=( 59477512413747, 79851403980273);
R:=( 125962305399026, 124644987166940);

(10) p:= 9223372036854782251; a:=1;b:=0;
n:= 9223372036854782252; r:= 2305843009213695563;
P:=(8930887567779448763 , 890632237231967440);
R:=( 4707122633993752935 , 3224323188778636920);

(11) p:=604462909807314587364667;a:=1;b:=0;
n:=604462909807314587364668; r:=151115727451828646841167;
P:=(587411173575122535454189, 184243119926212298785598);
R:=(539012794797204313781763, 513627008874848913042314);

(12) p:= 39614081257132168796771986051; a:=1;b:=0;
n:= 39614081257132168796771986052;
r:= 9903520314283042199192996513;
P:=( 17135037968192446511660916347 , 15756828316532436197954290560);
R:=( 14307140364976860571933505517 , 31289859728052046761658770776);

(13) p:=2596148429267413814265248164627363;a:=1;b:=0;
n:=2596148429267413814265248164627364;
r:=649037107316853453566312041156841;
P:=(622497953272208887929891881018762, 578415484635633376407094129167605);
R:=(1641315995010304174750922058961802, 498062680065145119027669812682594);

(14) p:= 170141183460469231731687303715884123283; a:=1;b:=0;
n:= 170141183460469231731687303715884123284;
r:= 42535295865117307932921825928971030821;
P:=(67561795560749592594257348250381095281 ,132967032564783335773794402620839168397);
R:=( 81767392472072972289932811718039895097 , 74483734086357842747707740743879456218);

(15) p:=11150372599265311570767859136324180753031283;a:=1;b:=0;
n:=11150372599265311570767859136324180753031284;
r:=2787593149816327892691964784081045188257821;
P:=(10280081406291279076050813261615407334758360, 10524832460733629896529554181939223304289725);
R:=(1653939556554266819965991031125172966638801, 8370614898071115688249737076845551200138218);

(16) p:= 730750818665451459101842416358141509827966272147; a:=1;b:=0;
n:= 730750818665451459101842416358141509827966272148;
r:= 182687704666362864775460604089535377456991568037;
P:=(221903508784709687556506235376523499020990986034 , 287854209568598432667871196372312232614552000893);
R:=( 219270464789952726868617287704232288912801490505, 578348937880270477205296252062048509994911317888);

第三类曲线参数：
(17) p:= 140737488355333; a:=-3;b:=234;
n:= 140737484527007;r:=n;
P:= (118344265104828, 25754556069705);
R:=( 8594518695631, 14966619423525);

(18) p:= 9223372036854775837; a:=-3;b:=37;
n:= 9223372038068412403;r:=n;
P:=(7220661838117791356 ,6477969291505257777);
R:=( 7819726923954549567 ,6266868167000835108);

(19) p:=604462909807314587353111;a:=-3;b:=95;
n:= 604462909807750541909849;r:=n;
P:=(428432040100075198254744, 95025782588400118295756);
R:=(472138605558837378507194, 138148835226095728614736);

(20) p:= 39614081257132168796771975177; a:=-3;b:=562;
n:= 39614081257132147751873462213;r:=n;
P:=(39220344157117715096559716859 , 3087260393566610895498596606);
R:=( 13160703755766149325136222951 , 6533567029273948676370251736);

(21) p:= 2596148429267413814265248164610099; a:=-3;b:=171;
n:= 2596148429267413788194246433592681;r:=n;
P:=(177627746966506201527866528484813 , 1735330667419561032038559795836927);
R:=( 1575178132453901115471501570466697, 538238983595050290992251454098891);

(22) p:= 170141183460469231731687303715884105757; a:=-3;b:=33;
n:= 170141183460469231728561996679834270597; r:=n;
P:=( 96152442714630401692673834213524521597 , 58626340067602219522071225434282008266);
R:=( 47795192678737921133501161460114957836 , 166078919686417913546029950371468891352);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
// 大步小步法对离散问题
#include<bits/stdc++.h> 
#define mo 211108170305887LL //模数
#define a 0LL
#define b 7LL
#define x first
#define y second
using namespace std;
using LL=long long;
#define Point pair< LL,LL >

Point P={47815642535808LL, 116240163507508LL};
Point R={77983503452527LL, 143728424564583LL};
Point inv;
LL ans,block,sz;
map<Point,LL> M;

LL mul(LL p,LL q) //快速乘模
{
	p=(p%mo+mo)%mo,q=(q%mo+mo)%mo;
	return ((p*q-(LL)((long double)p/mo*q+1e-6)*mo)%mo+mo)%mo;
}

LL quick_power(LL p, LL q)  //快速幂
{
	LL res=1LL,base=p;
	while(q)
	{
		if(q&1LL)
			res=mul(res,base);
		base=mul(base,base);
		q>>=1;
	}
	return res;
}

Point Point_square(Point Q)  //点的平方
{
	Point P;
	LL tmp=mul((3LL*mul(Q.x,Q.x)%mo+a)%mo,quick_power(2LL*Q.y%mo,mo-2LL));
	P.x=(mul(tmp,tmp)-2LL*Q.x%mo+mo)%mo;
	P.y=(mul(tmp,(Q.x-P.x+mo)%mo)-Q.y+mo)%mo;
	return P;
}

Point Point_mul(Point P, Point Q)  //点的乘积
{
	if(P==Q)
		return Point_square(P);
	Point res;
	LL tmp=mul((Q.y-P.y+mo)%mo,quick_power((Q.x-P.x+mo)%mo,mo-2LL));
	res.x=(mul(tmp,tmp)-Q.x+mo-P.x+mo)%mo;
	res.y=(mul(tmp,(P.x-res.x+mo)%mo)-P.y+mo)%mo;
	return res;
}

Point Point_quick_power(Point p, LL q)  //点的快速幂
{
	Point res=p,base=p;
	--q;
	while(q)
	{
		if(q&1LL)
			res=Point_mul(res,base);
		base=Point_mul(base,base);
		q>>=1LL;
	}
	return res;
}

int main()
{
	Point PP=P,QQ=R;
	block=LL(sqrtl(mo))*10LL;  //定义分块个数，乘以10是一个内存限制的体现
	sz=(mo-1)/block+1;  //求出块的大小
	inv=Point_quick_power(P,sz);  //P^-sz
	inv.y=mo-inv.y;
	for(int i=1;i<=sz;i++)
	{
		M[PP]=i;
		PP=Point_mul(PP,P);
	}
	printf("%d",M.size());
	for(int i=0;i<=block;i++)
	{
		if(i%(block/100)==0)
			printf("%d\n",i);
		if(M.count(QQ))  //找到碰撞，求出答案
		{
			printf("%lld",i*sz+M[QQ]);
			break;
		}
		QQ=Point_mul(QQ,inv);  //求出新的QQ
	}
	return 0;
}

大概四分钟跑出来了，还是第一组的第一个数据，可想而知第22个数据需要跑多久了了。这也正正体现了离散对数中求k的困难型，成本十分巨大。

Bitcoin

⼀个⽐特币钱包中包含⼀系列的密钥对， 每个密钥对包括⼀个私钥和⼀个公钥。 私钥k 是⼀个数字， 通常是随机选出的。

⽐特币⽹络中的所有⼈都可以通过所提交的公钥和签名进⾏验证， 并确认该交易是否有效， 即确认⽀付者在该时刻对所交易的⽐特币拥有所有权。（⼤多数⽐特币钱包⼯具为了⽅便会将私钥和公钥以密钥对的形式存储在⼀起。 然⽽， 公钥可以由私钥计算得到， 所以只存储私钥也是可以的。

公钥和私钥之间的数学关系， 使得私钥可⽤于⽣成特定消息的签名。 此签名可以在不泄露私钥的同时对公钥进⾏验证。

公钥⽤于接收⽐特币， ⽽私钥⽤于⽐特币⽀付时的交易签名。

⽀付⽐特币时， ⽐特币的当前所有者需要在交易中提交其公钥和签名（ 每次交易的签名都不同， 但均从同⼀个私钥⽣成）

有了私钥， 我们就可以使⽤椭圆曲线乘法这个单向加密函数产⽣⼀个公钥K .有了公钥K ， 我们就可以使⽤⼀个单向加密哈希函数⽣成⽐特币地址A 。

⽐特币使⽤了 secp256k1 标准所定义的⼀条特殊的椭圆曲线和⼀系列数学常数。

私钥k

1
1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD

生成公钥

1
2
{K = k * G}
# K = 1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD * G

EC ElGamal

EC ElGamal是ECC的一种，把ElGamal移植到椭圆曲线上来实现

AND一些其他问题，这里就不一一列出了，个人能力也十分有限等学到后再补上。

如果您觉得有所收获的话，还希望不要吝啬您的赞，也欢迎您请我喝奶茶哦

参考：

1
2
3
4
5
6
7
8
9
10
11
颜松远，椭圆曲线[M]，大连理工大学出版社，2011.05
杨波，现代密码学(第4版)[M]，清华大学出版社，2017.07
[1] Hankerson D., Menezes A.J.,Vanstone S.: Guide to Elliptic Curve Cryptography. 
Springer, Heidelberg (2004)
[2] Bailey D., Batina L., Bernstein D.J., Birkner P., Bos J.W., et al .: Breaking 
ECC2K-130. Cryptology ePrint Archive, Report 2009/541 (2009)
[3] Smart N.P.: The discrete logarithm problem on elliptic curves of trace one. J. 
Cryptol. 12, 193-196 (1999)
[4] Menezes A.J., Okamoto T., Vanstone S.A.: Reducing elliptic curve logarithms to 
logarithms in a finite field. IEEE Trans. Inf. Theory. 39(5), 1639 -1646 (1993)