#gf2

정수가 아니라 GF(2) 위 4096차 다항식을 법으로 쓰는 RSA. "Red or Black, 0 or 1, binary fields"라는 힌트 그대로 곱셈은 carryless 다항식 곱이고 암호문은 flag^65537이다. 정수 인수분해는 어렵지만 유한체 위 다항식 인수분해는 다항시간이라, n을 0.16초 만에 8개 기약다항식으로 쪼개 유닛군 위수를 구하고 d=e⁻¹로 flag를 복원한다.

15MB짜리 disaster.py 안에 시프트·XOR 연산이 320,000줄 흩뿌려져 있고 함수 32개가 각각 8비트만 돌려준다. 세 연산 모두 자리올림이 없어 GF(2) 위에서 선형이라, 전체가 f(v) = A·v + c 라는 아핀사상 하나로 접힌다. f(0)으로 상수를, f(e_i)로 열벡터를 뽑아 257번 호출만에 256×256 행렬을 복원하고 가우스 소거 한 번으로 끝났다.

같은 23088비트를 32비트씩, 16비트씩, 8·4·2비트씩, 마지막엔 1비트씩 흘리는 여섯 개의 MT19937. twist 도 tempering 도 GF(2) 위에서 선형이라 누출 비트 하나가 곧 1차식 한 줄이 된다. 19968개 미지수를 numpy 비트팩 소거로 풀어 상태를 복원하고, 예측한 난수로 AES 키 체인을 되감아 플래그까지 갔다.