ECC

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 3.1k 阅读时长 ≈ 11 分钟

记录笔者学习椭圆曲线加密算法

ECC(EllipseCurve Cryptography)全称椭圆曲线加密。是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域有

  1. $GF(p)$，以素数为模的整数域
  2. $GF(2^m)$，特征为2的伽罗华域

什么是椭圆曲线

首先了解有限域上的椭圆曲线

有限域上的椭圆曲线是指在椭圆曲线的定义式
$$
y^2 + axy + by = x^3 +cx^2 +dx + e
$$
中所有的系数都是在某个有限域$GF(p)$中的元素，其中p是一个大素数。

常用于加密的方程是Weierstrass方程
$$
y^2 = x^3+ax+b
$$
其中，$ \Delta = − 16 (4a^3 + 27 b) ≠ 0$,用来保证曲线是光滑的，即曲线上的所有点都没有两个或者两个以上不同的切线

椭圆曲线上的加法

设$P=(x_1,y_1),Q=(x_2,y_2)\in E_p(a,b)$，设$P+Q=(x_3,y_3)$

则
$$
x_3 \equiv k^2 - x_1 - x_2 \mod p
$$

$$
y_3 \equiv k(x_1-x_3) - y_1 \mod p
$$

k的计算如下
$$
k = \frac{y_2-y_1}{x_2-x_1} \mod p\quad \quad P\ne Q
$$

$$
k = \frac{3x_1^2 + a}{2y_1} \mod p \quad \quad P = Q
$$

将P点关于x轴对称的点定义为-P，$P = (x,y)$,则$-P = (x,-y \mod p)$

几种常见的曲线参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#NIST P-256（Secp256r1）
#p = 2^224(2^32 − 1) + 2^192 + 2^96 − 1
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291

#Secp256k1（比特币使用）
#p = 2^256 − 2^32 − 2^9 − 2^8 − 2^7 − 2^6 − 2^4 − 1 = 2^256 – 2^32 – 977 
p = 115792089237316195423570985008687907853269984665640564039457584007908834671663
a = 0
b = 7

#NIST P-384
#p = 2^384 – 2^128 – 2^96 + 2^32 – 1
p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
a = -3
b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575

#NIST P-521
p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
a = -3
b = 1093849038073734274511112390766805569936207598951683748994586394495953116150735016013708737573759623248592132296706313309438452531591012912142327488478985984

ECC上的EIGamal

假设Bob要把消息加密后传给Alice

密钥生成

Alice先选择一条椭圆曲线$E_p(a,b)$，然后选择曲线上的一个生成元G，假设其阶为$n$，之后再选择一个正整数$n_a$作为密钥，计算$P_a = n_aG$

其中，公开$E_p(a,b)$,$p$,$G$。公钥为$P_a$，私钥为$n_a$

加密

Bob向Alice发送消息m，要先对m编码为曲线上的点M。加密步骤如下

  1. 使用Alice的公钥，$E_p(a,b)$,$p$,$P_a$,$G$
  2. 在$(1,p-1)$中选取随机数k
  3. 计算点$C_1 = kG$
  4. 计算点$K= kP_a$，如果是无穷远点，那么重复2,3步
  5. 计算点$C_2 = M + K = M + kP_a$
  6. 将$(C_1,C_2)$发给Alice

解密

Alice在收到Bob发送的$(C_1,C_2)$之后，根据以下步骤获取消息

  1. 计算$n_aC_1 = n_akG = kP_a$
  2. $M = C_2 - kP_a$

sagemath实现

常用函数

  1. E = EllipticCurve(GF(p),[a,b]) :定义曲线
  2. E.random_point():在椭圆曲线E上随机取一点
  3. E.set_order():设置椭圆曲线的阶
  4. E.point((x,y)):创建一个椭圆曲线上的点对象，该点对象的坐标为(x,y)
  5. discrete_log(K,G,operation='+'):求解$K = kG$，自动选取BSGS算法或Pohlig-Hellman算法
  6. E.order()：计算椭圆曲线的阶。
  7. discrete_log_rhp(K,G,operation='+'):用Pollard rho算法求解私钥
  8. discrete_log_lambda(K,G,bound,operation='+'):用Pollard Lambda算法求解私钥，能够确定所求值在某一小范围时效率较高

加密示例

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
import random 
"""
这里使用NIST P-256
"""
"""
已知Alice私钥为62082900092842610053287908404599315101005270141167316143733368271632829538584 
公钥为(107641879144396245698735275506803265840358797864132319680190373847271858164980,47355535520015758232672121387250557693006806715731251672455727730722279072073)
"""
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p),[a,b])
M = E(80764032034929976879602863302323059647882062252124869895215418422992624743795,4964654783828069942602279691168356721024126126864424301508238062949726916347)

G = E.gen(0)                    # 获取生成元
n = E.order()
Pa = E(107641879144396245698735275506803265840358797864132319680190373847271858164980,47355535520015758232672121387250557693006806715731251672455727730722279072073)

k = random.randint(1,p-1)
C1 = k*G
K = k*Pa
C2 = M + K

print(C1)
print(C2)
"""
C1 = E(57728498705822675870223033275964016497503135785449483276975549209363755426632,100207880026633678257826613394394896220264123242435071203173012352108326553272)
C2 = E(37815699639437978342774585294689161021328418818072948538182050516188487137302,98438576994494511703874400677395107315311376509871600325640423991402748907811)
na = 62082900092842610053287908404599315101005270141167316143733368271632829538584
"""

解密实例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
a = 115792089210356248762697446949407573530086143415290314195533631308867097853948
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
E = EllipticCurve(GF(p),[a,b])

C1 = E(57728498705822675870223033275964016497503135785449483276975549209363755426632,100207880026633678257826613394394896220264123242435071203173012352108326553272)
C2 = E(37815699639437978342774585294689161021328418818072948538182050516188487137302,98438576994494511703874400677395107315311376509871600325640423991402748907811)
na = 62082900092842610053287908404599315101005270141167316143733368271632829538584

M = C2 - na*C1
print(M)
"""
(80764032034929976879602863302323059647882062252124869895215418422992624743795 : 4964654783828069942602279691168356721024126126864424301508238062949726916347 : 1)
"""

用Crypto库生成ECC密钥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.PublicKey import ECC

#生成ECC密钥
key = ECC.generate(curve='NIST P-256') #使用椭圆曲线NIST P-256

#输出密钥（包括私钥k，基点G）
print(key)

#公钥（point_x，point_y是基点G的坐标）
print(key.public_key())

#椭圆曲线
print(key.curve)

#私钥k
print(key.d)

#导出为pem密钥文件
print(key.export_key(format='PEM'))

#导入密钥文件
key = ECC.import_key(f.read())

例题

题目给的不是生成元

处理方法是用阶来当作生成元

例题是广东强网杯 2021 团队组——DLP

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

assert(flag[:5] == b"flag{" and flag[-1:] == b"}")

flag = flag[5:-1]

d1 = bytes_to_long(flag[:len(flag)//2])
d2 = bytes_to_long(flag[len(flag)//2:])

N1 = 27544759469094453505371358768052861416297003882211878831861112512567899543941
A1 = 4208715803791813173086894172778966025419787767340027559010619240548499823390
B1 = 11846440123913040489420209031751160809904311707943252241515965930654415480691
P1x = 479750084250968709343887919962436485997147832319843477221083468203689368148
P1y = 15452861783577624143044213767588871736433639621547613407582902947429567101675

P1 = (P1x,P1y)
E1 = EllipticCurve(Zmod(N1), [0, 0, 0, A1, B1])
P1 = E1(P1)
Q1 = d1 * P1

N2 = 6471339743593595797696002766822660599108196938080465998531085409467
A2 = 3199218821393204771660095172457569312269694438403110131957204042314
B2 = 762889472027318213897694878260359911054972690369935049954326689904
P2x = 2557373437970770011124755960432555084678930336188254243278984381842
P2y = 4442763096366920105760404533052204677305995021662082361185473321644

P2 = (P2x,P2y)
E2 = EllipticCurve(Zmod(N2), [0, 0, 0, A2, B2])
P2 = E2(P2)
Q2 = d2 * P2

print(Q1)
print(Q2)
'''
(14736970297054248276364510675718632926198693034158620007675880103924809577805 : 3447209262654420855289144268810543114387612255490962015335062266658385100211 : 1)
(4834036103940457959470026215023033401071737087504569417466448644066 : 5511016821581393405975510064568222454318072088628361854656950557373 : 1)
'''

首先对于$\mod n$，且$n=pq$的椭圆曲线，可以拆成$\mod p$和$\mod q$，分别求离散对数，再用中国剩余定理。

不过需要注意的是，这题选取的P都不是生成元，所以用中国剩余定理组合起来的时候，需要用$P$的阶，而不是椭圆曲线的阶。

exp:

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
from Crypto.Util.number import *

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)

N1 = 27544759469094453505371358768052861416297003882211878831861112512567899543941
A1 = 4208715803791813173086894172778966025419787767340027559010619240548499823390
B1 = 11846440123913040489420209031751160809904311707943252241515965930654415480691
P1x = 479750084250968709343887919962436485997147832319843477221083468203689368148
P1y = 15452861783577624143044213767588871736433639621547613407582902947429567101675

Q1x = 14736970297054248276364510675718632926198693034158620007675880103924809577805 
Q1y = 3447209262654420855289144268810543114387612255490962015335062266658385100211 

p1 = 92636417177965240871815246762704348071
q1 = N1 // p1

P1 = (P1x, P1y)
Q1 = (Q1x, Q1y)
E1p = EllipticCurve(Zmod(p1), [0, 0, 0, A1, B1])
n1p = E1p.order()
P1p = E1p(P1)
Q1p = E1p(Q1)

# Pohlig Hellman
d1p = P1p.discrete_log(Q1p)

E1q = EllipticCurve(Zmod(q1), [0, 0, 0, A1, B1])
n1q = E1q.order()
P1q = E1q(P1)
Q1q = E1q(Q1)

# Smart
d1q = SmartAttack(P1q, Q1q, q1)

d1 = crt([d1p, d1q], [P1p.order(), P1q.order()])
print("d1=",d1)

N2 = 6471339743593595797696002766822660599108196938080465998531085409467
A2 = 3199218821393204771660095172457569312269694438403110131957204042314
B2 = 762889472027318213897694878260359911054972690369935049954326689904
P2x = 2557373437970770011124755960432555084678930336188254243278984381842
P2y = 4442763096366920105760404533052204677305995021662082361185473321644
Q2x = 4834036103940457959470026215023033401071737087504569417466448644066 
Q2y = 5511016821581393405975510064568222454318072088628361854656950557373 

p2 = 69857405335111415530599248077
q2 = 92636417177965240871815246762704348071

P2 = (P2x,P2y)
Q2 = (Q2x,Q2y)
E2p = EllipticCurve(Zmod(p2), [0, 0, 0, A2, B2])
n2p = E2p.order()
P2p = E2p(P2)
Q2p = E2p(Q2)

# Pohlig Hellman
d2p = P2p.discrete_log(Q2p)

E2q = EllipticCurve(Zmod(q2), [0, 0, 0, A2, B2])
n2q = E2q.order()
P2q = E2q(P2)
Q2q = E2q(Q2)

# Pohlig Hellman
d2q = P2q.discrete_log(Q2q)

d2 = crt([d2p, d2q], [P2p.order(), P2q.order()])
print("d2=",d2)

flag1 = long_to_bytes(int(d1))
flag2 = long_to_bytes(int(d2))
print(flag1+flag2)

[第五空间 2021]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
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)

part1

第一部分就是基础解$Q = kP$这个式子的k

part2

第二部分是利用中国剩余定理解离散对数问题，代码已经在附件里面了，需要把/改成//，不然跑不出来

part3

第三部分考察模数p和曲线的阶相等，用SmartAttack

exp:

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
#sage
from Crypto.Util.number import *
import gmpy2

#part1
p1 = 146808027458411567
A1 = 46056180
B1 = 2316783294673
E1 = EllipticCurve(GF(p1),[A1,B1])
P1 = E1(119851377153561800,50725039619018388)
Q1 = E1(22306318711744209,111808951703508717)

m1 = P1.discrete_log(Q1)        # flag1 = discrete_log(Q1,P1,operation='+')
flag1 = long_to_bytes(int(m1))
print(flag1)

#part2
p2 = 1256438680873352167711863680253958927079458741172412327087203
A2 = 377999945830334462584412960368612
B2 = 604811648267717218711247799143415167229480
E2 = EllipticCurve(GF(p2),[A2,B2])
P2 = E2(550637390822762334900354060650869238926454800955557622817950,700751312208881169841494663466728684704743091638451132521079)
Q2 = E2(1152079922659509908913443110457333432642379532625238229329830,819973744403969324837069647827669815566569448190043645544592)

def solve(P,Q,E):
    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
    m = CRT_list(dlogs,primes)
    return m

m2 = solve(P2,Q2,E2)
flag2 = long_to_bytes(int(m2))
print(flag2)

#part3
p3 = 0xd3ceec4c84af8fa5f3e9af91e00cabacaaaecec3da619400e29a25abececfdc9bd678e2708a58acb1bd15370acc39c596807dab6229dca11fd3a217510258d1b
A3 = 0x95fc77eb3119991a0022168c83eee7178e6c3eeaf75e0fdf1853b8ef4cb97a9058c271ee193b8b27938a07052f918c35eccb027b0b168b4e2566b247b91dc07
B3 = 0x926b0e42376d112ca971569a8d3b3eda12172dfb4929aea13da7f10fb81f3b96bf1e28b4a396a1fcf38d80b463582e45d06a548e0dc0d567fc668bd119c346b2
E3 = EllipticCurve(GF(p3),[A3,B3])
P3 = E3(10121571443191913072732572831490534620810835306892634555532657696255506898960536955568544782337611042739846570602400973952350443413585203452769205144937861 ,8425218582467077730409837945083571362745388328043930511865174847436798990397124804357982565055918658197831123970115905304092351218676660067914209199149610 )
Q3 = E3(964864009142237137341389653756165935542611153576641370639729304570649749004810980672415306977194223081235401355646820597987366171212332294914445469010927 ,5162185780511783278449342529269970453734248460302908455520831950343371147566682530583160574217543701164101226640565768860451999819324219344705421407572537 )

# print(p3 == E3.order())
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)

m3 = SmartAttack(P3,Q3,p3)
flag3 = long_to_bytes(int(m3))
print(flag3)

flag = b'flag{' + flag1 + flag2 + flag3 + b'}'
print(flag)

[领航杯江苏省赛 2021]ECC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import bytes_to_long
from secret import flag

p = 64464091191308356774703439660771627086045800299627641179047457478059588557461
a = 31926335967105564755113987930261069322507794703287741857397622356704769886356
b = 34835808070187351680507689900273321615070127680320357724483770400791707112940
Gx = 2053202552422630348010474635096983783565667661786369125783579647572276572403
Gy = 51320753844844801021362329076409450910659564359017581255542897537756778371539

assert flag[:5] == "CnHongKe{"
assert flag[-1] == "}"

k = bytes_to_long(flag[9:-1])
assert k < 32000000000000000000000000000

Zp = Zmod(P)
EC = EllipticCurve(Zp, [a, b])
G = EC(Gx, Gy)
K = k * G
print K

# (31981799071949968743482831587417174146463993877255771340814476669214408840460 : 15144025062588325012239455117890516531350002058200271280110877844265896081387 : 1)

曲线的阶能分解

用CRT解出一个特解，发现只有$74bit$，而正确的$k$不超过95bit

爆破一下即可

exp:

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
from Crypto.Util.number import *
from tqdm import *

p = 64464091191308356774703439660771627086045800299627641179047457478059588557461
a = 31926335967105564755113987930261069322507794703287741857397622356704769886356
b = 34835808070187351680507689900273321615070127680320357724483770400791707112940
Gx = 2053202552422630348010474635096983783565667661786369125783579647572276572403
Gy = 51320753844844801021362329076409450910659564359017581255542897537756778371539

Zp = Zmod(p)
EC = EllipticCurve(Zp, [a, b])
G = EC(Gx, Gy)

K = EC(31981799071949968743482831587417174146463993877255771340814476669214408840460,15144025062588325012239455117890516531350002058200271280110877844265896081387)

def solve(P,Q,E):
    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
    m = CRT_list(dlogs,primes)
    n = prod(primes)
    return m,n

d,n = solve(G,K,EC)
print(d)
print(int(d).bit_length())

for k in trange(2^21,0,-1):
    flag = d + k*n
    P = flag * G
    if P == K:
        print(b"NSSCTF{" + long_to_bytes(flag) + b"}")
        break

[HGAME 2023 week4]ECRSA

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
#sage
from sage.all import *
from sage.all_cmdline import *
from Crypto.Util.number import *
from secret import flag

Nbits = 512
x = bytes_to_long(flag)
f = open('./output', 'w')

def gen_pubkey(Nbits):
    p = getPrime(Nbits // 2)
    q = getPrime(Nbits // 2)
    n = p*q
    while True:
        a = getRandomInteger(Nbits // 2)
        b = getRandomInteger(Nbits // 2)
        if gcd(4*a**3 + 27*b**2, n) == 1:
            break
    E = EllipticCurve(Zmod(n), [a, b])
    e = getPrime(64)
    f.write(f"p={p}\nq={q}\n")
    return n, E, e

n, E, e = gen_pubkey(Nbits)
pt = E.lift_x(Integer(x))
ct = pt * e
f.write(f"n = {n}\na = {E.a4()}\nb = {E.a6()}\ne = {e}\n")
f.write(f"ciphertext = {long_to_bytes(int(ct.xy()[0]))}\n")

已知$Ct = Pt×e$

给出$Ct$的横坐标$x$

想利用E.lift_x(Integer(x))来求$Ct$的纵坐标$y$，发现算不出来

改用

1
2
3
4
#sage
R.<y> = Zmod(n)[]
f = x^3 + a*x + b - y^2
print(f.roots())

依然跑不出，做个推导

$\because y^2 \equiv x^3 + ax+b \mod n$，$n = p \times q$

$\therefore y$同时满足下列方程组
$$
\left{\begin{matrix}
y^2 \equiv x^3 + ax + b \mod p\
y^2 \equiv x^3 + ax + b \mod q
\end{matrix}\right.
$$
$x$代入计算得
$$
\left{\begin{matrix}
y^2 \equiv y_p^2 \mod p\
y^2 \equiv y_q^2 \mod q
\end{matrix}\right.
$$

对于$y^2 \equiv y_p^2 \mod p$

有$(y+y_p)(y-y_p) \equiv 0 \mod p$

$\therefore y \equiv y_p \mod p$

同理

$y \equiv y_q \mod q$

$\therefore y = y_p + k_1p = y_q + k_2q$

$k_1p = y_q-y_p+k_2q$

同模q得$k_1p \equiv y_q-y_p \mod q$

则$k_1 \equiv (y_q-y_p)p^1 \mod q$

带回$y = y_p + k_1p$得$y = y_p + (y_q-y_p)pp^{-1}$

模n后即可得到y

感觉这个推导有些麻烦了，用中国剩余定理应该就可以了

下面这个推导才重要

$\because Ct \equiv Pt \times e$

已知$e$和$Ct$，需要求$Pt$

记$Pt$生成元的阶为$n$，即$nPt = 0$

$e$与$n$互素时，设$e^{-1}$为$e$对$n$的逆元，即$ee^{-1} \equiv 1 \mod n \longrightarrow ee^{-1} = kn+1$

$\therefore ee^{-1}P =e^{-1}Q = knP+P = P$

$\therefore P = e^{-1}Q$

实际操作过程中发现，$n$不是素数，所以求不出阶$Zmod(n)$的椭圆曲线的阶。

先求模p,q下的阶，再相乘(这个没理解)

在求解$Ct$的纵坐标时，我选择用中国剩余定理

exp:

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
#sage
from Crypto.Util.number import *

p = 115192265954802311941399019598810724669437369433680905425676691661793518967453
q = 109900879774346908739236130854229171067533592200824652124389936543716603840487
n = 12659731371633323406361071735480743870942884407511647144758055911931321534333057725377899993936046070028289182446615763391740446071787318153462098556669611
a = 34573016245861396068378040882622992245754693028152290874131112955018884485688
b = 103282137133820948206682036569671566996381438254897510344289164039717355513886
e = 11415307674045871669
ciphertext = b'f\xb1\xae\x08`\xe8\xeb\x14\x8a\x87\xd6\x18\x82\xaf1q\xe4\x84\xf0\x87\xde\xedF\x99\xe0\xf7\xdcH\x9ai\x04[\x8b\xbbHR\xd6\xa0\xa2B\x0e\xd4\xdbr\xcc\xad\x1e\xa6\xba\xad\xe9L\xde\x94\xa4\xffKP\xcc\x00\x907\xf3\xea'

E = EllipticCurve(Zmod(n), [a, b])

cx = bytes_to_long(ciphertext)
# cx = 5378524437009518839112103581484521575801169404987837300959984214542709038676856596473597472098329866932106236703753833875049687476896652097889558230201322
# cy = E.lift_x(Integer(cx))    太慢了

# R.<cy> = Zmod(n)[]
# f = cx^3 + a*cx + b - cy^2
# print(f.roots())           跑不出

R.<y> = Zmod(p)[]
f = cx^3 + a*cx + b - y^2
mps = f.roots()
# print(mps)

R.<y> = Zmod(q)[]
f = cx^3 + a*cx + b - y^2
mqs = f.roots()
# print(mqs)

cy_all = []
for mpp in mps:
    x = mpp[0]
    for mqq in mqs:
        y = mqq[0]
        cy_all.append(CRT_list([int(x), int(y)], [p, q]))
        
E1 = EllipticCurve(Zmod(p), [a, b])
E2 = EllipticCurve(Zmod(q), [a, b])

order1 = E1.order()
order2 = E2.order()
d = gmpy2.invert(e,order1*order2)
for cy in cy_all:
    Ct = E(cx,cy)
    mx,my = (int(d) * Ct).xy()
    print(long_to_bytes(int(mx)))

脚本来源：HGAME 2023 Week 4 | Lazzaro (lazzzaro.github.io)

思路来源：HGame 2023 Week4 部分Writeup_不做评论的博客-CSDN博客

参考文章：

[ECC - CTF Wiki (ctf-wiki.org)](https://ctf-wiki.org/crypto/asymmetric/discrete-log/ecc/#:~:text=ECC - CTF Wiki ECC 概述,ECC 全称为椭圆曲线加密，EllipseCurve Cryptography，是一种基于椭圆曲线数学的公钥密码。 与传统的基于大质数因子分解困难性的加密方法不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。 它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。)

-------------已经到底啦！-------------