import math from Crypto.Hash import CMAC from Cryp...

Short version:
This is a CTF-style number-theory / protocol-design crypto challenge, not an elliptic-curve cryptography problem.

You’re supposed to:

1. Understand and break the toy “MAC gate” / verification logic around the modulus.
2. Abuse the custom obfuscation obfuscateSmall (a knapsack/subset-sum-style thing) using chosen inputs.
3. Use standard modular arithmetic / RSA-style reasoning, possibly combined with ordinary integer factoring.

Elliptic curves might show up only as “one possible factoring algorithm”, not as the core concept of the problem.

---

1. High-level picture of the challenge

What the script does conceptually:

• It generates a 2048-bit modulus n as a product of many primes (generator()).
• It computes an AES-CMAC over n and prints it (My m4c&ch3353:).
• It prints a weird “signature” of the internal base (My signature:) that leaks some bits of base.
• The only place the flag actually gets used is in communicate():
  • First obfuscateSmall(flag) is applied → gives some “obfuscated” integer x.
  • Then it prints c = x^base mod n (after some tweaks to ensure gcds are 1).
• You can interact via menu options:
  1. Ask it to encrypt the flag (but only after successful verification).
  2. Try to “verify” a modulus N with a prime factorization you supply.
  3. Use the obfuscation oracle on messages of your choice.
  4. Quit.

So there are really three moving parts:

1. The modulus / MAC / verification dance (n, process, verify).
2. The “base” state updated by power_tower_mod (next, power_tower).
3. The small-bit obfuscation (obfuscateSmall, communicate).

Your job (at a conceptual level) is to get enough control / information that from the final ciphertext you can reconstruct flag.

---

2. What each component is actually doing

2.1. Modulus generator (generator)

python
def generator(self):
    chunk = 128
    while 1:
        data = []
        n = 1
        for i in range(2 * self.security // chunk):
            data.append([getPrime(chunk), 1])
            n *= data[-1][0]
        data.append([2, 2 * self.security - n.bit_length()])
        while n.bit_length() < 2 * self.security:
            n *= 2
        if n.bit_length() == 2 * self.security:
            return n, data

• security = 1024, so 2*security = 2048.
• It picks 16 random 128-bit primes and multiplies them together.
• Then adds a factor of 2^k so the total bitlength of n is exactly 2048.
• data is essentially the prime factorization: [p1, 1], ..., [p16, 1], [2, k].

Concepts here:

• This looks like an RSA-style modulus, but with many smallish primes instead of two big ones.
• The factorization is known to the server (and stored in self.data).

2.2. The MAC on n (process)

python
def process(self):
    x = long_to_bytes(self.n)
    cc = CMAC.new(x[:16], ciphermod=AES)
    self.mac = cc.update(x).hexdigest()

• Key = first 16 bytes of n (x[:16]).
• Message = full bytes of n (x).
• Output = AES-CMAC digest.

Important: AES-CMAC here is being treated as a black-box secure MAC.
You are not expected to break AES or CMAC. That would be wildly out of scope for a CTF problem.

2.3. The “signature” (bit-leaky square)

python
def getSignature(self, toSign):
    return (toSign * toSign) % (1 << (toSign.bit_length() - (self.security // 250)))

• security//250 with security=1024 is 4.
• So if toSign (initially self.base) has bitlength L ≈ 2048, the modulus is 2^(L-4).
• That means you see the lower L−4 bits of base² (top ~4 bits chopped off).

Conceptually this is:

• A partial leakage of base via its square modulo a power of two.
• If needed, you could treat this as a “recover x from x² mod 2^k” problem – that’s classical number theory / Hensel lifting over 2-adic integers, still not elliptic curves.

2.4. The verification logic (verify)

python
def verify(self, N, data):
    self.next()
    if self.verified:
        ...
    if N.bit_length() != 2 * self.security:
        ...
    prev = self.n
    mac = self.mac
    self.n = N
    self.process()
    x = 1
    maxPrime = 0
    for i in range(len(data)):
        data[i][0] = int(data[i][0])
        data[i][1] = int(data[i][1])
        if not isPrime(data[i][0]):
            self.n = prev
            self.mac = mac
            ...
            return False
        x *= pow(data[i][0], data[i][1])
        maxPrime = max(maxPrime, data[i][0])

    if self.mac != mac or x != N or maxPrime.bit_length() > self.security // 5:
        self.n = prev
        self.mac = mac
        ...
        return False

    print("Yayyyyyyyy! big mac got verified! for n =", prev)
    print("Data =", self.data)

    self.data = data
    self.n = N
    self.verified = True
    return True

Key points:

• It first calls self.next() (so the internal base is advanced).
• It stores the current n and mac in prev, mac.
• Temporarily sets self.n = N and recomputes self.mac.
• It checks:
  • All supplied factors are prime.
  • Their product x equals N.
  • N is 2048 bits.
  • The largest prime factor size is ≤ security//5 = 204 bits.
  • And crucially: the new self.mac equals the old mac.

If all that passes:

• It prints the old modulus and its factorization (prev and self.data).
• Then it switches the internal modulus to your N and data.
• And sets self.verified = True.

So:

• verify is a kind of “certify this modulus” gate, guarded by a MAC over the modulus value.
• After a successful verify, you now know the factorization of the original modulus, and you have moved the internal modulus to something you supplied.

This is a protocol / logic-design target, not a “break AES” challenge.
You’re meant to notice where it leaks and how you can abuse that, not to attack CMAC directly.

2.5. The “randomizer” (next, power_tower, power_tower_mod)

python
def next(self):
    self.base = power_tower_mod(self.base, self.data, self.n)

def power_tower(self, x):
    self.next()
    if self.verified:
        print("WTF(What a Freak), you have n do it yourself.")
        return -1
    return power_tower_mod(x, self.data, self.n)

• power_tower_mod is described as computing an infinite power tower: $$x^{x^{x^{\dots}}} \bmod n$$ using self.data (factorization) and self.n.
• It’s used to keep self.base evolving in some complicated but deterministic way.

Notice:

• Before verification, you can query power_tower(x), so you get black-box access to power_tower_mod with the server’s modulus and data.
• After verification, power_tower just refuses to tell you anything useful.

The comment in the code says “There are no vulnerabilities in that function trust me!!” – which usually means for CTF purposes: don’t try to cryptanalyze the power tower, it’s just a state-update PRF-ish thing. The real bugs are elsewhere.

2.6. The obfuscation (obfuscateSmall)

python
def obfuscateSmall(self, m):
    obs = m & ((1 << self.bits) - 1)
    m ^= obs
    final = 0
    for i in range(self.bits):
        if ((obs >> i) & 1):
            final += self.keys[i]
    return m + final

• self.bits = 96.
• self.keys is a list of 96 randomly chosen 96-bit primes.

Mechanics:

1. obs = the lowest 96 bits of m.
2. m ^= obs → this clears those 96 low bits (because m_low ⊕ m_low = 0); high bits stay the same.
3. For each bit i that is 1 in obs, it adds keys[i] to final.
4. Returns m' + final, where m' is m with low 96 bits zeroed.

So you can think of this as:

• Keep the high bits of m intact.
• Replace the low 96 bits by a subset sum of the secret primes keys[i], depending on the original low bits.

This is exactly a knapsack / subset-sum-style encoding of the low 96 bits.

Now look at menu option 3:

python
elif x == 3:
    x = int(input("Enter your message : "))
    print("Here is your obfuscated message : ", big.obfuscateSmall(x))

You get a full chosen-plaintext oracle for this obfuscation with the same keys. That’s super important.

And it turns out to be hilariously weak:

• If you query obfuscateSmall(1 << i) for 0 ≤ i < 96, you get:
  • High bits = 0 (because only the low bit is set).
  • obs = 1 << i, so final = keys[i].
  • m' = 0.
  • So output is just keys[i].

So with at most 96 chosen messages, you can recover all the secret primes keys[0..95].
Once you know them, obfuscation is just a linear system over the integers: you can invert it and recover the original 96 low bits of any obfuscated m.

Conceptually: this part is a broken knapsack / subset-sum scheme, defeated by a chosen-plaintext attack, not by elliptic curves.

2.7. The actual “encryption” (communicate)

python
def communicate(self):
    self.next()
    if self.verified:
        x = self.obfuscateSmall(bytes_to_long(flag))
        while math.gcd(x, n) != 1:
            x += 1
        while math.gcd(self.base, self.n) != 1:
            self.base += 1
        print(f"Here is your obfuscated c: {pow(x, self.base, self.n)}")
    else:
        print("Verification needed.")

After verification:

1. self.next() advances base again.
2. It computes x = obfuscateSmall(flag) – the same obfuscation you can query in menu option 3, just applied to the secret flag.
3. It tweaks x upward until gcd(x, n) == 1.
4. It tweaks self.base upward until gcd(self.base, self.n) == 1.
5. It prints c = x^base mod n.

This is essentially RSA-style encryption:

• Modulus: n (the current self.n).
• Exponent: e = self.base.
• Plaintext: x = obfuscateSmall(flag).

If you know:

• n and its factorization → you can get φ(n) or λ(n).
• e (or enough to make gcd(e, φ(n)) = 1) → you can compute a decryption exponent d = e^{-1} mod φ(n).
• c → you can get x = c^d mod n.
• Then invert obfuscateSmall (using the recovered keys) to get flag.

So the crypto concepts here are:

• Modular exponentiation / RSA.
• Coprimality & gcd.
• Recovering a message from a knapsack-style encoding.

Elliptic curves are not involved in any of that structure.

---

3. So what type of problem is this?

Putting it together, this is a multi-stage CTF cryptography challenge built from:

1. A MAC-protected modulus switch and leak.

   • Category: protocol design / implementation bug.
   • You’re expected to analyze the logic of verify, see what information it leaks, and how/when you can control which modulus is in use and (possibly) know its factorization.

2. A toy knapsack / subset-sum “obfuscation”.

   • Category: broken custom scheme.
   • You exploit the chosen-plaintext oracle to recover all keys[i].
   • Then you can invert the obfuscation on the flag once you know the intermediate value x.

3. RSA-style modular arithmetic.

   • Category: number theory / modular exponentiation.
   • The ciphertext is c = x^base mod n.
   • You want to arrange things so that:
     • n is known and factorable (or chosen by you).
     • You know enough about base to invert the exponentiation (or otherwise recover x).

4. Optional: standard integer factoring.

   • If you end up facing a known modulus without its factors, you might apply standard factoring algorithms.
   • Elliptic curves (Lenstra’s ECM) may be used as a factoring algorithm, but that’s just a computational tool, not the conceptual heart of the challenge.
   • There’s no actual “elliptic-curve cryptography” in the code (no EC points, scalar multiplications, curve parameters, etc.).

So: this is best thought of as a “weird RSA + bad knapsack + buggy verification” problem, not an ECC problem.

---

4. What you’re expected to use (conceptually)

If you’re planning how to tackle it, the toolbox is roughly:

• Careful code auditing / protocol reasoning

  • Understand exactly when self.n, self.data, self.base, self.mac, and self.verified change.
  • See what gets leaked (original n, original factorization) and under what conditions.

• Number theory

  • Bitlengths, prime sizes.
  • Modular exponentiation (pow(x, e, n)).
  • φ(n), λ(n), and RSA-style inversion of an exponent.

• Integer arithmetic / 2-adic reasoning (if you go after getSignature)

  • Working with x² mod 2^k.
  • Possibly reconstructing x from partial information.

• Knapsack / subset-sum reasoning

  • Interpreting obfuscateSmall as: low bits → subset of primes → sum.
  • Using chosen inputs like 1<<i to recover keys[i].
  • Solving for low bits of flag from the known subset sums.

• (Maybe) standard factoring

  • If at any point you get a big modulus whose factors you don’t know, and need them, you’d use something like ECM or GNFS as an implementation detail.

But: elliptic curves are only relevant if you choose to use ECM for factoring.
They are not being used in the cryptosystem itself, and you’re not expected to do elliptic-curve cryptanalysis.

---

If you want, next step we can zoom in on one part (for example, inverting obfuscateSmall, or understanding the verify logic in detail) and I can walk through how you’d systematically attack just that piece.