Crypto CTF 2022 WriteUps

發表於 2022-07-18

分類於 CTF

這次我加入了 isanapap 和其他幾位台灣的 ctf crypto player 參加了今年的 Crypto CTF，並且很幸運的拿下了第一名。這邊大概只會寫我認為比較值得寫的題目而已，且有寫的題目也不一定是我賽中有解的題目。

medium-easy

SOTS

這題沒有 source，用 nc 連上去之後會看到

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hey math experts, in this challenge we will deal with the numbers   |
|  those are the sum of two perfect square, now try hard to find them! |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating the `n', please wait...
| Options:
|       [G]et the n
|       [S]olve the challenge!
|       [Q]uit
G
| n = 4681699452900793124255588703544500598149979834311033888906299527764579361
| Options:
|       [G]et the n
|       [S]olve the challenge!
|       [Q]uit
S
| Send your pair x, y here:

簡單來說有個 $n$ ，要找到兩個正整數 $x,y$ 符合 $x^2+y^2=n$ 。而這個最簡單的解法是在 Google 一下之後會發現 sage 中有內建 two_squares 的函數，它正好就是解這個問題的。所以直接輸進去之後就能解開了。

當然，如果要從數學上探討的話可以知道:

x^2+y^2=(x+iy)(x-iy)

所以在 Gaussian integer $\mathbb{Z}[i]$ 下把 $n$ 分解開之後就容易找到解答了。因為 $n$ 本身用 ecm.factor(n) 測試也能知道它固定為 $n=pqr$ 的格式，且數字也不大所以分解並不難。

另外也有一些單純用基本數論去解的作法，可以參考這篇 writeup。

polyRSA

這題的質數符合固定形式 $p=f(k), q=g(k)$ ，且 $\deg{f(x)}=6, \deg{g(x)}=5$ ，所以直接在 $\mathbb{Z}$ 上對 11 次多項式 $f(x)g(x)-n$ 求根可得到 $k$ ，由此可分解 $n$ 。

from Crypto.Util.number import *

n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532

P.<k> = ZZ[]
p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
f = p * q - n
k = f.roots()[0][0]
p = ZZ(p(k))
q = ZZ(q(k))
d = inverse_mod(31337, (p-1)*(q-1))
m = power_mod(enc, d, n)
print(long_to_bytes(m))

medium

Cantilever

有 $n=pq$ ，然後 flag 被切成兩半 $m_1, m_2$ ，分別以 $c_1 \equiv m_1^e \pmod{n}$ 和 $c_2 \equiv e^{m_2} \pmod{n}$ 加密。

讀 source code 可以知道 $p-1$ 和 $q-1$ 的 factor 都小於 $2^{19}$ ，所以直接用 pollard p-1 可以分解 $n$ ，然後用 RSA 可以解出 $m_1$ 。

$m_2$ 的部分是 discrete log 問題，只要分別在 $\mathbb{F}_p$ 和 $\mathbb{F}_q$ 下解開後 CRT 回來就能還原。而因為 $p-1,q-1$ 都很 smooth，直接 pohlig hellman 就能解了。

from Crypto.Util.number import *

n = 7069789930583271525053215046247773438899869283661158227309691853515987055334306019600324056376312479212090202373516405860759222837585952590589336295698718699890424169542280710721069784487366121478569760563045886361884895363592898476736269784284754788133722060718026577238640218755539268465317292713320841554802703379684173485217045274942603346947299152498798736808975912326592689302969859834957202716983626393365387411319175917999258829839695189774082810459527737342402920881184864625678296442001837072332161966439361793009893108796934406114288057583563496587655548536011677451960307597573257032154009427010069578913
c_1 = 488692928085934899944055554857568564903346089951134051486941368561567330884363274156339625953702601270565654444836193796061118053575538224794730472032345171432952984560662218697488844007827176184413713651118743456250147472678673801728916283759932987216388378211555067885210167894310696549664382751443669387953644382833924884208966436685137553434532738845959014828804809425096115758364136546390809453200055265653531950423111482644330073443545410319576097902472017235065047191133112557289289189187696092145850680765843608118584107829268136014912479701945735063525799796920293418182776436767911172221104640501952880057
c_2 = 109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212
e = 0x10001

a = 2
for p in primes(2 ^ 19):
    a = power_mod(a, p, n)
    p = gcd(a - 1, n)
    if 1 < p < n:
        print(p)
        break
q = n // p
m_1 = power_mod(c_1, inverse_mod(e, (p - 1) * (q - 1)), n)
m_2p = GF(p)(c_2).log(e)
m_2q = GF(p)(c_2).log(e)
m_2 = crt([ZZ(m_2p), ZZ(m_2q)], [p, q])
print(long_to_bytes(m_1) + long_to_bytes(m_2))

Diploma

這題也沒有 source，用 nc 連上去之後會看到

||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|  Hi all, cryptographers know that the calculation of the order of a  |
|  given element in a group is not easy at all. We are working in the  |
|  group GL(d, p), the group of invertible matrices of order `d' on a  |
|  finite field of order `p'. In each stage send the order matrix M.   |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Generating the parameters for p = 127, please wait...
| M =
[ 44 119   6]
[123  30  99]
[ 57  23  50]
| Send the order of matrix M:

要你計算矩陣 $GL(\mathbb{F}_p)$ 下矩陣的 order，而這個 sage 有內建，所以寫個腳本搞定。

from pwn import remote, context
import re

context.log_level = 'debug'

def s2row(s):
    return list(map(int, re.split(r'\s+', s[1:-1].strip())))

io = remote("08.cr.yp.toc.tf", 37313)
for _ in range(20):
    io.recvuntil(b'p = ')
    p = int(io.recvuntil(b',')[:-1])
    print(f'{p = }')
    io.recvuntil(b'M = \n')
    s = io.recvlineS().strip()
    row = s2row(s)
    mat = [row]
    for _ in range(len(row) - 1):
        s = io.recvlineS().strip()
        print(s)
        row = s2row(s)
        mat.append(row)
        print(row)
    M = matrix(GF(p), mat)
    print(M)
    od = M.multiplicative_order()
    print(od)
    io.sendline(str(od).encode())
io.interactive()
# CCTF{ma7RicES_4R3_u5EfuL_1n_PUbl!c-k3y_CrYpt0gr4Phy!}

Faonsa

這題有類似 DSA 的 signature，需要得到一個指定 message 的 signature。一個 oracle 是 signing oracle，還有另外一個 oracle 允許你 flip 任意 30 個 $p$ 的 bits。正常解法就是想辦法 flip 使得 $p-1$ 夠 smooth，然後解 signature 的 DLP 之後還原 private key 即可。

然而它的關鍵程式碼長這樣:

def main():
    border = "|"
    pr(border*72)
    pr(border, "Hello guys! This is a another challenge on fault attack too, again  ", border)
    pr(border, "our storage could apply at most `l' bit fault on ElGamal modulus, p,", border)
    pr(border, "try to sign the given message and get the flag! Have fun and enjoy!!", border)
    pr(border*72)
    pr(border, "Generating the parameters, it's time consuming ...")
    nbit = 256
    while True:
        _p = getPrime(255)
        p = 2 * _p + 1
        if isPrime(p):
            g = 2
            if pow(g, _p, p) != 1: break
            else: g += 1
    x = getRandomRange(2, p // 2)
    y = pow(g, x, p)

    B, l = [int(b) for b in bin(p)[2:]], 30
    
    MSG = "4lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P"
    m = bytes_to_long(MSG.encode('utf-8'))

    while True:
        pr("| Options: \n|\t[A]pply fault \n|\t[G]et the parameters \n|\t[S]ign the message \n|\t[V]erify the signature \n|\t[Q]uit")
        ans = sc().lower()
        if ans == 'a':
            _B = B
            pr(border, f"please send at most {l}-tuple array from indices of bits of ElGamal modulus, like: 5, 12, ...")
            ar = sc()
            try:
                ar = [int(_) for _ in ar.split(',')]
                if len(ar) <= l:
                    for i in range(len(ar)): _B[ar[i]] = (_B[ar[i]] + 1) % 2
                    P = int(''.join([str(b) for b in _B]), 2)
                    Y = pow(g, x, P)
                else: raise Exception('Invalid length!')
            except: pr(border, "Something went wrong!!")
		# omitted...

最主要是 _B = B 的地方做的是 shallow copy，當它在下面修改 _B 的時候也修改到了 B，所以只要使用 Apply fault 多次就能 flip 任意數量的 bits。而根據它的 signature verification 來說最簡單的做法是直接 $p=1$ 就能通過驗證了。

from pwn import *

# io = process(["python", "faonsa.py"])
io = remote("06.cr.yp.toc.tf", 31117)
io.sendline(b"g")
io.recvuntil(b"p = ")
p = int(io.recvline())
io.recvuntil(b"g = ")
g = int(io.recvline())
io.recvuntil(b"y = ")
y = int(io.recvline())
print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

bits = [int(x) for x in bin(p)[2:]]
print(bits)
idxs = [i for i, b in enumerate(bits) if b]
print(idxs)

chk = 30
for grp in [idxs[i : i + chk] for i in range(0, len(idxs), chk)]:
    print(grp)
    io.sendline(b"a")
    io.sendline(",".join(map(str, grp)).encode())
io.sendline(b"a")
io.sendline(str(len(bits) - 1).encode())
io.sendline(b"v")
io.sendline(b"1,1")
io.interactive()
# CCTF{n3W_4t7aCk_8y_fAuL7_!nJ3cT10N_oN_p!!!}

另外這題還有第二個 unintended，主要在這個地方:

        elif ans == 's':
            pr(border, "Please send your message to sign: ")
            msg = sc().encode('utf-8')
            if msg != MSG.encode('utf-8'):
                _m = bytes_to_long(msg)
                try:
                    sgn = sign_esa((g, P, Y), x, _m)
                    pr(border, f'sign = {sgn}')
                except:
                    import traceback
                    traceback.print_exc()
                    pr(border, "Something went wrong!!")
            else:
                pr(border, "Kidding me!? Really?")

它的 signing oracle 檢查的是 msg != MSG.encode('utf-8')，但是後面使用了 bytes_to_long(msg)，所以用 msg = b'\x00' + MSG.encode() 的話就能繞過檢查得到目標的 signature 了。

from pwn import *
import ast

# io = process(["python", "faonsa.py"])
io = remote("06.cr.yp.toc.tf", 31117)
io.sendline(b"g")
io.recvuntil(b"p = ")
p = int(io.recvline())
io.recvuntil(b"g = ")
g = int(io.recvline())
io.recvuntil(b"y = ")
y = int(io.recvline())
print(f"{p = }")
print(f"{g = }")
print(f"{y = }")

io.sendline(b"a")
io.sendline(b"0,0")
io.sendline(b"s")
io.sendline(b"\x004lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P")
io.recvuntil(b"sign = ")
sig = ast.literal_eval(io.recvlineS())
io.sendline(b"v")
io.sendline(",".join(map(str, sig)).encode())
io.interactive()
# CCTF{n3W_4t7aCk_8y_fAuL7_!nJ3cT10N_oN_p!!!}

Fiercest

這題和 Faonsa 類似，但是這邊用的是 RSA signature，也沒有 signing oracle 給你用，且 flip 的 bits 數量也只有 2。

然而前一題說的 shallow copy 的 bug 還在，所以可以把 $N$ 任意 flip 成一個質數 $p$ 就能通過這題了。

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

# context.log_level = 'debug'

# io = process(["python", "firecest.py"])
io = remote("04.cr.yp.toc.tf", 37713)
io.sendline(b"g")
io.recvuntil(b"e = ")
e = int(io.recvline())
io.recvuntil(b"n = ")
n = int(io.recvline())
print(f"{e = }")
print(f"{n = }")

bits = [int(x) for x in bin(n)[2:]]
print(bits)
idxs = [i for i, b in enumerate(bits) if b]
print(idxs)
chk = 2
for grp in [idxs[i : i + chk] for i in range(0, len(idxs), chk)]:
    print(grp)
    io.sendline(b"a")
    io.sendline(",".join(map(str, grp)).encode())

p = getPrime(n.bit_length())
bits = [int(x) for x in bin(p)[2:]]
print(bits)
idxs = [i for i, b in enumerate(bits) if b]
print(idxs)
chk = 2
for grp in [idxs[i : i + chk] for i in range(0, len(idxs), chk)]:
    print(grp)
    io.sendline(b"a")
    io.sendline(",".join(map(str, grp)).encode())
m = bytes_to_long(b"4lL crypt0sy5t3ms suck5 fr0m faul7 atTaCk5 :P")
e = 65537
d = pow(e,-1,p-1)
io.sendline(b"v")
io.sendline(str(pow(m,d,p)).encode())

io.interactive()
# CCTF{R3aLlY_tH1S_1z_Seiferts_R54_AT7aCk!!?}

Starter ECC

#!/usr/bin/env sage

from Crypto.Util.number import *
from secret import n, a, b, x, flag

y = bytes_to_long(flag.encode('utf-8'))

assert y < n
E = EllipticCurve(Zmod(n), [a, b])

try:
	G = E(x, y)
	print(f'x = {x}')
	print(f'a = {a}')
	print(f'b = {b}')
	print(f'n = {n}')
	print('Find the flag :P')
except:
	print('Ooops, ERROR :-(')

題目給予一個 $n$ 和一條橢圓曲線 $E$ 和一個點的 x 座標，該點的 $y$ 座標為 flag。

首先用 ecc.factor(n) 可以知道 $n=p^{63} q^6 r^5$ ，其中 $p=2$ ，而直接 lift_x 的話在 $p^{63}$ 的地方不知為何會花上許多時間。

查一下知道 sage 內建有 square_root_mod_prime_power，但是在處理 $p=2$ 的情況還是會花上許多時間，所以乾脆自己用 hensel lift 去解比較快。

它之所以慢的原因是因為 sage 的 implementation 使用的方法很爛 $\mathcal{O}(2^k)$ ，不過這個方法在此 commit 被修好了，所以未來在 sage 9.7 的時候就能直接用了

from Crypto.Util.number import *
from collections.abc import Iterable

x = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046477020617917601884853827611232355455223966039590143622792803800879186033924150173912925208583
a = 31337
b = 66826418568487077181425396984743905464189470072466833884636947306507380342362386488703702812673327367379386970252278963682939080502468506452884260534949120967338532068983307061363686987539408216644249718950365322078643067666802845720939111758309026343239779555536517718292754561631504560989926785152983649035
n = 117224988229627436482659673624324558461989737163733991529810987781450160688540001366778824245275287757373389887319739241684244545745583212512813949172078079042775825145312900017512660931667853567060810331541927568102860039898116182248597291899498790518105909390331098630690977858767670061026931938152924839936

# ecm.factor(n)
p = 2
q = 690712633549859897233
r = 651132262883189171676209466993073
assert n == p ^ 63 * q ^ 6 * r ^ 5


def single_lift(f, df, p, k, rs):
    # f(r) = 0 (mod p^k)
    # df(r) != 0 (mod p^k)
    # returns s such that f(s) = 0 (mod p^(k+1))
    pk = p**k
    pk1 = pk * p
    for r in rs:
        assert f(r) % pk == 0, (r, k)
        # assert df(r) % (p ** k) != 0, (r,k)
        if df(r) % p != 0:
            a = inverse_mod(df(r), p)
            s = r - f(r) * a
            assert f(s) % pk1 == 0
            yield s
        else:
            for t in range(0, p):
                s = r + t * pk
                if f(s) % pk1 == 0:
                    yield s


def hensel_lift(f, df, p, k, m, rs):
    # f(r) = 0 (mod p^k)
    # df(r) != 0 (mod p^k)
    # returns s such that f(s) = 0 (mod p^m)
    if not isinstance(rs, Iterable):
        rs = [rs]
    assert m >= k
    if m == k:
        return rs
    return hensel_lift(f, df, p, k + 1, m, single_lift(f, df, p, k, rs))


y2 = (x ^ 3 + a * x + b) % n
f = lambda x: x ^ 2 - y2
df = lambda x: 2 * x
for yp in hensel_lift(f, df, p, 1, 63, [ZZ(GF(p)(y2).sqrt())]):
    for yq in hensel_lift(f, df, q, 1, 6, [ZZ(GF(q)(y2).sqrt())]):
        for yr in hensel_lift(f, df, r, 1, 5, [ZZ(GF(r)(y2).sqrt())]):
            y = crt([ZZ(yp), ZZ(yq), ZZ(yr)], [p ^ 63, q ^ 6, r ^ 5])
            EllipticCurve(Zmod(n), [a, b])(x, y)
            print(long_to_bytes(y))
# CCTF{8E4uTy_0f_L1f7iN9_cOm3_Up!!}

裡面的 hensel lifting 是我之前自己寫的一個版本: https://gist.github.com/maple3142/acf736f336cb303cdf47a3ef18f543dc

另外賽後有在 discord 知道原來這種 square root modulo prime power 可以直接用 p-adic 解，大概像是這樣:

yp = ZZ(Qp(p, prec=63)(y2).sqrt()) % (p ^ 63)
assert power_mod(yp, 2, p ^ 63) == y2 % (p ^ 63)

medium-hard

313 Loyal

這題首先要自己選一組 Paillier 的 public key 給 server，然後再決定一個多項式 $f(x)$ 。server 那邊會有一些 flag points。對於每個 flag points 中的點 $x$ 它會用 Paillier 的同態性質計算 $k f(x)+x$ 給你，其中 $k$ 是一個每次都會變的隨機數。

首先因為 public key 自選，所以 ciphertext 都能很容易的解密。而取得那些點的方法就只要用 $f(x)=n$ 就能把 $k$ 消掉。

from Crypto.Util.number import *
from pwn import *
import numpy as np


def keygen(nbit):
    p, q = [getPrime(nbit) for _ in "__"]
    n, phi = p * q, (p - 1) * (q - 1) // 2
    while True:
        g = getRandomRange(2, n**2)
        if GCD(g, n) == 1:
            w = (pow(g, phi, n**2) - 1) // n
            if GCD(w, n) == 1:
                u = inverse(w, n)
                break
    pkey, skey = (n, g), (phi, u)
    return pkey, skey


def add(pkey, a, b):
    n, g = pkey
    return pow(a * b, 1, n**2)


def multiply(pkey, a, k):
    n, g = pkey
    return pow(a, k, n**2)


def encrypt(pkey, m):
    n, g = pkey
    while True:
        r = getRandomRange(2, n)
        if GCD(r, n) == 1:
            break
    return (pow(g, m, n**2) * pow(r, n, n**2)) % (n**2)


def decrypt(pkey, skey, c):
    n, g = pkey
    phi, u = skey
    t = (pow(c, phi, n**2) - 1) // n
    return (t * u) % n


def evaluate_poly(pkey, poly, point):
    n, g = pkey
    _point = point
    result = poly[0]
    for term in poly[1:]:
        result = add((n, g), result, multiply((n, g), term, _point))
        _point = (_point * point) % n
    return result


pkey, skey = keygen(256)
print(pkey)

# io = process(['python', '313loyal.py'])
io = remote("07.cr.yp.toc.tf", 31377)
lenflag = 43


def sendparam(io, n, g, poly):
    io.sendline(b"S")
    io.sendline(f'{n},{g},{" ".join(map(str, poly))}'.encode())
    res = []
    for _ in range(lenflag):
        io.recvuntil(b"=")
        res.append(int(io.recvline()))
    return [decrypt(pkey, skey, x) for x in res]


def encrypt_poly(poly):
    return [encrypt(pkey, x) for x in poly]


n, g = pkey
res = sendparam(io, *pkey, encrypt_poly([n]))
s = np.array(res).argsort()
f = np.array([x % (2**10) for x in res])[s]
print(bytes(f.tolist()))
# CCTF{4n0t3R_h0MomORpH1C_3NcRyP7!0n_5CH3Me!}

Soda

這題有個基於 RSA 的特殊 signature:

def soda(g, p, q, m):
	n, phi = p * q, (p - 1) * (q - 1)
	if isPrime(m) and m.bit_length() <= 128:
		e = m
	else:
		e = 2 * (pow(g, m**2, n) % 2**152) ^ 1
	if GCD(e, phi) == 1:
		d = inverse(e, phi)
		return pow(g, d, n)

一樣是要 sign 某個指定的 message，還有附帶一個 oracle 讓你 sign 該 message 以外的所有值。

然而可以注意到它用了 m**2，這代表 $m$ 和 $-m$ 都有一樣的 signature，因此用 oracle sign $-m$ 之後拿到 verify 就能有 flag 了。

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

# io = process(['python', 'soda_server.py'])
io = remote("01.cr.yp.toc.tf", 37711)
io.sendline(b"G")
io.recvuntil(b"n = ")
n = int(io.recvline())
print(f"{n = }")

m = bytes_to_long(b"Long Live Crypto :))")
io.sendline(b"T")
io.sendline(str(-m).encode())
io.recvuntil(b"soda(g, p, q, m) = ")
sig = int(io.recvline())
io.sendline(b"V")
io.sendline(str(sig).encode())
io.interactive()
# CCTF{f4cToriZat!On__5Tt4cK_0n_4_5i9na7urE!}

真正的預期解應該就如 flag 所說，透過分解它的特殊的 $e$ 去 forge 吧。

Sparse

#!/usr/bin/env python3

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

def sparse(p, k):
	nbit = p.bit_length()
	while True:
		CF = [getRandomRange(-1, 1) for _ in '_' * k]
		XP = [getRandomRange(3, nbit - 3) for _ in '_' * k]
		A = sum([CF[_] * 2 ** XP[_] for _ in range(0, k)])
		q = p + A
		if isPrime(q) * A != 0:
			return q

p = getPrime(417)
q = sparse(p, 5)
e, n = 65537, p * q
print(f'n = {n}')
m = bytes_to_long(flag.encode('utf-8'))
assert m < n
c = pow(m, e, n)
print(f'c = {c}')

這題的 $p,q$ 符合

q=p-\sum_{i \in S}{2^i}

其中 $|S| \leq 5$ ，所以可以考慮直接爆破這個 $|S|$ 然後解二次方程就能分解掉了。

我這個腳本只有爆破到 $|S|=3$ ，但是以這題的參數來說 $|S|=1$ 就夠了。

from Crypto.Util.number import *
from itertools import combinations, chain
import gmpy2


n = 94144887513744538681657844856583985690903055376400570170371837200724227314957348031684706936655253125445176582486308241015430205703156336248578475428712275706238423997982248462635972817633320331030484841129628650918661036694615254018290264619628335177
c = 80250313885079761377138486357617323555591919111371649902793873860183455237161293320577683249054725852540874552433031133240624696119120378419135912301004715004977978507247634217071922495893934816945961054193052791946557226599493364850793396744903765857

tp = [gmpy2.mpz(1 << i) for i in range(512)]
it = chain(*[combinations(range(3, 417 - 3), i) for i in range(4)])
for cf in it:
    A = -sum([tp[i] for i in cf])
    # q = p + A
    # n=pq=p(p+A)
    # p^2+Ap-n=0
    # D=A^2-4*1*-n
    D = A**2 + 4 * n
    if gmpy2.is_square(D):
        d = gmpy2.isqrt(D)
        p = (-A + d) // 2
        q = n // p
        print(p)
        print(q)
        print(p * q == n)
        print(bin(p - q))
        break
e = 65537
d = pow(e, -1, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)))

另外賽後有人說可以用類似 Google CTF 有題 YAFM 的做法 (或是 PlaidCTF 的 xorsa)，從 LSB 開始 bit by bit 恢復，然後 coppersmith。

Versace

這題有個神秘的 $n$ 和 $e=65537$ ，還有 $\mathit{fi}=5^x, \mathit{th}=13^y$ 為 public key。

然後加密是

\begin{aligned} c_1&=k^e \\ c_2&=5^u \\ c_3&=13^v \\ c_4&=\mathit{fi}^u \mathit{th}^v (k+1)^e m \end{aligned}

一律在 $\mathbb{Z}_n$ 下計算的

可以知道它算是 diffie hellman + rsa 的混和體，因為應該要算 dlog 所以 Utaha 猜測 $\phi(n)$ 應該很 smooth，所以我用 rsactftool 的 pollard p-1 就成功把它分解為 $n=pqr$ 。

之後就分別 dlog 後 crt，另外也解密回 $k$ 之後就能得到 $m$ 。

from Crypto.Util.number import *
import gmpy2

n = 141886649864474336567180245736091175577519141092893110664440298696325928109107819365023509727482657156444454196974621121317731892910779276975799862237645015028934626195549529415068518701179353407407170273107294065819774663163018151369555922179926003735413019069305586784817562889650637936781439564028325920769
p = 106618752612001652530923691512073519044983443846656721126867402977583225110529
q = 104492689192892408108975038373966852967734827395344990285038653889732962680833
r = 12735676857401163601385118447483795668229644118624917660231942016044435957817541173149617917604011645058841872384142319678290750015804888147769138207522817
assert p * q * r == n
assert all(is_prime(p) for p in [p, q, r])
n, e, fi, th = (
    141886649864474336567180245736091175577519141092893110664440298696325928109107819365023509727482657156444454196974621121317731892910779276975799862237645015028934626195549529415068518701179353407407170273107294065819774663163018151369555922179926003735413019069305586784817562889650637936781439564028325920769,
    65537,
    125494383162828289973475117066203219587304356806057400173045477137700391356840397636206107925460433939119412469184723408274805651096828270461235114589209044543108910295997506041345432448035371092981112305692014036117962906342882215492784319467728201344342591126197621795974549431806828947671232171059809967991,
    138257736445723754207239869344459794807808248188757696052272858978544083465381926995900887162870612185045399616892685750962667762789508194359878372465943702647287813020223160406789982302692329883577043521781397505345137392777694159916452699296748509096494301465498192136911589776144421856343483031920756519249,
)
c1, c2, c3, c4 = (
    88920444409754899592335110119456825172544580816901497880270628553955508488170483498726344301421934007876515783471747430111559265733377611608113080609941423596790625452564403457107243481310552344096683637970851198148957553062631972064855184560312748315536290880767375156429548232884895308088306625307674645678,
    45539956581550314230977168288877082058214432324397034618326297663129864608739856352261029083496409133620455599376139981575342903237304167908534019438874239934645347320209162850653298515960349717851268830205737252263548268549179642907155075129172651815656517165432021020317138111104384072600486843574535899860,
    69849817078368866947686316374564245958824276178721440086311727765763093314086243149277327430285562537315291446874425715021031882041090977200029684675392021083309757246079110723453995717856469919242618068208424495615283285085190255592463862108516827540775850882615540406750734639040903336048095547788528187976,
    20285007564778647051596518902857046010716548094264173639037549746086538656814534621919993169453446815272789643882592631536755194356753848872566348635207131520597253599540337542405837637606323276917410384296602682043902830628022440639028040137219164743287397377174047728489836106561656239657061612908104843401,
)

print(factor(p - 1))
print(factor(q - 1))
print(factor(r - 1))


def alllog(a, b):
    xp = ZZ(GF(p)(a).log(b))
    xq = ZZ(GF(q)(a).log(b))
    xr = ZZ(GF(r)(a).log(b))
    assert power_mod(b, xp, p) == a % p
    assert power_mod(b, xq, q) == a % q
    assert power_mod(b, xr, r) == a % r
    x = crt(
        [xp, xq, xr],
        [
            GF(p)(b).multiplicative_order(),
            GF(q)(b).multiplicative_order(),
            GF(r)(b).multiplicative_order(),
        ],
    )
    assert power_mod(b, x, n) == a
    return x


d = inverse_mod(e, (p - 1) * (q - 1) * (r - 1))
k = power_mod(c1, d, n)
x = alllog(fi, 5)
y = alllog(th, 13)
t = power_mod(c2, x, n) * power_mod(c3, y, n) * power_mod(k + 1, e, n) % n
m = (c4 / t) % n
print(long_to_bytes(m))

Watery soup

這題有很特別的 oracle，需要選兩個數 $p,g$ 。 $p$ 是一個 128 到 224 bits 的質數，而 $g$ 是 64 到 128 bits 的數。

然後記 flag (超過 256 bits) 為 $x$ ，它會給你:

r \equiv (g^3 x)^{x-g} x + x^2 + g \pmod {p}

這題我賽中沒碰，不過後來有按照 Utaha 的做法再實作一遍。概念上就是因為 $x^x$ 很難處理，需要想辦法消掉，所以會想用 $g^3=1$ 的性質看看能不能怎樣。

然後他的方法就是除了 $g^3=1$ 以外再挑個 $tg=t+1$ ，然後對 oracle 送 $(p,t)$ 和 $(p,tg)$ 。假設拿到的數字分別是 $r_1, r_2$ ，可知它們為:

\begin{aligned} r_1 &= (t^3 x)^{x-t} t + x^2 + g \\ r_2 &= (t^3 x)^{x-t-1} t + x^2 + tg \end{aligned}

整理一下得到:

\begin{aligned} r_1 &= (t^3 x)^{x-t} t + x^2 + g \\ (t^3 x)r_2 &= (t^3 x)^{x-t} t + (t^3 x)(x^2 + tg) \end{aligned}

消掉之後得到一個 $x$ 的多項式可以解，也就拿到 $x \bmod{p}$ ，之後再 CRT 就能拿回 flag 了。

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


def gen():
    while True:
        p = ZZ(getPrime(128))
        rs = [ZZ(x) for x in GF(p)(1).nth_root(3, all=True) if x != 1]
        if len(rs) == 0:
            continue
        g = rs[0]
        t = inverse_mod(g - 1, p)  # t*g=t+1
        if (64 < t.nbits() < 128) and (64 < (t * g % p).nbits() < 128):
            return p, g, t


# io = process(["python", "watery_soup.py"])
io = remote("05.cr.yp.toc.tf", 37377)
mods = []
rems = []
while len(mods) < 3:
    p, g, t = gen()
    io.sendline(b"S")
    io.sendline(str(p).encode())
    io.sendline(str(t).encode())
    io.recvuntil(b"mixed flag: ")
    r1 = ZZ(io.recvline())
    io.sendline(b"S")
    io.sendline(str(p).encode())
    io.sendline(str((t * g) % p).encode())
    io.recvuntil(b"mixed flag: ")
    r2 = ZZ(io.recvline())
    P = PolynomialRing(GF(p), "x")
    x = P.gen()
    t3x = t**3 * x
    lhs = r1 - t3x * r2
    rhs = x**2 + t - t3x * (x**2 + t * g)
    f = lhs - rhs
    if len(f.roots()) != 1:
        continue
    x = ZZ(f.roots()[0][0])
    rems.append(x)
    mods.append(p)
x = crt(rems, mods)
print(long_to_bytes(x))
# CCTF{Pl34se_S!r_i_w4N7_5omE_M0R3_5OuP!!}

另外 hellman 有給另一個作法是送 $g,2g,4g,8g$ 之後可以得到一個多項式系統，一樣能解出 $x$ 。

備註: 這題似乎是基於這題的 (by hellman)

hard

Persian cat

這題有一個很奇怪的 block cipher，code 既長又難讀。但是解題所需的 code 其實就這一塊而已:

def keygen(u, v):
    return [a ^ b for a, b in zip(u, v)][:20]


def encrypt(msg, key):
    msg = padding(msg)
    blocks = [msg[i * 32 : i * 32 + 32] for i in range(len(msg) // 32)]
    ciphers = []
    enc = encrypt_iginition([ord(item) for item in blocks[0]], key)
    ciphers.append(enc)
    for i in range(len(blocks) - 1):
        enc = encrypt_iginition(
            [ord(item) for item in blocks[i + 1]],
            keygen([ord(item) for item in blocks[i]], ciphers[i]),
        )
        ciphers.append(enc)
    return "".join("".join(str(format(i, "02x")) for i in item) for item in ciphers)

可以知道它先分 block，然後拿前一個 block 的 plaintext 和 ciphertext 去 xor 得到下一個 block 的 key。而題目的 oracle 是允許你得到 encrypt(msg + flag, key) 的結果，所以只要 msg == 'a' * 32 就能讓 flag 對齊 block，然後得到解密 flag 所需的 key 了。

再來是它的解密函數其實不用自己寫，因為 encrypt_iginition 似乎在同樣的 key 下是自身的反函數，所以直接這樣就能解開了:

pt = b"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
ct = bytes.fromhex(
    "127f1023480f4f61caab33b69825447a38f8d62592f4c1b0fb2f92cf3b10e4bb168e208a12f39b725addbe1e8e9f923477fa62508c0f9d7fbe0ca52026e470458f6fbf2b0ca4865e50018d735e055233ab0953882f0f3da553fcab3db6710621722ae640fa3b9e3b47c52597b9e91dc1bf6d139ea7c1cb58c83228d7b8ae3250"
)
blks = [ct[i : i + 32] for i in range(0, len(ct), 32)]
for prev, cur in zip(blks, blks[1:]):
    key = keygen(pt, prev)
    pt = bytes(encrypt_iginition(cur, key))
    print(pt.decode(), end="")
# the flag is: CCTF{d0_yOu_tH47_the_ori9iN_of_Iraqi_C1ph3r_Iz_Iran?!!}****************************

另外一個更簡單的做法是注意到使用相同 key 加密兩次之後相當於沒有加密，所以就能直接這樣拿 flag。 (by hellman)

medium-easy#

SOTS#

polyRSA#

medium#

Cantilever#

Diploma#

Faonsa#

Fiercest#

Starter ECC#

medium-hard#

313 Loyal#

Soda#

Sparse#

Versace#

Watery soup#

hard#

Persian cat#