-
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}...
-
알고리즘 문제 접근 과정 4
알고리즘 문제 접근 과정 4 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 줄 세우기 - KOI 2013 지역본선 중등부 4번 관찰 최소한의 이동이라는 조건이 없을 때에, 우리는 어떻게 줄을 세울 수 있을까요? 우리는 1번부터 N번까지의 학생을 모두 순서대로 뒤로 보내거나, N번부터 1번까지의 학생을 모두 앞으로...