The Matrix

cryptohack

Task: a 50x50 invertible matrix over GF(2) encodes the flag bits (mat[i][j]=msg[i+j*N]) and only ciphertext=mat^E with public E=31337 is given. Solution: a matrix over a finite field is periodic, so compute the multiplicative order of the ciphertext matrix via factoring its minimal polynomial over GF(2) (ord(C)=351843720888315), invert the exponent d=E^-1 mod ord, recover mat=C^d by fast GF(2) matrix exponentiation (verify mat^E==C), then read the first 280 flag bits from mat[i][j]=msg[i+j*N].