-
$O(N^{1/4 + ε})$ 시간 복잡도에 소인수 분해하기
$O(N^{1/4 + \epsilon})$ 시간 복잡도에 소인수 분해하기 소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 “어려운” 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다...
-
비트 연산을 활용하여 두 문자열의 LCS 빠르게 구하기
이 포스트에서는 두 문자열 $A[1..n]$, $B[1..m]$의 최장 공통 부분 수열(이하 LCS)을 $O(nm/w)$ 시간에 구하는 방법에 대해 서술합니다. Lloyd Allison, Trevor I. Dix의 A bit-string longest-common-subsequence algorithm을 보고 작성한 글입니다. 일반적으로 LCS를 구하는 방법 $T[i][j]$를 $A[1..i]$와 $B[1..j]$의 LCS 길이로 정의하면, 아래와 같은 점화식이 성립한다는 사실이 잘 알려져 있습니다. \[T[i][j] = \begin{cases} 0 & \text{if $i=0$ or $j=0$} \\ T[i-1][j-1]+1 & \text{if $A[i] = B[j]$} \\ \max(T[i-1][j],T[i][j-1])& \text{otherwise} \end{cases}\] $0 \le T[i][j] - T[i][j-1] \le 1$이므로, 새로운...
-
Shellcoding and Bitflip Conjecture
서론 이번에 DEF CON CTF 2019에 팀 SeoulPlusBadass로 다녀왔습니다. 결과 링크 대회의 대부분의 문제가 프로그램의 취약점을 찾아서 익스플로잇하는 Pwnable 문제였는데, 그렇지 않은 문제는 ropship, DOOOM, bitflip conjecture 세 문제였습니다. 그 중에서도 Bitflip Conjecture는 흥미로운 Shellcoding 문제여서 이번에 공유하고자 합니다. Bitflip Conjecture Bitflip Conjecture는 X64 Assembly로 작성된 Binary를 전송하는 문제입니다. 자세한 것은 문제에 접속하면 나오는 메시지를 살펴봅시다: =============================================================================== Definition: A snippet of assembly code is `N-Flip Resistant` if its output remains constant (i.e., it produces the...
-
Suffix Automaton 구현과 그 응용
목차 1. 개요 2. 구현 3. 응용 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 이번 포스트에서 살짝 양심고백을 한다면, 원리를 100% 이해하지 못하고 그 구현과 구현체만을 응용하는 것을 다루는 것을 리뷰하려고 합니다. Suffix Automaton의 구현과 동작이 모두 $O(N)$에 이루어지기 때문에 그 효율성 때문에 사용만 가능하다면 매우 유용할 것 입니다. Suffix Automaton의 원리를 전부 이해하고 구현한다면 참 좋겠지만, 아직 몇가지 소정리에 대해서 더 공부해야 이해가 제대로 될 것 같아서 구현방법만 집중적으로 설명하고, 응용에...
-
Linear Feedback Shift Register
안녕하세요, 이번 글에서는 Linear Feedback Shift Register에 대해 알아보도록 하겠습니다. Linear Feedback Shift Register Linear Feedback Shift Register(a.k.a LFSR)는 현재 상태에서의 선형 연산을 통해 다음 상태를 생성하는 레지스터입니다. 예를 들어 상태는 4비트이고 다음 입력값은 1-indexed 기준 4번째 비트와 3번째 비트의 XOR으로 생성된다고 해봅시다. 만약 현재 상태가 1011일 경우 $1 \oplus 1 = 0$이기에 다음 입력값은 0이고, 다음 상태는 0101이 됩니다. 그 다음 입력값은 $0 \oplus 1 = 1$이고, 다음 상태는 1010입니다. 아래의 그림을 참고해보세요. 4번째...