抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

2024 HKCERT Crypto Writeup

crypto日常比赛

发布于：2025年2月25日

次浏览

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

数据：

1
2
3
4
lcg = LCG(bits=128, a=181525535962623036141846439269075744717, c=115518761677956575882056543847720910703)
n = 481114791694785858695050549695538734046971417176843978882044871919616727765643820034066591387776993303130591599679964348353329376559922076715381691496791199317834852972956556186543750873476577029492255903246050392214315442941266567737558736141253495436298490003513325026207840446389886295321748490024615821174562383476857761918630446488869812894422048853097952363719756297344014883459670109643440173428469002028435568608888993928248402297380061528970024946401518041243564217741744613525402813984605478699738311132717493610790718032712239270654974446116711995328572373804563487208899590643981315012517538379075118546604524143430683964513429268368997878214614073305169449253802788601323508855536854500946367628892634824935231007194546528797696281628426050519984306590514055620223093615738335974270220301535497863462980632453977776013292134758089648072661829571370276168813518517058289217357255320627263734650032320305279867840420886394855960116879598125383109784504746667833173574005936871719063288584361794901458463052848937392072728849939635133710409996428462876274835371522565826839423046726308001047859782566419852401917763502007196004524754115471117969452116174478677547559057917128250716516531170082878464757039874318490906158689
e = 65537
c = 345977789156696385683581168846000378215844867611205467179181525756923773343997491856273352579925123046597359189866939437231366570263052567113535467666353517443555775669947203980735918360811410985879753948221470545729133552842244535778330182549296248222039054438197983267418429814674564210947108838042963108251861548375535326969960093796185009763176002544709169063466256285182205803310470811843866647483609768051301160908646352263376778439044867189801653416628219979460525679135210530110143121851284249580066642389243748128010268277263972367956550837364650977683324140767090284085773301486622501777068017859676285398384937589784505599555747372780238872296757407155242584567297352399943303106161556729208284654934208601533197169169514879515899747537955886064112109885660797961038075757520138954391314283382301755474526387505278386817416193439304304484679228240909612236945218009947246430065957288065358434877715856330476675541582153869420244176864467086961698529560004535449279996657026744930241841052475481816491735959706500890907139027990119800255632071177694111432383236909734940374926954075681464953536382583119130818187839809617068848876572944726598351264384270260481762978383770917542259594389267566490962365207501538561114532291

seed只有16比特，直接多线程爆破就行了

这边对于一个固定的seed来说，他生成的素数是固定的，所以我们知道先生成一个素数，检验能不能整除n就行了，不需要一次性都生成，这样可以快两三倍以上

其实p的部分比特位之间是有lcg的关系的，很容易想到剪枝，而且模数还是2的次幂

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
from Crypto.Util.number import long_to_bytes, inverse
from Crypto.Util.number import isPrime as is_prime
from multiprocessing import Pool
from tqdm import trange
import secrets

class LCG:
    def __init__(self, bits, a=None, b=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 = b
        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):
    for _ in range(4000):  
        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
    return False


def attack(range_):
    low, high = range_[0], range_[1]
    a = 181525535962623036141846439269075744717
    b = 115518761677956575882056543847720910703
    n = 481114791694785858695050549695538734046971417176843978882044871919616727765643820034066591387776993303130591599679964348353329376559922076715381691496791199317834852972956556186543750873476577029492255903246050392214315442941266567737558736141253495436298490003513325026207840446389886295321748490024615821174562383476857761918630446488869812894422048853097952363719756297344014883459670109643440173428469002028435568608888993928248402297380061528970024946401518041243564217741744613525402813984605478699738311132717493610790718032712239270654974446116711995328572373804563487208899590643981315012517538379075118546604524143430683964513429268368997878214614073305169449253802788601323508855536854500946367628892634824935231007194546528797696281628426050519984306590514055620223093615738335974270220301535497863462980632453977776013292134758089648072661829571370276168813518517058289217357255320627263734650032320305279867840420886394855960116879598125383109784504746667833173574005936871719063288584361794901458463052848937392072728849939635133710409996428462876274835371522565826839423046726308001047859782566419852401917763502007196004524754115471117969452116174478677547559057917128250716516531170082878464757039874318490906158689
    e = 65537
    c = 345977789156696385683581168846000378215844867611205467179181525756923773343997491856273352579925123046597359189866939437231366570263052567113535467666353517443555775669947203980735918360811410985879753948221470545729133552842244535778330182549296248222039054438197983267418429814674564210947108838042963108251861548375535326969960093796185009763176002544709169063466256285182205803310470811843866647483609768051301160908646352263376778439044867189801653416628219979460525679135210530110143121851284249580066642389243748128010268277263972367956550837364650977683324140767090284085773301486622501777068017859676285398384937589784505599555747372780238872296757407155242584567297352399943303106161556729208284654934208601533197169169514879515899747537955886064112109885660797961038075757520138954391314283382301755474526387505278386817416193439304304484679228240909612236945218009947246430065957288065358434877715856330476675541582153869420244176864467086961698529560004535449279996657026744930241841052475481816491735959706500890907139027990119800255632071177694111432383236909734940374926954075681464953536382583119130818187839809617068848876572944726598351264384270260481762978383770917542259594389267566490962365207501538561114532291
    for seed in trange(low, high):
        lcg = LCG(bits=128, seed=seed, a = a, b = b)
        tmp = get_prime(lcg, bits=1024)
        if tmp and n % tmp == 0:
            ps = [tmp]
            [ps.append(get_prime(lcg, bits=1024)) for _ in range(3)]
            phi = (ps[0] - 1) * (ps[1] - 1) * (ps[2] - 1) * (ps[3] - 1)
            d = inverse(e, phi)
            m = long_to_bytes(int(pow(c, d, n)))
            # print(m, flush = True)
            return m  # 返回答案


if __name__ == "__main__":   
    ranges = [(i, i + 4096) for i in range(0, 2 ** 16, 4096)]
    with Pool(16) as pool:    #2 ** 15 // 16 = 2048
        results = pool.imap_unordered(attack, ranges)
        for m in results:
            if m:  # 如果找到答案
                print(m)     #b'hkcert24{0k4y_th1s_1s_n0t_ev3n_vu1n3r4b1e_b3c4u5e_0f_1cgs}'
                pool.terminate()  # 终止所有进程
                break  # 退出循环

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

数据：

1
2
3
4
5
lcg = LCG(bits=256, a=102197201962123846389438942955101245465045811321520032783251514372432272871077, c=0)
n = 712650313276602240132329097304430048400352751513310575526412992129597422070848111072491134888258819603174150809317988369755331029009864211216547294646211646094933573124257136163629116984386416188859789467395164897001085191528084740453428500956450177548977865861466055171717564208692444769495508512419622780024874941844495178742341131675818700155796280310646897103229083027529919187454771613414875490462993045875936234591157744167214046734190302287427367403568860249349359776931200150301621481939428066984857258770478004853926288162003818241246878159630318266155498887714140614580751646422502723648142074111613225912644502226694307736726087673647398291980857229829977354067820423709011783907277562489549103977052076140881547728240425069463175586173317054911517453708001448687312406872942899280723472709421452062317503252258181984837591194705354256671714708896675155493168030996749797654707148117051477506855802867089687545890519363621855230477269747205380531049996041867129632051572747028441506474146062043427303954298727328531350438208765938027973006421501568307421856483699068172998763428694958905673708416275143602068221058898394079378423785058886143156065469790907727616640696078658243794470631540358286862899496224884600294835441
e = 65537
c = 445308155915029567991204642441037106636274278969323594266962964897048528466773947276913391974222302661172087064465526779062356615268434642959161607080766074334140739062421641878296527210809334178619685030176261525389226557543594953035919061416292966585184462770190073132725325830890587610808224156896611989260754435566640011008330800266408350415234832430226789140062590779004940578475055195767146347394381212157930691103929079825296986828415158506003438261121628407171546274414046568037336522095223978532053246031668840069046046390952201058199981492454288495640857942797704964843287034359460079316661425483842570190113998195387780579545809621808801626313837113473885818945052873823360056317079785841069224993435527933283918571286444280017102781865312454024328849395335083566145607543834607504822081522250923714391873652357185101163374950977150829214936039230387625706376713934778873385375582488086205462961139042991664546797362021066081938999660281537596860879414252495949608351649066648594254272314188241185715920283526637402373027396529855631498571685297193020517033784357794223831020791070397249992230576960345185544552280142788704673413055403847038488791910041421887897364099871208624646292906015164161354890370666964030412257423

对于nn的每个因子，我们假设为n0,n1,n2,n3n_0, n_1, n_2, n_3，对于n0n_0，我们知道它是由4次lcglcg迭代而成的，假设第一次到第四次生成的分别为n00,n01,n02,n03n_{00}, n_{01}, n_{02}, n_{03}

那么他应该满足如下的等式

n0=2768∗n00+2512∗n01+2256n02+n03n_{0} =2^ {768}*n_{00}+ 2^ {512} * n_{01}+2^ {256}n_{02}+n_{03}

显然有如下的等式，

n0=2768∗(ai∗x)%m+2512∗(ai+1∗x)%m+2256∗(ai+2∗x)%m+(ai+3∗x)%mn_{0} = 2 ^ {768} * (a^i *x ) \% m + 2^ {512} * (a ^ {i + 1} * x) \% m + 2 ^ {256} * (a^{i + 2} * x) \% m + (a^{i + 3} * x) \% m

直接都转为模mm的意义下，则有

n0≡ai+3∗x (mod m)n_{0} \equiv a^{i + 3} * x\ (mod\ m)

对于其他的其他的因子，也有

n1≡aj+3∗x (mod m)n2≡ak+3∗x (mod m)n3≡al+3∗x (mod m)\begin{array}{l} n_{1} \equiv a^{j + 3} * x\ (mod\ m)\\ n_{2} \equiv a^{k + 3} * x\ (mod\ m)\\ n_{3} \equiv a^{l + 3} * x\ (mod\ m) \end{array}

那么也就有

(ai+3∗x)∗(ai+3∗x)∗(ai+3∗x)∗(ai+3∗x)≡n (mod m)ai+j+k+l+12∗x4≡n (mod m)\begin{array}{l} (a^{i + 3} * x) * (a^{i + 3} * x) * (a^{i + 3} * x) * (a^{i + 3} * x) \equiv n\ (mod\ m)\\ a^{i + j + k + l + 12} * x^4 \equiv n\ (mod\ m)\\ \end{array}

i+j+k+l+12i + j + k + l + 12的值，本地测试的话，其实每个一般最多也就4k，保险起见我们直接爆16000，这题的flagflag是比较短的

找到一个模数直接解RSARSA就可以了

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
from tqdm import trange
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
from Crypto.Util.number import *
import sys

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):
    for _ in range(4000):
        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

n = 712650313276602240132329097304430048400352751513310575526412992129597422070848111072491134888258819603174150809317988369755331029009864211216547294646211646094933573124257136163629116984386416188859789467395164897001085191528084740453428500956450177548977865861466055171717564208692444769495508512419622780024874941844495178742341131675818700155796280310646897103229083027529919187454771613414875490462993045875936234591157744167214046734190302287427367403568860249349359776931200150301621481939428066984857258770478004853926288162003818241246878159630318266155498887714140614580751646422502723648142074111613225912644502226694307736726087673647398291980857229829977354067820423709011783907277562489549103977052076140881547728240425069463175586173317054911517453708001448687312406872942899280723472709421452062317503252258181984837591194705354256671714708896675155493168030996749797654707148117051477506855802867089687545890519363621855230477269747205380531049996041867129632051572747028441506474146062043427303954298727328531350438208765938027973006421501568307421856483699068172998763428694958905673708416275143602068221058898394079378423785058886143156065469790907727616640696078658243794470631540358286862899496224884600294835441
e = 65537
c = 445308155915029567991204642441037106636274278969323594266962964897048528466773947276913391974222302661172087064465526779062356615268434642959161607080766074334140739062421641878296527210809334178619685030176261525389226557543594953035919061416292966585184462770190073132725325830890587610808224156896611989260754435566640011008330800266408350415234832430226789140062590779004940578475055195767146347394381212157930691103929079825296986828415158506003438261121628407171546274414046568037336522095223978532053246031668840069046046390952201058199981492454288495640857942797704964843287034359460079316661425483842570190113998195387780579545809621808801626313837113473885818945052873823360056317079785841069224993435527933283918571286444280017102781865312454024328849395335083566145607543834607504822081522250923714391873652357185101163374950977150829214936039230387625706376713934778873385375582488086205462961139042991664546797362021066081938999660281537596860879414252495949608351649066648594254272314188241185715920283526637402373027396529855631498571685297193020517033784357794223831020791070397249992230576960345185544552280142788704673413055403847038488791910041421887897364099871208624646292906015164161354890370666964030412257423
a = 102197201962123846389438942955101245465045811321520032783251514372432272871077


R.<x> = Zmod(2 ^ 256)[]

ps = []
for t in trange(16000):
    f = a ^ (t + 12) * x ^ 4 - n
    roots = f.roots(multiplicities=False)
    if roots:
        for seed in roots:
            seed = ZZ(seed)
            if seed % 2 == 1:
                lcg = LCG(bits=256, c=0, seed = seed, a = a)
                n0 = get_prime(lcg, bits=1024)
                if n0 and n % n0 == 0 and n0 not in ps:
                    phi = (n0 - 1)  
                    d = inverse(65537, phi)
                    print(long_to_bytes(pow(c, d, n0)))  #b'hkcert24{c0mpu71n9_subs3qu3nc3s_0f_g30m3tr1c_s3qu3nc3s_1s_fun}'
                    sys.exit()

如果确实需要全部因子开个多线程即可

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

数据：

1
2
3
4
5
lcg = LCG(bits=256, a=1, c=14258939715516539295587731120991968901228171455016001595761489750577784177213)
n = 279784521303926518544200383491171400996467006054806060652945044514173580730320793076951350168517896308345078513333979433742090849938580604359515861344088875721354836410510396140219655796215325682295239294661185563708496490830500773420871847769568879274978173218440545663363350310752698066412613793738234395676975963986090446949443295350235071286869321557833967521199446244573020803085515110891641843096725596572980675877230459500589604078432572911282759481893882548258867802789628543364574694501159808895930747113406016718685856976531978713324829507636743778130758650283045513372598798114943752532619142439604369129493324057181519512588183783756314385380800844831034863151900295735342816476791991454383732133474515109758087482912794282007801160780475284011802960270750792620686906175026995623082009841402872948756740311519047998978234628057595438481437871594714428834059691733188294695393205472914443179153321670750219104306769911019089432918102588905808629421158434486927928786793524017503900505368724824170796339023214910404096208544407500008089429770878575702088992309354303731919302687039737672125268143820658069899761163750521000478474705014645224845757836226858836333259628284972467671764606702417658922805838428375959908059533
e = 65537
c = 12668023009781840908542456747150790958366008947388222673139950309896560492008423201703814113959062916216738813414905779255815616125482715748800637882572776464413794672305560913420843604427904075596817771292191713968187201485479797042112384390953800170012145372635694385419895184449315436204936393181245447065007450494691263361925589404791904565458416407877820052394996905208559706702586674504665164085593562932792149402776674399837342851449263354042894145700586851308674806581185881411576045932596814585050689676622481653401541955765009732517013919996864475158687111703292317464104677422251199063539026204584634157266215824371162154934075299210675220082034930924899581928745732959112210135371763739653442724659470938281648056607023621212384635978368358089470066114660978000389704285586405309891824263306072117253963803228130111794609335559502199299483268104278641029669532263556375348912538425414244341532656162870453118645106346455731193356791582571147804331894783849241501307040707035938949680381788534081674899875606974239354654393310878542209938345878740320797711262798440736790479007006147569066845667894663218494368548456732889916013895067014484182872120996578247736683746861794081478555452926231507488557048374863197550101866

对于这题，aa的值是1，对于每次lcglcg的输出，它的值就都是cc决定的

那现在就是要确定迭代等式了，先仔细研究一下

1
2
3
4
5
6
7
8
9
10
11
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

对于nn的每个因子，我们假设为n0,n1,n2,n3n_0, n_1, n_2, n_3，对于n0n_0，我们知道它是由4次lcglcg迭代而成的，假设第一次到第四次生成的分别为n00,n01,n02,n03n_{00}, n_{01}, n_{02}, n_{03}

那么他应该满足如下的等式

n0=2768∗n00+2512∗n01+2256n02+n03n_{0} =2^ {768}*n_{00}+ 2^ {512} * n_{01}+2^ {256}n_{02}+n_{03}

现在就是看如何在这类的等式基础上再带入seedseed和cc

改造一下get_primeget\_prime函数（类似上一题）

1
2
3
4
5
6
7
8
9
10
11
12
def get_prime(lcg, bits):
    count = 0
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        count += 1
        if p.bit_length() != bits: continue
        if not is_prime(p): continue
        # print(count)
        return p, count

因为我们上一题已经测试过了，其实count的值一般很小，范围是0~4000左右，显然有点爆破的希望

先来个假设法，我们假设在count1=1count_1 = 1的时候，拿到了n0n_0，这时候到n00n_{00}的时候已经迭代了四次lcglcg，那么n00n_{00}其实可以表示为

n00≡s+c (mod m)n_{00} \equiv s + c\ (mod\ m)

那么对于一般情况，n00n_{00}可以表示为（实际上应该是count1−1count_1 - 1，但是我们只要在return的时候减1就行了，这样就不用写的很复杂了）

n00≡s+(4∗count1+1)∗c (mod m)n_{00} \equiv s + (4 * count_1 + 1)*c\ (mod\ m)

同理，其余的可以表示为

n01≡s+(4∗count1+2)∗c (mod m)n02≡s+(4∗count1+3)∗c (mod m)n03≡s+(4∗count1+4)∗c (mod m)\begin{array}{l} n_{01} \equiv s + (4*count_1 + 2)*c\ (mod\ m)\\ n_{02} \equiv s + (4*count_1 + 3)*c\ (mod\ m)\\ n_{03} \equiv s + (4*count_1 + 4)*c\ (mod\ m) \end{array}

都带入n0n_0之后，未知量也就是只有seedseed和count1count_1小量

对于nn的第二个因子n1n_{1}，它对应的count2count_2其实只有把第一个因子n0n_0返回的count1count_1和这次返回的count2count_2相加就可以了，这样开起来，如果硬爆破，也只要四层循环，如果都设置4000的话，有48比特的数量级，那肯定还是不行的（而且起始等式还蕴含了一个先模mm之后才能乘上27682^{768}之类的），当然如果count1count_1的值不大的时候可行，但是我们要追求的肯定是通法

思路到这边是无了，后面看了wpwp才发现这样一个要点

因为上面的等式，count1count_1的值本身都是不大的，那么我们给等式变形一下

n00≡s+(4∗count1+1)∗c−k00∗mn01≡s+(4∗count1+2)∗c−k01∗mn02≡s+(4∗count1+3)∗c−k02∗mn03≡s+(4∗count1+4)∗c−k03∗m\begin{array}{l} n_{00} \equiv s + (4*count_1 + 1)*c-k_{00} * m \\ n_{01} \equiv s + (4*count_1 + 2)*c-k_{01} * m\\ n_{02} \equiv s + (4*count_1 + 3)*c-k_{02} * m\\ n_{03} \equiv s + (4*count_1 + 4)*c-k_{03} * m \end{array}

同理

n10≡s+(4∗count2+1)∗c−k10∗mn11≡s+(4∗count2+2)∗c−k11∗mn12≡s+(4∗count2+3)∗c−k12∗mn13≡s+(4∗count2+4)∗c−k13∗m\begin{array}{l} n_{10} \equiv s + (4*count_2 + 1)*c-k_{10} * m \\ n_{11} \equiv s + (4*count_2 + 2)*c-k_{11} * m\\ n_{12} \equiv s + (4*count_2 + 3)*c-k_{12} * m\\ n_{13} \equiv s + (4*count_2 + 4)*c-k_{13} * m \end{array}

其余类似，经过测试发现

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
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):
    count = 0
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        count += 1
        if p.bit_length() != bits: continue
        if not is_prime(p): continue
        # print(count)
        return p, count - 1  #这边注意-1


lcg = LCG(bits=256, a=1)
seed = lcg.seed  #注意先拿出最初始的seed，不然后面会变
n0, count1 = get_prime(lcg, bits=1024)
n1, count2 = get_prime(lcg, bits=1024)
n2, count3 = get_prime(lcg, bits=1024)
n3, count4 = get_prime(lcg, bits=1024)

#这边用假设法自己想想就明白了
count2 = count1 + count2 + 1
count3 = count2 + count3 + 1
count4 = count3 + count4 + 1


#第一个因子n0
n00 = (seed + (4 * count1 + 1) * lcg.c) % lcg.m
n01 = (seed + (4 * count1 + 2) * lcg.c) % lcg.m
n02 = (seed + (4 * count1 + 3) * lcg.c) % lcg.m
n03 = (seed + (4 * count1 + 4) * lcg.c) % lcg.m
assert (2 ** 768 * n00 + 2 ** 512 * n01 + 2 ** 256 * n02 + n03) == n0


k00 = (seed + (4 * count1 + 1) * lcg.c - n00) // lcg.m
k01 = (seed + (4 * count1 + 2) * lcg.c - n01) // lcg.m
k02 = (seed + (4 * count1 + 3) * lcg.c - n02) // lcg.m
k03 = (seed + (4 * count1 + 4) * lcg.c - n03) // lcg.m




#第二个因子n1
n10 = (seed + (4 * count2 + 1) * lcg.c) % lcg.m
n11 = (seed + (4 * count2 + 2) * lcg.c) % lcg.m
n12 = (seed + (4 * count2 + 3) * lcg.c) % lcg.m
n13 = (seed + (4 * count2 + 4) * lcg.c) % lcg.m
assert (2 ** 768 * n10 + 2 ** 512 * n11 + 2 ** 256 * n12 + n13) == n1


k10 = (seed + (4 * count2 + 1) * lcg.c - n10) // lcg.m
k11 = (seed + (4 * count2 + 2) * lcg.c - n11) // lcg.m
k12 = (seed + (4 * count2 + 3) * lcg.c - n12) // lcg.m
k13 = (seed + (4 * count2 + 4) * lcg.c - n13) // lcg.m



#第三个因子n2
n20 = (seed + (4 * count3 + 1) * lcg.c) % lcg.m
n21 = (seed + (4 * count3 + 2) * lcg.c) % lcg.m
n22 = (seed + (4 * count3 + 3) * lcg.c) % lcg.m
n23 = (seed + (4 * count3 + 4) * lcg.c) % lcg.m
assert (2 ** 768 * n20 + 2 ** 512 * n21 + 2 ** 256 * n22 + n23) == n2


k20 = (seed + (4 * count3 + 1) * lcg.c - n20) // lcg.m
k21 = (seed + (4 * count3 + 2) * lcg.c - n21) // lcg.m
k22 = (seed + (4 * count3 + 3) * lcg.c - n22) // lcg.m
k23 = (seed + (4 * count3 + 4) * lcg.c - n23) // lcg.m

#第四个因子n3
n30 = (seed + (4 * count4 + 1) * lcg.c) % lcg.m
n31 = (seed + (4 * count4 + 2) * lcg.c) % lcg.m
n32 = (seed + (4 * count4 + 3) * lcg.c) % lcg.m
n33 = (seed + (4 * count4 + 4) * lcg.c) % lcg.m
assert (2 ** 768 * n30 + 2 ** 512 * n31 + 2 ** 256 * n32 + n33) == n3


k30 = (seed + (4 * count4 + 1) * lcg.c - n30) // lcg.m
k31 = (seed + (4 * count4 + 2) * lcg.c - n31) // lcg.m
k32 = (seed + (4 * count4 + 3) * lcg.c - n32) // lcg.m
k33 = (seed + (4 * count4 + 4) * lcg.c - n33) // lcg.m



print(k01 - k00)
print(k02 - k00)
print(k03 - k00)
print()

print(k11 - k10)
print(k12 - k10)
print(k13 - k10)
print()


print(k21 - k20)
print(k22 - k20)
print(k23 - k20)
print()



对于每个因子里面的lcglcg输出的kk，第二三四个与第一个的差值一般不会超过4，在0~4之间波动，一般是0和1的排序或者1、2和3的排序

那这就好办了，我们只要爆破第一个k，然后再0到4的范围了爆破其他k，拿到n00n_{00}的等式之后在模nn下进行copper就可以了（对于这题的cc测试了好像都是0和1，随机的cc的话就是0~4）

实际测试了一下，只有一个小因子的等式是coppercopper不出来的，这边至少需要两个

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 long_to_bytes, inverse
from tqdm import trange
from itertools import product
import sys

lcg = LCG(bits=256, a=1, c=14258939715516539295587731120991968901228171455016001595761489750577784177213)
# n = 279784521303926518544200383491171400996467006054806060652945044514173580730320793076951350168517896308345078513333979433742090849938580604359515861344088875721354836410510396140219655796215325682295239294661185563708496490830500773420871847769568879274978173218440545663363350310752698066412613793738234395676975963986090446949443295350235071286869321557833967521199446244573020803085515110891641843096725596572980675877230459500589604078432572911282759481893882548258867802789628543364574694501159808895930747113406016718685856976531978713324829507636743778130758650283045513372598798114943752532619142439604369129493324057181519512588183783756314385380800844831034863151900295735342816476791991454383732133474515109758087482912794282007801160780475284011802960270750792620686906175026995623082009841402872948756740311519047998978234628057595438481437871594714428834059691733188294695393205472914443179153321670750219104306769911019089432918102588905808629421158434486927928786793524017503900505368724824170796339023214910404096208544407500008089429770878575702088992309354303731919302687039737672125268143820658069899761163750521000478474705014645224845757836226858836333259628284972467671764606702417658922805838428375959908059533
# e = 65537
# c = 12668023009781840908542456747150790958366008947388222673139950309896560492008423201703814113959062916216738813414905779255815616125482715748800637882572776464413794672305560913420843604427904075596817771292191713968187201485479797042112384390953800170012145372635694385419895184449315436204936393181245447065007450494691263361925589404791904565458416407877820052394996905208559706702586674504665164085593562932792149402776674399837342851449263354042894145700586851308674806581185881411576045932596814585050689676622481653401541955765009732517013919996864475158687111703292317464104677422251199063539026204584634157266215824371162154934075299210675220082034930924899581928745732959112210135371763739653442724659470938281648056607023621212384635978368358089470066114660978000389704285586405309891824263306072117253963803228130111794609335559502199299483268104278641029669532263556375348912538425414244341532656162870453118645106346455731193356791582571147804331894783849241501307040707035938949680381788534081674899875606974239354654393310878542209938345878740320797711262798440736790479007006147569066845667894663218494368548456732889916013895067014484182872120996578247736683746861794081478555452926231507488557048374863197550101866


n = 137901271620770530444979467265306698963300379873762646955096755186354930735304918372289140596720917762758847070370483428973514408418628979052575001399839479964236388384592454351581294402142689950836737119521308010939579913209400584937467448247421938473374279964715750954877002425671430016780765357697953826064752412513276880811866073346926187068422905961037266141521558532842200259675483186673784036096622596131632074976481194531719223107572589545599559274477103464671545421480311986792418663985910805561635462899746822165750021328658599427505540376591443283186639370878367744056207172446624121979049120950567268970923980296230400145346204243489375722370599995827229715720981413086514632356491041187470084978029195031472272789013484957818664696491269861826810191401511154574083436305463870243104955212766810116254578188829616717039038123851072791043283813915205633094242230669917580733833013022187199172787831795455232337027846985444402635412955865470658383940533022542477342150474747608498486525772892356938420295056170595791401825514817604040983778387921145190522916223105658320829815228416452840176121351019536463612506154420568382357783865711144677053701669675155684142208086313350112192581112528356523187039314745044226982294781

k00 = 347
k01, k02, k03 = k00 + 0, k00 + 0, k00 + 0
count1 = 705

k10 = 804
k11, k12, k13 = k10 + 0, k10 + 0, k10 + 1
count2 = 1633



R.<s> = Zmod(n)[]
f1 = 2 ^ 768 * ((s + (4 * count1 + 1) * lcg.c) - k00 * 2 ^ 256) + 2 ^ 512 * ((s + (4 * count1 + 2) * lcg.c) - k01 * 2 ^ 256) + 2 ^ 256 * ((s + (4 * count1 + 3) * lcg.c) - k02 * 2 ^ 256) + (s + (4 * count1 + 4) * lcg.c) - k03 * 2 ^ 256
f2 = 2 ^ 768 * ((s + (4 * count2 + 1) * lcg.c) - k10 * 2 ^ 256) + 2 ^ 512 * ((s + (4 * count2 + 2) * lcg.c) - k11 * 2 ^ 256) + 2 ^ 256 * ((s + (4 * count2 + 3) * lcg.c) - k12 * 2 ^ 256) + (s + (4 * count2 + 4) * lcg.c) - k13 * 2 ^ 256
f = f1 * f2

f = f.monic()
f.small_roots(X = 2 ^ 256, beta = 0.374)


不带epsilonepsilon参数也可以coppercopper出来

exp：

1

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

数据：

1
2
3
4
lcg = LCG(bits=256, a=14766004292360945258404852367497617471774948936126805425073927394403062559771, c=101392444572529008969348961056906071660419768871029068095780498478077435335658)
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
c = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945

这次aa和cc都给了，但是seedseed是比较特殊的

1
seed = secrets.randbits(128)<<128 | 1

也就是他模21282^{128}的值为1

关于lcglcg线性推导这边不详细展开

对于第一个因子n0n_0，显然有

n0=2768∗(ai1∗seed+b∗∑j=0i1−1aj)+2512∗(ai1+1∗seed+b∗∑j=0i1aj)+2256∗(ai1+2∗seed+b∗∑j=0i1+1aj)+ai1+3∗seed+b∗∑j=0i1+2aj\begin{array}{l} n_0=2^{768}*(a^{i_1} * seed + b * \sum_{j=0}^{i_1 - 1}{a^j}) + 2^{512}*(a^{i_1 + 1} * seed + b * \sum_{j=0}^{i_1}{a^j}) +\\ 2^{256}*(a^{i_1 + 2} * seed + b * \sum_{j=0}^{i_1 + 1}{a^j}) + a^{i_1 + 3} * seed + b * \sum_{j=0}^{i_1 + 2}{a^j} \end{array}

转为模21282^{128}下

n0≡ai1+3+b∗∑j=0i1+2aj (mod 2128)n_0\equiv a^{i_1 + 3} + b * \sum_{j=0}^{i_1 + 2}{a^j} \ (mod\ 2^{128})

同理可得

n1≡ai2+3+b∗∑j=0i2+2aj (mod 2128)n2≡ai3+3+b∗∑j=0i3+2aj (mod 2128)n3≡ai4+3+b∗∑j=0i4+2aj (mod 2128)\begin{array}{l} n_1\equiv a^{i_2 + 3} + b * \sum_{j=0}^{i_2 + 2}{a^j} \ (mod\ 2^{128})\\ n_2\equiv a^{i_3 + 3} + b * \sum_{j=0}^{i_3 + 2}{a^j} \ (mod\ 2^{128})\\ n_3\equiv a^{i_4 + 3} + b * \sum_{j=0}^{i_4 + 2}{a^j} \ (mod\ 2^{128})\\ \end{array}

显然有

n≡(ai1+3+b∗∑j=0i1+2aj)∗(ai2+3+b∗∑j=0i2+2aj)∗(ai3+3+b∗∑j=0i3+2aj)∗(ai4+3+b∗∑j=0i4+2aj) (mod 2128)\begin{array}{l} n\equiv (a^{i_1 + 3} + b * \sum_{j=0}^{i_1 + 2}{a^j}) * (a^{i_2 + 3} + b * \sum_{j=0}^{i_2 + 2}{a^j}) * (a^{i_3 + 3} + b * \sum_{j=0}^{i_3 + 2}{a^j}) * (a^{i_4 + 3} + b * \sum_{j=0}^{i_4 + 2}{a^j})\ (mod\ 2^{128})\\\\ \end{array}

i1,i2,i3,i4i_1,i_2,i_3,i_4显然都是小量，前面测试过最多也就4k左右，由这个等式其实很容易想到mimt了，只不过这边也不是利用上面的等式硬爆这些小量，因为实际测试的时候会发现计算非常慢（理论应该可行，可能要半小时以上）

这因为这边在模21282^{128}下，seedseed就相当于是1，那么我们可以自己实例化个lcglcg，seedseed​设为1，自行生成4000以内的mimt字典就行了

测试脚本如下：

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
from functools import reduce
from operator import mul
import secrets
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
        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):
    count = 0
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()
        count += 1
        if p.bit_length() != bits: continue
        if not is_prime(p): continue
        print(count)
        return p

def get_my_number(lcg, bits):  #这边直接不检验了，直接拿每四个一对的输出
    while True:
        p = 0
        for i in range(bits//lcg.bits):
            p <<= lcg.bits
            p |= lcg.next()

        return p

a = 14766004292360945258404852367497617471774948936126805425073927394403062559771
b = 101392444572529008969348961056906071660419768871029068095780498478077435335658
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
c = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945

seed = secrets.randbits(128)<<128 | 1
lcg1 = LCG(bits=256, seed=seed, a = a, c = b)
lcg2 = LCG(bits=256, seed=1, a = a, c = b)
t1 = get_prime(lcg1, 1024) % 2 ^ 128

for i in trange(1, 4000):
    t = get_my_number(lcg2, 1024) % 2 ^ 128
    if t1 == t:
        print(i)
        break

实际测试会发现他们输出的结果是一样的，那么我们就可以存取seedseed为1的内容，然后去mimt，这样会快很多

get_my_number没有素性检测是因为lcg内部运算还是在模22562^{256}下的，最后结果才模21282^{128}，所以seedseed为1得到的第一个素数和seedseed是题目的得到的是不一样的

最后mimt后利用上面的等式验证一下后直接在模22562^{256}下解方程就行了，比模nn​简单

(ai1+3∗seed+b∗∑j=0i1+2aj)∗(ai2+3∗seed+b∗∑j=0i1+2aj)∗(ai3+3∗seed+b∗∑j=0i1+2aj)∗(ai4+3∗seed+b∗∑j=0i1+2aj)≡n (mod 2256)(a^{i_1 + 3} * seed + b * \sum_{j=0}^{i_1 + 2}{a^j}) * (a^{i_2 + 3} * seed + b * \sum_{j=0}^{i_1 + 2}{a^j}) * (a^{i_3 + 3} * seed + b * \sum_{j=0}^{i_1 + 2}{a^j}) * (a^{i_4 + 3} * seed + b * \sum_{j=0}^{i_1 + 2}{a^j}) \equiv n\ (mod\ 2^{256})

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
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
from tqdm import trange
from Crypto.Util.number import *

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

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

        return p

a = 14766004292360945258404852367497617471774948936126805425073927394403062559771
b = 101392444572529008969348961056906071660419768871029068095780498478077435335658
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
c = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945

lcg2 = LCG(bits=256, seed=1, a = a, c = b)
ALL = []
for _ in range(4000):
    ALL.append(get_my_number(lcg2, 1024) % 2 ^ 128)

'''
dic = {}
for i1 in trange(4000):
    for i2 in range(i1, 4000):
        dic[ALL[i1] * ALL[i2] % 2 ^ 128] = str(i1) + ' ' + str(i2)

for i3 in trange(4000):
    for i4 in range(i3, 4000):
        tmp = n * inverse(ALL[i3] * ALL[i4], 2 ^ 128) % 2 ^ 128
        if tmp in dic.keys():
            print(dic[tmp], str(i3) + ' ' + str(i4))
            sys.exit()
'''

tmp = [595,1597, 2848,3158]  #小到大排序
tmp = [4 * i + 1 for i in tmp]   #多测测就知道了

i1, i2, i3, i4 = tmp
f = (pow(a, i1 + 3, 2 ^ 128) + b * sum(pow(a, j , 2 ** 128) for j in range(i1 + 3))) \
    * (pow(a, i2 + 3, 2 ^ 128) + b * sum(pow(a, j , 2 ** 128) for j in range(i2 + 3))) \
    * (pow(a, i3 + 3, 2 ^ 128) + b * sum(pow(a, j , 2 ** 128) for j in range(i3 + 3))) \
    * (pow(a, i4 + 3, 2 ^ 128) + b * sum(pow(a, j , 2 ** 128) for j in range(i4 + 3))) % 2 ^ 128
assert f == (n % 2 ^ 128)


R.<seed> = Zmod(2 ^ 256)[]
f = (a ^ (i1 + 3) * seed + b * sum(pow(a, j , 2 ** 256) for j in range(i1 + 3))) \
    * (a ^ (i2 + 3) * seed + b * sum(pow(a, j , 2 ** 256) for j in range(i2 + 3))) \
    * (a ^ (i3 + 3) * seed + b * sum(pow(a, j , 2 ** 256) for j in range(i3 + 3))) \
    * (a ^ (i4 + 3) * seed + b * sum(pow(a, j , 2 ** 256) for j in range(i4 + 3))) - n

for seed in f.roots(multiplicities=False):
    lcg = LCG(bits=256, seed=ZZ(seed), a = a, c = b)
    ps = [get_prime(lcg, bits=1024) for _ in range(4)]
    phi = (ps[0] - 1) * (ps[1] - 1) * (ps[2] - 1) * (ps[3] - 1)
    d = inverse(e, phi)
    m = long_to_bytes(int(pow(c, d, n)))
    if m.isascii():
        print(m)  #b'hkcert24{i5_th1s_y3t_4n0th3r_l33tc0d3_f0ur_sum_qu3s71on?}'
        break

这边sage10.5解f.roots(multiplicities=False)是很快的，如果不是10.5，其实也可以用剪枝，逻辑也挺简单的

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
from functools import reduce
from operator import mul
import secrets
from Crypto.Util.number import isPrime as is_prime
from tqdm import trange
from Crypto.Util.number import *
sys.setrecursionlimit(1000000)

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

a = 14766004292360945258404852367497617471774948936126805425073927394403062559771
b = 101392444572529008969348961056906071660419768871029068095780498478077435335658
n = 310104949044058363811425892282439667555795850923698164575500719920877363952490328278993741848588550303907803963138208625777769116407165079299045658359072735954939955634899149028890186203432587177185672614983999894171325785452784795686085757918290966774324125319406224747711723917236527562556229579589022628862590296281590323788478820477333016394079937231878378358046269624402362566235154381484471820688582120004595351405438024178098190005187895688879764539037795309008703147966413618274215850034115978270168263624156747737483336047033398686990065931568589053366201551840168657333564635190953575770912434947264202860664609208924668470174089395139643640441218757659152083626042918967413234744394606549606305861281752161107561439760204185976944782327736965087510398008449771008025699947582049442588729371212204993669594933838721600502189158688622194652824336960901728311819450912079584032482610919375366829986623070788751982011540521220055895553821778224253746970625666841786339189340344498152279172317609743104777470108401770109956350920020610131660906732383196598286142112787914912796448301345111823730145040316068582039211121377301361760688564938322941885358577303167411970251703604232966219027983536858119778300500933101751641899457
e = 65537
c = 103062216319994633883021726707255505833894115982244229797744500400724941059411346264133479322957473182662752018633592486294774530211270693527482730004815628242002327808204776228223444383519632042858531074466552102288702530352869324049976713089889252600765238196110451324303956172732401402047005544975223308718486936799382134071405038584109821524691964342940757473561547043393942877521141027936710682878315017107714350048208655766169663561363722598270709129397838087810818396682268983758680728353233325680608113581239966748966828100455121487936700949018790286804701500925964419202040562160087415752569883786048654250026952720505649274955681447219364518875892085854376617187428517680579374255991868541726338897567149638047885985817814723274557132684796698662679779677729590702208805883768828626340945484760552452520907126473183457061321026569739763527385628295340908066618403473190885048961117252304808518351740671498261396384433967551138018727839531240932197016466713851341150888734655103395641340466366445201973820121462512449662479632578237405866465926851495594436176622348441495580476338358402531879195673909374090632193981789951544889982768669254824649367936539308980191669227919352771464458152027996758074065744620552247585183945

tmp = [595,1597, 2848,3158]  #小到大排序
tmp = [4 * i + 1 for i in tmp]

i1, i2, i3, i4 = tmp


m = 2**256
PR.<s> = PolynomialRing(Zmod(m))
def f(x):
    return (pow(a, x + 3, m) * s + b * sum([pow(a, i, m) for i in range(x + 3)])) 
g = f(i1) * f(i2) * f(i3) * f(i4)
g = g.change_ring(ZZ)


def find(sl, l):
    tmp = int(sl, 2)

    if g(tmp) % 2 ** l != n % 2 ** l:
        return 

    if l == 256:  #注意检测256的就行，再加255之类的会导致剪的很慢
        ps = []
        lcg = LCG(bits=256, seed=tmp, a = a, c = b)
        ps.append(get_prime(lcg, bits=1024))
        if n % ps[0] == 0:
            ps = ps + [get_prime(lcg, bits=1024) for _ in range(3)]
            phi = (ps[0] - 1) * (ps[1] - 1) * (ps[2] - 1) * (ps[3] - 1)
            d = inverse(e, phi)
            m = long_to_bytes(int(pow(c, d, n)))
            if m.isascii():
                print(m)  #b'hkcert24{i5_th1s_y3t_4n0th3r_l33tc0d3_f0ur_sum_qu3s71on?}'
                sys.exit()

    else:
        find('1' + sl, l + 1)
        find('0' + sl, l + 1)

find('1', 1)

更新于：2025年3月2日

评论

评论区