-
cracking mysql_hash_password
Intro 안녕하세요, kwoncycle입니다. 이번 글에서는 mysql_hash_password 라는 해시 함수를 crack하는 방법에 대해 다룹니다. mysql_hash_password 함수는 2000년 이전에 MySQL에서 사용된 비밀번호 해시 함수로, 해시 로직은 아래의 코드와 같습니다. def mysql_hash_password(password): nr = 1345345333 add = 7 nr2 = 0x12345671 for c in password: if c == 32 or c == 9: continue nr ^= (((nr & 63) + add) * c) + (nr << 8) & 0xFFFFFFFF nr2 = (nr2 + ((nr2 << 8) ^ nr))...
-
TFHE : Fully Homomorphic Encryption over the Torus - 2
Introduction 안녕하세요. 지난 게시글에서는 동형암호 scheme중 하나인 TFHE의 암호화 / 복호화 / 덧셈 연산에 대해서 다루었습니다. 그리고 다음 게시글에서는 TFHE의 곱셈에 대해 다루기 위해서 GSW scheme과 gadget decomposition을 다루었는데요, 이 글의 이해를 위해서는 두 게시글을 읽고 오시길 추천드립니다! 이번 글에서는 TFHE에서의 곱셈(external product)가 어떻게 진행되는지와, 그리고 이러한 연산을 통해서 최종적으로 TFHE의 bootstrapping이 어떤 식으로 진행되는지에 대한 개괄적 설명을 하고자 합니다! TFHE Multiplication(External Product) Gadget Decomposition Gadget decomposition을 처음 접하시는 분은 이 글 의 설명을 읽으신다면...
-
Block Decomposition을 이용한 Online FFT 구현
Introduction 이 글에서는 Block Decomposition을 이용한 Online FFT(Fast Fourier Transform) 구현 방법을 소개합니다. 두 수열 $A$, $B$의 convolution $C$를 $\mathcal{O}(n\log n)$에 구하는 FFT 알고리즘은 두 수열 $A$, $B$가 모두 주어져야만 사용할 수 있습니다. Online FFT는 $A$, $B$의 원소 $a_i$, $b_i$가 하나씩 주어질 때 $c_i$를 온라인으로 구하는 알고리즘입니다. 이는 점화식이 convolution 형태이면서 $c_0, \cdots, c_{i-1}$을 알아야 $a_i$, $b_i$를 구할 수 있는 경우(예를 들면 카탈란 수 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$)에 사용할 수 있습니다. Online FFT는 여러...
-
Custom Select Box 만들기 (overflow 문제 해결) - (Nuxt3, Vue3)
Intro 안녕하세요. 이번 글에서는 Nuxt3에서 Custom Select Box를 구현해보려고 합니다. 이때, overflow를 허용하는 Component 내부에 존재하는 Custom Select Box에 대해 생기는 스크롤 문제를 해결하는 것이 이 글의 목표입니다. 명확한 해결책을 제시해 주는 곳이 없어 이를 해결할 수 있는 방법을 공유하고자 합니다. 또한, Select Box 외에도 Tooltip과 같이 특정 컴포넌트가 position: absolute인 상태로 상대 위치를 계산해야 하는 상황에서도 동일한 방법으로 해결할 수 있습니다. Nuxt3로 작성된 글이긴 하지만, javascript 기반으로 작동하는 여러 트릭이 많아서 굳이 Nuxt3를 몰라도,...
-
LCS 알고리즘 최적화
개요 LCS(Longest Common Subsequence) 문제는 두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 문제로, 컴퓨터과학에서 가장 고전적이면서 중요한 문제 중 하나입니다. 이 글에서는 이 문제를 해결하는 간단한 Dynamic Programming 해법부터, 이것의 공간 복잡도를 개선한 Hirschberg 알고리즘과, 일반적인 문자열에서 더 효율적인 Hunt-Szymanski 알고리즘을 소개할 것입니다. 그리고 이들을 비트 집합을 이용해 더욱 최적화하는 방법을 다룰 것입니다. 간단한 DP 해법 $DP[i][j]$를 $A$의 길이 $i$인 접두사와 $B$의 길이 $j$인 접두사의 LCS 길이로 정의하면 다음과 같은 점화식으로 $A$와...