Embryonic Plant — HackTheBox

Description

A crypto challenge where a custom PRNG based on LCG (Linear Congruential Generator) is combined with RSA encryption. The server:

1. Generates three 768-bit primes p, q, r (with condition p < r and q < r)
2. Computes RSA modulus n = p * q * r
3. Uses p as multiplier and q as increment in LCG with modulus r
4. Outputs 5 consecutive LCG states
5. Encrypts the flag with AES-ECB using key SHA256(long_to_bytes(d)), where d is the RSA private exponent
6. Outputs n, 5 states, and the encrypted flag

server.py

from Crypto.Util.number import getPrime, long_to_bytes, inverse
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256

class RNG:
    def __init__(self, seed):
        self.e = 0x10001
        self.s = seed

        self.r = getPrime(768)
        while True:
            self.p, self.q = getPrime(768), getPrime(768)
            if self.p < self.r and self.q < self.r:
                break

        self.n = self.p * self.q * self.r
        phi = (self.p - 1) * (self.q - 1) * (self.r - 1)
        self.d = inverse(self.e, phi)

    def next(self):
        self.s = (self.s * self.p + self.q) % self.r
        return self.s

def main():
    rng = RNG(getPrime(512))
    rns = [rng.next() for _ in range(5)]

    key = sha256(long_to_bytes(rng.d)).digest()
    cipher = AES.new(key, AES.MODE_ECB)
    enc_flag = cipher.encrypt(pad(open("flag.txt", "rb").read(), 16)).hex()

    print(f'n = {rng.n}')
    print(f's = {rns}')
    print(f'enc_flag = {enc_flag}')

if __name__ == "__main__":
    main()

Server Data

n = 1150602878033962579855587435264463985561012991119468384668592829382526932589050290371404229384060543197185078682129439131294791379084500189190231412746161286693154884895141125456931328624900187394941798752850819099764919782782642330580439797482460200468145633885876719222177123707152556442412289759906022614679836201388628305159526565300196360493229419912194500227149338920601332146540404790692796377022404483802701157711406436843618897489140695102107253071354750636710631299814041318603795393293540269551015332763767683913171219245087255659850460905590634163331241697384677357454776163885003393547816995455512951384945606579995325804502583579173867892740439373075319665455440581859481403053903
s = [1194181135724590315929397382099851721253320971527479487532432173501109537761907741713114873723774928650610296973362872696735288562020017463106691286557392826219185288558801536137192654049666478897366710748464296356830733752510988415, 31426380591662426184590447064387998555608291456216952585360896208704737026291205241216599152515584113271024086240872988211180741801389233254535923885617526085612402544232997514857109445672407534854581574060993434437090934539959516, 37584685120235974231837935172129411514430552023472108029276203384894012122983665837737720432802304685439812117915741229535003326333800172880689092862772080496309574091484963943534926427850064533183894201506708279074560566704292759, 1004001166364963680862365509409110302013325687135947580582960207226383134361098786676605936927176573806063127486111911772996510243998842906106067363062350444198723856366258512848370757982044054323128350525984342093530669656581965702, 1103967668262241312837591587456987006921418992697329349746145242232970298143874165739086070439781778793795257242320365423073697045399567727802612172351347216088757962123686104498466416134111880555812483871124434169981201776586041585]
enc_flag = a5897ee8bccce3f9988f35e8af4f6d608127e533e94c293a3fb3c49ae56b7074b8097535d64ca8568b2ff7614abb73f82c9bb88f7eb5419e41bd31f5498c5d8c8210189c9d079da5960f16f3264e27a8

Analysis

Challenge Structure

The challenge combines two cryptographic constructions:

...