NEKO

ECC-learn

2018/10/18

感觉ECC这方面挺薄弱的,记得以前写过一个计算ECC公钥的脚本,刚才看了下貌似是错的?玩极客大挑战时和zeroi3搞一道ECC的题也花了好久时间。

弱すきだと思いけれと、まあ、頑張ります。
以后遇到ECC的题目就在这记录一下。
ECC的一些基础知识:
https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/discrete-log/ecc/
https://www.pediy.com/kssd/pediy06/pediy6014.htm

geek_9th

attachment:

1
2
3
4
5
6
7
8
9
10
y^2 = x^3 - 4 (mod 1300047890243775110411566068001)
G(2, 2)
Pb = (909389018886235696038766661889, 46368123338914480456323106832)
Cm = {
(728655000686462026765334924207, 784703279412824406448137419123),
(1093265331080107082393273907159, 659299866410220726142342115664)
}

flag格式:
SYC{横坐标 纵坐标}

这里给了公钥:Ep(a,b),Pa(此处为Pb)和密文Cm
题目要求要求明文m.

引用wiki上的加密过程:

1
2
3
4
5
6
用户B在向用户A发送消息m,这里假设消息m已经被编码为椭圆曲线上的点,其加密步骤如下:
1. 查询用户 A 的公钥Eq(a,b),q,Pa,G 。
2. 在 (1,q-1) 的区间内选择随机数 k 。
3. 根据 A 的公钥计算点(x1,y1)=kG 。
4. 计算点(x2,y2)=kPa ,如果为 O,则从第二步重新开始。
5. 计算C=m+(x2,y2)将((x1,y1),C) 发送给 A。

现知C,若要求m,则需得知(x2,y2),而(x2,y2)=kPa
Pa已知,求出k即可得解。

由等式(x1,y1)=kG求出k是困难的,但可以使用Pohlig-Hellman算法来攻击ECC。
具体参考:https://www.anquanke.com/post/id/159893

下面直接写过程。
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
sage: F=GF(1300047890243775110411566068001)
sage: E=EllipticCurve(F,[0,-4])
sage: G=E([2,2])
sage: Pa=E([909389018886235696038766661889,46368123338914480456323106832])
sage: pub=E([728655000686462026765334924207,784703279412824406448137419123]
....: )
sage: factor(G.order())
43 * 12451 * 15958903501 * 50718027954697
sage: prime=[43,12451,15958903501] #这里没有写50718027954697是因为下面没求出此阶的li,因为算过一次,这里就不写了。
sage: for fac in primes:
....: t=int(G.order())/int(fac)
....: dlog=discrete_log(t*pub,t*G,operation='+')
....: dlogs+=[dlog]
....: print("factor:"+str(fac)+", Discrete log: "+str(dlog))
....:
factor:43, Discrete log: 25
factor:12451, Discrete log: 7690
factor:15958903501, Discrete log: 22332333
sage: crt(dlogs,primes)
22332333# 求出私钥k=22332333
sage: k=22332333
sage: a=k*Pa #a=(x2,y2)
sage: C=E.point([1093265331080107082393273907159,65929986641022072614234211
....: 5664,1],false)#需要加上参数false,表示此点不在椭圆曲线E上,理论上此点应该在曲线上,后来出题人表示出题失误。
sage: m=C-a
sage: print m
(22334411 : 22331144 : 1)

最后的flag为:SYC{2233441122331144}

hack.lu 2018

Multiplayer Part-1

其实并没有用到什么ECC的考点,看懂源码就可以了。
花了点功夫在sage里安了pwntools,但直接sage exp.sage会爆pwntools的错误,只好在sage的shell里写exp了。

attachment
paramenter.sage:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
param = {   "hacklu":
((889774351128949770355298446172353873, 12345, 67890),
# Generator of Subgroup of prime order 73 bits, 79182553273022138539034276599687 to be excact
(238266381988261346751878607720968495, 591153005086204165523829267245014771),
# challenge Q = xP, x random from [0, 79182553273022138539034276599687)
(341454032985370081366658659122300896, 775807209463167910095539163959068826)
)
}

serverAdress = '0.0.0.0'
serverPort = 23426

(p, a, b), (px, py), (qx, qy) = param["hacklu"]
E = EllipticCurve(GF(p), [a, b])

P = E((px, py))
Q = E((qx, qy))

def is_distinguished_point(p):
return p[0] < 2^(100)

定义了ECC曲线,和P,Q两点。
server.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
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import asyncore, socket, json, sqlite3, time

FLAG1 = "flag{XXXXXXXXXXX}"
POINT_TRESHOLD = 200

def json_response(code, additional_parameter=""):
response_codes = {
0 : "Point added",
1 : "Collision found",
2 : "Point already included",
3 : 'Wrong input format. Please provide a string like this: {"x": val, "y": val, "c": val, "d": val, "groupID": val})',
4 : "Value mismatch! X != c*P + d*Q",
5 : "Server Error"
}
return '{"Response": "%d", "Message": "%s"%s}' % (code, response_codes[code], additional_parameter)


# Teams should choose a non-guessable groupID
def get_response(x, y, c, d, groupID):
# open connection to database
conn = sqlite3.connect("points.db")
conn.row_factory = sqlite3.Row
conn_cursor = conn.cursor()

# convert sage integers to string to avoid "Python int too large for SQLite INTEGER"
x = str(x)
y = str(y)
c = str(c)
d = str(d)

# Select records that map to the same X value
conn_cursor.execute("SELECT * FROM points WHERE x = :x", {"x": x})
query = conn_cursor.fetchall()

# No record found -> Point is not yet included
if len(query) == 0:
# Insert point into database
conn_cursor.execute("INSERT INTO points (x, y, c, d, groupID) VALUES (?, ?, ?, ?, ?)",
(x, y, c, d, groupID))
# Get number of points added by this group
conn_cursor.execute("SELECT x FROM points WHERE groupID = :gID", {"gID": groupID})
points_found = conn_cursor.fetchall()
add_param = ', "points_found": %d' % len(points_found)
# When they found POINT_TRESHOLD distinguished points and a collision occured, return the colliding values as well
if len(points_found) > POINT_TRESHOLD:
add_param += ', "flag1": "%s"' % FLAG1
if server.collision_found:
# compute x from the collision, second flag is just x (not in flag format)
add_param += ', "collision": %s' % (server.collision)
response = json_response(0, add_param)
else:
# One (or more) records found -> check if they have the same exponents
is_included = False
for row in query:
if row["c"] == c and row["d"] == d:
is_included = True
response = json_response(2)
break

if not is_included:
# Exponents are different -> Collision found, add this point
conn_cursor.execute("INSERT INTO points (x, y, c, d, groupID, collision) VALUES (?, ?, ?, ?, ?, 1)",
(x, y, c, d, groupID))
# Get number of points added by this group
conn_cursor.execute("SELECT x FROM points WHERE groupID = :gID", {"gID": groupID})
points_found = conn_cursor.fetchall()
add_param = ', "points_found": %d' % len(points_found)
# add collision
server.collision_found = True
server.collision = '{"c_1": %s, "d_1": %s, "c_2": %s, "d_2": %s}' % (c, d, row["c"], row["d"])
if len(points_found) > POINT_TRESHOLD:
add_param += ', "collision": %s' % (server.collision)
else:
add_param += ', "collision": "collision found but not enough distinguished points submitted yet"'

response = json_response(1, add_param + ', "c": %s, "d": %s' % (row["c"], row["d"]))

# close db connection and return response
conn.commit()
conn_cursor.close()
conn.close()
return response


class DLogHandler(asyncore.dispatcher_with_send):

def handle_read(self):
try:
json_data = self.recv(8192)
if not json_data:
return
data = json.loads(json_data)
# check if the format is correct
if not ("x" in data and "y" in data and "c" in data and "d" in data and "groupID" in data):

response = json_response(3)
else:
c = Integer(data["c"])
d = Integer(data["d"])
x = Integer(data["x"])
y = Integer(data["y"])
X = E((x, y))
if X == c*P + d*Q:
response = get_response(data["x"], data["y"], data["c"], data["d"], data["groupID"])
else:
print("expected %s = %d*%s + %d*%s, but got %s" % (c*P + d*Q, c, P, d, Q, X))
response = json_response(4)
self.send(response)

except Exception as e:
response = json_response(5, ', "Error Message": "%s"' % e)


class Server(asyncore.dispatcher_with_send):

def __init__(self, host, port):
asyncore.dispatcher.__init__(self)
self.create_socket(socket.AF_INET, socket.SOCK_STREAM)
self.set_reuse_addr()
self.bind((host, port))
self.listen(5)
# variable to store some collision
self.collision_found = False
self.collision = {}

def handle_accept(self):
pair = self.accept()
if pair is not None:
sock, addr = pair
print("incoming connection from %s" % repr(addr))
DLogHandler(sock)


if __name__ == '__main__':

load("parameters.sage")
server = Server(serverAdress, serverPort)
asyncore.loop()

代码挺长的,简单来说就是每次用json格式向程序输入5个数:x,y,c,d,groupID,groupID是自己的标识。
x,y,c,d需要满足E((x,y))==c*P+d*D(随便构造个等式就行了),输入200次之后,会给flag。

exp.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
# coding=utf-8
import json
from pwn import *
def json_input(x, y, c, d, groupID):
dict1 = {'x': str(x), 'y': str(y), 'c': str(c), 'd': str(d), 'groupID': str(groupID)}
return json.dumps(dict1)


param = { "hacklu":
((889774351128949770355298446172353873, 12345, 67890),
# Generator of Subgroup of prime order 73 bits, 79182553273022138539034276599687 to be excact
(238266381988261346751878607720968495, 591153005086204165523829267245014771),
# challenge Q = xP, x random from [0, 79182553273022138539034276599687)
(341454032985370081366658659122300896, 775807209463167910095539163959068826)
)
}

(p, a, b), (px, py), (qx, qy) = param["hacklu"]
E = EllipticCurve(GF(p), [a, b])

P = E((px, py))
Q = E((qx, qy))

# 随便起个groupID,因为是本地,不会和别的队伍冲突
groupID=233333


io=remote('127.0.0.1','23426')

for i in range(1,202):
X=i*P+i*Q #随意构造下
x=X[0]
y=X[1]
c=d=i
data=json_input(x,y,c,d,groupID)
io.sendline(data)
print io.recv()

1

原文作者: n3k0

发表日期: October 18th 2018, 3:38:59

发出嘶吼: 没有魔夜2玩我要死了

CATALOG
  1. 1. geek_9th
  2. 2. hack.lu 2018