The Matrix Reloaded

cryptohack

Task: recover SECRET from H=G^SECRET in GL(30, F_p) given only one pair (v, w=H*v); p-1 holds a 364-bit prime so the field DLP is hopeless. Solution: G's characteristic polynomial has an eigenvalue lambda0 of algebraic multiplicity 2 but geometric multiplicity 1 -> a 2x2 Jordan block, on which G^S f = lambda0^S f + S*lambda0^(S-1) e exposes SECRET LINEARLY; project the single pair with the left eigenvector l0 and left generalized eigenvector l1 to solve SECRET = (l1.w - lambda0^S*(l1.v))*lambda0 / (lambda0^S*(l0.v)) mod p with NO discrete log, then KEY=SHA256(str(SECRET))[:32] AES-CBC decrypts the flag.