dawgctf 2025

Team : NICP

27/760

Name	Category
The Birds	Cryptography
Baby Rsa 1	Cryptography
Baby Rsa 2	Cryptography
Cantor's Pairadox	Cryptography
Guess Me If You Can	Cryptography
This Pokemon team Is my Roman Empire	Cryptography
Jokesmith	Cryptography
The MAC FAC	Cryptography
The Fractalist	Cryptography

1

The Birds

You think you're being watched, and you see a suspicious flock of birds on the powerlines outside of your house each morning. You think the feds are trying to tell you something. Separate words with underscores and encase in DawgCTF{}. All lowercase.

DawgCTF{thereisnoescape}

2

Baby Rsa 1

You think your Algebra skills are pretty good huh? Well let's test it out.

chall.py
from Crypto.Util.number import *
from sage.all import randint

p = getPrime(512)
q = getPrime(512)
N = p * q

e = 0x10001

m = bytes_to_long(b"DawgCTF{fake_flag}")

c = pow(m, e, N)

print("N =", N)
print("e =", e)
print("ct =", c)
print()

a = randint(0, 2**100)
b = randint(0, 2**100)
c = randint(0, 2**100)
d = randint(0, 2**100)

x = a * p + b * q
y = c * p + d * q

print("a =", a)
print("b =", b)
print("c =", c)
print("d =", d)
print()
print("x =", x)
print("y =", y)

solve.py
from Crypto.Util.number import *
from sympy import mod_inverse

n = 82012538447359821165849738352756467719053530066892750177578020351019136006996881441650616631012602654920370573185549134046659875914860421394782338722082599261391182262036434549525388081948429632803770833590739702562845306267418403878169267641023564108136843672261999376998284926318313315387819024961709097101
p = 6743157372168500256063482560637365574152487940325590507177860664787954181316130485116121883062542995102725009460890756991543596608364763570502665225651511
q = 12162334930199885688769183795689969592410185555679120917249758283834302412858357859449128842077327318557896169674210867635116014075086788310254623347673691
c = 16978597269030388872549064541934623430749704732655891928833779185083334396093332647023718343748730349576361193985691953617733288330780060179716905267988202710452028943623598185277149645724247199640730959820455032298145782015884558972868277752456856802145299858618876838286795962548300080924547387662096543717
e = 65537
phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

3

Baby Rsa 2

If all I have to do is keep my factors p and q secret, then I can save computation time by sharing the same modulus between all my friends. I'll give them unique e and d pairs to encrypt and decrypt messages. Sounds secure to me!

chall.py
from Crypto.Util.number import *
from secret import flag

# This is my stuff! Don't look at it
p = getPrime(512)
q = getPrime(512)
N = p * q

e_priv = 0x10001
phi = (p - 1) * (q - 1)

d_priv = inverse(e_priv, phi)

m = bytes_to_long(flag)
c = pow(m, e_priv, N)

# This is your stuff!
e_pub = getPrime(16)
    
d_pub = inverse(e_pub, phi) 

print(f"e = {e_pub}")
print(f"d = {d_pub}")
print(f"N = {N}")
print(f"c = {c}")

we were tasked to find the d we were given the epub and dpub which e is a small prime and d is the inverse of e so

epub . dpub = 1 mod phi

epub . dpub - 1 = k . phi

phi = (epub . dpub - 1)/k

phi = N - (p+q) + 1

p + q = N + 1 - phi

we can use the identity (p - q)^2 = (p + q)^2 - 4pq

p - q = sqrt((p + q)^2 - 4pq)

2p = (p + q) + (p - q)

p = ((N + 1 - phi) + sqrt((p + q)^2 - 4pq))/2

2q = (p + q) - (p - q)

q = ((N + 1 - phi) - sqrt((p + q)^2 - 4pq))/2

from math import isqrt
from Crypto.Util.number import inverse, long_to_bytes

e_pub = 58271
d_pub = 16314065939355844497428646964774413938010062495984944007868244761330321449198604198404787327825341236658059256072790190934480082681534717838850610633320375625893501985237981407305284860652632590435055933317638416556532857376955427517397962124909869006289022084571993305966362498048396739334756594170449299859
N = 119082667712915497270407702277886743652985638444637188059938681008077058895935345765407160513555112013190751711213523389194925328565164667817570328474785391992857634832562389502866385475392702847788337877472422435555825872297998602400341624700149407637506713864175123267515579305109471947679940924817268027249
c = 107089582154092285354514758987465112016144455480126366962910414293721965682740674205100222823439150990299989680593179350933020427732386716386685052221680274283469481350106415150660410528574034324184318354089504379956162660478769613136499331243363223860893663583161020156316072996007464894397755058410931262938
e_priv = 65537
tmp = e_pub * d_pub - 1
for k in range(1, e_pub + 1):
    if tmp % k != 0:
        continue
    phi_candidate = tmp // k
    
    sum_pq = N + 1 - phi_candidate
    
    discriminant = sum_pq**2 - 4 * N
    if discriminant < 0:
        continue
    
    sqrt_disc = isqrt(discriminant)
    if sqrt_disc * sqrt_disc != discriminant:
        continue
    
    p = (sum_pq + sqrt_disc) // 2
    q = (sum_pq - sqrt_disc) // 2
    
    if p * q == N:
        # print("Found phi:", phi_candidate)
        # print("p:", p)
        # print("q:", q)
        
        d_priv = inverse(e_priv, phi_candidate)
        
        m = pow(c, d_priv, N)
        print(long_to_bytes(m))
        break

4

Cantor's Pairadox

Now that I have encrypted my flag with a new math function I was just researching I can know share it with my friend Cantor and no one will know how to read it except us!

from sage.all import sqrt, floor
from secret import flag

def getTriNumber(n):
    return n * (n + 1) // 2  # Ensure integer division

def pair(n1, n2):
    S = n1 + n2
    return getTriNumber(S) + n2

def pair_array(arr):
    result = []
    for i in range(0, len(arr), 2):
        result.append(pair(arr[i], arr[i + 1]))    
    return result

def pad_to_power_of_two(arr):
    result = arr
    n = len(result)
    while (n & (n - 1)) != 0:
        result.append(0)
        n += 1
    return result
    
flag = [ord(f) for f in flag]  
flag = pad_to_power_of_two(flag)

temp = flag
for i in range(6):
    temp = pair_array(temp)

print("Encoded:", temp)

"ABC" = [65 66 67]

then we pad the arr with 0 until the size is the power of 2

[65 66 67 0]

then it will combine the numbers in pairs

pair(a, b) = T(a + b) + b

example S = 65 + 66 = 131 T(131) = (131 * 132)/2 = 8646 so pair(65, 66) = 8646 + 66 = 8712

after 6 iterations it will become a single number

remember that

P = T(S) + b

so b = P - T(S)

S = a + b

so a = S - b

T(S) = S^2 / 2 respectively

so S^2 + S - 2P should be 0

we can use the quadratic to find

S = (sqrt(1 + 8P) - 1)/2

from math import isqrt

def T(k):
    return k * (k + 1) // 2

def unpair(P):
    possible = []
    sqrt_val = isqrt(8 * P + 1)
    S_approx = (sqrt_val - 1) // 2
    for S in [S_approx - 1, S_approx, S_approx + 1, S_approx + 2]:
        if S < 0:
            continue
        T_S = T(S)
        n2 = P - T_S
        if n2 >= 0:
            n1 = S - n2
            if n1 >= 0:
                possible.append((n1, n2))
    return possible

def decode(encoded):
    current = encoded.copy()
    for _ in range(6):
        new_current = []
        for num in current:
            pairs = unpair(num)
            n1, n2 = pairs[0]
            new_current.append(n1)
            new_current.append(n2)
        current = new_current
    original_ascii = []
    for num in current:
        if num != 0:
            original_ascii.append(num)
        else:
            break
    flag = ''.join(chr(c) for c in original_ascii)
    return flag

encoded_output = [4036872197130975885183239290191447112180924008343518098638033545535893348884348262766810360707383741794721392226291497314826201270847784737584016]
flag = decode(encoded_output)
print(flag)

5

Guess Me If You Can

Check out the note-taking app I created! I heard users are really bad at picking passwords, so I made a really really secure number generator to give users passwords! Good luck trying to break it now.

#!/usr/local/bin/python3
from Crypto.Util.number import *
from secret import flag, init, N, a, b

seed = init
state = seed

current_user = (None, None)

accounts = []
notes = dict()

menu1 = '''[1] - Register
[2] - Login
[3] - Manage Notes
[4] - List Users
[5] - Exit 
'''

menu2 = '''[1] - Register
[2] - Logout
[3] - Manage Notes
[4] - List Users
[5] - Exit 
'''
menu3 = '''[1] - Add Note
[2] - Remove Note
[3] - Return to Menu
'''

def getNext(state):
    state = (a * state + b) % N
    return state
    
def make_account(name, password):
    global accounts
    global notes
    accounts.append((name, password))
    notes[name] = []

def register(name):
    for account in accounts:
        if name == account[0]:
            print("An account with this name already exists")
            raise ValueError(f"User '{name}' already exists. Please choose a different username")
    global state
    state = getNext(state)
    make_account(name, state)
    
    return state

def list_users():
    print("Here are all list of all users currently registered.")
    for i in range(len(accounts)):
        print("Account [" + str(i) + "] - ", accounts[i][0])
    
def login(name, password):
    for account in accounts:
        if account[0] == name and str(account[1]) == str(password):
            global current_user
            current_user = account
            print()
            print(f"Succesfully Logged in as {current_user[0]}")
            return
    print("Invalid username or password")    

def logout():
    global current_user
    current_user = (None, None)
    
def get_menu_choice(minimum, maximum, prompt, input_func=input):
    choice = ""
    while(True):
        choice = input_func(prompt)
        try:
            choice = int(choice)
            if (choice < minimum or choice > maximum):
                print("Invalid Choice. Try again")
            break
        except:
            print("Error parsing your input. Try again")
    return choice

def view_notes(user):
    print(f"Here are the notes for user '{user}'")
    current_notes = notes[user]
    if (len(current_notes) == 0):
        print("This user currently has no notes!")
        return
    i = 1
    for value in current_notes:
        print(f"Note {i}: {value}")
        i += 1
    return

def add_note(user, message):
    if (len(message) == 0):
        print("Can't add note with an empty message")
        return
    current_notes = notes[user]
    current_notes.append(message)
    notes[user] = current_notes
    return

def remove_note(user, index):
    current_notes = notes[user]
    del current_notes[index]
    return

def is_logged_in():
    global current_user
    if (current_user[0] == None and current_user[1] == None):
        return False
    return True

def handle_note(user, input_func=input):
    global notes
    view_notes(user)
    print()
    while(True):
        print(menu3)
        choice = get_menu_choice(1, 3, "> ")
        if choice == 1:
            msg = input_func("What message do you want to save? ")
            add_note(user, msg)
            break
        elif choice == 2:
            num_notes = len(notes[user])
            if num_notes == 0:
                print("This user currently has no notes to remove.")
            else:
                note_choice = get_menu_choice(1, num_notes, f"Which note do you want to remove? (1 - {num_notes}) ")
                remove_note(user, note_choice - 1)
                break
        elif choice == 3:
            break
def initAdmin():
    register("admin")
    add_note("admin", flag)
    
        
def run(input_func=input):
    global notes
    global accounts
    initAdmin()
    print("Welcome to the state of the art secure note taking app, Global Content Library . You can make accounts, see active users, store and view private information. Everything you can ask for. You can rest well knowing your password is securely generated, just make sure you don't lose it. That's the only way to access your account!")
    while(True):
        print()
        if is_logged_in():
            print(menu2)
        else:
            print(menu1)
        choice = get_menu_choice(1, 5, "> ")
        if choice == 1: # Register
            name = input_func("Enter your name: ")
            try:
                password = register(name)
            except:
                continue
            print("Your secret password is: ", password, "\nPlease don't lose it!!")
        if choice == 2:
            if (current_user[0] == None and current_user[1] == None):
                name = input_func("Enter your name: ")
                password = input_func("Enter your password: ")
                login(name, password)
            else:
                logout()               
        if choice == 3:
            if (current_user[0] == None):
                print("You must be logged in to use this feature")
            else:
                handle_note(current_user[0])
        if choice == 4:
            list_users()
        if choice == 5:#Exit
            print("See you later!")
            exit()
                
if __name__ == '__main__':
    run()

the server uses a LCG password generator

where

def getNext(state):
    state = (a * state + b) % N
    return state

the flaw is that it was using a weak pseudo random (LCG) for the password generation where LCG itself is predictable if we can observe several consecutive outputs

strategy

gather 3 LCG outputs like so

s1 = register_user('user1')
s2 = register_user('user2')
s3 = register_user('user3')

then we can calculate the parameters

t1 = (s2 - s1) % N t2 = (s3 - s2) % N

we can calculate the a

inv_t1 = pow(t1, -1, N) # Modular inverse of t1 a = (t2 * inv_t1) % N

then b = (s2 - a * s1) % N

inv_a = pow(a, -1, N)

admin = ((s1 - b) * inv_a) % N

6

This Pokemon team Is my Roman Empire

I was on a really sleep deprived tumble, so I decided to hide the key string to my bank account in a Pokemon Team. I know nothing about Pokemon, so I asked a friend and he said the movesets "looked really weird". Can you help find my key string? It should consist of unseparated letters, and be in all caps.

from the website it says the pokemon skills is weird thats problably a hint and the chall called roman empire is also a hint

every first letter of the skill then do a caesar bruteforce to gain the text but every pokemon has a different shift so we have to do it one by one

DawgCTF{ITSAROCKSOLIDPOKEMONTEAM}

7

Jokesmith

#!/usr/local/bin/python3

from secret import flag
from Crypto.Util.number import *


jokes = [
    "Why did the prime break up with the modulus? Because it wasn't factoring in its feelings",
    "Why did the cryptographer bring RSA to the dance? Because it had great curves — wait, no, wrong cryptosystem",
    "Why did the CTF player cross the road? To get to the " + flag,
]

def hideFlag(message):
    hidden = ""
    start = False
    for c in message:
        if (start):
            hidden += "X"
        else:
            hidden += c
        if c == "{":
            start = True
    if (start):
        hidden = hidden[:-1] + "}"
    return hidden

def run():
    print("You think you're funny? I got a few jokes of my own, tell me a joke and I'll tell you mine")
    transcript = []
    for i in range(3):
        joke = input("Tell me a joke: ")
        funny = bytes_to_long(joke.encode()) % 2
        if (not funny):
            print("Really? That's it? Come back with some better material")
            exit()
        else:
            transcript.append(joke)
            print("Ha! That was pretty funny! Here's one of my own")
            print(hideFlag(jokes[i]))
            transcript.append(jokes[i])
    print("Here is our jokes! Show it to a friend to make them laugh! I better encrypt it though in case I said something private")

    m = "\n".join(transcript)
    
    p = getPrime(512)
    q = getPrime(512)
    N = p * q
    
    e = 3
    c = pow(bytes_to_long(m.encode()), e, N)
    print("c =", c)
    print("N =", N)
    print("e =", e)

if __name__ == '__main__':
    run()

look at the small e but the m is very large but we can still manage a hastads attack

from pwn import *
from Crypto.Util.number import *

HOST = "connect.umbccd.net"
PORT = 20549

# context.log_level = "debug"

server = remote(HOST, PORT)

for _ in range(3):
    server.recvuntil(b"Tell me a joke: ")
    server.sendline(long_to_bytes(1))

for _ in range(3):
    trashcan = server.recvline()

print(server.recv())

8