이산로그 편집하기

'''이산로그'''<!--이산 로그-->(discrete logarithms)는 일반 로그와 비슷하게 군론에서 정의된 연산으로, 1보다 큰 자연수 <math> a \ </math>, <math> \ m </math>
, 정수 <math> b \ </math> 에 대하여 방정식 <math> a^{x} \ = \ b </math> 만족하는 정수 <math> x \ </math>를 가리킨다. [[이산로그]]를 계산하는 다항식 시간(polynomial time) 알고리즘이 알려져 있지 않아 이산로그는 현대 암호에 응용되고 있다.<ref name="위키백과">〈[https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%82%B0_%EB%A1%9C%EA%B7%B8?action=edit 이산_로그]〉, 《위키백과》</ref> '''이산대수'''(離散對數)라고도 한다.<ref>로그(logarithm)를 대수(對數)라 부르기도 하므로, 이산대수와 이산로그는 같은 말이다.</ref>

== 개념 ==
<math> a^{x} \ = \ b </math> 일 때 <math> x \ = \ log_{a}b </math> 이다. 실수에서 <math> a \ , \ b </math>가 주어지고 <math> a^{x} \ = \ b </math>를 만족하는 <math> x \ </math>, 즉 <math> log_{a}b \ </math>를 간단하게 계산할 수 있다. 그러나 <math> Z_{p} </math>에서 주어진 <math> a \ , \ b </math>에 대해 <math> a^{x} \ = \ b </math>를 만족하는 <math> x \ </math>를 찾는 것이 바로 이산로그 문제이다. 이산 로그 문제에서 <math> p \ </math>는 [[소수]], <math> a \ </math>는 <math> p \ </math>의 [[원시근]]인 것이 좋다. <ref name="secmem"></ref>

이산대수의 역함수인 이산 거듭제곱은 효율적으로 계산할 수 있지만, 이산대수 계산은 어려운 것으로 알려진 군이 존재한다. (이산 거듭제곱의 경우 제곱을 여러번 반복해서 효율적으로 계산하는 방법등이 있다.) 일부 암호는 이런 비대칭성을 바탕으로 설계되기도 한다. 일반 이산대수를 구하는 문제는 일반 이산대수 문제(generalized discrete logarithm problem, 혹은 줄여서GDLP)라고 부르며, 현재까지 이에 대한 효율적인 알고리즘을 찾지 못하고 있다. 암호학에서 <math>G</math>는 보통 순환군 <math>{Z_p}^{*}</math>를 사용한다. 최근에는 유한체에서 정의된 [[타원 곡선]]의 순환 부분군을 암호에 적용하기 위해 많은 연구가 진행되고 있다.<ref name="꼬막"></ref>

이산대수의 가장 단순한 형태는 <math>{Z_p}^{*}</math>에서 정의하는 것이다. <math>{Z_p}^{*}</math>의 집합은 <math>\left\{ 1, 2, ... , p-1 \right\}</math>이고 소수 <math>p</math>를 법으로 가지는 모듈로 곱셈에 대하여 닫혀있다. 이 군에서 어떤 수의 <math>k</math> 제곱을 구하려면, 그 수를 <math>k</math>번 제곱한 다음 <math>p</math>로 나눈 나머지를 구하면 된다. 이런 연산을 [[이산 거듭제곱]](discrete exponentiation)이라고 한다.<ref name="꼬막">꼬막, 〈[http://blog.naver.com/PostView.nhn?blogId=komark7&logNo=40052038392&categoryNo=5&viewDate=&currentPage=1&listtype=0&from=postList 이산대수-위키]〉, 《네이버 블로그》, 2008-06-11</ref> 예를 들어, <math>{Z_7}^{*}</math>에서 <math>3^{5}</math>을 구하는 경우, <math>3^5=243</math> 이고 <math>243\div7</math>의 나머지가 <math>5</math>이므로 <math>{Z_7}^{*}</math>에서 <math>3^5=5</math>이다. 이산대수는 이산 거듭제곱의 역함수이다. 앞의 예제를 사용하여 설명하면, <math>3^k \equiv 5 \pmod{7}</math>일 때 이 조건을 만족시키는 가장 작은 <math>k</math>가 <math>{Z_7}^{*}</math>에서 밑이 <math>3</math>인 <math>5</math>의 이산대숫값이다. 이산로그문제(discrete logarithm problem)라고도 한다. 이산대수의 정의를 일반화하면, <math>G</math>가 <math>n</math>개의 원소를 가진 유한 순환군이라고 하자. 이 군은 곱셈군이라고 가정한다. <math>b</math>가 <math>G</math>의 생성원(primitive root, primitive element)이면 <math>G</math>의 모든 원소 <math>x</math>는 임의의 정수 <math>k</math>에 대하여 <math>x = b^{k}</math>의 형태로 쓸 수 있다. 또한 <math>x</math>를 표현하는 모든 원소들은 모듈로 n에 대해 합동이다. 이런 조건에서 다음과 같은 함수를 정의한다.
<math>\log _{b}:\ G\ \rightarrow \ \mathbf {Z}_{n}</math>

여기서 <math>Z_n</math>은 정수 <math>n</math>을 법으로 가지는 환이고 <math>x</math>에는 모듈로 <math>n</math>에 대한 congruence class를 할당한다. 이와 같은 [[군 동형사상]]을 밑이 <math>b</math>인 이산대수라고 부른다. 로그 함수의 밑변환은 이산대수에서도 그대로 적용된다. <math>c</math>가 <math>G</math>의 또다른 생성원이면, 다음 식이 성립한다.
<math>\log _{c}(x)=\log _{c}(b)\cdot \log _{b}(x).</math><ref>〈[https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%82%B0_%EB%A1%9C%EA%B7%B8 이산 로그]〉, 《위키백과》</ref>

== 특징 ==
아직까지 이산 로그 문제에 대한 효율적인 계산법은 나오지 않았다.(여기서 효율적인 계산법이라고 하는 것은 참고로 이산 로그 문제는 NP-complete에 속하는 문제는 아니기에 효율적인 계산법이 나올 가능성은 충분히 있다. 또한 Quantum Computer에서는 P에 속함이 증명되어 있다. 이산 로그는 Elgamal Encryption, Diffie-Hellman 키 교환, Digital Siganature Algorithm 등과 같이 암호화, 키 교환, 인증 등의 각종 암호 분야에서 쓰이고 있다. 만약 이산 로그 문제가 효율적으로 풀리게 된다면 위에서 언급한 암호 시스템이 안전하지 않게 된다. 또한, 비록 일반적인 이산 로그에 대한 풀이법 자체는 아직 찾지 못했다고 하더라도 a,b,p를 적절하게 택하지 못하는 구현의 실수로 인해 기밀성이 지켜지지 않는 경우도 있다. <ref name="secmem">〈[http://www.secmem.org/blog/2019/05/17/%EC%9D%B4%EC%82%B0-%EB%A1%9C%EA%B7%B8/ 이산-로그]〉, 《secmem》</ref>

; Safe Prime
Pohlig-Hellman Algorithm에서 볼 수 있듯 <math> p - 1 \ </math>의 소인수 중 그다지 큰 것이 없으면 이산 로그를 굉장히 쉽게 구할 수 있다. 이를 막기 위해 <math> p \ </math>를 safe prime으로 택하는 것이 좋다. safe prime은 <math> p \ = \ 2q + 1 </math> 꼴의 소수를 의미합니다.2048-bit의 safe prime을 택하기 위해서는 1024-bit의 prime <math> q \ </math>를 임의로 택한다. 그리고 <math> p \ = \ 2q + 1 </math> 이 소수인지 확인하는 방법으로 만들어낼 수 있다. <math> p \ = \ 2q + 1 </math>이 소수일 확률은 소수 정리에 의해 <math> 1 \ / \ ln(2q + 1) </math>에 근사하기 때문에 대략 2048개의 <math> q \ </math>를 잡으면 safe prime을 만들어낼 수 있다.<ref name="secmem"></ref>

===이산대수 문제===
이산대수 문제(Discrete Logarithm Problem, DLP)는 군(group)을 이용한다. 일반적으로 차수가 <math>t</math>인 집합 <math>G</math>의 원소 <math>g</math>와 집합 <math>G</math>의 다른 원소가 주어졌을 때 <math>x</math>를 구하는 것은 어려우며 이를 이산대수 문제(DLP: Discrete Logarithm Problem)라 한다. 여기서 <math>0 \le x \le t-1</math>이다. <math>y</math>는 <math>g</math>를 <math>x</math>번 곱한 결과이다. 원소 <math>g</math>는 전형적으로 <math>G</math>의 모든 원소들을 생성하거나 또는 적어도 <math>0</math>에서 <math>t-1</math>사이의 모든 정수들을 가지고 누승함으로서(즉, 반복적으로 그룹 연산을 함으로서)큰 부분집합을 생성할 수 있다. 원소 <math>g</math>가 군 내의 모든 원소들을 생성할 수 있다면 원소 <math>g</math>를 생성자(generator)라고 한다. 유한체의 이산대수문제는 유한체의 곱셈군에 대한 이산대수문제이다. 소인수분해 문제와 마찬가지로 이산대수 문제는 일방향 함수의 어려운 문제라 여겨지고 있다. 이러한 이유로 이산대수 문제는 [[엘가말]](ElGamal) 시스템과 DSS를 포함한 여러 공개키 암호 시스템들의 기초를 이루어 왔다. 이들 시스템들의 안전성은 이산대수를 계산하기가 어렵다는 가정에 의존하고 있다. 이산대수 문제는 유한체(finite fields)상에서 보다 임의의 군(group)상에서 훨씬 어려운 듯하다. 즉, 이것은 [[타원 곡선]](elliptic curve)군에 기초한 암호 시스템의 동기 부여이다.<ref>Fist1stPark, 〈[https://fistpark.tistory.com/entry/%EC%9C%A0%ED%95%9C%EC%B2%B4%EC%9D%98-%EC%9D%B4%EC%82%B0%EB%8C%80%EC%88%98 유한체의 이산대수]〉, 《티스토리》, 2009-04-03</ref>

== 알고리즘 ==
* '''전수조사'''
이 방법은 가장 떠올리기 쉽고 간단한 풀이법이다. 바로 <math> x \ </math>에 0부터 <math> p \ - \ 1 </math>까지 차례로 넣어보며 <math> a^{x} \ = \ b </math>를 만족하는 <math> x \ </math>를 찾는 것 이다. 아쉽게도 이 방식은 최악의 경우 <math> p \ </math>번의 곱셈이, 평균적으로는 <math> p \ / \ 2 </math>번의 곱셈이 필요하기 때문에 <math> p \ </math>가 1024 bit 혹은 2048 bit인 보통의 경우에서는 현실적인 시간 내에 풀이가 불가능하다.
 def func(a, b, p):
  val = 1
  for x in range(p):
    if val == b: return x
    val = val*a % p
  return -1

* '''Baby-step giant-step Algorithm (아기걸음 거인걸음)'''
알고리즘의 이름은 생소할 수 있지만 일종의 MITM(Meet In The Middle) 알고리즘으로, 이 알고리즘을 통해 시간복잡도를  <math> O(p) \ </math>에서  <math> O(p^{0.5}) \ </math>로 떨어 뜨릴 수 있다. 해쉬를 이용할 경우  <math> O(p^{0.5}) \ </math>, 정렬을 이용할 경우  <math> O(p^{0.5}lgp) \ </math>에 이산 로그 문제를 해결할 수 있다. 정렬을 이용한 예시 코드는 아래와 같다.
 def egcd(a1, a2):
  x1, x2 = 1, 0
  y1, y2 = 0, 1
  while a2:
    q = a1 // a2
    a1, a2 = a2, a1 - q * a2
    x1, x2 = x2, x1 - q * x2
    y1, y2 = y2, y1 - q * y2
  return (x1, y1, a1)
 def inv(a, m):
  x, y,g = egcd(a, m)
  if g != 1:
    raise Exception('No modular inverse')
  return x%m
 def func2(a, b, p):
  table1 = []
  k = int(p**0.5)
  val = 1
  mul = pow(a,k,p)
  for i in range(0,p,k):
    table1.append((val, i//k))
    val = val * mul % p
 table2 = []
  ainv = inv(a,p)
  val = b
  for i in range(k):
    table2.append((val, i))
    val = val * ainv % p
    table1.sort()
  table2.sort()
 idx1 = 0
  idx2 = 0
  while idx1 < len(table1) and idx2 < len(table2):
    if table1[idx1][0] < table2[idx2][0]:
      idx1 += 1
    elif table1[idx1][0] > table2[idx2][0]:
      idx2 += 1
    else:
      return k*table1[idx1][1]+table2[idx2][1]
  return -1

*'''Pollard’s rho Algorithm'''
Pollard’s rho Algorithm은  <math> a^{n_{1}}b^{m_{1}} \ = \ a^{n_{2}}b^{m_{2}} </math>인 적절한  <math> n_{1} \, \ n_{2}, \ m_{1}, m_{2} \ </math>를 찾았을 때  <math> log_{a}b \ = \ (n_{2} - n_{1})(m_{1} - m_{2})^{-1} </math>이라는 점을 이용하는 알고리즘 이다. 이 알고리즘의 시간복잡도는 <math> O(p^{0.5}) \ </math>입니다. 같은 시간복잡도를 가지는 Baby-step giant-step Algorithm과 비교할 때 이 알고리즘은 확률적 알고리즘이기 때문에 <math> O(p^{0.5}) \ </math>에 반드시 답이 찾아짐을 보장할 수 없고 상수가 약간 크다는 단점이 있지만, 공간을  <math> O(1) \ </math>만 사용한다는 아주 큰 장점이 있습니다. 이 알고리즘은 임의의 <math> a^{n}b^{m} \ </math> 꼴의 수들로 수열을 만들었을 때 해당 수열에서 cycle을 찾아내는 방식으로 동작합니다. 수열에서의 cycle은 Floyd’s cycle-finding algorithm으로 구할 수 있습니다. 알고리즘에 대해 간략하게 설명을 하자면, 한 번에 한 칸씩 가는 거북이와 두 칸씩 가는 토끼를 수열 상에서 이동시켜 거북이와 토끼가 같은 값에 위치하는 순간을 찾는 방법입니다.  <math> f(x) \ = \ a^{n}b^{m} </math>꼴의 수열을 만들기 위해 <math> x \ </math> 를 3으로 나눈 나머지에 따라 각각  <math> f(x + 1) \ = \ ax </math> 혹은 <math> f(x + 1) \ = \ bx </math> 혹은 <math> f(x + 1) \ = \ x^{k} </math>으로 계산합니다. 반드시 <math> ax \, \ bx, \ x^{k} </math>일 필요는 없고 <math> a^{2}x \, \ b^{2}x, \ ab^{2}x^{4} </math>등과 같이 <math> f(x + 1) \ </math>이 여전히 <math> \ a^{n}b^{m} </math>으로 잡아도 무관하다. 그 후 <math> f(x) \ </math>에 대해 앞서 소개한Floyd’s cycle-finding algorithm 으로 <math> a^{n_{1}}b^{m_{1}} \ = \ a^{n_{2}}b^{m_{2}} </math>를 만족하는 <math> n_{1} \, \ n_{2}, \ m_{1}, m_{2} \ </math>를 찾습니다. 만약  <math> m_{1} \ = \ m_{2} </math>일 경우는 탐색 실패 이므로 다른 초기 항을 잡아 같은 절차를 반복한다. 예시 코드는 아래이다.
 def egcd(a1, a2):
  x1, x2 = 1, 0
  y1, y2 = 0, 1
  while a2:
    q = a1 // a2
    a1, a2 = a2, a1 - q * a2
    x1, x2 = x2, x1 - q * x2
    y1, y2 = y2, y1 - q * y2
  return (x1, y1, a1)
 def inv(a, m):
  x, y,g = egcd(a, m)
  if g != 1:
    raise Exception('No modular inverse')
  return x%m
 def nxt(x, n, m, a, b, p):
  if x % 3 == 0:
    x = a*x%p
    n = (n+1)%(p-1)
  elif x % 3 == 1:
    x = b*x%p
    m = (m+1)%(p-1)
  else:
    x = x*x*x%p
    n = 3*n%(p-1)
    m = 3*m%(p-1)
  return x,n,m
 def cycle_detection(a, b, p):
  nrandom = random.randint(0,p-2)
  mrandom = random.randint(0,p-2)
  x_calc = pow(a, nrandom, p)*pow(b,mrandom,p)%p
  x1, n1, m1 = x_calc, nrandom, mrandom
  x2, n2, m2 = x_calc, nrandom, mrandom  
  while(True):
    x1, n1, m1 = nxt(x1, n1, m1, a, b, p)
    x2, n2, m2 = nxt(x2, n2, m2, a, b, p)
    x2, n2, m2 = nxt(x2, n2, m2, a, b, p)
    if x1 == x2:
      try:        
        return (n2-n1)*inv(m1-m2, p-1)%(p-1)
      except:
        return -1           
    def func3(a, b, p):
  while True:
    ret = cycle_detection(a,b,p)
    if ret != -1: return ret

* Pohlig-Hellman Algorithm
Pohlig-Hellman Algorithm은 위에서 언급한 것과 같이 <math> p \ - \ 1 </math>의 소인수에 대한 주기를 찾아내는 알고리즘이고 <math> p \ - \ 1 </math>이 작은 소인수의 곱으로 나타낼 때는 큰 <math> p \ </math>에 대해 현실적인 시간 내에 계산이 가능해질 수 있다. 
 def egcd(a1, a2):
  x1, x2 = 1, 0
  y1, y2 = 0, 1
  while a2:
    q = a1 // a2
    a1, a2 = a2, a1 - q * a2
    x1, x2 = x2, x1 - q * x2
    y1, y2 = y2, y1 - q * y2
  return (x1, y1, a1)
 def inv(a, m):
  x, y,g = egcd(a, m)
  if g != 1:
    raise Exception('No modular inverse')
  return x%m
 def crt(a, m);
 n = len(m)
  ret = a[0]
  mod = m[0]
  for i in range(1,n):
    m1 = mod
    mod *= m[i]
    m2inv = inv(m[i],m1)
    m1inv = inv(m1,m[i])
    ret = (ret*m[i]*m2inv+a[i]*m1*m1inv)%mod
  return ret
 def func2(a, b, p):
  table1 = []
  k = int(p**0.5)
  val = 1
  mul = pow(a,k,p)
  for i in range(0,p,k):
    table1.append((val, i//k))
    val = val * mul % p
 table2 = []
  ainv = inv(a,p)
  val = b
  for i in range(k):
    table2.append((val, i))
    val = val * ainv % p
 table1.sort()
  table2.sort()
 idx1 = 0
  idx2 = 0
  while idx1 < len(table1) and idx2 < len(table2):
    if table1[idx1][0] < table2[idx2][0]:
      idx1 += 1
    elif table1[idx1][0] > table2[idx2][0]:
      idx2 += 1
    else:
      return k*table1[idx1][1]+table2[idx2][1]
  return -1
 def MITM(a, b, mod, pp):
  table1 = []
  k = int(pp**0.5)
  val = 1
  mul = pow(a,k,mod)
  for i in range(0,pp,k):
    table1.append((val, i//k))
    val = val * mul % mod
 table2 = []
  ainv = inv(a,mod)
  val = b
  for i in range(k):
    table2.append((val, i))
    val = val * ainv % mod
 table1.sort()
  table2.sort()
 idx1 = 0
  idx2 = 0
  while idx1 < len(table1) and idx2 < len(table2):
    if table1[idx1][0] < table2[idx2][0]:
      idx1 += 1
    elif table1[idx1][0] > table2[idx2][0]:
      idx2 += 1
    else:
      return k*table1[idx1][1]+table2[idx2][1]
  return -1
 def func4(a, b, p):
  factors = []
  i = 2
  tmp = p-1
  while tmp >= i*i:
    if tmp % i != 0:
      i += 1
      continue
    cnt = 0
    while tmp % i == 0:
      tmp //= i
      cnt += 1
    factors.append((i, cnt))
    i += 1
  if tmp != 1:
    factors.append((tmp, 1))
 crt_a = []
  crt_m = []  
  for factor in factors:
    pp, ee = factor
    cura = pow(a, (p-1)//(pp**ee), p)
    curb = pow(b, (p-1)//(pp**ee), p)
    gamma = pow(cura, pp**(ee-1), p)
    exp = 0
    for i in range(ee):
      b_tmp = inv(pow(cura, exp, p), p) * curb % p
      b_tmp = pow(b_tmp, (pp**(ee-1-i)), p)
      # Want to find gamma ** x = b_tmp (mod p), x in (0,1,2,...,pp-1)
      exp += MITM(gamma, b_tmp, p, pp)*pp**i
 crt_a.append(exp)
    crt_m.append(pp**ee)
 return crt(crt_a, crt_m)
 a = 7
 b = 12423425
 p = 4766587461926291
 x = func4(a,b,p)
 print(x, pow(a,x,p)==b) <ref name="secmem"></ref>

== 활용 ==

===엘가말=== 
[[엘가말]](EIGamal)은 1985년 이산 대수 문제에 바탕을 둔 공개키 암호시스템이다. 아래는 엘가말 암호 알고리즘을 이용하여 송신인 갑이 수신인 을에게 메시지를 전달하는 절차를 설명한 것이다.

* 준비과정 
# 차수가 소수 <math>p</math>인 순환군 <math>G</math>와 이의 한 생성원 <math>\alpha</math> 를 정한다.
# 을은 정수 <math>y</math>를 선택한다. (<math>0 \le y \le p-1</math>)
# <math>\beta :=\alpha ^{y}</math>을 계산한다.
# <math>\left( p,\alpha,\beta \right)</math>가 공개 키가 된다.

* 암호화 
# 갑은 을의 공개 키를 전달받는다.
# 갑은 을에게 전달할 메시지 <math>m\in G</math>을 선택한다.
# 갑은 무작위로 정수 <math>k</math>를 선택한다. (<math>0\le k\le p-1</math>)
# <math>c_{1}:=\alpha ^{k}</math>과 <math>c_{2}:=\beta ^{k}m</math> 계산한다.
# 갑이 을에게 암호문 <math> (c_{1},c_{2})</math>를 전달한다.

*복호화
# 을은<math> s:=c_{1}^{y}</math>을 계산한다. (이는 <math>\beta ^{k}</math>와 그 값이 동일하다.)
# 을이 <math>c_{2}s^{-1}</math>을 계산하면 갑이 전달하고자 했던 메시지 <math>m</math>이 나온다.<ref>〈[https://ko.wikipedia.org/wiki/%EC%97%98%EA%B0%80%EB%A7%90_%EC%95%94%ED%98%B8 엘가말 암호]〉, 《위키백과》</ref>

===디피 헬만===
[[디피 헬만]] 알고리즘(Diffie-Hellman Algorithm)은 상대방의 공개키와 나의 개인키를 이용하여 계산을 하면 비밀키가 나온다. 그 후 나와 상대방은 비밀키를 사용하여 데이터를 암호화한 후 전달하면 된다. 이러한 DH 알고리즘은 '키 교환(key exchange)' 알고리즘으로 대칭키를 공유하는데 사용한다. 이는 암호화나 서명을 위한 것이 아니며, 이산 대수 문제(Discrete Logarithm Problem)(혹은 이산 로그)라는 방식을 이용하는데 <math>y=g^{x} \,\bmod\, p</math>일때 <math>g</math>와 <math>x</math>와 <math>p</math>를 안다면 <math>y</math>는 구하기 쉽지만 <math>g</math>와 <math>y</math>와 <math>p</math>를 알땐 <math>x</math>를 구하기는 어렵다는 방식에 착안하여 만들어진 알고리즘이다.

* 동작원리
: 공개적으로 교환할 발생기(Generator)를 생성한다. 이는 <math>g</math>라고 하고 우리가 <math>\,\bmod\,</math> 할 값 <math>p</math>는 소수로 지정한다.

# A는 개인키 a를 이용하여 <math>g^{a} \,\bmod\, p</math>를 생성한다.
# B는 개인키 b를 이용하여 <math>g^{b} \,\bmod\, p</math>를 생성한다.
# A는 B에게 <math>g^{a} \,\bmod\, p</math>를 보내고 B는 A에게 <math>g^{b} \,\bmod\, p</math>를 보낸다.
# A는 자신의 개인키 a를 이용하여 <math>g^{ab} \,\bmod\, p (g^{b^{a}} \,\bmod\, p)</math>를 만들고
# B는 자신의 개인키 b를 이용하여 <math>g^{ab} \,\bmod\, p (g^{a^{b}} \,\bmod\, p)</math>를 만든다.
# A와 B는 새롭게 생성된 키를 대칭키(비밀키)로 이용한다.

: 이때 공격자인 T가 있다고 가정해보면 T는 A와 B사이에서 데이터를 가로채기 시작하는데 공격자가 가로챈 값들로는 절대 <math>g^{ab} \,\bmod\, p </math>를 만들 수 없음을 알 수 있다.

* 취약점
: 디피 헬만 알고리즘은 대칭키를 비밀스럽게 만들 수 있다는 점에서 장점이 있지만, T가 값을 조작해버리면 [[중간자 공격]](Man In the Middle attack, MIM)에 당하게 된다.

# A와 B가 서로 g를 이용하여 <math>g^{a} \,\bmod\, p</math>와 <math>g^{b} \,\bmod\, p</math>를 보낸다.
# 중간에서 T가 t라는 개인키로 서로에게 보내고 T는 <math>g^{a} \,\bmod\, p</math>와 <math>g^{b} \,\bmod\, p</math>를 이용하여 <math>g^{at} \,\bmod\, p</math>와 <math>g^{bt} \,\bmod\, p</math>를 만든다.
# A와 B는 눈치채지 못하고 t가 준 <math>g^{t} \,\bmod\, p</math>를 이용하여 서로 <math>g^{at} \,\bmod\, p</math>와 <math>g^{bt} \,\bmod\, p</math>를 만든다.
# 이제 A, B, T 모두 같은 대칭키를 가지게 되어 공격을 당할 수 있게 되었다.<ref>Crocus, 〈[https://www.crocus.co.kr/1233 디피 헬만 알고리즘(Diffie-Hellman Algorithm)]〉, 《티스토리》, 2018-04-22</ref>

== 암호학 ==
암호학에서는 이산 로그의 효율적 [[알고리즘]]이 존재하지는 않는다. 하지만 그 반대 방향인 거듭제곱 연산은 간단히 계산할 수 있다는 일방항 함수의 아이디어를 RSA에서와 마찬가지로 이용한 것이다. 만약 이산 로그 문제를 계산할 수 있다면 원래 비밀 숫자를 알아낼 수 있다. 이 때문에 이산 로그의 비효율성은 보안성에 중요 역할을 한다. 엘가말 암호와 전자 서명 알고리즘 등의 암호 체계에서도 비슷한 방법을 이용한다. 타원 곡선 암호에서는 유한체에서 정의된 타원 곡선의 순환 부분군의 이산 로그 문제를 활용한다.<ref name="위키백과"></ref>

===타원곡선암호===
[[파일:타원곡선 그래프.png|썸네일|400픽셀|'''타원곡선''' <math>y^{2} = x^{3} +ax = b</math><br>들의 그래프]]

* 정의
: 일반적으로 타원곡선 방정식은 다음과 같은 형태의 3차 방정식을 이용한다.

 (식 1) <math>y^{2} + {b_1}xy + {b_2}y = x^{3} + {a_1}{x^2} + {a_2}x + {a_3}</math> 

그러나, 실수상의 타원 곡선은 다음과 같은 특별한 범주에 속하는 타원 곡선을 사용한다.

 (식 2) <math>y^{2} = x^{3} + ax + b</math> 

타원곡선은 일반적으로 타원 형태의 그래프를 생각하기 쉬우나, 타원곡선은 우측의 그림과 같은 형태의
곡선을 가지며 (식 2)의 <math>a</math> 와 <math>b</math> 의 값에 따라 다양한 형태의 타원 곡선을 정의할 수 있다. 타원곡선의 특징은 <math>x</math>축을 중심으로 대칭되며, 비 수직선에 대해 최대 3개 지점에서 곡선과 교차한다는 점이다.

=== 타원곡선의 이산대수 문제에 기반한 타원곡선 암호화===
[[파일:타원곡선 덧셈.jpg|썸네일|700픽셀|'''타원곡선''' 덧셈 그래프]]
* 타원곡선암호의 원리 및 키생성
: [[타원곡선암호]]는 타원곡선 위의 이산로그 문제가 어렵다는 사실을 이용한 공개키 암호 방식이다. 타원곡선 암호화를 위한 타원곡선은 임의의 정수 <math>a</math>, <math>b</math> 에 대해 정의된 다음과 같은 방정식의 해 <math>(X, Y)</math> 의 집합이다.

 (식 3) <math>Y^{2} = X^3 +aX + b \pmod{p}</math> 

점 <math>P=(x, y)</math>가 타원곡선 상에 있다는 것은 위 방정식을 만족시킨다는 뜻이고, 두 점 <math>P</math>, <math>Q</math> 와 임의의 정수 <math>x</math>에 대해 다음 방정식을 정의할 수 있다.

 (식 4) <math>Q = xG</math> 

이때 해 <math>x</math>를 구하는 것이 타원곡선 이산대수 문제이다. 이로부터 타원곡선암호에서 사용하는 키 쌍은 다음과 같이 정의할 수 있다.

 <math>G</math> : 생성자, 임의의 시작 포인트
 <math>x</math> : 개인키, <math>P</math> 보다 적은 소수(Prime)로, 난수 생성기로 생성
 <math>Q</math> : 공개키, 개인키로부터 연산

이때 공개키 <math>Q</math> 는 <math>Q = x \times G = G+G+...+G</math> (<math>x</math>번 덧셈)으로 <math>G</math>를 <math>x</math>번 덧셈연산한 값이다. <math>Q=xG</math> 수식에서 <math>x</math>와 <math>G</math>를 이용해서 <math>Q</math>를 구하기는 쉽지만, <math>G</math>와 <math>Q</math>를 안다고 해서, <math>x</math>값을 유추해 내기가 굉장히 어려운 타원곡선 이산대수 문제를 이용한다. <math>G</math>는 타원 곡선상의 임의의 점이며 <math>x\times G</math>는 <math>G</math>를 타원곡선상에서 <math>x</math>번 덧셈 연산한 것을 의미한다. <math>2G=G+G</math>는 점 <math>G</math>에서의 접선이 타원곡선과 만나는 제 3의 점을 <math>x</math>축으로 대칭시킨 지점이다. <math>4G = 2G+2G</math>는 <math>2G</math>에 해당하는 점에서 마찬가지로 접선을 그어 타원 곡선과 만나는 점의 <math>x</math>축 대칭 점이다. <math>G</math>의 상수 배 연산은 이를 반복적으로 수행하여 표현할 수 있으며, 타원곡선상에서 이루어지는 특성을 보인다. 타원 곡선은 공개키 암호 체계를 수학적으로 수행하는 한 가지 방법으로써 타원곡선을 이용하여, RSA, [[엘가말]], [[디피 헬만]]을 구현할 수 있다.

{| class="wikitable" width=650 style="color:balck; text-align: center; background-color:#F8F9FA;" 
!  || 엘가말 공개키 암호 || 타원곡선 공개키 암호 
|-
! 공개키
|  <math>(g, p, y = g^{x} \,\bmod\, p )</math> || <math>(G, p, Y = xG)</math>
|-
! 개인키
| <math>(x)</math> || <math>(x)</math>
|-
! 암호화
| <math>({c_1}, {c_2}) = ( g^{x} \,\bmod\, p, y^{x}m \,\bmod\, p )</math> || <math>({C_1}, {C_2}) = (x'G, x'Y + M)</math>
|-
! 복호화
| <math> {c_2} {{c_1}^-x} \,\bmod\, p </math> || <math>{C_2}-x{C_1}</math>
|-
|}
: (<math>x'</math>는 임의의 난수이다.)<ref>김미영, 〈[https://www.ilifo.co.kr/files/newsletter/NL000021/.../2/.../20180719181637157.pdf 이제는 알 때가 됐다! – ECC 알고리즘]〉, 《아이리포》, 2018</ref>

{{각주}}

== 참고자료 ==
* 〈[https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%82%B0_%EB%A1%9C%EA%B7%B8 이산 로그]〉, 《위키백과》
* 〈[https://terms.naver.com/entry.nhn?docId=5669271&cid=60207&categoryId=60207 이산로그]〉, 《네이버 지식백과》
* 〈[https://ko.wikipedia.org/wiki/%EC%97%98%EA%B0%80%EB%A7%90_%EC%95%94%ED%98%B8 엘가말 암호]〉, 《위키백과》
* blisstoner , 〈[http://www.secmem.org/blog/2019/05/17/%EC%9D%B4%EC%82%B0-%EB%A1%9C%EA%B7%B8/ 이산-로그]〉, 《secmem》, 2019-05-17
* 꼬막, 〈[http://blog.naver.com/PostView.nhn?blogId=komark7&logNo=40052038392&categoryNo=5&viewDate=&currentPage=1&listtype=0&from=postList 이산대수-위키]〉, 《네이버 블로그》, 2008-06-11
* Fist1stPark, 〈[https://fistpark.tistory.com/entry/%EC%9C%A0%ED%95%9C%EC%B2%B4%EC%9D%98-%EC%9D%B4%EC%82%B0%EB%8C%80%EC%88%98 유한체의 이산대수]〉, 《티스토리》, 2009-04-03
* Crocus, 〈[https://www.crocus.co.kr/1233 디피 헬만 알고리즘(Diffie-Hellman Algorithm)]〉, 《티스토리》, 2018-04-22
* 김미영, 〈[https://www.ilifo.co.kr/files/newsletter/NL000021/.../2/.../20180719181637157.pdf 이제는 알 때가 됐다! – ECC 알고리즘]〉, 《아이리포》, 2018

== 같이 보기 ==
* [[엘가말]]
* [[디피-헬만]]
* [[소인수분해]]

{{암호 알고리즘|검토 필요}}