OKAY with this information you have: The program ...

Here’s a solver skeleton that follows exactly the attack you described and talks to

nc remote.infoseciitr.in 4001

You’ll have to fill in a couple of mathematically-heavy parts (factoring with ECM / base recovery / de-obfuscation) depending on the exact version of your brother’s challenge, but all the plumbing around the menu, oracles, and data-flow is done.

I’ll assume:

• Python ≥3.8
• You’re okay installing pwntools, sympy and pycryptodome locally.
• The remote prints:
  • My m4c&ch3353: <hex>
  • My signature: <int>
  • (Possibly also n = <int> – if not, you’ll hard-code or parse it some other way.)

High-level structure

The solver does:

1. Connect to the service, read MAC + signature (+ optionally n if printed).
2. Leak all 96 primes used in obfuscateSmall by querying option 3 with inputs 2^i.
3. Obtain / factor n (either from the service output or from a file / constant).
4. Call verify once with the real (n, factorization) so the service dumps the original factorization (and fixes self.n, self.data, self.verified).
5. Call communicate to get the RSA-like ciphertext c.
6. Offline:
   • Reconstruct base (encryption exponent) from the signature.
   • Re-implement the infinite power tower modulo n (if needed) and follow the same sequence of next() calls as the server to get the final exponent e.
   • Compute φ(n) (or λ(n)), then d = e^{-1} mod φ(n).
   • Decrypt: x = c^d mod n.
   • Undo obfuscation using the 96 primes to recover the flag.

Below is a reasonably clean implementation with a few TODO hooks where you’ll plug your “math heavy” pieces.

Full solver skeleton (Python)

python
#!/usr/bin/env python3
#
# bigMac solver skeleton
#
# Needs:
#   pip install pwntools pycryptodome sympy
#

from pwn import remote
from Crypto.Util.number import inverse, long_to_bytes
from math import gcd, lcm
from sympy import factorint

HOST = "remote.infoseciitr.in"
PORT = 4001

SECURITY = 1024
SMALL_BITS = 96


# ---------------------------------------------------------------------------
# Helpers for number theory
# ---------------------------------------------------------------------------

def phi_from_factors(factors):
    """
    Compute Euler's totient φ(n) from prime factorization.
    factors: dict {p: e}
    """
    phi = 1
    for p, e in factors.items():
        if p == 2:
            # φ(2^e) = 2^(e-1)  for e >= 1
            phi *= 1 << (e - 1)
        else:
            phi *= (p - 1) * (p ** (e - 1))
    return phi


def carmichael_from_factors(factors):
    """
    Compute Carmichael λ(n) from prime factorization.
    λ(p^k) = φ(p^k) for odd p
    λ(2) = 1
    λ(4) = 2
    λ(2^k) = 2^(k-2) for k >= 3
    λ(n) = lcm(λ(p_i^e_i))
    """
    def lam_prime_power(p, e):
        if p == 2:
            if e == 1:
                return 1
            if e == 2:
                return 2
            return 1 << (e - 2)
        # odd prime
        return (p - 1) * (p ** (e - 1))

    curr = 1
    for p, e in factors.items():
        curr = lcm(curr, lam_prime_power(p, e))
    return curr


# ---------------------------------------------------------------------------
# Infinite power tower (tetration) modulo n
# ---------------------------------------------------------------------------

def infinite_power_tower_mod(a, n, lam_cache=None):
    """
    Compute ^∞ a mod n, using the Carmichael-chain idea.

    This is a generic implementation; in the real challenge, 'hidden.power_tower_mod'
    presumably does something equivalent but more optimized, possibly using 'data'.

    Assumes gcd(a, n) == 1 for correctness of the λ-reduction.
    """
    if n == 1:
        return 0

    if lam_cache is None:
        lam_cache = {}

    def lam(m):
        if m in lam_cache:
            return lam_cache[m]
        # For this problem, m will always be of the form λ^k(n) where n
        # is a product of small primes -> factoring is feasible.
        fac = factorint(m)
        val = carmichael_from_factors(fac)
        lam_cache[m] = val
        return val

    # Recursive definition:
    #   E(m) = a^(E(λ(m))) mod m
    #   Stop when λ(m) == 1 (exponent collapses).
    def E(m):
        if m == 1:
            return 1
        lm = lam(m)
        if lm == 1:
            # exponent effectively ≡ 1 (mod 1), but we know it's non-zero
            return pow(a, 1, m)
        e = E(lm)
        # ensure exponent is not 0 modulo λ(m)
        if e == 0:
            e += lm
        return pow(a, e, m)

    return E(n)


# ---------------------------------------------------------------------------
# Recover base from signature (you may need to tweak this for your exact chall)
# ---------------------------------------------------------------------------

def recover_base_candidates(signature, security=SECURITY):
    """
    WARNING:
        This depends heavily on the exact implementation of getSignature.

        In the code you pasted:
            return (toSign * toSign) % (1 << (toSign.bit_length() - (security//250)))

        In the *description* you gave, it's described as "essentially leaking the
        exponent by revealing all but a few MSBs via a power-of-two modulus".

        If, in your real instance, getSignature actually behaves like:
            signature = base % 2^(L - security//250)
        then you can reconstruct base up to the top (security//250) bits.

        The function below assumes that: signature == base mod 2^k,
        where k = base.bit_length() - security//250.

        It returns all 2^(security//250) candidates (e.g. 16 when security=1024).
    """
    # number of bits chopped off from the top
    top_bits = security // 250       # = 4 for security=1024
    low = signature
    k = low.bit_length()
    # approximate full length
    L = k + top_bits

    candidates = []
    for hi in range(1 << top_bits):
        base = low + (hi << k)
        candidates.append(base)
    return candidates


# ---------------------------------------------------------------------------
# Obfuscation helpers
# ---------------------------------------------------------------------------

def leak_small_keys(io, bits=SMALL_BITS):
    """
    Use option 3 ("Obfuscating") with m = 1 << i.

    For 0 <= i < bits:
        obs = 1<<i
        m ^= obs -> 0
        final = keys[i]
        return final

    So each query directly reveals keys[i].
    """
    keys = []
    for i in range(bits):
        io.recvuntil(b"Choose:")
        io.sendline(b"3")
        io.recvuntil(b"Enter your message : ")
        io.sendline(str(1 << i).encode())
        line = io.recvline().decode().strip()
        # "Here is your obfuscated message :  <int>"
        val = int(line.split()[-1])
        keys.append(val)
        print(f"[+] key[{i}] = {val}")
    return keys


def deobfuscate_small(y, keys, bits=SMALL_BITS):
    """
    Invert obfuscateSmall(m):

        obs = m & ((1<<bits) - 1)
        m ^= obs       # clear low bits
        final = sum(keys[i] for i with bit i of obs = 1)
        return m + final

    Given y = obfuscateSmall(m) (possibly plus a very small increment
    to make gcd(y, n) == 1), and given keys[], we want m.

    Naively this is a subset-sum of dimension 96, which is too big to brute-force.

    For the actual challenge, you have a few options:

      * If the increment loop almost always exits immediately (overwhelmingly likely),
        you can *assume* y is exactly m_hat + Σ key_i * bit_i, and then solve the
        subset-sum **mod 2^bits** with a clever algorithm (2-adic / bit DP / lattice).

      * Alternatively, you can implement a meet-in-the-middle or an LLL-based subset sum
        solver, or simply patch your local copy of the chall to print the flag’s low
        96 bits for debugging and skip this stage 🙂

    For now, this is a placeholder that raises, so the rest of the script is structurally
    correct but you know what has to be filled in.
    """
    raise NotImplementedError("deobfuscate_small: implement subset-sum / bit-DP to invert obfuscation.")


# ---------------------------------------------------------------------------
# Remote I/O helpers
# ---------------------------------------------------------------------------

def connect():
    io = remote(HOST, PORT)
    return io


def read_banner(io):
    """
    Read the initial 'My m4c&ch3353' and 'My signature' lines.
    If your real instance also prints n, parse it here.
    """
    line = io.recvline().decode().strip()
    assert "m4c&ch3353" in line
    mac = line.split()[-1]

    line = io.recvline().decode().strip()
    assert "My signature" in line
    signature = int(line.split()[-1])

    print(f"[+] MAC = {mac}")
    print(f"[+] signature = {signature}")

    # If challenge prints n up-front, parse it here, e.g.:
    #   line = io.recvline().decode().strip()
    #   if "n =" in line:
    #       n = int(line.split("=")[1])
    # else set n = None and load from some other source.
    n = None
    return mac, signature, n


def do_verify(io, n, factors):
    """
    Call menu option 2 (verify) with the real modulus and its factorisation.
    This should print the *original* factorisation and set verified=True.
    """
    io.recvuntil(b"Choose:")
    io.sendline(b"2")
    io.recvuntil(b"Give me the MY modulus : ")
    io.sendline(str(n).encode())

    io.recvuntil(b"Enter prime factorization in format")
    parts = [f"[{p}, {e}]" for p, e in factors.items()]
    s = "-".join(parts)
    io.sendline(s.encode())

    # Read until we see the next menu.
    out = io.recvuntil(b"1: Communicate.", drop=False).decode()
    print("[+] verify() output:")
    print(out)


def get_ciphertext(io):
    """
    Call menu option 1 (communicate) after verify() succeeded.
    This should give us the RSA-like ciphertext.
    """
    io.recvuntil(b"Choose:")
    io.sendline(b"1")
    io.recvuntil(b"Here is your obfuscated c:")
    line = io.recvline().decode().strip()
    c = int(line.split()[-1])
    print(f"[+] ciphertext c = {c}")
    return c


# ---------------------------------------------------------------------------
# Main solve logic
# ---------------------------------------------------------------------------

def main():
    io = connect()
    mac, signature, n_from_server = read_banner(io)

    # 1) Leak all small primes used in obfuscateSmall
    keys = leak_small_keys(io, bits=SMALL_BITS)

    # 2) Get or set modulus n.
    #
    #    The code you posted never prints n at startup, but verify() only
    #    accepts the *original* modulus (thanks to the MAC check), which
    #    means in practice the real challenge *must* give you n somehow
    #    (otherwise you'd have to break AES-CMAC).
    #
    #    If your instance prints it, use n_from_server; otherwise hard-code
    #    it from a previous run or put it in a file.
    #
    if n_from_server is not None:
        n = n_from_server
    else:
        # TODO: set n here if not printed by the service
        # Example:
        # n = int(open("modulus.txt").read().strip())
        raise ValueError("Modulus n is not known – parse it from the service or hard-code it.")

    print(f"[+] n (modulus) = {n}")

    # 3) Factor n with ECM / factorint (many ~128-bit primes => ECM-friendly)
    print("[*] factoring n (this may take a while)...")
    factors = factorint(n)     # sympy uses Pollard Rho / ECM internally
    print(f"[+] factorization of n: {factors}")

    # 4) Call verify() with the correct modulus and factorization
    do_verify(io, n, factors)

    # 5) Get ciphertext from communicate()
    c = get_ciphertext(io)

    # 6) Compute φ(n) and λ(n)
    phi_n = phi_from_factors(factors)
    lam_n = carmichael_from_factors(factors)
    print(f"[+] φ(n)  = {phi_n}")
    print(f"[+] λ(n)  = {lam_n}")

    # 7) Reconstruct base candidates from signature
    base_candidates = recover_base_candidates(signature, security=SECURITY)
    print(f"[+] {len(base_candidates)} candidate base values from signature")

    # 8) For each candidate, try to emulate the same 'next()' sequence
    #    the server uses and see which one yields a plausible flag.

    #   Sequence of base updates in chall:
    #       base0 = getPrime()*getPrime()
    #       print signature(base0)
    #       next()           # during __init__
    #       ...
    #       verify(): next()
    #       communicate(): next()
    #
    #   So encryption exponent is base3 (plus a small increment to make gcd(base3,n)=1).
    #

    flag_bytes = None

    for idx, base0 in enumerate(base_candidates):
        print(f"[*] Trying base candidate {idx+1}/{len(base_candidates)}")

        base1 = infinite_power_tower_mod(base0, n)
        base2 = infinite_power_tower_mod(base1, n)
        base3 = infinite_power_tower_mod(base2, n)

        # simulate the "while gcd(self.base, self.n) != 1: self.base += 1"
        e = base3
        while gcd(e, n) != 1:
            e += 1

        try:
            d = inverse(e, phi_n)
        except ValueError:
            # not invertible mod φ(n), so this can't be the real exponent
            print("    [-] base candidate not coprime to φ(n)")
            continue

        x = pow(c, d, n)  # this should be obfuscateSmall(flag) (mod n)
        # with high probability x < n, so it's exact, not reduced.

        # Try to undo the obfuscation
        try:
            m = deobfuscate_small(x, keys, bits=SMALL_BITS)
        except NotImplementedError:
            print("[!] deobfuscate_small not implemented – stop here.")
            return

        fb = long_to_bytes(m)

        # crude sanity check for a CTF-style flag
        if b"flag{" in fb or b"FLAG{" in fb or b"inctf{" in fb:
            print("[+] Looks like a valid flag:")
            print(fb)
            flag_bytes = fb
            break
        else:
            print("    [-] candidate base did not yield a plausible flag")

    if flag_bytes is None:
        print("[-] Exhausted all base candidates without finding a valid flag.")
    else:
        print(f"[+] Final flag: {flag_bytes}")


if __name__ == "__main__":
    main()

What you still need to fill in / adjust

Because your description and the pasted code don’t line up perfectly, there are three “hard” pieces that you (or your brother 😈) have to make precise:

1. How exactly getSignature behaves.

   • If in the real challenge it is:

     python
     return toSign % (1 << (toSign.bit_length() - (security // 250)))

     then recover_base_candidates above is the right approach: you get all possibilities for the chopped-off top bits (16 when security=1024), and you test them.

   • If it really uses base**2 mod 2^k, you’ll need a 2-adic / Hensel-style reconstruction step (as mentioned in your own write-up). You can still plug that into recover_base_candidates().

2. How you get n.

   • The posted code never prints n, but verify’s CMAC check effectively forces you to reuse the original modulus, which means in practice the real instance has to give you n somewhere (or you’d be doing a CMAC forgery).
   • Either parse it in read_banner, or just paste it from a previous run into the script.

3. The deobfuscate_small inverse.

   • Mathematically, given y and the 96 primes, you’re solving a subset-sum equation modulo 2^96. There are known ways to do this with lattice reduction or bit-DP, and the problem size is small enough for an offline solver.
   • For a homelab challenge, you can also cheat: instrument your local copy of chall.py to print both flag and obfuscateSmall(flag) once, log the low bits mapping, and then hard-code the reverse in your solver.

If you like, you can send me what the actual server prints on startup (the first few lines after connecting), and I can tighten the parsing and the recover_base_candidates part to match it more precisely.