HKCERT2024

发表于

复现一下去年hkcert的部分题目，剩下的有空再看

Almost DSA / 數立僉章寅算法

题目

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
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()

我们要使得

v=gu1yu2=gms−1yrs−1mod  pmod  q=rv=g^{u_1}y^{u_2}=g^{ms^{-1}}y^{rs^{-1}}\mod p\mod q=r

直接令 s=qs=q ，那么 v=1v=1

故 s=q,r=1s=q,r=1

RSA LCG (0)

题目

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只有16bits，直接多线程爆破就完事了

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
import secrets
from Crypto.Util.number import *
from tqdm import trange
import multiprocessing


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 isPrime(p):
            continue

        return p


def find_seed(start_seed, end_seed, lcg, n):
    for seed in trange(start_seed, end_seed, 2):
        lcg.seed = seed
        ps = get_prime(lcg, bits=1024)
        if n % ps == 0:
            return seed 
    return None


def main():
    lcg = LCG(
        bits=128,
        a=181525535962623036141846439269075744717,
        c=115518761677956575882056543847720910703,
        seed=1,
    )
    
    n = 481114791694785858695050549695538734046971417176843978882044871919616727765643820034066591387776993303130591599679964348353329376559922076715381691496791199317834852972956556186543750873476577029492255903246050392214315442941266567737558736141253495436298490003513325026207840446389886295321748490024615821174562383476857761918630446488869812894422048853097952363719756297344014883459670109643440173428469002028435568608888993928248402297380061528970024946401518041243564217741744613525402813984605478699738311132717493610790718032712239270654974446116711995328572373804563487208899590643981315012517538379075118546604524143430683964513429268368997878214614073305169449253802788601323508855536854500946367628892634824935231007194546528797696281628426050519984306590514055620223093615738335974270220301535497863462980632453977776013292134758089648072661829571370276168813518517058289217357255320627263734650032320305279867840420886394855960116879598125383109784504746667833173574005936871719063288584361794901458463052848937392072728849939635133710409996428462876274835371522565826839423046726308001047859782566419852401917763502007196004524754115471117969452116174478677547559057917128250716516531170082878464757039874318490906158689
    e = 65537
    c = 345977789156696385683581168846000378215844867611205467179181525756923773343997491856273352579925123046597359189866939437231366570263052567113535467666353517443555775669947203980735918360811410985879753948221470545729133552842244535778330182549296248222039054438197983267418429814674564210947108838042963108251861548375535326969960093796185009763176002544709169063466256285182205803310470811843866647483609768051301160908646352263376778439044867189801653416628219979460525679135210530110143121851284249580066642389243748128010268277263972367956550837364650977683324140767090284085773301486622501777068017859676285398384937589784505599555747372780238872296757407155242584567297352399943303106161556729208284654934208601533197169169514879515899747537955886064112109885660797961038075757520138954391314283382301755474526387505278386817416193439304304484679228240909612236945218009947246430065957288065358434877715856330476675541582153869420244176864467086961698529560004535449279996657026744930241841052475481816491735959706500890907139027990119800255632071177694111432383236909734940374926954075681464953536382583119130818187839809617068848876572944726598351264384270260481762978383770917542259594389267566490962365207501538561114532291

    num_processes = 16
    range_size = 2**16 // num_processes
    pool = multiprocessing.Pool(num_processes)

    results = pool.starmap(find_seed, [
        (i * range_size + 1, (i + 1) * range_size + 1, lcg, n) for i in range(num_processes)
    ])

    for result in results:
        if result:
            seed = result
            print(f"Found seed: {seed}")
            break

    lcg = LCG(
    bits=128,
    a=181525535962623036141846439269075744717,
    c=115518761677956575882056543847720910703,
    seed=seed,
    )
    ps = [get_prime(lcg, bits=1024) for _ in range(4)]
    n = ps[0] * ps[1] * ps[2] * ps[3]
    phi = (ps[0] - 1) * (ps[1] - 1) * (ps[2] - 1) * (ps[3] - 1)
    e = 0x10001
    d = pow(e, -1, phi)

    m = pow(c, d, n)

    flag = long_to_bytes(m)
    print(flag)



if __name__ == "__main__":
    main()

RSA LCG (1)

题目

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***}')

    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 = }')

已知

pi=aixb3+ai+1xb2+ai+2xb+ai+3x=aix(b3+ab2+a2b+a3)n=pipjpkpl=ai+j+k+lx4(b3+ab2+a2b+a3)≡ai+j+k+l+12x4mod  bp_i=a^ixb^3+a^{i+1}xb^2+a^{i+2}xb+a^{i+3}x=a^ix(b^3+ab^2+a^2b+a^3)\\ n=p_ip_jp_kp_l=a^{i+j+k+l}x^4(b^3+ab^2+a^2b+a^3)\equiv a^{i+j+k+l+12}x^4\mod b

经测试可以知道 i,j,k,li,j,k,l 大概位于[−4000,4000][-4000,4000]以内

那么我们可以利用剪枝计算出 ai+j+k+l+12x4a^{i+j+k+l+12}x^4 然后枚举来得到 pip_i 以分解 nn

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

def find(x):
    if len(x) == 256:
        xx = int(x, 2)
        if (pow(a, I, b) * pow(xx, 4, b) - n) % b == 0:
            out.append(xx)
            return
    else:
        for i in "01":
            xx = i + x
            bb = 2 ** len(x)
            xxx = int(xx, 2)
            if (pow(a, I, bb) * pow(xxx, 4, bb) - n) % bb == 0:
                find(xx)


out = []
b = 2**256
a = 102197201962123846389438942955101245465045811321520032783251514372432272871077
n = 712650313276602240132329097304430048400352751513310575526412992129597422070848111072491134888258819603174150809317988369755331029009864211216547294646211646094933573124257136163629116984386416188859789467395164897001085191528084740453428500956450177548977865861466055171717564208692444769495508512419622780024874941844495178742341131675818700155796280310646897103229083027529919187454771613414875490462993045875936234591157744167214046734190302287427367403568860249349359776931200150301621481939428066984857258770478004853926288162003818241246878159630318266155498887714140614580751646422502723648142074111613225912644502226694307736726087673647398291980857229829977354067820423709011783907277562489549103977052076140881547728240425069463175586173317054911517453708001448687312406872942899280723472709421452062317503252258181984837591194705354256671714708896675155493168030996749797654707148117051477506855802867089687545890519363621855230477269747205380531049996041867129632051572747028441506474146062043427303954298727328531350438208765938027973006421501568307421856483699068172998763428694958905673708416275143602068221058898394079378423785058886143156065469790907727616640696078658243794470631540358286862899496224884600294835441
e = 65537
c = 445308155915029567991204642441037106636274278969323594266962964897048528466773947276913391974222302661172087064465526779062356615268434642959161607080766074334140739062421641878296527210809334178619685030176261525389226557543594953035919061416292966585184462770190073132725325830890587610808224156896611989260754435566640011008330800266408350415234832430226789140062590779004940578475055195767146347394381212157930691103929079825296986828415158506003438261121628407171546274414046568037336522095223978532053246031668840069046046390952201058199981492454288495640857942797704964843287034359460079316661425483842570190113998195387780579545809621808801626313837113473885818945052873823360056317079785841069224993435527933283918571286444280017102781865312454024328849395335083566145607543834607504822081522250923714391873652357185101163374950977150829214936039230387625706376713934778873385375582488086205462961139042991664546797362021066081938999660281537596860879414252495949608351649066648594254272314188241185715920283526637402373027396529855631498571685297193020517033784357794223831020791070397249992230576960345185544552280142788704673413055403847038488791910041421887897364099871208624646292906015164161354890370666964030412257423
I = 0
find("")
P = []
for x in out:
    for i in range(-4000, 4000):
        p = pow(a, i, b) * x % b * b**3 + pow(a, i + 1, b) * x % b * b**2 + pow(a, i + 2, b) * x % b * b**1 + pow(a, i + 3, b) * x % b
        if n%p == 0:
            P.append(p)
P = set(P)
print(len(P))
print(P)
phi = 1
for p in P:
    phi *= p-1
d=inverse(e,phi)
print(long_to_bytes(pow(c,d,n)))

RSA LCG (2)

题目

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***}')

    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 = }')

已知

pi=(x+ic)%bb3+(x+(i+1)c)%bb2+(x+(i+2)c)%bb+(x+(i+3)c)%bp_i=(x+ic)\%bb^3+(x+(i+1)c)\%bb^2+(x+(i+2)c)\%bb+(x+(i+3)c)\%b

很显然每个部分的k的都在0和1之间，直接开爆就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from Crypto.Util.number import *


b = 2**256
c = 14258939715516539295587731120991968901228171455016001595761489750577784177213
n = 279784521303926518544200383491171400996467006054806060652945044514173580730320793076951350168517896308345078513333979433742090849938580604359515861344088875721354836410510396140219655796215325682295239294661185563708496490830500773420871847769568879274978173218440545663363350310752698066412613793738234395676975963986090446949443295350235071286869321557833967521199446244573020803085515110891641843096725596572980675877230459500589604078432572911282759481893882548258867802789628543364574694501159808895930747113406016718685856976531978713324829507636743778130758650283045513372598798114943752532619142439604369129493324057181519512588183783756314385380800844831034863151900295735342816476791991454383732133474515109758087482912794282007801160780475284011802960270750792620686906175026995623082009841402872948756740311519047998978234628057595438481437871594714428834059691733188294695393205472914443179153321670750219104306769911019089432918102588905808629421158434486927928786793524017503900505368724824170796339023214910404096208544407500008089429770878575702088992309354303731919302687039737672125268143820658069899761163750521000478474705014645224845757836226858836333259628284972467671764606702417658922805838428375959908059533
"""
from tqdm import trange
PR.<x> = PolynomialRing(Zmod(n))
for i in trange(1000):
    k = 4 * i
    t = k * c % b
    for k1 in range(2):
        for k2 in range(2):
            for k3 in range(2):
                for k4 in range(2):
                    for k5 in range(2):
                        for k6 in range(2):
                            for k7 in range(2):
                                pp = x * b ^ 3 + (x + c - k1 * b) * b ^ 2 + (x + 2 * c - (k1 + k2) * b) * b + x + 3 * c - (k1 + k2 + k3) * b
                                qq = (x + t - k4 * b) * b ^ 3 + (x + t + c - (k4 + k5) * b) * b ^ 2 + (x + t + 2 * c - (k4 + k5 + k6) * b) * b + x + t + 3 * c - (k4 + k5 + k6 + k7) * b
                                f = pp * qq
                                roots = f.monic().small_roots(X=2 ^ 256, beta=0.25)
                                if roots:
                                    print(roots)
"""
x = 84705119374453985280579495397595127888476080054094351532697352435930792929010
p = x % b * b**3 + (x + c) % b * b**2 + (x + 2 * c) % b * b + (x + 3 * c) % b
enc = 12668023009781840908542456747150790958366008947388222673139950309896560492008423201703814113959062916216738813414905779255815616125482715748800637882572776464413794672305560913420843604427904075596817771292191713968187201485479797042112384390953800170012145372635694385419895184449315436204936393181245447065007450494691263361925589404791904565458416407877820052394996905208559706702586674504665164085593562932792149402776674399837342851449263354042894145700586851308674806581185881411576045932596814585050689676622481653401541955765009732517013919996864475158687111703292317464104677422251199063539026204584634157266215824371162154934075299210675220082034930924899581928745732959112210135371763739653442724659470938281648056607023621212384635978368358089470066114660978000389704285586405309891824263306072117253963803228130111794609335559502199299483268104278641029669532263556375348912538425414244341532656162870453118645106346455731193356791582571147804331894783849241501307040707035938949680381788534081674899875606974239354654393310878542209938345878740320797711262798440736790479007006147569066845667894663218494368548456732889916013895067014484182872120996578247736683746861794081478555452926231507488557048374863197550101866
e = 65537
d = inverse(e, p - 1)
print(long_to_bytes(pow(enc, d, p)))

RSA LCG (3)

题目

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
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 = }')

我们将LCG模 21282^{128} 可以发现seed就为0了，这时候LCG的全部参数已知，我们要计算 pipjpkpl≡nmod  128p_{i}p_{j}p_{k}p_{l}\equiv n \mod{128} 的i,j,k,li,j,k,l。由于这些参数很小，我们可以考虑使用mitm， 得到这些参数后带回去解方程即可得到seed。之后就是常规的解RSA了。

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

class LCG:
    def __init__(self, bits, a, c, seed):
        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 __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 isPrime(p): continue

        return p
    
def get_number(lcg, bits):
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        return p
    
M = 3200
a = 14766004292360945258404852367497617471774948936126805425073927394403062559771
c = 101392444572529008969348961056906071660419768871029068095780498478077435335658
m = 2**128
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
enc = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945
lcg = LCG(bits=256, seed=1, a=a, c=c)
ps = [get_number(lcg, 1024) % m for _ in range(M)]

mitm = {}
def MITM():
    for x1 in trange(M):
        for x2 in range(x1):
            mitm[ps[x1] * ps[x2] % m] = (x1, x2)
    for x3 in trange(M):
        for x4 in range(x1):
            u = n * gmpy2.invert(ps[x3] * ps[x4], m) % m
            if u in mitm:
                return (*mitm[u], x3, x4)
X = MITM()
print(X) 
X = [4 * (i + 1) for i in X]
mod = 2**256
R.<s> = Zmod(mod)[]
def gen(x):
    return pow(a, x, mod) * s + c * sum(pow(a, i, mod) for i in range(x))
f = prod(gen(x) for x in X) - n
seeds = [int(i) for i in f.roots(multiplicities=False)]
for seed in seeds:
    if seed % m == 1:
        lcg = LCG(bits=256, seed=seed, a=a, c=c)
        ps = [get_prime(lcg, bits=1024) for _ in range(4)]
        if prod(ps) == n:
            d = inverse(e, prod(p - 1 for p in ps))
            print(long_to_bytes(pow(enc, d, n)))