타원곡선 암호

3. 이론

공개 키 암호 방식은 계산 복잡도 이론에 기반을 둔다. 이론적으로는 유한한 시간 안에 계산이 가능하지만, 실제로는 매우 오랜 시간이 걸리는 특성을 이용한다. 초기 공개 키 암호 방식은 큰 정수를 소수로 나누는 것이 어렵다는 점을 이용했다. 타원곡선 암호는 알려진 특정한 점에 대한 무작위 타원 곡선의 이산 로그를 찾는 것이 어렵다는 점을 이용한다.^[5]

타원곡선 암호의 보안은 타원 곡선 점 곱셈을 계산하는 것은 쉽지만, 원래 점과 곱셈 점이 주어졌을 때 곱셈자를 계산하는 것은 어렵다는 점에 기반한다. 곡선 방정식을 만족하는 이산 정수 쌍의 총 개수로 측정되는 타원 곡선의 크기는 문제의 난이도를 결정한다.

타원 곡선 암호는 RSA와 같은 기존 방식에 비해 더 작은 키 크기로 동일한 보안 수준을 제공하여 저장 및 전송 요구 사항을 줄일 수 있다는 장점이 있다. 예를 들어, 256비트 타원 곡선 공개 키는 3072비트 RSA 공개 키와 유사한 보안 수준을 제공한다.^[5]

3. 1. 타원 곡선의 정의

• $\backslash tilde\{f\}\_p(O)\; =\; O$
• $\backslash tilde\{f\}\_p(x,y)\; =\; (f\_p(x),f\_p(y))$

3. 2. 타원 곡선 위의 연산

• 먼저, $P\_1\; +\; O\; =\; O\; +\; P\_1\; =\; P\_1$이다. 즉, 무한원점 $O$가 영원이다.
• 만약 $x\_1\; =\; x\_2,\; y\_1\; =\; -\; y\_2$라면, $P\_1\; +\; P\_2\; =\; O$이다. 이 때 $P\_2$를 $-P\_1$로 쓰고, $P\_1$의 역원이라고 부른다.
• 그 외의 경우, $P\_1\; +\; P\_2$는, 두 점 $P\_1,\backslash ,P\_2$를 지나는 직선과 $E$와의($P\_1$ 및 $P\_2$와 다른) 교점의 y좌표의 부호를 반전시킨 것이다. 즉 $P\_3\backslash ,(x\_3,y\_3)\; =\; P\_1\; +\; P\_2$라고 놓으면, 다음과 같이 계산된다.

• 영원 $O$의 존재
• 각 원소 $P\_1$에 대한 역원 $-P\_1$의 존재
• 교환성: $P\_1\; +\; P\_2\; =\; P\_2\; +\; P\_1$ (정의식의 대칭성으로부터 명백함)
• 결합성: $(P\_1\; +\; P\_2)\; +\; P\_3\; =\; P\_1\; +\; (P\_2\; +\; P\_3)$ (번잡하지만 정의식을 주의 깊게 풀면 증명할 수 있다)

• 이 경우, 먼저 $y\_1\; =\; 0$일 때는, $2P\_1\; =\; O$이다. 또한, $2O\; =\; O+O\; =\; O$이다.
• 그 외의 경우에는, $2\; P\_1$는, $P\_1$에서의 $E$의 접선이 $E$ 자신과 교차하는 ($P\_1$과 다른) 교점의 $y$좌표의 부호를 반전시킨 것이다. 즉 $P\_4\backslash ,\; (x\_4,\backslash ,\; y\_4)\; =\; 2\; P\_1$로 두면, 다음과 같이 계산된다.

3. 3. 이산 로그 문제

3. 4. 디피-헬만 문제

4. 구현

타원곡선 암호(ECC) 구현에는 몇 가지 고려해야 할 사항이 있다.

먼저, 모든 참여자는 타원 곡선을 정의하는 도메인 매개변수에 동의해야 한다. 도메인 매개변수는 NIST나 SECG 등 표준 기관에서 제공하는 것을 사용하거나, 자체적으로 생성할 수 있다. 자체 생성 시에는 곡선 상의 점의 수 계산이 필요하며, 취약한 곡선을 피해야 한다.

타원 곡선 연산의 효율성을 위해 다양한 좌표계(사영, 야코비안, 로페즈-다합 등)를 사용할 수 있다. 특히, 의사 메르센 소수를 사용하면 모듈로 감소 연산을 빠르게 수행할 수 있어, 비트 연산을 사용하는 컴퓨터 환경에서 효율적이다.

암호화 및 복호화 과정에는 스칼라 곱셈 연산(Q=dP)이 필요하며, 이는 Binary 방식 등을 통해 효율적으로 수행할 수 있다. 하지만 스칼라 곱셈 연산은 부채널 공격(SPA, DPA)에 취약하므로 주의해야 한다.

다음은 타원곡선 암호 구현과 관련된 주요 라이브러리 및 도구 목록이다.

• OpenSSL
• NSS
• Crypto++
• MIRACL
• seccure
• SKS
• eccGnuPG
• Curve25519
• TinyECC
• libecc
• Bouncy Castle

4. 1. 도메인 파라미터

• NIST, [https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf 정부 사용 권장 타원 곡선]
• SECG, [http://www.secg.org/sec2-v2.pdf SEC 2: 권장 타원 곡선 도메인 매개변수]
• ECC Brainpool, [http://www.ecc-brainpool.org/download/Domain-parameters.pdf ECC Brainpool 표준 곡선 및 곡선 생성]^[14][15]

• 임의의 곡선을 선택하고 일반적인 점 계산 알고리즘 (예: Schoof의 알고리즘 또는 Schoof–Elkies–Atkin 알고리즘) 사용.
• 점의 수를 쉽게 계산할 수 있는 패밀리에서 임의의 곡선을 선택하거나 (예: Koblitz 곡선).
• ''복소수 곱셈'' 기술을 사용하여 점의 수를 선택하고 이 점의 수로 곡선을 생성한다.^[17]

• 소수가 아닌 ''m''을 갖는 $\backslash mathbb\{F\}\_\{2^m\}$ 위의 곡선은 바일 강하 공격에 취약하다.^[18][19]
• ''n''이 충분히 작은 ''B''에 대해 $p^B-1$을 나누는 곡선 (여기서 ''p''는 필드의 특성이다: 소수 필드의 경우 ''q'', 이진 필드의 경우 $2$)는 메네제스–오카모토–반스톤 (MOV) 공격에 취약하다.^[20][21] 이 공격은 ECDLP를 해결하기 위해 $\backslash mathbb\{F\}\_p$의 작은 차수 확장 필드에서 일반적인 이산 대수 문제 (DLP)를 적용한다. 바운드 ''B''는 필드 $\backslash mathbb\{F\}\_\{p^B\}$에서 이산 로그를 계산하는 것이 타원 곡선 $E(\backslash mathbb\{F\}\_q)$에서 이산 로그를 계산하는 것만큼 어렵도록 선택해야 한다.^[22]
• $|E(\backslash mathbb\{F\}\_q)|\; =\; q$인 곡선은 곡선 상의 점을 $\backslash mathbb\{F\}\_q$의 가산 그룹에 매핑하는 공격에 취약하다.^[23][24][25]

4. 2. 표준 곡선

각 소수 필드에 대해 하나의 타원 곡선이, 각 이진 필드에 대해 하나의 타원 곡선과 하나의 코블리츠 곡선이 권장된다. NIST 권장 사항에는 총 5개의 소수 곡선과 10개의 이진 곡선이 포함되어 있으며, 이 곡선들은 최적의 보안과 구현 효율성을 위해 선택되었다.^[4]

국가안보국(NSA)은 스위트 B에서 키 교환을 위한 ECDH와 디지털 서명을 위한 ECDSA를 승인했다. NSA는 384비트 키를 사용하여 최고 기밀까지의 기밀 정보를 보호하는 데 이를 사용할 수 있도록 허용한다.^[6]

타원 곡선 암호(ECC)를 사용하려면 모든 당사자가 타원 곡선을 정의하는 모든 요소, 즉 체계의 ''도메인 매개변수''에 동의해야 한다. 사용되는 필드의 크기는 일반적으로 소수(p로 표시)이거나 2의 거듭제곱($2^m$)이다. 필드는 소수 케이스에서는 ''p''로 정의되고 이진 케이스에서는 ''m''과 ''f''의 쌍으로 정의된다. 타원 곡선은 정의 방정식에 사용된 상수 ''a''와 ''b''로 정의된다. 마지막으로, 순환 부분군은 생성자(기저점) ''G''로 정의된다. 암호 응용 프로그램의 경우, ''G''의 차수는 일반적으로 소수 ''n''이다. ''n''은 $E(\backslash mathbb\{F\}\_p)$의 부분군의 크기이므로 라그랑주 정리에 따라 숫자 $h\; =\; \backslash frac\{1\}\{n\}|E(\backslash mathbb\{F\}\_p)|$는 정수이다. 암호 응용 프로그램에서 이 숫자 ''h''(''코팩터'')는 작아야($h\; \backslash le\; 4$) 하며, 가급적이면 $h\; =\; 1$이어야 한다. 요약하면, 소수 케이스에서 도메인 매개변수는 $(p,a,b,G,n,h)$이고, 이진 케이스에서는 $(m,f,a,b,G,n,h)$이다.

도메인 매개변수가 사용과 관련하여 신뢰할 수 있는 당사자에 의해 생성되었다는 보장이 없는 한, 도메인 매개변수는 사용 전에 ''반드시'' 검증해야 한다.

도메인 매개변수를 생성하는 것은 곡선 상의 점의 수 계산을 포함하며 시간 소모적이고 구현하기 어렵기 때문에 일반적으로 각 참여자가 수행하지 않는다. 그 결과, 여러 표준 기관에서 몇 가지 일반적인 필드 크기에 대한 타원 곡선의 도메인 매개변수를 게시했다. 이러한 도메인 매개변수는 "표준 곡선" 또는 "명명된 곡선"으로 알려져 있으며, 명명된 곡선은 이름이나 표준 문서에 정의된 고유한 객체 식별자로 참조할 수 있다.

• NIST, [https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf 정부 사용 권장 타원 곡선]
• SECG, [http://www.secg.org/sec2-v2.pdf SEC 2: 권장 타원 곡선 도메인 매개변수]
• ECC Brainpool, [http://www.ecc-brainpool.org/download/Domain-parameters.pdf ECC Brainpool 표준 곡선 및 곡선 생성]^[14][15]

4. 3. 효율적인 연산

• 사영(projective) 시스템: 각 점이 세 개의 좌표 \\((X,Y,Z)\\)로 표현되며, \\(x = \frac{X}{Z}\\), \\(y = \frac{Y}{Z}\\) 관계를 사용한다.
• 야코비안(Jacobian) 시스템: 점은 세 개의 좌표 \\((X,Y,Z)\\)로 표현되지만, \\(x = \frac{X}{Z^2}\\), \\(y = \frac{Y}{Z^3}\\) 관계가 사용된다.
• 로페즈-다합(López-Dahab) 시스템: \\(x = \frac{X}{Z}\\), \\(y = \frac{Y}{Z^2}\\) 관계를 사용한다.
• 수정된 야코비안 시스템: 동일한 관계가 사용되지만 네 개의 좌표 \\((X,Y,Z,aZ^4)\\)가 저장되고 계산에 사용된다.
• 추드노프스키(Chudnovsky) 야코비안 시스템: 다섯 개의 좌표 \\((X,Y,Z,Z^2,Z^3)\\)가 사용된다.

5. 보안 및 공격

2013년, 뉴욕 타임스는 Dual Elliptic Curve Deterministic Random Bit Generation(Dual_EC_DRBG)가 NSA의 영향으로 NIST 국가 표준으로 포함되었으며, NSA는 해당 알고리즘과 권장 타원 곡선에 의도적인 약점을 포함시켰다고 보도했다.^[7] RSA 시큐리티(RSA Security)는 2013년 9월, 고객들에게 Dual_EC_DRBG 기반의 모든 소프트웨어 사용을 중단할 것을 권고하는 권고안을 발표했다.^[8][9] Dual_EC_DRBG가 "NSA의 은밀한 작전"으로 드러나면서, 암호학 전문가들은 NIST가 권장하는 타원 곡선의 보안에 대해서도 우려를 표명하며, 타원 곡선이 아닌 그룹 기반의 암호화로 복귀할 것을 제안했다.^[10]

암호학 전문가들은 미국 국가안보국(NSA)이 적어도 하나의 타원 곡선 기반 의사 난수 생성기에 암호화 백도어를 삽입했다는 우려를 표명했다.^[37] 전 NSA 계약자 에드워드 스노든이 유출한 내부 메모에 따르면 NSA는 Dual EC DRBG 표준에 백도어를 삽입했다.^[38] 가능한 백도어에 대한 한 분석에 따르면 알고리즘의 비밀 키를 가진 공격자는 32바이트의 PRNG 출력만으로 암호화 키를 얻을 수 있었다고 결론 내렸다.^[39]

SafeCurves 프로젝트는 안전하게 구현하기 쉽고 백도어의 가능성을 최소화하기 위해 완전히 공개적으로 검증할 수 있는 방식으로 설계된 곡선을 목록화하기 위해 시작되었다.^[40]

가상 머신에서 타원 곡선 암호(ECC)를 사용할 때, 공격자는 유효하지 않은 곡선을 사용하여 전체 PDH 개인 키를 얻을 수 있다.^[47]

5. 1. 보안 강도

5. 2. 부채널 공격

5. 3. 양자 컴퓨터 공격

6. 응용

타원 곡선 암호의 사용은 1985년 닐 코블리츠^[1]와 빅터 S. 밀러^[2]에 의해 독립적으로 제안되었다. 타원 곡선 암호 알고리즘은 2004년부터 2005년 사이에 널리 사용되기 시작했다.

미국 국립표준기술연구소(NIST)는 1999년에 15개의 타원 곡선을 권장했다. 구체적으로 FIPS 186-4^[3]는 10개의 권장된 유한 필드를 가지고 있는데, 5개는 소수 필드 $\backslash mathbb\{F\}\_p$이고, 5개는 이진 필드 $\backslash mathbb\{F\}\_\{2^m\}$이다. NIST는 최적의 보안과 구현 효율성을 위해 총 5개의 소수 곡선과 10개의 이진 곡선을 권장했다.^[4]

RSA 컨퍼런스 2005에서, 국가안보국(NSA)은 디지털 서명 생성 및 키 교환에 ECC를 독점적으로 사용하는 스위트 B를 발표했다. 이 스위트는 기밀 및 비기밀 국가 안보 시스템과 정보를 보호하기 위한 것이었다.^[5] 국립표준기술연구소(NIST)는 권장 알고리즘 집합인 스위트 B에서 타원 곡선 암호화를 승인했으며, 특히 키 교환을 위한 ECDH와 디지털 서명을 위한 ECDSA를 승인했다. NSA는 384비트 키를 사용하여 최고 기밀까지의 기밀 정보를 보호하는 데 이를 사용할 수 있도록 허용한다.^[6]

최근 바일 및 테이트 페어링과 같은 다양한 타원 곡선 그룹에서 쌍선형 매핑을 기반으로 하는 많은 수의 암호 원시 요소가 도입되었다.

타원 곡선 암호는 전송 계층 보안 및 비트코인과 같은 수많은 인기 있는 프로토콜에서 성공적으로 사용되고 있다. 공개 키 암호 방식은 특정 수학적 문제의 계산적 난해성에 기반을 둔다. 타원 곡선 기반 프로토콜의 경우, 공개적으로 알려진 기준점을 기준으로 임의의 타원 곡선 요소의 이산 대수를 찾는 것이 불가능하다는 것이 기본적인 가정이다(계산적 디피-헬만 가정): 이것이 "타원 곡선 이산 대수 문제"(ECDLP)이다.

타원 곡선 암호가 RSA와 같은 대안보다 약속하는 주요 이점은 더 작은 키 크기로, 저장 및 전송 요구 사항을 줄이는 것이다.^[5] 예를 들어, 256비트 타원 곡선 공개 키는 3072비트 RSA 공개 키와 보안 수준이 유사해야 한다.

몇몇 이산 대수 기반 프로토콜이 타원 곡선에 적용되어 그룹 $(\backslash mathbb\{Z\}\_\{p\})^\backslash times$를 타원 곡선으로 대체되었다.

• 타원 곡선 디피-헬만(ECDH) 키 합의 방식은 디피-헬만 방식을 기반으로 한다.
• 타원 곡선 통합 암호화 방식 (ECIES)
• 타원 곡선 디지털 서명 알고리즘 (ECDSA)
• EdDSA
• ECMQV 키 합의 방식
• ECQV 암시적 인증서 방식

참조

_[1] 논문 Elliptic curve cryptosystems
_[2] 서적 Advances in Cryptology — CRYPTO '85 Proceedings 1986
_[3] 웹사이트 Digital Signature Standard (DSS) https://csrc.nist.go[...] National Institute of Standards and Technology 2013-07-19
_[4] 간행물 Digital Signature Standard (DSS) http://csrc.nist.gov[...] FIPS PUB 186-3
_[5] 웹사이트 The Case for Elliptic Curve Cryptography http://www.nsa.gov/b[...]
_[6] 웹사이트 Fact Sheet NSA Suite B Cryptography http://www.nsa.gov/i[...]
_[7] 뉴스 N.S.A. Able to Foil Basic Safeguards of Privacy on Web https://www.nytimes.[...] 2013-09-05
_[8] 뉴스 RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm https://www.wired.co[...] Wired 2013-09-19
_[9] 웹사이트 Search – CSRC http://csrc.nist.gov[...]
_[10] 뉴스 Are the NIST Standard Elliptic Curves Back-doored? http://it.slashdot.o[...] Slashdot 2013-09-11
_[11] 간행물 Commercial National Security Algorithm Suite and Quantum Computing FAQ https://cryptome.org[...] U.S. National Security Agency 2016-01
_[12] 웹사이트 6.3.4 Are elliptic curve cryptosystems patented? http://www.emc.com/e[...]
_[13] 웹사이트 Irrelevant patents on elliptic-curve cryptography http://cr.yp.to/ecdh[...]
_[14] 웹사이트 https://web.archive.[...] 2018-04-17
_[15] 간행물 Elliptic Curve Cryptography "Made in Germany" https://www.secunet.[...] 2014-06-25
_[16] 웹사이트 GEC 2: Test Vectors for SEC 1 http://www.secg.org/[...]
_[17] 서적 Algorithmic Number Theory
_[18] 서적 A cryptographic application of the Weil descent
_[19] 웹사이트 Constructive and destructive facets of Weil descent on elliptic curves http://www.hpl.hp.co[...] 2006-01-02
_[20] 논문 Reducing elliptic curve logarithms to logarithms in a finite field
_[21] 논문 On an Improved Definition of Embedding Degree http://eprint.iacr.o[...]
_[22] 웹사이트 P1363 http://grouper.ieee.[...] IEEE 2007-02-13
_[23] 논문 Evaluation of discrete logarithm in a group of ''p''-torsion points of an elliptic curve in characteristic ''p''
_[24] 논문 The discrete logarithm problem on elliptic curves of trace one http://www.hpl.hp.co[...]
_[25] 논문 Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves
_[26] 간행물 Recommendation for Key Management—Part 1: general http://csrc.nist.gov[...] NIST 2005-08
_[27] 웹사이트 112-bit prime ECDLP solved – LACAL http://lacal.epfl.ch[...] 2009-07-11
_[28] 웹사이트 Certicom Announces Elliptic Curve Cryptography Challenge Winner http://www.certicom.[...] 2004-04-27
_[29] 웹사이트 Breaking ECC2K-130 http://www.ecc-chall[...]
_[30] 논문 Implementing an efficient elliptic curve cryptosystem over GF(p) on a smart card http://anziamj.austm[...]
_[31] 서적 Advances in Cryptology — ASIACRYPT'98
_[32] 서적 Topics in Cryptology — CT-RSA 2001 http://cr.yp.to/bib/[...]
_[33] 웹사이트 SafeCurves: choosing safe curves for elliptic-curve cryptography https://safecurves.c[...] 2013-12-01
_[34] 논문 A comb method to render ECC resistant against Side Channel Attacks http://eprint.iacr.o[...]
_[35] 웹사이트 Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system http://blog.cr.yp.to[...]
_[36] 서적 Advances in Cryptology — CRYPTO 2000 http://www.iacr.org/[...]
_[37] 웹사이트 Did NSA Put a Secret Backdoor in New Encryption Standard? https://www.schneier[...]
_[38] 웹사이트 Government Announces Steps to Restore Confidence on Encryption Standards http://bits.blogs.ny[...] 2013-09-10
_[39] 웹사이트 On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng http://rump2007.cr.y[...]
_[40] 웹사이트 SafeCurves: choosing safe curves for elliptic-curve cryptography http://safecurves.cr[...] 2016-10-01
_[41] arXiv Quantum resource estimates for computing elliptic curve discrete logarithms
_[42] 간행물 Concrete quantum cryptanalysis of binary elliptic curves https://eprint.iacr.[...]
_[43] 웹사이트 RSA in a "Pre-Post-Quantum" Computing World https://www.f5.com/l[...] 2021-03-16
_[44] 웹사이트 Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies https://eprint.iacr.[...] IACR 2014-05-03
_[45] 간행물 Breaking SIDH in polynomial time https://eprint.iacr.[...] 2022
_[46] 웹사이트 Commercial National Security Algorithm Suite https://apps.nsa.gov[...] 2020-01-08
_[47] 웹사이트 AMD-SEV: Platform DH key recovery via invalid curve attack (CVE-2019-9836) https://seclists.org[...] 2019-06-25
_[48] 간행물 Elliptic curve cryptosystems
_[49] 간행물 Use of elliptic curves in cryptography
_[50] 서적 フェルマーの大定理 [第3版] 日本評論社 1996-05
_[51] 서적 プログラミング・ビットコイン ゼロからビットコインをプログラムする方法 オライリー・ジャパン (オーム社) 2020-10
_[52] 보고서 SEC 2：Recommended Elliptic Curve Domain Parameters (Version 2.0) https://www.secg.org[...] Standards for Efficient Cryptography Group (SECG) 2010-01-27
_[53] 보고서 Recommendation for Key Management, Part 1: General https://nvlpubs.nist[...] 2020-05
_[54] 보고서 Recommendation for Key Management, Part 1: General https://nvlpubs.nist[...] 2020-05
_[55] 보고서 On the correct use of the negation map in the Pollard rho method https://eprint.iacr.[...] IACR Cryptology ePrint Archive 2016-11-14
_[56] 보고서 Recommendation for Key Management, Part 1: General https://nvlpubs.nist[...] 2020-05
_[57] 간행물 A comb method to render ECC resistant against Side Channel Attacks http://eprint.iacr.o[...]
_[58] 웹사이트 Cr.yp.to: 2014.03.23: How to design an elliptic-curve signature system http://blog.cr.yp.to[...] 2020-01-02
_[59] arXiv Quantum resource estimates for computing elliptic curve discrete logarithms
_[60] 간행물 Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies https://www.degruyte[...]