The Matrix Revolutions

cryptohack

Task: break Diffie-Hellman over GL(150, GF(2)) given G, A_pub=G^a, B_pub=G^b and the AES-encrypted flag. Solution: minpoly(G) = irreducible(deg89) * irreducible(deg61) with 2^89-1 and 2^61-1 both Mersenne primes; build a Krylov (cyclic) basis so G acts as the companion matrix, express A_pub*u in that basis to read off a(x)=x^a mod minpoly, reduce a(x) mod each irreducible factor to land in GF(2^89) and GF(2^61), solve the two field DLPs with PARI fflog (index calculus, instant), then CRT a mod 2^89-1 and a mod 2^61-1 to get the 149-bit private a, compute shared=B_pub^a, key=SHA256(bits)[:32], AES-CBC.