-
블루투스의 취약점들
1. Introduction 블루투스는 수많은 기기들이 근거리 통신을 위해 사용하는 프로토콜입니다. 컴퓨터와 연관이 있는 키보드, 마우스, 스피커 등의 입출력장치는 물론이고 심장박동수 측정 기기와 같은 의료기기들도 무선으로 정보를 송/수신해야할 필요가 있을 경우 블루투스를 사용합니다. 블루투스 통신에서 오가는 정보는 반드시 기밀이 유지되어야 하고 송/수신자가 아닌 외부의 공격자가 내용을 감청하거나 변조하는 일이 없어야 합니다. 그렇기 때문에 블루투스의 통신 규약을 보면 내용은 암호화가 되고 다양한 공격들에 대한 대비책을 미리 마련해두고 있습니다. 그러나 현존하는 모든 시스템이 그러하듯 블루투스 프로토콜도 다양한 취약점이...
-
Error-bounded Piecewise Linear Representation
안녕하세요? 오늘은 주어진 데이터를 여러 개의 선형 방정식으로 근사하되, 모든 점들마다 최대 오차가 $\delta$ 이하로 bound되도록 하는 Error-bounded Piecewise Linear Representation를 구하는 방법에 대해 알아보겠습니다. 이 글의 내용은 2014년 발표된 논문인 Maximum error-bounded Piecewise Linear Representation for online stream approximation을 참고하였습니다. PLR이란? Piecewise Linear Representation(PLR)은 주어진 데이터를 구간마다 여러 개의 선형 방정식으로 근사하는 방법입니다. PLR을 사용하면 얻을 수 있는 이점은 데이터의 절약입니다. 위 Fig 1는 총 11개의 데이터를 포함하고 있지만, 해당 데이터를 3개의 선으로 근사한다면...
-
동적 계획법 모델화하기
서론 세상에는 수없이 많은 알고리즘 문제가 있습니다. 그러나 새로운 문제를 볼 때마다 항상 지금껏 보지 못한 새로운 기법을 사용해야 하는 것은 아닙니다. 문제의 특성을 파악하고, 조건들을 이용하여 자신이 아는 문제로 변환한 뒤, 이전에 다른 문제를 풀 때 사용했던 기법을 비슷하게 적용하여 풀 수 있기도 합니다. 이처럼 많은 문제는 몇 가지 정해진 전형적인 형태로 모델화 되는 경우가 많습니다. 반면에 큰 알고리즘 분류 중에 많은 사람들이 처음 접할 때 큰 벽을 느끼는 분야가 있습니다. 바로 동적 계획법(dynamic...
-
SVP and CVP
서론 이번에 N1CTF에 Super Guesser 팀으로 참전해서 4등을 차지했습니다. (ctftime) 한국의 강력한 crypto hacker rkm0959님과 함께 할 수 있는 좋은 자리였는데요, N1CTF에 나온 한 문제가 SVP(Shortest Vector Problem)과 CVP(Closest Vector Problem)에 대해서 다루기 좋아서 이번에 이렇게 글을 작성하게 되었습니다. 본론 Lattice 우선 SVP와 CVP에 대해서 살펴보기 전에 Lattice에 대해서 알아봐야 합니다. Lattice는 이름에서 알 수 있듯이 격자 형태를 나타내는 수학적 개념입니다. Lattice는 서로 independent한 vector ${v_1, v_2, \ldots v_n}$이 있을 때 다음과 같은 집합을 의미합니다....
-
IOI 2020
IOI 2020 IOI 2020 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 최은수, 100 / 100 / 100 / 100 / 93.00 / 100, 593.00점, 2등 (금메달) 송준혁, 75 / 100 / 100 / 100 / 92.62 / 65.32, 532.94점, 12등 (금메달) 임성재, 44 / 100 / 41 / 100 / 92.24 / 100, 477.24점, 30등 (은메달) 반딧불, 32 / 100 / 53 / 21 / 80.14 / 100, 386.14점, 61등 (은메달) 올해 한국 학생들의...