[5月公开赛] mylcg

题目

from Crypto.Util.number import *
from hashlib import sha256
f = open('flag.txt')
flag = f.read()
f.close()
assert flag[:5] == 'flag{'
seed = getPrime(256)


class my_LCG:
    def __init__(self):
        self.p = getPrime(512)
        self.a = getRandomNBitInteger(256)
        self.b = getRandomNBitInteger(256)
        self.c = getRandomNBitInteger(256)
        self.seed = seed

    def next(self):
        self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p
        return self.seed >> 64

    def output(self):
        print("a =", self.a)
        print("b =", self.b)
        print("c =", self.c)
        print("p =", self.p)


lcg = my_LCG()
lcg.output()
print("state1 =", lcg.next())
print("state2 =", lcg.next())
cipher = []
for i in flag:
    tmp = int(sha256(i.encode()).hexdigest(), 16)
    cipher.append(pow(tmp, 3, seed) ^ (lcg.next() >> 192))
print(cipher)
# a = 68823589009570846705623113091430161477799561031575612135516351257937127579444
# b = 76549169049080319489163980188997771079750670038002598167961495813084486794567
# c = 99215492498952976642031024510129092308042391285395704888838178561670205468882
# p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031
# state1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507
# state2 = 269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352
# [104612880565354761070267231258959974017713136013091552542621012009434344223091, 75867315122609665862412321569592448016548595925558860261941234225747875658355, 106901597652387441116797426235259979167755542628252028460970918870852084813985, 22282265919236743389726915885827434932651977730848876965702592028838506934802, 113663688553403244683128957504190135685760214545373190153400188368329624810824, 16387987427743919688629484112748920627537972533590712542304182257404148095432, 42660781848852863873070244368035358673436082124276647936063403560054320824947, 31162780219880567100421404229662317404195331726681121575505050872412728752846, 4387263209760294127327273998365291139136756172378440265726369942465661809226, 9486548512905762310741629559650376499881990751841396019470492813536817972788, 48175096956218645396129797881617184816956038092368660196837813749510220209020, 44832999096333655680734980423005605365074861714291594434259782779054037518357, 91949111038768792853022977677056688517414191501656202462769670180011454736134, 84362160451115508526234487916725793664590119636637539810168371139175756722218, 37991151261861388606427583658548923882501719664397171054526120281654768250027, 76502569176155441262877857713986290804857527394931115027371407239085302418015, 69004590108972326779999503375035935629144187797049165946644383062664912505793, 4882509736578426220928083701456224217596136409513934115208162112269124095036, 43923135793747042362291047632803354256532285967402459802384563909906286571537, 60099118217689452210082521471087211926434931778809056323284225098458442535387, 41772186654628607473153061053630877342481864865985327695842922897386493117840, 79556569085671906788310296380605892417410665990711208999213184300355584627493, 113368724525353223298893326950045576507359981373213697703045622403941359594816, 59568498228965811827206375159844085215141410061444029744235874177744506595963, 5813871055160958965491186951684884799390692165774935048726620511285107065171, 101481471612354001038968281423076176339698400003836978206153754002016784653117, 96713934756979037100616702408060142461624534046186352589457317850269578096978, 50360544372106359495068645870868114000049436655822775857718387298804448386259, 74343018392522018803983491192044402773734077434586754153316411931268932053849, 85064649783728020457864819723803995069342386266325766064354175704654032312470, 35444692928369969109775411420972206587166544062593932622816977149910920025593, 88364976585873094910882074779610461514853793492269703066264952338524869329015, 57171789241051208558861663926443006215165105080980300229007074324952708746414, 53398702677161874182117493992247921340773468735882139055903326524685751323223, 22084022599630141597766375557874162908749682780683228274573161676243137075985, 67811375554342446963928136891489894009025011339123405492350978811178609371520, 54279152372926754185972096972067394007518618911313269898203907795172124806761, 71337965908378379886587542454943435140109212437982933800558803691194797247858, 91631795365993438211094618411930046881699597378889861280702841447103987549686, 55725715889928044127700572038972949057067144434626788557169321659022938298621, 68379770126152524442093415542514227284857840135092144556912468864495685413179, 40664875356285535027116296315063139118439996515430069978781752466656941376294]

线性同余加RSA的一道题,用题目中给出的两个state可以求出完整的lcg.next()

构造下面的方程

$$a(state1+x)^2+b(state1+x)+c-(state2+y)\equiv0\pmod{p}$$

用二元coppersmith方法求解

sage脚本:

from sage.all import *
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
 
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
 
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    #print(G)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
 
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
 
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []


a = 68823589009570846705623113091430161477799561031575612135516351257937127579444
b = 76549169049080319489163980188997771079750670038002598167961495813084486794567
c = 99215492498952976642031024510129092308042391285395704888838178561670205468882
p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

state1 = 664406108637237317109372377546194289077117372665932150107678757303243619963182733408311739663233548725195723884930183442927293177078507
state2 = 269639459994260392015105629865659210391196381140872041084737976688017858324308345528702533444116282512066085580909718347778743354754352

seed1 = state1 << 64
seed2 = state2 << 64
PR.<x, y> = PolynomialRing(Zmod(p))
f = a*(seed1 + x)^2 + b*(seed1 + x) + c - (seed2 + y)

roots = small_roots(f, (2^64, 2^64), 3, 2)

print(roots)

x = int(roots[0][0])
y = int(roots[0][1])

seed1 = seed1 + x
seed2 = seed2 + y
print(seed1, '\n', seed2)
'''
[(4696961136341886199, 3558746530789497743)]
seed1 = 12256129447040382014545559694380637404973427806615255879415755813326872746484293878302279841562237263671079585622657761243463788893311797799201976142603511 
seed2 = 4973970110687366614999601116072392521603538210827787686343160442628599822457642083916901548842513568140815369122306139402715676098474240043517438534130575
'''

拿到state1和state2后,自然想到去求seed然后这道题就解决了。

构造一元二次同余方程

$$f=ax^2+bx+c-state1\pmod{p}$$

这是一个一般的二次同余方程,模数p又是素数,可以转化成二次剩余式来求解

$$y^2\equiv d\pmod{p},(y=2x+a^{-1}b,\quad d=(a^{-1})^2(b^2-4a(c-seed1)))$$

$$p\equiv3\pmod{4}$$

所以
$$y=d^{\frac{p+1}{4}}$$

当然可以直接用sage

PR.<x> = PolynomialRing(Zmod(p))

f = a*x^2 + b*x + c - seed1

root = f.roots()
print(root)

seed = []
for i in root:
    if i[0] < 2^256:
        seed.append(i[0])
seed = seed[0]
#seed = 93161902675685857786932571331038018595140621249413834179036444009740278201203
lcg = my_LCG(seed)

assert lcg.next() == state1
assert lcg.next() == state2

最后就可以求得flag每一位的sha256值,爆破就行了,不过要注意的是,由于有模运算,所以RSA解出来的不一定等于实际的sha256值,测出来是最后5位不对,要加上一个seed

from hashlib import sha256
from gmpy2 import *
from Crypto.Util.number import *
import string

table = string.printable

class my_LCG:
    def __init__(self):
        self.p = p
        self.a = a
        self.b = b
        self.c = c
        self.seed = seed

    def next(self):
        self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p
        return self.seed >> 64

a = 68823589009570846705623113091430161477799561031575612135516351257937127579444
b = 76549169049080319489163980188997771079750670038002598167961495813084486794567
c = 99215492498952976642031024510129092308042391285395704888838178561670205468882
p = 12775129699668988473759438271274836254349225413222075887429387682336494103348583050672280757042383792640084197832605411237644937815012509935794275313643031

state1 = 12256129447040382014545559694380637404973427806615255879415755813326872746484293878302279841562237263671079585622657761243463788893311797799201976142603511 
state2 = 4973970110687366614999601116072392521603538210827787686343160442628599822457642083916901548842513568140815369122306139402715676098474240043517438534130575
cipher = [104612880565354761070267231258959974017713136013091552542621012009434344223091, 75867315122609665862412321569592448016548595925558860261941234225747875658355, 106901597652387441116797426235259979167755542628252028460970918870852084813985, 22282265919236743389726915885827434932651977730848876965702592028838506934802, 113663688553403244683128957504190135685760214545373190153400188368329624810824, 16387987427743919688629484112748920627537972533590712542304182257404148095432, 42660781848852863873070244368035358673436082124276647936063403560054320824947, 31162780219880567100421404229662317404195331726681121575505050872412728752846, 4387263209760294127327273998365291139136756172378440265726369942465661809226, 9486548512905762310741629559650376499881990751841396019470492813536817972788, 48175096956218645396129797881617184816956038092368660196837813749510220209020, 44832999096333655680734980423005605365074861714291594434259782779054037518357, 91949111038768792853022977677056688517414191501656202462769670180011454736134, 84362160451115508526234487916725793664590119636637539810168371139175756722218, 37991151261861388606427583658548923882501719664397171054526120281654768250027, 76502569176155441262877857713986290804857527394931115027371407239085302418015, 69004590108972326779999503375035935629144187797049165946644383062664912505793, 4882509736578426220928083701456224217596136409513934115208162112269124095036, 43923135793747042362291047632803354256532285967402459802384563909906286571537, 60099118217689452210082521471087211926434931778809056323284225098458442535387, 41772186654628607473153061053630877342481864865985327695842922897386493117840, 79556569085671906788310296380605892417410665990711208999213184300355584627493, 113368724525353223298893326950045576507359981373213697703045622403941359594816, 59568498228965811827206375159844085215141410061444029744235874177744506595963, 5813871055160958965491186951684884799390692165774935048726620511285107065171, 101481471612354001038968281423076176339698400003836978206153754002016784653117, 96713934756979037100616702408060142461624534046186352589457317850269578096978, 50360544372106359495068645870868114000049436655822775857718387298804448386259, 74343018392522018803983491192044402773734077434586754153316411931268932053849, 85064649783728020457864819723803995069342386266325766064354175704654032312470, 35444692928369969109775411420972206587166544062593932622816977149910920025593, 88364976585873094910882074779610461514853793492269703066264952338524869329015, 57171789241051208558861663926443006215165105080980300229007074324952708746414, 53398702677161874182117493992247921340773468735882139055903326524685751323223, 22084022599630141597766375557874162908749682780683228274573161676243137075985, 67811375554342446963928136891489894009025011339123405492350978811178609371520, 54279152372926754185972096972067394007518618911313269898203907795172124806761, 71337965908378379886587542454943435140109212437982933800558803691194797247858, 91631795365993438211094618411930046881699597378889861280702841447103987549686, 55725715889928044127700572038972949057067144434626788557169321659022938298621, 68379770126152524442093415542514227284857840135092144556912468864495685413179, 40664875356285535027116296315063139118439996515430069978781752466656941376294]
seed = 93161902675685857786932571331038018595140621249413834179036444009740278201203

lcg = my_LCG()
lcg.next()
lcg.next()
d = inverse(3, seed - 1)

flag = b''
for i in range(len(cipher)):
    tmp = cipher[i] ^ (lcg.next() >> 192)
    tmp = pow(tmp, d, seed)
    if i >= (len(cipher) - 5):
        tmp += seed
    for j in table:
        if int(sha256(j.encode()).hexdigest(), 16) == tmp:
            flag += j.encode()
            #print(flag)
            break

print(flag)
# flag{c4787f1-a99e-4c-cbe-d08484f1}

[NPUCTF2020]babyLCG

buuoj下载来的附件还要自己把文件格式改成zip

题目 enc.py

from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

class LCG:
    def __init__(self, bit_length):
        m = getPrime(bit_length)
        a = getRandomRange(2, m)
        b = getRandomRange(2, m)
        seed = getRandomRange(2, m)
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed
        
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state
    
    def export_key(self):
        return self._key


def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    f = open("key", "w")
    f.write(str(key))
    return rand_iter


def leak_data(rand_iter):
    f = open("old", "w")
    for _ in range(20):
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter


def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)


def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    encrypt(rand_iter)


if __name__ == "__main__":
    main()

跟pwnhub五月公开赛的题目一样是LCG,这道题给了20组输出,但只需要前两个就可以算出seed,后面的可以用来验证seed的正确性

计算seed

from sage.all import *
import itertools

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
 
    R = f.base_ring()
    N = R.cardinality()
 
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
 
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    #print(G)
    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)
 
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
 
    B = B.dense_matrix().LLL()
 
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
 
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

a = 107763262682494809191803026213015101802
b = 153582801876235638173762045261195852087
m = 226649634126248141841388712969771891297

state1 = 7800489346663478448
state2 = 11267068470666042741

seed1 = state1 << 64
seed2 = state2 << 64
PR.<x, y> = PolynomialRing(Zmod(m))
f = a*(seed1 + x) + b - (seed2 + y)

roots = small_roots(f, (2^64, 2^64), 3, 1)

print(roots)
x = int(roots[0][0])
y = int(roots[0][1])

seed1 = seed1 + x
seed2 = seed2 + y
print(f'seed1 = {seed1}')
print(f'seed2 = {seed2}')
PR.<x> = PolynomialRing(Zmod(m))

f = a*x + b - seed1

root = f.roots()
print(root)
'''
[(6524632084338656352, 1510343526611795913)]
seed1 = 143893630627599013214247726129298228320
seed2 = 207840728539338564937360506842813415369
[(73991202721494681711496408225724067994, 1)]
'''

得到seed = 73991202721494681711496408225724067994,后面的就很简单了,虽然还有一个AES_CBC加密但是并不需要自己写解密的代码,直接用Crypto库的就行

from Crypto.Util.number import *
from Crypto.Cipher import AES

Seed = 73991202721494681711496408225724067994

def decrypt(ciphertext, rand_iter):
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)

    m = cipher.decrypt(ciphertext)
    return m.decode()

class LCG:
    def __init__(self):
        m = 226649634126248141841388712969771891297
        a = 107763262682494809191803026213015101802
        b = 153582801876235638173762045261195852087
        seed = Seed
        self._key = {'a':a, 'b':b, 'm':m}
        self._state = seed
        
    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state

rand_iter = LCG()
f = open('old.txt', 'r')
for i in range(20):
    assert rand_iter.next() >> 64 == int(f.readline())
f.close()
print(f'seed = {Seed}')

f = open('ct.txt', 'rb')
ciphertext = f.read()
f.close()
print(decrypt(ciphertext, rand_iter))
# npuctf{7ruc4t3d-L(G-4nd-LLL-4r3-1nt3r3st1ng}