FedTensor

ECC-6. ECDLP가 DLP보다 풀기 어려운 이유

핵심을 한 문장으로 요약하면, 전통적인 DLP를 푸는 데에는 '지름길' 같은 효율적인 공격 알고리즘이 존재하지만, ECDLP에는 아직 그런 '지름길'이 발견되지 않았기 때문입니다.문제의 구조적 차이: 왜 '지름길'이 없을까?두 문제의 난이도 차이는 이들이 정의된 수학적 공간의 근본적인 구조 차이에서 비롯됩니다.​사람 찾기 비유전통적인 DLP: 잘 정돈된 격자 도시에서 특정 번지수(h)를 가진 집을 찾는 것과 같습니다. 이 도시에는 g라는 '이동 규칙'(예: 동쪽으로 1칸, 북쪽으로 2칸)이 있고, 이 규칙을 몇 번(x) 반복하면 목표(h)에 도착하는지 알아내는 것이 문제입니다. 도시가 매우 규칙적이기 때문에, 우리는 지도를 활용하고, 구역을 나누어 탐색하는 등 효율적인 탐색 전략(지름길)을 사용할 수 있..

ECC-5. 유한체 위의 타원 곡선 이산 로그 문제(ECDLP)

암호학에서 사용되는 타원 곡선 이산 로그 문제(Elliptic Curve Discrete Logarithm Problem, ECDLP)는 반드시 유한체(Finite Field) 위에서 정의됩니다. 우리가 개념을 설명할 때 흔히 보는 부드러운 곡선 그래프는 실수(Real Numbers) 위에서 그려진 것이지만, 이를 직접 암호에 사용하지는 않습니다.실수 위가 아닌, 유한체 위의 점들암호학에 타원 곡선을 사용하기 위해서는 곡선을 이산적이고 유한한 공간으로 가져와야 합니다. 이는 모든 계산을 특정 소수 p로 나눈 나머지, 즉 모듈러 연산(Modular Arithmetic)을 통해 수행함으로써 이루어집니다.개념 (실수 위): $y^2 = x^3 + ax + b$ 방정식의 해가 되는 무한히 많은 점 (x, y)들..

ECC-4. 타원 곡선 암호(ECC)

타원 곡선(Elliptic Curve)은 이름과 달리 타원 모양이 아니며, 특정 수학 방정식을 만족하는 점들의 집합으로 정의됩니다. 이 곡선은 독특한 성질을 가지고 있어 현대 암호학에서 매우 중요한 역할을 합니다.타원 곡선이란?타원 곡선은 일반적으로 다음과 같은 형태의 방정식으로 정의됩니다.$y^2=x^3+ax+b$​여기서 a와 b는 상수이며, 곡선이 특이점(뾰족한 점이나 교차점)을 갖지 않도록$4a^3+27b^2\ne 0$​이라는 조건을 만족해야 합니다. 이 방정식의 해가 되는 모든 점 $(x, y)$와 무한 원점(point at infinity, $\mathcal{O}$)이라고 불리는 특별한 점을 포함하여 타원 곡선을 구성합니다.타원 곡선 예시(출처: 위키피디아)​ 그래프를 보면 알 수 있듯이, 타원..

이 문제의 어려움은 간단한 지름길이나 공식이 없어서, 답을 찾으려면 사실상 거의 모든 가능성을 하나하나 확인해야 한다는 데 있습니다.시계 위에서의 점프 게임먼저, 모듈러 연산을 거대한 눈금을 가진 시계라고 상상해 보겠습니다. 일반 시계는 눈금이 12개지만, 암호학에서 사용하는 시계(법, p)는 그 눈금의 수가 상상도 할 수 없을 만큼 많습니다.​쉬운 문제 (앞으로 점프하기)​3을 5번 곱하고 17로 나눈 나머지(3^5 mod 17)를 구하는 것은 쉽습니다. 이는 "17칸짜리 시계에서, 3배씩 점프하는 규칙으로 5번 뛰어라. 최종 위치는 어디인가?"와 같습니다.3^1 → 33^2 → 93^3 → 27 ≡ 10 (mod 17)3^4 → 10 * 3 = 30 ≡ 13 (mod 17)3^5 → 13 * 3 = ..