redpwn CTF 2021 | scrambled-elgs

#redpwnctf2021

#!/usr/bin/env sage
import secrets
import json
from Crypto.Util.number import bytes_to_long, long_to_bytes
from sage.combinat import permutation

n = 25_000
Sn = SymmetricGroup(n)

def pad(M):
    padding = long_to_bytes(secrets.randbelow(factorial(n)))
    padded = padding[:-len(M)] + M
    return bytes_to_long(padded)

#Prepare the flag
with open('flag.txt','r') as flag:
    M = flag.read().strip().encode()
m = Sn(permutation.from_rank(n,pad(M)))

#Scramble the elgs
g = Sn.random_element()
a = secrets.randbelow(int(g.order()))
h = g^a
pub = (g, h)

#Encrypt using scrambled elgs
g, h = pub
k = secrets.randbelow(n)
t1 = g^k
t2 = m*h^k
ct = (t1,t2)

#Provide public key and ciphertext
with open('output.json','w') as f:
    json.dump({'g':str(g),'h':str(h),'t1':str(t1),'t2':str(t2)}, f)

対称群 上の離散対数問題

sageのdiscrete logが対応していない群の離散対数問題を解くテク で、今回は位数が小さい素因数に分解できるのでPohlig-Hellman Attackすれば良い

import json

n = 25_000
Sn = SymmetricGroup(n)

output = json.loads(open("output.json").read())

g = Sn(output["g"])
h = Sn(output["h"])

g_order = g.order()
facs = list(factor(g_order))

dlogs = []
for p, e in facs:
    g1 = g**(g_order // p**e)
    h1 = h**(g_order // p**e)
    for d in range(p**e):
        if g1^d == h1:
            dlogs.append((d, p**e))
            print(f"d = {d}, p = {p}, e = {e}")
            break

print("dlogs =", dlogs)

rems = [i[0] for i in dlogs]
mods = [i[1] for i in dlogs]
secret = CRT(rems, mods)