-
TLS 1.3 프로토콜
1. Introduction 8월 16일 오후 3시부터 24시간동안 삼성에서 열린 SCTF에 DecryptTLS라는 이름의 TLS 관련 문제가 출제되었습니다. 해당 문제에서는 구글 웹사이트와 통신한 TLS 패킷파일이 제공되어서 해당 파일로부터 플래그를 알아내야 했습니다. 문제에 들어있던 암호학적 취약점 자체는 그렇게 복잡하지는 않았지만 정작 프로토콜의 Specification을 보고 데이터를 추출하는데에 rkm0959님과 같이 아주 긴 시간동안 고통을 받았습니다. 그래도 그 과정에서 TLS 1.3 버전에 대한 공부를 할 수 있었어서 TLS 1.3에 대한 포스팅을 작성하고자 합니다. 2. TLS 옛날 옛적에는 웹서버와 통신을 할 때...
-
와일드카드 문자열 매칭
서론 문자열 매칭 알고리즘은, 문자열 $S$와 $T$가 주어졌을 때, $S$의 부분문자열(substring) 중에 $T$가 어느 위치에 등장하는지 찾는데 사용하는 알고리즘이다. 우리는 이 문자열 매칭 알고리즘에 와일드카드 문자, 즉, 어떤 문자에도 대응 될 수 있는 ? 문자가 들어갔을 때 어떤 식으로 문제를 해결해야 하는지 알아본다. ? 문자가 들어가지 않았을 때 문자열 매칭을 하는 법에 대해서는, KMP 알고리즘과 Aho-Corasick 알고리즘 문서에 잘 설명이 되어 있으니, 참고하면 된다. 문제 우리가 풀고 싶은 문제는 다음과 같다. 문자열 길이 $N$의 문자열...
-
Python 3의 문자열 fastsearch 기법들
개요 Python 3는 내장된 수많은 기능을 통해 사용자에게 편의성을 제공합니다. 여기에는 문자열 자료형인 str과 관련 라이브러리들이 포함되는데, 대부분의 기능이 언어 자체에 내장되어 일반 리스트처럼 대괄호를 사용한 인덱스 접근도 가능하고, ‘문자’와 ‘문자열’의 구분도 없으며, 널 문자같은 귀찮은 요소도 신경쓰지 않아도 되고 마음대로 인덱스를 지정해 잘라내거나(slicing) + 연산자로 이어붙이고 심지어는 * 연산자로 반복까지 할 수 있는 등 만능의 성격을 갖추고 있습니다. 이처럼 높은 접근성을 고려한 구현은 CPython의 문자열 구현체에서도 드러나는데, 문자열 내에서 문자열을 검색하기 위한 find 기능이...
-
APIO 2021
APIO 2021 APIO 2021은 아시아 태평양 학생들을 대상으로 진행되는 정보 올림피아드 대회로, 국제 정보 올림피아드 (IOI) 바로 다음 순위의 권위와 중요성을 가진 국제 대회이다. 조금 늦기는 했지만 아직 APIO 2021의 문제들을 완전히 풀이한 글이 없어서 풀이를 작성한다. 문제 풀이 한 줄 요약 육각형 영역: 다각형 내부의 모든 격자점 간의 거리 합을 구하는 문제로 환원할 수 있다. 다각형의 3개의 축을 분리하여 생각하면, 각 축에 대해서 삼각분할과 비슷한 일종의 트리를 형성할 수 있고, 모든 경로가 이 트리...
-
An Automatic System to Detect Equivalence Between Iterative Algorithms
논문 링크 : https://arxiv.org/abs/2105.04684 논문 저자 : Shipu Zhao, Laurent Lessard, Madeleine Udell Introduction : Optimization Algorithms and Their Equivalence 수학적 최적화에는 문제를 해결하기 위한 다양한 알고리즘이 있습니다. 각 알고리즘은 그 형태를 통해서 우리에게 최적화에 대한 직관을 주기도 하고 훌륭한 성능으로 우리가 최적화 문제를 어떻게 해결할 수 있는지 알려줍니다. 이는 이미 작성했던 여러 글에서도 강조했던 내용입니다. 예를 들어, 단순히 smooth differentiable convex function $f$를 최소화하는 문제에는 여러 알고리즘이 있고, 특히 Accelerated Gradient Method를 기반으로 하는...