## 질문 답변

1. ECC가 그림을 그리는 방법(기하적 방법)과 유한체를 이용한 방법 2가지가 있는 것이 맞나요??

- NO 그냥 그림은 보조도구임

2. ECC가 유한체를 쓰는 이유가 정수로 계산을 해야 해서, 수가 유한개여서 보안에 적합하기 때문이 맞나요?

- NO, 체(field)인게 중요한거임

3. 그림을 그리는 방법에서 p == q 일 때(p에서의 접선과 만나는 점의 x축 대칭, 그 점에서의 접선과 만나는 점의 x축 대칭), p != q 일 때(두 점을 지나는 직선과 만나는 점을 x축 대칭, 그 점과 p를 지나는 직선과 만나는 점을 x축 대칭) 이 과정을 계속하는 것이 맞나요??

- ???, 무슨 소리인지 모르겠음

결론: 이해를 못한 것으로 보임

최대한 간단한게 ECC 설명을 해봄

## 1. Background

- 컴퓨터는 실수 연산이 부정확함
- 컴퓨터도 메모리의 한계가 있기 떄문에 무한하게 정밀한 실수를 담을 수 없음
- 컴퓨터의 실수 계산들은 실수오차가 있음(0.1 + 0.2 도 0.3이 아님)
- [실제로는 0.30000000000000004임](https://0.30000000000000004.com/)
- 오차가 있다? 보안 영역에서는 못 씀
- 정수는 그냥 당연히 잘 계산함 뭐 틀릴수가 없고 속도도 빠름

- 대수학적인 배경
- 일단 체(field)라는 개념이 있음 (그밖에도 군, 환, 모노이드 등등 뇌절하는 구조들 많음)
- 체에는 좋은 성질이 있어서 일단 체면 좋음
- 체는 뭐 수학적 정의는 좀 더 복잡한데 쉽게 얘기하면 집합내 원소들끼리 더하고 빼고 곱하고 나누었을 때 집합 내 원소가 되면 체라고 함 (이런걸 보고 덧셈과 곱셈에 닫혀 있다고 함)
- 예를 들어보면
- 유리수는 유리수끼리 더하면 유리수고, 유리수끼리 곱해도 유리수고, 유리수끼리 나눠도 유리수고(0제외), 유리수끼리 빼도 유리수임 => 그러니 유리수는 체임
- 비슷하게 실수의 집합도, 복소수의 집합도 체임 (실수체, 복소수체)
- 근데 정수는 체가 아님 (정수 나누기 정수는 정수가 아님, e.g. 2를 4로 나누면 정수가 아님)
- 우리는 컴퓨터에서 쓸거니깐 정수로 체를 만들고 싶음
- 이때 좀 놀라운 성질이 하나 있는데 정수를 소수(prime number)로 modular(나머지?)한 결과는 체가 됨 이걸 유한체라고 부름
- 음 증명은 인터넷 찾으면 나옴
- 예를 들면 5(소수)로 modular하면 {0, 1, 2, 3, 4} 일텐데
- 3 + 4 = 2 (mod 5)
- 2 * 3 = 1 (mod 5)
- 2 / 4 = 3 (mod 5) (4의 modular inverse는 4임 -> 계산하는법 궁금하면 검색)
- 어쩄든 이런식으로 계산결과가 집합내 원소랑 전부 1대1대응이 됨
- 소수가 아닌수로 modular하면 답이 없거나 여러개 나올수 있어서 안 됨
- 갈루아체라고도 많이 부름
- 군(Group)이라는 개념도 있음
- 군은 결합법칙 적용되고, 항등원 있고, 역원 있으면 군임
- 예를 들면 정수에서 덧셈은 군임
- 1. 결합법칙 작용함 (a + b) + c = a + (b + c)
- 2. 항등원 있음 a + 0 = a = 0 + a, 만족하는 a가 0이 존재하고 유일함
- 3. 역원 있음 a + x = 0 x + a, 만족하는 x=-a가 항상 존재
- 예시) 정수,유리수, 실수, 복소수의 덧셈, 곱셈 등등

## 2. 타원 곡선

ECC에서 말하는 타원 곡선은 수학에서 쓰이는 타원곡선이랑은 조금 식이 다름 (같은거긴 한데)

$y^2 = x^3 + ax + b$

근데 여기서 우리는 p라는 소수를 하나 정해서 modular를 취해준다면?
말했듯이 정의역이 유한체가 되고 x, a, b가 어떤 수든 체니깐 당연히 더하고 곱하고 해도 유한체 안 결과가 나오니깐 치역도 유한체가 됨

어떤 점(x, y)이 타원 곡선에 있다는 건? 저 위 방정식을 만족하는 p-유한체 좌표쌍인거임


타원 곡선의 성질의 가장 중요한건 첫번째그림임
두 점($P, Q$)을 지나는 직선과 타원곡선의 또다른 교점은 -R이고, x축 대칭하면 R인데 $P + Q = R$
그냥 한직선이 세개의 점 만날때 그거 다 더하면 0이라고 생각해도 됨(당연히 최대 3개만 만남)

두번째 그림은 만약 P + P를 할수도 있음을 보여주는거고(접선 그려서 타원곡선과 만나는 지점이 -R)
세번째 그림은 역원을 더하면 무한점 O로 감을 보여줌 (그래서 타원곡선 정의 제대로 찾아보면 무한점이 포함됨)

잘생각해보면 얘도 결합법칙도 적용되고, 항등원도 존재하고, 역원도 존재한다.그럼 이것도 타원곡선의 덧셈 군(Group)이다.

## 3. 암호 만들기

암호의 기본 원리는 만드는건 쉬운데, 푸는건 어려운거임

우리는 암호를 되게 간단하게 만들 수 있음

$Q = xG$

처음 G(Generator)를 그냥 임의로 정한 그래프상의 아무 점
$x$가 이제 우리의 개인키인데 당연히 p보다는 작아야함 (큰 메시지를 보내려면 p를 키우면 됨)
그래서 xG를 계산하면 됨.
근데 우리는 타원곡선에서 좌표의 덧셈 군만 정의했지 곱셈에 대해서는 말하지 않았다.
그래서 xG를 G+G+G+G+....(x번 더함)이라고 생각한다.

만약에 대충 p가 31(소수)이라고 정하고 x가 16이라고 생각해보자.

계산 과정은

G+G=2G를 계산 (위에 그림에서 얘기했듯 임의의 P+P 계산을 쉽게 할 수 있음)
2G+2G=4G를 만들고
4G+4G=8G를 만들고
8G+8G=16G를 만들면된다.

그러면 만들떄 계산을 몇번했는지를 생각해보면 계산을 4번한거다.
만약에 우리가 이거를 풀려고 한다면??

최악의 경우 30번의 계산을 해야한다. Q랑 G를 알아도 x가 얼마일때 저 계산이 나올지는 전혀 알 방법이 없기 때문에 그냥 하나하나 대입해야한다.(why? 타원 곡선의 곱셈 역원이 없음)

- G = Q인지 확인 => 맞으면 x = 1
- 2G = Q인지 확인 => 맞으면 x = 2
- 3G = Q인지 확인 => 맞으면 x = 3
- ...
- 30G = Q인지 확인 => 맞으면 x = 30

지금은 p를 매운 작게 했지만 실제로는 600비트(2^600), 1000비트 막 이정도의 수를 쓴다.

예를 들어 한 100비트만 되어도 만들떄는 200번안의 계산만으로 암호화를 할 수 있지만

하나하나 대입해서 풀려면 2^100이니깐 1267650600228229401496703205376번의 무지막지한 시도를 해야하고 이정도 수만 되도 태양이 폭발할때까지 찍어서 못맞추는 수준이다.

N비트의 소수 p가 있을때 암호화를 하는건 N번 정도의 계산이면 되지만($\mathcal{O}(N)$)
복호화를 하는건 $2^N$정도의 시간이나 걸린다($\mathcal{O}(2^N)$)

*물론 저것보다 좀 더 효율적인 공격 방법이 존재하긴 하지만 어쨌든 엄청 느리고 경우의수가 많다*

## 다시 질문을 봐보면

1. ECC가 그림을 그리는 방법(기하적 방법)과 유한체를 이용한 방법 2가지가 있는 것이 맞나요??

- 유한체를 이용한건 맞고 방법은 그냥 그거 한가지이다. 그림은 그냥 설명용이고 실제로는 그림 안그리고 그냥 타원 곡선의 접선의 방정식 같은거로 해서 걍 계산하면 된다.

2. ECC가 유한체를 쓰는 이유가 정수로 계산을 해야 해서, 수가 유한개여서 보안에 적합하기 때문이 맞나요?

- 정수로 계산을 해야하는건 맞음(뭐 이론상 실수체나 유리수체, 복소수체로 못하는건 아니지만 걍 정수로 만든 체가 컴퓨터에서 편하니깐). 수가 유한개인건 뭐 컴퓨터에 저장된 수가 무한할수 없는것도 있고 소수로 modular해야 체가 되니깐 결론적으로 유한할수 밖에 없다.

3. 그림을 그리는 방법에서 p == q 일 때(p에서의 접선과 만나는 점의 x축 대칭, 그 점에서의 접선과 만나는 점의 x축 대칭), p != q 일 때(두 점을 지나는 직선과 만나는 점을 x축 대칭, 그 점과 p를 지나는 직선과 만나는 점을 x축 대칭) 이 과정을 계속하는 것이 맞나요??

- 그림을 그리는건 아니고 암호화할때 그냥 P+P=2P, 2P+2P=4P, ... 이런걸 반복할듯 (x가 2의 배수가 아니면? 남은 부분도 다시 비슷하게 재귀적으로 처리하면 됨) 근데 ECC도 기본 아이디어고 실제로 구현된 종류가 많아서 저 설명에 관련된 무언가도 있을수 있긴한데 잘은 모르겠음

## 이해를 못했다면 2줄 요약

- 암호화할 떄는 그냥 저렇게 2배씩 늘려가면서 계산 할수 있어서 빠르지만 복호화는 하나하나 대입해서 찾는거 외에는 노답이라 매우 오래걸림.
- 계산을 할때 항상 타원 곡선 위에 있는게 보장이 되고, 정답이 하나 밖에 없다는게 보장이 되는건 유한체와 타원곡선의 성질임

## 여담

걍 작은수로 a,b,x,g,p 같은거 만들어서 해보는게 이해 더 잘 될듯

수학적으로 틀린 내용 다수 존재 가능