Hkcert2024

Zsm included in CTF

views 2025-02-24 4130 words 9 minutes views

Contents

前言

距离初赛过了好久好久，复现一直没咋搞，nss上有环境，最近复现一下，主要是那几个lcg和rsa

题目

Almost DSA

task

 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


import os
from Crypto.Util.number import getPrime as get_prime
from Crypto.Util.number import isPrime as is_prime
import secrets
import hashlib

# Computes the inverse of a mod prime p
def inverse(a, p):
    return pow(a, p-2, p)

def hash(m):
    h = hashlib.sha256(m).digest()
    return int.from_bytes(h, 'big')

def generate_parameters():
    # FIPS 186-4 specifies that p and q can be of (2048, 256) bits
    while True:
        q = get_prime(256)
        r = secrets.randbits(2048-256)
        p = r*q + 1
        if p.bit_length() != 2048: continue
        if not is_prime(p): continue
        break
    
    h = 1
    while True:
        h += 1
        g = pow(h, (p-1)//q, p)
        if g == 1: continue
        break

    return p, q, g

def sign(params, x, m):
    p, q, g = params

    k = secrets.randbelow(q)
    r = pow(g, k, p) % q
    s = inverse(k, q) * (hash(m) + x*r) % q

    return (r, s)

def verify(params, y, m, sig):
    p, q, g = params
    r, s = sig

    assert 0 < r < p
    assert 0 < s < p

    w = inverse(s, q)
    u1 = hash(m) * w % q
    u2 = r * w % q
    v = pow(g, u1, p) * pow(y, u2, p) % p % q
    assert v == r


def main():
    # The parameters were generated by generate_parameters(), which will take some time to generate.
    # With that reason, we will use a fixed one instead of a random one.
    p = 17484281359996796703320753329289113133879315487679543624741105110874484027222384531803606958810995970161525595158267517181794414300756262340838882222415769778596720783078367872913954804658072233160036557319401158197234539657653635114116129319712841746177858547689703847179830876938850791424742190500438426350633498257950965188623233005750174576134802300600490139756306854032656842920490457629968890761814183283863329460516285392831741363925618264196019954486854731951282830652117210758060426483125525221398218382779387124491329788662015827601101640859700613929375036792053877746675842421482667089024073397901135900307
    q = 113298192013516195145250438847099037276290008150762924677454979772524099733149
    g = 2240914810379680126339108531401169275595161144670883986559069211999660898639987625873945546061830376966978596453328760234030133281772778843957617704660733666090807506024220142764237508766050356212712228439682713526208998745633642827205871276203625236122884797705545378063530457025121059332887929777555045770309256917282489323413372739717067924463128766609878574952525765509768641958927377639405729673058327662319958260422021309804322093360414034030331866591802559201326691178841972572277227570498592419367302032451643108376739154217604459747574970395332109358575481017157712896404133971465638098583730000464599930248

    print(f'{p = }')
    print(f'{q = }')
    print(f'{g = }')

    x = secrets.randbelow(q)
    y = pow(g, x, p)
    print(f'{y = }')

    m = b'gib flag'

    r = int(input('r = '))
    s = int(input('s = '))

    verify((p, q, g), y, m, (r, s))

    flag = os.getenv('FLAG', 'hkcert24{***REDACTED***}')
    print(flag)

if __name__ == '__main__':
    main()

比赛的时候以为是一个很复杂的根据dsa原理去做的题目，后面发现自己还是太蠢了，只要取一对正确的rs值就行了，其实就是在找他这个密码题的漏洞，r=1时s=q即符合要求

Mask-mask-RSA

task

 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


from Crypto.Util.number import getPrime, bytes_to_long

FLAG = b'flag{this_is_a_test_flag}'

def mask_expr(expr):
    global e, n
    assert '**' not in expr, "My computer is weak, I can't handle this insane calculation"
    assert len(expr) <= 4, "Too long!"
    assert all([c in r'pq+-*/%' for c in expr]), "Don't try to break me"
    res = eval(expr)
    return str(pow(res, e, n))[::2]

if __name__ == '__main__':

    e = 65537
    p, q = 1, 1
    while p == q:
        while (p-1) % e == 0:
            p = getPrime(513)
        while (q-1) % e == 0:
            q = getPrime(513)

    m = bytes_to_long(FLAG)
    n = p * q
    c = pow(m, e, n)
    print(f'{c = }')
    for _ in range(6):
        expr = input('Input your expression in terms of p, q and r: ')
        print(mask_expr(expr))

他是一个改编题，原版是 https://github.com/OfficialCyberSpace/CSCTF-2024/tree/main/crypto/mask-rsa ，修改地方就是e=3 -> 65537，还有交互的内容发送接收不同了，我们根据原题目的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
 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
158
159
160
161
162
163
164
165
166
167
168


from pwn import *
from math import gcd
from Crypto.Util.number import isPrime as is_prime


def attempt(id):
    e = 65537

    log.info(f'attempt #{id}')

    r = remote('node7.anna.nssctf.cn',24426)

    r.recvuntil(b'c = ')
    c0 = int(r.recvline().decode())

    r.sendline(b'p')
    r.sendline(b'q')
    r.sendline(b'p+q')

    r.recvuntil(b'Input your expression in terms of p, q and r: ')
    s1 = int(r.recvline().decode()) # a := p^e mod n
    r.recvuntil(b'Input your expression in terms of p, q and r: ')
    s2 = int(r.recvline().decode()) # b := q^e mod n
    r.recvuntil(b'Input your expression in terms of p, q and r: ')
    s3 = int(r.recvline().decode()) # c := (p^e + q^e) mod n

    # s1 and s2 are of different lengths
    if set([len(str(s1)), len(str(s2))]) != set([154, 155]):
        r.close()
        return False
    
    # Require that a + b = c
    if len(str(s3)) != 155:
        r.close()
        return False

    if len(str(s1)) < len(str(s2)):
        # p < q
        s1, s2 = s2, s1
        r.sendline(b'q-p')
        r.sendline(b'p+p')
        r.sendline(b'-q%p')
    else:
        # p > q
        r.sendline(b'p-q')
        r.sendline(b'q+q')
        r.sendline(b'-p%q')

    # Nonetheless, we have p > q now.

    r.recvuntil(b'Input your expression in terms of p, q and r: ')
    s4 = int(r.recvline().decode()) # s4 := (p^e - q^e) mod n
    r.recvuntil(b'Input your expression in terms of p, q and r: ')
    s5 = int(r.recvline().decode()) # s5 := (2^e q^e) mod n
    r.recvuntil(b'Input your expression in terms of p, q and r: ')
    s6 = int(r.recvline().decode()) # s6 := (-p^e - 2^e q^e) mod n

    if len(str(s4)) != 154:
        r.close()
        return False

    if len(str(s5)) != 155:
        r.close()
        return False
    if len(str(s6)) != 154:
        r.close()
        return False

    _a = [None for _ in range(309)]
    _b = [None for _ in range(309)]
    _s = [None for _ in range(309)] # a+b
    _d = [None for _ in range(309)] # a-b
    _c = [None for _ in range(309)] # c
    _f = [None for _ in range(309)] # c-a

    for i in range(155): _a[2*i+0] = int(str(s1)[i])
    for i in range(154): _b[2*i+1] = int(str(s2)[i]); _b[0] = 0
    for i in range(155): _s[2*i+0] = int(str(s3)[i])
    for i in range(154): _d[2*i+1] = int(str(s4)[i]); _d[0] = 0
    for i in range(155): _c[2*i+0] = int(str(s5)[i])
    for i in range(154): _f[2*i+1] = int(str(s6)[i]); _f[0] = 0
    
    assert _a[0] == 1

    a = b = s = d = 0
    for i in range(308, 0, -2):
        # Fill in the i-th digit
        a += _a[i] * 10**(308-i)
        s += _s[i] * 10**(308-i)
        b  = (s - a) % 10**(308-i+1)
        d  = (a - b) % 10**(308-i+1)
        
        # Fill in the (i-1)-th digit
        b += _b[i-1] * 10**(308-i+1)
        d += _d[i-1] * 10**(308-i+1)
        a  = (b + d) % 10**(308-i+2)
        s  = (a + b) % 10**(308-i+2)

    a += _a[0] * 10**308
    s += _s[0] * 10**308

    c = f = 0
    for i in range(308, 0, -2):
        # Fill in the i-th digit
        c += _c[i] * 10**(308-i)
        f  = (c - a) % 10**(308-i+1)

        # Fill in the (i-1)-th digit
        f += _f[i-1] * 10**(308-i+1)
        c  = (f + a) % 10**(308-i+2)
    
    c += _c[0] * 10**308
    f += _f[0] * 10**308

    # a = p^e mod n
    # b = q^e mod n

    # Sanity check
    assert int(str(a)[::2]) == s1
    assert int(str(b)[::2]) == s2
    assert int(str(s)[::2]) == s3
    assert int(str(d)[::2]) == s4
    assert a + b == s
    assert a - b == d
    assert c - a == f

    # a = p^65537 mod n
    # b = q^65537 mod n
    # c = 2^65537 * q^65537 mod n

    q = gcd(b, c)
    for k in range(2, 10**6):
        while q % k == 0:
            q //= k
    assert q.bit_length() == 513
    assert is_prime(q)
    
    dq = pow(e, -1, q-1)
    p = pow(a, dq, q) + q
    assert p.bit_length() == 513
    assert is_prime(p)

    n = p * q

    # Sanity check, the real one
    assert int(str(pow(p,     e, n))[::2]) == s1
    assert int(str(pow(q,     e, n))[::2]) == s2
    assert int(str(pow(p+q,   e, n))[::2]) == s3
    assert int(str(pow(p-q,   e, n))[::2]) == s4
    assert int(str(pow(2*q,   e, n))[::2]) == s5
    assert int(str(pow(2*q-p, e, n))[::2]) == s6

    phi = (p-1) * (q-1)
    d = pow(e, -1, phi)
    m0 = pow(c0, d, n)

    flag = int.to_bytes(m0, (m0.bit_length()+7)//8, 'big')
    print(f'{flag = }')

    return True

def main():
    id = 0
    while not attempt(id):
        id += 1

if __name__ == '__main__':
    main()

rsalcg0

task

 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


import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime


class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        if self.seed is None: self.seed = secrets.randbits(bits) | 1
        self.a = a
        if self.a is None: self.a = secrets.randbits(bits) | 1
        self.c = c
        if self.c is None: self.c = secrets.randbits(bits)
        self.bits = bits
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

    def __repr__(self):
        return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'


def get_prime(lcg, bits):
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()

        if p.bit_length() != bits: continue
        if not is_prime(p): continue

        return p


if __name__ == '__main__':
    FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')

    seed = secrets.randbits(16) | 1
    lcg = LCG(bits=128, seed=seed)

    print(f'{lcg = }')

    ps = [get_prime(lcg, bits=1024) for _ in range(4)]
    n = reduce(mul, ps)
    e = 0x10001

    m = int.from_bytes(FLAG, 'big')
    c = pow(m, e, n)

    print(f'{n = }')
    print(f'{e = }')
    print(f'{c = }')

seed只有16位，我们只需要优化一下线程或者是直接爆破就行

 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


from Crypto.Util.number import isPrime as is_prime
from tqdm import trange

class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        self.a = a
        self.c = c
        self.bits = bits
        self.m = 2**bits
    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

def get_prime(lcg, bits):
    while True:
        p = 0
        for _ in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        if p.bit_length() != bits: continue
        if not is_prime(p): continue
        return p

lcg = LCG(bits=128, a=181525535962623036141846439269075744717, c=115518761677956575882056543847720910703, seed=1)
n = 
c = 

for seed in trange(58725, 2**16, 2):
    lcg.seed = seed
    p = get_prime(lcg, bits=1024)
    if n%p == 0:
        break
flag = pow(c, pow(65537, -1, p-1), p)
print(bytes.fromhex(f'{flag:x}'))

rsalcg1

task

 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


import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime


class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        if self.seed is None: self.seed = secrets.randbits(bits) | 1
        self.a = a
        if self.a is None: self.a = secrets.randbits(bits) | 1
        self.c = c
        if self.c is None: self.c = secrets.randbits(bits)
        self.bits = bits
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

    def __repr__(self):
        return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'


def get_prime(lcg, bits):
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()

        if p.bit_length() != bits: continue
        if not is_prime(p): continue

        return p


if __name__ == '__main__':
    FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')

    lcg = LCG(bits=256, c=0)

    print(f'{lcg = }')

    ps = [get_prime(lcg, bits=1024) for _ in range(4)]
    n = reduce(mul, ps)
    e = 0x10001

    m = int.from_bytes(FLAG, 'big')
    c = pow(m, e, n)

    print(f'{n = }')
    print(f'{e = }')
    print(f'{c = }')

seed很大，爆破就不现实了，发现c=0，这就在暗示思路了 $$ (s \times a^{x_1} ) \times (s \times a^{x_2} ) \times (s \times a^{x_3} ) \times (s \times a^{x_4} ) \equiv n \mod m \ a^{x_1 +x_2+x_3+x_4} \times s^4 \equiv n \mod m \ let \ t = x_1 +x_2+x_3+x_4 \ s^4 ≡ n \times a^{-t} $$

哎推到这里了，我要去求s，对式子开四次方，na已知，我只要暴力求解t就行了,这个t都是4个一批的

 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


import secrets
class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        if self.seed is None: self.seed = secrets.randbits(bits) | 1
        self.a = a
        if self.a is None: self.a = secrets.randbits(bits) | 1
        self.c = c
        if self.c is None: self.c = secrets.randbits(bits)
        self.bits = bits
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

    def __repr__(self):
        return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'

def get_prime(lcg, bits):
    while True:
        p = 0
        for _ in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        if p.bit_length() != bits: continue
        if not is_prime(p): continue
        return p

n = 
c = 
a = 
m = 2**256
from Crypto.Util.number import *
t = 0
while True:
    t += 4
    for seed in Zmod(m)(n * pow(a, -t, m)).nth_root(4, all=True):
        lcg = LCG(bits=256, seed=int(seed), a=a, c=0)
        p = get_prime(lcg, bits=1024)
        if n%p != 0:
            continue
        flag = pow(c, pow(65537, -1, p-1), p)
        flag=long_to_bytes(flag)
        print(flag)

rsalcg2

task

 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


import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime


class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        if self.seed is None: self.seed = secrets.randbits(bits) | 1
        self.a = a
        if self.a is None: self.a = secrets.randbits(bits) | 1
        self.c = c
        if self.c is None: self.c = secrets.randbits(bits)
        self.bits = bits
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

    def __repr__(self):
        return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'


def get_prime(lcg, bits):
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()

        if p.bit_length() != bits: continue
        if not is_prime(p): continue

        return p


if __name__ == '__main__':
    FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')

    lcg = LCG(bits=256, a=1)

    print(f'{lcg = }')

    ps = [get_prime(lcg, bits=1024) for _ in range(4)]
    n = reduce(mul, ps)
    e = 0x10001

    m = int.from_bytes(FLAG, 'big')
    c = pow(m, e, n)

    print(f'{n = }')
    print(f'{e = }')
    print(f'{c = }')

和上一个一样爆破是不可能的，我们现在的式子就变成了s+xc，我感觉更像一个算法题（），我们利用01去写四个误差情况，计算出可能的误差，排列出所有的情况，用异常去判断情况，然后通过的去求多项式根，直到能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


import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
import itertools
from tqdm import tqdm


class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        if self.seed is None: self.seed = secrets.randbits(bits) | 1
        self.a = a
        if self.a is None: self.a = secrets.randbits(bits) | 1
        self.c = c
        if self.c is None: self.c = secrets.randbits(bits)
        self.bits = bits
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

    def __repr__(self):
        return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'


def get_prime(lcg, bits):
    while True:
        p = 0
        pi_list = []
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            pi = lcg.next()
            pi_list.append(pi)
            p |= pi
            if i == 0:
                orig_seed = pi
        

        if int(p).bit_length() != bits: continue
        if not is_prime(p): continue

        return p


if __name__ == '__main__':
    FLAG = b'hkcert24{***REDACTED***}'
    
    c = 
    M = 2^256    

    n = 

    possible_bias = [(0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 1, 1), (0, 0, 0, 0)]
    possible_B = []
    for bias_list in possible_bias:
        B = sum((i * c - bi * M) * M^(3-i) for i, bi in enumerate(bias_list))
        possible_B.append(B)

    A = sum(M^(3-i) for i in range(len(bias_list)))

    for my_indices in itertools.product(range(4), repeat=4):
        Bs = prod(possible_B[index] for index in my_indices) % A
        if Bs == n % A:
            break
    else:
        raise Exception("abab")
    
    B_list = [possible_B[index] for index in my_indices]
    bias_list = [possible_bias[index] for index in my_indices]
    print(f'{bias_list = }')


    PR.<x> = Zmod(n)[]

    for kdiff_0 in tqdm(range(-3000, 3000)):
        kdiff = 4 * kdiff_0
        xdiff0 = c * kdiff % M
        for xdiff in [xdiff0, xdiff0 - M]:
            f0 = (A * x + B_list[0]) * (A * (x + xdiff) + B_list[1])
            f = f0.monic()
            sol = f.small_roots(X=2^256, beta=0.48)
            for x_ in sol:
                p = A * ZZ(x_) + B_list[0]
                if n % p == 0:
                    print(f'{p = }')
                    exit()

from Crypto.Util.number import *
e = 65537
c = 
p = 
d = inverse(e, p-1)
m = pow(c, d, p)
print(long_to_bytes(m))

rsalcg3

task

 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


import os
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime


class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        if self.seed is None: self.seed = secrets.randbits(bits) | 1
        self.a = a
        if self.a is None: self.a = secrets.randbits(bits) | 1
        self.c = c
        if self.c is None: self.c = secrets.randbits(bits)
        self.bits = bits
        self.m = 2**bits

    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        return self.seed

    def __repr__(self):
        return f'LCG(bits={self.bits}, a={self.a}, c={self.c})'


def get_prime(lcg, bits):
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()

        if p.bit_length() != bits: continue
        if not is_prime(p): continue

        return p


if __name__ == '__main__':
    FLAG = os.environb.get(b'FLAG', b'hkcert24{***REDACTED***}')

    seed = secrets.randbits(128)<<128 | 1
    lcg = LCG(bits=256, seed=seed)

    print(f'{lcg = }')

    ps = [get_prime(lcg, bits=1024) for _ in range(4)]
    n = reduce(mul, ps)
    e = 0x10001

    m = int.from_bytes(FLAG, 'big')
    c = pow(m, e, n)

    print(f'{n = }')
    print(f'{e = }')
    print(f'{c = }')

这个是真不会，seed被«128，那么$seed«128 \mod 2^{128}=1$，按着佬的思路来说，直接做一个$2^{128}$的mitm，去恢复x1到x4，然后就有一个mod 2**256的方程，利用.roots(multiplicities=False)求解，或者是lsb也可以，看不懂。

 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


from tqdm import trange, tqdm

a = 
c = 
n = 
e = 65537
ct = 

class LCG:
    def __init__(self, bits, a=None, c=None, seed=None):
        self.seed = seed
        self.a = a
        self.c = c
        self.bits = bits
        self.m = 2**bits
        self.counter = 0
    def next(self):
        self.seed = (self.seed * self.a + self.c) % self.m
        self.counter += 1
        return self.seed

def get_prime(lcg, bits):
    while True:
        p = 0
        for _ in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        if p.bit_length() != bits: continue
        if not is_prime(p): continue
        return p

def get_chunk(lcg, bits):
    p = 0
    for _ in range(bits//lcg.bits):
        p <<= lcg.bits
        p |= lcg.next()
    return p 

lcg = LCG(bits=256, seed=1, a=a, c=c)
MAX = 3200
m = 2**128
pp = [get_chunk(lcg, 1024) % m for _ in range(MAX)] # possible prime lsbs

def mitm():
    lookup = {}
    for x2 in trange(MAX):
        for x1 in range(x2):
            lookup[pp[x1] * pp[x2] % m] = (x1, x2)
    for x4 in trange(MAX):
        for x3 in range(x4):
            t = n * pow(pp[x3] * pp[x4], -1, m) % m
            if t in lookup:
                x1, x2 = lookup[t]
                return (x1, x2, x3, x4)

x1, x2, x3, x4 = mitm()
#x1, x2, x3, x4 = [2848, 3158, 595, 1597]
print(x1, x2, x3, x4)
x1, x2, x3, x4 = (4*(x1+1), 4*(x2+1), 4*(x3+1), 4*(x4+1))

m = 2**256 # now work mod 2**256
PR.<s> = PolynomialRing(Zmod(m))
def f(x):
    return (pow(a, x, m) * s + c * sum([pow(a, i, m) for i in range(x)])) 
g = f(x1) * f(x2) * f(x3) * f(x4) - n
g = g.change_ring(ZZ)

sol = {0}
for i in range(256):
    cur_sol = set()
    for rr in sol:
        for b in [0, 1]:
            r = b*2**i + rr
            M = 2**(i+1)
            if 0 != g(r) % M:
                continue
            cur_sol.add(r)
        sol = cur_sol

for seed in tqdm(sol):
    if seed % 2**128 != 1:
        continue
    if seed.bit_length() != 256:
        continue
    lcg = LCG(bits=256, seed=seed, a=a, c=c)
    p = get_prime(lcg, 1024) 
    if n % p == 0:
        break
flag = pow(ct, pow(e, -1, p-1), p)
print(bytes.fromhex(f'{flag:x}'))

总结

含金量很高很难的比赛，24年没有去线下很遗憾，相信自己吧，25加油