BLOG2026-08-17
blog
[🥈 Silver 4] 소수를 모듈러로 쓴 제곱 PRNG에서 시드 되찾기 — DreamHack the present 풀이
플래그를 시드로 넣은 제곱 되먹임 PRNG가 두 번째 출력만 공개한다. 모듈러가 두 소수의 곱이 아니라 512비트 소수 하나라서, 제곱근이 거듭제곱 한 번으로 계산된다. 네제곱근 후보를 전부 구하고 이차잉여 판정으로 가지를 쳐내니 남은 건 두 개뿐이었고 그중 하나가 그대로 플래그였다.
#dreamhack#ctf#crypto+6