# 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)) ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://l0mb4rd.gitbook.io/home/ctf-stuff/cscctfv6-writeups/cryptography.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.