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

from Crypto.Util.number import *
from functools import reduce
from math import gcd
import gmpy2
def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    print('lcg_c =',increment)
def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * gmpy2.invert(states[1] - states[0], modulus) % modulus # 注意这里求逆元
    print('lcg_m =', multiplier)
    return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    print('lcg_n =',modulus)
    return crack_unknown_multiplier(states, modulus)


states = [2166771675595184069339107365908377157701164485820981409993925279512199123418374034275465590004848135946671454084220731645099286746251308323653144363063385,
6729272950467625456298454678219613090467254824679318993052294587570153424935267364971827277137521929202783621553421958533761123653824135472378133765236115,
2230396903302352921484704122705539403201050490164649102182798059926343096511158288867301614648471516723052092761312105117735046752506523136197227936190287,
4578847787736143756850823407168519112175260092601476810539830792656568747136604250146858111418705054138266193348169239751046779010474924367072989895377792,
7578332979479086546637469036948482551151240099803812235949997147892871097982293017256475189504447955147399405791875395450814297264039908361472603256921612,
2550420443270381003007873520763042837493244197616666667768397146110589301602119884836605418664463550865399026934848289084292975494312467018767881691302197]
crack_unknown_modulus(states)

 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

from Crypto.Util.number import *
class LCG:
    lcg_n = 8311271273016946265169120092240227882013893131681882078655426814178920681968884651437107918874328518499850252591810409558783335118823692585959490215446923
    lcg_m = 99470802153294399618017402366955844921383026244330401927153381788409087864090915476376417542092444282980114205684938728578475547514901286372129860608477
    lcg_c = 3910539794193409979886870049869456815685040868312878537393070815966881265118275755165613835833103526090552456472867019296386475520134783987251699999776365

    def __init__(self, lcg_s):
        self.state = lcg_s

    def next(self):
        self.state = (self.state * self.lcg_m + self.lcg_c) % self.lcg_n
        return self.state

bits = 512
it = 8
seed = 211286818345627549183608678726370412218029639873054513839005340650674982169404937862395980568550063504804783328450267566224937880641772833325018028629959635
lcg = LCG(seed)
primes_arr = []
dump = True
items = 0
dump_file = open("dump.txt", "w")
primes_n = 1
while True:
    for i in range(it):
        while True:
            prime_candidate = lcg.next()
            if dump:
                dump_file.write(str(prime_candidate) + '\n')
                items += 1
                if items == 6:
                    dump = False
                    dump_file.close()
            if not isPrime(prime_candidate):
                continue
            elif prime_candidate.bit_length() != bits:
                continue
            else:
                primes_n *= prime_candidate
                primes_arr.append(prime_candidate)
                break

    # Check bit length
    if primes_n.bit_length() > 4096:
        print("bit length", primes_n.bit_length())
        primes_arr.clear()
        primes_n = 1
        continue
    else:
        break
phi = 1
for k in primes_arr:
    phi *= (k - 1)
print(phi)

1
2
3
4
5
6
7
8

from Crypto.Util.number import *
n = 10663197782188755187683519128391607889384236984841159980368295444757556251666173181966270935627381363634363152017932100870866073743196496182631686860974529519304898483583880797787662017633083156395595834399833548697123723014690019039843286516441722069672629491734333533874814655021750465470744221908153042891598629847474248035637833322061522018106952433195747728295433960640630861246440503259390376775374597599893181929337896828585045200809527092809746018806372033463639511758548910283175609247004446838778595246305426570138737826179346237355482797652195577697810275921391495040635386160960077290295503041318571091585994232128977189250560450541724526298324540333633756525782039764692046496665886338829810667477580556894564708344208454824227841439832096019161139930247745872364451624685509376111571650368725564985474387879414080347347860850162991841345901292668284154455326375190710973306072342463052980587717861754724857153296737480485351289440257347649463959856275061657492903860650820592573032713540474706170687783458640870091611869081448943812812946839710972240290444677129959352614435646729998203754847928052523568784250017348717982594389028978174915940120215557880850880860400503991453968452316505964854586987874049061874850121
e = 65537
c = 10055254817050606245078153964646282242016712923067254347101179149126378075855557984444414832883736339376030157110423579564741992729154299416090391420673495156302631715184952278776857766630468957122329097655361855535821012593032248081430756595979234217592639981583078092538703328639975720325313111710799382457518258395223013618693662530651002257735692525447623832044481622746940704891677411801830135208674961935858773315372231561192043480490442131198776900157673286071484062314825613878317224314010080367732125262343817670331752772111584576200940020826867275528178570726846114159707083421681687680774090415554465967672606070482724934208764047203678460712508708647282278957530279325745679169141484341188338798865804249431810624874933179557415020940131495920677234399770552248514559162081906594199582776738188034083043493761702452697831623872823660942359263083188815075033808190977768416992965529025751418921326743349959309259035744651361425225375254040098604181809300720180774470683783401044114415010132938312251359225043793491588434652587442607783449289445897392963984411136478966903796587388294245194356306941496594442766170466555151436915204077741696524766661045685287856846632686882652415672316507235603192046053967442247947850572
phi = 10663197782188755187683519128391607889384236984841159980368295444757556251666173181966270935627381363634363152017932100870866073743196496182631686860974518215336308559118375893619890700566492246455484248865065942975919518821420696894418516412087824875580336264450895120608590786960103732463735259314746627602481490634183029017002524008299865576550974115842994899362462506740342026543406560282128252586317741411826809367436511777686104024771128452674932531192224723706907716833848808135180104501764984240012323401024049549978818892958211947253027021172432101248326724880191387361026527894934644325582519289043602145078962059823083375709403213297514989173849682349374277191142325479424357500368940265794006074137733272137342565970150847115890972043431768285064555903295753465581583657708894234169997201812684367717581685538245496933190164547560072929740493318805568286958724231450156740155971287257415601496588835565287706802963284818961466920678551895969101307349683566564580517648582979443095366832488807574064804819371853182596765904847800309068939076791323026159289764642558267730090790476527577604463134018573846651149743622527934870659053517579542096949282004235077015296802375481771769578980224915514371840316985391540016742400
d = inverse(phi,n)
print(long_to_bytes(pow(c,d,n)))
# b'CTF{C0nGr@tz_RiV35t_5h4MiR_nD_Ad13MaN_W0ulD_b_h@pPy}'