先週末に開催されていたASIS CTF 2021に出たので自分が解いた問題のWriteupを書きます。

Table of Contents §

Crypto Warm up §

次のようなスクリプトとその実行結果が与えられる

#!/usr/bin/env python3

from Crypto.Util.number import *
import string
from secret import is_valid, flag

def random_str(l):
	rstr = ''
	for _ in range(l):
		rstr += string.printable[:94][getRandomRange(0, 93)]
	return rstr

def encrypt(msg, nbit):
	l, p = len(msg), getPrime(nbit)
	rstr = random_str(p - l)
	msg += rstr
	while True:
		s = getRandomNBitInteger(1024)
		if is_valid(s, p):
			break
	enc = msg[0]
	for i in range(p-1):
		enc += msg[pow(s, i, p)]
	return enc

nbit = 15
enc = encrypt(flag, nbit)
print(f'enc = {enc}')

15bitの整数pを法として1024bitの整数sからidx = pow(s,i,p)を計算し、enc[i+1] = msg[idx]となるように暗号文を並べ替えている。pmsgencの長さと一致している。また、明らかにs >> pなのでsは1024bitではあるが、実質pと同程度のエントロピーしかない。

この構成から例えばフラグ2文字目の文字I(フラグフォーマットはASIS{...})はを解いてに対応するインデックスに飛ぶのでsp未満の数で回してこの離散対数問題を解き(pが小さいので簡単に解ける)、対応するインデックスにIが存在するかを調べる。これを後続のS,{についても同様に行う事でsの候補を絞る事が出来る。

これらのsの候補を用いて復号すると1つだけまともに復号出来たのがあったのでそれがフラグ

from xcrypto.prime import is_prime
from xcrypto.dlp import baby_step_giant_step


def exploit():
    enc = open("output.txt").read()
    p = len(enc)
    print(is_prime(p), p)

    s_cand = []
    for s in range(2, p):
        if pow(s, (p-1)//2, p) == 1:
            continue
        if pow(s, (p-1)//3, p) == 1:
            continue
        if pow(s, (p-1)//7, p) == 1:
            continue
        if pow(s, (p-1)//29, p) == 1:
            continue

        e = baby_step_giant_step(s, 2, p)
        if e is None:
            continue
        if enc[e+1] != "I":
            continue

        e = baby_step_giant_step(s, 3, p)
        if e is None:
            continue
        if enc[e+1] != "S":
            continue

        e = baby_step_giant_step(s, 4, p)
        if e is None:
            continue
        if enc[e+1] != "{":
            continue

        s_cand.append(s)

    for s in s_cand:
        flag = "AS"
        for i in range(2, 100):
            e = baby_step_giant_step(s, i, p)
            m = enc[e+1]
            flag += m

        print(flag)


if __name__ == "__main__":
    exploit()
  • Flag: ASIS{_how_d3CrYpt_Th1S_h0m3_m4dE_anD_wEird_CrYp70_5yST3M?!!!!!!}

Spiritual §

配布スクリプトは無いが、サーバーに繋ぐと次のようなクイズが出題される。

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+   hello, you know valuable information about given elliptic curve,   +
+   your mission is to answer the question in each stage quickly!      +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| E is an elliptic curve with k elements in the following form: 
| E: y**2 = x**3 + a*x + b (mod p) 
| p = 6615696742597842521
| a = ?
| b = ?
| k = 6615696744334514383
| What's the number of elements of E over finite field GF(p**n) where n = 5?

楕円曲線の位数と法が与えられている状況で上の同じ楕円曲線の位数を答えよという問題。

この問題見る前は楕円曲線の位数について何も知らなかったのでたまたま今取っている講義の教科書に指定されていた「代数学から学ぶ暗号理論|日本評論社」を読んだらフロベニウス写像のトレースと位数、有限体の法となっている素数に次の関係があるらしい。

$$ \mathrm{tr}(\varphi) = 1 + p - k $$

また、このトレースを用いるとの位数も次の式で求める事が出来るらしい

$$ k_n = p^n + 1 - \alpha^n + \beta^n $$

ここでは特性多項式:の2つの根である。

というわけでこれに沿って計算するだけのコードを書いて17問正解したらフラグをくれた。

ところで、こういう問題は最初に何問正解したらフラグをくれるのかを明記してほしいです。

from pwn import remote


def create_conn():
    host, port = "168.119.108.148", 13010

    return remote(host, port)


def solve(sc):
    sc.recvuntil(b"p = ")
    p = int(sc.recvline())
    sc.recvuntil(b"k = ")
    k = int(sc.recvline())
    sc.recvuntil(b"n = ")
    n = int(sc.recvline().strip()[:-1])
    print("[+] instance:")
    print(f"  {p=}")
    print(f"  {k=}")
    print(f"  {n=}")

    tr_phi = 1 + p - k
    D = sqrt(tr_phi^2 - 4*p)
    alpha = (tr_phi + D) / 2
    beta = (tr_phi - D) / 2

    alpha_n = expand(alpha^n)
    beta_n = expand(beta^n)

    answer = p^n + 1 - alpha_n - beta_n
    print(f"[+] answer: {answer}")

    sc.sendline(str(answer).encode("utf-8"))


def exploit():
    sc = create_conn()
    cnt = 17
    for i in range(cnt):
        solve(sc)

    sc.interactive()




if __name__ == "__main__":
    exploit()
  • flag: ASIS{wH47_iZ_mY_5P1R!TuAL_4NiMal!???}

Madras §

次のようなスクリプトとその実行結果をくれる

#!/usr/bin/env python3

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

def gentuple(nbit):
	a, b, c = [getPrime(nbit // 3) for _ in '012']
	return a, b, c

def encrypt(msg, params):
	a, b, c = params
	e, n = 65537, a * b * c
	m = bytes_to_long(msg)
	assert m < n
	enc = pow(m, e, n)
	return enc

nbit = 513
a, b, c = gentuple(nbit)
enc = encrypt(FLAG, (a, b, c))

print(f'a*b + c = {a*b + c}')
print(f'b*c + a = {b*c + a}')
print(f'c*a + b = {c*a + b}')
print(f'enc % a = {enc % a}')
print(f'enc % b = {enc % b}')
print(f'enc % c = {enc % c}')
print(f'enc     = {enc}')

Multi-prime RSAで暗号化されていて、a,b,cの関係式が3つ与えられるので、終結式に放り込むと解けて素因数分解出来る。

from Crypto.Util.number import long_to_bytes


def get_params():
    ha = 4414187148384348278031172865715942397786003125047353436418952679980677617016484927045195450392723110402
    hb = 2621331497797998680087841425011881226283342008022511638116013676175393387095787512291008541271355772802
    hc = 4553352994596121904719118095314305574744898996748617662645730434291671964711800262656927311612741715902
    ca = 1235691098253903868470929520042453631250042769029968
    cb = 2235727505835415157472856687960365216626058343546572
    cc = 1197976933648163722609601772402895844093866589777721
    cn = 6238548897897912462708514382106387305984378113132192980353695746912882399991285268937548949835500837749446265632471076030233510866260067177632747513323223

    return (ha, hb, hc, ca, cb, cc, cn)


def exploit():
    ha, hb, hc, ca, cb, cc, cn = get_params()
    PR.<a,b,c> = PolynomialRing(ZZ)

    fa = a + b*c - ha
    fb = b + a*c - hb
    fc = c + a*b - hc

    r1 = fc.resultant(fb, c)
    print(r1)
    r2 = fc.resultant(fa, c)
    print(r2)
    r = r1.resultant(r2, b)
    print(r)

    ra = r.univariate_polynomial().roots()[0][0]
    rb = r2(a=ra).univariate_polynomial().roots()[0][0]
    rc = fc(a=ra, b=rb).univariate_polynomial().roots()[0][0]

    assert ra + rb*rc == ha
    assert rb + ra*rc == hb
    assert rc + rb*ra == hc

    N = ra*rb*rc
    phi = (ra-1)*(rb-1)*(rc-1)
    e = 65537

    d = inverse_mod(e, phi)
    m = pow(cn, d, N)

    print(long_to_bytes(m))


if __name__ == "__main__":
    exploit()
  • Flag: ASIS{m4dRa5_iZ_RSA_l1k3_cH41L3n9E?!!}

Pinhole §

次のようなスクリプトとその実行結果をくれる

#!/usr/bin/env sage

from sage.all import *
from Crypto.Util.number import *
from secret import a, flag

def random_poly(degree):
	R.<x> = ZZ[]
	f = x**degree
	for i in range(1, degree):
		f += randint(-3, 3) * x ** (degree - i)
	return f

def genkey(a):
	M, N = [SL2Z.random_element() for _ in '01']  # Special Linear Group

	A = N * matrix(ZZ, [[0, -1], [1, 1]]) * N**(-1)
	B = N * matrix(ZZ, [[0, -1], [1, 0]]) * N**(-1)
	r, s = [randint(5, 14) for _ in '01']
	U, V = (B * A) ** r, (B * A**2) ** s  # V is not used?

	F = []
	for _ in range(2):
		Ux = [random_poly(randint(1, 4)) for _ in range(4)]
		Ux = [Ux[i] - Ux[i](a) + U[i // 2][i % 2] for i in range(4)]
		Ux = matrix([[Ux[0], Ux[1]], [Ux[2], Ux[3]]])
		F.append(Ux)

	X, Y = M * F[0] * M ** (-1), M * F[1] * M ** (-1)
	pubkey, privkey = (X, Y), (M, a)
	return pubkey, privkey

def encrypt(msg, pubkey):
	X, Y = pubkey
	C = Y
	for b in msg:
		C *= X ** (int(b) + 1) * Y
	return C

pubkey, privkey = genkey(a)
msg = bin(bytes_to_long(flag.lstrip(b'ASIS{').rstrip(b'}')))[2:]
enc = encrypt(msg, pubkey)

print(f'pubkey = {pubkey}')
print(f'enc = {enc}')

秘密となっているMは特殊線形群とかいうやつの要素らしく、SageのSL2Z.random_element()だと各成分の絶対値が高々100のものが返される。そこでまず特殊線形群の要素で成分が小さいものを全部調べると100000弱だったのでこれを候補として更に絞り込む。

行列X,YはそれぞれX = M * F[0] * M**(-1), Y= M * F[1] * M**(-1)であり、F[0], F[1]はその作り方から定数項以外の係数の絶対値が高々3である(random_poly()より)。というわけでMの候補とX,YからF[0], F[1]を計算し、その任意の成分がこのような小さい係数の多項式であるようなMを探す。すると4つに絞れた上にこれらは符号を除いて差が無かったので殆ど一意に定まった。

問題は暗号化手順でC *= X ** (int(b) + 1) * Yをフラグの各bitに対して行っている。X,Yの定義から計算すると次が成り立つ。

$$ M^{-1} C M = F_1 \left( \prod_i F_0^{b_i + 1} F_1 \right) $$

ここでSageではF[0], F[1]の逆行列を計算出来るが、要素が整数係数多項式ではなく多項式の分数になる。しかし、前述の式を見れば分かるように左辺はF[1]と何らかの整数係数多項式を成分に持つ行列の積であり、F[1]**(-1)を計算して両辺左からかけてあげるとどちらも整数係数多項式を成分に持つ行列が現れる。

これを利用して右辺の項の数を減らすように左からF[0]**(-1)F[1]**(-1)を掛けていき、整数係数多項式を成分に持つ行列が現れるかどうかをオラクルにして各ビットを特定する事が出来る。

無理にassertionを挟んだせいでエラーを吐くが、適宜フラグのビットを出力していたので残りは気合で解いたスクリプトは以下の通り。

load("result.sage")


def search():
    cand = []
    for a in range(-100, 100):
        if a == 0:
            continue
        for b in range(-100, 100):
            for c in range(-100, 100):
                nume = b*c + 1
                denom = a
                if nume % denom != 0:
                    continue
                d = nume // denom
                if abs(d) >= 100:
                    continue
                assert a*d - b*c == 1
                cand.append((a,b,c,d))

    return cand


def get_pubkey():
    R.<x> = ZZ[]
    X = [[ 1235*x^2 - 4196*x + 2802185, 4225*x^2 - 14356*x + 9559410],[  -361*x^2 + 1227*x - 821422, -1235*x^2 + 4198*x - 2802211]]
    X = matrix(R, X)
    Y = [
        [  -779*x^4 - 2829*x^3 + 205*x^2 + 252*x + 40630633, -2665*x^4 - 9676*x^3 + 697*x^2 + 863*x + 138967416],[      228*x^4 + 828*x^3 - 60*x^2 - 73*x - 11893098, 780*x^4 + 2832*x^3 - 204*x^2 - 250*x - 40677503]
    ]
    Y = matrix(R, Y)

    return X,Y


def check_matrix(F):
    F = [F[0][0], F[0][1], F[1][0], F[1][1]]
    for f in F:
        coefs = f.coefficients()[1:]
        for c in coefs:
            if abs(c) > 3:
                return False

    return True


def recover_M():
    cand = search()
    X,Y = get_pubkey()
    M_cand = []
    for i, (a,b,c,d) in enumerate(cand):
        M = matrix(ZZ, [[a,b],[c,d]])
        M_inv = matrix(ZZ, [[d,-b],[-c,a]])
        F_1 = M_inv * X * M
        F_2 = M_inv * Y * M
        res = check_matrix(F_1)
        if res and check_matrix(F_2):
            print("[+] Found!!", (a,b,c,d))
            print(M)
            print(F_1)
            print(F_2)
            M_cand.append(M)
            print("=====" * 10)

    return M_cand


# from `recover_a` and `recover_M`
def get_privkey():
    raw_M = [
        (-65, 41, 19, -12), (-41, -65, 12, 19), (41, 65, -12, -19), (65, -41, -19, 12)
    ]

    Ms = []
    for a,b,c,d in raw_M:
        M = matrix(ZZ, [[a,b], [c,d]])
        assert M in SL2Z
        Ms.append(M)

    a = 14

    return Ms, a


def recover_a():
    X,Y = get_pubkey()
    a_cand = []
    M_cand = recover_M()
    for M in M_cand:
        print(M)
        F_X = M^(-1) * X * M
        F_Y = M^(-1) * Y * M
        for a in range(50000):
            if F_X(a) == F_Y(a):
                print("[+] Found!!", a)
                U = F_X(a)


def exploit():
    RZ.<x> = ZZ[]
    C = matrix(RZ, enc)
    X, Y = get_pubkey()
    Ms, a = get_privkey()
    for M in Ms:
        MCM = M^(-1) * C * M
        F_X = M^(-1) * X * M
        F_Y = M^(-1) * Y * M
        F_X_inv = F_X^(-1)
        F_Y_inv = F_Y^(-1)
        lhs = F_Y_inv * MCM
        assert lhs.denominator() == 1

        flag = ""
        while True:
            print(flag)
            lhs = F_X_inv * lhs
            assert lhs.denominator() == 1
            _lhs = F_X_inv * lhs
            if _lhs.denominator() == 1:
                flag = flag + "1"
                __lhs = F_Y_inv * _lhs
                assert __lhs.denominator() == 1
                lhs = __lhs
            else:
                _lhs = F_Y_inv * lhs
                assert _lhs.denominator() == 1
                flag = flag + "0"
                lhs = _lhs


if __name__ == "__main__":
    # L0OpHo13S_iN_cRyp705YST3mS!
    exploit()

ちなみにaも算出出来たが使わなかった、謎

  • Flag: ASIS{L0OpHo13S_iN_cRyp705YST3mS!}

Lagleg §

次のようなスクリプトとその実行結果が与えられる。

#!/usr/bin/env python3

from Crypto.Util.number import *
from gmpy import *
from math import gcd
from flag import flag

def lag(k, a, n):
	s, t = 2, a
	if k == 0:
		return 2
	r = 0
	while k % 2 == 0:
		r += 1
		k //= 2
	B = bin(k)[2:]
	for b in B:
		if b == '0':
			t = (s * t - a) % n
			s = (s **2 - 2) % n
		else:
			s = (s * t - a) % n
			t = (t** 2 - 2) % n
	for _ in range(r):
		s = (s ** 2 - 2) % n
	return s

def legkey(nbit):
	while True:
		r = getRandomNBitInteger(nbit >> 1)
		s = getRandomNBitInteger(nbit >> 3)
		p, q = r**5 + s, s + r
		if isPrime(p) and isPrime(q):
			while True:
				a = getRandomRange(2, q)
				if q*legendre(a, p) - p*legendre(a, q) == p - q:
					return p, q, a

def keygen(p, q, a):
	e = 65537
	if gcd(e, p**2 - 1) * gcd(e, q**2 - 1) < e:
		d = inverse(e, (p**2 - 1) * (q**2 - 1))
		x = pow(d, e, n)
		y = lag(x, a, p * q)
		return e, y, d

def encrypt(m, n, a, y, e):
	assert m < n
	r = getRandomRange(2, n)
	enc = (lag(r, a, n), (lag(r, y, n) + lag(e, m, n)) % n)
	return enc

p, q, a = legkey(256)
n = p * q
e, y, d = keygen(p, q, a)
m = bytes_to_long(flag)
c = encrypt(m, n, a, y, e)
print(f'a = {a}')
print(f'n = {n}')
print(f'y = {y}')
print(f'C = {c}')

「ここで扱われたCryptosystemについては理解する必要が無い」と私の中のゴーストが囁くので無視してnの素因数分解をまず試みる。ちなみに最近、攻殻機動隊S.A.C.を一気に見ました、面白かったです。

2つの素数はそれぞれ128bit, 32bitというCryptoにしては比較的小さい値を用いて次のように計算されている。

$$ \begin{aligned} p = r^5 + s \cr q = r+s \end{aligned} $$

ここでなのでである。そこで、ある程度素数生成の実験を繰り返すとは高々程度である事が判明した。というわけでから1ずつ減らしていくことで正しいを探した。

この判定にはより、が正の整数解を持つという条件を利用した。

これは30分ぐらい回すと無事に求められ、つまり素因数分解が成功した。

あとは復号するだけだが、正直よくわかっていない。2年半CTFをやってきた勘によればenc = (lag(r, a, n), (lag(r, y, n) + lag(e, m, n)) % n)がElGamal暗号っぽい形をしていると感じたのでべき乗をlag、乗算/除算を加算/減算に対応させてElGamal暗号と同様の復号手順を経ることでlag(e,m,n)をまず求める。問題スクリプトによれば鍵生成時に秘密鍵dd = inverse(e, (p**2 - 1) * (q**2 - 1))で求めていたのでこれをlagの第1引数に入れてlag(e,m,n)を第2引数に入れたら復号されるんじゃないかとGuessしたら何故か解けた。

r導出用のコード §

from Crypto.Util.number import long_to_bytes
from math import gcd, isqrt
from xcrypto.num_util import int_nth_root


def get_params():
    a = 192948041792305023195893277034532781336
    n = 772559547290160010920412621051392165317498598296084946084386444091060134053985973087541256301003639549317798291916637210182966424107689011211268907278162096553174971554689109947325734336069313105789282878112740205249104820920364881
    y = 754843853942922590978288450377461057162899072980081889481597335367906588582097339709346991452615504422434823707721197330881973700388055679080814559570248350531810374624494389646277873934234170885190847719684200687267925979436889772
    C = (9083709539234699681499154559006541145975405183323215645582033885264296926186620280958201308661746194284022873377667665062501349047202357817146222033735539058147945671541486202387767382626733526030628929826676457655813734637020574, 625771268848498566477216756364333384750869252753726246816617776940622341574266652518894117167008714362418009723919180248010211052475114496172513936468417590330695688907796560242492250071433491517329459840410014214097477377322316145)

    return (a, n, y, C)



def exploit():
    a,n,y,C = get_params()

    start_r = int_nth_root(n, 6)
    r = start_r
    diff = 0
    while True:
        if diff % 10000000 == 0:
            print(diff)
        D = (r**5 + r)**2 - 4*(r**6 - n)
        sqrt_D = isqrt(D)

        if sqrt_D**2 == D:
            print("[+] Found!!", r)
            break

        diff -= 1
        r -= 1


if __name__ == "__main__":
    exploit()

復号コード §

from Crypto.Util.number import long_to_bytes, inverse
from math import gcd, isqrt
from xcrypto.num_util import solve_quadratic_eq


def lag(k, a, n):
    s, t = 2, a
    if k == 0:
        return 2
    r = 0
    while k % 2 == 0:
        r += 1
        k //= 2
    B = bin(k)[2:]
    for b in B:
        if b == '0':
            t = (s * t - a) % n
            s = (s **2 - 2) % n
        else:
            s = (s * t - a) % n
            t = (t** 2 - 2) % n
    for _ in range(r):
        s = (s ** 2 - 2) % n
    return s


def factorize(n, r):
    ss = solve_quadratic_eq(1, r**5+r, r**6 - n, int_sol=True)
    s = ss[0] if ss[0] > 0 else ss[1]
    p = r**5 + s
    q = s+r
    assert p*q == n

    return (p,q)


def get_params():
    a = 192948041792305023195893277034532781336
    n = 772559547290160010920412621051392165317498598296084946084386444091060134053985973087541256301003639549317798291916637210182966424107689011211268907278162096553174971554689109947325734336069313105789282878112740205249104820920364881
    y = 754843853942922590978288450377461057162899072980081889481597335367906588582097339709346991452615504422434823707721197330881973700388055679080814559570248350531810374624494389646277873934234170885190847719684200687267925979436889772
    C = (9083709539234699681499154559006541145975405183323215645582033885264296926186620280958201308661746194284022873377667665062501349047202357817146222033735539058147945671541486202387767382626733526030628929826676457655813734637020574, 625771268848498566477216756364333384750869252753726246816617776940622341574266652518894117167008714362418009723919180248010211052475114496172513936468417590330695688907796560242492250071433491517329459840410014214097477377322316145)
    r = 302915847001663746574137782281707162419
    p,q = factorize(n, r)

    return (a, n, y, C, p, q)


def decrypt():
    a, n, y, C, p, q = get_params()
    e = 65537

    # decryption (if factorization succeed)
    c1, c2 = C
    order = (p**2 - 1) * (q**2 - 1)
    _d = inverse(e, order)
    x = pow(_d, e, n)

    dec = (c2 - lag(x, c1, n)) % n
    _m = lag(_d, dec, n)

    print(long_to_bytes(_m))


if __name__ == "__main__":
    decrypt()
  • Flag: ASIS{N0w_LUc4s_vers10n_Of_the_El_Gamal_3nCryp7iOn_5cH3mE_:P}

感想 §

Cryptoを5/6埋める事が出来て良かったです。

目立った感想も無いのでこのコーナーは次からとても楽しかった場合やチームメイトや作問者に感謝の意を伝えたい場合、補足がある場合等を除いて廃止します。