Tags: crypto 

Rating: 3.0

We are given the output of the following script.

from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p

def encrypt(m, k, p):
return pow(m, 1 << k, p)

assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)

k = 64
pt = bytes_to_long(flag.encode())
ct = encrypt(pt, k, p)

with open("output.txt", "w") as f:
f.write(str(ct) + "\n")
f.write(str(p) + "\n")


We know that the flag $m$ satisfies the congruence $m^e = c \mod p$ for $e=e^{64}$.
We can easily compute an $e$-th root of $c$ using sage, but it is not unique.

R = GF(p)(c).nth_root(2^64)

It holds that two $e$-th roots are equal up to a root of unity:
Let $R, R'$ be two $e$-th roots of $c$ and $\alpha = R/R'$.
Then $\alpha^e = R^e/{R'}^e = c/c = 1$.

This gives us an idea to solve the challenge:
Iterate over all $e$-th roots of unity $\alpha$ and check if $\alpha R$ is the flag (i.e., contains `TWCTF{`).

How many roots of unity are there and how can we compute them?
Let $g$ be a generator of $\mathbb Z_p^*$ ($g=3$ works).
Let $\alpha = g^a$ an $e$-th root of unity.
Therefore, $\alpha^e = 1$ or equivalently $ae = 0 \mod (p-1)$.
Hence, $(p-1) \mid a\cdot 2^{64}$.
Equivalently, $a$ must be a multiple of $(p-1)/2^{30}$, since $2^{30}$ is the largest power of $2$ that divides $p-1$.

Therefore, we can iterate all $e$-th roots of $c$ by repeatedly multiplying $R$ with $3^{(p-1)/2^{30}}$.

from multiprocessing import Process, Queue
from Crypto.Util.number import long_to_bytes

R = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271

q = Queue()
def search(start, n, notify=0x10000):
a = (p-1)//2**30
r0 = pow(3, a, p)
b = R * pow(3, a*start, p)
for i in range(n):
flag = long_to_bytes(b)
if b"TWCTF{" in flag:
if i % notify == 0:
b = r0 * b % p

N = 16
chunk_size = 2**30//N
procs = []
for i in range(0, 2**30, chunk_size):
proc = Process(target=search, args=(i, chunk_size))
cnt = 0
while 1:
cnt += q.get()