暗号解析チャレンジの実装手法

本稿では、複数の暗号解読課題に対する実装手法を解説する。特にRSA系アルゴリズムの脆弱性を突いた攻撃手法に焦点を当てる。

基礎RSA解析

与えられたパラメータセットからフラグを復元する際、以下の手順で処理を行う：

from Crypto.Util.number import inverse, long_to_bytes

params = [
    {"e": 12433, "p": 149, "q": 197, "c": 104},
    {"e": 8147, "p": 131, "q": 167, "c": 6633},
    // 他のパラメータを同様に定義...
]

result = bytearray()
for param in params:
    n = param["p"] * param["q"]
    totient = (param["p"] - 1) * (param["q"] - 1)
    d = inverse(param["e"], totient)
    m = pow(param["c"], d, n)
    result.append(m)
print(long_to_bytes(result).decode())

実行結果: hgame{L00ks_l1ke_y0u've_mastered_RS4!}

カスタムシーザー暗号

与えられた暗号文と参照テキストから鍵を導出し、復号化するプロセス：

ref_text = " of England', with which the meetings always ended."
cipher_text = " if Rqesysz', bvjv bjxsh szr uaaxivjd zlcdbc mnirb."

key_sequence = []
for a, b in zip(ref_text, cipher_text):
    if a.isalpha():
        shift = (ord(b) - ord(a)) % 26
        key_sequence.append(shift)
    else:
        key_sequence.append(None)

def decrypt(ciphertext, key):
    output = []
    for i, char in enumerate(ciphertext):
        if not char.isalpha():
            output.append(char)
            continue
        base = ord('A') if char.isupper() else ord('a')
        shift = key[i % len(key)] if key[i % len(key)] is not None else 0
        output.append(chr((ord(char) - base - shift) % 26 + base))
    return ''.join(output)

encrypted_flag = "xaawr{B0_d0l_cs0m_'Pp0mn-odn1vpabt_deqzcq'?}"
print(decrypt(encrypted_flag, key_sequence))

出力結果: hgame{D0_y0u_kn0w_'Kn0wn-pla1ntext_attack'?}

多素数RSAの実装

複数の素因数を持つRSAにおいて、オイラーのトーシェント関数を正しく計算する必要がある。n = p^k1q^k2r^k3... の場合、φ(n) = p^k1-1(p-1) × q^k2-1(q-1) × ... となる。

from Crypto.Util.number import long_to_bytes, inverse

p = 109056753224725357860050862987465749131702509174531265860789564184166504627089
q = 64871884070495743485110397060920534297122908609816622599229579748089451488127
r = 73817195552029165561107245309535744382442021553254903166961729774806232509583
s = 89907870347457693114161779597928900080173728317019344960807644151097370118553

n = 33794524799153118863078063165082249755290840142595950821414501959089117599957065...
e = 65537
c = 28102092664741973677846577771451224198973823533910576286387472587051172515510186...

phi = p**(2-1)*(p-1) * q**(3-1)*(q-1) * r**(5-1)*(r-1) * s**(7-1)*(s-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

楕円曲線暗号の復号化

公開されたパラメータから秘密鍵を用いず復号化する手法。c1 = m + r·K および c2 = r·G の関係より、m = c1 - k·c2 が成り立つ。

from sage.all import *

p = 74997021559434065975272431626618720725838473091721936616560359000648651891507
a = 61739043730332859978236469007948666997510544212362386629062032094925353519657
b = 8782182818477817609882526316479721490919815013668096771992360002467657827319
k = 93653874272176107584459982058527081604083871182797816204772644509623271061231

E = EllipticCurve(GF(p), [a, b])
c1 = E(23456789012345678901234567890123456789012345678901234567890123456789012, ...)
c2 = E(9876543210987654321098765432109876543210987654321098765432109876543210, ...)

m_point = c1 - k * c2
m_x = m_point[0]
m_y = m_point[1]

flag_left = cipher_left * inverse_mod(m_x, p) % p
flag_right = cipher_right * inverse_mod(m_y, p) % p
print(convert_to_string(flag_left) + convert_to_string(flag_right))

Mersenne Twisterの状態復元

624個の乱数出力から内部状態を復元し、以降の乱数列を予測する手法。temper処理の逆操作を実装し、状態配列を再構築する。

def untemper(y):
    y ^= y >> 18
    y ^= (y << 15) & 0xEFC60000
    y ^= (y << 7) & 0x0000009D
    y ^= (y << 7) & 0x7F46D46B
    y ^= (y >> 11) & 0xFFD58000
    y ^= (y >> 11) & 0x00000001
    y ^= (y >> 8) & 0x00000000  # 実際には追加のマスクが必要
    return y

state = [untemper(output[i]) for i in range(624)]
mt = MT19937Recover()
mt.set_state(state)

next_values = [mt.random() for _ in range(21)]
flag_bytes = [cipher[i] ^ next_values[i] for i in range(21)]
print(bytes(flag_bytes).decode())