타원 곡선 암호 방식

타원 곡선 암호 방식(ECC)은 타원 곡선 상의 점들로 이루어진 군(group)을 기반으로 공개 키 암호 방식을 구현하며, RSA 또는 유한체 디피-헬만(Diffie-Hellman)과 동일한 수준의 보안을 훨씬 작은 키로 달성합니다.

Definition

타원 곡선 암호 방식은 유한체 상의 타원 곡선 점들의 집합을 기본 군으로 하는 공개 키 암호 방식이며, 그 보안은 타원 곡선 이산 로그 문제의 난이도에 기반합니다.

Scope

이 주제는 유한체 상의 타원 곡선 군 법칙, 타원 곡선 이산 로그 문제, 그리고 이를 기반으로 구축된 방식들(타원 곡선 디피-헬만(ECDH), ECDSA 및 EdDSA 서명 방식, Curve25519와 같은 현대 곡선)을 다룹니다. 또한 타원 곡선 이산 로그가 유한체 이산 로그보다 어려운 이유(준지수적 지수 계산법(subexponential index calculus)의 부재)와 ECDSA에서 논스(nonce) 재사용과 같은 구현상의 문제점들을 다룹니다. 이 주제는 자매 주제에서 다루는 RSA 및 유한체 이산 로그 방식은 제외합니다.

Core questions

• 타원 곡선 상의 점들의 기하학적 덧셈이 어떻게 암호학적 군을 형성하는가?
• 타원 곡선 이산 로그가 유한체 아날로그보다 어려워서 더 작은 키를 허용하는 이유는 무엇인가?
• 타원 곡선 상에서 디피-헬만과 디지털 서명은 어떻게 구현되는가?
• Curve25519와 같은 현대 곡선이 기존 NIST 곡선보다 구현하기에 더 안전한 이유는 무엇인가?
• ECDSA에서 서명별 논스 고유성이 왜 중요한가?

Key concepts

• 타원 곡선 군 법칙
• 스칼라 곱셈
• 타원 곡선 이산 로그 문제
• ECDH
• ECDSA
• EdDSA 및 Ed25519
• Curve25519
• 논스 재사용 취약점
• 키 크기 대 RSA

Key theories

타원 곡선 이산 로그 문제

곡선 상의 점 P와 Q = kP가 주어졌을 때, 스칼라 k를 복구하는 것은 잘 선택된 곡선의 경우 완전 지수적인 노력이 필요하다고 여겨지는데, 이는 유한체 이산 로그를 약화시키는 지수 계산법 공격이 적용되지 않기 때문입니다.

동일한 보안을 위한 더 작은 키

타원 곡선 이산 로그에 대한 최상의 공격은 일반적인 제곱근 알고리즘이기 때문에, 256비트 타원 곡선은 대략 128비트 보안을 제공하며, 이는 3072비트 RSA와 유사하여 더 빠른 연산과 더 작은 키 및 서명을 가능하게 합니다.

Mechanisms

유한체 상의 타원 곡선 점들은 기하학적 덧셈 법칙에 따라 아벨 군(abelian group)을 형성합니다. 기본 점 P를 k번 반복하여 더하는 것(스칼라 곱셈, kP)은 효율적이지만, kP로부터 k를 복구하는 것은 어려운 문제입니다. ECDH는 기본 점의 스칼라 배수를 교환하여 디피-헬만을 수행합니다. ECDSA와 EdDSA는 메시지별 스칼라(논스)로부터 서명을 생성하는데, 이 논스가 반복되거나 예측 가능할 경우 개인 키가 유출될 수 있음이 여러 실제 침해 사례를 통해 입증되었습니다.

Clinical relevance

ECC는 새로운 시스템에서 기본 공개 키 선택으로 자리 잡고 있습니다. ECDHE는 TLS 1.3에서 전방향 비밀 키 교환(forward-secret key exchange)을 제공하며, Ed25519는 SSH 키, 소프트웨어 업데이트 및 인증서에 서명하고, Curve25519는 Signal, WireGuard 및 최신 메시징을 보호합니다. 작은 키 크기와 빠른 연산 속도는 모바일 장치, 스마트 카드 및 제한된 IoT 하드웨어에 적합합니다.

Evidence & guidelines

ECDSA는 FIPS 186에, ECDH는 NIST SP 800-56A에, EdDSA/Ed25519는 RFC 8032에 표준화되어 있습니다. Curve25519/X25519는 RFC 7748에 표준화되어 있습니다. 현대의 관행은 구현상의 함정에 대한 저항성 때문에 Edwards 곡선과 X25519를 선호합니다. 논스 재사용 시 ECDSA의 취약점(특히 2010년 Sony PlayStation 3 키 추출 사건)은 경고적인 표준 사례입니다.

History

Neal Koblitz와 Victor Miller는 1985-1987년에 독립적으로 암호학에 타원 곡선을 사용할 것을 제안했습니다. 특허 및 신뢰 문제, NIST 곡선의 복잡성으로 인해 초기 채택은 더뎠지만, 2010년대에 키 크기 효율성이 더욱 중요해지고 Bernstein의 Curve25519(2006)와 Ed25519가 빠르고 오용에 강한 설계를 제공하면서 ECC는 지배적인 위치를 차지하게 되었고 현재 널리 배포되고 있습니다.

Key figures

• Neal Koblitz
• Victor Miller
• Daniel J. Bernstein
• Alfred Menezes
• Scott Vanstone

Seminal works

• koblitz1987
• hankerson2004
• katz2020

Frequently asked questions

256비트 타원 곡선 키가 3072비트 RSA 키와 일치하는 이유는 무엇인가요?

타원 곡선 이산 로그에 대한 가장 잘 알려진 공격은 일반적이며 군 크기의 제곱근에 비례하는 시간이 소요되는 반면, 인수분해 및 유한체 이산 로그에는 더 빠른 준지수적 알고리즘이 존재합니다. 따라서 타원 곡선은 동일한 보안 수준을 위해 훨씬 적은 비트를 필요로 합니다.

NIST 타원 곡선은 신뢰할 수 있나요?

표준 NIST P-곡선은 널리 사용되며 깨진 것으로 알려져 있지 않지만, 설명되지 않은 상수 선택과 구현의 어려움으로 인해 많은 사람들이 Curve25519 및 Ed25519를 선호하게 되었습니다. 이들은 투명한 설계 근거를 가지며 일정한 시간(constant time) 내에 안전하게 구현하기 더 쉽습니다.