概述

这里的椭圆曲线跟高中学的椭圆曲线方程啥的完全不是一回事。

ECC是椭圆密码学的简称，ECDH和ECDSA是基于椭圆密码学的具体算法。

椭圆曲线

在椭圆曲线密码学中，射影平面（Projective Plane）是一种用来定义和操作椭圆曲线上的点的数学结构。它是椭圆曲线上的有限点集合加上一个称为无穷远点的特殊点构成的。

一条椭圆曲线为在射影平面上满足Weierstrass方程的所有的点的集合，用Weierstrass公式加以描述的椭圆曲线$E$为：
$$
E:{(x,y)|y^2+A_1y=x^3+A_2x^2+A_3x+A_4}
$$
参数$A_1,A_2$决定了椭圆曲线的形状，实际常用的简化的Weierstrass方程（WNF）如下：
$$
E:{(x,y)|y^2=x^3+ax+b}
$$
我们在算法运算时需要使用WMF曲线的切线，所以需要使其处处光滑可导，需要判别式不为领，在方程中，有：
$$
\triangle=4a^3+27b^2≠0
$$
定义射影平面的无穷远点设为$0$，无穷远点是所有曲线在无穷远的交点，被称为理想点。这样，引入WNF的完整形式：
$$
E:{(x,y)\in R^2|y^2=x^3+ax+b,\triangle=4a^3+27b^2≠0}\cup{0}
$$

易发现椭圆曲线关于$x$轴对称。

在椭圆曲线密码中，一个符合要求的椭圆曲线应该是不含有奇异点的点。尖点和自相交点都属于奇异点。

当$\triangle≠0$时，曲线为非奇异，光滑的；$\triangle=0$时，曲线为奇异，不光滑的。

椭圆曲线群

数论中，群满足封闭性、结合律、逆元、单位元。满足交换律成为阿贝尔群。

对于椭圆曲线可以定义阿贝尔群：

1.群的元素是椭圆曲线点集合。

2.单位元是无穷远的点，记为$0$。

3.元素点$P$的逆元是关于$x$轴对称的点。

4.定义一条直线交椭圆曲线的三个非零点$P,Q,R$，有$P+Q+R=0$，运算与其顺序无关，满足结合律和交换律。

几何加法

取一条椭圆曲线，用它们的$x,y$坐标标记曲线上的两个点$P,Q$。画一条穿过两个点的直线。现在继续直线，直到它第三次与曲线相交。标记这个新的交点$R$。最后，取$R$并沿$y$方向反射它，得到$-R=R(x,-y)$。点相加的结果是$P+Q=-R$。

一些特殊点：

1.$P=0\ or \ Q=0$：$P+0=P$或者$Q+0=Q$。

2.$P=-Q$：$P+Q=P+(-P)=0$。

3.$P=Q$：让$Q’≠P$，使其无限接近于$P$，得到切线：$P+Q=P+P=-R$，$R$为切线和椭圆曲线的交点：

4.$P≠Q$：找不到第三点$R$，此时线$PQ$为椭圆曲线的切线，假设$P$为切点，$P+Q=-P$，假设$Q$为切点，$P+Q=-Q$：

代数加法

当$PQ$相等时，求直线斜率：$m=\frac{3x_P^2+A}{2y_P}$；当$PQ$不相等时，求直线斜率：$m=\frac{y_P-y_Q}{x_P-x_Q}$；

交点$R(x_R,y_R)$的坐标：
$$
\begin{cases}x_R=m^2-x_P-x_Q\y_R=y_P+m(x_R-x_P)\end{cases}
$$
得到$(x_P,y_P)+(x_Q,y_Q)=(x_R,-y_R)$

标量乘（加倍累加算法）

$$
nP=P+P+…+P
$$

介绍一个著名的加倍累加算法，直接举个例子：

对于$n=151$，二进制值为$10010111$，即为：
$$
\begin{align}
151 & = 1\times 2^7+0\times 2^6+0\times 2^5+1\times 2^4+0\times 2^3+1\times 2^2+1\times 2^1+1\times 2^0 \
& = 2^7+2^4+2^2+2^1+2^0 \
\end{align}
$$

$$
151\times P=2^7\times P+2^4\times P+2^2\times P+2^1\times P+2^0\times P
$$

接下来就可以从后往前倍加运算。

有限域椭圆曲线

模$p$整数域

这里简记模$p$整数域为$F_p$。

在$F_p$定义如下：
$$
E={(x,y)\in(F_p)^2|y^2=x^3+ax+b(\bmod p),4a^3+27b^2\not\equiv0(\bmod p)}\cup{0}
$$
这里的$0$还是位于无限远位置的点，$a,b$是域上的两个整数。在$F_p$下的椭圆曲线变成了不相连的离散点集合。

点加法

在实数域里，三个共线点的和为$0$，而在$F_p$下，共线的直线需要变为$ax+by+c\equiv 0(\bmod p)$。

在$F_p$下，仍有以下特性：

$Q+0=0+Q=Q$

对于$Q$的逆元$-Q$，如果在$F_{29}$上设$Q=(2,5)$，那么$-Q=(2,-5)=(2,24)$。仍有$P+(-P)=0$。

代数加法

和之前普通的代数加法一样，这里的代数加法只是多了个模$p$罢了：

如果$P+Q=-R$，有：
$$
x_R=(m^2-x_P-x_Q)(\bmod p)
$$

$$
y_R=[y_P+m(x_R-x_P)]\bmod p=[y_Q+m(x_R-x_Q)]\bmod p
$$

$m$为$PQ$直线的斜率，有计算公式：
$$
\begin{cases}m=(y_P-y_Q)(x_P-x_Q)^{-1}\bmod p(P\not=Q)\m=(3x_P^2+a)(2y_P)^{-1}\bmod p(P=Q)\end{cases}
$$

椭圆曲线阶

椭圆曲线群的点的个数称为椭圆曲线群的阶，如果$p$较大的话，计算群的阶会比较复杂，可以使用Schoof’s algorithm算法计算群的阶。在sage里可以使用E.order()计算阶。

标量乘法

在$F_p$上仍然可以使用翻倍累加算法计算标量乘法。这里我们举一个例子：

1
2
3
4
5
6
7
p = 97
A = 2
B = 3
E = EllipticCurve(GF(p),[A,B])
P=E(3,6)
print(0*P,1*P,2*P,3*P,4*P,5*P,6*P,7*P,8*P,9*P)
#(0 : 1 : 0) (3 : 6 : 1) (80 : 10 : 1) (80 : 87 : 1) (3 : 91 : 1) (0 : 1 : 0) (3 : 6 : 1) (80 : 10 : 1) (80 : 87 : 1) (3 : 91 : 1)

会发现乘积只出现了五种不同的答案，而且循环出现，也就是：
$$
kP=(k\bmod 5)P
$$
这体现出加法上的封闭性，有$nP+mP=(n+m)P$，$P$的乘积集合是由椭圆曲线群的一个循环子群，这里的$P$就是发生器或基点。

循环子群阶

之前已经知道：阶是椭圆曲线群的点的个数。在循环子群中，认为：循环子群的阶是满足$nP=0$的最小正整数$n$。上面的例子中，循环子群的阶就是$5$。

根据拉格朗日定理（对于一个有限群$G$，对于$G$的任意一个子群$H$，$H$的阶一定能整除$G$的阶。）可以求解$P$子群的阶：

1.先得到椭圆曲线的阶$N$；（Schoof’s algorithm或者E.order()）

2.得到$N$的所有因子；

3.对因子进行遍历计算$nP$，找到满足满足$nP=0$的最小正整数$n$，就是循环子群的阶。

如果椭圆曲线域$F_p$的$p$是质数，由于$p$的因子只有$1$和$p$，当$n=1$时，子群只包含无限远点；所以，此时的所有循环子群的阶都是$p$。

寻找基点

根据拉格朗日定理：$h=\frac Nn$是个整数，我们把$h$叫做子群的协因子。

对于椭圆曲线的每个点，都有$NP=n(hP)=0$，当$n$是一个素数，点$G=hP$可以得到阶为$n$的子群。

所以，为了找到合适的基点，首先计算椭圆曲线阶$N$，找到一个子群质数阶$n$，计算协因子$h$，选择一个随机点$P$，计算$G=hP$，如果$G\not=0$，就找到了阶为$n$而且协因子为$h$的子群。

椭圆曲线离散对数问题

在有限域$F_p$上的离散对数问题（DLP）为如下形式：

Alice公布了两个数字$g,h$，秘密是同余的指数$x$：
$$
h\equiv g^x(\bmod p)
$$
相应的，定义在离散有限域的椭圆曲线离散对数问题（ECDLP），如果我们已知$k,P$求$Q=kP$是比较容易的，但是如果知道$PQ$求$k$是很困难的。

在椭圆曲线密码学中，私钥是在${1,…,n-1}$选的随机正整数$d$，$n$为子群的阶；公钥是是点$H=dG$，$G$是子群的基准点。

为了求解$d$，就需要解决离散对数问题。

常用的基于椭圆曲线密码学的公钥算法是ECDH（用于加密）和ECDSA（用于数字签名）。

ECDH密钥交换

将椭圆曲线应用到密码学，最常见的应用是Diffie-hellman密钥交换。

交换过程

公共参数创建：可信方选择并发送一个大素数$p$，一条椭圆曲线$E(F_p)$和椭圆曲线上一点$P$。

私人计算：

1.Alice选择一个秘密整数$n_A$，计算$Q_A=n_AP$。

2.Bob选择一个秘密整数$n_B$，计算$Q_B=n_BP$。

数值交换：

Alice把$Q_A$发送给Bob，Bob把$Q_B$发送给Alice。

私有秘密值双方可计算：
$$
secret=n_AQ_B=n_A(n_BP)=n_B(n_AP)=n_BQ_A
$$
定义：设$E(F_p)$是有限域上的椭圆曲线，设$P\in E(F_p)$，椭圆曲线Diffie-hellman问题就是提供已知的$n_1P,n_2P$去计算$n_1n_2P$的值。

ElGamal公钥密码系统

Alice和Bob选择一个特定的素数$p$，椭圆曲线$E$和点$P\in E(F_p)$。

Alice选择一个秘密乘数$n_A$，计算并发布$Q_A=n_AP$作为公钥。Bob明文为$M\in E(F_p)$，他选择一个整数$k$作为临时密钥，计算：
$$
C_1=kP
$$

$$
C_2=M+kQ_A
$$

Bob将$C_1,C_2$两个点发送给Alice，Alice计算$C_2-n_AC_1=M$来恢复出明文。

ECDSA签名

Bob选择随机整数$d$，$d\in[1,n-1]$，计算$Q=dG$，得到公钥$Q$，私钥$d$。

进行数字签名，选择随机整数$k\in[1,n-1]$，计算解点$P=(x,y)=kG$，和$r=x\bmod n$，计算$t=k^{-1}\bmod n$，以及$e=Hash(m)$，计算：
$$
s=k^{-1}(e+dr)\bmod n
$$
对消息的签名就是$(r,s)$对。

对弱曲线的攻击

Pohlig-Hellman攻击

Pohlig-hellman只能用于求解光滑阶群，指阶可以分解成小的素因子乘积。

该算法由由Pohlig和Hellman发明，这是一种为解决离散对数问题而提出的攻击方法，它的主要思想是对阶数进行分解，这样就把对应的离散对数问题转移到了每个因子条件下对应的离散对数，这样就可以利用中国剩余定理进行求解。

假设我们要求解的式子为$Q=kP$，$P$为选择的一个基点，$n$为要求解的私钥。

先求解椭圆曲线的阶$k$，将$k$进行分解：
$$
n=p_1^{e_1} p_2^{e_2}…p_r^{e_r}
$$
分别将这些因子拿出来，设$i$从$1$到$r$计算：
$$
k_i=k \bmod p_i^{e_i}
$$
就得到了$r$个式子：
$$
\begin{cases}k_1\equiv k (\bmod p_1^{e_1})\k_2\equiv k (\bmod p_2^{e_2})\…\k_r\equiv k (\bmod p_r^{e_r})\end{cases}
$$
现在我们需要得到这些$k_1,…,k_r$，可以利用多项式的思想，将$k_i$设为$e$项的多项式，通过计算$z_j$来得到$k_i$的值：
$$
k_i=z_0+z_1p_i+z_2p_i^2+…+z_{e-1}p_i^{e-1}
$$
通过计算可以得到$z_0$，然后代入循环计算可以得到所有的$z_i$，就可以使用中国剩余定理进行求解了：

1
2
3
4
5
6
7
8
9
10
11
12
E=EllipticCurve(GF(1256438680873352167711863680253958927079458741172412327087203),[1110668700631625869694878253913765190838859401253774210906747,1046475761463312903815812602516218762528328411160289227233273 ])
P=E(688198189464934601412152156581728476817235971565960983401549 ,1085422260166303612986957608547578937042081201541180575045892 )
Q=E(1012738765669127668857662399104589210747323857774608742862915 , 194783268319937974400068498276761709425155795796852820831727 )
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
dlogs = []
for fac in primes:
        t = int(int(P.order()) // int(fac))
        dlog = discrete_log(t*Q,t*P,operation="+")
        dlogs += [dlog]
        print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
print(crt(dlogs,primes))

SmartAttack

当$P$的阶和$p$相等时，可以使用SmartAttack这种方法计算离散对数，先学习一些额外知识。

Hensel引理

可以使用Hensel引理实现：对于多项式$f(x)\in Z[x]$有$x$满足$f(x)\equiv 0(\bmod p^s)$，能找到唯一的$x’$使得$x’\equiv x(\bmod p^s)$和$f(x’)\equiv 0(\bmod p^{s+1})$。也就是说，给一个$f\bmod p^s$的解，能计算$f\bmod p^{s+1}$的唯一解。

对于$f(x)\in Z[X]$，让$x$是$f\bmod p^s$的一个根，且导数$f’(x)$在模$p$下可逆（$f’(x)\not\equiv0(\bmod p)$，不受椭圆曲线奇异点影响），使得存在$uf’(x)\equiv 1(\bmod p)$，让$x’$满足：
$$
x’=x-uf’(x)
$$
利用Hensel引理，可以将元素从$F_p$域提升到下面的P-adic数域。

P-adic数

P-adic数（p进数）可以用一个无限级数表示：
$$
c_{-n}p^{-n}+…+c_0+c_1p+…+c_mp_m+…
$$
P-adic数域用$Q_p$表示，没有负数幂的数为P-adic整数（对应的域也就是$Z_p$），我们可以在P-adic数域上定义椭圆曲线，利用上面的方法提升到$Q_p$，相当于简化了计算：

P-adic椭圆对数（记为$𝜓_𝑝$）：对一个点$S\in E_1(Q_p)$，通过点坐标展开成P-adic数形式，利用无限级数展开进行运算：
$$
𝜓_𝑝(S)=-\frac{x(S)}{y(S)}
$$
这里的思想是通过减少寻找$k$使得$Q=kP$的困难度来更方便的计算$k$，原理太复杂先不讨论，了解一下就行。

总结

对于这种阶数模数相等的曲线，首先是将这些点提升到$E(Q_p)$上得到$P’,Q’$，计算时需要使得$P,P’$的$x$坐标相等，用Hensel引理通过固定$x$的曲线方程计算$y$，之后利P-adic椭圆对数计算$k$：
$$
k=\frac{𝜓_𝑝(pQ’)}{𝜓_𝑝(pP’)}
$$
下面是根据原理实现的SmartAttack代码：

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
def SmartAttack(P,Q,p):
    E = P.curve()
    
    # 创建一个拓展p-adic域,构造一个拓展p-adic椭圆曲线
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
    
    # 对输入点P,Q进行提升
    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break
    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break
    
    # 进行点倍乘操作并提取结果的坐标
    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp
    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()
    
    # 计算比值k
    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

赛题

[第五空间 2021]ecc

这是一道基础的ECC题目：

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
print 'Try to solve the 3 ECC'

from secret import flag
from Crypto.Util.number import *
assert(flag[:5]=='flag{')
flag = flag[5:-1]
num1 = bytes_to_long(flag[:7])
num2 = bytes_to_long(flag[7:14])
num3 = bytes_to_long(flag[14:])

def ECC1(num):
	p = 146808027458411567
	A = 46056180
	B = 2316783294673
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

def ECC2(num):
	p = 1256438680873352167711863680253958927079458741172412327087203
	#import random
	#A = random.randrange(389718923781273978681723687163812)
	#B = random.randrange(816378675675716537126387613131232121431231)
	A = 377999945830334462584412960368612
	B = 604811648267717218711247799143415167229480
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
	factors, exponents = zip(*factor(E.order()))
	primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
	print primes
	dlogs = []
	for fac in primes:
		t = int(int(P.order()) / int(fac))
		dlog = discrete_log(t*Q,t*P,operation="+")
		dlogs += [dlog]
		print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
	print num
	print crt(dlogs,primes)

def ECC3(num):
	p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
	A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
	B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

ECC1(num1)
print '=============='
ECC2(num2)
print '=============='
ECC3(num3)


Try to solve the 3 ECC
Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
P: (119851377153561800 : 50725039619018388 : 1)
Q: (22306318711744209 : 111808951703508717 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)
==============
Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
P: (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 : 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 : 1)
Q: (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 : 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 : 1)

ECC1（参数较小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ECC1(num):
	p = 146808027458411567
	A = 46056180
	B = 2316783294673
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
    
Elliptic Curve defined by y^2 = x^3 + 46056180*x + 2316783294673 over Finite Field of size 146808027458411567
P: (119851377153561800 : 50725039619018388 : 1)
Q: (22306318711744209 : 111808951703508717 : 1)

已知了PQ，求num，可以用sage里的discrete_log来计算：

1
2
3
4
5
6
7
8
p = 146808027458411567
A = 46056180
B = 2316783294673
E = EllipticCurve(GF(p),[A,B])
P=E(119851377153561800,50725039619018388)
Q=E(22306318711744209,111808951703508717)
print(P.discrete_log(Q))
#13566003730592612

ECC2（中国剩余定理求k）

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
def ECC2(num):
	p = 1256438680873352167711863680253958927079458741172412327087203
	#import random
	#A = random.randrange(389718923781273978681723687163812)
	#B = random.randrange(816378675675716537126387613131232121431231)
	A = 377999945830334462584412960368612
	B = 604811648267717218711247799143415167229480
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q
	factors, exponents = zip(*factor(E.order()))
	primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
	print primes
	dlogs = []
	for fac in primes:
		t = int(int(P.order()) / int(fac))
		dlog = discrete_log(t*Q,t*P,operation="+")
		dlogs += [dlog]
		print("factor: "+str(fac)+", Discrete Log: "+str(dlog)) #calculates discrete logarithm for each prime order
	print num
	print crt(dlogs,primes)
	
Elliptic Curve defined by y^2 = x^3 + 377999945830334462584412960368612*x + 604811648267717218711247799143415167229480 over Finite Field of size 1256438680873352167711863680253958927079458741172412327087203
P: (550637390822762334900354060650869238926454800955557622817950 : 700751312208881169841494663466728684704743091638451132521079 : 1)
Q: (1152079922659509908913443110457333432642379532625238229329830 : 819973744403969324837069647827669815566569448190043645544592 : 1)

当然，这个题目非常好心的把CRT求解的代码直接给我们了，我们只需要构建好PQ和椭圆曲线即可：

1
2
3
4
5
6
7
8
9
10
11
12
E=EllipticCurve(GF(1256438680873352167711863680253958927079458741172412327087203),[377999945830334462584412960368612,604811648267717218711247799143415167229480 ])
P=E(550637390822762334900354060650869238926454800955557622817950 ,700751312208881169841494663466728684704743091638451132521079 )
Q=E(1152079922659509908913443110457333432642379532625238229329830 , 819973744403969324837069647827669815566569448190043645544592 )
factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-1]
dlogs = []
for fac in primes:
        t = int(int(P.order()) // int(fac))
        dlog = discrete_log(t*Q,t*P,operation="+")
        dlogs += [dlog]
        print("factor: "+str(fac)+", Discrete Log: "+str(dlog))
print(crt(dlogs,primes))

ECC3（SmartAttack）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ECC3(num):
	p = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
	A = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
	B = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
	E = EllipticCurve(GF(p),[A,B])
	P = E.random_point() 
	Q = num*P
	print E
	print 'P:',P
	print 'Q:',Q

Elliptic Curve defined by y^2 = x^3 + 490963434153515882934487973185142842357175523008183292296815140698999054658777820556076794490414610737654365807063916602037816955706321036900113929329671*x + 7668542654793784988436499086739239442915170287346121645884096222948338279165302213440060079141960679678526016348025029558335977042712382611197995002316466 over Finite Field of size 11093300438765357787693823122068501933326829181518693650897090781749379503427651954028543076247583697669597230934286751428880673539155279232304301123931419
P: (10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 : 8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 : 1)
Q: (964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 : 5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 : 1)

P阶数和p相等使用SmartAttack，直接上脚本：

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
p =0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A =0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B =0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E = EllipticCurve(GF(p),[A,B])
P =E(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610)
Q =E(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537)

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])
    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break
    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break
    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp
    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()
    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

num = SmartAttack(P, Q, p)
print(num)

[HGAME 2022 week4]ECC

一道基于ECC的小学数学题：

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
from Crypto.Util.number import getPrime
from libnum import s2n
from secret import flag

p = getPrime(256)
a = getPrime(256)
b = getPrime(256)
E = EllipticCurve(GF(p),[a,b])
m = E.random_point()
G = E.random_point()
k = getPrime(256)
K = k * G
r = getPrime(256)
c1 = m + r * K
c2 = r * G
cipher_left = s2n(flag[:len(flag)//2]) * m[0]
cipher_right = s2n(flag[len(flag)//2:]) * m[1]

print(f"p = {p}")
print(f"a = {a}")
print(f"b = {b}")
print(f"k = {k}")
print(f"E = {E}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"cipher_left = {cipher_left}")
print(f"cipher_right = {cipher_right}")

p = 74997021559434065975272431626618720725838473091721936616560359000648651891507
a = 61739043730332859978236469007948666997510544212362386629062032094925353519657
b = 87821782818477817609882526316479721490919815013668096771992360002467657827319
k = 93653874272176107584459982058527081604083871182797816204772644509623271061231
E = Elliptic Curve defined by y^2 = x^3 + 61739043730332859978236469007948666997510544212362386629062032094925353519657*x + 12824761259043751634610094689861000765081341921946160155432001001819005935812 over Finite Field of size 74997021559434065975272431626618720725838473091721936616560359000648651891507
c1 = (14455613666211899576018835165132438102011988264607146511938249744871964946084 : 25506582570581289714612640493258299813803157561796247330693768146763035791942 : 1)
c2 = (37554871162619456709183509122673929636457622251880199235054734523782483869931 : 71392055540616736539267960989304287083629288530398474590782366384873814477806 : 1)
cipher_left = 68208062402162616009217039034331142786282678107650228761709584478779998734710
cipher_right = 27453988545002384546706933590432585006240439443312571008791835203660152890619

根据已知信息，求m，找到有关m的表达式：
$$
c_1 = m + rK\ \ \ \ c_2 = rG
$$
而又有$K = k G$，得到：
$$
m=c_1-kc_2
$$
用sage顺着题目解下去就得到flag了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from Crypto.Util.number import *

p = 74997021559434065975272431626618720725838473091721936616560359000648651891507
A = 61739043730332859978236469007948666997510544212362386629062032094925353519657
B = 87821782818477817609882526316479721490919815013668096771992360002467657827319
E = EllipticCurve(GF(p),[A,B])
c1=E(14455613666211899576018835165132438102011988264607146511938249744871964946084,25506582570581289714612640493258299813803157561796247330693768146763035791942)
c2=E(37554871162619456709183509122673929636457622251880199235054734523782483869931,71392055540616736539267960989304287083629288530398474590782366384873814477806)
k=93653874272176107584459982058527081604083871182797816204772644509623271061231

cipher_left = 68208062402162616009217039034331142786282678107650228761709584478779998734710
cipher_right = 27453988545002384546706933590432585006240439443312571008791835203660152890619

m=c1-k*c2
f1=cipher_left//m[0]
f2=cipher_right//m[1]
print(long_to_bytes(int(f1)).decode()+long_to_bytes(int(f2)).decode())

[巅峰极客 2022]point-power

Do you know Powerpoint?How about point-power?

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
from Crypto.Util.number import *
from gmpy2 import *
from random import *
from secrets import flag

assert len(flag)==42
p=getPrime(600)
a=bytes_to_long(flag)
b=randrange(2,p-1)
E=EllipticCurve(GF(p),[a,b])
G=E.random_element()

x1,y1,_=G
G=2*G
x2,y2,_=G

print(f"p = {p}")
print(f"b = {b}")
print(f"x1 = {x1}")
print(f"x2 = {x2}")
'''          
p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
'''

这题并没有给a，需要求a，所以没有基定义不了圆锥曲线，但是题目还进行了一次点加法：

1
2
3
x1,y1,_=G
G=2*G
x2,y2,_=G

给了加前和加后的x坐标，对于圆锥曲线的点加法，有：

如果$P≠Q:\ \ λ=\frac{y_2-y_1}{x_2-x_1}$
如果$P=Q:\ \ λ=\frac{3x_1^2+a}{2y_1}$

$x_3=λ^2−x_1−x_2,y_3=λ(x_1−x_3)−y_1$
$P+Q=(x_3,y_3)$

本题的PQ都是G，所以相等，有：
$$
\lambda=\frac{3x_1^2+a}{2y_1}①
$$

$$
x_2=λ^2−x_1−x_1=\lambda-2x_1②
$$

根据椭圆曲线定义，有：
$$
y_1^2=x_1^3+ax_1+b③
$$
把①③两个式子都代入②式，消去λ和y，得到：
$$
x_2=\frac{(3x_1^2+a)^2}{4(x_1^3+ax_1+b)}-2x_1
$$
在模p下构造函数求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from Crypto.Util.number import *

p = 3660057339895840489386133099442699911046732928957592389841707990239494988668972633881890332850396642253648817739844121432749159024098337289268574006090698602263783482687565322890623
b = 1515231655397326550194746635613443276271228200149130229724363232017068662367771757907474495021697632810542820366098372870766155947779533427141016826904160784021630942035315049381147
x1 = 2157670468952062330453195482606118809236127827872293893648601570707609637499023981195730090033076249237356704253400517059411180554022652893726903447990650895219926989469443306189740
x2 = 1991876990606943816638852425122739062927245775025232944491452039354255349384430261036766896859410449488871048192397922549895939187691682643754284061389348874990018070631239671589727
p.<a>=PolynomialRing(Zmod(p))
res=4*(x1^3+a*x1+b)
f=(3*x1^2+a)^2-2*x1*res-res*x2
f.roots()
list=[(918875439627055594259552478508551728381826199399685938622511660790511287097297184191298481453657480331998130281110691444641445094194011219176724349745237973925436007792522611119050,
  1),
 (56006392793430010663016642098239513811260175999551893260401436587175373756825079518464264729364083325,
  1)]
for i in list:
    print(long_to_bytes(int(i[0])))