ASIS CTF Finals 2022 | vindica

#ASIS_CTF_Finals_2022

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag

def genkey(nbit, k):
    p = getPrime(nbit)
    q = getPrime(nbit >> 2)
    n = p * q
    N = (p**k - 1) * (q**k - 1)
    while True:
        e = getRandomRange(1, n)
        if gcd(e, n * N) == 1:
            pkey = e, n, N
            skey = p, q
            return (pkey, skey)

def two_layencrypt(msg, pkey):
    e, n, _ = pkey
    Zn = Zmod(n)
    m = bytes_to_long(msg)
    c = pow(m, e, n)
    _c = str(c)
    l = len(_c)
    _C = matrix(Zn, [[_c[:l//4], _c[l//4:l//2]], [_c[l//2:3*l//4], _c[3*l//4:l]]])
    assert gcd(det(_C), n) == 1
    C = _C ** e
    return C

k, nbit = 2, 1024

pkey, skey = genkey(nbit, k)
e, n, N = pkey

C = two_layencrypt(flag, pkey)

print(f'e = {e}')
print(f'n = {n}')
print(f'N = {N}')
print(f'C = {C}')

RSAと一般線形群上のRSA が二重掛けされている。とがあるので2式2変数なのでは簡単に求まり、やるだけ

暗号化で_C を作るときにleading zeroが消されているのでそれを復元してやる必要がある。なんだよそれ

# x, y = var('x, y')
# print(solve([n == x*y, N == (x**2 - 1)*(y**2 - 1)], x, y))

q = 170950292762310001223264475563312197286468934237604625244016377089655659415827654558423281087771522536195925401695701205922507577611932071437586268226766948989462882073821682716809333625293648698727995625804013710985655128890033313001359735306829870876327269630717849331861869587268227270644358638927032228841
p = 60620086000298754361622014599171452513716275594322952570361588639323700833033
assert n == p * q
assert N == (p**2 - 1) * (q**2 - 1)
C = matrix(Zmod(n), C)
d = inverse_mod(e, N)
M = C**d
assert M**e == C

cs = str(M[0][0]) + "00" + str(M[0][1]) + "0" + str(M[1][0]) + str(M[1][1])
c = int(cs, 10)
d = inverse_mod(e, (p-1)*(q-1))
m = pow(c, d, n)

assert pow(m, e, n) == c

print(bytes.fromhex(hex(m)[2:]))