BLOG2026-07-23
![[🥈 Silver 4] e 가 (p-1) 을 나누는 RSA — AMM 으로 e차근 구하기 — DreamHack special_rsa_parameter 풀이](/images/blog/dreamhack-special-rsa-parameter-writeup/thumbnail.png)
blog
[🥈 Silver 4] e 가 (p-1) 을 나누는 RSA — AMM 으로 e차근 구하기 — DreamHack special_rsa_parameter 풀이
공개지수 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.
#dreamhack#ctf#crypto+6