软件系统安全赛 2026 WriteUp

打星号(*)的是赛时未解出赛后复现的。

线上赛 - rsa#

level1#

题目：

encrypt.py：

1
import random
2
from Crypto.Cipher import AES, PKCS1_OAEP
3
from Crypto.PublicKey import RSA
4
from Crypto.Util.number import bytes_to_long, long_to_bytes
5

6
def get_rand_bytes(length):
7
    return bytes([random.randrange(256) for _ in range(length)])
8

9
def encrypt(public_key, message):
10
    if isinstance(message, str):
11
        message = message.encode('utf-8')
12

13
    n = public_key.n
14
    n_bits = n.bit_length()
15

16
    if n_bits >= 2048:
17
        key_len = (n.bit_length() + 7) // 8
18
        symmetric_key = get_rand_bytes(32)
19
        msg_header = PKCS1_OAEP.new(public_key).encrypt(symmetric_key)
20
        nonce = get_rand_bytes(12)
21
        cipher = AES.new(symmetric_key, mode=AES.MODE_GCM, nonce=nonce)
22
        msg_body, tag = cipher.encrypt_and_digest(message)
23
        return msg_header + nonce + msg_body + tag
24
    else:
25
        symmetric_key = get_rand_bytes(16)
26
        key_int = bytes_to_long(symmetric_key)
27

28
        if key_int >= n:
29
            while key_int >= n:
30
                symmetric_key = get_rand_bytes(16)
31
                key_int = bytes_to_long(symmetric_key)
32

33
        encrypted_key_int = pow(key_int, public_key.e, n)
34

35
        key_len = (n.bit_length() + 7) // 8
36
        msg_header = long_to_bytes(encrypted_key_int, key_len)
37

38
        nonce = get_rand_bytes(12)
39
        cipher = AES.new(symmetric_key, mode=AES.MODE_GCM, nonce=nonce)
40
        msg_body, tag = cipher.encrypt_and_digest(message)
41

42
        return msg_header + nonce + msg_body + tag
43

44

45
if __name__ == "__main__":
46
    message = "This is my test message. It's kind of long for testing."
47
    private_key = RSA.generate(4096)
48
    public_key = private_key.publickey()
49
    ciphertext = encrypt(public_key, message)

generate-plaintext.py：

1
from Crypto.Util.number import getPrime
2
import random
3

4
class AsmuthBloomSecretSharer:
5

6
    @staticmethod
7
    def split_secret(secret, k, n):
8

9
        if isinstance(secret, str):
10
            secret_bytes = secret.encode('utf-8')
11
        else:
12
            secret_bytes = secret
13
        S = int.from_bytes(secret_bytes, 'big')
14
        secret_bits = S.bit_length()
15
        original_bits = len(secret_bytes) * 8
16

17
        d = []
18
        base_bits = max(64, (secret_bits * 2) // k)
19

20
        for i in range(n):
21
            bits = base_bits + i * 10
22
            attempts = 0
23
            while attempts < 100:
24
                p = getPrime(bits)
25
                if not d or p > d[-1]:
26
                    d.append(p)
27
                    break
28
                attempts += 1
29
            if attempts >= 100:
30
                bits += 50
31
                p = getPrime(bits)
32
                d.append(p)
33

34
        shares = []
35
        for i, di in enumerate(d):
36
            ki = S % di
37
            share_str = f"{di:x}:{ki:x}:{original_bits:x}"
38
            shares.append(share_str)
39

40
        return shares
41

42
def main():
43
    with open('message1.txt', 'r') as f:
44
        PLAINTEXTS = [f.read()] * 10
45

46
    for i in range(2, 11):
47
        with open(f'message{i}.txt', 'r') as f:
48
            msg = f.read().strip()
49

50
        k = i
51

52
        shares = AsmuthBloomSecretSharer.split_secret(msg, k, 10)
53
        for j in range(10):
54
            PLAINTEXTS[j] += shares[j] + '\n'
55

56
    for j in range(10):
57
        with open(f'plaintext-{j+1}.txt', 'w') as f:
58
            f.write(PLAINTEXTS[j])
59

60

61
if __name__ == "__main__":
62
    main()

README.md：

level2.zip 密码藏在多个message里面我把多个message通过 Asmuth-Bloom 秘密共享保存然后把Asmuth-Bloom 秘密共享的内容通过RSA加密保管起来，这下只有我才能知道message是什么了吧

题目虽然说是Asmuth-Bloom秘密共享，但是看下面代码实际上还是一组类似Shamir秘密共享的同余方程组：

1
for i, di in enumerate(d):
2
    ki = S % di
3
    share_str = f"{di:x}:{ki:x}:{original_bits:x}"
4
    shares.append(share_str)

所以关键是求解出足够多的share来crt打出message。

检查一下pem文件后会发现实际上有几个pem文件是有可利用点的：

大e，维纳攻击：
- key-6,key-12，key-17
共享素因子：
- key-1和key-2共享素因子
- key-4和key-15共享素因子
小公钥：
- key-5可以直接factordb分解出 3 个素因子（但是这个其实不重要，似乎有没有都能求解）

然后我们用恢复出的几组公钥去尝试解密ciphertext-*.bin，但是要注意实际加密是AES-GCM加密，题目仅仅只是用RSA加密了AES-GCM的密钥：

当n_bits >= 2048时，使用RSA-OAEP加密AES-GCM密钥；

当n_bits < 2048时，使用pow(key_int, e, n)加密AES-GCM密钥。

同时AES-GCM的nonce，ct,tag保存在密钥的密文后，实际结构大概如下：

对称密钥的RSA加密密文 | nonce | 对称加密的密文 | tag

最后如开头所说crt打一下就出了。

exp_level1.py：

1
from Crypto.Util.number import long_to_bytes, inverse, bytes_to_long
2
from sympy.ntheory.residue_ntheory import crt
3
from Crypto.Cipher import PKCS1_OAEP, AES
4
from Crypto.PublicKey import RSA
5
from gmpy2 import *
6

7
class ContinuedFraction():
8
    def __init__(self, numerator, denominator):
9
        self.numberlist = []
10
        self.fractionlist = []
11
        self.GenerateNumberList(numerator, denominator)
12
        self.GenerateFractionList()
13

14
    def GenerateNumberList(self, numerator, denominator):
15
        # 生成简单连分数
16
        while numerator != 1:
17
            quotient = numerator // denominator
18
            remainder = numerator % denominator
19
            self.numberlist.append(quotient)
20
            numerator = denominator
21
            denominator = remainder
22

23
    def GenerateFractionList(self):
24
        self.fractionlist.append([self.numberlist[0], 1])
25
        for i in range(1, len(self.numberlist)):
26
            numerator = self.numberlist[i]
27
            denominator = 1
28
            for j in range(i):
29
                temp = numerator
30
                numerator = denominator + numerator * self.numberlist[i - j - 1]
31
                denominator = temp
32
            self.fractionlist.append([numerator, denominator])
33

34
def WienerAttack(n, e):
35
    def recover_pq(a, b, c):
36
        delta = b ** 2 - 4 * a * c
37
        if delta < 0:
38
            return None
39
        res = iroot(delta, 2)
40
        if res[1]:
41
            return (-b + res[0]) // (2 * a), (-b - res[0]) // (2 * a)
42
        else:
43
            return None
44
    res = ContinuedFraction(e, n)
45
    for k, d in res.fractionlist:
46
        # 判断哪一个是我们所需的d
47
        if k == 0:
48
            continue
49
        elif (e * d - 1) % k == 0:
50
            phi = (e * d - 1) // k
51
            pq = recover_pq(1, n - phi + 1, n)
52
            if pq is None:
53
                continue
54
            p, q = pq
55
            if p * q == n:
56
                return int(abs(p)), int(abs(q)), int(d)
57
    return None
58

59
ns = []
60
es = []
61
for i in range(20):
62
    pem = open("key-%d.pem" % i, "rb").read()
63
    pub = RSA.importKey(pem)
64
    ns.append(pub.n)
65
    es.append(pub.e)
66
privkeys = {}
67
for i in range(len(es)):
68
    if es[i] > 1:
69
        res = WienerAttack(ns[i], es[i])
70
        if res :
71
            p, q, d = res
72
            privkeys[i] = (ns[i], es[i], d, p, q)
73
        continue
74
for i in range(len(ns)):
75
    for j in range(i + 1, len(ns)):
76
        g = gcd(ns[i], ns[j])
77
        if g != 1 and g != ns[i] and g != ns[j]:
78
            q1 = ns[i] // g
79
            q2 = ns[j] // g
80
            phi1 = (g - 1) * (q1 - 1)
81
            phi2 = (g - 1) * (q2 - 1)
82
            d1 = inverse(es[i], phi1)
83
            d2 = inverse(es[j], phi2)
84
            privkeys[i] = (ns[i], es[i], int(d1), int(g), int(q1))
85
            privkeys[j] = (ns[j], es[j], int(d2), int(g), int(q2))
86
            continue
87
# print(ns[5], es[5])
88
# 334785342698732542062444521384791292280140027616240718110407 3
89
# factordb
90
p1, q1, r1 = 13734854446830088769, 15950473204537742369, 1528159911436197621287
91
phi1 = (p1 - 1) * (q1 - 1) * (r1 - 1)
92
d1 = inverse(es[5], phi1)
93
privkeys[5] = (ns[5], es[5], int(d1), int(p1), int(q1), int(r1))
94
shares = [[] for _ in range(9)]
95
for i in range(1, 11):
96
    data = open("ciphertext-%d.bin" % i, "rb").read()
97
    for idx in privkeys:
98
        if idx == 5:
99
            n, e, d, p, q, r = privkeys[idx]
100
        else:
101
            n, e, d, p, q = privkeys[idx]
102
        key_len = (n.bit_length() + 7) // 8
103
        c, nonce, ct, tag = data[:key_len], data[key_len:key_len + 12], data[key_len + 12:-16], data[-16:]
104
        try:
105
            if n.bit_length() >= 2048:
106
                symmetric_key = RSA.construct((n, e, d, p, q))
107
                aes_key = PKCS1_OAEP.new(symmetric_key).decrypt(c)
108
            else:
109
                aes_key = long_to_bytes(pow(bytes_to_long(c), d, n), 16)
110
            msg = AES.new(aes_key, mode=AES.MODE_GCM, nonce=nonce).decrypt_and_verify(ct, tag).decode()
111
            print(msg)
112
            lines = [x.strip() for x in msg.splitlines()[1:] if x.strip()]
113
            for l, line in enumerate(lines):
114
                m, v, bits = [int(x, 16) for x in line.split(":")]
115
                shares[l].append((m, v, bits))
116
            break
117
        except:
118
            pass
119
for idx, share in enumerate(shares, 2):
120
    ms = [s[0] for s in share]
121
    vs = [s[1] for s in share]
122
    bits = share[0][2]
123
    v, m = crt(ms, vs)
124
    if bits - 1 - v.bit_length() == 0:
125
        msg = long_to_bytes(v).decode()
126
        print(f"message{idx}: {msg}")
127

128

129
"""print(msg)
130
Great job! You've successfully decoded a ciphertext!
131
10b19714652e8526c373ad6cb7bef9ddfffe67860a014dd67b7a58707ec1308a23d0cdc44fe898dcaec44ec4cf6190c3003:416e6f74686572207375636365737321204f6e65206d6f72652063697068657220626974657320746865206475737421:180
132
e8a9bdfb8087920671df5ce172afcc7f82cc2af90e40ee969:48bb7c78c2a529cf4b3cf797da50112341ec05b1416c4ea9a:118
133
1645c76083f654f0560e7768d1110cbaacfbe7:ccb2dfcef30fa1410a6326528e795dc6b530:118
134
1104d7d85d6113e242bae92212df023:52d01f1a61488ba8be18f47c14b5f1:118
135
5bc6fc4bd38968da2cb73ff087:846571bcfec9e8cd29650fd9:118
136
e12d3f54d3093bd0c558e495feda2fcfd25:71a923ddf030e0c81f95cb661128b1cbd0c:1c8
137
7e7ff7154f841b7e9bcb:1ee02ad38eb97922cf54:118
138
31ca7676db72c0d64e5:6703b5f25112f9ddfb:118
139
3147914217380010647:2bae486d39c62ce465e:120
140

141
Great job! You've successfully decoded a ciphertext!
142
54d91c1c86e7a389726c98ef6401efd90e42703d4429f2d22fbf7ee4dc395d1c88329166fa7b6a180214931a81ca5f62c245d:416e6f74686572207375636365737321204f6e65206d6f72652063697068657220626974657320746865206475737421:180
143
31427d1130ed9fb24e672fa701bbc338e3529230ce15aba80ce5:1c57d6bbcc3277d93b43301198470b765cd35d0281cf945740f4:118
144
63cc753a9d6fe68473f7cb8974c29c1fb3fefe2f:618addcf6d06b98b313b15c7df3560d0df6e3b94:118
145
67865546ea0be5bc9e317f367adff58f1:36bd34d83d7c9056279ead60e13329a1a:118
146
1b2199433b2c1a9ba14f4222570b1:3202e6acaddddc38ed823466173e:118
147
3e0c1824674da08462c191d737a2f9d3fbbe83:1cd6206436afad1dd5c8f9d187b98aa1b14d90:1c8
148
1f6abac198bf1c692268e9f:57a789432b4dc61b93c805:118
149
a74e8e100f2c651669641:1b69af9387d0f50b53bb5:118
150
9ae1b43e3f9e2061c5207:4514232fe47476bd9aa8e:120
151

152
Great job! You've successfully decoded a ciphertext!
153
6a548b4126ef3a60e3d3a1aa5432435bd087c84eba61588eb83cb98ba11c1588fdf1c6927ce4a8c206d7ec1d55080f40d6836b5187:416e6f74686572207375636365737321204f6e65206d6f72652063697068657220626974657320746865206475737421:180
154
28edaade1120cf9b5d4ff34aef574b0327556ca80bbf53a6180700e0d:1142643ca94e4a20c163da62fb61c8ead619958a86fcb90e762b6783:118
155
4253c5f87f163ae8eee4529acfcdd6f1164ad7defb033:3a9290251a82c79de0f6a81893cf5009674212f097eee:118
156
6a3c2c96d12418c9a7a4c62a083d4bffc7ea9f:4835f3840e4dd2598f9c6cffef62d729d19685:118
157
1ae58d3e0158ab9d01285903c6f37d46fd:17c2d895c9a8ff7479e43bfbe67db87232:118
158
2ed9ab3420fd2767fa81613d413d28eb5b61a1102af:1aa706a7d47fa9b4c5a01395edf6c6e962937da8903:1c8
159
10b8e1dbc0a7daec4c638b77becf:236aba3c033970e29e920296542:118
160
e41179bf004c8bdb8fc4ce8023:a989b2a6a4b09ea7f8982a8728:118
161
d7b151f23049aefb60506259ed:536dc9874fba385cd83892dbe9:120
162

163
Great job! You've successfully decoded a ciphertext!
164
1b40b80e7ce444bbc7b480c519301997652a5e1df499635cc3bf86ea0bf23278f236a3df67e534bdb345ce978ac9fe1e5e5f7387dc1e790d6f:416e6f74686572207375636365737321204f6e65206d6f72652063697068657220626974657320746865206475737421:180
165
f7d439333a96cdc59effc9a9ef34c4ad6d7eb2b6b831708770e74f208b1972c3:980f5b1871f11cfdc45f02909772c0a797983299776c79d6787055480c3e525:118
166
1bb207af31fb84ab1ce798e087255220675f31297685634fe32b1:347e9acd5697dcdfb4f51a95ff40f7a1bcc0302a139eb212c37c:118
167
145f0c52e61164b191459f19ad3d967ec8a96dd67aad59:13921acc705387d6f8d723f542994a299df3fbe6b71e94:118
168
50b3bbc4e231a4c68ca13eca9fc779e18eb1e43e1:127be0f893841a2cd9fbd9e8f89fc83b4557f994d:118
169
a27b26cdee5742bb604ff9298f1868eb1cc774cc8593930b05:35ee9ae5b018708daad10fcb718036f685600d0ed79b6d77fb:1c8
170
7ec4924224f00ebe999119595833f02e961:43c1d65c8985d14e59813b8cc2ad1ae53db:118
171
29cc947882a3c5d19ca475ca5c47143b7d:11a6d43eb78ec2b08167e6f3d24716180:118
172
3ab84a60b4a400f6033eba59efd64549f9:2d6de44ddfaa5d4e1204824ec9f9942796:120
173
"""
174

175
"""print(f"message{idx}: {msg}")
176
message2: Another success! One more cipher bites the dust!
177
message3: You're nearly there! Keep going! 3!
178
message4: You're nearly there! Keep going! 4!
179
message5: You're nearly there! Keep going! 5!
180
message6: You're nearly there! Keep going! 6!
181
message7: Congratulations! next pass is 9Zr4M1ThwVCHe4nHnmOcilJ8。
182
message8: You're nearly there! Keep going! 8!
183
message9: You're nearly there! Keep going! 9!
184
message10: You're nearly there! Keep going! 10!
185
"""

level2#

题目：

1
import gmpy2
2
import hashlib
3
from Crypto.Util.number import *
4

5
def generate_polynomial_coefficients(degree, bound=100):
6
    coefficients = []
7
    for i in range(degree + 1):
8
        coefficients.append(getRandomRange(-bound, bound))
9
    while coefficients[-1] == 0:
10
        coefficients[-1] = getRandomRange(-bound, bound)
11
    return coefficients
12

13
def evaluate_polynomial(coeffs, x, n):
14
    result = 0
15
    power = 1
16
    for i, coeff in enumerate(coeffs):
17
        result = (result + coeff * power) % n
18
        power = (power * x) % n
19
    return result
20

21
p = getPrime(512)
22
q = getPrime(512)
23
d = getPrime(180)
24

25
lam = (p-1) * (q-1) // gmpy2.gcd(p-1, q-1)
26

27
e = gmpy2.invert(d, lam)
28

29
n = p * q
30
m1 = bytes_to_long(b"Secret message: " + b"A" * 16)
31

32
poly2_coeffs = generate_polynomial_coefficients(2)
33
poly3_coeffs = generate_polynomial_coefficients(3)
34

35
m2 = evaluate_polynomial(poly2_coeffs, m1, n)
36
m3 = evaluate_polynomial(poly3_coeffs, m1, n)
37

38
c1 = pow(m1, e, n)
39
c2 = pow(m2, e, n)
40
c3 = pow(m3, e, n)
41

42
flag_hash = hashlib.sha256(str(p + q).encode()).hexdigest()
43
flag = f"next pass is {flag_hash}"
44

45
poly2_coeffs_display = poly2_coeffs.copy()
46
poly2_coeffs_display[0] = "?"
47
poly3_coeffs_display = poly3_coeffs.copy()
48
poly3_coeffs_display[0] = "?"
49

50
print("n =", n)
51
print("e =", e)
52
print("c1 =", c1)
53
print("c2 =", c2)
54
print("c3 =", c3)
55
print("poly2_coeffs =", poly2_coeffs_display)
56
print("poly3_coeffs =", poly3_coeffs_display)
57

58
# n = 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470918466007730570718648025143561656395751518428630742587023267450633824636936953524868735263666089452348466018195099471535823969365007120680546592999022195781
59
# e = 12076830539295193533033212232487568888200963123024189287629493480058638222146972496110814372883829765692623107191129306190788976704250502316265439996891764101447017190377014980293589797403095249538391534986638973035285900867548420192211241163778919028921502305790979880346050428839102874086046622833211913299
60
# c1 = 88537483899519116785221065592618063396859368769048931371104532271282451393564912999388648867349770059882231896252136530442609316120059139869000411598215669228402275014417736389191093818032356471508269901358077592526362193180661405990147957408129845474938259771860341576649904811782733150222504695142224907008
61
# c2 = 94664119872856479106437852390497826718494891787231788048637569911820802241271385500237521849783257742020074596801243551199558780516078698265978603364906102405513805258523893161481880920117078266554039648951735640682344760175446065823258414274759467738667667682764189886842676476993302026419523097311062869020
62
# c3 = 17452842791128500883484238194649202112170709841838938382334668085116735124742824096780522905501631340623564870573855325492444043679562915249332054460794149403631363005265204604824764244033832504758820981926933304283896441280291037649477532990161765794023799333588888734136298348520144818810380374971149851767
63
# poly2_coeffs = ['?', -36, -94]
64
# poly3_coeffs = ['?', -11, -20, 11]

多项式系数啊密文啊啥的都没用，就看n，e就行。私钥指数直接指明了为 180 bit，考虑维纳攻击直接打，但是e的生成有点小 trick：

1
lam = (p-1) * (q-1) // gmpy2.gcd(p-1, q-1)
2
e = gmpy2.invert(d, lam)

所以原本维纳攻击中的：

e*d=k*phi+1

要改成：

e*d*g=k*phi+g

然后实际我们搜索的连分数收敛项应该是：

\frac{e*g}{n}

其余都基本类似，然后得到phi之后利用n，phi和p，q之间的关系求解p和q就行。

exp_level2.py：

1
from gmpy2 import iroot
2
import hashlib
3

4
class ContinuedFraction():
5
    def __init__(self, numerator, denominator):
6
        self.numberlist = []
7
        self.fractionlist = []
8
        self.GenerateNumberList(numerator, denominator)
9
        self.GenerateFractionList()
10

11
    def GenerateNumberList(self, numerator, denominator):
12
        # 生成简单连分数
13
        while numerator != 1:
14
            quotient = numerator // denominator
15
            remainder = numerator % denominator
16
            self.numberlist.append(quotient)
17
            numerator = denominator
18
            denominator = remainder
19

20
    def GenerateFractionList(self):
21
        self.fractionlist.append([self.numberlist[0], 1])
22
        for i in range(1, len(self.numberlist)):
23
            numerator = self.numberlist[i]
24
            denominator = 1
25
            for j in range(i):
26
                temp = numerator
27
                numerator = denominator + numerator * self.numberlist[i - j - 1]
28
                denominator = temp
29
            self.fractionlist.append([numerator, denominator])
30

31
def recover_pq(a, b, c):
32
    delta = b ** 2 - 4 * a * c
33
    if delta < 0:
34
        return None
35
    res = iroot(delta, 2)
36
    if res[1]:
37
        return (-b + res[0]) // (2 * a), (-b - res[0]) // (2 * a)
38
    else:
39
        return None
40

41
def brute_g(n, e):
42
    for g in range(2, 100):
43
        res = ContinuedFraction(e * g, n)
44
        for k, d in res.fractionlist:
45
            # 判断哪一个是我们所需的d
46
            if k == 0:
47
                continue
48
            elif (e * d * g - g) % k == 0:
49
                phi = (e * d * g - g) // k
50
                pq = recover_pq(1, n - phi + 1, n)
51
                if pq is None:
52
                    continue
53
                p, q = pq
54
                if p * q == n:
55
                    return int(abs(p)), int(abs(q)), g
56
    return None
57

58
n = 99573363048275234764231402769464116416087010014992319221201093905687439933632430466067992037046120712199565250482197004301343341960655357944577330885470918466007730570718648025143561656395751518428630742587023267450633824636936953524868735263666089452348466018195099471535823969365007120680546592999022195781
59
e = 12076830539295193533033212232487568888200963123024189287629493480058638222146972496110814372883829765692623107191129306190788976704250502316265439996891764101447017190377014980293589797403095249538391534986638973035285900867548420192211241163778919028921502305790979880346050428839102874086046622833211913299
60
p, q, g = brute_g(n, e)
61
password = hashlib.sha256((str(p + q).encode())).hexdigest()
62
print(password)
63
# 2aa9c360df99cbb4209e4dbab5a9f9ffd86d34906e3206fecfdabf0bb7aeb5ac

level3#

题目：

1
from Crypto.Util.number import getPrime, bytes_to_long
2

3
p = getPrime(1536)
4
q = getPrime(1536)
5
n = p * q
6
e = 65537
7

8
flag = b"dart{**************}"
9
c = pow(bytes_to_long(flag), e, n)
10

11
CONST1 = 0xDEADBEEFCAFEBABE123456789ABCDEFFEDCBA9876543210
12
CONST2 = 0xCAFEBABEDEADBEEF123456789ABCDEF0123456789ABCDEF
13
CONST3 = 0x123456789ABCDEFFEDCBA9876543210FEDCBA987654321
14
MOD128 = 2 ** 128
15
MASK64 = (1 << 64) - 1
16
MASK128 = (1 << 128) - 1
17

18
leak = ( (p * CONST1) ^ (q * CONST2) ^ ((p & q) << 64) ^ ((p | q) << 48) ^ ((p ^ q) * CONST3) ) + ((p + q) % MOD128) ^ ((p * q) & MASK64)
19

20
print(f"n = {n}")
21
print(f"e = {e}")
22
print(f"c = {c}")
23
print(f"leak = {leak}")
24

25
# n = 3656543170780671302102369785821318948521533232259598029746397061108006818468053676291634112787611176554924353628972482471754519193717232313848847744522215592281921147297898892307445674335249953174498025904493855530892785669281622228067328855550222457290704991186404511294392428626901071668540517391132556632888864694653334853557764027749481199416901881332307660966462957016488884047047046202519520508102461663246328437930895234074776654459967857843207320530170144023056782205928948050519919825477562514594449069964098794322005156920839848615481717184615581471471105167310877784107653826948801838083937060929103306952084786982834242119877046219260840966142997264676014575104231122349770882974818427591538551719990220347345614399639643257685591321500648437402084919467346049683842042993975696447711080289559063959271045082506968532103445241637971734173037224394103944153692310048043693502870706225319787902231218954548412018259
26
# e = 65537
27
# c = 1757914668604154089701710446907445787512346500378259224658947923217272944211214757488735053484213917067698715050010452193463598710989123020815295814709518742755820383364097695929549366414223421242599840755441311771835982431439073932340356341636346882464058493459455091691653077847776771631560498930589569988646613218910231153610031749287171649152922929066828605655570431656426074237261255561129432889318700234884857353891402733791836155496084825067878059001723617690872912359471109888664801793079193144489323455596341708697911158942505611709946252101670450796550313079139560281843612045681545992626944803230832776794454353639122595107671267859292222861367326121435154862607517890329925621367992667728899878422037182817860641530146234730196633237339901726508906733897556146751503097127672718192958642776389691940671356367304182825433592577899881444815062581163386947075887218537802483045756886019426749855723715192981635971943
28
# leak = 153338022210585970687495444409227961261783749570114993931231317427634321118309600575903662678286698071962304436931371977179197266063447616304477462206528342008151264611040982873859583628234755013757003082382562012219175070957822154944231126228403341047477686652371523951028071221719503095646413530842908952071610518530005967880068526701564472237686095043481296201543161701644160151712649014052002012116829110394811586873559266763339069172495704922906651491247001057095314718709634937187619890550086009706737712515532076

剪枝就行，给的题目约束很强，甚至没有多余的分支需要剪其实。。

通过如下两个等式从低位往高位搜索就行：

p*q\equiv n\pmod{2^k}\\ leak(p,q)\equiv leak\pmod{2^k}

exp_level3.py：

1
from Crypto.Util.number import long_to_bytes, inverse
2

3
def compute_leak(p: int, q: int) -> int:
4
    return ( (p * CONST1) ^ (q * CONST2) ^ ((p & q) << 64) ^ ((p | q) << 48) ^ ((p ^ q) * CONST3)) + ((p + q) % MOD128) ^ ((p * q) & MASK64)
5

6
n = 3656543170780671302102369785821318948521533232259598029746397061108006818468053676291634112787611176554924353628972482471754519193717232313848847744522215592281921147297898892307445674335249953174498025904493855530892785669281622228067328855550222457290704991186404511294392428626901071668540517391132556632888864694653334853557764027749481199416901881332307660966462957016488884047047046202519520508102461663246328437930895234074776654459967857843207320530170144023056782205928948050519919825477562514594449069964098794322005156920839848615481717184615581471471105167310877784107653826948801838083937060929103306952084786982834242119877046219260840966142997264676014575104231122349770882974818427591538551719990220347345614399639643257685591321500648437402084919467346049683842042993975696447711080289559063959271045082506968532103445241637971734173037224394103944153692310048043693502870706225319787902231218954548412018259
7
e = 65537
8
c = 1757914668604154089701710446907445787512346500378259224658947923217272944211214757488735053484213917067698715050010452193463598710989123020815295814709518742755820383364097695929549366414223421242599840755441311771835982431439073932340356341636346882464058493459455091691653077847776771631560498930589569988646613218910231153610031749287171649152922929066828605655570431656426074237261255561129432889318700234884857353891402733791836155496084825067878059001723617690872912359471109888664801793079193144489323455596341708697911158942505611709946252101670450796550313079139560281843612045681545992626944803230832776794454353639122595107671267859292222861367326121435154862607517890329925621367992667728899878422037182817860641530146234730196633237339901726508906733897556146751503097127672718192958642776389691940671356367304182825433592577899881444815062581163386947075887218537802483045756886019426749855723715192981635971943
9
leak = 153338022210585970687495444409227961261783749570114993931231317427634321118309600575903662678286698071962304436931371977179197266063447616304477462206528342008151264611040982873859583628234755013757003082382562012219175070957822154944231126228403341047477686652371523951028071221719503095646413530842908952071610518530005967880068526701564472237686095043481296201543161701644160151712649014052002012116829110394811586873559266763339069172495704922906651491247001057095314718709634937187619890550086009706737712515532076
10

11
CONST1 = 0xDEADBEEFCAFEBABE123456789ABCDEFFEDCBA9876543210
12
CONST2 = 0xCAFEBABEDEADBEEF123456789ABCDEF0123456789ABCDEF
13
CONST3 = 0x123456789ABCDEFFEDCBA9876543210FEDCBA987654321
14
MOD128 = 2 ** 128
15
MASK64 = (1 << 64) - 1
16
MASK128 = (1 << 128) - 1
17
p, q = 1, 1
18
for k in range(2, 1537):
19
    mask = (1 << k) - 1
20
    nl, ll = n & mask, leak & mask
21
    candidates = []
22
    for pbit in (0, 1):
23
        for qbit in (0, 1):
24
            pp = p + 2 ** (k - 1) * pbit
25
            qq = q + 2 ** (k - 1) * qbit
26
            if (pp * qq) & mask != nl:
27
                continue
28
            if compute_leak(pp, qq) & mask != ll:
29
                continue
30
            candidates.append((pp, qq))
31
    if len(candidates) != 1:
32
        print(k, candidates[:4])
33
    p, q = candidates[0]
34
assert p * q == n
35
phi = (p - 1) * (q - 1)
36
d = inverse(e, phi)
37
m = pow(c, d, n)
38
print(long_to_bytes(m).decode())
39
# dart{379c9308-e9a8-45a1-bd55-45bbd822e86d}

线下赛 - crypto(*)#

task.py：

1
import os
2
import hashlib
3
from Crypto.Util.number import getPrime, isPrime, bytes_to_long, long_to_bytes, sieve_base
4
from Crypto.Cipher import AES
5
from Crypto.Util.Padding import pad
6
from sage.all import *
7
import random
8
import json
9
from Secret import flag
10

11
p_ec = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
12
K_field = GF(p_ec)
13
E = EllipticCurve(K_field, [0, 4])
14
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
15

16
n1 = 859267
17
n2 = 52437899
18
n3 = 28355811
19

20
def generate_base_points():
21
    while True:
22
        G1 = E.random_point()
23
        G2 = E.random_point()
24
        G3 = E.random_point()
25
        if G1.order() == o and G2.order() == o and G3.order() == o:
26
            P1 = (o // n1) * G1
27
            P2 = (o // n2) * G2
28
            P3 = (o // n3) * G3
29
            return G1, G2, G3, P1, P2, P3
30

31
G1, G2, G3, P1, P2, P3 = generate_base_points()
32

33
while True:
34
    a0 = random.randrange(0, o)
35
    b0 = random.randrange(0, o)
36
    c0 = random.randrange(1, o)
37
    K_point = a0 * P1 + b0 * P2 + c0 * G3
38
    if K_point != E(0):
39
        break
40

41
def encrypt_bytes_with_weil(data_bytes, K_point, P1, P2, P3, G1, G2, G3, o):
42
    bits = bin(bytes_to_long(data_bytes))[2:].zfill(len(data_bytes) * 8)
43

44
    cs = [K_point.xy()]
45
    for bit in bits:
46
        a = random.randrange(0, o)
47
        b = random.randrange(0, o)
48
        c = random.randrange(0, o)
49
        if bit == '0':
50
            C = a * P1 + b * P2 + c * G3
51
        else:
52
            C = a * P1 + b * G2 + c * P3
53
        cs.append(C.xy())
54
    return cs
55

56
SBOX = [
57
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
58
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
59
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
60
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
61
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
62
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
63
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
64
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
65
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
66
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
67
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
68
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
69
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
70
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
71
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
72
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
73
]
74

75
RCON = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]
76

77
def key_expansion(key):
78
    w = [bytes_to_long(key[i:i+4]) for i in range(0, 16, 4)]
79
    for i in range(4, 44):
80
        temp = w[i-1]
81
        if i % 4 == 0:
82
            temp = ((temp << 8) & 0xffffffff) | (temp >> 24)
83
            temp = (SBOX[temp >> 24] << 24) | (SBOX[(temp >> 16) & 0xff] << 16) | \
84
                   (SBOX[(temp >> 8) & 0xff] << 8) | SBOX[temp & 0xff]
85
            temp ^= (RCON[i // 4] << 24)
86
        w.append(w[i-4] ^ temp)
87
    return b"".join([long_to_bytes(x, 4) for x in w[40:]])
88

89
def generate_prime(bits):
90
    while True:
91
        p_sub = 2
92
        for prime in sieve_base:
93
            p_sub *= prime
94
            if p_sub.bit_length() > bits - 2:
95
                break
96

97
        for k in range(2, 10000, 2):
98
            p = p_sub * k + 1
99
            if isPrime(p):
100
                return p
101

102
p = generate_prime(1024)
103
q = getPrime(1024)
104
n = p * q
105
e = 65537
106

107
random_key1 = os.urandom(16)
108
random_key2 = os.urandom(16)
109

110
key = bytes([a ^ b for a, b in zip(random_key1, random_key2)])
111

112
cs = encrypt_bytes_with_weil(random_key1, K_point, P1, P2, P3, G1, G2, G3, o)
113

114
last_key = key_expansion(random_key2)
115
c_rsa = pow(bytes_to_long(last_key), e, n)
116

117
iv = os.urandom(16)
118
cipher = AES.new(key, AES.MODE_CBC, iv)
119
c_aes = cipher.encrypt(pad(flag, 16))
120

121
print(f"n = {n}")
122
print(f"c_rsa = {c_rsa}")
123
print(f"iv = {iv.hex()}")
124
print(f"c_aes = {c_aes.hex()}")
125

126
print(f"p_ec = {p_ec}")
127
print(f"o = {o}")
128
print(f"n1 = {n1}")
129
print(f"n2 = {n2}")
130
print(f"n3 = {n3}")
131
print(f"cs_length = {len(cs)}")
132

133
cs_str = str(cs)
134
with open("cs_data.txt", "w") as f:
135
    f.write(cs_str)
136

137
# n = 146850411704422049184055831603438103611273998641574344539157187822470117111192441822840285426092531590494443560512774359361222760041102810475251420012967345253310508075313669874255385146463705376624174846090693327299696444447299357816218235953977513356010849073754388380066627173946423160005852531719468703482395149740126750238839756212987902673933340616278193564739329403982414297244500133278306869727068946995267433133315170300944475227726688168414050083748281907770360887506262390792675100088131056162503296688058603163204412988395608692569420997582022237320094219469054284986095923802700263866210516176584677461256983
138
# c_rsa = 74231514119138617803996275719518567011575633515104945151215552023045037756701780526260789061976755658325418843994780806559238907177047055473949449639134295693377584046710895240662122821981567353777690859611002522560646785856006740342985854904695610475038620729237499009395199224056982292128775251998161390549676312977578250989501803335573269265794244598105444939510585700441331525728789380327207222547771575094896363209815599271832390676431405381466011192298785646752634683579526124097356770748495318358864466168591744819079230251579490595399596992924889730056630225282899769366237095274859047801524294366610885266499330
139
# iv = 9ee38737a1bdaaa5f665b4d91988e8d6
140
# c_aes = 8533aeeb80395a4dc344ca9e4fe036463e6563b3acc3ad85087c166a4e497c516b8cda153dbe3ab2d59999d61195b16e
141
# p_ec = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
142
# o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
143
# n1 = 859267
144
# n2 = 52437899
145
# n3 = 28355811
146
# cs_length = 129

题目整体可以分为四部分：ECC编码random_key1，密钥扩展random_key2得到last_key，RSA加密last_key，以random_key1 ^ random_key2为密钥的AES-CBC加密。

一步步拆解来做，首先从简单的开始叭，先把random_key2恢复出来。

RSA#

仔细观察generate_prime函数，我们会发现p并非随机素数，而是形如：

p=p_{sub}\cdot k+1

其中p_sub是素数集合从小到大按顺序累乘得到的满足p_sub.bit_length() > bits - 2的乘积，而k也是在2 ~ 10000的偶数中顺序枚举的数，也就是说，这个函数生成的素数只会随着bits参数的改变而改变，我们只需要在本地再次运行generate_prime(1024)就能找到p。

key_expansion#

RSA解出last_key后，我们要根据last_key反推出原始的key，AES-128 的key schedule关系为：

w_i=w_{i-4}\oplus f(w_{i-1})

因此反推时：

w_{i-4}=w_i\oplus f(w_{i-1})

ECC#

根据函数名encrypt_bytes_with_weil，我们可以知道这题应该是用weil pairing来做的。题目定义了一条曲线，并生成了三个阶为o的点G1，G2，G3，并再构造：

1
P1 = (o // n1) * G1
2
P2 = (o // n2) * G2
3
P3 = (o // n3) * G3

也就是说P1是n1阶点，P2是n2阶点，P3是n3阶点。之后随机生成一个K_point = a0 * P1 + b0 * P2 + c0 * G3。并按照random_key1的bit进行加密：

1
if bit == '0':
2
    C = a * P1 + b * P2 + c * G3
3
else:
4
    C = a * P1 + b * G2 + c * P3

因此区别主要在P2/G2和P3/G3的结构上。

我们观察参数n1 = 859267, n3 = 28355811，可以发现n3 = 33 * n1。我们可以令h = o // 33，然后将K_point和密文点都乘上h。

对于K_point：

K=a_0P1+b_0P2+c_0G3

因为P1、P2的阶都会被h消掉，所以：

hK=h(c_0G3)

也就是只剩下G3方向。

对于bit = 0，同理有：

hC=h(cG3)

因此hC和hK位于同一个循环子群中，weil 配对的结果为 1。

而对于bit = 1，乘上h后会有：

hC=h(bG2)+h(cP3)

一般会保留G2方向的分量，因此和hK的配对值通常不为 1。

所以我们可以先用一轮 33 阶 Weil Pairing 筛出一部分bit = 1的情况，此时剩下的部分不能直接判成bit = 0，因为有一小部分bit = 1的数据中，我们生成的系数h有可能把G2方向消掉，也出现配对值为 1 的情况，所以先标记为?。

接下来我们可以找一个确定bit = 1的点作为参考点，然后令g = o // n2，对于bit = 1的情况有：

C=aP1+bG2+cP3

因为gP1 = 0，gP3 = 0，所以：

gC=g(bG2)

即bit = 1的点乘上g后会落在G2方向的n2阶子群中，然后取第一轮确定bit = 1的一个点为参考点，对于每个?点计算weil pairing值，若结果为 1，说明该点和参考点同处于G2方向的循环子群中，判为 1，否则判为 0。这样就可以恢复random_key1的bit流了。

AES-CBC#

拿到random_key1和random_key2后异或得到key，iv已知，直接AES-CBC求解就行。

exp.py：

1
# SageMath 10.7
2
from Crypto.Util.number import isPrime, bytes_to_long, long_to_bytes, sieve_base, inverse
3
from Crypto.Util.Padding import unpad
4
from Crypto.Cipher import AES
5
from ast import literal_eval
6

7
SBOX = [
8
    0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
9
    0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
10
    0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
11
    0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
12
    0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
13
    0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
14
    0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
15
    0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
16
    0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
17
    0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
18
    0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
19
    0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
20
    0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
21
    0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
22
    0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
23
    0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
24
]
25

26
RCON = [0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]
27

28
def generate_prime(bits):
29
    while True:
30
        p_sub = 2
31
        for prime in sieve_base:
32
            p_sub *= prime
33
            if p_sub.bit_length() > bits - 2:
34
                break
35

36
        for k in range(2, 10000, 2):
37
            p = p_sub * k + 1
38
            if isPrime(p):
39
                return p
40

41
n = 146850411704422049184055831603438103611273998641574344539157187822470117111192441822840285426092531590494443560512774359361222760041102810475251420012967345253310508075313669874255385146463705376624174846090693327299696444447299357816218235953977513356010849073754388380066627173946423160005852531719468703482395149740126750238839756212987902673933340616278193564739329403982414297244500133278306869727068946995267433133315170300944475227726688168414050083748281907770360887506262390792675100088131056162503296688058603163204412988395608692569420997582022237320094219469054284986095923802700263866210516176584677461256983
42
c_rsa = 74231514119138617803996275719518567011575633515104945151215552023045037756701780526260789061976755658325418843994780806559238907177047055473949449639134295693377584046710895240662122821981567353777690859611002522560646785856006740342985854904695610475038620729237499009395199224056982292128775251998161390549676312977578250989501803335573269265794244598105444939510585700441331525728789380327207222547771575094896363209815599271832390676431405381466011192298785646752634683579526124097356770748495318358864466168591744819079230251579490595399596992924889730056630225282899769366237095274859047801524294366610885266499330
43
iv = bytes.fromhex("9ee38737a1bdaaa5f665b4d91988e8d6")
44
c_aes = bytes.fromhex("8533aeeb80395a4dc344ca9e4fe036463e6563b3acc3ad85087c166a4e497c516b8cda153dbe3ab2d59999d61195b16e")
45
p_ec = 4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787
46
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
47
n1 = 859267
48
n2 = 52437899
49
n3 = 28355811
50
cs_length = 129
51
e = 65537
52

53
p = generate_prime(1024)
54
q = n // p
55
assert p * q == n
56
phi = (p - 1) * (q - 1)
57
d = inverse(e, phi)
58
last_key = long_to_bytes(pow(c_rsa, d, n))
59
print(last_key)
60
# b'x\x0b\xed\xbd\x0b\xea\x8e\xec|\xd42g\x19U\x00\x06'
61

62
w = [0] * 40 + [bytes_to_long(last_key[i:i + 4]) for i in range(0, 16, 4)]
63
for i in range(43, 3, -1):
64
    temp = w[i - 1]
65
    if i % 4 == 0:
66
        temp = ((temp << 8) & 0xffffffff) | (temp >> 24)
67
        temp = (SBOX[temp >> 24] << 24) | (SBOX[(temp >> 16) & 0xff] << 16) | \
68
               (SBOX[(temp >> 8) & 0xff] << 8) | SBOX[temp & 0xff]
69
        temp ^^= (RCON[i // 4] << 24)
70
    temp ^^= w[i]
71
    w[i - 4] = temp
72
random_key2 = b"".join([long_to_bytes(x, 4) for x in w[:4]])
73
print(random_key2)
74
# b'Q\xde\xd1\x08\x8b\xe2\xbf\xd8"\x91\xa0JB\xf6\xcd2'
75

76
p_ec = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
77
o = 793479390729215512516507951283169066088130679960393952059283337873017453583023682367384822284289
78
n2 = 52437899
79
K_field = GF(p_ec)
80
E = EllipticCurve(K_field, [0, 4])
81
cs = literal_eval(open("cs_data.txt", "r").read())
82
K = E(cs[0])
83
pts = [E(xy) for xy in cs[1:]]
84
# 第一轮：33-torsion 上直接判
85
h33 = o // 33
86
K33 = h33 * K
87
tags = []
88
sure_one = None
89
for C in pts:
90
    z = (h33 * C).weil_pairing(K33, 33)
91
    if z != 1:
92
        tags.append('1')
93
        if sure_one is None:
94
            sure_one = C
95
    else:
96
        tags.append('?')
97
# 第二轮：把 ? 补掉
98
g = o // n2
99
ref = g * sure_one
100
bits = []
101
for t, C in zip(tags, pts):
102
    if t == '1':
103
        bits.append('1')
104
    else:
105
        z = (g * C).weil_pairing(ref, n2)
106
        bits.append('1' if z == 1 else '0')
107
bitstr = ''.join(bits)
108
random_key1 = long_to_bytes(int(bitstr, 2), 16)
109
print(random_key1)
110
# b'\x8d\xf5c\xa8#\xb3\xad\xd6\xe0\xa4\xda1\xf2U^\xbe'
111

112
key = bytes([a ^^ b for a, b in zip(random_key1, random_key2)])
113
cipher = AES.new(key, AES.MODE_CBC, iv)
114
flag = unpad(cipher.decrypt(c_aes), 16).decode()
115
print(flag)
116
# dart{0d7c228a-0c75-4914-a272-ca2c96cd5ca7}

持续更新中~

线上赛 - rsa#

level1#

level2#

level3#

线下赛 - crypto(*)#

RSA#

key_expansion#

ECC#

AES-CBC#