2025H&NCTF lcgp

97次阅读

共计8865个字符，预计需要花费23分钟才能阅读完成。

题目

题目给出了源码，同样也是非常简短：

import uuid
from Crypto.Util.number import *
import gmpy2
import random

n = getPrime(1024)
flag = b"H&NCTF{" + str(uuid.uuid4()).encode() + b"}"
flag = bytes_to_long(flag)
e = 2024
c = pow(e, flag, n)

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed
        self.a = a
        self.b = b
        self.m = m

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed

lcg = LCG(c, getPrime(256), getPrime(256), getPrime(2048))
random = [lcg.generate() for _ in range(5)]

print(random)
print("n=", n)
# [11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437, 1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636, 147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459, 7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136, 10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074]
# n=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

分析

flag 先转换成了整数，经过以下数学公式运算：

 $c = e^{flag} \; mod \; n$

这是离散对数问题，可以解决。接着对 $$c$$ 进行了变换，利利用 线性同余生成器（LCG） 生成 5 个随机数，并输出这 5 个随机数和 $$n$$ 的值，$$e$$ 也已知。

思路

首先攻击线性同余生成器，参考博客，用以下代码解出 $$a,b,m,c$$。

from functools import reduce
from math import gcd
from Crypto.Util.number import bytes_to_long, long_to_bytes
import gmpy2

# 给定数据
random = [
  11250327355112956284720719987943941825496074893551827972877616718074592862130806975889275745497426515405562887727117008818863728803549848574821067056997423443681347885027000632462241968640893471352200125748453396098854283137158609264944692129301617338233670002547470932851350750870478630955328653729176440142198779254117385657086615711880537380965161180532127926250520546846863536247569437,
  1289730679860726245234376434590068355673648326448223956572444944595048952808106413165882424967688302988257332835229651422892728384363094065438370663362237241013242843898967355558977974152917458085812489310623200114007728021151551927660975648884448177346441902806386690751359848832912607313329587047853601875294089502467524598036474193845319703759478494109845743765770254308199331552085163360820459311523382612948322756700518669154345145757700392164795583041949318636,
  147853940073845086740348793965278392144198492906678575722238097853659884813579087132349845941828785238545905768867483183634111847434793587821166882679621234634787376562998606494582491550592596838027522285263597247798608351871499848571767008878373891341861704004755752362146031951465205665840079918938797056361771851047994530311215961536936283541887169156535180878864233663699607369701462321037824218572445283037132205269900255514050653933970174340553425147148993214797622395988788709572605943994223528210919230924346860415844639247799805670459,
  7426988179463569301750073197586782838200202717435911385357661153208197570200804485303362695962843396307030986052311117232622043073376409347836815567322367321085387874196758434280075897513536063432730099103786733447352512984165432175254784494400699821500026196293994318206774720213317148132311223050562359314735977091536842516316149049281012797103790472349557847649282356393682360276814293256129426440381745354969522053841093229320186679875177247919985804406150542514337515002645320320069788390314900121917747534146857716743377658436154645197488134340819076585888700553005062311578963869641978771532330577371974731136,
  10389979373355413148376869524987139791217158307590828693700943753512488757973725227850725013905113587408391654379552713436220790487026223039058296951420273907725324214990441639760825661323514381671141482079783647253661594138658677104054180912818864005556386671430082941396497098166887200556959866845325602873713813206312644590812141400536476615405444030140762980665885244721798105034497461675317071497925846844396796854201566038890503298824928152263774446268093725702310124363765630370263370678902342200494544961012407826314577564991676315451785987248633724138137813024481818431889574317602521878974976264742037227074,
]
n = 604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

def egcd(a, b):
  if a == 0:
    return (b, 0, 1)
  else:
    g, x, y = egcd(b % a, a)
    return (g, y - (b // a) * x, x)

def modinv(b, n):
  g, x, _ = egcd(b, n)
  if g == 1:
    return x % n

def crack_unknown_increment(states, modulus, multiplier):
  increment = (states[1] - states[0] * multiplier) % modulus
  return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
  multiplier = ((states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
  )
  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))
  return crack_unknown_multiplier(states, modulus)

m, a, b = crack_unknown_modulus(random)

print("Recovered a:", a)
print("Recovered b:", b)
print("Recovered m:", m)

# 步骤 3: 恢复种子 c (即加密结果)
c = (random[0] - b) * modinv(a, m) % m
print("Recovered c:", c)

2025H&NCTF lcgp

最终得到 $$c$$ 为 98136663393066487319477131255488756533037186459124433869847045986870213783395243380337142782779765255670853582334927187474123853371504168896312528278296763527266828907487342102002206806408616944398694810398049626860321901229014612541564249969665358849039818103044159048535403863928440335143886672949700153798350。

接着利用 SageMath 工具解决 离散对数问题，代码如下：

n = 604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059
e = 2024
c = 98136663393066487319477131255488756533037186459124433869847045986870213783395243380337142782779765255670853582334927187474123853371504168896312528278296763527266828907487342102002206806408616944398694810398049626860321901229014612541564249969665358849039818103044159048535403863928440335143886672949700153798350

R = Zmod(n)
e = R(e)
c = R(c)
ord = e.multiplicative_order()
flag = discrete_log(c, e, ord=ord)

print(f"flag = {flag}")

2025H&NCTF lcgp

得到 flag 的值为 2585548131954935324714601390223187094173509829165052609589365162529357667570949567410312552605565626429821。最后使用 print(long_to_bytes(2585548131954935324714601390223187094173509829165052609589365162529357667570949567410312552605565626429821).decode()) 解码即可，得到：

2025H&NCTF lcgp