Zenn
🔓

SECCON CTF 13 Quals writeup (reiwa_rot13)

2024/11/30に公開
CTF
seccon
tech

問題

chall.py
from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))
output.txt
n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

考察

chall.py の処理を読んでいくと次のことがわかる。

  • 2つのメッセージが暗号化される
    • 英小文字10文字のメッセージ
    • そのメッセージの各文字を13文字ずらしてできるメッセージ
  • それら2つのメッセージに対して、同じRSAの鍵で暗号化がされている

2つのメッセージの差が分かっていれば、 Frankin-Reiter Related Massage Attack という攻撃ができる。
今回は各文字にあたる文字コードが、13足されたか引かれたかどちらかになる。パターン数としては 1024 通りなので、それらすべてに対して Frankin-Reiter Related Massage Attack をすればよさそうである。

平文 m, m + d に対して、同じ RSA の秘密鍵 e で暗号化した際、元のメッセージが簡単に求められる。
それらのメッセージの暗号文をそれぞれ c_1, c_2 とすると、

\begin{aligned} c_1 &= m^e \mod N \\ c_2 &= (m + d)^e \mod N \end{aligned}

として求められる。ここで関数 f, g を、

\begin{aligned} f(x) &= x^e - c_1 \mod N \\ g(x) &= (x + d)^e - c_2 \mod N \end{aligned}

とおくと、 f(m) = g(m) = 0 になるので、 (x - m) は f と g の共通因数になる。なので f, g の最大公約数を求めてやれば (x - m) を求めることができる。

解法

solve.py
from Crypto.Cipher import AES
from Crypto.Util.number import *
import hashlib

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"


def pgcd(f, g):
    while g:
        f, g = g, f % g
    return f

for x in range(1024):
    diff = 0
    for i in range(10):
        diff = diff << 8
        if (x >> i) & 1:
            diff += 13
        else:
            diff -= 13

    PR.<x> = PolynomialRing(Zmod(n))
    f = x^e - c1
    g = (x + diff)^e - c2
    h = pgcd(f, g).monic();
    key = -h[0]

    try:
        k = long_to_bytes(lift(key)).decode()
        cipher = AES.new(hashlib.sha256(k.encode()).digest(), AES.MODE_ECB)
        s = cipher.decrypt(encyprted_flag)
        print(s)
    except:
        pass

おわりに

実装中に、最大公約数を求める関数がインデントが1つずれていて、気づくまでに1時間ほどかかってしまった...。

def pgcd(f, g):
    while g:
        f, g = g, f % g
        return f

まぁでも、今年も1問解けて良かった。

Discussion