はじめに

お久しぶりです。管理人です。ほぼ1年ぶりのブログ更新です。次はC言語の2回目やるとかほざいてましたけど忘れてました。
今回は、06/15~16に開催されたSECCON for Beginners 2024に参加したので解いた問題(1問)の解法を説明しようと思います。
チーム名は”THE Students”で、69/962位でした。チームメイトは9人で、そのうち4人はLiberlunaのメンバーです。

Writeup

今回僕が解いた問題はCrypto問題のSafe Primeです。名前からある程度想像が付くと思いますが、RSAの問題です。
結構早い段階(開始6~7分程)にsubmitしたんですが8番目でした。悲しい。

他にも何問か解こうと思ったんですが、できませんでした。唯一、競技時間内に解けたCrypto問題です。

Safe Prime

一応、解説はしますが数学めちゃくちゃ苦手なので当てにしないでください。

追記

一応他の問題のWriteupも載せます。

Safe Prime

About	----
author	ptr-yudai
Tag	Beginner
Desc	Using a safe prime makes RSA secure, doesn’t it?
配布ファイル	Safe_Prime.tar.gz 774280c0d7d278ed01f537b13014fa15b4dc1d3a

ソースコード

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

FLAG = os.getenv("FLAG", "ctf4b{*** REDACTED ***}").encode()
m = int.from_bytes(FLAG, 'big')

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q
e = 65537
c = pow(m, e, n)

print(f"{n = }")
print(f"{c = }")

$n = p \cdot (2 p + 1)$ で表されます。
$p$ を利用して $q$ を生成しているので $n$ を $p$ の1変数を使用する2次方程式で表せれます。
solver ※PyCryptoDomeを使っても解けます。

from sympy import nextprime, isprime
from math import isqrt

n = 292927367433510948901751902057717800692038691293351366163009654796102787183601223853665784238601655926920628800436003079044921928983307813012149143680956641439800408783429996002829316421340550469318295239640149707659994033143360850517185860496309968947622345912323183329662031340775767654881876683235701491291
c = 40791470236110804733312817275921324892019927976655404478966109115157033048751614414177683787333122984170869148886461684367352872341935843163852393126653174874958667177632653833127408726094823976937236033974500273341920433616691535827765625224845089258529412235827313525710616060854484132337663369013424587861

p = isqrt(n // 2)
while True:
    q = 2 * p + 1
    if n % p == 0 and n % q == 0 and n == p * q:
        break
    p = nextprime(p)

q = 2 * p + 1
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi)

m = pow(c, d, n)
flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()

print("FLAG:", flag)

実行するとflagが出ます。

ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}

二分探索(?)をするのがいいみたいです。

math

時間中に解けませんでした。理由はどこかの過程で計算ミスをしていてバイナリからテキストに変換できませんでした。
ですが、競技が終了して一度睡眠し、頭をスッキリさせたら解けました。

math

About	----
author	task4223
Tag	easy
Desc	RSA暗号に用いられる変数に特徴的な条件があるようですね…?
配布ファイル	math.tar.gz 2740fceb50df89f4638a1e3b6ded3487a55461fc

ソースコード

from Crypto.Util.number import bytes_to_long, isPrime
from secret import (
    x,
    p,
    q,
)  # x, p, q are secret values, please derive them from the provided other values.
import gmpy2


def is_square(n: int):
    return gmpy2.isqrt(n) ** 2 == n


assert isPrime(p)
assert isPrime(q)
assert p != q

a = p - x
b = q - x
assert is_square(x) and is_square(a) and is_square(b)

n = p * q
e = 65537
flag = b"ctf4b{dummy_f14g}"
mes = bytes_to_long(flag)
c = pow(mes, e, n)

print(f"n = {n}")
print(f"e = {e}")
print(f"cipher = {c}")
print(f"ab = {a * b}")

assert gmpy2.mpz(a) % 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169 == 0
assert gmpy2.mpz(b) % 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661 == 0

このコードを見ると、 $a$ , $b$ , $x$ はいずれも完全平方数で、 $a$ と $b$ はそれぞれ $p$ , $q$ から $x$ を引いた数であり、どちらも巨大数との $mod$ が $0$ になると推測されます。たぶん。
$ab$ は $a$ , $b$ の積なので、素因数分解を行うことで $a$ と $b$ をある程度絞り込めます。たぶん。
また、 $p$ , $q$ はそれぞれ $(a+x)$ と $(b+x)$ であり、 $p*q = n$ なので、 $x**2 + (a+b)*x + (ab-n) = 0$ の方程式が成り立つことがわかります。たぶん。
少し割愛して、特定した $a$ , $b$ , $x$ を使用すると $p$ , $q$ を求めれるので、solverを書きます。
solver

n = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649220231238608229533197681923695173787489927382994313313565230817693272800660584773413406312986658691062632592736135258179504656996785441096071602835406657489695156275069039550045300776031824520896862891410670249574658456594639092160270819842847709283108226626919671994630347532281842429619719214221191667701686004691774960081264751565207351509289
e = 65537
cipher = 21584943816198288600051522080026276522658576898162227146324366648480650054041094737059759505699399312596248050257694188819508698950101296033374314254837707681285359377639170449710749598138354002003296314889386075711196348215256173220002884223313832546315965310125945267664975574085558002704240448393617169465888856233502113237568170540619213181484011426535164453940899739376027204216298647125039764002258210835149662395757711004452903994153109016244375350290504216315365411682738445256671430020266141583924947184460559644863217919985928540548260221668729091080101310934989718796879197546243280468226856729271148474
ab = 28347962831882769454618553954958819851319579984482333000162492691021802519375697262553440778001667619674723497501026613797636156704754646434775647096967729992306225998283999940438858680547911512073341409607381040912992735354698571576155750843940415057647013711359949649102926524363237634349331663931595027679709000404758309617551370661140402128171288521363854241635064819660089300995273835099967771608069501973728126045089426572572945113066368225450235783211375678087346640641196055581645502430852650520923184043404571923469007524529184935909107202788041365082158979439820855282328056521446473319065347766237878289

_facs = [3, 173, 199, 306606827773]

facs = []
for x in _facs:
    facs.append(x*x)

sub_a = 4701715889239073150754995341656203385876367121921416809690629011826585737797672332435916637751589158510308840818034029338373257253382781336806660731169
sub_a *= sub_a
sub_b = 35760393478073168120554460439408418517938869000491575971977265241403459560088076621005967604705616322055977691364792995889012788657592539661
sub_b *= sub_b
from Crypto.Util.number import *
import gmpy2

for S in range(1 << 4):
    A = sub_a
    B = sub_b
    for i in range(4):
        if S >> i & 1:
            A *= facs[i]
        else:
            B *= facs[i]

    ng = 0
    ok = (1 << 1024)

    while ok - ng > 1:
        mid = (ng+ok) // 2
        if (A+mid)*(B+mid) >= n:
            ok = mid
        else:
            ng = mid

    P = A + ok
    Q = B + ok

    if P*Q != n:
        continue

    phi = (P - 1) * (Q - 1)

    d = pow(e, -1, phi)

    m = pow(cipher, d, n)

    print(long_to_bytes(m))

実行するとflagが出ます。

ctf4b{c0u1d_y0u_3nj0y_7h3_m4theM4t1c5?}