-
컴퓨터 과학의 미해결 문제들
개요 수학에는 많은 난제들이 있습니다. 전세계적으로 유명한 밀레니엄 문제가 대표적입니다. 인지도 있고 학술적 가치가 높은 난제는 하나를 해결하는 것이 평생의 업적이 되기도 합니다. 많은 난제들이 꾸준히 풀리고 있지만, 새로운 문제가 창조되는 것에도 역시 끝이 없습니다. 난제의 범위를 컴퓨터 과학으로 좁혀봅시다. 대표적인 것으로는 밀레니엄 문제의 일부이기도 한 P-NP 문제가 있습니다. P-NP 문제는 너무나 유명해서 이 글을 읽을 사람이라면 누구나 한 번쯤은 들어보았을 것입니다. 하지만 그 외에 다른 컴퓨터 과학 난제는 그다지 널리 알려진 것이 없는 것...
-
2021 ICPC Seoul Regional
2021 ICPC Seoul Regional 이 글에서는 2021 ICPC Seoul Regional의 문제 풀이를 다룬다. 올해 문제는 예년 비해서 상당히 어렵게 출제된 편이다. 거의 모든 해에서 우승 팀이 모든 문제를 풀었고, 그렇지 않은 해 (2015, 2018 등) 에도 웬만하면 한 문제 빼고 다 풀었다는 점을 감안하면 상당히 이례적이다. 다만 모든 문제를 푸는 난이도는 솔직히 2018년이 더 어렵지 않나 싶다. 솔직히 말해서 문제가 자꾸 봤던 유형에서 계속 재탕 삼탕하는 느낌이 너무 강하다. 어느 정도야 그럴 수 있겠지만 올해는...
-
Wireless Digital Communication 5
서론 지난 글에서는 ISI와 Nyquist criterion에 대해 설명을 했습니다. 지난 글까지 잘 따라오셨다면 OFDM을 공부하기 위한 기초적인 지식을 다 공부한 것입니다. 이번 글과 다음 글, 두 번에 걸쳐 OFDM에 대한 내용을 다룰 예정입니다. 이번 글에서는 OFDM이란 무엇인가, 그리고 DFT/IDFT와 어떤 관계가 있는가에 대해서 다룰 예정입니다. 본론 OFDM은 Orthogonal Frequency Division Multiplexting의 약자로, FDM은 FDM인데 신호들을 Orthogonal 하게 중첩시켜 Bandwidth를 절반 정도로 줄인 기법을 의미합니다. FDM은 어떤 주파수 대역을 겹치지 않는 하부 대역으로 나눠 분리된 대역을...
-
Smart Contract Vulnerabilities
서론 최근 스마트 컨트랙트 보안에 대해 공부하게 되었습니다. 블록체인 위에 있는 여러 스마트 컨트랙트들은 대부분 NFT나 ERC20 토큰, 또는 ETH, AVAX 등 블록체인 위의 기초 화폐를 다루는 만큼 그 보안이 매우 중요하게 여겨지고 있습니다. DeFi (Decentralized Finance, 탈중앙화 금융) 서비스를 개발하는 회사들은 여러 보안 전문 회사에 Security Audit을 받으면서 보안성을 강화하려고 하지만, 모든 실수를 완벽하게 막을 수는 없기 때문에 여러 해킹사건이 발생하고는 합니다. 이 글에서는 스마트 컨트랙트 위에서 발생하는 공격들에 몇 가지에 대해서 간략하게 알아보도록...
-
Breaking Combined Multiple Recursive Generators
서론 10월 중에 제가 속한 CTF 팀 perfect blue에서 pbctf 2021을 주최했습니다. CTF를 준비하면서 다양한 암호학 논문들을 읽어보았는데, 그 중에서도 참고할만한 흥미로운 공격이 있어서 Yet Another PRNG라는 문제로 작성하게 되었습니다. 해당 문제는 CMRG(Combined Multiple Recursive Generator)라는 PRNG의 선형성을 공격하는 문제로, 이 논문의 5절에서 공격의 원형을 살펴볼 수 있습니다. 본론 CMRG CMRG는 2개의 LCG를 혼합한 형태입니다. 서로소인 $m1, m2$가 존재할 때, $x_i = a_{11} x_{i-1} + a_{12}x_{i-2} + a_{13} x_{i-3} \mod m_1$ $y_i = a_{21} y_{i-1}...