-
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라고 불리는...
-
Knuth's Algorithm X
안녕하세요? 오늘은 Knuth’s Algorithm X에 대해 알아보도록 하겠습니다. Knuth’s Algorithm X는 기본적으로 Brute-Force 알고리즘의 일종이지만, 성능이 좋은 편에 속하고 그 과정이 상당히 아름답습니다. Knuth’s Algorithm X Knuth’s Algorithm X는 간단히 말해, 어떠한 집합의 exact cover를 찾는 알고리즘입니다. Exact cover란 무엇인지, 간단한 예시를 통해 살펴보도록 하겠습니다. 집합 X = {1, 2, 3, 4, 5, 6, 7}이 있고, 집합 X의 부분집합의 집합인 집합 S가 주어집니다. S = {A, B, C, D, E, F}라고 하고 각각을 다음과 같이...
-
Effective Modern C++ (2)
저번시간에 이어서 오늘은 예전에 Effective Modern C++ 을 공부하며 정리했던 내용들을 포스팅해볼까 합니다~ C++11/14 에서의 best practice 에 관한 내용으로서 최근 C++20 이 나오는 시점에서 이 또한 최신 내용은 아니긴 하지만 여전히 많은 부분들이 유효합니다. Chapter 4. 똑똑한 포인터 (Smart Pointer) 항목 18. 소유권 독점 자원의 관리에는 std::unique_ptr를 사용하라. 보통 smart pointer를 처음 접한 사람들은 std::shared_ptr만을 남용(?)하는 경향이 있다.그러나 std::shared_ptr이 매우 강력한 존재이긴 하지만 크게 2가지 측면에서 단점이 있다. 첫 번째는 overhead이다. 참조 계수를 관리하기...
-
Cactus graph realization of degree sequence
Degree sequence 그래프에서, Degree sequence란 undirected graph의 각 정점의 차수(degree)를 늘어놓은 수열을 말한다. Graph realization problem이란, 수열이 주어졌을 때 그 수열을 degree sequence로 갖는 그래프를 실제로 construct하는 문제를 말한다. 여기서 다루는 그래프는 self-loop나 multiedge가 존재하지 않는 simple graph이다. 어떤 Degree sequence가 주어졌을 때, 이를 만족하는 simple graph가 존재할 조건은 Erdos - Gallai theorem 으로 널리 알려져 있다. 정리 1 (Erdos - Gallai theorem). $d_1 \ge d_2 \ge … \ge d_n \ge 0$ 가 finite simple...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 2)
동적 계획법을 최적화하는 9가지 방법 (Chapter 2) 이 글은 Chapter 1에서 계속된다. 4. Knuth’s Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할...