#number-theory

RSA 문제인데 공개된 값이 딱 하나, 개인키 d뿐이다. 공개키 n도, 지수 e도, 암호문도 없다. 그런데 flag 자체가 RSA의 소수 p로 그대로 쓰였다는 걸 알면 이야기가 달라진다. e·d - 1 이 (p-1)(q-1)의 배수라는 사실 하나만으로, n을 몰라도 이 숫자 하나를 완전히 소인수분해해서 p와 q를 통째로 되감을 수 있다. SageMath로 410비트 숫자를 끝까지 쪼갠 뒤, 그 조각들을 어떻게 나누면 진짜 소수 두 개가 나오는지 전수탐색으로 찾아냈다.

평문을 두 키의 거듭제곱 차이에 곱해 암호문 하나로 내보내는 crypto 문제. 키가 두 개지만 하나는 공개되고 다른 하나는 좁은 범위라, 암호문이 정수로 떨어지는 키를 전수조사하면 평문 정수 p가 그대로 복원된다. 그 p 자체가 플래그이며, ord 값을 이어 붙인 형태라 사람이 읽을 수도 있다.

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