System32.kr [RSA107] 풀이

System32.kr

RSA107 풀이

 

간만에 system32.kr 문제를 풀었다.

 

보면 모듈러 n 중간에 많은 0이 특징이다.

 

 

rsa 문제 풀이들을 찾아보다가

 

ctftime.org/writeup/22977

CTFtime.org / Crypto CTF 2020 / Decent RSA / Writeup

이런 풀이인가 싶었는데, 여기 풀이는 n값이 대부분 0으로 구성되었을 때였다.

 

그러다가 포스트 하나를 찾았다.

party4bread.github.io/a-year-of-ctf-rsa/#pq%EC%97%90-0%EC%9D%B4-%EB%A7%8E%EC%9D%84-%EA%B2%BD%EC%9A%B0

A year of CTF RSA | Haven 4 BREAD

오 출제자님 블로그

 

 

1234..00000000...1234 이런 식으로 구성되어 있으면 p나 q중에 하나는 100000...00 + z 형태를 취하고 있을 가능성이 높다.

 

따라서 n값을 0000...000을 기준으로 큰 부분을 a로 두고

작은 부분을 b로 두어 b/a를 계산하였더니 나누어 떨어졌다.

 

p = 1000...0000 + 961

이렇게 p와 q를 구할 수 있다.