2022-08-12   15 m   2.3 k0 visits

corCTF2022 部分Crypto wp复现

准备抽空把corCTF2022里几个低解Crypto题目复现学习一下，先能码多少是多少吧。

[corCTF 2022] threetreasures

题目源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from sage.all import *
from Crypto.Util.number import bytes_to_long, getPrime
from random import getrandbits
from secret import flag, p, x, y

def random_pad(n, length):
    return (n << (length - n.bit_length())) + getrandbits(length - n.bit_length())

flag = bytes_to_long(flag)
fbits = flag.bit_length()
piece_bits = fbits // 3
a, b, c = flag >> (2 * piece_bits), (flag >> piece_bits) % 2**piece_bits, flag % 2**piece_bits
print(f'flag bits: {fbits}')
assert p.bit_length() == 512
q = getPrime(512)
n = p * q
ct = pow(random_pad(c, 512), 65537, n)
E = EllipticCurve(GF(p), [a, b])
G = E(x, y)
assert G * 3 == E(0, 1, 0)
print(f"n = {n}")
print(f"ct = {ct}")
print(f"G = {G}")

题目中将375bits的flag分为125bits的a,b,c。其中c使用RSA进行加密，a,b用作ECC的构造参数，且RSA与ECC共用参数p。

题目给出了一个椭圆曲线上阶为3的点G，即：.稍加变形有：,因此有.根据倍乘公式, 即可得到, 这里a的高位是已知的（flag格式为‘corctf{’），可以直接用coppersmith攻击解出a。然后利用gcd可以得到模数p。接着根据可以得到b。最后由于因子p已经算出，解RSA即可还原出c。

解题脚本如下：

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

flag_bits = 375
n = 97915144495462666300795364589570761584322186881492143950078938328867290046424857019504657598883431857075772605985768551863478086544857915637724181292135280539943713583281151707224031808445390796342632369109562433275679473233398168787639940620683354458292117457239552762694657810883738834935391913698852811737
ct = 20363336204536918055183609604474634074539942561101208682977506918349108499764147141944713060658857301108876346227077713201766486360148051069618774935469969057808945271860025712869868421279488925632657486125211168314387620225601572070169746014988350688548088791906161773656057212229972967244998930356157725393
Gx,Gy = (3115938227771961657567351113281194074601897467086373590156577019504528350118731801249444974253028485083440228959842232653488953448859690520619223338133881 , 2665631524518629436093690344927156713668794128141943350227439039472817541262750706395352700109556004195261826476428128993836186741129487842876154876730189)
e=65537

pref=bytes_to_long(b'corctf{')
ahbits=pref.bit_length()
kbits=125-ahbits
print(kbits)
ah=pref<<kbits
R.<al>=PolynomialRing(Zmod(n))
f=(3*Gx^2+ah+al)^2-12*Gx*Gy^2
root=int(f.small_roots(X=2^kbits,beta=0.4)[0])
a=ah+root
G0=(3*Gx^2+a)^2-12*Gx*Gy^2
p=gcd(G0,n)
assert isPrime(p)
b=int((Gy^2-Gx^3-a*Gx)%p)
q=n//p
d=inverse(e,(p-1)*(q-1))
c=int(pow(ct,d,n)>>(512-125))
flag=(a<<250)+(b<<125)+c
print(long_to_bytes(flag))
#b'corctf{you_have_conquered_the_order_of_three!!}'

[corCTF 2022] corrupted-curves & corrupted-curves+

一道ecc+lattice的题目，感觉质量蛮好的，看了两天终于差不多了，感觉格这一块儿还是不熟，重新温习相关知识花了好长时间。

corrupted-curves+题目源码：

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
#!/usr/local/bin/python
from secrets import randbits
from Crypto.Util.number import getPrime
from random import randrange

def square_root(a, p):
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:
        return 0
    elif p == 2:
        return 0
    elif p % 4 == 3:
        return pow(a, (p + 1) // 4, p)
    s = p - 1
    e = 0
    while s % 2 == 0:
        s //= 2
        e += 1
    n = 2
    while legendre_symbol(n, p) != -1:
        n += 1
    x = pow(a, (s + 1) // 2, p)
    b = pow(a, s, p)
    g = pow(n, s, p)
    r = e
    while True:
        t = b
        m = 0
        for m in range(r):
            if t == 1:
                break
            t = pow(t, 2, p)
        if m == 0:
            return x
        gs = pow(g, 2 ** (r - m - 1), p)
        g = (gs * gs) % p
        x = (x * gs) % p
        b = (b * g) % p
        r = m

def legendre_symbol(a, p):
    ls = pow(a, (p - 1) // 2, p)
    return -1 if ls == p - 1 else ls

class EllipticCurve:
    
    def __init__(self, p, a, b):
        self.a = a
        self.b = b
        self.p = p
        if not self.check_curve():
            raise Exception("Not an elliptic curve!")
        
    def check_curve(self):
        discrim = -16 * (4*pow(self.a, 3) + 27*pow(self.b, 2))
        if discrim % self.p:
            return 1
        return 0
    
    def lift_x(self, px):
        y2 = (pow(px, 3) + self.a*px + self.b) % self.p
        py = square_root(y2, self.p)
        if py == 0:
            raise Exception("No point on elliptic curve.")
        return py

with open("flag.txt", "rb") as f:
    flag = f.read()
    flag = int.from_bytes(flag, 'big')

print("Generating parameters...")
while True:
    p = getPrime(512)
    a, b = randbits(384), randbits(384)
    try:
        E = EllipticCurve(p, a, b)
        fy = E.lift_x(flag)
        print(f"p = {p}")
        print(f"flag y = {fy}")
        break
    except:
        continue
checked = set()
count = 0
while count < 2022:
    x = randrange(2, p)
    if int(x) in checked or x < 2**384 or abs(x - p) < 2**384:
        print(">:(")
        continue
    try:
        e = randbits(48)
        print(f"e = {e}")
        E = EllipticCurve(p, a^e, b^e)
        py = E.lift_x(x)
        checked.add(x)
        print(f"x = {x}")
        print(f"y = {py}")
        count += 1
    except:
        print(":(")
    more = input("more> ")
    if more.strip() == "no":
        break
print("bye!")

corrupted-curves的区别仅在于x可选择输入，e为64位。两个题版本之间没有太多改变，因此只记录corrupted-curves+的解法。

题目定义了椭圆曲线的实现，已知p和flag_y，并且点在椭圆曲线上。然后给了一个oracle，可以得到椭圆曲线上的随机点，e是给出的48位随机值。简单分析可以知道，题目的首要目标是利用oracle来求出a和b。

首先得到oracle生成的两个点： 由于和e的异或运算只影响a,b的低48位，为了简便表示，记： 且令： 则有： 两式相减消去b，并将a分解为高位(336bits)和低位(48bits)： 于是我们可以根据等式： 构造格矩阵： 令

可以证明向量是在格M上的，因为。并且，向量r的长度非常短，趋近于1。因此，我们对格矩阵M进行LLL规约求解SVP问题可以得到短向量r，从而得到a的高位。

除此之外，我们还可以从向量r中得到，由于（异或运算只影响低位），我们可以求出，从而得到完整的a的值。

接着很容易得到b的值： 拿到a,b之后利用椭圆曲线方程求flag_y对应的根即可。

解题脚本solve.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
from pwn import *
from Crypto.Util.number import *

sh = remote('be.ax',31132)
context.log_level='debug'
l64 = lambda      :u64(sh.recvuntil("\x7f")[-6:].ljust(8,"\x00"))
l32 = lambda      :u32(sh.recvuntil("\xf7")[-4:].ljust(4,"\x00"))
sla = lambda a,b  :sh.sendlineafter(str(a),str(b))
sa  = lambda a,b  :sh.sendafter(str(a),str(b))
lg  = lambda name,data : sh.success(name + ": 0x%x" % data)
se  = lambda payload: sh.send(payload)
rl  = lambda      : sh.recvline()
rv  = lambda n    : sh.recv(n)
sl  = lambda payload: sh.sendline(payload)
ru  = lambda a     :sh.recvuntil(str(a))
rud  = lambda a     :sh.recvuntil(str(a),drop=True)

def getpoints():
	points=[]
	cnt=0
	while cnt<2: 
		line=rl().decode()
		if '>:(' not in line:
			print(line)
			e=int(line.split('e = ')[1])
			line=rl().decode()
			if ':(' not in line:
				x=int(line.split('x = ')[1])
				ru('y = ')
				y=int(rl())
				points.append((e,x,y))
				cnt+=1
		sla('more> ','yes')
	sla('more> ','no')
	sh.close()
	return points	

ru('p = ')
p=int(rl())
ru('flag y = ')
flagy=int(rl())
points=getpoints()
e1,x1,y1=points[0]
e2,x2,y2=points[1]
m1=(y1^2-x1^3)%p
m2=(y2^2-x2^3)%p

m=Matrix(QQ,6,6)
m.set_column(0,[p,2^48*(x1-x2)%p,-x1,x2,1,(m2-m1)%p])
m[1,1]=2^-336
for i in range(2,5):
	m[i,i]=2^-48
m[5,5]=1
res=m.LLL()
#print(res)
for row in res:
	if row[0]==0 and row[-1]==1:
		au=Integer(row[1]*2^384)
		al=Integer(-row[2]*2^48)^^e1
		a=au+al
		b=((m1-(a^^e1)*x1)%p)^^e1
		R.<X>=PolynomialRing(Zmod(p))
		f=X^3+a*X+b-flagy^2
		roots=f.roots()
		for root in roots:
			print(long_to_bytes(int(root[0])))

corrupted-curves解题脚本类似，稍微修改一下交互函数和位数即可。

[corCTF 2022] rlfsr

题目源码：

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 secrets import randbits
from random import shuffle
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

class LFSR:
    def __init__(self, key, taps):
        self.key = key
        self.taps = taps
        self.state = list(map(int, list("{:0128b}".format(key))))
    
    def _clock(self):
        ob = self.state[0]
        self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) % 2]
        return ob

key = randbits(128)
l = LFSR(key, [1, 2, 7, 3, 12, 73])
out = []

for i in range(118):
    bits = [l._clock() for _ in range(128)]
    shuffle(bits)
    out += bits

print(hex(sum([bit*2**i for i, bit in enumerate(out)])))

flag = open("flag.txt", "rb").read()
iv = randbits(128).to_bytes(16, 'big')
aeskey = sha256(key.to_bytes(16, 'big')).digest()[:32]
print((iv + AES.new(aeskey, AES.MODE_CBC, iv=iv).encrypt(pad(flag, 16))).hex())

一个经典的lfsr，只不过每128位加了一个shuffle。大致思路是考虑用sum来消除shuffle的影响（因为shuffle前后的求和是不变的），此外题目提供了118组128bits输出，因此可以在上构建118种与key相关的线性关系然后用groebner_basis求解，剩余10bits可以直接爆破。

直接上解题脚本solve.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
from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from tqdm import tqdm

class LFSR:
    def __init__(self, key, taps):
        self.key = key
        self.taps = taps
        self.state = key
    
    def _clock(self):
        ob = self.state[0]
        self.state = self.state[1:] + [sum([self.state[t] for t in self.taps]) ]
        return ob

lines=open('output.txt','r').readlines()
out=list(map(int,bin(int(lines[0],16))[2:].zfill(118*128)))[::-1]
out_parts=[ out[i:i+128] for i in range(0,len(out),128)]
ct=bytes.fromhex(lines[1])
iv = ct[:16]
c = ct[16:]

R=PolynomialRing(GF(2),['x%d'%i for i in range(128)])
key=list(R.gens())
l = LFSR(key, [1, 2, 7, 3, 12, 73])

I=[]
for i in range(118):
    bits = [l._clock() for _ in range(128)]
    I.append(sum(bits)-sum(out_parts[i])%2)

for i in tqdm(range(2^11)):
    guess=list(map(int,bin(int(i))[2:].zfill(11)))
    guessI=[key[i]-guess[i] for i in range(11)]
    res=Ideal(I+guessI).groebner_basis()
    if len(res)!=1:
        k=int(''.join([ str(res[i].constant_coefficient()) for i in range(len(res))]),2)
        aeskey = sha256(k.to_bytes(16, 'big')).digest()[:32]
        cipher=AES.new(aeskey,AES.MODE_CBC,iv)
        m=cipher.decrypt(c)
        if b'corctf{' in m:
            print(m)
            exit(0)
#corctf{m4yb3_w3_sh0uld_ju5t_cut_hum4n5_0ut_0f_th1s_c0mpl3t3ly_1f_th3y_d3c1d3_t0_f4k3_shuffl3_0r_s0m3th1ng}

这里爆破时是而不是，用会爆不出来，很奇怪。我想可能是因为要排除掉第一个128bits块的影响。

corCTF2022 部分Crypto wp复现

https://litao6666.github.io/202208/77a08f09.html

Author

zealot

Posted on

2022-08-12

Updated on

2022-08-27

Licensed under

Catalogue

×