> For the complete documentation index, see [llms.txt](https://l0mb4rd.gitbook.io/home/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://l0mb4rd.gitbook.io/home/ctf-stuff/cscctfv6-writeups/cryptography.md). # Cryptography ## RSA-TZ Mode \[Easy] ### Handouts: ```python from Crypto.Util.number import * Flag = b'CSCCTF{SXMgSFRVIHNvIGJhZCBhZnRlcmFsbD8}' Flag = bytes_to_long(Flag) p = getPrime(512) q = getPrime(512) while p >= q: q = getPrime(512) n = p*q e = 0x10001 def encrypt(m): return pow(m, e, n) with open('out.txt', 'w') as f: f.write(f'ct = {encrypt(Flag)}\n') f.write(f'n = {n}\n') f.write(f'e = {e}\n') f.write(f'TZ = {q%p}\n') ``` ``` ct = 62562419528725281705825472039862230356131804360170589033310545998433965077893323747801044149058853094603866188800547142867292464201088246372832509524215594752107540452196435375716242925066346564247590371031056007019767252962422943515983541461256422881338610430759275816704905732699771076992346950315902169527 n = 153085325935665697938711023109522495116369848257796969337872666255673285141800506994320862926191560830956992654526657464429408740976350569357280917140150421630518884792469954767390000951161051059928945347077543476184848596365785740479345137950810822246930103485767278148952079592365311351766875453600677864527 e = 65537 TZ = 102601048857742789950877916341203449593154982556508983972642976735012216219259152476520809612559455845502142731568315645864529172346843900288086618563394 ``` ### Solution Explanation In this challenge, we exploit the fact that the prime factors `p` and `q` of the modulus `n` are close in value given the hint `q%p`: #### Key Observations and Reshaping the Problem 1. **Given Relationship**: * Since `q % p = TZ` (the remainder when `q` is divided by `p`), we can express `q` in terms of `p` and `TZ` as: $$q = k \* p + TZ$$ Where `k` is a small integer, and we can assume `k` is small, since p is very close to q. 2. **Rewriting TZ**: * Using the relation `TZ = q - p`, we can substitute and reshape the equation. 3. **Substituting Into n**: * The modulus `n` is the product of `p` and `q`, so: $$ n = p \* q \newline n = p\*(TZ + p) $$ 1. **Quadratic Equation**: * Expanding and reshaping: $$n = p^2 + TZ \* p \newline p^2 + TZ \* p - n = 0$$ * This is a standard quadratic equation of the form: $$ax^2 + bx + c = 0$$ Here, `a = 1`, `b = TZ`, and `c = -n`. #### Solving for `q` Using the quadratic formula: $$p = (-b \pm \sqrt{b^2 - 4ac}) / 2a$$ Substituting the values: $$ p = (-TZ \pm \sqrt{TZ^2 + 4n}) / 2 $$ Select the positive root, as `q` must be positive. #### Finding `p` Once `q` is found, compute `p` using: ``` p = n // q ``` #### Computing `phi` and the Private Key `d` 1. **Compute `phi`**: * The Euler's totient function `phi` is given by: ``` phi = (p - 1) * (q - 1) ``` 2. **Find `d`**: * The private exponent `d` is the modular inverse of `e` modulo `phi`: ``` d = e^-1 mod phi ``` #### Decrypting the Ciphertext Finally, use the private key `d` to decrypt the ciphertext `ct`: ``` flag = ct^d mod n ``` The decrypted value `flag` represents the plaintext or solution to the challenge.In this challenge, we exploit the fact that the prime factors `p` and `q` of the modulus `n` are close in value (i.e., they have the same bit length), and `p` is slightly less than `q`. Here's a step-by-step breakdown of the solution: ### Solver: ```python from Crypto.Util.number import * import sympy as sp ct = 62562419528725281705825472039862230356131804360170589033310545998433965077893323747801044149058853094603866188800547142867292464201088246372832509524215594752107540452196435375716242925066346564247590371031056007019767252962422943515983541461256422881338610430759275816704905732699771076992346950315902169527 n = 153085325935665697938711023109522495116369848257796969337872666255673285141800506994320862926191560830956992654526657464429408740976350569357280917140150421630518884792469954767390000951161051059928945347077543476184848596365785740479345137950810822246930103485767278148952079592365311351766875453600677864527 e = 65537 TZ = 102601048857742789950877916341203449593154982556508983972642976735012216219259152476520809612559455845502142731568315645864529172346843900288086618563394 p = sp.symbols('p') q = sp.symbols('q') eq = sp.Eq(p*q, n) eq2 = sp.Eq(p - q, TZ) sol = sp.solve([eq, eq2], (p, q)) p = sol[1][0] q = sol[1][1] phi = (p-1)*(q-1) d = inverse(e, int(phi)) m = pow(ct, d, n) print(long_to_bytes(m)) ``` *** ## APT \[Medium] ### Handouts: ```python from Crypto.Util.number import * from pwn import xor import os FLAG = b"CSCCTF{aGUgd2FzIGEgY3RmIGJveSwgc2hlIHdhcyBhbiBBSSBnaXJs}" p = getStrongPrime(512) q = getStrongPrime(512) import random class APT: def __init__(self, members): """ Initialize the APT. game with members having two hands each. Args: members (list): List of member names participating in the game. """ self.n = p * q self.members = list(members) self.Es = [getPrime(40) for _ in members] # Each member has two hands, so the tower starts with twice the member names self.tower = self.randomize_hands(members) self.shots_taken = {member: 0 for member in members} chant = '''Chaeyoung’s favorite random game Random game Game start''' print(chant) print(f'Es: {self.Es}') print(f'N: {self.n}') def randomize_hands(self, members): """ Randomize the initial order of the hands in the tower. Args: members (list): List of member names. Returns: list: Randomized tower with two hands per member. """ members = list(members) hands = list(members) * 2 # Each member has 2 hands random.shuffle(hands) # Shuffle the hands return hands def play_round(self): """ Simulates a single round of the game. """ for i in range(3): print("| apateu, apateu") print("| tower: ", self.tower) # Randomly select a member to call a floor caller = random.choice(self.members) # Randomly determine a floor number (1 to 10, for example) floor_number = self.n + random.randint(1, 1000) print(f"| {caller} calls floor {floor_number}.") # Simulate moving the bottom hand to the top until the floor number is reached for _ in range(floor_number % len(self.tower)): self.tower.append(self.tower.pop(0)) # Move the bottom hand to the top # The member with the hand on top takes a shot shot_taker = self.tower[-1] shot = self.take_shot(shot_taker) return shot def distort(self,shot): print("| huh?") shot = bytes_to_long(xor(shot, b'\x10' * (len(shot)//2))) for i in self.Es: shot = pow(shot, i, self.n) shot = str(hex(shot)) return shot def take_shot(self, member): """ Simulates a member taking a shot. Args: member (str): Name of the member taking the shot. """ self.shots_taken[member] += 1 shot = str(hex(pow(bytes_to_long(FLAG), self.Es[self.members.index(member)], self.n))) if members[member] < 40: return f"| {member} took a shot! {self.distort(shot)}" else: members[member] = members[member] - 1 return f"| {member} took a shot! {shot}" banner ='''▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▌ ▐ ________ ________ _________ ▌ ▐|\ __ \|\ __ \|\___ ___\ ▌ ▐\ \ \|\ \ \ \|\ \|___ \ \_| ▌ ▐ \ \ __ \ \ ____\ \ \ \ ▌ ▐ \ \ \ \ \ \ \___| \ \ \ ___ ▌ ▐ \ \__\ \__\ \__\ \ \__\\___\▌ ▐ \|__|\|__|\|__| \|__\|__|▌ ▐▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▌ ''' print(f'| flag bits: {len(FLAG)*8}') print(banner) members = {"l0mb4rd": random.randint(0,50), "hamoor":random.randint(0,50), "H04X":random.randint(0,50), 'Ziadstr': random.randint(0,50), 'safareto': random.randint(0,50), 'alsa3eedi': random.randint(0,50)} no_of_heavy_heads = 0 for member in members: if members[member] > 39: no_of_heavy_heads += 1 while no_of_heavy_heads != 2: members[random.choice(list(members.keys()))] = random.randint(0,50) no_of_heavy_heads = 0 for member in members: if members[member] > 39: no_of_heavy_heads += 1 game = APT(members) menu = '''| [P]lay round | [Q]uit |''' def main(): while True: print(menu) choice = input("| Enter your choice > ") if choice.lower() == 'p': print(game.play_round()) elif choice.lower() == 'q': print("| Goodbye!") break else: print("| Invalid choice!") if '__main__' == __name__: main() ``` ### Solution Explanation This challenge leverages RSA encryption and exploits a cryptographic vulnerability known as the **common modulus attack**. Below is a detailed explanation of the challenge mechanics and how to solve it. *** #### **Challenge Details** The challenge introduces the APT game, where: 1. RSA encryption is used to generate ciphertexts ("shots"). 2. Each player is assigned a unique public exponent (`e`). 3. A common modulus `n` is used for all encryption operations. At the start of the game: * The list of public exponents (`Es`) and the modulus (`n`) is displayed. * The goal is to recover the plaintext (`FLAG`) by collecting ciphertexts and exploiting the vulnerability. *** #### **The Cryptographic Vulnerability** **Common Modulus Attack** The RSA encryption formula is: $$\[ c = m^e \mod n ]$$ Where: * ( c ): ciphertext * ( m ): plaintext * ( e ): public exponent * ( n ): common modulus If two ciphertexts are generated using the same modulus `n` but **different public exponents** `e1` and `e2`, and if `e1` and `e2` are coprime, the plaintext ( m ) can be recovered using the **common modulus attack**. *** #### **Attack Steps** **1. Collect Ciphertexts** You need two ciphertexts (( c1, c2 )) encrypted with different public exponents (( e1, e2 )). Ensure: * The ciphertexts are valid (not distorted, indicated by the absence of the `huh?` message). * ( e1 ) and ( e2 ) are coprime. $$c\_1 = m^{e\_1} \mod n\ c\_2 = m^{e\_2} \mod n$$ where $$m$$ is the plaintext, $$n$$ is the common modulus, and $$e\_1, e\_2$$ are the public exponents with $$\gcd(e\_1, e\_2) = 1$$. Using Bézout's identity, since $$\gcd(e\_1, e\_2) = 1$$, there exist integers $$a$$ and $$b$$ such that: $$\[ a \cdot e\_1 + b \cdot e\_2 = 1. ]$$ Raising $$m$$ to the power of this equation modulo $$n$$ gives: $$\[ m^{a \cdot e\_1 + b \cdot e\_2} \equiv m^1 \equiv m \mod n. ]$$ Substituting $$c\_1 = m^{e\_1} \mod n$$ and $$c\_2 = m^{e\_2} \mod n$$, we get: $$\[m = c\_1^a \cdot c\_2^b \mod n]$$ where $$a$$ and $$b$$ satisfy Bézout's identity. ### Solver: ```python from pwn import * from Crypto.Util.number import * context.log_level = 'debug' # p = process(['python3', 'chall.py']) p = remote('', ) p.recvuntil(b'Es: ') es = list(map(int,p.recvline().decode().strip()[1:-1].split(', '))) p.recvuntil(b'N: ') n = int(p.recvline().strip()) print(es) print(n) def attack(c1, c2, e1, e2, N): if GCD(e1, e2) != 1: raise ValueError("Exponents e1 and e2 must be coprime") s1 = inverse(e1,e2) s2 = (GCD(e1,e2) - e1 * s1) // e2 temp = inverse(c2, N) m1 = pow(c1,s1,N) m2 = pow(temp,-s2,N) return (m1 * m2) % N cts = [] while len(cts) < 2: p.recvuntil(b'choice: ') p.sendline(b'p') data = p.recvuntil(b'shot!') ct = int(p.recvline().strip(),16) if b'huh' not in data and ct not in cts: cts.append(ct) for i in es: for j in es: if i != j: try: m = attack(cts[0], cts[1], i, j, n) print(long_to_bytes(m).decode()) break except: pass ``` You could bruteforce the 6 Es like I did in my solver, or you could map each CTs shot taker to the corresponding entry in the Es array given, feel free to do it however you see fit :)) ## RZA \[Hard] ### Handout: ```python from Crypto.Util.number import * import random import os FLAG = os.getenv("FLAG").encode() e = 65537 class funny: def __init__(self, bitsize: int): self.p = getPrime(bitsize) self.q = getPrime(bitsize) self.n = self.p * self.q def encrypt(self, m: int): return pow(m, e, self.n) def get_hint(self): m = random.getrandbits(self.p.bit_length() // 10) return (self.p >> 14) % m , m RSA = funny(1024) banner = """| | | .----------------. .----------------. .----------------. | | .--------------. || .--------------. || .--------------. | | | | _______ | || | ________ | || | __ | | | | | |_ __ \ | || | | __ _| | || | / \ | | | | | | |__) | | || | |_/ / / | || | / /\ \ | | | | | | __ / | || | .'.' _ | || | / ____ \ | | | | | _| | \ \_ | || | _/ /__/ | | || | _/ / \ \_ | | | | | |____| |___| | || | |________| | || ||____| |____|| | | | | | || | | || | | | | | '--------------' || '--------------' || '--------------' | | '----------------' '----------------' '----------------' | | """ menu = '''| | 1. Encrypt Flag | 2. Get Hint | 3. Exit | ''' print(banner) print(f'| e = {e}') while True: print(menu) choice = input('| Enter your choice > ') if choice == '1': print(f'| Encrypted Flag: {RSA.encrypt(bytes_to_long(FLAG))}') elif choice == '2': a, b = RSA.get_hint() print(f'| Hint: {a , b}') elif choice == '3': print('| Ciao ciao!') break else: print('| Invalid choice') ``` ### Solution Explanation This challenge involves exploiting RSA encryption with hints provided through a custom modulus generation mechanism. The ultimate goal is to recover the `FLAG` using the provided ciphertext and modulus hints. *** #### **Challenge Details** The challenge uses: * An RSA public exponent ( e = 65537 ). * A ciphertext ( c ) that encrypts the flag. * Modulus hints provided through a menu option. At the start of the game: * You are given the ciphertext ( c ). * You can request modulus hints in the form of congruence relations, allowing the recovery of the modulus. The objective is to reconstruct the modulus ( p ), decrypt the ciphertext, and retrieve the `FLAG`. *** #### **The Cryptographic Vulnerability** The modulus ( p ) is generated with properties that allow reconstruction through the **Chinese Remainder Theorem (CRT)**: * Multiple congruences $$( a \mod m )$$ are provided. * Using CRT, the modulus ( p ) can be recovered. *** #### **Attack Steps** **1. Collect Congruences** Using the menu option, collect congruence relations (( a \mod m )). Ensure that the moduli ( m ) are pairwise coprime to use CRT. **2. Reconstruct ( p )** Apply CRT to the collected congruences to reconstruct ( p ). The reconstructed value will require a brute-force adjustment due to a missing bit range. **3. Decrypt the Ciphertext** Since the Flag is smaller than P, we don't need Q to decrypt **Proof** We are given: $$\[ c = m^e \mod (p \cdot q), ]$$ and need to prove: $$\[ c \mod p = m^e \mod p]$$ *** **Step 1: Express ( c )** From ( $$c = m^e \mod (p \cdot q)$$ ), there exists an integer ( k ) such that: $$\[ c = m^e - k \cdot (p \cdot q) ]$$ *** **Step 2: Take modulo ( p )** Taking ($$\mod p$$) on both sides: $$\[ c \mod p = \big(m^e - k \cdot (p \cdot q)\big) \mod p. ]$$ *** **Step 3: Simplify** Since ( p ) divides ($$p \cdot q$$ ), the term ( $$k \cdot (p \cdot q) \mod p$$) vanishes, leaving: $$\[ c \mod p = m^e \mod p ]$$ *** With ( p ), compute: $$\[ \phi = p - 1 ]$$ The private key ( d ) is calculated as: $$\[ d = e^{-1} \mod \phi ]$$ Finally, decrypt the ciphertext: $$\[ \text{FLAG} = c^d \mod p ]$$ ### Solver: ```python from Crypto.Util.number import * from pwn import * from sympy.ntheory.modular import crt # p = process(['python3', 'chall.py']) p = remote(, ) e = 65537 p.recvuntil(b'> ') p.sendline(b'1') p.recvuntil(b'Encrypted Flag: ') c = int(p.recvline().strip()) def check_coprime(m: int , n: list) -> bool: for i in n: if GCD(m, i) != 1: return False return True crts = [] ms = [] while len(crts) < 20: p.sendline(b'2') p.recvuntil(b'Hint: ') a, b = map(int, p.recvline().strip()[1:-1].split(b', ')) if check_coprime(b, ms): ms.append(b) crts.append(a) assert len(crts) == len(ms) m = crt(ms,crts)[0] << 14 for i in range(2**14): p = m + i if isPrime(p): try: phi = p - 1 d = inverse(e, phi) flag = long_to_bytes(pow(c, d, p)) if b'CSCCTF{' in flag: print(p) print(c) print(flag) break except: continue ``` ## Digital Encryption League \[Insane] ### Handout: ```python from ecdsa.ecdsa import * from ecdsa.ellipticcurve import * from Crypto.Util.number import bytes_to_long from hashlib import sha256 import random as rand import json import os FLAG = os.getenv["FLAG"].encode() secret_key = bytes_to_long(FLAG) # helper functions def merge(a, b): return a + b class SignMe: def __init__(self, curve, generator, secret_key): self.curve = curve self.generator = generator self.public_key = Public_key(generator, generator * secret_key) self.private_key = Private_key(self.public_key, secret_key) def sign_message(self, message, k): message = bytes_to_long(sha256(message.encode()).digest()) return json.dumps({"r": int(self.private_key.sign(message, k).r), "s": int(self.private_key.sign(message, k).s)}) Funky_Monkey = SignMe(curve_521, generator_521, secret_key) Banner = """| | __ _ __ _ | / ) _/_ // / ` _/_ _// | / /o_, o/ __. // /-- ____ _.__ __ ,_ / o______ / _ __. _, . ._ | /__/<(_)<<_(_/| ") if choice == '1': signature_counter += 1 if signature_counter > 2: print("| You have reached the limit of signatures") break message = input("| Enter the message > ") inp = int(input("| Enter the random number inp > ")) if inp in Used_inp: print("| You have already used this inp") break Used_inp.append(inp) signature = Funky_Monkey.sign_message(message, merge(inp, k)) print(f"| Signature: {signature}") elif choice == '2': break else: print("| Invalid choice!") ``` ### Solution Explanation In this challenge, we exploit a cryptographic vulnerability that arises when the same random value `k` is reused during the signing of two different messages. This section explains the process and how the attack functions. #### Key Concept: The Danger of Reusing `k` When signing a message, the user generates a random value `k` and uses it in the signature calculation. The following values are publicly shared as part of the signature: 1. $$r = (k \* G).x \mod p$$ 2. $$s = k^-1 \* (z + r \* dA)$$ Where: * `G` is the generator point. * `z` is the hash of the message. * `dA` is the private key. * `p` is the prime order of the curve or group. If the same `k` is used for two different signatures, the attacker can recover the private key `dA` using the following process. #### Exploiting the Reuse of `k` 1. **Obtain Two Signatures with the Same `k`**: * Let the two messages have hashes `z1` and `z2`, and the corresponding signatures are `(r, s1)` and `(r, s2)`. * Since the `k` value is the same for both signatures, we know: $$s1 = k^-1 \* (z1 + r \* dA)\newline s2 = k^-1 \* (z2 + r \* dA)$$ 2. **Calculate `k`**: * Subtract the two equations: $$s1 - s2 = k^-1 \* (z1 - z2)$$ * Rearrange to solve for `k`: $$k = (z1 - z2) / (s1 - s2)$$ 3. **Recover the Private Key `dA`**: * Using one of the signatures, calculate: $$dA = r^-1 \* (k \* s - z)$$ * This equation allows the attacker to compute the private key. #### Challenge-Specific Requirements For the attack to work, you must: 1. Send `inp1`, which is added to the static random value `k`. 2. Send `inp2`, where: ``` inp2 = inp1 + order_of_generator ``` By sending these inputs, the same `k` value is effectively reused in two signatures, enabling the attack as described above. Once the attacker has recovered the private key `dA`, they can find the flag as it is the secret key. ### Solver: ```python from pwn import * from ecdsa.ecdsa import generator_521 import json from Crypto.Util.number import inverse, bytes_to_long , long_to_bytes from hashlib import sha256 n = generator_521.order() p = process(['python3', 'chall.py']) def parse_data(msg,k): p.recvuntil(b"> ") p.sendline(b"1") p.recvuntil(b"> ") p.sendline(msg.encode()) p.recvuntil(b"> ") p.sendline(str(k).encode()) p.recvuntil(b"ture:") sig = p.recvline().decode().strip() sig = json.loads(sig) return sig msg1 = "Hamoor" msg2 = "l0mb4rd" z1 = bytes_to_long(sha256(msg1.encode()).digest()) z2 = bytes_to_long(sha256(msg2.encode()).digest()) k1 = 1561561 k2 = 1561561 + int(n) sig1 = parse_data(msg1,k1) sig2 = parse_data(msg2,k2) p.close() k = (z1 - z2) * inverse(sig1["s"] - sig2["s"], n) % n Flag = inverse(sig1["r"], n) * (k * sig1["s"] - z1) % n print(long_to_bytes(Flag)) ```