Discrete Logarithm Problem

1. Group(군)

- 집합 G와 이항연산 ◦ 로 구성된 구조로, 다음 네 가지 조건을 만족해야 함

 1) 닫힘성: a, b ∈ G라면, a ◦ b도 반드시 G에 있어야 함(예를들어 정수 집합 Z에서 +연산을 하면 항상 정수가 나옴)

 2) 결합법칙: a, b, c ∈ G일 때, (a ◦ b) ◦ c = a ◦ (b ◦ c) 만족

 3) 항등원 존재: 어떤 a ∈ G에 대해서도, a ◦ id = a를 만족하는 id ∈ G가 있어야 함

 4) 역원 존재: 각 a ∈ G에 대해, a ◦ a⁻¹ = id를 만족하는 a⁻¹ ∈ G가 있어야 함

- Abelian Group(아벨 군) : a ◦ b = b ◦ a (연산의 순서가 바뀌어도 결과가 같음)을 만족

- Subgroup(부분군) : (H, ◦)가 (G, ◦)의 부분군이 되려면, H는 G의 부분집합이고, 그 자체로도 하나의 군이어야 함

- 2x2 가역 행렬들의 집합도 군. 하지만 아벨군은 아님

- Zn*: n 과 서로소인 정수들의 집합

 

 

2. Order of an Element (원소의 차수)

- 군 (G,∘)의 원소 a의 차수 ord(a)는 a∘a∘⋯∘a=1 (k번 연산해서 항등원 1이 나오는 최소의 양의 정수 k)

- 예를들어 ( Z11*, x)에서 3의 차수 구하는 방법 :

 

 

3. Cyclic Group

- 군 G 안에 어떤 원소 g가 있을 때, g를 계속 곱해서 군의 모든 원소를 만들 수 있어야 함

- ord(g) = |G|를 만족하면 사이클릭 군

- 이때 g를 generator 또는 primitive element라 부름

- 예를들어 Z11*은 사이클릭 군

 

 

4. Discrete Logarithm Problem(이산 로그 문제)

- 군 (G,x)와 생성자 g, 원소 A∈G가 주어졌을 때 g^a = A를 만족하는 a를 찾아라.

- log(g)​A = a로 풀 수 있지만 정수(mod p) 세계에서는 계산이 어려움

- 예를들어 Z31*에서 g=3, A=20 일 때 a를 찾기

- 즉 3^a (mod 31) = 20이 되는 a를 찾기

- 해킹 시도로부터 안전하려면 적절한 크기의 파라미터를 사용해야 함

- Number Field Sieve: p가 작을 때의 공격

- Pollard rho 알고리즘: q가 작을 때의 공격

 

- Parameter Generation

  1) Select a (2λ)-bit prime q : 목표 보안 수준 λ에 대해, 그 2배 크기의 소수 q를 선택

  2) Select a random l, then compute p = 2lq+1

  3) P가 소수인지 확인하고 아니면 1번 혹은 2번으로 돌아가 다시 생성

  4) Zp*안의 원소 g를 랜덤으로 선택

  5) g := g^((p−1)/q) mod p. 만약 g=1이면 4번에서 다시 선택. 

  6) 최종 결과 : (q, p, g)