타원곡선 위 점의 스칼라 곱셈

[yangbongsoo]

(170, 142) + (170, 142) = 2 dot (170, 142) 2 dot (170, 142) + (170, 142) = 3 dot (170, 142)

[yangbongsoo]

prime = 223
a = FieldElement(0, prime)
b = FieldElement(7, prime)

x1 = FieldElement(170, prime)
y1 = FieldElement(142, prime)

p = Point(x1, y1, a, b)
print(p + p)

[yangbongsoo]

이산로그문제

점 P(170, 142) 가 있다고 하자. 7번 스칼라 곱셈을 하면 점 Q(218, 95) 가 나온다. 7 dot (170, 142) 를 계산해서 (218, 95) 점을 얻는것은 쉽다. 하지만 P(170, 142), P(218, 95) 를 안다고 했을 때, 몇번 스칼라 곱셈을 한것인가를 아는것은 어렵다.

다시말해 $P^x = Q$ 에서 P 와 x 를 알면 Q 는 구하기 쉽지만, $x = log_pQ$ P 와 Q 를 알았을 때 x 구하기는 어렵다. 실수에서는 로그 계산이 쉽지만 유한체에서는 어렵다. 현재 로그 방정식을 해석적으로 계산하는 알고리즘은 없다.

[yangbongsoo]

공개키 암호 기법에 스칼라 곱셈이 활용되는 이유는 타원곡선에서 스칼라 곱셈 역산이 어렵기 때문이다. 규칙적인 패턴도 보이지 않는다. 이런 계산식을 비대칭성을 띈다고 한다. 순방향 계산은 쉽지만 그 반대 방향 계산이 어려운 문제를 말한다. ex) 12(47,71) 구하는건 쉬운데, s(47,71) = (194,172) 에서 s 구하는건 어렵다. https://github.com/jimmysong/programmingbitcoin/blob/master/code-ch03/ecc.py#L298