from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import random

def kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk():
    random.seed(1337)
    return bytes([random.randint(0, 255) for _ in range(16)])

def aesaesaesaesaesaesaesaesaesaesaesaes(aesaesaesaesaesaesaesaesaesaesaes,aesaesaesaesaesaesaesaesaes):
    cipher = AES.new(aesaesaesaesaesaesaesaesaes, AES.MODE_ECB)
    ct_bytes = cipher.encrypt(pad(aesaesaesaesaesaesaesaesaesaesaes, AES.block_size))
    with open('output.txt', 'w') as f:
        f.write(ct_bytes.hex())

def flagflagflagflagflagflagflagflagflagflag():
    with open('flag.txt', 'rb') as f:
        flag = f.read()
    return flag

aesaesaesaesaesaesaesaesaesaesaesaes(flagflagflagflagflagflagflagflagflagflag(), kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk())

위 코드에서는 kk..kk() 함수를 통해 key를 얻어 AES 암호화한 값을 output.txt에 작성합니다.

해당 함수를 통해 key를 똑같이 얻고, 이를 통해 output.txt의 내용을 복호화하면 됩니다.

from Crypto.Cipher import AES
import random

def kkkk():
    random.seed(1337)
    return bytes([random.randint(0, 255) for _ in range(16)])

key = kkkk()
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.decrypt(bytes.fromhex("a7be6170309d68ca9e7989f63a0c2711a48ab69e82a5e654ecf18948b66802e6")))

RSA Private

RSA에 대해 알아봅시다.

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

keyPair = RSA.generate(2048)

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

pubkey = keyPair.publickey()
encryptor = PKCS1_OAEP.new(pubkey)
encrypted = encryptor.encrypt(flag)

with open('flag.enc', 'wb') as f:
    f.write(encrypted)

priKeyPEM= keyPair.export_key(passphrase="1337")

with open('private.pem', 'wb') as f:
    f.write(priKeyPEM)

RSA key를 생성하여 이를 통해 flag를 암호화한 flag.enc와, 비밀키 private.pem을 저장합니다.

주어진 비밀키를 통해 주어진 암호문을 복호화하면 됩니다.

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# Load the private key
with open('private.pem', 'rb') as f:
    private_key = RSA.import_key(f.read(), passphrase="1337")

# Load the encrypted data
with open('flag.enc', 'rb') as f:
    encrypted_data = f.read()

# Create a cipher object
decryptor = PKCS1_OAEP.new(private_key)

# Decrypt the data
decrypted_data = decryptor.decrypt(encrypted_data)

# Print or use the decrypted data
print(decrypted_data.decode())

Easy

Power X(6, 7, 1337)

Power 6

python3 chall.py를 실행하고 플래그를 획득하세요! ㅎ 아앗 컴퓨터가 뜨거워져...

# from Crypto.Util.number import getPrime
# p, q = getPrime(32), getPrime(32)
p, q = (2608745861, 3840342437)
n = p * q

k = (2**2**2**2**2**2) % n

print(f"hspace{{{str(k)}}}")

Power 7

python3 chall.py를 실행하고 플래그를 획득하세요! ㅎ 우주가 101295921388번 탄생하고 소멸되기를 반복했어요!

# from Crypto.Util.number import getPrime
# p, q = getPrime(32), getPrime(32)
p, q = (2608745861, 3840342437)
n = p * q

k = (2**2**2**2**2**2**2) % n

print(f"hspace{{{str(k)}}}")

Power 1337

python3 chall.py를 실행하고 플래그를 획득하세요! ㅎ https://youtu.be/QwXK4e4uqXY?si=gYjRNMx5skejfJ3X 뭐 이런 걸 보는거 같네요, 단지 이게 훨씬 오래걸리죠 ㅋㅋ

# from Crypto.Util.number import getPrime
# p, q = getPrime(32), getPrime(32)
p, q = (2608745861, 3840342437)
n = p * q

k = (2** ... **2) % n

print(f"hspace{{{str(k)}}}")

기본적으로 거의 동일한 코드에 2의 개수만 달라집니다.

당연히 직접 계산하는 것은 Power 6를 제외하면 불가능하며, 따라서 이를 빠르게 계산하는 방식을 찾아야 합니다.

우선 홀수 $n$ 에 대해 경우 $2^{ϕ (n)} \equiv 1 (\mod n)$ 입니다. ( $∵$ 오일러의 정리)

이에 착안하여, 다음과 같이 해결하신 경우가 많을 거라 개인적으로 생각합니다.

X = 6
# X = 7
# X = 1337

p, q = (2608745861, 3840342437)
n = p * q
ns = []
for i in range(X):
    ns.append(n)
    n = euler_phi(n)
ns = ns[::-1]

k = 1
for i in range(X):
    k = ZZ(pow(2, k, ns[i]))
print(f"hspace{{{str(k)}}}")

실제로 위 코드를 통해서 flag를 얻을 수 있습니다.

하지만, 짝수 $n$ 에 대해서는 $2^{ϕ (n)} \equiv 1 (\mod n)$ 는 성립하지 않습니다.

엄밀한 풀이

$a \geq ϕ (n), n = 2^{r} n^{'} (n^{'} \equiv 1 (\mod 2))$ 라고 합시다.

$a = k ϕ (n) + b$ , 라면 $2^{a} - 2^{b} = 2^{b} (2^{k ϕ (n)} - 1) \equiv 0 (\mod n^{'})$

( $∵ 2^{k ϕ (n)} - 1 \equiv 0 (\mod n^{'})$ )

그런데 모든 n에 대하여 $r \leq ϕ (n)$ 이므로 ( $∵$ $r$ 이 크고 $ϕ (n)$ 이 작으려면 $n = 2^{k}$ 꼴이어야 하나 이때 모두 식 만족)

$2^{a} \equiv 0 (\mod 2^{r})$ 이 됩니다.

즉, $a \equiv b (\mod ϕ (n))$ 과 $b > r$ 을 만족하면 $2^{a} \equiv 2^{b} (\mod n)$ 이며,

$b = a % ϕ (n) + ϕ (n)$ 이 이를 만족합니다.

이를 반영하여 코드를 짜보면 다음과 같습니다.

X = 6
# X = 7
# X = 1337

p, q = (2608745861, 3840342437)
n = p * q
ns = []
for i in range(X):
    ns.append(n)
    n = euler_phi(n)# n = phi(n)
ns = ns[::-1]

k = 1
for i in range(X):
    if ns[i].nbits() > k: # 2^k <= ns[i]
        k = ZZ(pow(2, k, ns[i]))
    else: # 2^k > ns[i]
        k = ZZ(pow(2, k, ns[i])) + ns[i]
print(f"hspace{{{str(k % ns[-1])}}}")

sagmath 관련 추가설명

이 문제에서는 euler_phi를 사용하기 위해 쓰였습니다.
CTF에서 Crypto 문제를 풀 때 Pwnable에서의 pwntools 이상으로 중요하다고 생각합니다.
해당 코드는 .sage 확장자를 가지는 sagemath 코드입니다.
- sagemath에서 pow의 리턴값은 ring의 원소이며, 에러를 피하기 위해 ZZ()를 통해 interger로 바꿉니다.
- euler_phi는 sagemath에서 자체적으로 제공하는, 오일러 파이 함수입니다.

Medium

Triple sus

maple3142의 sus를 아나요? 아니면 diff의 cry는요?

Description에서 언급된 문제는 각각 ImaginaryCTF 2023 - Sus 와 Wacon 2023 Quals - Cry 입니다.

주어진 문제보다는 훨씬 어렵지만, 둘 다 매우 훌륭한 문제이므로 기회가 되면 살펴보시는걸 추천드립니다.

from Crypto.Util.number import *

def gen(bits):
    while True:
        p = getPrime(bits)
        q = 2 * p + 1
        if isPrime(q):
            return p * q

n = gen(300) * gen(300) * gen(300) * getPrime(300)
m = int.from_bytes(open("flag.txt", "rb").read(), "big")
c = pow(m, 0x10001, n)

print((n, c))

$n$ , $c$ 가 주어지며, $n$ 을 인수분해 할 수 있다면 $c$ 를 복호화하여 $m$ 을 구할 수 있을것입니다.

gen()로 생성된 $n$ 의 두 소인수 $p$ , $q$ 및 이와 서로소인 $x$ 에 대하여, $(x^{2})^{n} - 1 \equiv 0 (\mod q)$ 입니다.

proof

$x ≢ 0 (\mod q) \to x^{2 p} \equiv 1 (\mod q)$ ( $∵ q = 2 p + 1$ )

즉, $(x^{2})^{n} - 1 \equiv (x^{2})^{k p q} - 1 \equiv (x^{k q})^{2 p} - 1 \equiv 0 (\mod q)$

따라서, $a = x^{2} (\mod q)$ 의 해가 존재하면 $a^{n} - 1 \equiv 0 (\mod q)$ 입니다.

from Crypto.Util.number import *

n, c = (..., ...)

qs = set()
for a in range(2, 100): # testing a, 2 to 99 
    q = GCD(n, pow(a, n, n) - 1)

    # 단 하나의 q에 대해서만 해 x 존재
    if q.bit_length() == 301: 
        qs.add(q)

# 3개의 q 모두 추출
assert len(qs) == 3 
qs = list(qs)

# p 계산
ps = [q // 2 for q in qs] 

# 마지막 소인수(r) 계산
r = n 
for i in range(3): 
    r //= ps[i]
    r //= qs[i]

# phi 계산
phi = r - 1 
for i in range(3):
    phi *= ps[i] - 1
    phi *= qs[i] - 1

# c 복호화
d = pow(0x10001, -1, phi)
pt = pow(c, d, n)
print(long_to_bytes(pt))

위와 같이 여러 $a$ 에 대해 GCD(n, pow(a, n, n) - 1)을 계산함으로써, $q$ 를 추출하고 $n$ 을 소인수분해합니다.

DSArrrrrgh

DSA? Isn't it cryptographically secure?

from Crypto.Util.number import *
import random

class DSA:
    def __init__(self):
        while True:
            self.q = getPrime(160)
            r = random.randrange(1 << 863, 1 << 864)
            self.p = self.q * r + 1
            if self.p.bit_length() != 1024 or isPrime(self.p) != True:
                continue
            h = random.randrange(2, self.p - 1)
            self.g = pow(h, r, self.p)
            if self.g == 1:
                continue
            self.x = random.randrange(1, self.q)
            self.y = pow(self.g, self.x, self.p)
            break

    def sign(self, h):
        k = random.randrange(1, self.q)
        r = pow(self.g, k, self.p)
        s = inverse(k, self.q) * (h + self.x * r) % self.q
        return (r, s)

    def verify(self, h, sig):
        r, s = sig
        if s == 0:
            return False
        s_inv = inverse(s, self.q)
        e1 = h * s_inv % self.q
        e2 = r * s_inv % self.q
        r_ = pow(self.g, e1, self.p) * pow(self.y, e2, self.p) % self.p
        if r_ == r:
            return True
        else:
            return False

flag = "hspace{}"

dsa = DSA()
h0 = random.randrange(1, dsa.q)
r, s = dsa.sign(h0)
print(f"h = {h0}")
print(f"p = {dsa.p}")
print(f"q = {dsa.q}")
print(f"g = {dsa.g}")
print(f"y = {dsa.y}")
print(f"r = {r}")
print(f"s = {s}")

h = int(input("h = "))
r = int(input("r = "))
s = int(input("s = "))

if dsa.verify(h, [r, s]) and (h0 - h) % dsa.q != 0:
    print(flag)
else:
    print("I knew DSA was safe.")

DSA의 여러 인수들과 서명 하나가 주어지고, $h$ 의 값이 다른 또 다른 서명을 입력하면 flag가 주어집니다.

보통 DSA와 차이점은 h를 마음대로 조작할 수 있다는 점에 있습니다.

우선, 서명은 다음 식을 만족해야 합니다.
$g^{h s^{- 1} (\mod q)} y^{r s^{- 1} (\mod q)} \equiv r (\mod p)$

우리는 여기서 $g$ 를 제외한 모든 숫자를 조작할 수 있습니다.

개인적으로 까다롭다고 느낀 점은 $r$ 이 mod $q$ 상에서 곱셈연산을 하고 $p$ 로 나눈 나머지와 비교가 이루어져,

새로운 $r$ 에 무언가 계산한 값을 넣기 쉽지 않았습니다.

다행히도, 매우 단순한 해답이 존재합니다.

$(h, r, s) = (0, y, y)$

해당 값을 대입하면 위 식을 만족하며, flag을 획득할 수 있습니다.

Padding Noracle Attack

Padding oracle attack은 너무 지겨워요, 제가 unpad 함수를 비틀었으니 한 번 이거도 확인해봐주실래요?

from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from os import urandom
import hashlib

def myunpad(msg):
    return msg[:-msg[-1]]
    # never raises an error, so padding oracle attack is useless.

def unpad_and_proof(msg):
    return hashlib.sha256(myunpad(msg)).digest()

if __name__ == "__main__":
    key = urandom(16)
    iv = bytes(16)

    flag = open("flag.txt", "rb").read()

    enc_flag = AES.new(key, AES.MODE_CBC, iv).encrypt(pad(flag, 16))

    print(f"enc_flag = {bytes.hex(enc_flag)}")

    while True:
        commit = bytes.fromhex(input("Input ciphertext: "))
        proof = unpad_and_proof(AES.new(key, AES.MODE_CBC, iv).decrypt(commit))

        print(f"Proof: {bytes.hex(proof)}")

임의의 ciphertext를 입력해, 복호화된 문장의 해시값을 얻을 수 있습니다.

우선 입력으로 마지막에 random한 블록을 준다면, 복호화된 평문의 마지막 바이트도 무작위할 것입니다.

그리고, myunpad()는 마지막 바이트의 값에 따라 앞을 잘라내므로 0~255중 무작위로 고른 값만큼 잘려나갑니다.

이를 이용하여, 앞의 n글자를 알고 있을때 앞의 n+1글자의 가능한 모든 해시값을 계산해두고,

랜덤하게 얻은 해시값 중 하나가 이에 속하면 다음 글자를 알 수 있습니다.

from pwn import *
import hashlib
import os


def sha256(msg):
    return hashlib.sha256(msg).digest()


r = remote("3.34.190.217", "2347")

enc_flag = bytes.fromhex(r.recvline()[11:].decode())

# 해시값 획득
def get_hash(x):
    assert len(x) % 16 == 0
    r.sendlineafter(b": ", x.hex().encode())
    return bytes.fromhex(r.recvline()[7:].decode())

# 맨 앞부터 한글자씩 추출
ans = []
for i in range(64):
    candidates = [sha256(bytes(ans + [c])) for c in range(256)]
    while True:
        h = get_hash(enc_flag + os.urandom(16))
        if h in candidates:
            break
    ans.append(candidates.index(h))
    print(bytes(ans))

Hard

daead

"AEAD is dead"

— Friedrich Nietzsche

~~니체는 이런말 한 적 없습니다~~

#!/usr/local/bin/python3
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
import os

FLAG = 'hspace{fake_flag}'

key = os.urandom(16)
nonce = os.urandom(12)

def encrypt(data):
    aesgcm = AESGCM(key)
    ct = aesgcm.encrypt(nonce=nonce, data=data, associated_data=key)
    return ct

def int_input(message):
    try:
        user_input = input(message)
        user_input = int(user_input)
        if not (0 < user_input < 1024):
            raise
        return user_input
    except KeyboardInterrupt:
        exit(130)
    except:
        print("Invalid input!")
        exit(1)

print("AEADAEADAEADAEADA")
print("E    Welcome    E")
print("A  Select menu  A")
print("DAEADAEADAEADAEAD")
print("===")

while True:
    print("1. Print random bytes")
    print("2. Print encrypted random bytes")
    print("3. Print encrypted flag")
    print("4. Exit")

    choice = int_input("Choose >>> ")

    if choice == 1:
        l = int_input("Length >>> ")
        print(os.urandom(l).hex())
    elif choice == 2:
        l = int_input("Length >>> ")
        ct = encrypt(os.urandom(l))
        print(ct.hex())
    elif choice == 3:
        ct = encrypt(FLAG.encode('utf-8'))
        print(ct.hex())
    elif choice == 4:
        print("Bye")
        exit(0)
    else:
        print("Invalid choice!")

encrypt는 key, nonce, associated_data가 모두 고정된 AES-GCM 암호화를 진행합니다.

(GCM mode에 관해서는 개인적으로 위키백과가 제일 깔끔하게 설명했다고 생각합니다.)

그리고 AESGCM의 reference 를 보면, AESGCM.encrypt()는 16byte 태그를 암호화된 값의 뒤에 붙여서 리턴합니다.

$E_{k}, A (= k e y), H$ 모두 고정되어있고, $C$ 의 길이도 마음대로 지정할 수 있으므로 이를 모두 계산할 수 있습니다.

우선, $E_{k}$ , $A$ , $k e y$ , $H$ 계산에 있어 중심이 되는 식은 아래 4가지입니다.

# tag0 = E_k + bitlen_block(16, 16) * H + data0[-1] * H ^ 2 + A * H ^ 3
# tag1 = E_k + bitlen_block(16, 16) * H + data1[-1] * H ^ 2 + A * H ^ 3
# tag2 = E_k + bitlen_block(16, 32) * H + data2[-1] * H ^ 2 + data2[-2] * H ^ 3 + A * H ^ 4
# A = key

bitlen_block()은 A, C의 바이트 수를 입력으로 받아 len(A)||len(C) 블록을 리턴합니다.
len(A) = len(data0) = len(data1) = 16
len(data2) = 32

그 이후 위 식들을 토대로 $H$ , $k e y$ , $E_{k}$ 순으로 계산하였습니다.

이 뒤에는 아래의 두 식을 통해 검산 및 nonce를 계산하였습니다.

# H = enc(0)
assert cipher.encrypt(b"\x00" * 16) == ele2bytes(H)
# dec(E_k) = counter0 = IV || 0^31 || 1
nonce = cipher.decrypt(Ek)[:12]

필요한 모든 값을 계산하였으므로, 동일한 cipher을 만들고 복호화를 하면 됩니다.

# https://cryptohack.org/challenges/forbidden_fruit/solutions/
# functions from VincBreaker's writeup
from Crypto.Util.number import bytes_to_long, long_to_bytes

BF.<X> = GF(2)[]
FF.<A> = GF(2 ^ 128, modulus=X ^ 128 + X ^ 7 + X ^ 2 + X + 1)

# int to element
def int2ele(integer):
    res = 0
    for i in range(128):
        # rightmost bit is x127
        res += (integer & 1) * (A ^ (127 - i))
        integer >>= 1
    return res

# bytes to element
def bytes2ele(b):
    return int2ele(bytes_to_long(b))

# element to int
def ele2int(element):
    integer = element.integer_representation()
    res = 0
    for i in range(128):
        res = (res << 1) + (integer & 1)
        integer >>= 1
    return res

# element to bytes
def ele2bytes(ele):
    return long_to_bytes(ele2int(ele))


from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from Crypto.Cipher import AES
from pwn import *

# len(A)||len(C) 블럭을 FF의 원소로 리턴
def bitlen_block(auth_len, plain_len):
    auth_bitlen = auth_len * 8
    plain_bitlen = plain_len * 8
    return int2ele((auth_bitlen << 64) | plain_bitlen)


r = remote("3.34.190.217", "41337")

r.sendlineafter(b"> ", b"3")
enc = bytes.fromhex(r.recvline().decode())

# 블럭들과 태그로 쪼개서 리턴
def get2ele(x):
    r.sendlineafter(b"> ", b"2")
    r.sendlineafter(b"> ", str(x).encode())
    data = bytes.fromhex(r.recvline().decode())
    data, tag = data[:-16], data[-16:]
    return [bytes2ele(data[i : i + 16]) for i in range(0, len(data), 16)], bytes2ele(tag)

data0, tag0 = get2ele(16)
data1, tag1 = get2ele(16)
data2, tag2 = get2ele(32)

# tag0 = E_k + bitlen_block(16, 16) * H + data0[-1] * H ^ 2 + A * H ^ 3
# tag1 = E_k + bitlen_block(16, 16) * H + data1[-1] * H ^ 2 + A * H ^ 3
# tag2 = E_k + bitlen_block(16, 32) * H + data2[-1] * H ^ 2 + data2[-2] * H ^ 3 + A * H ^ 4
# A = key

r.close()

# tag0 + tag1 = (data0[0] + data1[0]) * H ^ 2
H2 = (tag0 + tag1) / (data0[0] + data1[0])

# H2 ^ (2 ^ 128 - 1) = 1
# (H2 ^ (2 ^ 127)) ^ 2 = H2
H = H2 ^ (2 ^ 127)


rem1 = tag1 + bitlen_block(16, 16) * H + data1[-1] * H ^ 2
rem2 = tag2 + bitlen_block(16, 32) * H + data2[-1] * H ^ 2 + data2[-2] * H ^ 3
rem = rem1 + rem2

# rem1 = E_k + key * H ^ 3
# rem2 = E_k + key * H ^ 4
# rem = key * (H ^ 4 + H ^ 3)

key = rem / (H ^ 4 + H ^ 3)
Ek = rem1 + key * H ^ 3


key, Ek = ele2bytes(key), ele2bytes(Ek)
cipher = AES.new(key, AES.MODE_ECB)

# H = enc(0)
assert cipher.encrypt(b"\x00" * 16) == ele2bytes(H)
# dec(E_k) = counter0 = IV || 0^31 || 1
nonce = cipher.decrypt(Ek)[:12]

aesgcm = AESGCM(key)
print(aesgcm.encrypt(nonce, enc, key))

Another RSA permutation

36진법이라, 재미있군요. 과연 36!개의 연산이 가능할까요?

from Crypto.Util.number import getPrime
import random

# I will use all 0 ~ 9 & a ~ z
def permute(num):
    res = ""
    while num:
        res = perm[num % 36] + res
        num //= 36
    return res

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
d = pow(e, -1, (p - 1) * (q - 1))

perm = list("0123456789abcdefghijklmnopqrstuvwxyz")
random.shuffle(perm)

m = int.from_bytes(open("flag.txt", "rb").read(), "big")
c = pow(m, e, n)

print(f"enc_flag = {permute(c)}")

while True:
    c = int(input("Input ciphertext: "))
    m = pow(c, d, n)
    print(f"Plaintext: {permute(m)}")

chall.py는 암호문을 출력하고, 모든 입력에 대해 복호화된 값을 출력합니다.

다만 모든 출력은 36진수로, 각각의 문자가 무슨 값을 의미하는지 모른채로 이루어집니다.

풀이의 핵심이 되는 성질은 d가 홀수이므로 $x^{d} + (- x)^{d} \equiv 0 (\mod n)$ 이며,

$0 \leq m < n$ 이므로 $x, - x$ 를 입력으로 주었을 때 $m$ 이 0이 아니라면 반드시 합이 $n$ 이 됩니다.

각 글자가 가지는 값을 미지수로 생각하면, 해당 문제를 일차연립방정식으로 나타낼 수 있게 됩니다.

예를 들어, "13n"이 16이라면
$1296 x_{1} + 36 x_{3} + x_{n} = 16$ 와 같이 나타낼 수 있습니다.

또한 이러한 수식은 인수를 나타내는 벡터와 미지수를 나타내는 벡터의 내적으로 나타낼 수 있습니다.

from pwn import *

r = remote("3.34.190.217", "2346")


def dec(x):
    r.sendlineafter(b": ", str(x).encode())
    r.recvuntil(b": ")
    return r.recvline()[:-1].decode()


def analysis(x):
    chars = "0123456789abcdefghijklmnopqrstuvwxyz"
    ret = [0] * 36
    t = 1
    for c in x[::-1]:
        ret[chars.index(c)] += t
        t *= 36
    return vector(ret)


def dec_analysis(x):
    return analysis(dec(x)) + analysis(dec(-x))


r.recvuntil(b"= ")
enc = r.recvline()[:-1].decode()

M = []
for i in range(36):
    M.append(dec_analysis(i + 2) - dec_analysis(1))
M = Matrix(M)

dec_analysis(x)는 $x, - x$ 를 입력했을 때 리턴되는 문자열을 토대로 방정식의 인수를 나타낸 벡터를 리턴합니다.

즉, $x$ 가 $n$ 의 배수가 아닌 이상 dec_analysis(x)에 미지수를 나타내는 벡터를 내적하면 $n$ 이 됩니다.

이를 이용하여, 미지수를 나타내는 벡터 $v$ 에 대해 $M v = \vec{0}$ 을 만족하는 $M$ 을 만듭니다.

여기서 M을 구하는 방법은 다양합니다만, 저는 LLL을 활용하도록 하겠습니다.

M = M.stack(identity_matrix(36))
M = M.transpose()
v = M.LLL()[0][36:]

M의 원소들의 크기에 비해 저희가 원하는 값들의 크기는 36 미만으로 매우 작습니다.

단위행렬을 아래 붙여 각 열에 1을 붙이고, 이의 전치행렬에 LLL을 계산하면
앞의 36개 원소는 0, 뒤의 36개 원소는 각 미지수의 값인 벡터가 구해집니다.

따라서, 이제 36진수 문자열을 복호화 할 수 있으며 flag 또한 계산할 수 있습니다.

from pwn import *

r = remote("3.34.190.217", "2346")


def dec(x):
    r.sendlineafter(b": ", str(x).encode())
    r.recvuntil(b": ")
    return r.recvline()[:-1].decode()


def analysis(x):
    chars = "0123456789abcdefghijklmnopqrstuvwxyz"
    ret = [0] * 36
    t = 1
    for c in x[::-1]:
        ret[chars.index(c)] += t
        t *= 36
    return vector(ret)


def dec_analysis(x):
    return analysis(dec(x)) + analysis(dec(-x))


r.recvuntil(b"= ")
enc = r.recvline()[:-1].decode()

M = []
for i in range(36):
    M.append(dec_analysis(i + 2) - dec_analysis(1))
M = Matrix(M)

M = M.stack(identity_matrix(36))
M = M.transpose()
v = M.LLL()[0][36:]

# v 부호 양수로 고정
if v[0] < 0:
    v = v * -1

# enc 문자열 -> 정수
enc = analysis(enc) * v

# dec(enc) 문자열 -> 정수
ans = analysis(dec(enc)) * v

# print(long_to_bytes(ans))
print(bytes.fromhex(hex(ans)[2:]))

'CTF > writeup-ko' 카테고리의 다른 글

CODEGATE 2024 Quals 풀이 - Crypto+α (0)	2024.06.04
KalmarCTF 2024 풀이 - Symmetry 2, 3 (0)	2024.03.19
Space WAR 2023 풀이 (1)	2023.12.31

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

ks의 잡다한 블로그

2024 Feb Space WAR (Crypto) 풀이

Beginner

SEA