위키원
"이산로그"의 두 판 사이의 차이
| 31번째 줄: | 31번째 줄: | ||
y1, y2 = y2, y1 - q * y2 | y1, y2 = y2, y1 - q * y2 | ||
return (x1, y1, a1) | return (x1, y1, a1) | ||
| − | def inv(a, m): | + | def inv(a, m): |
x, y,g = egcd(a, m) | x, y,g = egcd(a, m) | ||
if g != 1: | if g != 1: | ||
raise Exception('No modular inverse') | raise Exception('No modular inverse') | ||
return x%m | return x%m | ||
| − | def func2(a, b, p): | + | def func2(a, b, p): |
table1 = [] | table1 = [] | ||
k = int(p**0.5) | k = int(p**0.5) | ||
2019년 7월 31일 (수) 15:30 판
이산로그는 일반 로그와 비슷하게 군론에서 정의된 연산으로 1보다 큰 자연수 , 정수 에 대하여 방정식 (mod m) 만족하는 정수 x가 이산로그이다. 이산로그를 계산하는 다항식 시간(polynomial time) 알고리듬이 알려져 있지 않아 이산로그는 현대 암호에 응용되고 있다.
개요
개념
수학에서 로그는 모두 익숙할 것이다. 일 때 이다. 실수에서는 가 주어졌을 때 를 만족하는 , 즉 를 아주 간단하게 계산할 수 있다. 그러나 에서 주어진 에 대해 를 만족하는 를 찾는 문제가 바로 이산로그 문제이다. 이산 로그 문제에서 는 소수, 는 의 원시근인 것이 좋다.[1]
특징
아직까지 이산 로그 문제에 대한 효율적인 계산법은 나오지 않았습니다.(여기서 효율적인 계산법이라고 하는 것은 참고로 이산 로그 문제는 NP-complete에 속하는 문제는 아니기에 효율적인 계산법이 나올 가능성은 충분히 있습니다. 또한 Quantum Computer에서는 P에 속함이 증명되어 있습니다. 이산 로그는 Elgamal Encryption, Diffie-Hellman 키 교환, Digital Siganature Algorithm 등과 같이 암호화, 키 교환, 인증 등의 각종 암호 분야에서 쓰이고 있습니다. 만약 이산 로그 문제가 효율적으로 풀리게 된다면 위에서 언급한 암호 시스템이 안전하지 않게 됩니다. 또한, 비록 일반적인 이산 로그에 대한 풀이법 자체는 아직 찾지 못했다고 하더라도 a,b,p를 적절하게 택하지 못하는 구현의 실수로 인해 기밀성이 지켜지지 않는 경우도 있습니다. [1]
풀이법
- 전수조사
def func(a, b, p): val = 1 for x in range(p): if val == b: return x val = val*a % p return -1
이 풀이법은 가장 떠올리기 쉽고 간단한 풀이법입니다. 바로 에 0부터 까지 차례로 넣어보며 를 만족하는 를 찾는 것 입니다. 아쉽게도 이 방식은 최악의 경우 번의 곱셈이, 평균적으로는 번의 곱셈이 필요하기 때문에 가 1024 bit 혹은 2048 bit인 보통의 경우에는 현실적인 시간 내에 풀이가 불가능하다.
- Baby-step giant-step Algorithm (아기걸음 거인걸음)
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
알고리즘의 이름은 생소할 수 있지만 일종의 MITM(Meet In The Middle) 알고리즘으로, 이 알고리즘을 통해 시간복잡도를 에서 로 떨어 뜨릴 수 있다.
각주
같이보기
- blisstoner , 〈이산-로그〉, 《secmem》, 2019-05-17
