n!
Files given:
perm.py seems to be some generic implementation of permutations in python hence we can ignore it. In main, we see that our ciphertext is generated by XORing the flag with the output of shake256(key). Note that shake256 is an XOF which is basically a hash but with non-constant length.
def encrypt(key : str) -> str:
otp = shake_256(key.encode()).digest(len(FLAG))
return xor(otp, FLAG).hex()
random.shuffle(arr)
g = perm.Perm(arr)
a = randbits(h); b = randbits(h)
A = g ** a; B = g ** b
S = A ** b
key = str(S)
print(f"g = [{g}]"); print(f"A = [{A}]"); print(f"B = [{B}]");
print(f"c = {encrypt(key)}")
Here we see it is a very simple DLP problem. Since sage has a convenient implementation of permutations for us, we shall use it to solve for \(a\) and \(b\). First we check the order of \(g\) and see if it is smooth.
with open("out.txt","r") as f:
d = [i.split(" = ")[1] for i in f.read().split("\n")]
g = eval(d[0])
g = PermutationGroupElement(Permutation([i+1 for i in g]))
factor(g.order())
\[\ord(g)=2^2\times3^3\times5\times7\times17\times19\times73\times113\times241\]
we see that the primes are extremely small, hence we can use Pohlig Hellman to solve this quite quickly.
Solution at solve.sage
Flag:
grey{DLP_Is_Not_Hard_In_Symmetric_group_nzDwH49jGbdJz5NU}