RDSA派生アルゴリズムと攻撃手法

連続素数を利用したRSA (MRCTF2020 babyRSA)

この課題では、RSAの鍵生成に連続する素数と特殊な演算が使用されています。まず、公開情報から17個の連続した小さな素数を復元し、それらの積からなる $n$ を算出する必要があります。与えられた $p^{65537} \pmod n$ という値を利用し、離散対数問題的なアプローチあるいは既知の構造を利用して大きな素数 $p$ を特定し、そこから素数判定を用いて実際の $p$ を得ます。同様に $q$ についても特定し、通常通りRSA復号を行います。

import sympy
import gmpy2

# 与えられた10番目の素数とパラメータ
target_prime = 206027926847308612719677572554991143421
base_exponent = 65537
mod_factor = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839

# 連続する素数の生成
small_primes = [target_prime]
for _ in range(9):
    small_primes.insert(0, sympy.prevprime(small_primes[0]))
for _ in range(7):
    small_primes.append(sympy.nextprime(small_primes[-1]))

# nの計算
n_val = 1
for x in small_primes:
    n_val *= x

# pの復元 (p^base ≡ factor mod n)
# ここでは問題の性質上、p自体はfactorから直接導出するか、離散対数を解く必要があるが、
# 今回は次の素数というヒントがあるため、復元したpの次の素数を探す
# 簡略化のため、pを求めるロジックを記述
# 実際のCTFでは特定のアルゴリズムでpを求める
# ...
# 求めたpとqを用いて復号
# p = recovered_p
# q = recovered_q
# phi = (p-1)*(q-1)
# d = gmpy2.invert(base_exponent, phi)
# m = pow(ciphertext, d, p*q)
# print(gmpy2.iroot(m, base_exponent))

Rabin暗号へのアプローチ (WUSTCTF2020)

Rabin暗号は $c \equiv m^2 \pmod n$ という式で表され、$n$ の素因数 $p, q$ が $4k+3$ の形である場合、中国残余定理を用いて復号可能です。復号結果は4通り存在し、その中から意味のある平文を選択します。

import gmpy2

def decrypt_rabin(c, p, q):
    n = p * q
    # m_p = c^((p+1)/4) mod p
    mp = pow(c, (p + 1) // 4, p)
    # m_q = c^((q+1)/4) mod q
    mq = pow(c, (q + 1) // 4, q)

    # 中国残余定理の適用
    # gcd, yp, yq = gmpy2.gcdext(p, q)
    yp = gmpy2.invert(p, q)
    yq = gmpy2.invert(q, p)
    
    r = (yp * p * mq + yq * q * mp) % n
    s = (yp * p * mq - yq * q * mp) % n
    
    return [r, n - r, s, n - s]

# 例: c=162853095, p=49123, q=10663
# candidates = decrypt_rabin(162853095, 49123, 10663)
# 候補の中からフラグ形式に合うものを探す

DPの漏洩攻撃 (WUSTCTF2020 dp_leaking)

$d_p = d \pmod{p-1}$ が漏洩している場合、$d_p \cdot e = k(p-1) + 1$ という関係式を利用して $p$ を特定できます。$k$ は小さい値であるため、総当たり攻撃が可能です。

from Crypto.Util.number import long_to_bytes
import gmpy2

# 入力値
e = 65537
n = 0xDEADBEEF... # 省略
dp = 0xBADCODE... # 省略
ciphertext = 0xCIPHER... # 省略

for k in range(1, e):
    if (dp * e - 1) % k == 0:
        potential_p = (dp * e - 1) // k + 1
        if n % potential_p == 0:
            p = potential_p
            q = n // p
            phi = (p - 1) * (q - 1)
            d = gmpy2.invert(e, phi)
            m = pow(ciphertext, d, n)
            print(long_to_bytes(m))
            break

LCMとEulerのトーティエント関数 (NPUCTF2020 EzRSA)

通常RSAでは $\phi(n) = (p-1)(q-1)$ を使用しますが、本問題では $\lambda(n) = \text{lcm}(p-1, q-1)$ が与えられています。RSAの復号において、$\lambda(n)$ は $\phi(n)$ の倍数として機能し、$\lambda(n)$ を直接用いて $d$ を計算しても正しく復号できます。

from Crypto.Util.number import long_to_bytes, inverse

# gift = lcm(p-1, q-1) が与えられている
lcm_val = 0x...
e = 54722
c = 0x...
n = 0x...

# eが2の倍数である場合、調整が必要
if e % 2 == 0:
    e_reduced = e // 2
    d = inverse(e_reduced, lcm_val)
    m = pow(c, d, n)
    # 平方根を取る
    m, is_root = gmpy2.iroot(m, 2)
    if is_root:
        print(long_to_bytes(m))

共通剰余攻撃と多項式方程式 (De1CTF2019 babyrsa)

この問題は複数のステージで構成されており、特に最終段階では共通の素数 $p$ を含む異なるモジュラス $n_1, n_2$ が登場します。暗号文 $c_1, c_2$ に対し、$c_1 \equiv m^e \pmod{n_1}$, $c_2 \equiv m^e \pmod{n_2}$ が成り立ちます。ここで、$m^{gcd} \pmod{n}$ の形に変形し、中国残余定理を用いて方程式を統合し、Coppersmith法などで $m$ を解きます。具体的には、$m^{14}$ に関する合同式を組み合わせて $m^2$ を求める式を導出します。

# 複数ステージの解決例
# 1. CRTによるpの特定
# 2. 小さなeに対する低根攻撃
# 3. factordbによる因数分解
# 4. 共通素数を利用した多項式方程式の解決 (SageMath)

# Stage 4: m^2を求めるSageMathスクリプトの概念
# PR.<m> = PolynomialRing(Zmod(n_combined))
# f = m^2 - target_val
# roots = f.small_roots(X=2^200)
# m_val = roots[0]
# flag = m_val.sqrt()

Wiener攻撃と連分数展開 (羊城杯 2020)

$d$ が小さい場合、Wiener攻撃が有効です。$e/n$ の連分数展開を行うことで、$k/d$ の近似値を求め、そこから $p, q$ を特定します。

import gmpy2

def wiener_attack(e_val, n_val):
    # 連分数展開
    cf = gmpy2.continued_fraction(e_val, n_val)
    convergents = gmpy2.convergents(cf)
    
    for k, d in convergents:
        if k == 0: continue
        if (e_val * d - 1) % k == 0:
            phi = (e_val * d - 1) // k
            # x^2 - (n - phi + 1)x + n = 0 を解く
            p = gmpy2.isqrt(n_val - phi + 1)
            # 詳細なチェック...
            # p, qが見つかれば復号

古典暗号とその解析手法

多段階の古典暗号 (UTCTF2020 basic-crypto)

この問題は古典暗号の組み合わせです。解析手順は以下の通りです。

1. バイナリからテキストへ: バイナリデータをASCII文字列に変換。
2. Base64デコード: 変換された文字列をBase64としてデコード。
3. ヴィジュネル暗号: 得られた文字列に対し、ヴィジュネル暗号と推測して鍵長と鍵を特定する。
4. 置換暗号: 最後に残った文字列に対して単語のパターンマッチングなどを行い、置換テーブルを復元する。

ポリュビオスの方格 (Polybius Square)

ポリュビオス方格は、文字を数字のペア（座標）に置き換える暗号です。鍵となる文字列の順序が不明な場合、合理的な文字の並び（母音など）をヒントに全探索を行い、意味のある単語が出現するかを確認します。

共通モジュラス攻撃 (XNUCA2018 Warmup)

異なる公開鍵 $(e_1, n)$, $(e_2, n)$ で同じ平文 $m$ が暗号化されている場合、$e_1, e_2$ が互いに素であれば $ed_1 + ed_2 = 1$ となる $d_1, d_2$ を見つけ、$c_1^{d_1} c_2^{d_2} \pmod n$ により $m$ を復元できます。

離散対数問題とストリーム暗号

離散対数問題 (Wangding Cup 2020 you_raise_me_up)

有限体 $F_p$ 上で $g^x \equiv h \pmod p$ を満たす $x$ を求める問題です。$p$ が素数の場合、Sympyなどの数式計算ライブラリを用いて `discrete_log` 関数を適用することで効率的に解を求めることができます。

import sympy

p = 0x...
g = 0x...
h = 0x...

x = sympy.discrete_log(p, h, g)
print(x)

OTPの再利用 (UTCTF2020 OTP)

ワンタイムパッド (OTP) において、同じ鍵が再利用された場合、$C_1 \oplus C_2 = (M_1 \oplus K) \oplus (M_2 \oplus K) = M_1 \oplus M_2$ という性質を利用します。既知の平文が一部ある場合、または推測可能な単語がある場合、それを XOR して鍵や他の平文を導き出します。

def xor_bytes(a, b):
    return bytes(x ^ y for x, y in zip(a, b))

encoded_a = bytes.fromhex("213c234c...")
original_a = b"THE BEST CTF..."
key_guess = xor_bytes(encoded_a, original_a)
# この鍵を使ってEncoded Bを復号