Easy_calc ·

Table of Contents

description:

😆

Approach
#

We weren’t able to solve this during the CTF

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

so basically the encryption algorithm is using an AES cipher using s as the key, and given p and A we have to get the value of s

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

this is the algorithm used to generate A that we have to crack

taking some dry runs: $$ u = s(p-1) \mod p \newline u = s(p - s - 2) \mod p \newline u = s(p - s^2 - 2s - 3) \mod p \newline $$ and so on

this gives us something like the series $\sum_{i=1}^{p-1} is^{p-i} \mod p$ which is an AGP

solving this AGP gave me

$$ \frac {s(s^p - s)}{(s-1)^2} - \frac {s(p-1)}{(s-1)}\mod p $$

at this point I was stumped because I had no idea how to solve for $s$ with the $s^p$ term in the expression, I remembered seeing a considerably simpler expression in the WaniCTF discord which motivated me to try further

I searched for

$s^p \mod p$

and was guided to “Fermat’s Little Theorem” which states that $$ s^p - s \mod p = 0 $$ this means that I can neglect the first term in my AGP expression giving me finally $$ A = \frac {s}{(1-s)} \mod p $$ which I can rearrange for s as $$ s = \frac {A}{A + 1} \mod p $$

now I have $A, p$ which gives me $s$ and I also have the iv, now I can decrypt the AES cipher

I still stumbled with the python code and took help from some writeups though

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

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

s = (A) * pow(1 + A, -1, p) % p


def decrypt(c: bytes, key: int) -> bytes:
    iv = c[:16]
    ciphertext = c[16:]
    key = long_to_bytes(key)
    key = md5(key).digest()
    cipher = AES.new(key, AES.MODE_CBC, iv=iv)
    decrypted = cipher.decrypt(ciphertext)
    return decrypted


m = decrypt(bytes.fromhex(ciphertext), s)

print(m)