WaniCTF 2024 : easy calc

roaris commented 4 months ago

https://github.com/wani-hackase/wanictf2024-writeup/tree/main/cry/easy_calc

本番で解けなかった問題

roaris commented 4 months ago

import os
import random
from hashlib import md5

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, getPrime

FLAG = os.getenvb(b"FLAG", b"FAKE{THIS_IS_NOT_THE_FLAG!!!!!!}")

def encrypt(m: bytes, key: int) -> bytes:
    iv = os.urandom(16)
    key = long_to_bytes(key)
    key = md5(key).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    return iv + cipher.encrypt(m)

def f(s, p):
    u = 0
    for i in range(p):
        u += p - i
        u *= s
        u %= p

    return u

p = getPrime(1024)
s = random.randint(1, p - 1)

A = f(s, p)
ciphertext = encrypt(FLAG, s).hex()

print(f"{p = }")
print(f"{A = }")
print(f"{ciphertext = }")

roaris commented 4 months ago

$s$がAESの鍵なので、 $A$から $s$を求めることを考える $A(=f(s, p))$について考える

$$ \begin{aligned} A &= ((\ldots((ps+p-1)s+p-2)s+\ldots+2)s+1)s \\ &= ps^{p}+(p-1)s^{p-1}+\ldots+2s^{2}+s \\ &= \sum_{i=1}^{p} is^{i} \end{aligned} $$

さらに簡単にすることが出来る受験数学では「等差数列と等比数列の積の和」というパターンである https://examist.jp/mathematics/sequence/tousatouhiwa/

$$ \begin{aligned} A &= s + 2s^{2} + 3s^{3} + \ldots + (p-1)s^{p-1} + ps^{p} \\ sA &= s^{2} + 2s^{3} + \ldots + (p-2)s^{p-1} + (p-1)s^{p} \\ (1-s)A &= s + s^{2} + s^{3} + \ldots + s^{p-1} + s^{p} \\ &= \frac{s(1-s^{p})}{1-s} \\ A &= \frac{s(1-s^{p})}{(1-s)^{2}} \end{aligned} $$

となるここまでは本番で出来たのだが、ここからさらに式変形をしないと解けないフェルマーの小定理

$$ s^p = s \mod p $$

を使うこれによって、

$$ \begin{aligned} A &= \frac{s(1-s^{p})}{(1-s)^{2}} \\ &= \frac{s}{1-s} \\ s &= \frac{A}{1+A} \end{aligned} $$

となる

roaris commented 4 months ago

from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes

p = 108159532265181242371960862176089900437183046655107822712736597793129430067645352619047923366465213553080964155205008757015024406041606723580700542617009651237415277095236385696694741342539811786180063943404300498027896890240121098409649537982185247548732754713793214557909539077228488668731016501718242238229
A = 60804426023059829529243916100868813693528686280274100232668009387292986893221484159514697867975996653561494260686110180269479231384753818873838897508257692444056934156009244570713404772622837916262561177765724587140931364577707149626116683828625211736898598854127868638686640564102372517526588283709560663960
ciphertext = '9fb749ef7467a5aff04ec5c751e7dceca4f3386987f252a2fc14a8970ff097a81fcb1a8fbe173465eecb74fb1a843383'

s = A * pow(1+A, -1, p) % p
key = md5(long_to_bytes(s)).digest()

ciphertext = bytes.fromhex(ciphertext)
iv = ciphertext[:16]
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
plaintext = cipher.decrypt(ciphertext[16:]).decode()
print(plaintext) # FLAG{Do_the_math396691ba7d7270a}

パディングされていないので、decryptの結果をunpadする必要はない

roaris / ctf-log

WaniCTF 2024 : easy calc #58