1. 题目考查技术点

LCG，Coppersmith一元、二元攻击，数论

题目第一个关键的部分

def next(self):
    self.seed = (self.a * self.seed * self.seed + self.b * self.seed + self.c) % self.p
    return self.seed >> 64
print("state1 =", lcg.next())
print("state2 =", lcg.next())

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)
        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
PR. < s1_low, s2_low > = PolynomialRing(Zmod(p))
f = a * ((state1 << 64) + s1_low) ^ 2 + b * ((state1 << 64) + s1_low) + c - (state2 << 64) - s2_low
state1 = small_roots(f, (2 ^ 64, 2 ^ 64), m=3)[0][0] + (state1 << 64)
state2 = small_roots(f, (2 ^ 64, 2 ^ 64), m=3)[0][1] + (state2 << 64)
print(state2)

到这里，我们就可以预测此后的LCG输出了，但是要解出flag，还需要得到最初的seed。这里有两种方法：第一种是通过一元coppersmith求解方程，此方法脚本如下：

# 求seed 方法1
P.<x> = PolynomialRing(Zmod(p))
f = a * x * x + b * x + c - state1
f = f.monic()
print(f.roots())

第二种方法，由于flag的前5位已知，所以我们可以得到如下等式：

$$f

lag[i]-(cipher[i]\bigoplus (lcg.next() >> 192))=k_i*seed

$$

于是，我们可以计算前5位的值，然后计算他们的GCD，就可以得到seed。此方法脚本如下：

# 求seed 方法2
t = []
flag = 'flag{'
lcg = my_LCG()
for i in range(5):
    tmp = int(sha256(flag[i].encode()).hexdigest(), 16)
    t.append(tmp * tmp * tmp - (cipher[i] ^ (lcg.next() >> 192)))
print(GCD(GCD(GCD(t[0], t[1]), t[2]), t[3]))

得到seed就可以解出flag了。

seed = 93161902675685857786932571331038018595140621249413834179036444009740278201203
hashtable = []
flag = ''
lcg = my_LCG()
for i in printable:
   tmp = int(sha256(i.encode()).hexdigest(), 16)
   hashtable.append(pow(tmp, 3, seed))
for i in range(len(cipher)):
   tmp = lcg.next() >> 192
   ind = hashtable.index(tmp ^ cipher[i])
   flag += printable[ind]
print(flag)

END