이산로그

이산로그는 일반 로그와 비슷하게 군론에서 정의된 연산으로 1보다 큰 자연수 $a\ ,\ m$ , 정수 $b\$ 에 대하여 방정식 $a^{x}\ =\ b$ 만족하는 정수 $x\$가 이산로그이다. 이산로그를 계산하는 다항식 시간(polynomial time) 알고리즘이 알려져 있지 않아 이산로그는 현대 암호에 응용되고 있다.

개념

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

특징

아직까지 이산 로그 문제에 대한 효율적인 계산법은 나오지 않았다.(여기서 효율적인 계산법이라고 하는 것은 참고로 이산 로그 문제는 NP-complete에 속하는 문제는 아니기에 효율적인 계산법이 나올 가능성은 충분히 있다. 또한 Quantum Computer에서는 P에 속함이 증명되어 있다. 이산 로그는 Elgamal Encryption, Diffie-Hellman 키 교환, Digital Siganature Algorithm 등과 같이 암호화, 키 교환, 인증 등의 각종 암호 분야에서 쓰이고 있다. 만약 이산 로그 문제가 효율적으로 풀리게 된다면 위에서 언급한 암호 시스템이 안전하지 않게 된다. 또한, 비록 일반적인 이산 로그에 대한 풀이법 자체는 아직 찾지 못했다고 하더라도 a,b,p를 적절하게 택하지 못하는 구현의 실수로 인해 기밀성이 지켜지지 않는 경우도 있다.

• Safe Prime

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

알고리즘

• 전수조사

이 방법은 가장 떠올리기 쉽고 간단한 풀이법이다. 바로 $x\$에 0부터 $p\ -\ 1$까지 차례로 넣어보며 $a^{x}\ =\ b$를 만족하는 $x\$를 찾는 것 이다. 아쉽게도 이 방식은 최악의 경우 $p\$번의 곱셈이, 평균적으로는 $p\ /\ 2$번의 곱셈이 필요하기 때문에 $p\$가 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) 알고리즘으로, 이 알고리즘을 통해 시간복잡도를 $O(p)\$에서 $O(p^{0.5})\$로 떨어 뜨릴 수 있다. 해쉬를 이용할 경우 $O(p^{0.5})\$, 정렬을 이용할 경우 $O(p^{0.5}lgp)\$에 이산 로그 문제를 해결할 수 있다. 정렬을 이용한 예시 코드는 아래와 같다.

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은 $a^{n_{1}}b^{m_{1}}\ =\ a^{n_{2}}b^{m_{2}}$인 적절한 $n_{1}\,\ n_{2},\ m_{1},m_{2}\$를 찾았을 때 $log_{a}b\ =\ (n_{2}-n_{1})(m_{1}-m_{2})^{-1}$이라는 점을 이용하는 알고리즘 이다. 이 알고리즘의 시간복잡도는 $O(p^{0.5})\$입니다. 같은 시간복잡도를 가지는 Baby-step giant-step Algorithm과 비교할 때 이 알고리즘은 확률적 알고리즘이기 때문에 $O(p^{0.5})\$에 반드시 답이 찾아짐을 보장할 수 없고 상수가 약간 크다는 단점이 있지만, 공간을 $O(1)\$만 사용한다는 아주 큰 장점이 있습니다. 이 알고리즘은 임의의 $a^{n}b^{m}\$ 꼴의 수들로 수열을 만들었을 때 해당 수열에서 cycle을 찾아내는 방식으로 동작합니다. 수열에서의 cycle은 Floyd’s cycle-finding algorithm으로 구할 수 있습니다. 알고리즘에 대해 간략하게 설명을 하자면, 한 번에 한 칸씩 가는 거북이와 두 칸씩 가는 토끼를 수열 상에서 이동시켜 거북이와 토끼가 같은 값에 위치하는 순간을 찾는 방법입니다. $f(x)\ =\ a^{n}b^{m}$꼴의 수열을 만들기 위해 $x\$ 를 3으로 나눈 나머지에 따라 각각 $f(x+1)\ =\ ax$ 혹은 $f(x+1)\ =\ bx$ 혹은 $f(x+1)\ =\ x^{k}$으로 계산합니다. 반드시 $ax\,\ bx,\ x^{k}$일 필요는 없고 $a^{2}x\,\ b^{2}x,\ ab^{2}x^{4}$등과 같이 $f(x+1)\$이 여전히 $\ a^{n}b^{m}$으로 잡아도 무관하다. 그 후 $f(x)\$에 대해 앞서 소개한Floyd’s cycle-finding algorithm 으로 $a^{n_{1}}b^{m_{1}}\ =\ a^{n_{2}}b^{m_{2}}$를 만족하는 $n_{1}\,\ n_{2},\ m_{1},m_{2}\$를 찾습니다. 만약 $m_{1}\ =\ m_{2}$일 경우는 탐색 실패 이므로 다른 초기 항을 잡아 같은 절차를 반복한다. 예시 코드는 아래이다.

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은 위에서 언급한 것과 같이 $p\ -\ 1$의 소인수에 대한 주기를 찾아내는 알고리즘이고 $p\ -\ 1$이 작은 소인수의 곱으로 나타낼 때는 큰 $p\$에 대해 현실적인 시간 내에 계산이 가능해질 수 있다.

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) 

활용

• 디피-헬만(Diffie-Hellman) 비밀키 교환

디피-헬만 키 교환(Diffie–Hellman key exchange)은 암호 키를 교환하는 하나의 방법으로, 휫필드 디피와 마틴 헬먼이 1976년에 발표하였다. 디피-헬먼 키 교환은 상대방의 공개키와 나의 개인키를 이용하여 계산을 하면 비밀키가 나온다. 그 후 서로 비밀키를 사용하여 데이터를 암호화 한 후 전달하면 된다. 디피-헬먼 키 교환은 기초적인 암호학적 통신 방법을 수립하였고, 이후 1977년 공개 키 암호 방식인 RSA 암호가 제안되었다.

• 엘가말(ElGamal) 암호 체계

엘가말은 1984년에 미국 스탠퍼드 대학교의 타헤르 엘가말(Taher ElGamal)이 제안한 공용 키 암호 방식의 하나이다. 소수 $=\ p$ 와 원시근 $=\ g$를 공통의 공용 키로 한다. 이용자는 자신의 비밀 키 $\ x$를 정하고 $\ g^{x}/\ p$ 나머지 $\ y$ $y\ =\ gx(modq)$ 를 자신의 공용 키로 한다. 평문과 난수의 공용 키로부터 암호문을 생성하고, 비밀 키로 복호화(decoding)한다. 암호문의 길이가 평문 길이의 2배로 되는 결점이 있지만 이산 대수 문제의 어려움에 안전성의 근거를 두고 있다. 엘가말 암호는 이산 대수(離散對數) 문제에 대한 최초의 공용 키 암호이며 디피-헬먼 키 분배법의 확정형이다. 이산대수 문제의 어려움이란, 주어진 $\ g,x,p$를 이용하여 $y\ =\ gx(modq)$를 구하긴 쉽지만 $\ g,y,p$값을 이용하여 원래의 $\ x$는 찾기 어렵다는 것이다. 엘가말 암호의 장점은 난수 $\ k$를 이용하기 때문에, 매 암호화 시 다른 암호문을 얻어 RSA에 비해 더 안전하다. 왜냐하면 RSA는 같은 메시지, 같은 키 값을 이용할 경우 그 암호문이 항상 일정한 데 반해 엘가말 암호는 같은 메시지, 같은 키 값을 사용해도 암호화를 할 때마다 그 암호문의 값이 변하기 때문이다. 다만 메시지 M을 암호화 하면 그 길이가 두 배가 되며 속도가 느리다는 단점이 있다.

• 소인수분해 문제

암호학

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

참고자료

• blisstoner , 〈이산-로그〉, 《secmem》, 2019-05-17
• 〈이산로그〉, 《네이버 지식백과》
• 〈이산_로그〉, 《위키백과》
• crocus, 〈디피 헬만 알고리즘(Diffie-Hellman Algorithm)〉, 《crocus》, 2018-04-22

같이 보기

• 엘가말
• 소인수분해

이 이산로그 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반