Ricerca CTF 2023 writeup - チョコラスクのブログ

Ricerca CTF 2023にチームDCDCで参加して、9位でした。

cryptoのボス問を単独正解することができてとても嬉しいです！

Revolving Letters (crypto)
Rotated Secret Analysis (crypto)
RSALCG (crypto)
dice-vs-kymn (crypto)

Revolving Letters (crypto)

11時半ごろに起きたら、すでに他のメンバーが解いてくれていました。

Rotated Secret Analysis (crypto)

次のソースコードとその実行結果が与えられます。

import os
from Crypto.Util.number import bytes_to_long, getPrime, isPrime

flag = os.environ.get("FLAG", "fakeflag").encode()

while True:
  p = getPrime(1024)
  q = (p << 512 | p >> 512) & (2**1024 - 1) # bitwise rotation (cf. https://en.wikipedia.org/wiki/Bitwise_operation#Rotate)
  if isPrime(q): break

n = p * q
e = 0x10001
m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'{n=}')
print(f'{e=}')
print(f'{c=}')

2048bitのRSA暗号ですが、 $p$ の上512bitと下512bitを入れ替えたものが $q$ になっています。

$p=2^{512}x+y$ , $q=2^{512}y+x$ ( $0\leq x, y\lt 2^{512}$ ) と表せます。このとき、

$\displaystyle{ n=(2^{1024}+1)xy+2^{512}(x^{2}+y^{2}) }$

です。 $0\leq xy\lt 2^{1024}$ , $0\leq x^{2}+y^{2}\lt 2^{1025}$ なので、 $n$ の下512bit が $xy$ の下512bitで、 $n$ の上512bitがほぼ $xy$ の上512bit となります。ただし、1536bit目における繰り上がりおよび、 $x^{2}+y^{2}$ が1024bitを1bitだけ超えた分が、 $n$ の1537bit目に足される可能性があるので、その分を引くパターンも試す必要があります。

$xy$ がわかれば、 $xy=m$ とすると、

$\displaystyle{ n=(2^{1024}+1)m+2^{512}(x^{2}+m^{2}/x^{2}) }$

です。これは $x^{2}$ の2次方程式なので解けます。

from Crypto.Util.number import *
from output import *
from gmpy2 import isqrt

xy = (n&(2**512-1)) | ((n>>1536)<<512)
xy -= 2**512 # 繰り上がりの分を引く
v = (n-xy*(2**1024+1))>>512
w = v*v-4*xy*xy
ws = isqrt(w)
x2 = (v-ws)//2
x = isqrt(x2)
y = xy//x
p = (x<<512)|y
q = (y<<512)|x
print(long_to_bytes(pow(c, inverse(e, (p-1)*(q-1)), n)))
# b'RicSec{d0nt_kn0w_th3_5ecr3t_w1th0ut_r0t4t1n9!}'

RSALCG (crypto)

次のソースコードとその実行結果が与えられます。

from Crypto.Util.number import getPrime, getRandomNBitInteger
import os

FLAG = os.getenv("FLAG", "RicSec{*** REDACTED ***}").encode()

def RSALCG(a, b, n):
    e = 65537
    s = getRandomNBitInteger(1024) % n
    while True:
        s = (a * s + b) % n
        yield pow(s, e, n)

def encrypt(rand, msg):
    assert len(msg) < 128
    m = int.from_bytes(msg, 'big')
    return int.to_bytes(m ^ next(rand), 128, 'big')

if __name__ == '__main__':
    n = getPrime(512) * getPrime(512)
    a = getRandomNBitInteger(1024)
    b = getRandomNBitInteger(1024)
    rand = RSALCG(a, b, n)
    print(f"{a = }")
    print(f"{b = }")
    print(f"{n = }")
    print(encrypt(rand, b"The quick brown fox jumps over the lazy dog").hex())
    print(encrypt(rand, FLAG).hex())
    print(encrypt(rand, b"https://translate.google.com/?sl=it&tl=en&text=ricerca").hex())

1つ目の暗号化時のsの値を $s$ とします。 $a_{2}=a^{2}$ , $b_{2}=ab+b$ とすると、2つ目, 3つ目の暗号化時のsはそれぞれ $as+b\bmod{n}$ , $a_{2}s+b_{2}\bmod{n}$ です。1つ目と3つ目の暗号文から、 $c_{1}=s^{e}\bmod{n}$ および $c_{3}=(a_{2}s+b_{2})^{e}\bmod{n}$ の値がわかります。 $(as+b)^{e}\bmod{n}$ を求められれば2つ目の暗号文からフラグを復元できます。

ふるつきさんのCTF crypto 逆引きにもある通り、 $c_{1}$ と $c_{3}$ の条件から $s$ を求めることができます。 $\mathbb{Z}/n\mathbb{Z}$ 上の多項式 $f_{1}(x), f_{3}(x)$ を、

$\displaystyle{ \begin{align} f_{1}(x)&=x^{e}-c_{1} \\ f_{3}(x)&=(a_{2}x+b_{2})^{e}-c_{3} \end{align} }$

と定めると、これらはともに $x=s$ を根にもつので、 $x-s$ で割り切れます。よって、

$\displaystyle{ \mathrm{gcd}(f_{1}(x), f_{3}(x))=x-s }$

となるので、gcdを計算できれば $s$ が求まります。

gcdの計算は、整数の場合と同じユークリッドの互除法でできます。

def gcd(a, b):
    while b:
        a %= b
        a, b = b, a
    return a

計算量は、1回のループで小さい方の次数が1以上下がり、1回の除算に $O(\text{次数})$ かかるので、全体で $O(e^{2})$ です (整数の四則演算を $O(1)$ と仮定した場合)。

今回 $e=65537$ でかなり時間がかかりそうに見えたので*1、half-gcdという高速なアルゴリズムを使いました。half-gcdの計算量は $O(e\log^{2}e)$ です。half-gcdはkurenaifさんの動画で解説されていて、動画で紹介されているdiceCTFの問題のwriteupを検索すると、ソースコードも見つかります。

from Crypto.Util.number import *

# https://scrapbox.io/crypto-writeup-public/diceCTF_2021_%7C_plagiarism
def pdivmod(u, v):
    """
    polynomial version of divmod
    """
    q = u // v
    r = u - q*v
    return (q, r)

def hgcd(u, v, min_degree=10):
    """
    Calculate Half-GCD of (u, v)
    f and g are univariate polynomial
    http://web.cs.iastate.edu/~cs577/handouts/polydivide.pdf
    """
    x = u.parent().gen()

    if u.degree() < v.degree():
        u, v = v, u

    if 2*v.degree() < u.degree() or u.degree() < min_degree:
        q = u // v
        return matrix([[1, -q], [0, 1]])

    m = u.degree() // 2
    b0, c0 = pdivmod(u, x^m)
    b1, c1 = pdivmod(v, x^m)

    R = hgcd(b0, b1)
    DE = R * matrix([[u], [v]])
    d, e = DE[0,0], DE[1,0]
    q, f = pdivmod(d, e)

    g0 = e // x^(m//2)
    g1 = f // x^(m//2)

    S = hgcd(g0, g1)
    return S * matrix([[0, 1], [1, -q]]) * R

def pgcd(u, v):
    """
    fast implementation of polynomial GCD
    using hgcd
    """
    if u.degree() < v.degree():
        u, v = v, u

    if v == 0:
        return u

    if u % v == 0:
        return v

    if u.degree() < 10:
        while v != 0:
            u, v = v, u % v
        return u

    R = hgcd(u, v)
    B = R * matrix([[u], [v]])
    b0, b1 = B[0,0], B[1,0]
    r = b0 % b1
    if r == 0:
        return b1

    return pgcd(b1, r)

a = 104932596701...
b = 146908709759...
n = 689154384544...
c1 = 0x05d7913ff5...
c2 = 0x1913ba387e...
c3 = 0x45054a08d5...
e = 65537
msg1 = b"The quick brown fox jumps over the lazy dog"
msg3 = b"https://translate.google.com/?sl=it&tl=en&text=ricerca"

c1 = c1^^int.from_bytes(msg1, 'big')
c3 = c3^^int.from_bytes(msg3, 'big')

R = Zmod(n)
PR.<x> = PolynomialRing(R)
a2 = a*a%n
b2 = (a*b+b)%n
f1 = x^e-c1
f3 = (a2*x+b2)^e-c3
f = pgcd(f1, f3).monic()
s = int(-f[0])
print(long_to_bytes(int(pow((a*s+b)%n, e, n))^^int(c2)))
# b"RicSec{1_7h1nk_y0u_uNd3r5t4nd_ev3ry7h1ng_4b0ut_Franklin-Reiter's_a7t4ck}"

dice-vs-kymn (crypto)

次のソースコードが与えられます。

import os
import signal

signal.alarm(1000)

for _ in range(77):
    x = randrange(1, 1 << 64)
    print("x:", x)
    a, b = int(input('a: ')), int(input('b: '))
    assert a != 0 and b != 0, "[kymn] Sorry for you!"

    for _ in range(10):
        p = random_prime(1 << 256)
        if legendre_symbol(x^3 + a*x + b, p) == 1:
            break
    else:
        print("[kymn] (^o^)m9 Bad luck!")
        exit()

    F = GF(p)
    E = EllipticCurve(F, [F(a), F(b)])
    G = E.lift_x(F(x))

    k = randrange(1, p)
    Q = k * G
    kymn_dice = (k % 6) + 1
    print("commitment:", (G[1], Q[1]))

    player_dice = int(input("Your dice: "))
    assert 1 <= player_dice <= 6, "Wrong input"

    if kymn_dice + player_dice == 7:
        print("[kymn] o(.o.)o You lucky bastard!")

    else:
        print("[kymn] (^o^)m9 Bad luck!")
        print("proof:", (p, k))
        exit()

else: # 77 wins!
    print("[kymn] I got totally destroyed! Hats off to you...")
    print("FLAG:", os.getenv("FLAG", "RicSec{*** REDACTED ***}"))

楕円曲線上の離散対数問題の答えを $\bmod{6}$ で求める問題に77回正解できればフラグが得られます。ただし、ランダムに決まる $G$ の $x$ 座標 $g_{x}$ が与えられた後に、楕円曲線の式の係数 $a, b$ を自由に決めることができますが、 $p$ は $a, b$ の入力後にランダムで決まるようになっています。

( $p$ がわかっているとして) $G$ の位数が6の倍数であれば、Pohlig-Hellmanアルゴリズムの要領で $k\bmod{6}$ を求めることができます。そこでまず、 $p$ によらず楕円曲線の位数が6の倍数となるような $a, b$ を探索してみました。すると、例えば $y^{2}=x^{3}-12x-11$ などいくつかの候補が見つかります。しかし、楕円曲線の位数が6の倍数でも $G$ の位数が6の倍数となるとは限らず、困りました。位数が $6^{n}$ の倍数の楕円曲線を探す方針でしばらく考えていましたが、全然見つからず時間を溶かしました。

何となく "y²=x³-12x-11 elliptic curve order" でググってみたところ、論文がヒットしました。 $y^{2}=x^{3}-12x-11$ は、torsion groupが $\mathbb{Z}/6\mathbb{Z}$ であるような楕円曲線 $y^{2}=x^{3}-372x+2761$ と $\mathbb{Q}$ 上でisogeniousなので、どんな $p$ でreductionをとっても位数は6の倍数だ、といったことが書かれています。これにより、 $\mathbb{Q}$ 上で考えて6-torsion pointをもつ楕円曲線を探せばよい、という正しい方針に進むことができました。

次に、"elliptic curve torsion group Z/6Z" でググると、6-torsion pointをもつ楕円曲線の例が色々書かれた論文がヒットしました。section2の例をWeierstrass標準形に直すと、

$\displaystyle{ \begin{align} a(c)&=-16c^{3}-(1+6c-3c^{2})^{2}/3 \\ b(c)&=2(1+6c-3c^{2})^{3}/27+16c^{3}(1+6c-3c^{2})/3 \\ x_{0}(c)&=-4c+(1+6c-3c^{2})/3 \end{align} }$

のとき、 $y^{2}=x^{3}+a(c)x+b(c)$ が $(x_{0}(c), \ast )$ を6-torsion pointにもつことがわかります。6-torsion point自体の具体的な式もあるので、 $G$ が6-torsion pointになるように $a, b$ を選ぶ方針でいきます。しかし、単純に $x_{0}(c)=g_{x}$ となる $c$ を考えると、 $a, b$ が整数になりません。そこで、 $x'=tx$ , $y'=t^{3/2}y$ という変換を考えると、

$\displaystyle{ \begin{align} a(c,t)&=(-16c^{3}-(1+6c-3c^{2})^{2}/3)t^{2} \\ b(c,t)&=(2(1+6c-3c^{2})^{3}/27+16c^{3}(1+6c-3c^{2})/3)t^{3} \\ x_{0}(c,t)&=(-4c+(1+6c-3c^{2})/3)t \end{align} }$

のとき、 $y'^{2}=x'^{3}+a(c,t)x'+b(c,t)$ が $(x_{0}(c,t), \ast )$ を6-torsion pointにもつ、といえます。これでパラメータが増えて調節しやすくなりました。 $x_{0}(c,t)$ が $t$ の1次式なので、 $c$ は定数を試してみることにします。

まず $c=1$ にしてみると、 $x_{0}(c,t)=g_{x}$ となる $t$ は $-3g_{x}/8$ で、このとき $a=-3g_{x}^{2}$ , $b=-11g_{x}^{3}/8$ となります。 $a, b$ は整数しか入力できないですが、 $g_{x}$ が奇数のとき $b$ が整数にならずダメです。 $a, b$ 整数の条件が意外と厳しく、 $c=2, -1, 1/2$ を試して同様にダメでしたが、 $c=1/3$ にしてみると、 $a=-15g_{x}^{2}$ , $b=-22g_{x}^{3}$ となり上手くいきます！

あとは、 $G, Q=kG$ の $y$ 座標 $g_{y}, q_{y}$ が与えられたときに、 $Q$ が $kG$ $(k=0, 1, \ldots, 5)$ のどれに一致するのかを判定できる必要があります。試してみると、 $G$ の $y$ 座標を $t$ としたとき、 $2G$ , $3G$ , $4G$ , $5G$ の $y$ 座標は $-t/3$ , $0$ , $t/3$ , $-t$ となっていることがわかります。

sage: gx = randrange(1, 1<<64)                                                                                                                            
sage: a = -15*gx**2                                                                                                                                       
sage: b = -22*gx**3                                                                                                                                       
sage: K.<t> = NumberField(x^2-(gx^3+a*gx+b))                                                                                                                                                                                                                                                        
sage: EQ = EllipticCurve([a, b], K)                                                                                                                       
sage: GQ = EQ.lift_x(K(gx))                                                                                                                               
sage: for k in range(7): 
....:     print(k*GQ) 
....:                                                                                                                                                     
(0 : 1 : 0)
(15333364164610908544 : t : 1)
(-46000092493832725632 : -1/3*t : 1)
(-30666728329221817088 : 0 : 1)
(-46000092493832725632 : 1/3*t : 1)
(15333364164610908544 : -t : 1)
(0 : 1 : 0)

今回 $p$ は与えられませんが、 $p$ は $g_{y}^{2}-(g_{x}^{3}+ag_{x}+b)$ を割り切ることに着目すると、例えば $Q=2G$ なら、 $\mathrm{gcd}(g_{y}^{2}-(g_{x}^{3}+ag_{x}+b), g_{y}+3q_{y})$ が $p$ の倍数で大きい値になるので、 $Q=2G$ かどうか判定できます。

import socket
from Crypto.Util.number import *

def recvuntil(client, delim=b'\n'):
    buf = b''
    while delim not in buf:
        buf += client.recv(1)
    return buf

host = 'dice-vs-kymn.2023.ricercactf.com'
port = 5963
client = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
client.connect((host, port))

for _ in range(77):
    recvuntil(client, b'x: ')
    gx = int(recvuntil(client).strip())
    a = -15*(gx**2)
    b = -22*(gx**3)
    recvuntil(client, b'a: ')
    client.send(str(a).encode()+b'\n')
    recvuntil(client, b'b: ')
    client.send(str(b).encode()+b'\n')
    recvuntil(client, b'commitment: ')
    gy, qy = eval(recvuntil(client).strip())

    kymn_dice = 0
    if qy == 1:
        kymn_dice = 0+1
    elif qy == 0:
        kymn_dice = 3+1
    elif qy == gy:
        kymn_dice = 1+1
    elif GCD(gy+qy, gy^2-gx^3-a*gx-b) > 2**64:
        kymn_dice = 5+1
    elif GCD(gy+3*qy, gy^2-gx^3-a*gx-b) > 2**64:
        kymn_dice = 2+1
    else:
        assert GCD(gy-3*qy, gy^2-gx^3-a*gx-b) > 2**64
        kymn_dice = 4+1
    player_dice = 7-kymn_dice
    recvuntil(client, b'Your dice: ')
    client.send(str(player_dice).encode()+b'\n')

recvuntil(client)
print(recvuntil(client))
# b'RicSec{t0rs10n_p01nt_1s_1nt3r3st1ng}'

$\mathbb{F}_{p}$ ではなく $\mathbb{Q}$ 上での考察が必要なCTFの楕円曲線問は初めて見たので、とても面白かったです。6-torsion pointをもつ楕円曲線は気合いで探索するのが想定解らしい(？)ので、ググって出てきたもので上手くいったのは運が良かったです。

*1:実際は数十分程度で解けるようです。