2023. 8. 25. 11:07ㆍ수학
글을 쓰기 앞서, 타원 굉장히 어렵습니다. 때문에 이 글에서는 타원곡선 알고리즘의 전체적인 전개흐름과 어떤 원리가 암호학에서 유용하게 쓰이고 있는지 이야기 해 보겠습니다.
우리는 앞서 디피-헬만 키, RSA암호에서 소인수 분해문제, 이산대수 문제를 살펴보았습니다. 타원 곡선 알고리즘은 위 암호 알고리즘과 같이 소인수 분해, 이산대수 문제를 응용하면서 암호 알고리즘에 응용할 수 있는 성질을 가집니다. 또한 위 암호 알고리즘들과 비슷한 안전성을 가지는데, 다른 공개키 알고리즘보다 적은 수의 비트로 사용 가능하다는 점이 가장 큰 장점입니다.
위 표에서 알 수 있듯이 동일한 안전도를 갖을 때, RSA암호가 타원 곡선 암호(ECC)보다 암호키가 상대적으로 길고 그에 따른 비트수도 더 큰 것을 볼 수 있습니다. 우리가 컴퓨터나 스마트폰과 같은 단말기에서 같은 안전도로 더 느린 암호체계를 사용할 이유는 없을 것입니다. 떄문에 ECC는 계산 능력이 제한적일 때, 회로 공간이 제한 될 떄, 빠른 속도를 필요할 때 그 효용성이 높아집니다.
앞으로는 타원곡선 이론에 대하여 가볍게 살피고 디피-헬만 키 교환 알고리즘을 타원 곡선 상의연산으로 바꾼 알고리즘을 소개하겠습니다.
우선 대략적인 타원곡선은 위 그림을 참고해 주세요. 공통적으로는 x축에 대하여 대칭이며 수직선에 대해 최대 3개의 점과 교차합니다.
알고리즘에 대한 수학적 원리를 살펴보기 전에 타원곡선 상의 덧셈연산을 소개하려 합니다. 위 타원곡선 상에서 직선을 그었을 때, 만나는 세점을 P, Q, R로표시할 때, P와 Q를 지나는 직선이 타원과 만나는 교점을 x축으로 대칭시킨 점을 P + Q = R로 정의합니다.
덧셈에 대하여 처음에 이해가 안 가실 수 있을 것 같습니다. 우리가 지금까지 배운 수학에서 덧셈이란 1+2=3와 같은 정수간의 혹은 좌표간의 덧셈에 국한되었기 떄문입니다. 타원 곡선에서는 저희가 지금까지 배운 ‘덧셈’이란 개념을 재정의한 것입니다.
$$7\square 5=7+5\times 2-1$$
위 수식에서 연산자 $$\square $$
의 역할이 (좌항)+(우항) ×2-1인 것처럼, 위 연산자 ‘+’ 의 역할을 바꾼 거라고 생각할 수 있습니다.
실수체 상에서는 위 2개의 타원곡선이 정의됩니다.
우리는 상수항을 포함하지 않는 y2=x3-x을 자세히 보겠습니다.
여기서 P=(x1, y1), Q=(x2, y2), R=(x3, y3)라고 합시다. 타언 곡선상의 새로운 점 R을 찾는 규칙이 타원 곡선 상의 덧셈 연산입니다.
그림 a를 먼저 보면 b, c와 달리 x1, x2의 값이 다릅니다.
이 때 R의 값은 두 점을 이은 직선이 교차하는 다른 점에서 x축에 대하여 대칭이동한 값입니다.
그림 b에서는 a 와 달리 x1, x2 의 값이 동일합니다. 이 때도 접선이 교차하는 다른 점에서 x축에 대하여 대칭이동한 값입니다.
그림 c에서는 b와 같이 x좌표의 값이 동일하지만 y좌표 값이 달라 x축에 수직선이 생성된 경우입니다. O=P+(-P)로 표현하였는데, 이 때 O은 무한원점이라고 얘기합니다. 가상의 점이라고 생각하면 됩니다. 이때는 교점이 없다고 얘기하지는 않고 교점이 무한대에 있다고 정의합니다.
이제 계산식을 정리하겠습니다.
위 그래프의 일반식 y2=x3+ax+b에서는 P=(x1, y1), Q=(x2, y2), R=(x3, y3)좌표 상에서 아래와 같은 정리가 성립됩니다.
(1) 그림 a: x1≠x2일 때
$$k=\frac{(y_2-y_1)}{(x_2-x_1)}$$
$$x_3=k^2-x_1-x_2$$
$$y_3=k(x_1-x_3)-y_1$$
(2) 그림 b: y1≠0이고 P= Q일 때
$$k=\frac{(3x_1^2+a)}{2y_1}$$
$$x_3=k^2-2x_1$$
$$y_3=k(x_1-x_3)-y_1$$
(3) 그림 c: x1=x2 이고 : y2=-y1일 떄
$$O=P+Q=Q+P$$
위 정리를 알고 있으면 이제 직접 계산을 통해 타원곡선연산을 수행할 수 있습니다.
예시를 들어, y2=x3+x+2곡선 상에서 P=(3, 5), Q=(6, 7)라고 할 때 R의 값을 구해봅시다.
x1≠x2이므로 (1) 계산을 따르겠습니다.
$$k=\frac{2}{3},\ \ \ x_3=-\frac{77}{9},\ \ \ y_3=-7$$
이므로 R=P+Q=(-77/9, -7)입니다.
이제 타원곡선연산방법을 디피-헬만 키 교환 알고리즘에 적용하여 암호에 어떻게 쓰이는지 알아봅시다. 기존 디피-헬만 키 교환의 이산대수 문제를 타원 곡선 이산대수문제로 바꿉니다. 이때 타원 곡선 이산대수문제란 타원 곡선 상 임의의 점 P, Q가 있을 때 자연수 k를 사용하여 Q=kP로 나타낼 수 있는데, P와 k를 알면 Q를 구하기는 쉽지만 그 반대 연산은 힘들다는 점을 의미합니다.
이 때, 위 식에서도 타원곡선 상의 덧셈 연산이 적용되어 Q=2P인 경우, Q=P+P로 좌표 P와 P를 위 (2)처럼 연산해야 합니다.
[원활한 이해를 위하여 앨리스, 이브, 밥 모두에게 공유되는 정보는 파란색, 자신만이 갖고 있는 정보를 빨간색으로 표시하겠습니다.]
앨리스, 이브, 밥이 등장했습니다. 앨리스와 밥이 24시간 감시하는 이브를 피해 서로 같은 비밀키를 가질 수 있는 방법이 있을까요? 타원곡선 이산대수문제를 활용하여 디피-헬먼 키 교환 알고리즘을 시행해 보겠습니다.
1. 타원 곡선 E를 선택합니다.
2. 원소 Q를 선택합니다.
3. 앨리스가 개인키 a를 설정합니다.
4. 앨리스가 aQ를 계산하여 공개합니다.
5. 밥이 개인키 b를 설정합니다
6. 밥이 bQ를 계산하여 공개합니다.
7. 앨리스가 밥이 공개한 bQ를 통해 P=abQ를 계산합니다.
8. 밥이 앨리스가 공개한 aQ를 통해 P=abQ를 계산합니다.
앨리스, 밥 그리고 이브이 가지고 있는 정보들을 요약해서 정리해 봅시다
| 앨리스 | 밥 | 이브 |
| - 개인키 a - 원소 Q - 타원 곡선 E - aQ - bQ - P= abQ |
- 개인키 b - 원소 Q - 타원 곡선 E - aQ - bQ - P= abQ |
- 타원 곡선 E - 원소 Q - aQ - bQ |
앨리스와 밥은 비밀키 P를 공유합니다. 이브는 비밀키를 알기위해선 a 혹은 b의 값을 알아야 합니다. 앞서 설명했듯이 aQ 와 bQ
는 단순 곱셈이 아닌 타원곡선이산대수로 풀어야하는 덧셈이기 때문에 위 식에서 a, b를 분리하여 비밀키 abQ를 알기는 굉장히 힘듭니다.
단적인 예를 들어봅시다. 앨리스가 a=2, 밥이 b=3으로 개인키를 설정했습니다. 앨리스의 공개키 는 2Q 이고, 밥의 공개키는 3Q입니다.
여기까지는 이브도 알고 있는 사실입니다. 다만 이브에게는 비밀키 6Q를 유추하기는 힘듭니다.
이브로서는 2Q, 3Q 둘 중 하나만 원소 Q를 몇 번 ‘덧셈연산’을 진행했는지 알아야 합니다.
앨리스와 밥은 비밀키 P를 공유합니다. 이브는 비밀키를 알기위해선 a 혹은 b의 값을 알아야 합니다. 앞서 설명했듯이 aQ
와 bQ는 단순 곱셈이 아닌 타원곡선이산대수로 풀어야하는 덧셈이기 때문에 위 식에서 a, b를 분리하여 비밀키 abQ를 알기는 굉장히 힘듭니다.
위 사진을 예로 들자면, 변수 G에 대하여 그것의 합의 값을 유추하기는 힘듭니다. G를 알더라도 연산을 반복하며 겹쳐지는 구간이 존재하여 해가 여러 개 나올 수 있고, G의 값을 모를 때는 nG에 대하여 (n-2)G, (n-1)G의 값을 특정 지을 수 없어서 역연산 자체가 불가능합니다. 수많은 경우에 대하여 빠른 연산과 확률의 유추가 가능하다면 정답을 낼 확률을 높일 수는 있겠지만 모든 해커들이 그 요건을 갖추기는 힘들 것입니다.