TetCTF 2021 Crypto Writeups

I participated in TetCTF as a member of Super Guesser. 

I was first to [solve all three crypto challenges]. Our team finished 2nd place :)

unimplemented (1st solve)

from collections import namedtuple
from Crypto.Util.number import getPrime
import random
 
Complex = namedtuple("Complex", ["re", "im"])
 
 
def complex_mult(c1, c2, modulus):
    return Complex(
        (c1.re * c2.re - c1.im * c2.im) % modulus,  # real part
        (c1.re * c2.im + c1.im * c2.re) % modulus,  # image part
    )
 
 
def complex_pow(c, exp, modulus):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = complex_mult(result, c, modulus)
        c = complex_mult(c, c, modulus)
        exp >>= 1
    return result
 
 
def generate_key_pair(nbits):
    while True:
        p = getPrime((nbits + 3) // 4)
        q = getPrime((nbits + 3) // 4)
        n = (p ** 2) * (q ** 2)
        if n.bit_length() == nbits:
            return (p, q), n
 
 
def pad(data, length):
    assert len(data) < length
    pad_length = length - len(data) - 1
    pad_data = bytes(random.choices(range(1, 256), k=pad_length))
    sep = b'\x00'
    return pad_data + sep + data
 
 
def unpad(data):
    assert b"\x00" in data, "incorrect padding"
    return data.split(b"\x00", 1)[1]
 
 
def encrypt(public_key, plaintext):
    n = public_key
    plaintext = pad(plaintext, 2 * ((n.bit_length() - 1) // 8))
    m = Complex(
        int.from_bytes(plaintext[:len(plaintext) // 2], "big"),
        int.from_bytes(plaintext[len(plaintext) // 2:], "big")
    )
    c = complex_pow(m, 65537, n)
    return (c.re.to_bytes((n.bit_length() + 7) // 8, "big")
            + c.im.to_bytes((n.bit_length() + 7) // 8, "big"))
 
 
def decrypt(private_key, ciphertext):
    # TODO
    raise Exception("unimplemented")
 
 
def main():
    private_key, public_key = generate_key_pair(2021)
    from secret import flag
 
    print("private_key =", private_key)
    print("public_key =", public_key)
    print("ciphertext =", encrypt(public_key, flag))
 
 
if __name__ == '__main__':
    main()
 
# Output:
# private_key = (128329415694646850105527417663220454989310213490980740842294900866469518550360977403743209328130516433033852724185671092403884337579882897537139175073013,
#                119773890850600188123646882522766760423725010264224559311769920026142724028924588464361802945459257237815241227422748585976629359167921441645714382651911)
# public_key = 236252683050532196983825794701514768601125614979892312308283919527619033977486749228418695923608569040825653688303374445536392159719426640289893369552258923597180869981053519695297428186215135878525530974780390951763007339139013157234202093279764459949020588291928614938201565110828675907781512603972957429701280916745719458738970910789383870206038035515777549907045905872280803964436193687072794878040018900969772972761081589529671158140590712503582004892067155769362463889653489918914397872964087471457070748108694165412065471040954221707557816986272311750297566993468288899523479556822418109112211944932649
# ciphertext = b'\x00h\xbe\x94\x8c\xcd\xdd\x04\x80\xf4\x9d\t\xd8\x8dO\x08\xf1\xd1\xc4\xb9\xa06\xe7\xe3\xb6\xc3\x01+\xa9\xf2\xb9\xe8\x8d\xe6\xc9\x0c_#\x93\x11\xad\x0f\x90\xd3\x0b6\xb0n\x13\xea~"V6\xdbA&\x87\xfe\xa3C\xcb\x16\xae\xd9\x83\xdbU\xc6\x06\xcd\x9a\x94\xa9\xce\x15{d\x95s\xc2\xfb\x90q\xe7\x02\xa2\x081:_C\xc68\x00y\x7fj4@\xd2\xcdE\x06\x943\xbe\xbcC3\xca\x91\xb4\x0e}C\xab\xff?X\xc30u\x069:Dc\xb5\xdc\x9b0%\x98\xbd\xd9\x13\xc0\x02w\xc5\xe5:\xca\xcf\x0c\xab\xc2\x9b}\xab\xd0\xcc\xbc\x0f\x9e9\t\xf7M\xb3\xed\x86\xb5E\x8b\xbc4\xfaH\x9b4\x1c\xc4\xab\xc0\xaf\x8a5XcX\x19K\xed\x19\xe1\x1c\xd0\x1e\x97c\x9fF:L\x9d\x90p\x99\xb8\xde\xcblM\xb3\x80sSL\xe1\xa4\xd6,\x81\xd6\x9c\xf1\xbb\x9c)\xf03\x155\xc0\xd5v\x13\xd6#\xb7\x19\xdea%\xce<\x1c\xf7\xf2!;\xc1\xd7w\xd1\xc8\x8d/\xaew\xa1\x1d\xc5(\xc8\x9d\x82v\xf6j\x90A,e\xbd\xa7]\x10\x8f\xe5\xe7\x93}:\xdf1~\xec\xd0-o`\r\x96\xe4\x03\xb9E\x9fdF\xc3\xf8L\xa0\xda\xf0E[\xf7\x02\xef|*\x08\x8a5pI&\xa9i\x0fZ\xa8\xb3H\xed\xe8v\xc4H\xff\xdb\xcb\x00\xf1\xae\x9bO\x18\xd5\xd8&p\xf5\xf6\xe9\xf1\x1brs\xc2\r\xceZ\xd0\xb24\x97+\x98b\x0e\xbb\xb8.\x8dT\xe4"\xad\xe4\xa3f\xd0M\xbf\xafX\xbb"[\x99\xdap\xa5\xcfT2Wx\x87M\x7f\x99!>B[Q\x04\xf6\x03\xbc\x84\xf4\xdfj\xdd1^I\x1a\x05\x81\x91\xde9Mf*\x8e\x8d\xe64\xf8\x93\x99&yP\xcd\x00!\x82\xab\xbcy\xed\xf1\x13\xd3\x81\xeaz\xbbP>\x9a2\x8c\x08\x0es\xbc\xa9\xf6\xa3\x8c\xb0\xb9t\xd9?\x06@\xc9\x90\xb7\xa7<\x85\xeb\x1a\x88#\x1c\xc3 \xec\xc7\x94d\x99\xd6\x8e>\x06\xf8Y\xf4\x19\xcaI/hy\x18\x8e\x0e8\xf8\r\xbb\xf6\x11\xb9\x8dCWB6 '
 

Introduction

We are given all the key values and the ciphertext, so we just need to work on the decryption algorithm.

Our encryption is a very RSA-like algorithm, with multiplication defined as complex multiplication, with the Re/Im values taken modulo $n$.

Strategy

Let's think about how RSA decryption works first, and start from there. Denote $n=pq$ with $p, q$ primes.

We know that $\text{gcd}(a, p) = 1$ implies $a^{p-1} \equiv 1 \pmod{p}$. We know that $\text{gcd}(a, q) = 1$ implies $a^{q-1} \equiv 1 \pmod{q}$.

Therefore, we see that with $\text{gcd}(a, p)=1$ and $\text{gcd}(a, q)=1$, we have $a^{(p-1)(q-1)} \equiv 1 \pmod{pq}$.

This is because $a^{(p-1)(q-1)}$ must be $1$ modulo each $p, q$, so we may apply Chinese Remainder Theorem.

Now, with the encryption exponent $e$, we can get decryption exponent by taking modulo inverse mod $(p-1)(q-1)$.

This problem should not be so different. We'll denote $a \equiv b \pmod{n}$ if $a, b$ has same Re/Im values $\pmod{n}$.

We should find a function $f$ that guarantees $a^{f(p)} \equiv 1 \pmod{p^2}$ if $\text{gcd}(a, p) = 1$, and $a^{f(q)} \equiv 1 \pmod{q^2}$ if $\text{gcd}(a, q) = 1$.

• Immediate Question : What does $\text{gcd}$ mean in this setting? I'll explain this later.

Anyways, if we find such $f$, we know $a^{f(p)f(q)} \equiv 1 \pmod{p^2q^2}$ must hold for the same reason.

We can then find the modular inverse of $e = 65537$ mod $f(p)f(q)$ and get the decryption exponent.

For now, let's just hope that we have $\text{gcd}(a, p) = \text{gcd}(a, q) = 1$ for our ciphertext. (whatever that gcd means)

Now we have to find what the function $f$ is all about. There are at least 5 ways to do this. (I used Method 2.)

Finish

• Method 1. We simply read the code of unevaluated.
  
• It's easy to see that "unevaluated" challenge gives us some discrete logarithm problem.
• If we read it more carefully, we see that $g = (re, im)^{24}$ precisely has order $pqr = p(p-1)(p+1)/24$. 
• Therefore, we can see that $(re, im)$ has an order that divides $p(p-1)(p+1)$.
• We can now guess that $f(p) = p^3 - p$ should work, and it indeed does. Done :)

• Method 2. We run some tests for small $p$, and guess our way to find $f$.
• Let's just fix some small primes $p$ and see when $a^{???} \equiv 1 \pmod{p^2}$. 
• Let's look at the minimum exponent that satisfies the modulo equation. It can be seen that it is a divisor of $p(p-1)(p+1)$.
• Therefore, we can now guess that $f(p) = p^3 - p$ should work, and it indeed does. Done :)

• Method 3. We actually do some mathematics to find our answer.
• We define $\text{gcd}(a+bi, p)$ as $\text{gcd}(a^2+ b^2, p)$. This is highly motivated by the norm map.

• We first claim that for odd primes $p$ and $\text{gcd}(a+bi, p)=1$, $(a+bi)^{p^2-1} \equiv 1 \pmod{p}$. 
• Case 1. $p \equiv 3 \pmod{4}$.
• This is the easy case, as our complex numbers can be now viewed as elements of $\mathbb{F}_{p^2}$.
• Since the multiplicative group of this extension field has $p^2-1$ elements, we are now done.
• Case 2. $p \equiv 1 \pmod{4}$.
• We prove that $(a+bi)^{p-1} \equiv 1 \pmod{p}$. This is enough to prove our result.
• Denote $(a+bi)^{p-1} \equiv c + di \pmod{p}$, and note that $(a-bi)^{p-1} \equiv c - di \pmod{p}$ by taking conjugates.
• Now we take an $x$ such that $x^2 \equiv -1 \pmod{p}$. We can now substitute $i$ as $x$ without an issue.
• This shows $1 \equiv (a+bx)^{p-1} \equiv c+ dx \pmod{p}$, and $1 \equiv (a-bx)^{p-1} \equiv c - dx \pmod{p}$.
• Combining these two equations directly gives us $c = 1$, and $d = 0$. Note that $x$ is nonzero.
• Note that $a+bx$ being nonzero $\pmod{p}$ is equivalent to $\text{gcd}(a^2 + b^2, p) = 1$. 

• Now we prove the main result : $(a+bi)^{p^3 - p} \equiv 1 \pmod{p^2}$ if $\text{gcd}(a+bi, p) = 1$.
• We know that $(a+bi)^{p^2-1} \equiv 1 \pmod{p}$, so we can write $(a+bi)^{p^2-1} \equiv 1 + pc \pmod{p^2}$ for some complex number $c$.
• Now we directly use Binomial Theorem to get $(a+bi)^{p^3-p} \equiv (1+pc)^p \equiv 1 \pmod{p^2}$. Done.
• This shows that we can use $f(p) = p^3-p$, with proof. It should work. Done :)

• Method 4. Google with keywords "Gaussian Integers" and "RSA"
• This leads to various resources, such as https://www.diva-portal.org/smash/get/diva2:1170568/FULLTEXT01.pdf

• Method 5. Lagrange's Theorem
• We start by defining $\text{gcd}(a+bi, p) = \text{gcd}(a^2 +b^2, p)$, just like in Method 3.
• It's not hard to prove that the elements with $\text{gcd}(a^2+b^2, p)=1$ form a multiplicative group. 
• Here, we look at elements $a+bi$ in $\pmod{p^2}$. Therefore, there are at most $p^4$ elements.
• If we count the number of elements with $\text{gcd}(a^2 + b^2, p)=1$, we can use that as $f(p)$, by Lagrange's Theorem.
• In other words, we use that $a^{|G|} = e$ for all finite groups $G$, identity element $e$, and element $a \in G$. 
• Case 1. $p \equiv 3 \pmod{4}$.
• For $\text{gcd}(a^2+b^2,p) \neq 1$, we need both $a, b$ to be multiples of $p$. There are $p^2$ such elements.
• Therefore, we may take $f(p) = p^4 - p^2$ in this case. Done!
• Case 2. $p \equiv 1 \pmod{4}$.
• We only need to look at $0 \le a, b < p$ and multiply by $p^2$ in the end.
• If $a=0$, only $b=0$ satisfies $\text{gcd}(a^2+b^2,p) \neq 1$. If $1 \le a < p$, there are $2$ such $b$s. 
• Therefore, there are $p^2-1-2(p-1) = (p-1)^2$ solutions. Multiplying by $p^2$, we have $f(p) = p^2(p-1)^2$. 
• Since casework is boring, we just take the LCM of the two expressions and select $f(p) = p^2(p-1)^2(p+1)$. Done.
• Looking at the flag, the mentions of "counting" seems to imply that this method is the intended solution.

I wish (at least) Method 1 was blocked by allowing contestants to see "unevaluated" only after solving this challenge. :(

private_key = (128329415694646850105527417663220454989310213490980740842294900866469518550360977403743209328130516433033852724185671092403884337579882897537139175073013,
               119773890850600188123646882522766760423725010264224559311769920026142724028924588464361802945459257237815241227422748585976629359167921441645714382651911)
public_key = 236252683050532196983825794701514768601125614979892312308283919527619033977486749228418695923608569040825653688303374445536392159719426640289893369552258923597180869981053519695297428186215135878525530974780390951763007339139013157234202093279764459949020588291928614938201565110828675907781512603972957429701280916745719458738970910789383870206038035515777549907045905872280803964436193687072794878040018900969772972761081589529671158140590712503582004892067155769362463889653489918914397872964087471457070748108694165412065471040954221707557816986272311750297566993468288899523479556822418109112211944932649
ciphertext = b'\x00h\xbe\x94\x8c\xcd\xdd\x04\x80\xf4\x9d\t\xd8\x8dO\x08\xf1\xd1\xc4\xb9\xa06\xe7\xe3\xb6\xc3\x01+\xa9\xf2\xb9\xe8\x8d\xe6\xc9\x0c_#\x93\x11\xad\x0f\x90\xd3\x0b6\xb0n\x13\xea~"V6\xdbA&\x87\xfe\xa3C\xcb\x16\xae\xd9\x83\xdbU\xc6\x06\xcd\x9a\x94\xa9\xce\x15{d\x95s\xc2\xfb\x90q\xe7\x02\xa2\x081:_C\xc68\x00y\x7fj4@\xd2\xcdE\x06\x943\xbe\xbcC3\xca\x91\xb4\x0e}C\xab\xff?X\xc30u\x069:Dc\xb5\xdc\x9b0%\x98\xbd\xd9\x13\xc0\x02w\xc5\xe5:\xca\xcf\x0c\xab\xc2\x9b}\xab\xd0\xcc\xbc\x0f\x9e9\t\xf7M\xb3\xed\x86\xb5E\x8b\xbc4\xfaH\x9b4\x1c\xc4\xab\xc0\xaf\x8a5XcX\x19K\xed\x19\xe1\x1c\xd0\x1e\x97c\x9fF:L\x9d\x90p\x99\xb8\xde\xcblM\xb3\x80sSL\xe1\xa4\xd6,\x81\xd6\x9c\xf1\xbb\x9c)\xf03\x155\xc0\xd5v\x13\xd6#\xb7\x19\xdea%\xce<\x1c\xf7\xf2!;\xc1\xd7w\xd1\xc8\x8d/\xaew\xa1\x1d\xc5(\xc8\x9d\x82v\xf6j\x90A,e\xbd\xa7]\x10\x8f\xe5\xe7\x93}:\xdf1~\xec\xd0-o`\r\x96\xe4\x03\xb9E\x9fdF\xc3\xf8L\xa0\xda\xf0E[\xf7\x02\xef|*\x08\x8a5pI&\xa9i\x0fZ\xa8\xb3H\xed\xe8v\xc4H\xff\xdb\xcb\x00\xf1\xae\x9bO\x18\xd5\xd8&p\xf5\xf6\xe9\xf1\x1brs\xc2\r\xceZ\xd0\xb24\x97+\x98b\x0e\xbb\xb8.\x8dT\xe4"\xad\xe4\xa3f\xd0M\xbf\xafX\xbb"[\x99\xdap\xa5\xcfT2Wx\x87M\x7f\x99!>B[Q\x04\xf6\x03\xbc\x84\xf4\xdfj\xdd1^I\x1a\x05\x81\x91\xde9Mf*\x8e\x8d\xe64\xf8\x93\x99&yP\xcd\x00!\x82\xab\xbcy\xed\xf1\x13\xd3\x81\xeaz\xbbP>\x9a2\x8c\x08\x0es\xbc\xa9\xf6\xa3\x8c\xb0\xb9t\xd9?\x06@\xc9\x90\xb7\xa7<\x85\xeb\x1a\x88#\x1c\xc3 \xec\xc7\x94d\x99\xd6\x8e>\x06\xf8Y\xf4\x19\xcaI/hy\x18\x8e\x0e8\xf8\r\xbb\xf6\x11\xb9\x8dCWB6 '
 
p = private_key[0]
q = private_key[1]
n = public_key
e = 65537
 
v = (p ** 3 - p) * (q ** 3 - q)
d = inverse(e, v) 
 
re = bytes_to_long(ciphertext[ : len(ciphertext) // 2])
im = bytes_to_long(ciphertext[len(ciphertext) // 2 : ])
 
ctxt = Complex(re, im)
 
ptxt = complex_pow(ctxt, d, n)
 
print(long_to_bytes(ptxt.re) + long_to_bytes(ptxt.im))
 
# TetCTF{c0unt1ng_1s_n0t_4lw4ys_34sy-vina:*100*48012023578024#}

uncollidable (4th solve)

import json
import os
from hashlib import sha256
from typing import Callable, Dict
 
H: Callable[[bytes], bytes] = lambda s: sha256(s).digest()
 
 
def get_mac(key: bytes, data: bytes) -> bytes:
    """Just a MAC generation function similar to HMAC.
    Reference link: https://en.wikipedia.org/wiki/HMAC#Implementation
    """
    if len(key) >= 32:
        key = H(key)
 
    if len(key) < 32:
        key += b"\x00" * (32 - len(key))
 
    inner_pad = bytearray(32)
    outer_pad = bytearray(32)
    for i in range(32):
        inner_pad[i] = key[i] ^ 0x20
        outer_pad[i] = key[i] ^ 0x21
 
    return H(outer_pad + H(inner_pad + data))
 
 
class SecureStorage:
    """Changes on data stored in this storage can be detected :) """
 
    def __init__(self, debug=False):
        self.keys: Dict[str, bytes] = {}  # key ID -> key
        self.data: Dict[bytes, bytes] = {}  # MAC -> data
        self.debug = debug
        if debug:
            # when debug mode is on, unique arguments to `store_data` will be
            # logged.
            self.store_data_args = set()
 
    def generate_key(self, key_id: str) -> None:
        """Generate a new key."""
        if key_id in self.keys:
            raise Exception("duplicated key id")
        self.keys[key_id] = os.urandom(32)
 
    def import_key(self, key_id: str, key: bytes) -> None:
        """Import an external key."""
        if key_id in self.keys:
            raise Exception("duplicated key id")
        self.keys[key_id] = key
 
    def store_data(self, key_id: str, data: bytes) -> bytes:
        """Store data and return a MAC that can be used to retrieve the data
        later."""
        if key_id not in self.keys:
            raise Exception("key not found")
 
        key = self.keys[key_id]
        if self.debug:
            self.store_data_args.add((key, data))
 
        mac = get_mac(key, data)
        if mac in self.data:
            raise Exception("data already stored")
 
        self.data[mac] = data
        return mac
 
    def retrieve_data(self, key_id: str, mac: bytes) -> bytes:
        """Retrieve data previously stored with `store_data`."""
        if key_id not in self.keys:
            raise Exception("key not found")
        if mac not in self.data:
            raise Exception("data not found")
 
        key = self.keys[key_id]
        data = self.data[mac]
        if get_mac(key, data) != mac:
            raise Exception("data has been tampered")
        return data
 
    def report_bug(self) -> int:
        """Claim your bounty here :) """
        if self.debug:
            # check for a massive collision bug
            if len(self.store_data_args) >= 10 and len(self.data) == 1:
                # check if collisions happened through different key sizes
                key_lengths = [len(key) for (key, _) in self.store_data_args]
                if min(key_lengths) < 32 <= max(key_lengths):
                    # Congrats :)
                    from secret import flag
                    return int.from_bytes(flag, "big")
        return 0
 
 
def main():
    ss = SecureStorage(debug=True)
    for _ in range(100):
        try:
            request = json.loads(input())
 
            if request["action"] == "generate_key":
                key_id = request["key_id"]
                ss.generate_key(key_id)
                print(json.dumps({}))
 
            if request["action"] == "import_key":
                key_id = request["key_id"]
                key = bytes.fromhex(request["key"])
                ss.import_key(key_id, key)
                print(json.dumps({}))
 
            elif request["action"] == "store_data":
                key_id = request["key_id"]
                data = bytes.fromhex(request["data"])
                mac = ss.store_data(key_id, data)
                print(json.dumps({"mac": mac.hex()}))
 
            elif request["action"] == "retrieve_data":
                key_id = request["key_id"]
                mac = bytes.fromhex(request["mac"])
                data = ss.retrieve_data(key_id, mac)
                print(json.dumps({"data": data.hex()}))
 
            elif request["action"] == "report_bug":
                print(json.dumps({"bounty": ss.report_bug()}))
 
        except EOFError:
            break
        except Exception as err:
            print(json.dumps({"error": str(err)}))
 
 
if __name__ == '__main__':
    main()
 

Introduction

We basically need a big collision of the MAC - 10 (key, data) values that map to a single MAC value.

We also need to use at least one key with length less than 32, and at least one key with length no less than 32 as well. 

Strategy & Finish

Let's actually look at the MAC code. We see that some preparation are done to make the key exactly 32 bytes.

If the length is at least 32 bytes, we apply SHA256. If not, we append some zeros at the end to make it 32 bytes.

We immediately get some collision cooking - a key full of zeros will lead to a same MAC if the key length is less than 32 bytes.

Of course, this is easily generalizable - if the "final" 32 byte key ends with a lot of zeros, we get a lot of collisions!

This is extremely suspicious - we just need a key that is at least 32 bytes to go along with it.

This means we need a 32 byte value with SHA256 ending with a lot of zeros - 9 bytes of it, to be exact.

Now this is a problem that I have seen before - DragonCTF's bitflip2. SHA256 ending with a lot of zeros leads us to bitcoin PoW.

We can find a bunch of values with SHA256 ending with 8 bytes worth of zeros in bitcoin. 

Luckily, the value we (Perfect Guesser) used at the time to solve bitflip2 already had 9 bytes of zeros in the end in the SHA256.

This solves the problem. This was a very good review exercise for me :)

HOST = "139.162.5.141"
PORT = 5555
 
r = remote(HOST, PORT)
 
key_id = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
 
print(long_to_bytes(61342502866914327869718742967850222962760441300896006743258488289386736694996435440480147718715690291226752007898889408599107845232272253))
tt = '294724a63e0fda8c731d9612b0a8e8b9bc0ec087ca9920c8488c5dd1df94ebff'
tt = bytes.fromhex(tt)
 
data = "1234"
 
for i in range(0, 10):
    key = '294724a63e0fda8c731d9612b0a8e8b9bc0ec087ca9920c8488c5dd1df94ebff'
    if i >= 1:
        key = bytes.fromhex(sha256(bytes.fromhex(key)).hexdigest())
        key = key[:-i]
        key = key.hex()
    request = {
        "action": "import_key",
        "key_id": key_id[i],
        "key": key
    }
    r.sendline(json.dumps(request))
    print(r.readline())
    request = {
        "action": "store_data",
        "key_id": key_id[i],
        "data": data
    }
    r.sendline(json.dumps(request))
    print(r.readline())
 
request = {
    "action": "report_bug"
}
 
r.sendline(json.dumps(request))
 
print(r.readline())
 
# TetCTF{HM4C_c4n_b3_m1sus3d-viettel:*100*718395803842748#}

unevaluated (1st solve)

from collections import namedtuple
from Crypto.Util.number import getPrime, isPrime, getRandomRange
 
Complex = namedtuple("Complex", ["re", "im"])
 
 
def complex_mult(c1, c2, modulus):
    return Complex(
        (c1.re * c2.re - c1.im * c2.im) % modulus,  # real part
        (c1.re * c2.im + c1.im * c2.re) % modulus,  # image part
    )
 
 
def complex_pow(c, exp, modulus):
    result = Complex(1, 0)
    while exp > 0:
        if exp & 1:
            result = complex_mult(result, c, modulus)
        c = complex_mult(c, c, modulus)
        exp >>= 1
    return result
 
 
class ComplexDiffieHellman:
    @staticmethod
    def generate_params(prime_length):
        # Warning: this may take some time :)
        while True:
            p = getPrime(prime_length)
            if p % 4 == 3:
                if p % 3 == 2:
                    q = (p - 1) // 2
                    r = (p + 1) // 12
                    if isPrime(q) and isPrime(r):
                        break
                else:
                    q = (p - 1) // 6
                    r = (p + 1) // 4
                    if isPrime(q) and isPrime(r):
                        break
        n = p ** 2
        order = p * q * r
        while True:
            re = getRandomRange(1, n)
            im = getRandomRange(1, n)
            g = complex_pow(Complex(re, im), 24, n)
            if (
                    complex_pow(g, order, n) == Complex(1, 0)
                    and complex_pow(g, order // p, n) != Complex(1, 0)
                    and complex_pow(g, order // q, n) != Complex(1, 0)
                    and complex_pow(g, order // r, n) != Complex(1, 0)
            ):
                return g, order, n
 
    def __init__(self, params=None, prime_length=128, debug=False):
        if not debug:
            raise Exception("security unevaluated")
        if params is None:
            params = ComplexDiffieHellman.generate_params(prime_length)
        self.g, self.order, self.n = params
 
    def get_public_key(self, private_key):
        return complex_pow(self.g, private_key, self.n)
 
    def get_shared_secret(self, private_key, other_public_key):
        return complex_pow(other_public_key, private_key, self.n)
 
 
def main():
    from os import urandom
    private_key = urandom(32)
    k = int.from_bytes(private_key, "big")
 
    cdh = ComplexDiffieHellman(debug=True)
    print("g =", cdh.g)
    print("order =", cdh.order)
    print("n =", cdh.n)
    print("public_key =", cdh.get_public_key(k))
 
    # Solve the discrete logarithm problem if you want the flag :)
    from secret import flag
    from Crypto.Cipher import AES
    if len(flag) % 16 != 0:
        flag += b"\x00" * (16 - len(flag) % 16)
    print("encrypted_flag = ",
          AES.new(private_key, AES.MODE_ECB).encrypt(flag))
 
 
if __name__ == "__main__":
    main()
 
# Output:
# g = Complex(re=20878314020629522511110696411629430299663617500650083274468525283663940214962,
#             im=16739915489749335460111660035712237713219278122190661324570170645550234520364)
# order = 364822540633315669941067187619936391080373745485429146147669403317263780363306505857156064209602926535333071909491
# n = 42481052689091692859661163257336968116308378645346086679008747728668973847769
# public_key = Complex(re=11048898386036746197306883207419421777457078734258168057000593553461884996107,
#                      im=34230477038891719323025391618998268890391645779869016241994899690290519616973)
# encrypted_flag = b'\'{\xda\xec\xe9\xa4\xc1b\x96\x9a\x8b\x92\x85\xb6&p\xe6W\x8axC)\xa7\x0f(N\xa1\x0b\x05\x19@<T>L9!\xb7\x9e3\xbc\x99\xf0\x8f\xb3\xacZ:\xb3\x1c\xb9\xb7;\xc7\x8a:\xb7\x10\xbd\x07"\xad\xc5\x84'
 

Introduction

We are given the same setup from "unimplemented". We are solving $g^x \equiv target \pmod{n}$ given $g, target, n$.

We also know that the order of $g$ is $order = p \cdot q \cdot r = p(p-1)(p+1)/24$, where $p, q, r$ are all primes.

We now have to solve a discrete logarithm problem to get a private key, which is used to encrypt our flag using AES.

Strategy 

First, some basic steps. From $n = p^2$, we can directly calculate the value of $p$.

From the parameter generation process, we can also calculate $q, r$. 

I actually computed $p$ by $\text{gcd}(n, order)$, and factorized $qr = order/ p$ using alpetron. 

UPD: This is why my values of $q, r$ in this writeup and solution code is swapped instead of the original $q, r$ given in the code.

Anyway, we now know $p, q, r$ and can focus on our task, the discrete logarithm.

• Idea 1. The flaw in parameter generation.
• There is actually a very important flaw in parameter generation. 
• Note that $p, q, r$ are around 128 bits. Therefore, the order $pqr$ is around $128 \cdot 3 = 384$ bits.
• However, the private key used in the AES and the discrete logarithm problem is 32 bytes, i.e. $256$ bits.
• Pohlig-Hellman style thinking shows we can compute $x \pmod{p}$, $x \pmod{q}$, $x \pmod{r}$ separately. 
• Because $x$ is $256$ bits, we can simply solve two of these three problems and combine using CRT!!

• Idea 2. The (multiplicative) norm map $N(a+bi) = a^2 + b^2$. 
• Note : I proved stuff for "unimplemented" (i.e. Method 3) after I solved all three challenges. However, the proof ideas are used here.
• The norm map allows us to move from weird complex number stuff to values in $\pmod{p}$, where we are more comfortable.
• Maybe this idea reminds us of MOV attack? I don't know. Anyways, let's finish the problem.

Finish

Let's first look at $x \pmod{r}$. We note that $r|(p-1)$, so norm map will work nicely here.

• We want $(g^{pq})^x \equiv target^{pq} \pmod{n}$, so $N(g^{pq})^x \equiv N(target^{pq}) \pmod{p}$. 
• If we calculate $N(g^{pq})$ and $N(target^{pq})$ we get values that are nonzero, and also not equal to $1$.
• This is expected to happen, since $pq$ is relatively prime to $p-1$ and $g$ has high order. 
• Therefore, we can solve the discrete logarithm problem in $\mathbb{F}_p$ to get information on $x$.
• We also see that (with Sage) $N(g^{pq})$ has order $r$ in $\mathbb{F}_p$. Therefore, we get the entire $x \pmod{r}$ here.

Next, we'll look at $x \pmod{p}$. If we get this, we'll solve the problem.

• We want $(g^{qr})^x \equiv target^{qr} \pmod{n}$. Note that $24qr \equiv 0 \pmod{p^2-1}$. 
• Here, the $24$ comes from the fact that $g$ is actually defined as $(re, im)^{24}$ for some $re, im$. 
• This shows that, from proof in Method 3 above, we must have $g^{qr} \equiv target^{qr} \equiv 1 \pmod{p}$.
• Therefore, we have $N(g^{qr}) \equiv N(target^{qr}) \equiv 1 \pmod{p}$ as well. 
• However, computation shows us that $N(g^{qr}) , N(target^{qr})$ are not $1 \pmod{p^2}$. This is not unexpected.
• We can now solve $x \pmod{p}$ with $N(g^{qr})^x \equiv N(target^{qr}) \pmod{p^2}$. 
• We simply note that $(1+pa)^x \equiv 1 +pax \pmod{p^2}$ using Binomial Theorem.
• Write $N(g^{qr}) \equiv 1 +pa \pmod{p^2}$ and $N(target^{qr}) \equiv 1 + pb \pmod{p^2}$, where $a, b$ are nonzero $\pmod{p}$.
• We now have, simply, $ax \equiv b \pmod{p}$. This can be solved with modular inverse.
• This looks quite like the Paillier Cryptosystem (which I learned by solving zer0ptsCTF Dirty Laundry) so that's cool.

When I first solved this problem, I found most of these insight by experiments. 

I did think of the norm map first, solved $\pmod{r}$ part based on it, and was quite surprised when $N(g^{qr})$ was $1 \pmod{p}$. 

Then I realized that I could use Binomial Theorem to solve the challenge. Looking back on "unimplemented" during write-up, I found out that most of my "surprises" during the solve was not actually surprising facts :) This is a very nice challenge, so thanks to ndh.

UPD: After some discussion with ndh in the CryptoHack server, it turns out I overcomplicated this problem a bit.

We can just solve for $N(g)^x \equiv N(target) \pmod{p^2}$ and solve the discrete logarithm problem here. :P

UPD: After even more discussion, it turns out that the above discrete logarithm in $\pmod{p^2}$ is not that easy.

Refer to the CryptoHack discord, or the writeup by Mystiz here, and TheBlueFlame121 here for more details. Highly suggest you read them.

These two writeups linked above have some important facts about discrete logarithm calculation in Sage in general. :)

In CryptoHack discord #ctf-challenges, $\$$in has a summarization on this subject, and there are even more discussions with smart people!

UPD: CryptoHack discord #ctf-challenges has a very in-depth analysis and discussion on this challenge, a must read.

UPD: CryptoHack has posted a solid review on these challenges. See https://blog.cryptohack.org/tetctf-2021

def norm(x):
    return x.re * x.re + x.im * x.im
 
 
g = Complex(re=20878314020629522511110696411629430299663617500650083274468525283663940214962,
            im=16739915489749335460111660035712237713219278122190661324570170645550234520364)
order = 364822540633315669941067187619936391080373745485429146147669403317263780363306505857156064209602926535333071909491
n = 42481052689091692859661163257336968116308378645346086679008747728668973847769
public_key = Complex(re=11048898386036746197306883207419421777457078734258168057000593553461884996107,
                     im=34230477038891719323025391618998268890391645779869016241994899690290519616973)
encrypted_flag = b'\'{\xda\xec\xe9\xa4\xc1b\x96\x9a\x8b\x92\x85\xb6&p\xe6W\x8axC)\xa7\x0f(N\xa1\x0b\x05\x19@<T>L9!\xb7\x9e3\xbc\x99\xf0\x8f\xb3\xacZ:\xb3\x1c\xb9\xb7;\xc7\x8a:\xb7\x10\xbd\x07"\xad\xc5\x84'
 
p = 206109322179011817882783419945552366363
q = 17175776848250984823565284995462697197
r = 103054661089505908941391709972776183181
 
# solve for mod p
p_g = complex_pow(g, q * r, n)
p_enc = complex_pow(public_key, q * r, n)
 
# norm : a^2 + b^2
c_1 = norm(p_g) % (p * p)
c_2 = norm(p_enc) % (p * p)
 
c_1 = (c_1 - 1) // p
c_2 = (c_2 - 1) // p
 
val_p = (c_2 * inverse(c_1, p)) % p 
 
# solve for mod r
r_g = complex_pow(g, p * q, n)
r_enc = complex_pow(public_key, p * q, n)
print(norm(r_g) % p, norm(r_enc) % p)
 
'''
p = 206109322179011817882783419945552366363
g = GF(p)(176015758946526802279559144270141551487) # r_g
enc = GF(p)(28369875517706698292997652748535456248) # r_enc

print(g.multiplicative_order()) # this equals r
print(enc.log(g)) # 26176203815975575469683683780455489251
'''
 
val_r = 26176203815975575469683683780455489251
val_tot, pr = CRT(val_p, p, val_r, r)
 
for i in range(0, 100):
    private_key = long_to_bytes(val_tot + i * pr)
    flag = AES.new(private_key, AES.MODE_ECB).decrypt(encrypted_flag)
    if b"TetCTF" in flag:
        print(flag)
        break
 
# TetCTF{h0m0m0rph1sm_1s_0ur_fr13nd-mobi:*100*231199111007#}