[🥉 브론즈 3] 세 나머지를 합쳐 flag를 되살리다 — DreamHack chinese what? 풀이

수식으로는, 모듈러들의 곱을 N = p1·p2·p3, 각 Ni = N / pi라 할 때

로 계산한다. Ni는 pi를 제외한 나머지 소수들의 곱이라 pj(j≠i)로는 나누어떨어지고, pi에 대해서만 역원을 곱해 딱 그 자리에서만 1이 되게 맞춘다. 그래서 각 항이 서로 간섭 없이 자기 나머지 조건만 만족시킨다.

핵심 조건은 "원래 수가 N보다 작아야 한다"는 것이다. CRT가 주는 답은 mod N 값이라, 원래 수가 N 이상이면 잘려 나간 정보를 되살릴 수 없다. 이 문제는 그 조건이 성립하도록 소수를 넉넉히 잡았다.

🔬 정찰 — flag를 나머지로만 흘렸다

prob.py를 보면 구조가 한눈에 들어온다.

flag를 정수로 만든 뒤, 세 개의 420비트 소수로 나눈 나머지 c1, c2, c3을 출력한다. output.txt에는 소수 세 개와 나머지 세 개가 그대로 들어 있다.

즉 우리가 아는 것은 pi와 flag mod pi뿐이다. 딱 CRT가 풀어내라는 형태다.

💣 핵심 — 왜 하나로는 안 되고, 셋이면 되는가

나머지 하나(c1 = flag mod p1)만으로는 flag를 못 되돌린다. flag가 p1보다 크기 때문이다. flag는 약 471비트(약 59바이트)인데 p1은 420비트라, flag mod p1은 이미 한 바퀴 이상 돌아 나온 값이다. c1만으론 flag가 c1인지 c1 + p1인지 c1 + 2·p1인지 알 수 없다.

그런데 서로 다른 소수 세 개로 나눈 나머지를 모두 알면 이야기가 달라진다. 세 소수의 곱 N = p1·p2·p3은 약 1259비트라 flag(471비트)보다 훨씬 크다. CRT는 0 ≤ x < N 범위에서 세 나머지 조건을 모두 만족하는 x를 유일하게 준다. flag가 이 범위 안에 있으니, 그 유일한 x가 바로 flag다. 작은 수로 원리를 먼저 확인해 봤다.

x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)를 CRT로 합치면 x = 23 하나로 떨어지고, 실제로 23을 각 수로 나누면 원하는 나머지가 나온다. 이 문제도 똑같이, 소수만 훨씬 클 뿐이다.

🚀 익스플로잇

CRT 공식을 그대로 구현해 세 합동식을 합친다.

복원한 정수가 정말 flag가 맞는지, 비트 수와 나머지 왕복으로 확인했다.

flag는 471비트로 N(1259비트)보다 작아 CRT 조건을 만족하고, 복원한 정수를 다시 각 소수로 나누면 원래 나머지 c1, c2, c3와 정확히 일치한다. 바이트로 되돌리면 플래그다.

"The Chinese remainder theorem was quite easy, right?" — 정말 그렇다.

📝 결론

CRT는 나머지 조각들을 원본으로 되돌리는 정리다.

이 문제는 flag를 세 개의 나머지로 쪼갰지만, 서로소인 소수들의 곱이 flag보다 크기만 하면 그 조각들은 언제든 하나로 합쳐진다. CRT는 RSA-CRT(개인키 연산 가속), 비밀 분산, 격자 공격 등 암호학 곳곳에서 쓰이는 기본 도구다. "나머지만 공개하면 안전하겠지"라는 직관은, 모듈러들의 곱이 원본보다 큰 순간 무너진다.

정보를 조각내 흘려도, 조각이 충분하면 복원된다.

각각의 ci는 flag의 일부 정보에 불과해 보인다. 하지만 서로소인 모듈러로 얻은 나머지들은 겹치지 않는 정보라, 곱이 원본을 덮을 만큼 모이면 완전히 재구성된다. 값을 진짜로 숨기려면 나머지 개수·크기를 원본보다 작게 유지하거나(정보를 부족하게), 애초에 나머지가 아니라 되돌릴 수 없는 형태로 감춰야 한다.