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

타원곡선위 한점을 계속 더하는것이다. 그리고 그 결과는 예측하기 어렵다.

$ (170,142) + (170, 142) = 2 \cdot (170, 142) $

$ 2 \cdot (170, 142) + (170, 142) = 3 \cdot (170, 142) $

 

출처: 밑바닥부터 시작하는 비트코인

 

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)

 

스칼라 곱셈의 또다른 특징이 있다. 어떤 점에 스칼라 값을 계속 증가시키면서 곱하다 보면 무한원점(덧셈에 대한 항등원. I) 에 도달한다.

그래서 만약 어떤 점 G 와 스칼라 곱을 무한원점에 도달할 때까지 반복한다면 다음 집합을 얻을 수 있다.

$\{G, 2G, 3G, 4G, ... , nG\} $ 여기서 nG = 0 

n은 유한한 특정 값이기에 유한순환군이라고 부른다. 

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

x1 = FieldElement(15, prime)
y1 = FieldElement(86, prime)

p1 = Point(x1, y1, a, b)
print(p1 + p1 + p1 + p1 + p1 + p1 + p1)
print(p1 + p1 + p1 + p1 + p1 + p1 + p1 == Point(None, None, a, b))  # True

 

이산로그문제

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

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

 

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

 

출처: 밑바닥부터 시작하는 비트코인