https://www.acmicpc.net/problem/16436

요새 감이 다 죽었는지 풀이가 전혀 떠오르지 않아 고생하다가 jh05013님의 풀이(http://jh05013.blog.me/221410114048) 를 보고 알아냈습니다. 이건 몰랐네여,,,,

https://github.com/blisstoner/BOJ/blob/master/16436.cpp

https://www.acmicpc.net/problem/16471

Greedy하게 생각해보면 나는 제일 작은 수부터 $(N+1)/2$개를 내고 상대는 $N/2$번째 수부터 쭉 낼 때 모든 경기를 이길 수 있어야 함을 알 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/16471.cpp

잘 안풀려서 좀 아쉬웠다. chainedrsa에서 팀원이 phi 대신 carmichael function임을 알아낸 후에 소인수분해를 해줘서 무려 퍼블을 먹었는데 tania랑 asrybab가 안풀리더라..

asrybab의 경우 일단 d에 곱해지는 소수를 정하고 나면 boneh durfee로 인수분해가 가능한데 소수 1개당 대략 1-2분정도 걸리기 때문에 컴퓨터 50대를 동시에 쓰는게 아니고서야 풀이가 불가능하고 Wiener's attack의 varient로 어떻게 해보려고 했는데 마찬가지로 잘 안되고..

tania는 k의 앞 60비트가 0임을 이용한 공격인건 알겠는데 lattice에 대해 잘 모르니 대회 직전까지도 되게 삽질을 하다가 끝났다. 내가 만든 데이터에 대해서는 secret key가 복원되던데 서버에서 보내주는 r, s를 가지고는 잘 안되서 좀 아쉬웠다.

두 문제 다 풀이가 궁금하다ㅎㅎ 풀다보니 lattice에 대해 좀 잘 이해할 필요가 있다는 느낌을 받았다.

그래도 확실히 CTF를 하는게 재밌다. 다같이 협력하면서 풀어내고 구석에서 쪽잠자고 그런거 하나하나가 재밌었다. 뛰어난 분들 보는 것도 신기했고.

대회를 참여하면 참여할수록 동기부여도 되고 공부해야할 것도 마구 생긴다!!