타원곡선 이산 로그 문제 가 뭔데

타원곡선 이산 로그 문제

aG = b 에서 G 와 b 값을 주었을때 a값을 구하는 효율적인 알고리즘이 없다.

왜?

타원곡선의 동일점 덧셈

타원곡선에서는 동일점 덧셈을 스칼라 곱셈으로 나타대는데

g+g+g = 3g

위와같은 식으로 표현된다.

만약 2g, 3g, 4g 를 구하게된다면
g 포인트의 접선과 곡선이 만나는 또다른점 을 찾고 찾은 점의 역원이 2g가 된다.

기존 g와 위에서 구한 2g에 선을 구하면 다른 점을 만나게 되는데
이 점의 역원이 3g이다.

기존 g와 위에서 구한 3g에 선을 구하면 다른 점을 만나게 되는데
이 점의 역원이 4g이다.

결론

aG = b 에서 G 와 b 값을 주었을때 a값을 구하는 효율적인 알고리즘이 없다.

위의 궁굼증을 확인해보면
결과인 aG는 결국 타원곡선상에 위치한 어떤 점이 될텐데
이 G를 도대체 몇번을 이동해서 해당 aG 의 위치로 가게된건지 알기가 어렵고
알려고 한다면 하나하나 연산을 해볼수밖에 없다.
따라서 못구하는것이 아니라 구하는 효율적인 방법이 없다는것이다.