Cycles - author: overllama - crypto

Writeup - bylal

By exploiting the fact that $g^a \equiv 1 \pmod{p}$ and that the order of 3 in $(\mathbb{Z}/p\mathbb{Z})^\times$ is $A = p - 1$, we deduce that $a = k(p - 1).$

Since $\text{len}(\text{bin}(a)) < 1050$, we know that $k < 2^{26}$, and it’s sufficient to try a few small values of $k$:

1. For each $k$, set $a_k = k(p - 1)$.
2. Compute the AES key: $\text{key}_k = \text{long_to_bytes}(a_k)[:16].$
3. Decrypt the ciphertext using AES-ECB and remove PKCS#7 padding.

We quickly find that for $k = 29,$ the decryption gives valid padding and reveals the flag.

Then writing a quick python script we find the flag:

byuctf{1t_4lw4ys_c0m3s_b4ck_t0_1_21bcd6}