elikaski/ecc_attacks타원 곡선 암호화에 대한 알려진 공격
최근 몇 년 동안 타원곡선 암호(Elliptic Curve Cryptography) 방식은 높은 효율성과 강력한 보안성 덕분에 널리 사용되고 있습니다. 이 글의 목적은 이 주제를 현재 인터넷에 존재하는 것보다 비교적 더 명확하게 제시하는 것입니다.
이 글에서 나는 타원곡선이 무엇인지, 타원곡선에서 수행할 수 있는 기본 연산들, 그리고 이들이 암호학적 맥락에서 어떻게 사용될 수 있는지를 소개하겠습니다. 이 글의 대부분은 잘못된 구현이나 잘못된 사용에 대한 알려진 공격 사례로 구성됩니다. 글 전반에 걸쳐 나는 설명을 직관적이고 높은 수준의 부분과 더 자세한 내용을 다루는 수학적 부분으로 나누려고 합니다. 독자께서는 해당 위치에서 자신이 관심 있는 부분에 집중하고 덜 관심 있는 부분은 건너뛰셔도 좋습니다.
즐거운 읽기 되세요!
일반적으로 타원곡선은 일종의 곡선입니다. 그 예로는 방정식의 형태가 $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ 인 포물선이 있으며, 다음과 같이 생겼습니다:
암호학적 맥락에서는 다음과 같은 형태의 방정식을 갖는 타원곡선을 사용하는 것이 일반적입니다.
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
예를 들어, 방정식 $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ 에 해당하는 타원곡선은 다음과 같습니다:
곡선의 방정식은 곡선 위 점의 𝑥 좌표와 𝑦 좌표 사이의 관계를 정의합니다. 암호학적 맥락에서 우리는 𝑥, 𝑦, 𝑎, 𝑏 를 정수로 제한하고, 계산을 어떤 큰 소수로 나눈 나머지(modulo)로 제한합니다. 따라서 타원곡선의 방정식은 다음과 같습니다:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
이는 곡선 위에 유한한 수의 점이 존재한다는 것을 의미합니다. 수학적 언어로는 곡선이 위수 𝑝 인 유한체 위에 정의된다고 말합니다. 그 결과 이제 모든 𝑥 좌표에 곡선 위의 점이 반드시 대응되지는 않습니다. 그에 대응하는 𝑦 좌표가 정수가 아닐 수 있기 때문입니다.
곡선 위의 점들의 집합은 곡선의 방정식을 만족하는 정수 쌍 (𝑥, 𝑦) 들로 구성됩니다. 이러한 점들 외에도 "무한대(Infinity)"라고 불리는 또 다른 특별한 점이 정의되며, 이는 𝒪 로 표기됩니다. 수학적 언어로 이 점은 덧셈 연산에 관한 곡선 위 점들 집합의 항등원(neutral element)입니다. 덧셈 연산은 다음 섹션에서 정의하겠습니다. 곡선 위의 점의 수(점 𝒪 포함)를 "곡선의 위수(order of the curve)"라고 합니다.
또 다른 관찰로는 타원곡선이 X 축에 대해 대칭이라는 것입니다. 즉, 점 $𝑃 = (𝑥, 𝑦)$ 가 곡선 위에 있다면 점 $−𝑃 = (𝑥, −𝑦)$ 도 곡선 위에 있습니다. 실제로 이 점들은 서로의 "역원(inverse)"으로 간주되며(따라서 두 번째 점에 대해 −𝑃 로 표기), 이들 사이의 덧셈 연산 결과는 항등원 𝒪 로 정의됩니다.
Hasse의 정리라고 불리는 정리는 곡선의 위수인 #𝐸 에 대한 추정치를 제공하며, 그 크기는 Θ(𝑝) 입니다. 더 정확하게는:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
곡선 위의 두 점이 주어지면, 그들 사이의 덧셈 연산을 정의할 수 있으며, 그 결과는 곡선 위에 있는 세 번째 점이 됩니다. 이 점을 기하학적으로 찾으려면, 주어진 두 점 사이에 직선을 그리고 곡선과 세 번째 점에서 교차할 때까지 연장합니다. 이 점을 𝑋 축에 대해 대칭 이동한 점이 덧셈의 결과로 정의됩니다.
다음은 점 𝑃 와 𝑄 가 주어졌을 때 점 $𝑃 + 𝑄$ 를 어떻게 찾을 수 있는지 보여주는 다이어그램입니다:
이 설명에서 생길 수 있는 질문은 두 점 사이에 그린 직선이 곡선과 다시 교차하지 않으면 어떻게 되는가입니다. 이 경우 직선이 "무한대"에서 곡선과 교차한다고 말하며, 덧셈의 결과는 점 𝒪 입니다. 이 경우는 그린 직선이 수직일 때 발생합니다. 즉, 점 𝑃 를 그 역점인 −𝑃 와 더하려고 할 때입니다:
이로부터 두 가지 기본 항등식이 도출됩니다. 모든 점 𝑃 에 대해 다음이 성립합니다:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
기하학적 설명에서 생기는 또 다른 질문은 점을 자기 자신에 어떻게 더하는가입니다. 서로 다른 두 점 𝑃 와 𝑄 를 더하기 위해 두 점 사이에 직선을 그리고 그 연장선과 곡선의 교차점을 본다는 것을 확인했습니다. 직관적으로, 𝑃 를 고정시켜 두고 𝑄 가 𝑃 와 "점점 더 가까워지도록" 이동하면서 𝑄 가 𝑃 와 합쳐질 때까지 생기는 직선을 보겠습니다. 우리가 얻는 것은 점 𝑃 에서 곡선에 점점 더 "접하는" 직선이며, 이것이 바로 𝑃 를 자기 자신에 더할 때 보게 될 직선입니다:
점 𝑃 를 자기 자신에 더하려면 점 𝑃 에서 곡선에 접선을 그리고, 곡선과 두 번째 점에서 교차할 때까지 연장합니다. 이 점을 𝑋 축에 대해 대칭 이동한 점이 덧셈의 결과로 정의됩니다. 덧셈의 결과를 $𝑃 + 𝑃 = 2𝑃$ 로 표기하는 것이 일반적입니다. 다시 말하지만, 접선이 곡선과 두 번째 점에서 교차하지 않으면 "무한대"에서 곡선과 교차한다고 말하며, 이 경우 덧셈의 결과는 점 𝒪 입니다.
이러한 시각적 기하학적 설명은 점 덧셈이 어떻게 작동하는지 훌륭하게 보여주고 이해를 돕습니다. 하지만 실제로는 어떻게 계산할까요? 물론 수학 방정식입니다!
점 $𝑃 = (𝑥_𝑃, 𝑦_𝑃)$ 와 $𝑄 = (𝑥_𝑄, 𝑦_𝑄)$ 가 주어졌을 때, 덧셈의 결과는 $𝑅 = (𝑥_𝑅, 𝑦_𝑅)$ 이며 다음과 같습니다:
$𝑥_𝑅 = 𝜆^2 − 𝑥_𝑃 − 𝑥_𝑄\ \ \ \ \ \ \ \ \ (mod\ 𝑝)$
$𝑦_𝑅 = 𝜆(𝑥_𝑃 − 𝑥_𝑅) − 𝑦_𝑃\ \ \ \ (mod\ 𝑝)$
여기서 𝜆 는 두 점이 서로 다른 경우 두 점을 연결하는 직선의 기울기로 정의되고, 점이 자기 자신에 더해지는 경우 곡선의 그 점에서의 접선의 기울기로 정의됩니다. 공식적으로는:
$\displaystyle𝜆 = \frac{𝑦_𝑃 − 𝑦_𝑄}{𝑥_𝑃 − 𝑥_𝑄}\ \ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 ≠ 𝑄$
$\displaystyle𝜆 = \frac{3{𝑥_𝑃}^2 + 𝑎}{2𝑦_𝑃}\ \ \ \ (mod\ 𝑝)\ \ \ ;\ \ \ 𝑖𝑓 𝑃 = 𝑄$
점 덧셈 뒤의 수학적 계산은 이 글의 나머지 부분에 중요하지 않습니다. 그런 의미에서 우리는 점 덧셈을 곡선 위의 두 점을 받아 곡선 위에 있는 세 번째 점을 반환하는 블랙박스로 볼 수 있습니다.
점 𝑃 를 자기 자신에 더할 수 있고, 그 결과 점을 2𝑃 로 표기한다는 것을 확인했습니다. 이 결과에 다시 점 𝑃 를 더하면 3𝑃 로 표기되는 점에 도달하고, 이런 식으로 계속됩니다. 이러한 방식으로 점을 반복적으로 자기 자신에 더함으로써(숫자 간의 곱셈과 유사하게) 점을 상수로 "곱하기"를 정의할 수 있습니다:
$𝑛𝑃 = 𝑃 + 𝑃 + ⋯ + 𝑃\ \ \ \ \ (n\ times)$
겉보기에는 점을 숫자 𝑛 으로 곱하려면 점 사이의 덧셈 연산을 𝑛 번 수행해야 하는 것처럼 보입니다. 이는 시작점이 주어졌을 때 "한 단계씩" 도달하지 않고서는 "마지막" 점이 어디에 위치할지 미리 알기 어렵기 때문입니다. 𝑛 이 매우 클 수 있으므로 이러한 계산은 매우 비효율적일 것입니다.
이를 위해 Double And Add 알고리즘이 존재합니다. 이 알고리즘에서는 점 𝑃 에서 시작하여 𝑛 의 이진 표현에서 각 비트에 대해 현재 점을 2 로 곱하고(즉, 자기 자신에 더하고), 비트 값이 1 이면 결과에 더합니다. 이 알고리즘의 실행 시간 복잡도는 $𝑂(log 𝑛)$ 이며, 매우 큰 수로 점을 효율적으로 곱할 수 있게 해줍니다.
나중에 사용할 점 곱셈의 중요한 속성은 모든 점 𝑃 와 숫자 쌍 𝑎, 𝑏 에 대해 다음이 성립한다는 것입니다:
$𝑏(𝑎𝑃) = (𝑏𝑎)𝑃 = (𝑎𝑏)𝑃 = 𝑎(𝑏𝑃)$
직관적으로, 점 𝑃 에서 시작하여 그로부터 𝑎 단계를 이동해 점 𝑎𝑃 에 도달한다고 가정해 봅시다. 이 점에서 "크기" 𝑎 의 단계를 𝑏 번 이동하여 점 $𝑏(𝑎𝑃)$ 에 도달합니다. 또는 다른 시나리오에서는 점 𝑃 에서 시작하여 𝑏 단계를 이동해 점 𝑏𝑃 에 도달할 수 있습니다. 이 점에서 "크기" 𝑏 의 단계를 𝑎 번 이동하여 점 $𝑎(𝑏𝑃)$ 에 도달합니다.
두 시나리오 모두에서 점 𝑃 로부터 총 동일한 양의 𝑎𝑏 단계를 이동했으므로, 두 시나리오 모두에서 동일한 최종 점에 도달했습니다. 수학적으로, 점을 상수로 곱하는 것은 결합 법칙이 성립합니다.
점 𝑃 에서 시작하여 그것을 계속해서 반복적으로 더하면, 각 단계마다 곡선 위의 어떤 새로운 점에 도달하게 됩니다. 곡선 위에는 유한한 수의 점이 있기 때문에, 어떤 단계에서는 이전에 도달했던 점들에 다시 도달하게 되고, 일종의 루프 또는 "원(circle)" 안에 있게 됩니다. 더 정확히 말하면, 어떤 단계에서는 점 -𝑃 에 도달하고, 다음 단계에서는 점 𝒪 에 도달하며, 그 다음 단계에서는 우리가 시작했던 점 𝑃 에 다시 도달하게 됩니다.
이러한 "원"을 만드는 점을 생성자(Generator)라고 합니다. 전체 "원"이 그 점으로부터 생성될 수 있기 때문이며, 보통 문자 𝐺 로 표기합니다. "원" 안의 점의 수(점 𝒪 포함)를 "생성자 𝐺 의 위수(order)"라고 하며, 보통 𝑛 으로 표기합니다. 곡선 위의 각 점은 어떤 종류의 "원"을 형성합니다. 수학적으로 이 "원" 위의 점들의 집합은 순환군(cyclic group)입니다.
이로부터 나오는 흥미로운 속성은 점 𝐺 에 그 위수 𝑛 을 곱하면 무한대의 점이 된다는 것입니다:
𝑛𝐺 = 𝒪
"점 𝑃 와 𝑄 가 어떤 𝑥 에 대해 $𝑄 = 𝑥𝑃$ 를 만족할 때, 𝑥 를 찾는 것은 어렵다."
말로 표현하면, 어떤 사람이 어떤 시작점에서 출발하여 그 지점에서 일정한 수의 단계를 이동해 최종 점에 도달했다고 가정해 봅시다. 시작점과 최종 점이 주어졌을 때, 그들이 몇 단계를 이동했는지 어떻게 알 수 있을까요?
이 질문에 대한 답은 그렇게 직관적이지 않습니다. 시작점에서 단계를 이동하여 어떤 점들에 도달할지 미리 예측하기 어렵기 때문입니다. 순진한 해결책은 우리 자신이 𝑃 에서 시작하여 그 지점에서 한 번에 한 단계씩 앞으로 나아가며 𝑄 에 도달할 때까지 이동한 단계 수를 세는 것입니다. 이 해결책의 복잡도는 $𝑂(𝑥)$ 이며, 𝑥 가 큰 수임이 알려진 경우, 예를 들어 𝑥 가 256 bit 인 경우 실행 불가능합니다.
이 문제를 타원곡선 이산 로그 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)라고 하며, 이는 어려운 문제입니다. 하지만 얼마나 어려울까요?
암호학적 맥락에서는 "문제의 어려움" 또는 "암호 시스템의 강도"를 Security Level 이라는 지표로 측정하는 것이 일반적입니다. 이 지표에서 어떤 문제가 $𝑂(2^𝑛)$ 단계로 해결하는 가장 잘 알려진 공격이 있다면 그 문제는 "𝑛 비트 보안"을 가진다고 말합니다.
