🔄

SECCON CTF 2024

2024/11/25に公開

CTF

お家で、Fate/Zeroを見ていたらCTFが始まっていました。

 Crypto
 reiwa_rot13AES_ECBで暗号化されたフラッグと、それに使われたKeyがRSAで暗号化されている問題。

解く順番としては、おそらくKeyを復号してからそれを使ってフラッグを手に入れに行かせたいんだなと感じる。
output.txtではn,e,c1,c2,encyprted_flagが与えられている。

そして、c1,c2がそれぞれ平文ｍとROT13されたｍであることが、Pythonからわかる。

あとeがそれなりに小さい。
RSAで復号に必要なのはp,q,dのどれか一つだが、今回はどれも取れそうではない。

eは小さいがそれが有効に作用するのはm^e < nが成り立つ場合だ。

かといってc1,c2の差分からなにか得られるわけでもない。なので、攻撃方法探しの放浪の旅に出る。「RSA CTF [検索]」
RSAの攻撃でよく見つかる方法としては「Coppersmith Method」が多い。（今ひとつわかっていないので、スルーしている。）

今回は、Franklin-Reiter Related Message Attackが目に入った。参考サイト

2つの平文m1,m2が以下のような形で表せて、且つそれぞれの暗号文が手に入っているとき平文を複合できるようだ。参考サイト
 m_1  m_2 = am_1 + b式は難しかったので完全に理解できたわけではないが、要するに上の式みたいにm1とm2に関係があるときに最大公約数を取ったらm1が取得できるらしい。こういう式に起こせる。
f(x) = x^e - c_1f(x) = (am_1 + b)^e -c_2今回はROT13なので、bの部分にそれぞれの文字に13足す(a->n)か13引く(n->a)かしたものをなんとかいれたら良さそうと考えた。ただ、どうなっているかわからないので総当たりしかない。

なので、差分全部作成させる部分を作成した。

def generate_all_patterns():
    # 'a' と 'n' の2種類の文字で10桁のパターンを生成
    for pattern in product("an", repeat=10):
        # パターンを文字列に結合
        yield "".join(pattern)

# ROT13シフトの計算
def calculate_rot13_shift(original):
    rotated = codecs.encode(original, 'rot13')
    print("ROT13:", rotated) 
    shift_value = bytes_to_long(rotated.encode()) - bytes_to_long(original.encode())
    print("ROT13 shift value:", shift_value)
    return shift_value
あとは Franklin-Reiter Related Message Attackでなんとかしたらいいので、m1をXとおいて、SympyのPolyで連立方程式を立てて最大公約数を取る。

from Crypto.Util.number import *
import codecs
import string
import random
import sys
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from sympy import symbols, gcd, Poly

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233

x = symbols('x')
rot13_shift = bytes_to_long((chr(13)+chr(13)+chr(13)+chr(13)+chr(13)+chr(13)+chr(13)+chr(0)+chr(13)+chr(13)).encode())
# 多項式 g(x), h(x) を構築
g = Poly(x**e - c1, x, modulus=n)
h = Poly((x + rot13_shift)**e - c2, x, modulus=n)  # rot13_shift は ROT13 による変換値

# 最大公約数を計算
gcd_poly = gcd(g, h)

print(gcd_poly)
# GCD の根を取得
m1 = gcd_poly.nroots()

# メッセージを復元
if m1:
    key = long_to_bytes(int(m1[0]))
    print("Recovered key:", key)

Crypto

reiwa_rot13

Discussion