【crypto】 IERAE CTF 2024 公式 Writeup

更新日：2024.10.09

本記事では2024年9月21日～22日に開催された、IERAE CTF 2024のcrypto問題の解法を解説します。

derangement (warmup)
Weak PRNG (easy)
splitting (easy)
enjoyable lattice (medium)
Heady Heights (medium)
cluster (medium)
Free Your Mind (hard)

他のジャンルの解説は以下の記事をご覧ください:

derangement (warmup)

作問者: gyoza_beer
正解チーム数: 106

概要

magic_word というランダムな15文字の文字列が、隠された状態で生成されます。

その次に、同じ位置に同じ文字が一切現れないように magic_word を並べ替えた文字列がヒントとして提供されます。このヒントをもとに、magic_word を特定する問題です。

解法

magic_word の文字の集合を $ A$ として、最初のヒントから取得します。
複数のヒントを集め、それぞれのヒントで 1 文字目に出現する文字を順次 $A$ から除外していきます。
最終的に残った 1 文字が magic_word の 1 文字目となります。この操作を、他の$n$文字目に対しても適用します。

Weak PRNG (easy)

作問者: ayokura
正解チーム数: 54

概要

疑似乱数のある出力をサーバーが隠し持っています。
それ以後の疑似乱数の出力を用いて、疑似乱数生成器の状態を再現し、サーバーが隠し持っている過去の出力を再現してください。

本問題では、Pythonのrandom.Random()をそのまま疑似乱数生成器としています。
random.Random()では、challengeのコメントにあるように、Mersenne Twister (MT19937)がそのまま使われています。

（乱数値が推測できてはいけない場面で、暗号論的疑似乱数生成器（CSPRNG）を使わずに、疑似乱数生成器（PRNG）を使った場合のリスクの一つについて、実体験してみよう、という問題です。）

解法

本問題では以下の二つの操作を実装する必要があります。

サーバーからの出力をもとに、乱数生成器の内部状態(state)を再現する
取得した内部状態をもとに、過去の内部状態を計算し、隠し持つ値を特定する

MT19937についての性質を調べたり、ソースコードを確認したりすると、MT19937は624ワード(以下、1ワード＝32ビットとする)の内部状態（state）をもつことがわかります。
ここでは、MTのソースコードのgenrand_int32を見て考えますが、疑似乱数としての出力は、この内部状態のうちの1ワードに対してTemperingという操作を施したものとなります。
また、624ワード分を出力した後は、この内部状態はすべてが更新され、それ以後の624ワードは新しい内部状態を用いて出力をする仕組みとなっています。

今回のchallangeサーバーでは、16ワード分の出力を1度に出力しますので、39回その操作を繰り返して624ワード分の値を取得し、Tempering操作の逆の操作をすれば、MT19937の内部状態を再現できそうです。
そして、内部状態の更新操作の逆操作もできれば、今回求める秘密の数字についても当てることができそうですね。

ということを踏まえたうえで、実際に実装するか、適切なキーワードで検索をすると過去に同様の実装をしたコードに到達することができます。
なお、日本語で検索した場合で、SolutionをPythonで実装する場合では、Zennに存在するみゃう/HK_ilohasさんの Mersenne Twister (MT19937) で未来と過去の乱数列を予測してみる【Python】という記事が最も近そうに見えます。

これらを踏まえてコードを実装するとフラグを得ることができます。

from pwn import tubes,process,remote,context
import random
import sys

# ---- from https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state#%E9%81%8E%E5%8E%BB%E3%81%AE%E5%86%85%E9%83%A8%E7%8A%B6%E6%85%8B%E3%81%AE%E5%BE%A9%E5%85%83
def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x

def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y

def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y

def get_prev_state(state):
    for i in range(623, -1, -1):
        result = 0
        tmp = state[i]
        tmp ^= state[(i + 397) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
        result = (tmp << 1) & 0x80000000
        tmp = state[(i - 1 + 624) % 624]
        tmp ^= state[(i + 396) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
            result |= 1
        result |= (tmp << 1) & 0x7fffffff
        state[i] = result
    return state

# ----

context.log_level = 'info'

#io = remote('127.0.0.1', 19937)
io = process([sys.executable, './challenge.py'])

io.recvuntil(b'Enter your choice (1-3)\n> ')

outputs = []
required_outputs = 624

while len(outputs) < required_outputs:
    io.sendline(b'1')
    io.recvuntil(b'Here are your random data:\n')
    for _ in range(16):
        line = io.recvline().strip()
        num = int(line)
        outputs.append(num)
    io.recvuntil(b'Enter your choice (1-3)\n> ')

outputs = outputs[:624]
state = [untemper(output) for output in outputs]

state = get_prev_state(state)

mt = random.Random()
state = (3, tuple(state + [623]), None)
mt.setstate(state)

answer = mt.getrandbits(32)

io.sendline(b'2')
io.sendlineafter(b'> ', str(answer).encode())

print(io.recvallS())

splitting (easy)

作問者: mitsu
正解チーム数: 21

概要

netcat でサーバに接続すると，三つのパラメータと大量の座標が与えられます．

# challenge.sage
FLAG = getenv("FLAG", "TEST{TEST_FLAG}").encode()
f = bytes_to_long(FLAG)

p = random_prime(2^128)
Fp = GF(p)
a, b = Fp.random_element(), Fp.random_element()
E = EllipticCurve(Fp, [a, b])

print(a)
print(b)
print(p)

gens = list(E.gens())
if len(gens) < 2:
    gens.append(ZZ(Fp.random_element()) * E.gens()[0])

res = []
while f > 0:
    r = Fp.random_element()
    res.append(ZZ(r) * gens[f & 1])
    f >>= 1

for R in res:
    print(R.xy())

配布された sage のコードを読むと，128 bit 素数 $p$ による有限体上の楕円曲線 $E$ が与えられ，さらにフラグの $i$ 番目のビット $f_i$ について次の点が与えられます．
$$
R_i=\begin{cases}
r_iG_0 & \mathrm{if} \ f_i=0\\
r_iG_1 & \mathrm{if} \ f_i=1
\end{cases}
$$

$G_0,G_1$ は E.gens() から生成された曲線上の点で，与えられた座標がどちらの点の倍数なのかを判定できればフラグが入手できます．

解法

sagemath には一般に巡回群の上で離散対数問題を解く関数 discrete_log があります．
しかし内部実装のデフォルトは BsGs で，離散対数問題を簡単に解いてしまう魔法のような実装ではありません．そのため今回の $\left,\left$ のような大きな群だと，関数が解を出力するまでに非常に時間がかかります．
また discrete_log の動作として，曲線上の点 $P,Q$ について $Q = rP$ となるような整数 $r$ が存在しない場合は ValueError で停止するようになっています．
sagemath の内部実装でこのエラー出力の判定は高速に行われるため，この時間の差を利用して，timeout_decorator なり sagemath の alarm なりで discrete_log(Q, P, operation="+") を一秒程度動かしたときの例外で倍数の判定が可能となります．

注意として，$G_1 = rG_0$ の場合だとこの判定法は使えないため，複数回接続することで E.gens() が二つの点を出力する場合を引く必要があります．

また半分くらいの確率で $R_i$ が $G_0,G_1$ どちらの倍数でもあるような場合がありますが，今回は何度も接続できる問題なので全てのビットが確定できるまで接続しなおすことで問題が解決できます．

以下がソルバです．
inputs に出力から得た座標のタプルを格納してプログラムを回すと，フラグの確定したビットが 01 で，確定しなかった部分は 2 として出力されます．(高速化のため，フラグの IERAE{} の部分は読み飛ばしています)

# -----------------------------------------------------------
# attack part
# -----------------------------------------------------------
inputs = []
a, b, p = a, b, p
for R in res:
    inputs.append((ZZ(R.xy()[0]), ZZ(R.xy()[1])))
Fp = GF(p)
E = EllipticCurve(Fp, [a, b])

gens = E.gens()

assert len(gens) == 2, "not split"

@timeout_decorator.timeout(1)
def test(R, G):
    discrete_log(R, G, operation="+")

res = []
for R in inputs:
    R = E(R)

    try:
        test(R, gens[0])
    except ValueError:
        e0 = 2
    except timeout_decorator.timeout_decorator.TimeoutError:
        e0 = 1

    try:
        test(R, gens[1])
    except ValueError:
        e1 = 2
    except timeout_decorator.timeout_decorator.TimeoutError:
        e1 = 1

    if e0 == 1 and e1 != 1:
        res.append("0")
    elif e0 != 1 and e1 == 1:
        res.append("1")
    else:
        res.append("2")
    print("res:", res, len(res))

res.reverse()
print("?? count:", res[47:-8].count("2"))
print("".join(res)[47:-8])

上のソルバで得た複数個のビット列 (不確定なビット 2 も含まれる) を以下のように統合すればフラグが得られます．

# -----------------------------------------------------------
# search part
# -----------------------------------------------------------
"""
?? count: 184
20110212022222220110012102222222212000100222222200120220002102010022212000220000202102020012001020220112002210212110000100210000021001000022022102220022001102020022000000111002002221010222010202110020202202000211011222212022002120120021202201102011001201200022122020120210001100000222022102112200001101000011001100212000021000122012222200220211011002022220021002222020002210020012210120120000022210020022000202100101001122220012220102100021002120000210012021200010001120002022200202200222021002200021020100110201
?? count: 255
22112211021001222210010120212110212222202022021102122122202201012222222200110000202202202222201220220220221220212212220202220200011222202021211202200212221102220222222002112002221222212021222100110200002201020012212122211001002120220211200201102221002202122222222222110110021200202222010220212102222202202011222220211022221202210212022202110022012022022222022020122000022222010222010102220020021212210022002201120202201121110021022102100222021220200210211221120010021100220221000022120212221020120222012100120221
...
"""

targets = /* REDACTED */

target = ""
for i in range(len(targets[0])):
    res = "2"
    for j in targets:
        if j[i] == "0":
            res = "0"
            break
        elif j[i] == "1":
            res = "1"
            break
    target += res

print("?? count:", target.count("2"))
print(b"IERAE{" + long_to_bytes(int(target, 2)) + b"}")

より高速な解法

上の解法は discrete_log を計算し終了が遅いか否かを判定する方法なので，今回のようにビット数が非常に多い場合は計算が終了するまで5分程度時間がかかります．

easy 問題的にはこれで問題ありませんが，実は discrete_log を使ったものより高速な判定方法があります．

Weil ペアリング $e_n$ は $E(\mathbb{F_p})$ 上で 2x2 の行列式のような動作をし，$e_n(R_i, G_0),e_n(R_i,G_1)$ を計算することで点の独立性を確かめることができます．

以下がソルバです．
出力を上の解法の search part に入力してください．

# -----------------------------------------------------------
# attack part
# -----------------------------------------------------------

inputs = []
a, b, p = a, b, p
for R in res:
    inputs.append((ZZ(R.xy()[0]), ZZ(R.xy()[1])))
Fp = GF(p)
E = EllipticCurve(Fp, [a, b])

gens = E.gens()

assert len(gens) == 2, "not split"

o1 = gens[1].order()
o0 = gens[0].order()
res = []
for R in inputs:
    R = E(R)
    try:
        e0 = gens[0].weil_pairing(R, o0)
    except:
        e0 = gens[0].weil_pairing(R, o1)
    try:
        e1 = gens[1].weil_pairing(R, o1)
    except:
        e1 = gens[1].weil_pairing(R, o0)
    if e0 == 1 and e1 != 1:
        res.append("0")
    elif e0 != 1 and e1 == 1:
        res.append("1")
    else:
        res.append("2")

res.reverse()
print("?? count:", res[47:-8].count("2"))
print("".join(res)[47:-8])

enjoyable lattice (medium)

作問者: gyoza_beer
正解チーム数: 7

概要

MLWEを用いた格子ベースの暗号手法により、AESキーが暗号化されています。
以下をもとに、AESキーを復号する問題です。

$Q, A, t$: 多項式環で表現された公開鍵とパラメータ。
ciphertexts: AESキーの各ビットを、格子ベースの暗号手法により暗号化したもの。

解法

LLLを用いて秘密鍵を求め、暗号文を復号します。

多項式係数としてのベクトル削減:
- 公開鍵として、行列 $A$ とベクトル $t$ が与えられます。これらはSageMathの多項式環 $R$ 上で定義されています。
- $A$ の各要素（$A_1, A_2, A_3, A_4$）を数値行列に変換し、これをブロック行列として composite_A に埋め込みます。このとき、各多項式の係数が格子の基底ベクトルとして扱われます。
- さらに、ベクトル $t$ も同様に多項式の係数を展開して composite_A に組み込み、全体として数値行列 composite_A を構築します。
- この composite_A を含む格子行列 $B$ を構築し、LLLアルゴリズムを適用することで、秘密鍵 $s$ とエラー項 $e$ に対応する短いベクトルを見つけ出します。
秘密鍵 $s$ を用いた暗号文の復号:
- 取得した秘密鍵 $s$ を使って、暗号文 ciphertexts を復号し、元のAESキーのビット列を復元します。
- 復号された多項式の各係数を個別に評価し、それぞれの係数が $(Q + 1) // 2$ に近いか遠いかでビットを判断します。
フラグの取得:
- 復元したAESキーを使って、encrypted_flag を復号し、フラグを取得します。

from sage.all import *
from Crypto.Cipher import AES  
from Crypto.Util.Padding import unpad

def round_custom(val, center, bound):
    dist_center = abs(center - val)
    dist_bound = min(val, bound - val)
    return 1 if dist_center < dist_bound else 0

def compress(decry_v, Q):
    dm = [int(i) for i in decry_v.list()]
    center = (Q + 1) // 2
    return [round_custom(coef, center, Q) for coef in dm]

def decrypt(sk, c, Q):
    u, v = c
    decrypted_value = v - sk * u
    return compress(decrypted_value, Q)

def aes_decrypt(aes_key, encrypted_flag):
    iv = encrypted_flag[:16]  
    ciphertext = encrypted_flag[16:]  
    cipher = AES.new(aes_key, AES.MODE_CBC, iv)
    decrypted_flag_padded = cipher.decrypt(ciphertext)
    decrypted_flag = unpad(decrypted_flag_padded, AES.block_size)
    return decrypted_flag

def main():
    Q = 4183169813 
    N, k = 32, 2

    PR.<x> = PolynomialRing(GF(Q))
    R.<z> = PR.quotient_ring(x^N + 1)

    A = /* REDACTED */
    t = /* REDACTED */
    ciphertexts = /* REDACTED */
    encrypted_flag = b"!\xed\xdc|\xd9^\xcf\xa8.Jg;)\x9bO\xa4\xdd\xca\xfa\x8f\x86nD\xf5WkK\x83\xd6\x07u\x92\xdf\xd7t\xef\x82\x92\xdd[%B\xeb\x91\xdb\xe9\x97h\xedQw\xba\xe4\xab\xf1\xc7*\x18\x99\xa5\xea\xc9\xb8V\xf2\x07\xe5\xe9\x10'\xf9\xb9\xde]q\x88\xbew\xc5T"

    A = matrix(R, A)
    composite_A = matrix(QQ, k * N + 1, k * N)

    A1, A2 = A[0, 0], A[0, 1]
    A3, A4 = A[1, 0], A[1, 1]

    composite_A = matrix(QQ, k * N + 1, k * N)
    composite_A[:N, :N] = A1.matrix()
    composite_A[N:k * N, :N] = A2.matrix()
    composite_A[:N, N:] = A3.matrix()
    composite_A[N:k * N , N:] = A4.matrix()
    composite_A[k * N] = vector(QQ, list(t[0].list()) + list(t[1].list()))

    B = matrix(QQ, 2 * k * N + 1, 2 * k * N + 1)
    B[:k * N, :k * N] = Q * identity_matrix(QQ, k * N, k * N)
    B[k * N:2 * k * N + 1, :k * N] = composite_A
    B[k * N:2 * k * N + 1, k * N:] = identity_matrix(QQ, k * N + 1, k * N + 1)

    reduced = B.LLL()
    shortest_vector = reduced[0]
    e = list(shortest_vector[:k * N])
    s = list(-shortest_vector[k * N:2 * k * N])

    e = vector([R(e[:N]), R(e[N:])])
    s = vector([R(s[:N]), R(s[N:])])
    t = vector(R, t)
    assert -e == A * s - t

    sage_ciphertexts = []
    for (u, v) in ciphertexts:
        u_sage = vector(R, u)
        v_sage = R(v)
        sage_ciphertexts.append((u_sage, v_sage))

    decrypted_texts = []
    for (u, v) in sage_ciphertexts:
        m = decrypt(s, (u, v), Q)

        decrypted_msg = []
        for i in range(0, len(m), 8):
            byte_str = ''.join(map(str, m[i:i+8]))
            decrypted_msg.append(chr(int(byte_str, 2)))  
        decrypted_msg_str = ''.join(decrypted_msg) 
        decrypted_texts.append(decrypted_msg_str)

    decrypted_aes_key = ''.join(decrypted_texts)
    aes_key_bytes = decrypted_aes_key.encode('latin-1')  
    decrypted_flag = aes_decrypt(aes_key_bytes, encrypted_flag)
    print(f"Decrypted flag: {decrypted_flag.decode('utf-8')}")

if __name__ == "__main__":
    main()

Heady Heights (medium)

作問者: elliptic_shiho
正解チーム数: 5

概要

$p$を素数とします. $\mathbb{Z}/p^8\mathbb{Z}$上の楕円曲線の点$P, Q, R$が与えられます. フラグ$f$と乱数$r$について, 以下の条件が成立しています.

$Q = rP$
$R$のx座標を$x(R)$と書くとき, $x(R) = rf\bmod{p^8}$.

$f$を求めてください.

解法

$P, Q, R$の乗っている楕円曲線は, 標数が2, 3と異なることから $y^2 = x^3 + ax + b$ の形で表せます. 以降$a, b$は楕円曲線のパラメータとします.

まず所与の点はそれぞれ$P = (x_1, y_1)$, $Q = (x_2, y_2)$, $R = (x_3, y_3)$と表せるものとします. 楕円曲線の関係式から, すべての$i\in\lbrace\,1, 2, 3\,\rbrace$について, ある$k_i\in\mathbb{Z}$が存在し, $y_i^2 = x_i^3 + ax + b + k_ip^8$をみたします. この関係式をもとに式変形すると

$$
\begin{aligned}
&((y_1^2 - x_1^3) - (y_2^2 - x_2^3))(x_1 - x_3) - ((y_1^2 - x_1^3) - (y_3^2 - x_3^3))(x_1 - x_2)\cr
&= (a(x_1 - x_2) + (k_1 - k_2)p^8)(x_1 - x_3) - (a(x_1 - x_3) + (k_1 - k_3)p^8)(x_1 - x_2)\cr
&= a(x_1 - x_2)(x_1 - x_3) + (k_1 - k_2)(x_1 - x_3)p^8 - a(x_1 - x_2)(x_1 - x_3) - (k_1 - k_3)(x_1 - x_2)p^8\cr
&= ((k_1 - k_2)(x_1 - x_3) - (k_1 - k_3)(x_1 - x_2))p^8\cr
\end{aligned}
$$

という形で$p$を素因数に含む形に変形できます. したがって, この数値を素因数分解できれば$p$を求められます.

問題ファイルより$p$は88ビットです. 小さい素因数を含む場合にはECMを用いた素因数分解が有効です. 実際, 88ビット程度であれば長くても30分程度あれば素因数を吐き出します. ただし, 完全な素因数分解には時間がかかりすぎますから, たとえばPari/GPのfactor関数やSageMathの同名関数を使う方法だと素因数分解しきれず終了しない可能性があります. yafuやprimefac等途中経過を出力するタイプの素因数分解ソルバを用い, 途中で計算を打ち切るのが良いかと思われますが, primefacはそのままではECMの初期パラメータを設定できませんので, primefacの場合は運が良くないと分解できないでしょう. 作問者はGMP-ECMを用い, B1として$10^5$程度を指定することで, 現実的な時間内に$p$を計算できることを確認しています.

さて$p$が求まりました. すると$((y_1^2 - y_2^2) - (x_1^3 + x_2^3)) / (x_1 - x_2) \equiv a\pmod{p^8}$より$a$が, $y_1^2 - x_1^3 - ax_1 \equiv b\pmod {p^8}$より$b$が求まります. これによりパラメータを復元できました.

あとは$R$のx座標をECDLPの解で割ればよいです. これにはいくつかの方法がありますが, $p$べきでmodを取っていることからp進数体に持ち上げる攻撃が最も高速です. すなわち, $N$を mod p上での 楕円曲線$y^2 = x^3 + ax + b$の位数とするとき, $N$倍写像の像はその楕円曲線の形式群に含まれますから, 形式対数を取って割ればECDLPは解けます. この方法はいわゆるSSSA Attackと呼ばれている方法と同じものであり, またp進数体上の楕円曲線に持ち上げる攻撃例として基本的なものです. たとえば J. H. Silverman. 2009. Lifting and Elliptic Curve Discrete Logarithms. が参考になります.

from sage.all import *

BITS = 88
K = 8

def random(lower_bound=0, upper_bound=2 ^ BITS, bits=None):
    return ZZ.random_element(lower_bound, upper_bound)

def random_bits(bits):
    return random(2 ^ (bits - 1), 2 ^ bits)

(x1, x2, x3) = (
    1337,
    108758038897050520831860923441402897201224898270547825657705075428051130846061735614252293345445641285591980004736447964462956581141116321772403519125859758137648644808920743070411296325521866392898376475395494,
    5438451076181919949694350690364579526012926958491719881284366792649670689294870931317007945903275017524668258922051576064401873439529896167369498669912618211164397682696947429627504905294350782410183543966679528,
)
(y1, y2, y3) = (
    2356240417146305163212384832005924367753484871437731042165238964932920608988096746757585282365391701455222258919772283748442969489163122612874542328479985011793178437324509351503404273134948028573603448460822465,
    5224211491008373131406603536527981755345757742567201307027247664784412223361972085071271594280642689356776497337283996518196426296230388008390390705691353643411319840725993589925599219787596133403802269715179842,
    1255469150673352477643406441586559401886808227235272570913194477760462899397412967437903450228715079681927518702031385236882455686813595191144244687009073603134094899106009798791920033413388436982273752206346286,
)

A1 = (y1 ^ 2 - x1 ^ 3) - (y2 ^ 2 - x2 ^ 3)
A2 = (y1 ^ 2 - x1 ^ 3) - (y3 ^ 2 - x3 ^ 3)

# Factoring it
# print(A2 * (x1 - x2) - A1 * (x1 - x3))

# You can factor that by GMP-ECM with B1=1e5 and ~10000 iterations
# echo [COMPOSITE HERE] | ./ecm -c 10000 1e5
p = 223490196137382483691737269

assert (A1 * (x1 - x3) - A2 * (x1 - x2)) % p ^ K == 0
a = Mod(A1 / (x1 - x2), p ^ K).lift()
b = Mod(y1 ^ 2 - x1 ^ 3 - a * x1, p ^ K).lift()

E = EllipticCurve(Qp(p, prec=K), [a, b])
P = E(x1, y1)
Q = E(x2, y2)
R = E(x3, y3)

E0 = EllipticCurve(GF(p), [a, b])
N = E0.order()
ell = E.formal_group().log().polynomial()

def formal_log(P):
    return ell.subs(t=P[0] / P[1])

secret_key = ZZ(formal_log(N * Q) / formal_log(N * P))
print(bytes.fromhex(hex(Mod(x3 / secret_key, p ^ K).lift())[2:]))

cluster (medium)

作問者: ta1yak1
正解チーム数: 9

概要

from secret import p, q, r, flag
from Crypto.Util.number import isPrime, bytes_to_long

N = p * q * r

assert isPrime(p) and p.bit_length() < 1024
assert isPrime(q) and q.bit_length() < 1024
assert isPrime(r) and r.bit_length() < 1024
assert p ** 2 + q ** 2 + r ** 2 + (p * q + q * r + r * p) == 6 * N

m = bytes_to_long(flag)
e = 65537
c = pow(m, e, N)

print(f'{c = }')

上記の短いコードおよび暗号文$c$が与えられます. やることは文字通り

$$
p^2 + q^2 + r^2 + (pq + qr + rp) = 6pqr
$$

を満たす1024ビットの素数$p, q, r$を見つけ, RSA復号する問題です.

解法

解法とは関係ないですが, 下記をもとにソルバを回した結果CTF{***}というflagが出てきます. 本CTFでのflagフォーマットであるIERAE{***}と齟齬が生じており, flag提出時に非本質的な推測をさせてしまうこととなりました. 改めてお詫び申し上げます.

想定解は https://arxiv.org/abs/2109.09639 あるいはその一般化である https://arxiv.org/abs/2201.10919 を実装するものです.
"diophantine equation cluster"などでGoogle検索かけるとヒットします.

(追記)
一旦素数という条件を外し, 条件を満たす自然数解を総当たりで列挙していき, 6673や16693辺りをGoogle検索かければ https://oeis.org/A357749 に行き着きます.
(上記OEISでも上記の論文は引用されています)

Free Your Mind (hard)

作問者: elliptic_shiho
正解チーム数: 7

概要

1の11乗根$\zeta$について, $\omega := \zeta^2 + \zeta^{-2}$とおき, $K := \mathbb{Q}$, $L := K(\omega)$とします. あなたは$L$の元$\alpha$を指定できます. 指定すると, $e := N_{L/K}(\alpha)$を計算し($N_{L/K}$はノルム写像), 素数$p$, $q$を生成した後に$N := pq$, $e$によるRSA暗号化処理をフラグに適用します. あなたは$\alpha$と暗号化されたフラグ, そして$N$を知っていますが, それ以外はわかりません.

なお, $\alpha$の各パラメータに現れる数は$2^{16}$より大きくないといけません. たとえば, 既約分数表示$a/b$について$a$, $b$はともに$2^{16}$より大きくある必要があります.

解法

この問題は当初もう少し遠回りな道筋を考えており, レビュー段階でHard想定としたのもその道筋に対する横槍をその時間内に考慮しきれなかったためでした. しかしながら, たとえば以下の方法であれば, 最小限の前提知識で済みます(数式アレルギーさえなければ). なのでここではそれを紹介します. 想定解法は次回の宿題です 🙂

ノルムとは, 複素数でいうところの$\lvert z\rvert^2 = a^2 + b^2$です. $L$上の元$\alpha$について$K$の元を割り当てます. ノルムが1, すなわち$N_{L/K}(\alpha) = 1$であるように$\alpha$を選ぶことができたら, 我々は$e = 1$のRSA暗号としてフラグを暗号化することになります. $e$を小さくするのは(適当にやるとわかりますが)難しいので, $e = 1$が一番シンプルに解きやすい方法でしょう.

$N_{L/K}(1) = 1$のような単純な例であればすぐ見つかりますが, これらは各数値が小さすぎるのでうまくいきません.

ところで, ノルムは掛け算をそのまま保存します. 具体的には$\alpha, \beta\in L$ならば$N_{L/K}(\alpha\beta) = N_{L/K}(\alpha)N_{L/K}(\beta)$です. このことから, $N_{L/K}(\alpha) = 1$なら任意の$k\in\mathbb{N}$について$N_{L/K}(\alpha^k) = N_{L/K}(\alpha)^k = 1^k = 1$です. 我々はノルムが1, かつ非自明な元を適当に探せば良いことになりました.

そのような元はすぐに見つかります. $N_{L/K}(\omega) = -1$より$N_{L/K}(\omega^2) = 1$です. 後はこれを適当に何乗かして, 制約に合うようにすればよいです. たとえば $\omega^{50}$ は
14453780545834*omega^4 - 13243217176106*omega^3 - 32295336107042*omega^2 + 18633285182577*omega + 7519722443381 かつノルム1です.