[질문] 이산대수 문제란? 솔로몬의지혜

-------------------------------------------------------------------------------- [질문] 이산대수 문제란? 솔로몬의지혜 안녕하세요. 저는 암호공부를 하고 있는 대학원생입니다. 공개키알고리즘의 Elgamal 알고리즘은 이산대수문제의 어려운 점을 이용한다고 합니다. 이산대수문제란 무엇인지 간략하게 설명해주시면 고맙겠습니다. 아래글은 자료입니다. ========================================= 2.6.8 이산 대수의 문제점은 무엇인가? 이산대수 문제는 그룹들을 이용한다. 일반적으로 차수가 t인 집합 G의 원소g와 집합 G의 다른 원소 y가 주어졌을 때 x 를 구하는 것은 어려우며 이를 이산대수 문제라 한다. 여기서 0≤x≤t-1이다. y는 g를 x번 곱한 결과이다. 원소g는 전형적으로 G의 모든 원소들을 생성하거나 또는 적어도 0에서 t-1사이의 모든 정수들을 가지고 누승함으로서(즉, 반복적으로 그룹 연산을 함으로서) 큰 부분집합을 생성할 수 있다. 원소 g가 그룹내의 모든 원소들을 생성할 수 있다면 원소g를 생성기(generator)라고 한다. 소인수분해 문제와 마찬가지로 이산대수 문제는 단방향 함수의 어려운 문제라 여겨지고 있다. 이러한 이유로 이산대수 문제는 ElGamal 시스템과 DSS를 포함한 여러 공개키 암호 시스템들의 기초를 이루어 왔다 ========================================== 작 성 일 : 2001년 01월 17일 첨부화일 : [답변] 이산대수와 암호 whiz 거의 말 그대로 입니다. 생성원(generator) g 를 갖는 순환군(cyclic group) G 가 있을 때, G 의 원소 x 는 g^m 인 m 을 x 의 차수라고 부릅니다. 그런데, m 을 지정해서 g^m 으로 x 를 만드는 것은 쉬우나, G 의 원소 x 가 있을 때, x = g^m 인 m 을 찾는 게 쉽지 않은 경우가 많습니다. 대표적인 예가 소수 p 에 대하여, 1,2,...,p-1 까지의 집합에 p 를 modulo 로 하는 곱을 준 경우입니다. (이 군이 항상 순환군임은 잘 알려져 있습니다) 예를 들어, p = 17 인 경우, { 1, 2, ..., 16 } 은 3 을 생성원으로 갖습니다. (생성원을 구하는 것도 어려운 문제지만...) 3, 3^2, 3^3, ..., 3^16 을 구해보면, (17 로 나눈 나머지) 3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1 의 순서로 나타나지요. 조금만 보면 알겠지만 규칙성이 거의 없어 보입니다. 여기에서 m=13 을 알고 있으면, 3^13 = 12 (mod 17) 이라는 것은 쉽게 알지만, 무턱대고 주어진 x = 12 에 대하여 12 = 3^m (mod 17) 인 m 이 13 이라는 것을 알기가 쉽지 않다는 것입니다. 위의 경우는 17 이라는 작은 소수를 택해서 그렇다는 것이고, 일반적으로 p 가 커지면 계산이 무척 복잡합니다. 아무튼 이런 의미에서 이산대수 문제는 단방향 함수가 된다는 뜻입니다. 즉, m 을 알면 x 를 쉽게 알지만, x 를 안다고 해서 m 을 구하는 것은 어렵다는 거죠.