XYCTF wp

1.Division

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
import random 
print('----Welcome to my division calc----')
print('''
menu:
      [1]  Division calc
      [2]  Get flag
''')
while True:
    choose = input(': >>> ')
    if choose == '1':
        try:
            denominator = int(input('input the denominator: >>> '))
        except:
            print('INPUT NUMBERS')
            continue
        nominator = random.getrandbits(32)
        if denominator == '0':
            print('NO YOU DONT')
            continue
        else:
            print(f'{nominator}//{denominator} = {nominator//denominator}')
    elif choose == '2':
        try:
            ans = input('input the answer: >>> ')
            rand1 = random.getrandbits(11000)
            rand2 = random.getrandbits(10000)
            correct_ans = rand1 // rand2
            if correct_ans == int(ans):
                print('WOW')
                with open('flag', 'r') as f:
                    print(f'Here is your flag: {f.read()}')
            else:
                print(f'NOPE, the correct answer is {correct_ans}')
        except:
            print('INPUT NUMBERS')
    else:
        print('Invalid choice')

PRNG问题，使用了getrandbits，涉及到MT19937

破解MT19937，需要624个32位数，也就是19968bits的信息

选择1的时候，输入分母，就会给出分数，那么，我们让分母等于1，就会得到分子，

使用Pwntools工具如此重复624次，就可以得到624个32位的数字

使用Randcrack库进行破解，恢复MT19937的状态

然后再获得rand1,rand2就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random
from pwn import *
from randcrack import RandCrack 
from tqdm import *
conn = remote('47.93.96.189', 24598, timeout=10)
rc = RandCrack()
for i in trange(624):
    conn.sendlineafter(b': >>> ',b'1')
    conn.sendlineafter(b'input the denominator: >>> ',b'1')
    s = str(conn.recvline().strip())[2:]
    number = s.split("//")[0] 
    rc.submit(int(number))
rand1 =rc.predict_getrandbits(11000)
rand2 =rc.predict_getrandbits(10000)
ans = rand1//rand2
conn.sendlineafter(b': >>> ',b'2')
conn.sendlineafter(b'input the answer: >>> ',str(ans).encode())
print(conn.recvline().strip())
print(conn.recvline().strip())

FLAG：XYCTF{9764d82e-d851-43e0-9a4e-9ae840431605}

2.Complex_sigin

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


class Complex:
    def __init__(self, re, im):
        self.re = re
        self.im = im

    def __mul__(self, c):
        re_ = self.re * c.re - self.im * c.im
        im_ = self.re * c.im + self.im * c.re
        return Complex(re_, im_)

    def __eq__(self, c):
        return self.re == c.re and self.im == c.im

    def __rshift__(self, m):
        return Complex(self.re >> m, self.im >> m)

    def __lshift__(self, m):
        return Complex(self.re << m, self.im << m)

    def __str__(self):
        if self.im == 0:
            return str(self.re)
        elif self.re == 0:
            if abs(self.im) == 1:
                return f"{'-' if self.im < 0 else ''}i"
            else:
                return f"{self.im}i"
        else:
            return f"{self.re} {'+' if self.im > 0 else '-'} {abs(self.im)}i"

    def tolist(self):
        return [self.re, self.im]


def complex_pow(c, exp, n):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = result * c
            result.re = result.re % n
            result.im = result.im % n
        c = c * c
        c.re = c.re % n
        c.im = c.im % n
        exp >>= 1
    return result

bits = 128
p = getPrime(1024)
q = getPrime(1024)
n = p * q
m = Complex(getRandomRange(1, n), getRandomRange(1, n))
e = 3
c = complex_pow(m, e, n)
print(f"n = {n}")
print(f"mh = {(m >> bits << bits).tolist()}")
print(f"C = {c.tolist()}")
print(f"enc = {ChaCha20.new(key=hashlib.sha256(str(m.re + m.im).encode()).digest(), nonce=b'Pr3d1ctmyxjj').encrypt(flag)}")

这貌似是XYCTF的一贯风格，复数的RSA问题，但是这里好像关系不大

因为这里p,q,n都是实数

只是m和c，用到了复数域，但是其实理解成一个二维向量就行了

还是有 那么显然 这看上去就类似那种两组c,m的问题。

以下记c1=cre,c2=cim

而这里m损失了128位，所以属于高位泄露问题，可以用CopperSmith方法求解

简单计算一下，设 那么 考虑到高位泄露，设mh[0]=m1,mh[1]=m2 于是有方程组 相当于 sagemath中的small_root只适用于单变量的形式，所以我们考虑消元

这里可以用结式(Resultant)来消元

设 那么f(x),g(x)的结式定义为 根据定义，显然当f和g有公共根的时候，结式为0

再考虑用线性代数的语言表述，就有Sylvester 矩阵

设 那么 现在考虑方程组 先把y视为常数，那么，x的解，应该是和y有关的一个函数， 那这样根据上面定义，结式是不含有x的，这样我们就实现了对x的消元

同理也可以消掉y

然后使用small_roots调参就行了，beta=0.4出不来，调到0.5发现就可以了

Sylvester在sage中可以用sylvester_matrix调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n = ,mh= ,C=
R = PolynomialRing(Zmod(n), 'x, y')
from sage.matrix.matrix2 import Matrix
x, y = R.gens()
m1,m2 = mh[0],mh[1]
c1,c2 = C[0],C[1]
f1 = (m1+x)^3 -3*(m1+x)*(m2+y)^2 - c1
f2 = 3*(m1+x)^2*(m2+y)-(m2+y)^3 - c2
syl_x = f1.sylvester_matrix(f2,x)
syl_y = f1.sylvester_matrix(f2,y)
det1 = Matrix.determinant(syl_y)
det2 = Matrix.determinant(syl_x)
r1 = det1.univariate_polynomial().monic()
r2 = det2.univariate_polynomial().monic()
x0 = r1.small_roots(X = 2^(128), beta = 0.5,epsilon=0.02)[0]
y0 = r2.small_roots(X = 2^(128), beta = 0.5,epsilon=0.02)[0]
mr = m1+x0
mi = m2+y0
enc = b'\x9c\xc4n\x8dF\xd9\x9e\xf4\x05\x82!\xde\xfe\x012$\xd0\x8c\xaf\xfb\rEb(\x04)\xa1\xa6\xbaI2J\xd2\xb2\x898\x11\xe6x\xa9\x19\x00pn\xf6rs- \xd2\xd1\xbe\xc7\xf51.\xd4\xd2 \xe7\xc6\xca\xe5\x19\xbe'
key=hashlib.sha256(str(mr + mi).encode()).digest()
cipher = ChaCha20.new(key=key, nonce=b'Pr3d1ctmyxjj')
flag = cipher.decrypt(enc)
print(flag)

FLAG:XYCTF{Welcome_to_XYCTF_Now_let_us_together_play_Crypto_challenge}