Malosdaf Blog

Write-up-Angstromctf-2024

Crypto challenges
 Write-up  1473  7 mins

PHIlosophy

Challenge decription:

Clam decided to start studying philosophy, and what is the difference between plus one and minus one anyway…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

p = getPrime(512)
q = getPrime(512)

m = int.from_bytes(flag.encode(), "big")

n = p * q
e = 65537
c = pow(m, e, n)

phi = (p + 1) * (q + 1)

print(f"n: {n}")
print(f"e: {e}")
print(f"c: {c}")
print(f"\"phi\": {phi}")

"""
n: 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084554536903236375579771401257801115918586590639686117179685431627540567894983403579070366895343181435791515535593260495162656111028487919107927692512155290673
e: 65537
c: 64457111821105649174362298452450091137161142479679349324820456191542295609033025036769398863050668733308827861582321665479620448998471034645792165920115009947792955402994892700435507896792829140545387740663865218579313148804819896796193817727423074201660305082597780007494535370991899386707740199516316196758
"phi": 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084573410416063246853198167436938724585247461433706053188624379514833802770205501907568228388536548010385588837258085711058519777393945044905741975952241886308
"""

Solution:

We notice that the phi is different from ordinary $phi = (p-1)*(p-1)$. But after some calculation, we will have $S=p+q$ and $P = pq$. Apply viete theorem and we will receive p,q.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

n=86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084554536903236375579771401257801115918586590639686117179685431627540567894983403579070366895343181435791515535593260495162656111028487919107927692512155290673
e=65537
c=64457111821105649174362298452450091137161142479679349324820456191542295609033025036769398863050668733308827861582321665479620448998471034645792165920115009947792955402994892700435507896792829140545387740663865218579313148804819896796193817727423074201660305082597780007494535370991899386707740199516316196758
phi = 86088719452932625928188797700212036385645851492281481088289877829109110203124545852827976798704364393182426900932380436551569867036871171400190786913084573410416063246853198167436938724585247461433706053188624379514833802770205501907568228388536548010385588837258085711058519777393945044905741975952241886308
# phi = (p+1)*(q+1)

# phi = p*q + p + q + 1
# phi = n + p + q + 1

pq = phi - n - 1
a = 1
b = pq
c = n
print(a,b,c)
var('x')
quadratic_eq = a*x^2 -b*x + c

# Solve the quadratic equation
solutions = quadratic_eq.roots()
print(solutions)
#actf{its_okay_i_figured_out_phi_anyway}

layers

Challenge decription:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import hashlib
import itertools
import os

def xor(key, data):
    return bytes([k ^ d for k, d in zip(itertools.cycle(key), data)])

def encrypt(phrase, message, iters=1000):
    key = phrase.encode()
    for _ in range(iters):
        key = hashlib.md5(key).digest()
        message = xor(key, message)
    return message

print('Welcome to my encryption service!')
print('Surely encrypting multiple times will make it more secure.')
print('1. Encrypt message.')
print('2. Encrypt (hex) message.')
print('3. See encrypted flag!')

phrase = os.environ.get('FLAG', 'missing')

choice = input('Pick 1, 2, or 3 > ')
if choice == '1':
    message = input('Your message > ').encode()
    encrypted = encrypt(phrase, message)
    print(encrypted.hex())
if choice == '2':
    message = bytes.fromhex(input('Your message > '))
    encrypted = encrypt(phrase, message)
    print(encrypted.hex())
elif choice == '3':
    print(encrypt(phrase, phrase.encode()).hex())
else:
    print('Not sure what that means.')

Solution:

We can see this a xor encryption, and the key is xored 1000 times with the message: $msg = msg \oplus key .. \oplus , key$ (1000 times): If we sent null bytes, we will receive the key xor with itself 1000 times, xor that back to the ciphertext and then we have reconverd the message.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from pwn import *
import itertools
conn = remote('challs.actf.co', 31398)    
def xor(key, data):
    return bytes([k ^ d for k, d in zip(itertools.cycle(key), data)])

en_flag = 'fb7fdbf9e714a08ce9cdf109bb527acba27accfeff16fcdcb1cdf358bb557898aa2d9da9af5c'
en_flag = bytes.fromhex(en_flag)
t = len(en_flag)
conn.recvuntil('> ')
conn.sendline('1')

payload  = b'\x00'*t
conn.sendline(payload)

conn.recvuntil('Your message > ')
rev = conn.recvline().strip()
rev = bytes.fromhex(rev.decode())

msg = xor(rev, en_flag)
print(msg)
#actf{593a7043ca58fcac7ec972e3dcf01263}

random rabin

Challenge decription:

I heard that the Rabin cryptosystem has four decryptions per ciphertext. So why not choose one randomly?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

from random import SystemRandom
from Crypto.Util.number import getPrime
from libnum import xgcd

random = SystemRandom()

def primegen():
	while True:
		p = getPrime(512)
		if p % 4 == 3:
			return p

def keygen():
	p = primegen()
	q = primegen()
	n = p * q
	return n, (n, p, q)

def encrypt(pk, m):
	n = pk
	return pow(m, 2, n)

def decrypt(sk, c):
	n, p, q = sk
	yp, yq, _ = xgcd(p, q) 
	mp = pow(c, (p + 1)//4, p) 
	mq = pow(c, (q + 1)//4, q)
	s = yp * p * mq % n
	t = yq * q * mp % n
	rs = [(s + t) % n, (-s - t) % n, (s - t) % n, (-s + t) % n] 
	r = random.choice(rs)
	return r

def game(): 
	pk, sk = keygen()
	print(f'pubkey: {pk}')
	secret = random.randbytes(16)
	m = int.from_bytes(secret, 'big')
	print(f'plaintext: {decrypt(sk, encrypt(pk, m))}')
	guess = bytes.fromhex(input('gimme the secret: '))
	return guess == secret

if __name__ == '__main__':
	for _ in range(64):
		success = game()
		if not success:
			exit()

	with open('flag.txt') as f:
		flag = f.read().strip()
		print(flag)

Solution:

The Rabin cryptosystem derive on the quadractic residue to encrypt, and decrypt message. We notice that in the decrypt process it will pick one of 4 and return it out. We don’t know what form of the number we receive but one of its property: $r^2 \equiv ct \pmod{n}$ and $ct \equiv m^2 \pmod{n}$. The message is only 16 bytes so it can not larger than modulo n with is 1024 bit.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

from pwn import *
from gmpy2 import iroot
def calculate(n, m):
    m = (m + n) % n
    c = (m * m) % n
    p = iroot(c, 2)[0]
    hex_p = hex(p)[2:]
    hex_p = hex_p.zfill(32)
    return hex_p
count = 0
conn = remote('challs.actf.co',31300)
while True:
    conn.recvuntil('pubkey: ')
    n = int(conn.recvline().decode().strip())
    conn.recvuntil('plaintext: ')
    m = int(conn.recvline().decode().strip())
    conn.recvuntil('gimme the secret: ')
    print(f'{count}th round')
    payload = calculate(n,m)
    print(f'answer:{payload}')
    conn.sendline(payload.strip())

    count += 1
    if count == 64:
        print(conn.recvall())
        break
    sleep(0.5)
#actf{f4ncy_squ4re_r00ts_53a370c33f192973}

tss1

Challenge decription:

I implemented a simple threshold signature scheme for Schnorr signatures.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

from hashlib import sha256
import fastecdsa.curve
import fastecdsa.keys
import fastecdsa.point

TARGET = b'flag'

curve = fastecdsa.curve.secp256k1

def input_point():
	x = int(input('x: '))
	y = int(input('y: '))
	return fastecdsa.point.Point(x, y, curve=curve)

def input_sig():
	c = int(input('c: '))
	s = int(input('s: '))
	return (c, s)

def hash_transcript(pk, R, msg):
	h = sha256()
	h.update(f'({pk.x},{pk.y})'.encode())
	h.update(f'({R.x},{R.y})'.encode())
	h.update(msg)
	return int.from_bytes(h.digest(), 'big') % curve.q

def verify(pk, msg, sig):
	c, s = sig
	R = s * curve.G + c * pk
	return c == hash_transcript(pk, R, msg)

if __name__ == '__main__':
	import sys

	if len(sys.argv) == 2 and sys.argv[1] == 'setup':
		sk1, pk1 = fastecdsa.keys.gen_keypair(curve)
		with open('key.txt', 'w') as f:
			f.write(f'{sk1}\n{pk1.x}\n{pk1.y}\n')
		exit()

	with open('key.txt') as f:
		sk1, x, y = map(int, f.readlines())
		pk1 = fastecdsa.point.Point(x, y, curve=curve)

	print(f'my public key: {(pk1.x, pk1.y)}')

	print('gimme your public key')
	pk2 = input_point()

	apk = pk1 + pk2
	print(f'aggregate public key: {(apk.x, apk.y)}')

	print('what message do you want to sign?')
	msg = bytes.fromhex(input('message: '))
	if msg == TARGET:
		print('anything but that')
		exit()

	k1, R1 = fastecdsa.keys.gen_keypair(curve)
	print(f'my nonce: {(R1.x, R1.y)}')

	print(f'gimme your nonce')
	R2 = input_point()

	R = R1 + R2
	print(f'aggregate nonce: {(R.x, R.y)}')

	c = hash_transcript(apk, R, msg)
	s = (k1 - c * sk1) % curve.q
	print(f'my share of the signature: {s}')
	print(k1)

	print(f'gimme me the aggregate signature for "{TARGET}"')
	sig = input_sig()
	if verify(apk, TARGET, sig):
		with open('flag.txt') as f:
			flag = f.read().strip()
			print(flag)

Solution:

The main idea is to make $apk$ and $R$ is determined. The easiy way to get it is to get $pk2$ and $R2$ (which we can calulate) to $-pk1+G$ and $-R1+G$ respectively. This will make $apk$ and $R$ is G - which we know, the rest is just some implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

from pwn import*
from hashlib import sha256
import fastecdsa.curve
import fastecdsa.keys
import fastecdsa.point
TARGET = b'flag'
curve = fastecdsa.curve.secp256k1

conn = remote('challs.actf.co', 31301)

conn.recvuntil(b'public key: ')
x,y = conn.recvline().strip().split(b',')
x = int(x[1:])
y = int(y[:-1])
print(x,y)
pk = fastecdsa.point.Point(x, y, curve=curve)
t = pk - curve.G
payload_x = int(t.x)
payload_y = -int(t.y)
conn.recvuntil(b'x: ')
conn.sendline(str(payload_x))
conn.recvuntil(b'y: ')
conn.sendline(str(payload_y))
print(conn.recvline())
print(conn.recvline())
conn.recvuntil(b'message: ')
conn.sendline(' ')
conn.recvuntil(b'my nonce: ')
x2,y2 = conn.recvline().strip().split(b',')
x2 = int(x2[1:])
y2 = int(y2[:-1])
R = fastecdsa.point.Point(x2, y2, curve=curve)
t2 = R - curve.G
payload_x2 = int(t2.x)
payload_y2 = -int(t2.y)
conn.recvuntil(b'x: ')
conn.sendline(str(payload_x2))
conn.recvuntil(b'y: ')
conn.sendline(str(payload_y2))
conn.recvuntil(b'c: ')
c = 29689281256975185254987441207265069040127336078857920796443223575336925266032
s = -(c-1)
conn.sendline(str(c))
conn.recvuntil(b's: ')
conn.sendline(str(s))
conn.interactive()
updatedupdated2026-04-072026-04-07

See Also: