0%

2024-corCTF&DeadsecCTF-wp-crypto

记录一下这周做到的几道赛题。

corCTF

steps

题目描述:

1
Alice and Bob have taken steps to communicate securely.

题目:

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
from Crypto.Util.number import getPrime
from random import randint
from hashlib import sha512
from secret import FLAG

p = getPrime(1024)

Pair = tuple[int, int]

def apply(x: Pair, y: Pair) -> Pair:
z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
z1 = x[0] * y[0] + x[1] * y[1]
return z0 % p, z1 % p

def calculate(n: int) -> Pair:
out = 0, 1
base = 1, 1

while n > 0:
if n & 1 == 1: out = apply(out, base)
n >>= 1
base = apply(base, base)

return out

def step(x: Pair, n: int):
'''Performs n steps to x.'''
return apply(x, calculate(n))

def xor(a: bytes, b: bytes) -> bytes:
return bytes(i ^ j for i, j in zip(a, b))

def main() -> None:
g = tuple(randint(0, p - 1) for _ in range(2))
a = randint(0, p)
b = randint(0, p)

A = step(g, a)
B = step(g, b)

print(p)
print(g)
print(A)
print(B)

shared = step(A, b)
assert shared == step(B, a)

pad = sha512(str(shared).encode()).digest()
print(xor(FLAG, pad))

if __name__ == "__main__":
main()

output.txt:

1
2
3
4
5
140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
(96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
(70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
(112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'

题目基于一个比较奇怪的DH密钥交换,其中主要的两个函数是apply和calculate,分别作用为(运算皆在模p下):

  • apply:接受两个向量$(x_0,x_1),(y_0,y_1)$作为输入,输出为:

  • calculate:显然是一个矩阵快速幂,对于输入的数字n,得到的结果是:

然后利用这两个函数商议了用于密钥交换的函数step,对于给定的向量g和私钥x,其得到的结果为apply(g,calculate(x))。然后A、B就利用step函数分别生成自己的密钥,并计算共享密钥:

给出g、A、B,要求计算shared来解密flag。

由于有g、A和B,所以由apply函数用resultant或者groebner可以轻松计算出calculate(a)和calculate(b)的值,而其实计算shared也就是在A的基础上继续计算(B也同理):

所以就很容易算出shared来了,因为并不需要解出a、b是多少,只需要知道calculate(a)和calculate(b)就行。

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

p = 140323158913416495607520736187548995477774864895449373468435168606940894555091715325755245563618777520381345121826124291879072024129139794758353829170487152290036863771427918014687523291663877491666410660298255515196964873944928956895167652588843616727666115196647426152811435167407394960435891152283442366721
g = (96065253104055475368515351480749372850658086665031683689391433619786525841252022013348418216780129963411710917302022475212035579772549622047772413277044476931991100469638284113901919733675144788049607999711496364391389612383885735460390196619821411998848060208912802838145365054170790882835846039461477718592, 99241616571709523646659145402511086659276737895777010655080069795289409091105858433710404513588065826008320709508748555232998727290258965620812790826701703542423766306117851146140634247906095481346444357123297761881438234083584836393572339820023598801127329326758926529813665950889866710376403818615042210724)
A = (70755695722452190644681854912493449110123792967984325777144153291795297730471865203878351550134745747839905472832417565386100721034554991782211134122667955909129461935072670637104557733518048519759925441567454988894610693095988261459294358350906447578625319131211019007537053689563772428590632011546870587548, 67209626648557152207459211543890871397518255584981755641031188457446084495247511864090204533159666638951190009379067537952490757956859052998865712873197974689323985952177932343928382624951392835548222455898153557185369330197085287972647654361464363270469055087587755117442462138962625643131163131541853061105)
B = (112356264561144892053527289833892910675229600209578481387952173298070535545532140474473984252645999236867287593260325203405225799985387664655169620807429202440801811880698414710903311724048492305357174522756960623684589130082192061927190750200168319419891243856185874901350055033712921163239281745750477183871, 53362886892304808290625786352337191943295467155122569556336867663859530697649464591551819415844644455424276970213068575695727349121464360678240605137740996864232092508175716627306324344248722088013523622985501843963007084915323781694266339448976475002289825133821073110606693351553820493128680615728977879615)
c = b'\xbaH\xca[V\xdf\xbb0d2jN"\x9d$e\xec\xe0M\x00\xdb\xf0\x8f\x99f\xc5\n\x8a\xc2h\xa7\xa7'

PR.<a0,a1> = PolynomialRing(Zmod(p))
f1 = g[0] * a1 + g[1] * a0 - g[0] * a0 - A[0]
f2 = g[0] * a0 + g[1] * a1 - A[1]
res = Ideal([f1,f2]).groebner_basis()
a0 = -res[0].coefficients()[1]
a1 = -res[1].coefficients()[1]

L = Matrix(Zmod(p),[
[0,1],
[1,1]
])
v0 = vector(Zmod(p),[0,1])
a = vector(Zmod(p),[a0,a1])


Pair = tuple[int, int]
def apply(x: Pair, y: Pair) -> Pair:
z0 = x[0] * y[1] + x[1] * y[0] - x[0] * y[0]
z1 = x[0] * y[0] + x[1] * y[1]
return z0 % p, z1 % p

def calculate(n: int) -> Pair:
out = 0, 1
base = 1, 1

while n > 0:
if n & 1 == 1: out = apply(out, base)
n >>= 1
base = apply(base, base)

return out

def step(x: Pair, n: int):
'''Performs n steps to x.'''
return apply(x, calculate(n))

def xor(a: bytes, b: bytes) -> bytes:
return bytes(i ^^ j for i, j in zip(a, b))


AB = apply(B, [a0,a1])
pad = sha512(str(AB).encode()).digest()
print(xor(c, pad))


#corctf{w4it_i7's_4ll_f1b0n4cci?}

然而真的想求出a、b其实也并不是一定没有办法,由于刚刚说了calculate实际上是个如下形式的快速幂:

所以对于calculate(a)来说就是:

所以实际上是求一个矩阵DLP。



monkfish

题目描述:

1
2
3
Hmm... smells like a fishy proof of knowledge...

(Part 1 out of 2)

题目:

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
#!/usr/bin/sage

import sys
print("I caught a monkfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
out = []
for i in range(m):
out.append((v.T * F[i] * v)[0, 0])
return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
out = []
for i in range(m):
out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
return matrix(FF, m, 1, out)

def create_pok(v, s, F):
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F, t)
verif = apply_verif_info(F, t, s)
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
return (com, t - a * s, verif)

def verif_pok(v, F, pi):
com = pi[0]
resp = pi[1]
verif = pi[2]
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
out1 = apply(F, resp)
out2 = com + (a * a) * v - a * verif
return out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = bytes(gen_seed)

F = []

for i in range(m):
cur = []
for j in range(n):
cur.append([])
for k in range(n):
cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
gen_seed = sha256(gen_seed).digest()
F.append(matrix(FF, n, n, cur))

s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)
assert verif_pok(v, F, pok)

print("m0 =", [list(FF).index(i[0]) for i in list(pok[0])])
print("m1 =", [list(FF).index(i[0]) for i in list(pok[1])])
print("m2 =", [list(FF).index(i[0]) for i in list(pok[2])])

print("Can you catch a monkfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])
m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

assert(m0 != [list(FF).index(i[0]) for i in list(pok[0])])
assert(m1 != [list(FF).index(i[0]) for i in list(pok[1])])
assert(m2 != [list(FF).index(i[0]) for i in list(pok[2])])

m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])
pi = (m0, m1, m2)

res = verif_pok(v, F, pi)
assert res == True

with open("flag.txt", "r") as f:
print(f.read())

题目基于一个矩阵zkp(运算皆在模5下),在连接上靶机后,靶机会按顺序完成以下几个步骤:

  • 随机生成64个0-255的整数当作seed

  • 利用seed生成m个nxn的矩阵,并组成列表F

  • 随机生成一个长为n的向量s

  • 对F中每个矩阵Fi,进行如下计算:

    并将结果拼接在一起,得到长度为m的向量v

做完上面这些后就进入createpok过程,其输入为 $(v,s,F)$,具体操作是:

  • 随机生成长度为n的向量t

  • 对F中每个矩阵Fi,进行如下计算:

    并将结果拼接在一起,得到长度为m的向量com(这个操作和上面得到v的操作一样,也就是apply函数)

  • 对F中每个矩阵Fi,进行如下计算:

    并将结果拼接在一起,得到长度为m的向量verif

  • 将com、v、verif一起做哈希并模5得到数字a

  • 返回三元组 $pok = (com, t - as, verif)$

之后是verify的过程,其输入为 $(v,F,pok)$,具体操作是:

  • 先解包pok得到com,resp和verify

  • 由com,v和verify计算哈希得到a

  • out1是apply(F,resp)得到的值

  • out2为:

  • out1与out2完全相等则能够通过verify

我们的任务是,给定seed、v和一个pok,要求产生另一个pok,其中每个向量均与给出的pok不相等,并且通过verify。

这很简单,由于只需要通过一次就有flag,而a只有0-4这几个值,所以随机到a=0的时候就压根不需要在意verify是什么了。

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
from Pwn4Sage.pwn import *
from hashlib import sha256
from Crypto.Util.number import *
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
out = []
for i in range(m):
out.append((v.T * F[i] * v)[0, 0])
return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
out = []
for i in range(m):
out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
return matrix(FF, m, 1, out)

def create_pok(v, s, F):
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F, t)
verif = apply_verif_info(F, t, s)
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
return (com, t - a * s, verif)

def verif_pok(v, F, pi):
com = pi[0]
resp = pi[1]
verif = pi[2]
#a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
a = 0
out1 = apply(F, resp)
out2 = com + (a * a) * v - a * verif
return out1 == out2


###################################################################### part1 get data
sh = remote("be.ax", 31105)
sh.recvuntil(b"m0 =")
m0 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"m1 =")
m1 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"m2 =")
m2 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"seed =")
init_seed = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"v =")
v = ast.literal_eval(sh.recvline().strip().decode())
v = Matrix(FF,v).T


###################################################################### part2 gen
gen_seed = bytes(init_seed)
F = []
for i in range(m):
cur = []
for j in range(n):
cur.append([])
for k in range(n):
cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
gen_seed = sha256(gen_seed).digest()
F.append(matrix(FF, n, n, cur))
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F, t)
ver = random_matrix(FF, m, 1)


###################################################################### part3 get flag
sh.recvuntil(b"m0 =")
sh.sendline(str([i for i in com]).encode())
sh.recvuntil(b"m1 =")
sh.sendline(str([i for i in t]).encode())
sh.recvuntil(b"m2 =")
sh.sendline(str([i for i in ver]).encode())
print(sh.recvline())


#corctf{dont_forget_the_soundness_error}



anglerfish

题目描述:

1
2
3
The devil of the sea strikes back!

(Part 2 out of 2)

题目:

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
#!/usr/bin/sage

import sys
print("I caught an anglerfish in the sea! ")
sys.stdout.flush()

from hashlib import sha256
from Crypto.Util.number import bytes_to_long
from random import SystemRandom
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)

def apply(F, v):
out = []
for i in range(m):
out.append((v.T * F[i] * v)[0, 0])
return matrix(FF, m, 1, out)

def apply_verif_info(F, a, b):
out = []
for i in range(m):
out.append((a.T * (F[i] + F[i].T) * b)[0, 0])
return matrix(FF, m, 1, out)

def create_pok(v, s, F):
proofs = []
for i in range(64):
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
com = apply(F, t)
verif = apply_verif_info(F, t, s)
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
proofs.append((com, t - a * s, verif))
return proofs

def verif_pok(v, F, pis):
coms = []
for pi in pis:
com = pi[0]
assert com not in coms
coms.append(com)
resp = pi[1]
verif = pi[2]
a = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(verif)])).digest()[0] % len(list(FF))]
out1 = apply(F, resp)
out2 = com + (a * a) * v - a * verif
assert out1 == out2

rng = SystemRandom()
gen_seed = []

for i in range(64):
gen_seed.append(rng.randint(0, 255))

init_seed = gen_seed
gen_seed = bytes(gen_seed)

F = []

for i in range(m):
cur = []
for j in range(n):
cur.append([])
for k in range(n):
cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
gen_seed = sha256(gen_seed).digest()
F.append(matrix(FF, n, n, cur))

s = random_matrix(FF, n, 1)

v = apply(F, s)

pok = create_pok(v, s, F)
verif_pok(v, F, pok)

for pi in pok:
print("m0 =", [list(FF).index(i[0]) for i in list(pi[0])])
print("m1 =", [list(FF).index(i[0]) for i in list(pi[1])])
print("m2 =", [list(FF).index(i[0]) for i in list(pi[2])])

print("Can you catch an anglerfish? ")
print("seed =", [int(i) for i in init_seed])
print("v =", [list(FF).index(i[0]) for i in v])

pis = []
for x in range(64):
m0 = [int(i) for i in ast.literal_eval(input("m0 = "))]
m1 = [int(i) for i in ast.literal_eval(input("m1 = "))]
m2 = [int(i) for i in ast.literal_eval(input("m2 = "))]

for pi in pok:
assert(m0 != [list(FF).index(i[0]) for i in list(pi[0])])
assert(m1 != [list(FF).index(i[0]) for i in list(pi[1])])
assert(m2 != [list(FF).index(i[0]) for i in list(pi[2])])

m0 = matrix(FF, m, 1, [list(FF)[i] for i in m0])
m1 = matrix(FF, n, 1, [list(FF)[i] for i in m1])
m2 = matrix(FF, m, 1, [list(FF)[i] for i in m2])

assert m0 not in [pi[0] for pi in pok]
assert m1 not in [pi[1] for pi in pok]
assert m2 not in [pi[2] for pi in pok]

pi = (m0, m1, m2)
pis.append(pi)

verif_pok(v, F, pis)

with open("flag.txt", "r") as f:
print(f.read())

和上一题比起来,这题需要通过64次才行,所以纯碰0显然是不行了。

但是目的仍然只有一个,并不需要特别理解这个zkp里verify的细节,我们只需要让verify中out1=out2,仅此而已。

而verify的可操作性相当大,除了给定的v和F,整个pok都是我们可以自行输入的,只要不与给定的那个pok相等就行。那么不妨按如下步骤操作:

  • 随机输入一个resp,得到out1
  • 随机输入一个com,之后在0-4爆破a1,并由out1=out2这个式子计算出verify
  • 计算出对应的verify之后,计算哈希值a2
  • 如果a1=a2,就找到了符合要求的碰撞了

如果0-4都不符合条件,就重新随机取就行。

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
from Pwn4Sage.pwn import *
from hashlib import sha256
from Crypto.Util.number import *
from tqdm import *
import ast

n = 100
m = 100
q = 5
FF.<x> = GF(q)


def apply(F, v):
out = []
for i in range(m):
out.append((v.T * F[i] * v)[0, 0])
return matrix(FF, m, 1, out)


###################################################################### part1 get data
sh = remote("be.ax", 31106)

poks = []
for i in trange(64):
sh.recvuntil(b"m0 =")
m0 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"m1 =")
m1 = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"m2 =")
m2 = ast.literal_eval(sh.recvline().strip().decode())
poks.append([m0,m1,m2])

sh.recvuntil(b"seed =")
init_seed = ast.literal_eval(sh.recvline().strip().decode())
sh.recvuntil(b"v =")
v = ast.literal_eval(sh.recvline().strip().decode())
v = Matrix(FF,v).T


###################################################################### part2 gen F
gen_seed = bytes(init_seed)
F = []
for i in range(m):
cur = []
for j in range(n):
cur.append([])
for k in range(n):
cur[-1].append(list(FF)[sha256(gen_seed).digest()[0] % len(list(FF))])
gen_seed = sha256(gen_seed).digest()
F.append(matrix(FF, n, n, cur))


###################################################################### part3 get flag
for i in trange(64):
while(1):
FIND = 0
t = matrix(FF, n, 1, [FF.random_element() for i in range(n)])
out1 = apply(F, t)
com = out1
for a in range(5):
if(a == 0):
ver = random_matrix(FF, m, 1)
else:
ver = (com + (a * a) * v - out1) * inverse(a,5)
aa = list(FF)[sha256(bytes([list(FF).index(i[0]) for i in list(com) + list(v) + list(ver)])).digest()[0] % len(list(FF))]
if(aa == a):
FIND = 1
break
if(FIND == 1):
break

sh.recvuntil(b"m0 =")
sh.sendline(str([i for i in com]).encode())
sh.recvuntil(b"m1 =")
sh.sendline(str([i for i in t]).encode())
sh.recvuntil(b"m2 =")
sh.sendline(str([i for i in ver]).encode())

print(sh.recvline())


#corctf{extra_equations_means_extra_information_isnt_zk}



roots

题目描述:

1
Check out this cool cryptosystem! Can you break it without the key?

题目:

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
from Crypto.Util.number import getPrime, bytes_to_long
from random import getrandbits
from decimal import Decimal, getcontext
from secret import FLAG

N = 3
MSIZE = 64
PSIZE = 128

getcontext().prec = 2024

def chunk(inp: bytes, n: int) -> list[bytes]:
return [inp[i:i + n] for i in range(0, len(inp), n)]

def generate() -> list[int]:
return sorted(getPrime(PSIZE) for _ in range(N))

def otp(data: int) -> list[int]:
key = [getrandbits(MSIZE) for _ in range(N - 1)]

# Apply multiple times for extra security! ;)
for k in key:
data ^= k

return key + [data]

def enc(data: int, key: list[int]) -> Decimal:
return sum(a * Decimal(p).sqrt() for a, p in zip(otp(data), key))

def encrypt(plaintext: bytes, key: list[int]) -> Decimal:
out = []
for pt in chunk(plaintext, MSIZE // 8):
out.append(enc(bytes_to_long(pt), key))

return out

def main() -> None:
key = generate()
ct = encrypt(FLAG, key)

print(ct)

if __name__ == "__main__":
main()

output.txt:

1
[Decimal('613865483278018068252699664344014709603.51690674693116605142775061636120046870769083140402021865687508441855022441399605307934286489840179576316516207824661811160477759304066064291205730622145206447227404607082151753919361349868545307462428210932437992623119255718054243534096986413211959304171135887211540587436459888779324151143025499619973135708235491605216411394962317959813656209629567607308778163987166821943423002154894970121188451784354115735408809579052563235078363998602200794840158081619720701643652284259066561050115602486569569690456649269369511972329349611423116985630502303784458447333880791258687570760036481989066910025496948546865951981177430643941260666483918647746947170525925083317666875914436471646901318749705595856856883346891726769074746650987330068104292614480104709810601198864073890537548001433033723615776224146304045036932985711688197452123005099236554526727107165691391180111605054039864164377438525310672107170437281478322426514683178129245151967154583110424925964982504343607726182942419964058684010006450471850408468724523024702559055514056791838218373955386876710426728739081458827252802226359687030921900842002785720726229892098824084346436742345912593840934579190526250607721076769764172513184565791506300616867803697312829413891917781663107526096475492046133891964020871514785931302212911910422061349227840920633130097807344731335384126657969326959305179863489255473137828869343169464391631468853227921632272791516165605848151467308601405844760824881338357444888188035204000407673339331919346899410420054651077086850532999310419256243385542853597931278472451318309939063364567112084455650629429599265528219435289213175349567467961574398181095962343974433190931067322110878499680729907288265465620467270493396020598011075090015918395921964211257921275263305336676548841001128867189130080538627211844161021733430009452985356108168888790283056201446152044771750329866340679923824523137794621308627512829896733426062792367679307468573465298446962647695970868442917945963296248995830871462803'), Decimal('245036407881857959287329830175942706463.41676802782442994887934627742200369945701412601647195354905097451178257098540606801565385675107318120460650888047274089786443222032370562593772359240722830861471549006005870906901656856743873456596259047367300567575908527230366385292440919562964298317812232800102576149495809413427952810634193186781922614214268017709482845572771078220390794231892763512491653218636267112852524278614145782738125962122310806946368712582799445479001874840170209715004731276988049273955290890839588161009103614134479683822558461311134193156291806539774288015592213012944114677791107334704048050248067790961044976635609645113466054839476916586971455181287563116833537875679872852426596500045916084590678852453213603747411621009244578584574321606967288315507350789499360210767971560504476491167021056575773203913674206412928683729647182751865762672106362511792516860263344700590671316013798899626125150168033775577935989491544189330151349377248071416776567110915867894841003988715963213282301539772548019203054604324657682585086974883293993693364621477765424253486620846417121914627069652179323747638053294808478946841684842391124370675090921956558456987438962361101647423473932215595029566302891192438202103166531605890363352381011015329475002801933772777494625189852526005526409489415563470356698119177369784245367090617016832725703245455210343971981483284742666226075984764682029024194412093587469973865623264825887838718407665448451327538641035583414835042280186524871430174844859199371418365330179156143049238655596474961217964906635309020982967098088279871772621354935094165104148277851308675528401723829872589324051699054275878133606165491429811386740566384976019587172015296076695877847670182335353621529186538640618471230538158759335554894682026973199860563823746052413212330496106907455577991532192244914548792485371507973770044500533179391911148716837049004674981572325374669719464763272448641196278444851808838959425053174592256179039838611577554410785172685506776747109456418706054407235309341'), Decimal('137345167246666152708695783992412451677.21558050568623481295196376367975242130555102201515580316330966697148890411534221923225952905285897183010922406175094262069208074739275097805536185634560982617648832780575658021059502299936366800046975825224832714908010519763833830348421655509168881358855533351044140363192436142763626456404652383592376546952793513967937938636543810723145564947948780573116974908526774605955951469943187865644596524139107481653386681950240101520692953876806620084423038367388560905871875836530739404184303742718262418117805718036122357051928716596276399762849629107495322882675719409051073299089695124393278836941013272789785477953131515760862594743832917404252472431732912434480355250761546326425334589230931109133966112698705631064298540629644087174339495451233415165784208154862632994746999100506080852291240231466075807689137982406781289386109243195384399444517321654449447540787541127685794368775611662723601685545144635953407926414192981817325925467123186823453700610674338813375219959042008201960857405988222431762449068615565770592161380029925528004633925411749903272512805896758350376028759094075163759541252996218647962921737695225607000672827355712319484834139082006323871120783473891599300315829557138141744616522321981481762618665822002496867084381222827633659627360022043393386819320488647893458122132426243653269827396864109912568570075611460793016682214280860824555257535036669613199445516497725227349649115460430628789851678786053832488469704975290639037623666238775508475503615248256142687325810589424170821237702234472583990907852983428072024771329547328770035145579513303770469872758505372515800860236159229593770017270383301142993264982903473737872532789578999358701823743117676045641159467315897055924399632998579024195194906804156820621748747515175782908138772828776041903750590418332731770693214602115172315637279313855936478443754676804416808777432960976763034716998360016818363826448918529745873789717604991019505220078545941396511331142324037841720139678985890298577830351331'), Decimal('248598813941244564314190366976956238846.21287154177193010973910605580779261210365984174749796180419923931211513873961571752231238459134695223104083276961569452018392982079324317136535206452261881826873414602629594471707660157457896214988591398626491707261264840694400878016171848489165321633160306766022332706508213328119352706170273262931280561423851178335709726505935522918272264480451898981178517451201483151591554008657960692345350455891365321593940275460890295306738282405071381298895783171740603832308867778448785711118127825021180253182388515151158156028351993831870085534975634188825697876813579914222802552156594566015228528827397850794636185597567790199750813063356917626291927109597628605896564415404785475255907843090500284371578116809505806089285850503289523274957689703557226650819188753255887580294403919233020671057076485044952433816771965385673494711771474126428651980119604119559562596188714862777544919355156232243652718517709528203262205358442941280815388198987743628689516005444663613668047007886122931571139930784688640045996582570962554713967405406762001906063378302125401898155550603489814135391137430186059041384496922239998747587303366147421038091369722510204804734395780572006815615350115111367222110517089689188974108653902029376056551397900019653419884380778042660817204485470749571339982927039079734483080043934563757326484950182811230031559346385457298240850154178951900739178353564235216322232791700369486112525607172179782914690610012323349746725297341069764127541218762893367556754429312136345943483494236203659704464226488931565438262759788872114208783818792121079840366002113316654063450919686404664767226446116187197107156555434824485171863955895656710114494285915504850382199832564322800850387423097212704670656698969249945269974571051395109564672354772654744585684053379753599154369914818372119637829894516195738013893515476266773802929361065238109305019468285763072333229080155510459572404321239788374283507107268753407976278020430629150787678790300001623259645896920037795093793915002')]

题目先生成3个128bit的素数p1、p2、p3,并按顺序排列好当作key。然后将flag按8字节拆成一个分组,记为mi,并计算:

明文共有四组,也就是有四个密文值,其中ki1、ki2是每次计算随机产生的64位nonce,并且计算精度为getcontext().prec = 2024,要求还原flag

首先,如果把四组明文拼接在一起,就成了一个矩阵乘法:

而如果同乘一个大系数T,就可以把含小数的计算转到整数下,也就是:

而由于精度固定,所以进行运算时也会产生一定误差,因此整个式子实际上是:

所以其实整个式子就抽象成了:

看上去像个LWE问题,但是问题在于我们只知道c而已。然而这个式子显然有个额外信息,就是除了e以外,A也是很小的,所有值都是64bit的数量级。因此可以用正交格的思路来考虑:

  • 找到短向量u,使得u与b近似正交,也就是ub的结果小

  • 由于u是短向量,因此ue结果也小

  • 又因为x是大向量,所以要使得下面式子继续成立的话:

    有理由相信此时下面的式子成立:

  • 而由于A也比较小,所以在u的右核中规约就有机会找到A了

而这样操作下了,实际上找到的并不是A,而是A中向量的线性组合,但是简单爆破一下线性组合就可以找到原始的A,之后做异或就能得到flag。

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
from Crypto.Util.number import *
from decimal import Decimal, getcontext
from itertools import *

N = 3
MSIZE = 64
PSIZE = 128

getcontext().prec = int(2024)

c = [Decimal('613865483278018068252699664344014709603.51690674693116605142775061636120046870769083140402021865687508441855022441399605307934286489840179576316516207824661811160477759304066064291205730622145206447227404607082151753919361349868545307462428210932437992623119255718054243534096986413211959304171135887211540587436459888779324151143025499619973135708235491605216411394962317959813656209629567607308778163987166821943423002154894970121188451784354115735408809579052563235078363998602200794840158081619720701643652284259066561050115602486569569690456649269369511972329349611423116985630502303784458447333880791258687570760036481989066910025496948546865951981177430643941260666483918647746947170525925083317666875914436471646901318749705595856856883346891726769074746650987330068104292614480104709810601198864073890537548001433033723615776224146304045036932985711688197452123005099236554526727107165691391180111605054039864164377438525310672107170437281478322426514683178129245151967154583110424925964982504343607726182942419964058684010006450471850408468724523024702559055514056791838218373955386876710426728739081458827252802226359687030921900842002785720726229892098824084346436742345912593840934579190526250607721076769764172513184565791506300616867803697312829413891917781663107526096475492046133891964020871514785931302212911910422061349227840920633130097807344731335384126657969326959305179863489255473137828869343169464391631468853227921632272791516165605848151467308601405844760824881338357444888188035204000407673339331919346899410420054651077086850532999310419256243385542853597931278472451318309939063364567112084455650629429599265528219435289213175349567467961574398181095962343974433190931067322110878499680729907288265465620467270493396020598011075090015918395921964211257921275263305336676548841001128867189130080538627211844161021733430009452985356108168888790283056201446152044771750329866340679923824523137794621308627512829896733426062792367679307468573465298446962647695970868442917945963296248995830871462803'), Decimal('245036407881857959287329830175942706463.41676802782442994887934627742200369945701412601647195354905097451178257098540606801565385675107318120460650888047274089786443222032370562593772359240722830861471549006005870906901656856743873456596259047367300567575908527230366385292440919562964298317812232800102576149495809413427952810634193186781922614214268017709482845572771078220390794231892763512491653218636267112852524278614145782738125962122310806946368712582799445479001874840170209715004731276988049273955290890839588161009103614134479683822558461311134193156291806539774288015592213012944114677791107334704048050248067790961044976635609645113466054839476916586971455181287563116833537875679872852426596500045916084590678852453213603747411621009244578584574321606967288315507350789499360210767971560504476491167021056575773203913674206412928683729647182751865762672106362511792516860263344700590671316013798899626125150168033775577935989491544189330151349377248071416776567110915867894841003988715963213282301539772548019203054604324657682585086974883293993693364621477765424253486620846417121914627069652179323747638053294808478946841684842391124370675090921956558456987438962361101647423473932215595029566302891192438202103166531605890363352381011015329475002801933772777494625189852526005526409489415563470356698119177369784245367090617016832725703245455210343971981483284742666226075984764682029024194412093587469973865623264825887838718407665448451327538641035583414835042280186524871430174844859199371418365330179156143049238655596474961217964906635309020982967098088279871772621354935094165104148277851308675528401723829872589324051699054275878133606165491429811386740566384976019587172015296076695877847670182335353621529186538640618471230538158759335554894682026973199860563823746052413212330496106907455577991532192244914548792485371507973770044500533179391911148716837049004674981572325374669719464763272448641196278444851808838959425053174592256179039838611577554410785172685506776747109456418706054407235309341'), Decimal('137345167246666152708695783992412451677.21558050568623481295196376367975242130555102201515580316330966697148890411534221923225952905285897183010922406175094262069208074739275097805536185634560982617648832780575658021059502299936366800046975825224832714908010519763833830348421655509168881358855533351044140363192436142763626456404652383592376546952793513967937938636543810723145564947948780573116974908526774605955951469943187865644596524139107481653386681950240101520692953876806620084423038367388560905871875836530739404184303742718262418117805718036122357051928716596276399762849629107495322882675719409051073299089695124393278836941013272789785477953131515760862594743832917404252472431732912434480355250761546326425334589230931109133966112698705631064298540629644087174339495451233415165784208154862632994746999100506080852291240231466075807689137982406781289386109243195384399444517321654449447540787541127685794368775611662723601685545144635953407926414192981817325925467123186823453700610674338813375219959042008201960857405988222431762449068615565770592161380029925528004633925411749903272512805896758350376028759094075163759541252996218647962921737695225607000672827355712319484834139082006323871120783473891599300315829557138141744616522321981481762618665822002496867084381222827633659627360022043393386819320488647893458122132426243653269827396864109912568570075611460793016682214280860824555257535036669613199445516497725227349649115460430628789851678786053832488469704975290639037623666238775508475503615248256142687325810589424170821237702234472583990907852983428072024771329547328770035145579513303770469872758505372515800860236159229593770017270383301142993264982903473737872532789578999358701823743117676045641159467315897055924399632998579024195194906804156820621748747515175782908138772828776041903750590418332731770693214602115172315637279313855936478443754676804416808777432960976763034716998360016818363826448918529745873789717604991019505220078545941396511331142324037841720139678985890298577830351331'), Decimal('248598813941244564314190366976956238846.21287154177193010973910605580779261210365984174749796180419923931211513873961571752231238459134695223104083276961569452018392982079324317136535206452261881826873414602629594471707660157457896214988591398626491707261264840694400878016171848489165321633160306766022332706508213328119352706170273262931280561423851178335709726505935522918272264480451898981178517451201483151591554008657960692345350455891365321593940275460890295306738282405071381298895783171740603832308867778448785711118127825021180253182388515151158156028351993831870085534975634188825697876813579914222802552156594566015228528827397850794636185597567790199750813063356917626291927109597628605896564415404785475255907843090500284371578116809505806089285850503289523274957689703557226650819188753255887580294403919233020671057076485044952433816771965385673494711771474126428651980119604119559562596188714862777544919355156232243652718517709528203262205358442941280815388198987743628689516005444663613668047007886122931571139930784688640045996582570962554713967405406762001906063378302125401898155550603489814135391137430186059041384496922239998747587303366147421038091369722510204804734395780572006815615350115111367222110517089689188974108653902029376056551397900019653419884380778042660817204485470749571339982927039079734483080043934563757326484950182811230031559346385457298240850154178951900739178353564235216322232791700369486112525607172179782914690610012323349746725297341069764127541218762893367556754429312136345943483494236203659704464226488931565438262759788872114208783818792121079840366002113316654063450919686404664767226446116187197107156555434824485171863955895656710114494285915504850382199832564322800850387423097212704670656698969249945269974571051395109564672354772654744585684053379753599154369914818372119637829894516195738013893515476266773802929361065238109305019468285763072333229080155510459572404321239788374283507107268753407976278020430629150787678790300001623259645896920037795093793915002')]

L = block_matrix(ZZ,[
[1,Matrix(ZZ,[int(i*int(10^2000)) for i in c]).T]
])
L = L.LLL()
res = L[0][:len(c)]
L = Matrix(Matrix(ZZ,res).right_kernel().basis())
A = L.LLL()

import string
vecs = [A[0],A[1],A[2]]
valid_vecs = []
for i in product([i for i in range(-5,5)],repeat=3):
i1 = 0
for j in range(3):
i1 += i[j] * vecs[j]
if(all(tt > 0 and tt < 2^64 for tt in i1) and i1 not in valid_vecs):
valid_vecs.append(i1)

for i in combinations(valid_vecs,3):
i1,i2,i3 = list(i)

flag = b""
for j in range(4):
flag += long_to_bytes(abs(int(i1[j])^^int(i2[j])^^int(i3[j])))
if(b"corctf{" in flag):
print(flag)


#corctf{I'm_r00t1ng_f0R_U!!!!!!!}



other

此外还有两个题目,一个是区块链一个是量子,都没接触过,之后有机会再说吧,不过感觉大概率不太会去了解太多XD。



Deadsec CTF

这比赛被Zima拉着一起看了看,其中有一个题目还比较有趣,所以还是记录下。

Flag killer

题目描述:

1
Is it enough obfuscation?

题目:

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
#!/usr/bin/python3

from binascii import hexlify

flag = hexlify(b'DEAD{test}').decode()

index = 0
output = ''

def FLAG_KILLER(value):
index = 0
temp = []
output = 0
while value > 0:
temp.append(2 - (value % 4) if value % 2 != 0 else 0)
value = (value - temp[index])/2
index += 1
temp = temp[::-1]
for index in range(len(temp)):
output += temp[index] * 3 ** (len(temp) - index - 1)
return output


while index < len(flag):
output += '%05x' % int(FLAG_KILLER(int(flag[index:index+3],16)))
index += 3

print(output)

enc.txt:

1
0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883

不用细看步骤,看最下面的while就知道实际上就是把flag的每三位16进制的值用某个5位十六进制表示,所以建个表然后查就好了。

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

def FLAG_KILLER(value):
index = 0
temp = []
output = 0
while value > 0:
temp.append(2 - (value % 4) if value % 2 != 0 else 0)
value = (value - temp[index])/2
index += 1
temp = temp[::-1]
for index in range(len(temp)):
output += temp[index] * 3 ** (len(temp) - index - 1)
return hex(int(output))[2:].zfill(5)

c = "0e98b103240e99c71e320dd330dd430de2629ce326a4a2b6b90cd201030926a090cfc5269f904f740cd1001c290cd10002900cd100ee59269a8269a026a4a2d05a269a82aa850d03a2b6b900883"

if(0):
dic = {}
for i in trange(2**24):
dic[FLAG_KILLER(i)] = hex(i)[2:].zfill(3)

flag = ""
for i in trange(len(c)//5):
flag += dic[c[i*5:i*5+5]]
print(flag)

print(bytes.fromhex("444541447b323633663837316538383065396463376432343031303030333034666336306539386337633538387d"))


#DEAD{263f871e880e9dc7d2401000304fc60e98c7c588}



Raul Rosas

题目描述:

1
"I say weird stuff all the time."

题目:

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

p1 = bin(getPrime(1024))[2:]
p2 = p1[:605]
p2 = p2 + ('0'*(len(p1)-len(p2)))

p1 = int(p1,2)
p2 = nextprime(int(p2,2))

q1 = getPrime(300)
q2 = getPrime(300)

n1 = p1*p1*q1
n2 = p2*p2*q2

e = 65537
flag = bytes_to_long(b'REDACTED')
c1 = pow(flag,e,n1)
c2 = pow(flag,e,n2)

print(f'{n1=}')
print(f'{n2=}')
print(f'{c1=}')
print(f'{c2=}')


"""
n1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
n2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
c1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
c2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
"""

难得见到这么亲切的RSA题目,熟悉的味道。

题目先生成1024bit的素数p1。然后保留p1的高605位,并把低位全部抹掉之后,取nextprime得到p2,之后计算:

其中q1、q2是300bit的小素数。给出n1、n2,并给出分别用n1、n2加密flag得到的c1、c2,要求还原明文。

由于p2低位仅有一个nextprime的小量,也就是他可以写成:

所以n2就是:

展开一下:

可以看出其实n2的低位其实是:

所以爆破一下delta就可以得到q2了,之后就很容易。

exp:

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

t = int("11100110111010000010101011000000011010100111100000010000101011001001011100001111111101100011100100011011111110000001110110010010111111001100111100011010101000010001100100000010000111010011010001101111011101101011111011111000000111100001001100001100111011110011011010001000110111110000101010110010111000111010010111",2)

n1=33914684861748025775039281034732118800210172226202865626649257734640860626122496857824722482435571212266837521062975265470108636677204118801674455876175256919094583111702086440374440069720564836535455468886946320281180036997133848753476194808776154286740338853149382219104098930424628379244203425638143586895732678175237573473771798480275214400819978317207532566320561087373402673942574292313462136068626729114505686759701305592972367260477978324301469299251420212283758756993372112866755859599750559165005003201133841030574381795101573167606659158769490361449603797836102692182242091338045317594471059984757228202609971840405638858696334676026230362235521239830379389872765912383844262135900613776738814453
n2=45676791074605066998943099103364315794006332282441283064976666268034083630735700946472676852534025506807314001461603559827433723291528233236210007601454376876234611894686433890588598497194981540553814858726066215204034517808726230108550384400665772370055344973309767254730566845236167460471232855535131280959838577294392570538301153645042892860893604629926657287846345355440026453883519493151299226289819375073507978835796436834205595029397133882344120359631326071197504087811348353107585352525436957117561997040934067881585416375733220284897170841715716721313708208669285280362958902914780961119036511592607473063247721427765849962400322051875888323638189434117452309193654141881914639294164650898861297303
c1=5901547799381070840359392038174495588170513247847714273595411167296183629412915012222227027356430642556122066895371444948863326101566394976530551223412292667644441453331065752759544619792554573114517925105448879969399346787436142706971884168511458472259984991259195488997495087540800463362289424481986635322685691583804462882482621269852340750338483349943910768394808039522826196641550659069967791745064008046300108627004744686494254057929843770761235779923141642086541365488201157760211440185514437408144860842733403640608261720306139244013974182714767738134497204545868435961883422098094282377180143072849852529146164709312766146939608395412424617384059645917698095750364523710239164016515753752257367489
c2=3390569979784056878736266202871557824004856366694719533085092616630555208111973443587439052592998102055488632207160968490605754861061546019836966349190018267098889823086718042220586285728994179393183870155266933282043334755304139243271973119125463775794806745935480171168951943663617953860813929121178431737477240925668994665543833309966378218572247768170043609879504955562993281112055931542971553613629203301798161781786253559679002805820092716314906043601765180455118897800232982799905604384587625502913096329061269176369601390578862509347479694697409545495592160695530037113884443071693090949908858172105089597051790694863761129626857737468493438459158669342430468741236573321658187309329276080990875017
q2 = GCD(t,n2)

p2 = iroot(n2 // q2,2)[0]
print(p2)
phi2 = p2*(p2-1)*(q2-1)
print(long_to_bytes(pow(c2,inverse(65537,phi2),n2)))


#DEAD{Rual_R0s4s_Chiweweiner!!}

不过其实p2、q2是300bit,以及p1、q1高位相同,这些信息明显是指向copper的,比如AGCD。



SSP

题目描述:

1
Sometimes it requires GPU to compute huge amount of operation... like $O(2^100)$..? Nah, you'll use better algorithm, $O(2^50)$ seems fair huh?

题目:

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
MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method

from random import randrange

for n in range(1, MAX_N + 1):

print(f"Stage {n}")

arr = [ randrange(0, RAND_MAX) for _ in range(n) ]
counts = randrange(0, n + 1)

used = set()

while True:

idx = randrange(0, n)
used.add(idx)

if len(used) >= counts:
break

s = 0
for idx in used:
s += arr[idx]

for a in arr:
print(a, end=' ')
print(s)

answer = list(map(int, input().split()))

user_sum = 0
for i in answer:
user_sum += arr[i]

if user_sum != s:
print("You are wrong!")
exit(0)

print(f"Stage {n} Clear")

print("Long time waiting... Here's your flag.")

with open('./flag', 'r') as f:
print(f.read())

题目还专门说了背包没法彻底解决,然而就用背包做完全没遇到障碍TT,并且也没看出有什么特殊点。

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
from Pwn4Sage.pwn import *
from tqdm import *

MAX_N = 100
RAND_MAX = 10 ** 200 # You can't even solve with knapsack method

sh = remote("35.188.216.251",32222)

for n in trange(1, MAX_N + 1):
sh.recvline()
arr = list(map(int,(list(sh.recvline().strip().decode().split(" ")))))
s = arr[-1]
arr = arr[:-1]

L = block_matrix(ZZ,[
[1,Matrix(ZZ,arr).T],
[Matrix.zero(1, len(arr)),-s]
])
L[:,-1:] *= RAND_MAX
res = L.LLL()[0][:-1]

ans = ""
for i in range(len(res)):
if(abs(res[i]) == 1):
ans += (str(i) + " ")
sh.sendline(ans.encode())
sh.recvuntil(b"Clear")
sh.recvline()

print(sh.recvline())
print(sh.recvline())


#DEAD{T00_B1g_Number_Causes_Pr0blem...}

后来想了想他说的不能用的背包解法也许是指算法里的。。。



Password Guesser

题目描述:

1
Can you figure out my password, I lost it

题目:

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 collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math

flag = b'<REDACTED>'
P = 13**37
password = b'<REDACTED>'
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)

print(f"counts = {[cnt for _, cnt in Counter(password2).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC)
print(f"c = {cipher.encrypt(pad(flag, 16))}")
print(f"iv = {cipher.iv}")


'''
counts = [5, 4, 7, 5, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 4, 4, 4, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]
c = b'q[\n\x05\xad\x99\x94\xfb\xc1W9\xcb`\x96\xb9|CA\xb8\xb5\xe0v\x93\xff\x85\xaa\xa7\x86\xeas#c'
iv = b'+\xd5}\xd8\xa7K\x88j\xb5\xf7\x8b\x95)n53'
'''

这个题目挺有意思,他先是从printable里面选取了一些字符记作password,这个password满足:

将他排序好之后得到password2,给出password2里面每个元素的count,要求还原password2来解AES得到flag。

首先就是,printable里面有100个字符,然而count中只有89个,所以如果直接爆破的话,需要爆破$C_{100}^{89}$这么多种,虽然说用c++加多进程并不是做不到,但是显然有点太粗糙了。

而且可以发现,这个思路有一个很大的弊端,就是仅仅把上面给出的这个条件:

当作检验爆破正确的结果在使用,然而这个条件本身肯定是解题的关键。

对于sum来说,由于所有字符都是printable里的,值都小于128,所以结合count的实际情况来看,这个sum最大也就几万,是远远小于13^37的,而prod则很轻松就能超过13^37。

那么不妨记这个sum值为c,那么其实就有:

而仔细想想这个等式会发现,13^37其实带来了很大的特殊性,由于c最多只有几万,所以一定有:

那么对于prod,如果其中因子含13的字符超过了4个,那么就一定不符合上面的式子了,这是因为若有:

则:

所以说,password里面其实根本就没几个因子含13的字符,不然他们的prod在模13^37下一定会大于他们的sum,所以就大大减小了爆破范围,因此较短时间内就能找到解。

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
from collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math
import string
from tqdm import *
from itertools import *

P = 13**37
table = sorted([ord(i) for i in string.printable])
counts = [5, 4, 7, 5, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 4, 4, 4, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]

def mul(t1,t2):
tt = 1
assert len(t1) == len(t2)
for i,j in zip(t1,t2):
tt *= i**j
tt = tt % P
return tt % P

def dot(t1,t2):
tt = 0
assert len(t1) == len(t2)
for i,j in zip(t1,t2):
tt += i*j
return tt % P

if(0):
for kkk in range(1,10):
if(kkk == 2):
continue
tt = [ord(i) for i in string.printable if ord(i) % 13 != 0]
tt = [13*kkk] + tt
tt = sorted(tt)
idx_kkk = tt.index(13*kkk)

for i in tqdm(combinations(range(len(tt)), len(tt) - len(counts)),total=math.comb(len(tt),len(counts))):
temp = [0 for i in range(len(tt))]
idxx = 0
for j in range(len(tt)):
if(j not in i):
temp[j] = counts[idxx]
idxx += 1

if(temp[idx_kkk] > 4):
continue
if(dot(tt,temp) == mul(tt,temp)):
print(temp)

temp = [5, 4, 7, 5, 0, 5, 8, 9, 4, 5, 7, 4, 4, 7, 5, 7, 8, 4, 2, 5, 5, 4, 3, 10, 4, 5, 7, 4, 4, 4, 6, 5, 12, 5, 5, 5, 8, 7, 9, 2, 3, 2, 5, 8, 6, 4, 4, 7, 2, 4, 5, 7, 9, 4, 9, 7, 4, 7, 8, 4, 2, 4, 4, 4, 4, 3, 3, 7, 4, 6, 9, 0, 4, 4, 0, 4, 0, 6, 7, 4, 4, 4, 1, 3, 5, 8, 4, 9, 11, 7, 4, 2, 4]
tt = [ord(i) for i in string.printable if ord(i) % 13 != 0]
tt = [13*1] + tt
tt = sorted(tt)

password = b""
for i in range(len(temp)):
password += (temp[i] * chr(tt[i])).encode()
print(password)
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)


c = b'q[\n\x05\xad\x99\x94\xfb\xc1W9\xcb`\x96\xb9|CA\xb8\xb5\xe0v\x93\xff\x85\xaa\xa7\x86\xeas#c'
iv = b'+\xd5}\xd8\xa7K\x88j\xb5\xf7\x8b\x95)n53'
print(f"counts = {[cnt for _, cnt in Counter(password2).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC, iv)
flag = cipher.decrypt(c)
print(flag)


#DEAD{y0u_Gu3ssEd_mY_p4s5w0rD}



*Password Guesser Revenge

这题现在还做不来,先放在这里,各位师傅也可以看看有没啥思路,我学会了就更新

题目:

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 collections import Counter
from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib
from Crypto.Util.Padding import pad
import math

flag = b'<redacted>'
P = 13**37
password = b'<redacted>' # password charset is string.printable
pl = list(password)
pl = sorted(pl)
assert math.prod(pl) % P == sum(pl) % P
password2 = bytes(pl)
#print(password2)
print(f"counts = {[cnt for _, cnt in Counter(password).items()]}")
cipher = AES.new(hashlib.sha256(password2).digest(), AES.MODE_CBC)
print(f"c = {cipher.encrypt(pad(flag, 16))}")
print(f"iv = {cipher.iv}")


'''
counts = [2, 4, 14, 7, 3, 2, 5, 3, 1, 3, 1, 4, 3, 3, 2, 10, 2, 6, 4, 1, 3, 4, 3, 2, 4, 3, 6, 1, 1, 4, 2, 21, 8, 8, 2, 4, 1, 9, 3, 4, 8, 3, 1, 2, 2, 5, 8, 2, 7, 2, 9, 2, 2, 6, 6, 3, 3, 9, 1, 3, 6, 6, 2, 4, 5, 3, 3, 8, 5, 1, 1, 9, 2, 8, 4, 1, 4, 9, 4, 1, 3, 4, 3, 4, 6, 4]
c = b'\xfb\x9e\xda\x81\xa6\xdf.\xc9zw\xb6t\x9e\x05\xb7\xdb\x84\xe5\x01\x97\xfb\xd2\x04 i\xa5\x13d\xfd\x89c\x0b'
iv = b'\xd4\xa6\xbc\xae\t/\xd3\x85YY\xb5\xda\xcf\xcaX\xb3'
'''

可以看出这一题中,给出的不再是password2的counter,而是password的,这就导致刚才的方法完全没法用了,因为还需要爆破一个置换,复杂度奇高无比。

我大致的思路是,由于sum也还是几万那个数量级,是爆破允许的复杂度范围内的,因此先假设他已知,就记为c。那么就只用sum的话,其实整个式子可以看作一个背包,虽然并不知道counter中每个量具体是谁的,但是可以用noisecrt的类似思路来做。

这个思路弊端也很明显:

  • noisecrt造的格太大了,并且c也要爆破,复杂度不允许
  • printable的字符值都是连续量,规约肯定有多解的
  • 根本没利用上prod

如果要利用prod,可以找到一个生成元g,然后用dlp转到指数上去做背包,此时可以避免printable的字符值都是连续量这个问题,然而也有几个缺陷:

  • 仍然要利用noisecrt,c仍然要爆破
  • 模13^37根本找不到生成元

所以不会了。