#crt

800 미만 소수 139개마다 sorted([p % i, q % i]) 를 흘려 주는 2048비트 RSA 문제. 정렬 때문에 어느 쪽이 p 인지는 사라지지만 두 값의 합은 그대로 남는다. 139개 소수에서 (p+q) mod i 를 모아 CRT 로 p+q 를 복원하고, 이차방정식 근으로 N 을 분해했다.

공개지수 e=257 이 (p-1) 을 딱 한 번 나눈다. gcd(e, φ(N)) 이 1 이 아니라 d=e⁻¹ mod φ 가 존재하지 않아 평범한 RSA 복호가 막힌다. p·q 가 이미 주어졌으니 CRT 로 mod p / mod q 로 쪼갠 뒤, e차근이 유일한 mod q 는 그대로 풀고, e차근이 257개인 mod p 는 AMM(Adleman-Manders-Miller) 으로 전부 구해 CRT 로 다시 합친다. 257개 후보 중 BISC 로 시작하는 평문이 flag.

공개 지수 e 도 개인키 d 도 주지 않고 dp, dq, qinv 와 암호문만 주는 RSA-CRT 문제. 두 소수를 p = nextprime(q + 1) 로 만들어 사실상 연속 소수라, 2048비트 모듈러스인데도 Fermat 인수분해로 0스텝에 갈라진다. dp·dq·qinv 는 그 자체가 CRT 복호 파라미터라, 소인수만 알면 e·d 복원 없이 곧장 평문을 얻는다.

flag를 정수로 본 뒤 세 개의 420비트 소수로 나눈 나머지만 공개된 crypto 문제. 나머지 하나로는 flag가 소수보다 커서 복원되지 않지만, 서로소인 세 소수의 곱이 flag보다 크므로 중국인의 나머지 정리(CRT)로 세 합동식을 합치면 flag가 유일하게 결정된다. CRT로 정수를 복원해 바이트로 되돌렸다.