이산 로그 문제

Discrete Logarithm Problem

이항 연산자 $\;\circ$ 에 대해 닫혀 있고, 결합 법칙, 항등원, 역원을 만족하는 집합

1. 닫힘: $\forall\; a, b \in G, a \circ b \in G$
2. 결합 법칙: $\forall\; a, b, c \in G, (a \circ b) \circ c = a \circ (b \circ c)$
3. 항등원: $\exists\;s e \in G, \forall\; a \in G, a \circ e = e \circ a = a$
4. 역원: $\forall\; a \in G, \exists\; a^{-1} \in G, a \circ a^{-1} = a^{-1} \circ a = e$
5. 교환 법칙(abelian): $\forall\; a, b \in G, a \circ b = b \circ a \rightarrow$
   아벨 군

군 $G$의 부분집합 $H$가 군이 되기 위한 조건

• $(\mathbb{Z}, +)$, $(\mathbb{Q}, +)$, $(\mathbb{R}, +)$, $(\mathbb{C}, +)$: 아벨 군
  • $(\mathbb{Z}, +)$는 $(\mathbb{Q}, +)$의 부분군이다.
• $(\mathbb{Q} \setminus \{0\}, \times)$, $(\mathbb{R} \setminus \{0\}, \times)$, $(\mathbb{C} \setminus \{0\}, \times)$: 아벨 군
• $(\mathbb{Z} \setminus \{0\}, \times)$: 군이 아니다 (역원이 존재하지 않음)
• 가역적인 2x2 행렬의 집합: 군이지만 아벨 군이 아니다 (행렬의 곱셈이 교환적이지 않음)

원소의 개수가 유한한 군

• $(\mathbb{Z}_n, +)$: 양의 정수 $n$에 대해 아벨 군 ($|\mathbb{Z}_n| = n$)
• $(\mathbb{Z}_n^*, \times)$: 양의 정수 $n$에 대해 아벨 군 ($|\mathbb{Z}_n^*| = \phi(n)$, 여기서 $\phi$는 오일러 파이 함수)

• 군은 항상 닫혀 있고,
  항등원
  과
  역원
  을 가진다.
• 군은
  결합 법칙
  을 만족한다.
• 군은
  교환 법칙
  을 만족하지 않을 수 있다.
• 군은
  부분군
  을 가질 수 있다.
• 군은
  유한 군
  일 수 있다.

$(\mathbb{G}, \circ)$가 군이고 $a \in \mathbb{G}$일 때, $a$의

원소차수(ord)

는 $a$를 반복해서 연산하여 항등원 $e$를 만들 때 필요한 최소 횟수이다.

• $3^1 = 3$
• $3^2 = 9$
• $3^3 = 27 = 5 \;(\text{mod}\; 11)$
• $3^4 = 15 = 4 \;(\text{mod}\; 11)$
• $3^5 = 12 = 1 \;(\text{mod}\; 11)$
• 따라서 $\text{ord}(3) = 5 \;\text{in}\; (\mathbb{Z}_{11}^*, \times)$

최대 차수 $\operatorname{ord}(g) = |\mathbb{G}|$를 가진 원소 $g$를 포함하는 군 $\mathbb{G}$를 순환 군이라고 한다. $g$를

발생자

또는

원시 원소

라고 부른다.

• $2^1 = 2$
• $2^2 = 4$
• $2^3 = 8$
• $2^4 = 16 \; (\text{mod} \; 11) = 5$
• $2^5 = 5 \times 2 = 10 \; (\text{mod} \; 11)$
• $2^6 = 10 \times 2 = 9 \; (\text{mod} \; 11)$
• $2^7 = 9 \times 2 = 7 \; (\text{mod} \; 11)$
• $2^8 = 7 \times 2 = 3 \; (\text{mod} \; 11)$
• $2^9 = 3 \times 2 = 6 \; (\text{mod} \; 11)$
• $2^{10} = 6 \times 2 = 1 \; (\text{mod} \; 11)$
• 따라서 $\text{ord}(2) = 10$, $|\mathbb{Z}_{11}^*|\; \& \;\mathbb{Z}_{11}^*$는 순환 군이다.

• 군 $\mathbb{G}$의 원소 $a$의
  원소차수
  는 $\mathbb{G}$의 원소 중 $a$를 반복해서 연산하여 항등원을 만들 때 필요한 최소 횟수이다.
• 순환 군은 최대 차수를 가진 원소(
  발생자
  or
  원시 원소
  )를 포함하는 군이다.
• 순환 군이 발생자를 가질 때, 그 발생자는 순환 군의 모든 원소를 생성할 수 있다.

군 $(\mathbb{G}, \times)$와 발생자 $g$가 주어졌을 때, $\mathbb{G}$의 원소 $A$에 대해 $A = g^a$를 만족하는 $a$를 찾는 문제이다.

• $\mathbb{Z}_{31}^*$에서 $g = 3$, $A = 20$일 때, $3^x \pmod{31} = 20$을 만족하는 $x$를 찾는 것은 쉬움
  • $3^1 = 3, 3^2 = 9, 3^3 = 27, 3^4 = 19, \cdots ,3^{8} = 20$
• $p$ 가 충분히 큰 소수일 경우 $\mathbb{Z}_p^*$ 에서 DLP는 어려운 문제

• $p$ 가 크지 않은 경우: 일반/특수 체 알고리즘 (GNF, SNF)
• $q$ 가 크지 않은 경우: 폴라드로 알고리즘 (Pollard's rho algorithm)

• 이산 로그 문제는 군 $\mathbb{G}$와 발생자 $g$가 주어졌을 때, $\mathbb{G}$의 원소 $A$에 대해 $A = g^a$를 만족하는 $a$를 찾는 문제이다.
• 이산 로그 문제는 실수 집합에서 로그를 계산하는 것과 달리 이산 세계에서는 어려운 문제이다.
• 이산 로그 문제는 $\mathbb{Z}_p^*$의 부분군 $\mathbb{G}$에서 정의된 DLP 해결법을 사용하여 해결할 수 있다.