-
Erdös-Ginzburg-Ziv 정리의 O(n log n) 시간 해법 찾기
Erdös-Ginzburg-Ziv 정리는 임의의 길이 $2n-1$의 정수열에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. 이전에 작성된 글에서는 $O(n^2/w)$ 풀이를 소개했지만, 최근에 공개된 이 부분수열을 직접 찾는 $\mathcal{O}(n \log n)$ 풀이에 대해서 소개합니다. Erdös-Ginzburg-Ziv 정리와 증명 Erdös-Ginzburg-Ziv 정리는 길이가 $2n-1$인 임의의 정수열 $A = { {a}_1, {a}_2, \cdots, {a}_{2n-1}}$에 대해 길이가 $n$이고 원소의 합이 $n$의 배수인 부분수열이 항상 존재한다는 정리입니다. $A$에 따른 $A$의 부분수열을 Erdös-Ginzburg-Ziv 정리의 해법이라고 부릅니다. Erdös-Ginzburg-Ziv가 간단한 증명을 제시했고, 이...
-
Erdös-Ginzburg-Ziv 정리
서론 0과 1이 $X$개 있을 때, 그 중 항상 같은 수가 $N$개 이상 있게 하는 최소의 $X$는 $2N-1$이다. $X=2N-2$인 경우에는, 0과 1이 $N-1$개 존재하면 불가능하다. $X = 2N-1$개 있을 때는, 비둘기집의 원리에 의해서 항상 0이 $N$개 혹은 1이 $N$개 존재한다. 우리는 이 비둘기집의 원리의 일반화된 버전을 생각해 본다. 임의의 정수가 $X$개 있을 때, 그 중 합이 $N$의 배수가 되는 $N$개를 고를 수 있는 최소의 $X$는 얼마인가? 수로 0과 1만 가능한 것이 아니라, 모든 정수가 가능하다....
-
Forgery Attack on ElGamal Signatures
서론 최근에 한 문제에 대한 질문을 받았습니다. FuzzyLand라는 사이트의 WebShop 2.0 이라는 문제로, ElGamal signature 에 대한 공격을 요구하는 문제였습니다. 문제를 풀다보니 아이디어가 흥미로워서 공유하게 되었습니다. 본론 ElGamal Signatures ElGamal signature는 RSA signature와 비슷하게 discrete logarithm의 어려움에 바탕을 둔 signature scheme입니다. ElGamal signature는 다음과 같은 방식으로 돌아갑니다. 파라미터 및 생성 어떤 $N$-bit 소수 $p$를 고릅니다. 그리고 Hash function $H$를 고릅니다. 2부터 $p-1$ 사이의 어떤 수 $g$를 고릅니다. 이 수를 generator라고 부릅니다. 이 때 generator라고 불리는...
-
On Factoring Given Any Bits
서론 이번에 Belluminar 라고 하는 대회에 참가했습니다. 해당 대회는 각 팀마다 문제를 두 개 씩 출제하고, 대회 시간 동안 문제를 풀면서 점수를 겨루는 방식으로 구성되어 있습니다. 저는 이번에 공부했던 테크닉을 문제로 내기로 결심해서 작성을 했는데, 생각보다 만족스러운 퀄리티로 문제가 나오지 않아 아쉬웠습니다. 본래라면 공부한 내용을 포스트로 바로 쓰겠지만, 제 이름이나 아이디를 검색해 그대로 솔버에 사용하는 것을 원치 않았기 때문에 이러한 소셜 해킹을 방지하기 위해서 이제서야 포스팅을 하게 되었습니다. 이번 포스트는 제가 냈던 문제의 근간이 되는...
-
Smooth number and Factorization
서론 이번 HITCON CTF 2019 Quals에서 안타깝게 14등으로 본선을 진출하지 못하게 되었습니다. 결과 링크 아쉬운 부분은 푼 팀이 적은 암호학 문제들을 풀지 못했다는 건데, 그 중 한 문제가 소인수분해와 관련이 있어 이번 포스팅을 작성하게 되었습니다. RSA 위에서 말한 문제는 Lost Key Again이라는, RSA와 관련된 문제입니다. RSA에 대해서 간편하게 살펴보자면, $a \equiv b (\mathbb{mod}\ c)$는 $a$를 $c$로 나눈 나머지와 $b$를 $c$로 나눈 나머지가 같다는 뜻으로 이해할 수 있습니다. 편의상 $a$를 $b$로 나눈 나머지를 $a (\mathbb{mod}\ b)$로...
-
$O(N^{1/4 + ε})$ 시간 복잡도에 소인수 분해하기
$O(N^{1/4 + \epsilon})$ 시간 복잡도에 소인수 분해하기 소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 “어려운” 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다...
-
Digital Signature and Nonce Reuse
서론 Digital signature, 혹은 디지털 서명은 컴퓨터 네트워크에서 빠져서는 안 될 중요한 요소 중 하나이다. 수신자는 발신자로부터 메시지를 수신한 뒤, 메시지에 같이 붙어 온 digital signature를 검증해 해당 메시지가 정말로 발신자로부터 온 것인지 확인할 수 있다. 이를 보장할 수 있는 근간에는 다양한 수학 이론이 깔려있고, 이 중 중심이 되는 것은 정수론과 타원 곡선이라고 할 수 있다. 오늘 이 포스트에서는 이 중에서도 가장 쉽게 이해할 수 있고 널리 쓰이고 있는 DSA에 대해서 알아보고, nonce reuse가 왜...
-
Prime Number
목차 1. 개요 2. 개념 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학교 고급 알고리즘 시간에 Miller–Rabin Algorithm 에 대해서 공부하게 되었다. 매우 흥미로운 내용이 많았으며, 다른 사람들과 공유하면 좋겠다고 생각하여 소인수 분해 알고리즘 등의 다양한 알고리즘을 알게 된것을 포함하여 공유하고 싶어졌다. 이번 포스트에서는 그 알고리즘들의 구현과 실제 문제에 대해 어떻게 사용되는지 소개하고자 한다. 기본 지식 일단 최소한 Modulo Operation, 즉, 나머지 연산에 대해서 조금 설명할 필요가 있다. Mod 연산은...