타원곡선 암호는 finite field 위의 곡선 점들이 이루는 Abelian group을 사용한다. 정수 곱셈군의 DLP 대신 Elliptic Curve Discrete Logarithm Problem을 기반으로 하며, 같은 기본 구조로 key exchange, encryption, signature를 구성할 수 있다.
Elliptic Curve
characteristic가 2와 3이 아닌 field 위에서 짧은 Weierstrass form은
이다. 곡선이 singular하지 않으려면
이어야 한다. 이 조건은 cusp나 self-intersection 없이 tangent가 잘 정의되도록 한다.
곡선의 점 집합에 point at infinity 를 추가하여
로 둔다.
Geometric Point Addition
실수 위에서 서로 다른 두 점 를 지나는 직선은 곡선과 세 번째 점 에서 만난다. 이를 축에 대칭한 점을 로 정의한다. 즉 한 직선 위의 세 교점은
를 만족한다.
는 항등원이고 이다.
Addition Formula
, , 이면
이고
로 이다. Finite field에서는 division을 modular inverse로 해석한다.
Point Doubling
이면 tangent의 기울기를 사용한다.
그리고 같은 좌표 공식을 적용한다. 이면 tangent가 수직이므로
이다.
이 연산은 결합법칙을 만족하여 를 Abelian group으로 만든다. 결합법칙의 직접 대수적 증명은 길지만, algebraic geometry의 divisor 이론에서 자연스럽게 설명된다.
Elliptic Curves over Finite Fields
위에서는 가능한 마다 오른쪽 값이 quadratic residue인지 확인하여 점을 센다. 모든 점과 는 유한 Abelian group을 이룬다.
Hasse’s Bound는 점의 수를
로 제한한다. 즉 점의 수는 대략 와 비슷하지만 정확히 같지는 않다.
Scalar Multiplication과 ECDLP
정수 에 대해
로 정의한다. Double-and-add를 사용하면 번의 point operation으로 계산할 수 있다.
공개된 에서 를 구하는 문제를 ECDLP라고 한다. 일반적인 최선의 공격은 대략 square-root complexity를 가지며, finite field multiplicative group에서 가능한 index calculus와 같은 subexponential 공격이 일반 타원곡선에는 알려져 있지 않다.
ECDH
공개 매개변수는 큰 prime order 를 가진 base point 이다.
- Alice: private , public
- Bob: private , public
공유점은
이다. 실제 key는 공유점의 좌표를 그대로 쓰지 않고 key derivation function에 입력한다. 공개점 검증과 인증이 없으면 finite-field DH와 마찬가지로 MITM이나 invalid-curve attack이 가능하다.
Elliptic Curve ElGamal
메시지를 curve point 으로 encoding한다고 하자. 수신자의 public key가 이면 송신자는 nonce 를 골라
를 보낸다. 수신자는
으로 복호화한다.
실제 시스템에서는 임의 메시지를 곡선점에 직접 매핑하는 대신 hybrid encryption으로 ephemeral ECDH key를 만들고 symmetric encryption을 사용하는 방식이 일반적이다.
ECDSA
order가 prime 인 base point , private key , public key 를 사용한다. digest를 라 하자.
서명자는 nonce 를 골라
를 계산하고
로 둔다.
검증자는
를 계산하고
의 좌표 modulo 가 인지 확인한다.
정확성
이므로
이다. 따라서
이고 검증값이 일치한다.
ECDSA도 nonce 재사용 또는 bias에 매우 취약하다. 두 서명에서 같은 이 나타나면 nonce 재사용을 의심해야 한다.
왜 ECC는 작은 키를 사용하는가
Finite-field DLP에는 index calculus 계열의 subexponential algorithm이 존재하지만 일반적인 ECDLP에는 알려져 있지 않다. 따라서 비슷한 공격 비용을 만들기 위해 필요한 group size가 더 작다. 다만 실제 안전성은 curve 선택, subgroup order, point validation, side-channel 방어, nonce 생성에 달려 있다.
정리
타원곡선의 점 덧셈은 기하학적 secant–tangent rule에서 정의되며 finite field에서도 대수식으로 계산된다. Scalar multiplication은 쉽지만 ECDLP는 어렵다. 이 비대칭성으로 ECDH, EC ElGamal, ECDSA를 구성한다.
연습 문제
- 에서 의 를 구한다.
- ECDH에서 양쪽 공유점이 같은 이유를 보인다.
- EC ElGamal의 복호화 식을 증명한다.
풀이
1번
이다. 따라서
이므로 이다.
2번
Scalar multiplication은 정수 곱에 대해 결합적이므로
이다.
3번
이다.