椭圆曲线加密
- 参考博客：ECC椭圆曲线详解(有具体实例) - Yumeka - 博客园 (cnblogs.com)
- [ECC椭圆曲线加密算法—加解密（SageMath实现） - lnjoy - 博客园 (cnblogs.com)](https://www.cnblogs.com/lnjoy/p/ecc.html#:~:text=简介. ECC椭圆曲)
- 椭圆曲线 (sagemath.org)
- 椭圆曲线 - 杰哥的知识库
前言
-
椭圆曲线，英文名称为
Elliptic Curve。是代数几何中的一种曲线，椭圆曲线常用于现代密码学。 -
椭圆曲线加密，英文名称为
Elliptic Curve Cryptography，才是我们经常所的ECC。 -
以下为几个常见的椭圆曲线加密的实际应用：
ECDH，即椭圆曲线迪菲-赫尔曼密钥交换ECDSA，即椭圆曲线数字签名算法；还有一种数字签名算法为EDDSAECIES，椭圆曲线集成加密方案Elliptic Curve PGP，即椭圆曲线PGP加密- 在比特币和区块链中也使用ECC
-
这里先来介绍几个椭圆曲线的常见型式。椭圆曲线方程常见的型式有：
Weierstrass标准方程、Montgomery曲线、Edwards曲线。其中Weierstrass标准方程是椭圆曲线中加密的最常见的方程型式。接下来逐个介绍一下这些方程的型式。
型式1(Weierstrass标准方程——简化形式)：
$$
\begin{array}{l}
椭圆曲线的标准方程型式如下:\
y^2=x^3+ax+b\
其中：\
x和y是椭圆曲线上的点坐标\
a和b是定义椭圆曲线的常数,且该常数要满足条件:4a^3+27b^2≠0\
即这个条件确保曲线没有奇点(如尖点或自交点)
\end{array}
$$
型式2(Montgomery曲线)：
$$
\begin{array}{l}
该曲线的形式如下:\
By^2=x^3+Ax^2+x
\end{array}
$$
型式3(Edwards曲线)：
$$
\begin{array}{l}
x^2+y^2=1+dx^2y^2
\end{array}
$$
椭圆曲线基础
- 虽然椭圆曲线有椭圆两个字，但是和椭圆的关系并不大，所以这里就不多介绍椭圆。
椭圆曲线的定义
- 椭圆的定义是采用
Weierstrass标准方程定义的 - 定义如下：
$$
\begin{array}{l}
在\mathbb{R}^2上的曲线(即在平面上的曲线)，曲线上每一点(x,y)满足:\
要求4a^3+27b^2≠0，这种型式叫做Weierstrass型式
\\该型式的齐次方程为:\\
~~~~~~Y^2Z+a_1XYZ+a_3YZ^2=X^3+a_2X^2Z+a_4XZ^2+a_6Z^3
\end{array}
$$
## 椭圆曲线上点的运算
+ 我们在椭圆曲线上定义了加法运算、乘法运算。首先要明白，这个运算并不是数与数的加法运算，而是椭圆曲线上的点的加法运算。
+ 椭圆曲线上的点有一个比较奇特的地方，就是经过一些操作，椭圆曲线上的点满足群的运算性质。即满足群的定义：封闭性、结合律、单位元、逆元（如果是没有学过一点抽像代数就比较难理解，这就好比人为自定义的一个运算，比如小学我们学习乘法，3个相同的数相加就可以表示为这个数乘3，所以椭圆曲线上的加法运算、乘法运算只是人为定义，并且满足一定性质的运算。）
+ 接下来介绍一下我们是如何定义椭圆的上的加法等运算。这里先用一个比较直观的椭圆曲线去理解椭圆曲线的上定义的运算。
### 运算过程
+ 这边使用了`GeoGebra`画出了没有奇点的椭圆曲线，该椭圆曲线的方程和图像如下：
$$
y^{2}=x^3-x+1
$$
+ 我现在任意取椭圆曲线上的两点P、Q(若P、Q两点重合，则作P点的切线)，作直线交于椭圆曲线的另一点`R'`，过`R'`做y轴的平行线交椭圆曲线于R，则我们定义`P+Q=R`。这就是椭圆曲线上的加法，并且这个加法同样满足交换律、结合律，即`P+Q=Q+P=R`,`(P+Q)+C=P+(Q+C)=D`。具体加法过程如下图所示：
+ 上图介绍了椭圆曲线的加法，接下来介绍一下椭圆曲线的乘法，假设P是椭圆曲线上的一个点，则椭圆曲线上的`2P=P+P`即，当上图的Q与P重合的时候，过点P做切线，然后交椭圆曲线为另一个点`R'`，过`R'`做y轴的平行线，交椭圆曲线为`R`则R这个点就是`P+P=R`的结果，下面为具体的图片
+ 这样我们就可以引出`3P`的运算，`3P=P+P+P=2P+P`。
+ 所以我们就可以先求得`2P`的结果即点`R`
+ 然后我们再过点`P`和`R`做一条直线，交椭圆曲线为另一个点`H'`
+ 最后过`H'`做y轴的平行线，该平行线交椭圆曲线为`H`点，`H`点即为所求。
+ 具体图像如下图所示,图中的H点即为所求，即`3P=H`
### 运算定义
+ 举了个实例后就可以更明白椭圆曲线的加法和乘法运算了。
+ 接下来就具体说明一下椭圆曲线的加法的定义，在椭圆曲线上，可以定义点之间的加法运算，满足：
1. 单位元$O$为无穷点
2. 对于曲线上两点$P$和$$Q$$,取经过$$P$$和$$Q$$的直线，这条直线与椭圆曲线相交于最多三个点，其中两个点是$$P$$和$$Q$$，
如果第三个点存在且不和$$P、Q$$重合，记第三个点为$$R$$,那么满足$$P+Q+R=O$$，也就是$$P+Q=-R$$
3. 对一点$$R=(x_p,y_p)$$,其相反数$$-R=(x_p,-y_p)$$,也就是沿$$x$$轴对称的点
### 代数运算
+ 知道了椭圆曲线上点的运算规律，接下来就需要将椭圆曲线的点的运算转换为代数运算，这样才能求得椭圆曲线点的具体值。
## 有限域椭圆曲线
+ 椭圆曲线是连续的，这并不适合加密。而通过上面的运算可以知道，对X、Y坐标的计算只涉及到了加减乘。所以可以把其坐标换到其他域上。
+ 所以我们把椭圆曲线定义在有限域上。对于有限域，如果没有学抽象代数的话也并不是很理解有限域，对于有限域上的椭圆曲线，简单的理解为对椭圆曲线方程进行模运算。这里也给出有限域椭圆曲线的定义。
$$
\begin{array}{l}
在有限域上，椭圆曲线的定义通常是给定一个特定的有限域\mathbb{F}_q和一个椭圆曲线标准方程\\
对于有限域\mathbb{F}_q上的椭圆曲线,方程通常具有如下形式:\\
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~y^2\equiv x^3 + ax+b(mod~q~)\\
其中:\\
(1)a和b是给定的常数属于\mathbb{F}_q\\
(2)x和y是椭圆曲线上的点的坐标,它们的值属于有限域\mathbb{F}_q\\
(3)q是有限域的阶数,通常为素数p或素数的幂p^n
\end{array}
$$
**注意**：从有限域椭圆曲线的定义中可以得到x、y、a、b的取值只能在模数q的范围之内，且是一个正数。
+ 下图是我生成的一个有限域上椭圆曲线的图像，该有限域椭圆曲线的图像和方程如下：
$$
\begin{array}{l}
y^2\equiv x^3 -x+1(mod~101~)
\end{array}
$$
+ 从上方我们就可以发现，我们把之前连续的椭圆曲线，通过限制有限域，将图像变成离散。这样就更有利于加密，使得密文更不容易破解。
### 有限域上椭圆曲线的运算
+ 有限域上椭圆曲线的运算其实和正常的椭圆曲线上的运算差别不大，只是多了一个取模的步骤。
## (补充)特殊椭圆曲线图像
+ 这时其中一种不平滑的椭圆曲线，这种椭圆曲线是奇异的
+ 这是第二种奇异的椭圆曲线图，这里被挖掉了几个点
# sage与椭圆曲线
+ 在sage中有与椭圆曲线相关的类·，而在Python中没有，接下来就来介绍一下sage如何定义椭圆曲线和对椭圆曲线进行运算。
+ 在sage中`sage.schemes.elliptic_curves.constructor.EllipticCurveFactory`中有定义椭圆曲线类。
+ 在sage中的椭圆曲线方程默认为Weierstrass标准方程，即
$$
y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
$$
## 创建椭圆曲线类
+ 我们可以使用`EllipticCurve([a1,a2,a3,a4,a6])`，定义一个正常的椭圆曲线。
+ 我们还可以这样定义`EllipticCurve([a4,a6])`，定义一个`a1,a2,a3`都为0的椭圆曲线。
+ 我们还可以使用`EllipticCurve(GF(p),[a4,a6])`或`EllipticCurve(GF(p),[a,1,a2,a3,a4,a6])`来定义一个有限域上的椭圆曲线，其中`GF(p)`一个有限域`Fp`
## 椭圆曲线点相关
+ 椭圆曲线加密的是基于点的运算，所以ECC加密中，点的运算是很重要的。所以sage中椭圆曲线类也有相关方法去对椭圆曲线上的点进行操作
# 椭圆曲线加密
## 椭圆曲线Elgamal加密
+ 可以利用椭圆曲线实现`Elgamal`加密算法，其中`Elgamal`其实是基于离散对数问题的加密方案。
## ECC保密通信算法
+ `A`选定椭圆曲线E，并取椭圆曲线上的一点G**作为基点**
+ `A`再选择一个私有密钥`p`，并生成公钥`K=pG`
+ 然后`A`将`椭圆曲线E`、`公钥K`、`基点G`都传给`B`，自己则保留一个私钥`p`
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])# 定义一个有限域上的椭圆曲线
G = E.random_point() # 在该有限域上的椭圆曲线随机生成一个基点G
d = getPrime(256) # 生成私钥
K = d*G # 生成公钥
print("有限域上的椭圆曲线方程为:",E)
print("私钥为:",d)
print("公钥为:",K)
print("基点为:",G)
"""
有限域上的椭圆曲线方程为: Elliptic Curve defined by y^2 = x^3 + 34074834305188571141621784296213127818605719682511236882697040475349160662918*x + 63132765410951845376834020294406549474122314748305927686818130532536873941891 over Finite Field of size 81030663492019274685634371044174577656868933015941657714008669865992779042659
私钥为: 99810097591477275848902367520793650692915987115714414713302591310302269523321
公钥为: (80717954411716455917392752597469377265534463105017126347424985504514145340030 : 14147750910960321057471889563638948577248840688236726694878310015967182371744 : 1)
基点为: (41277325230094923827769782781870562338415098379333818899654876460813430152803 : 33183583264342591073816729856317076097935781827230667008430557415668571274778 : 1)
"""
+ `B`收到`椭圆曲线E`、`公钥K`、`基点G`后，先将消息`M`编码到椭圆曲线上一点`M`上，这个编码有很多种
+ `B`这边还要生成一个随机数`r`
+ `B`生成随机数后，计算`C1 = M+r*K`，`C2=r*G`
+ `B`再将`C1`和`C2`传给`A`
+ 这样`A`在收到`B`给的`C1`和`C2`就可以利用式子计算出M，`M=C1-p*C2`，数学推导过程如下
$$
\begin{array}{l}
C_1 = M+r*K\\
K=p*G\\
所以有:C_1=M+r*p*G
\\又已知:C_2=r*G
\\所以:p*C_2=p*r*G
\\所以:M=C_1-p*C_2
\end{array}
$$
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
from Crypto.Util.number import *
flag = b'flag{you_know_yixixi}'
p = 81030663492019274685634371044174577656868933015941657714008669865992779042659
a = 34074834305188571141621784296213127818605719682511236882697040475349160662918
b = 63132765410951845376834020294406549474122314748305927686818130532536873941891
E = EllipticCurve(GF(p),[a,b])
G = (41277325230094923827769782781870562338415098379333818899654876460813430152803,33183583264342591073816729856317076097935781827230667008430557415668571274778)
G = E(G)
M1 = bytes_to_long(flag[:len(flag)//2])
M2 = bytes_to_long(flag[len(flag)//2:])
M = (M1,M2) # 将消息编码到平面上一个点
K = (80717954411716455917392752597469377265534463105017126347424985504514145340030,14147750910960321057471889563638948577248840688236726694878310015967182371744)
# 使用公钥
G = E(G)
K = E(K)
r = getPrime(256) # 生成随机数r
print(r)
C1 = M[0]*G+r*K # 计算C1
C2 = M[1]*G+r*K # 计算C2
C3 = r*G # 计算C3
print(C1)
print(C2)
print(C3)
"""
65964405526157595714499022295389061886508913366432486863319174824978859701519
(69151207374963881506229419807414044606562589019128390449154463436113810170056 : 34212945283157084946826868040823333490762807263420338368084079939026517093747 : 1)
(20052133424534836327031887427641190087578911424005778789411093448513364175045 : 79290733772592920486937801634073957445824487251333206942425193951959204643346 : 1)
(13873839514926178929123206541508951197152950503924156547704705249810871181474 : 16649925998290493656119874109251230518218117755115487436290837089158719083016 : 1)
"""
+ 然后进行解密过程,由于映射方式选取的并不是特别好，所以最后解密只能使用爆破来得到明文。椭圆曲线对消息的不同映射对消息最后的恢复可能稍微有点影响。
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
from Crypto.Util.number import *
import libnum
p = 81030663492019274685634371044174577656868933015941657714008669865992779042659
a = 34074834305188571141621784296213127818605719682511236882697040475349160662918
b = 63132765410951845376834020294406549474122314748305927686818130532536873941891
E = EllipticCurve(GF(p),[a,b])
G = (41277325230094923827769782781870562338415098379333818899654876460813430152803,33183583264342591073816729856317076097935781827230667008430557415668571274778)
G = E(G)
d = 99810097591477275848902367520793650692915987115714414713302591310302269523321
C1 = (69151207374963881506229419807414044606562589019128390449154463436113810170056,34212945283157084946826868040823333490762807263420338368084079939026517093747)
C2 = (20052133424534836327031887427641190087578911424005778789411093448513364175045,79290733772592920486937801634073957445824487251333206942425193951959204643346)
C3 = (13873839514926178929123206541508951197152950503924156547704705249810871181474,16649925998290493656119874109251230518218117755115487436290837089158719083016)
C1 = E(C1)
C2 = E(C2)
C3 = E(C3)
D1 = C1 - p * C3
D2 = C2 - p * C3
for i in range(1,2**10):
if a == D1:
M1 = i
if a == D2:
M2 = i
print(libnum.n2s(int(M1)))
print(libnum.n2s(int(M2)))
"""
b'flag{you_k'
b'now_yixixi}'
"""
# 椭圆曲线题目
## ECC_level_1
+ 题目来源：攻防世界
1
2
3
4
5
6
7
8
9
已知椭圆曲线加密Ep(a,b)参数为
p = 15424654874903
a = 16546484
b = 4548674875
G(6478678675,5636379357093)
私钥为
k = 546768
求公钥K(x,y)
flag格式为cyberpeace{x+y的值}
+ 了解了一下ECC保密通信算法，就可以知道公钥的值，直接使用sage跑出结果
1
2
3
4
5
6
7
8
9
10
11
12
13
p = 15424654874903
a = 16546484
b = 4548674875
E = EllipticCurve(GF(p),[a,b])
G = (6478678675,5636379357093)
G = E(G)
k = 546768
K = k*G
print(K)
a = 13957031351290
b = 5520194834100
a = a + b
print("cyberpeace{"+str(a)+"}")
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 iyheart的博客！
wechat