Cryptography

RSA-TZ Mode [Easy]

Handouts:

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:

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:

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:

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:

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:

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:

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______    /  _ __. _, . ._ 
| /__/<(_)<<_(_/|</_   (___,/ / <(_/ (/ (_//_)<_<(_) / <_  /__</(_/|(_)(_/</_
|       /|                               //                          /|      
|      |/                               ''                          |/       
|"""

print(Banner)
menu = """| 1. Sign a message
| 2. Exit
|    """
signature_counter = 0
Used_inp = []
k = rand.randrange(curve_521.p())
while True:
    print(menu)
    choice = input("| Enter your choice >  ")
    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:

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))