#gcd

1000개의 RSA 암호문과 모듈러를 주는 문제. 각 모듈러는 네 소수의 곱이고, 각 소수는 정확히 네 개의 모듈러에 공유된다. 두 모듈러의 최대공약수로 공유 소수를 캐내 전부 인수분해하고, 모든 평문을 복호해 XOR하면 플래그가 나온다. 단, 모든 쌍을 O(n²)으로 대조하면 1000개 기준으로 실제 20초 넘게 걸린다 — 실무에서 대규모 키 집합을 감사할 때는 이 방식이 그대로는 안 통한다.

플래그를 상수 키로 XOR해 숨기고, 그 키에 서로소인 두 수를 곱한 a·b를 힌트로 주는 문제. gcd(a, b) = key · gcd(x, y) = key 이므로 두 곱의 최대공약수가 곧 XOR 키다. 유클리드 호제법을 손으로 직접 따라가며 508153과 610791의 gcd가 73으로 수렴하는 과정을 확인하고, 그 키로 enc를 XOR하면 플래그가 나온다.