타원곡선 디피-헬먼

3. 절차

앨리스와 밥이 공유 키를 설정하려는 상황을 가정한다. 이들이 사용할 수 있는 유일한 통신 채널은 제3자에 의해 도청될 수 있다.

먼저, 도메인 매개변수 (소수 위수 유한체에서는 $(p,\; a,\; b,\; G,\; n,\; h)$, 표수 2 유한체에서는 $(m,\; f(x),\; a,\; b,\; G,\; n,\; h)$)에 대해 합의해야 한다.

각 참여자는 타원 곡선 암호화에 적합한 키 쌍을 가져야 한다. 키 쌍은 개인 키 $d$ (구간 $[1,\; n-1]$에서 임의로 선택된 정수)와 공개 키 $Q$ ($Q\; =\; d\; \backslash cdot\; G$, 즉 $G$를 $d$번 더한 결과)로 구성된다. 앨리스의 키 쌍을 $(d\_\backslash text\{A\},\; Q\_\backslash text\{A\})$, 밥의 키 쌍을 $(d\_\backslash text\{B\},\; Q\_\backslash text\{B\})$라고 하자. 각 참여자는 프로토콜을 실행하기 전에 상대방의 공개 키를 알고 있어야 한다.

앨리스는 점 $(x\_k,\; y\_k)\; =\; d\_\backslash text\{A\}\; \backslash cdot\; Q\_\backslash text\{B\}$를 계산한다. 밥은 점 $(x\_k,\; y\_k)\; =\; d\_\backslash text\{B\}\; \backslash cdot\; Q\_\backslash text\{A\}$를 계산한다. 공유 비밀은 $x\_k$이다(점의 ''x'' 좌표). ECDH를 기반으로 하는 대부분의 표준화된 프로토콜은 일부 해시 기반 키 파생 함수를 사용하여 $x\_k$에서 대칭 키를 파생한다.

양쪽이 계산한 공유 비밀은 동일하다. 왜냐하면 $d\_\backslash text\{A\}\; \backslash cdot\; Q\_\backslash text\{B\}\; =\; d\_\backslash text\{A\}\; \backslash cdot\; d\_\backslash text\{B\}\; \backslash cdot\; G\; =\; d\_\backslash text\{B\}\; \backslash cdot\; d\_\backslash text\{A\}\; \backslash cdot\; G\; =\; d\_\backslash text\{B\}\; \backslash cdot\; Q\_\backslash text\{A\}$이기 때문이다.

다른 표현으로 정리하면 다음과 같다.

• 앨리스와 밥은 서로의 공개 키를 교환한다.
• 앨리스는 $(x\_A,\; y\_A)=d\_A\; Q\_B$를 계산하고, 밥은 $(x\_B,\; y\_B)=d\_B\; Q\_A$를 계산한다.
• * $d\_A\; Q\_B=d\_Ad\_B\; G=d\_Bd\_A\; G=d\_B\; Q\_A$
• 공유 비밀은 $x\_k$이다.
• * 최근에 사용되는 ECDH 기반 암호들은, 공유된 비밀값을 해시하여 대칭키를 만든다.^[4]

4. 특징

• 공개키가 영구적(static)이면 그냥 ECDH로, 일시적(ephemeral)이면 ECDHE (ECDH Ephemeral)로 부른다.^[4]
• 인증은 중간자 공격을 피하기 위한 필수 요소이다. 앨리스가 밥과 공유 키를 설정하려 할 때, 제3자가 도청할 수 있는 채널만 사용 가능하다면, 도메인 매개변수에 대한 합의가 필요하다.
• 각 당사자는 개인 키와 공개 키로 구성된 키 쌍을 가져야 한다. 앨리스의 키 쌍은 $(d\_\backslash text\{A\},\; Q\_\backslash text\{A\})$, 밥의 키 쌍은 $(d\_\backslash text\{B\},\; Q\_\backslash text\{B\})$이며, 프로토콜 실행 전에 상대방의 공개 키를 알아야 한다.
• 앨리스와 밥은 각각 $(x\_k,\; y\_k)\; =\; d\_\backslash text\{A\}\; \backslash cdot\; Q\_\backslash text\{B\}$와 $(x\_k,\; y\_k)\; =\; d\_\backslash text\{B\}\; \backslash cdot\; Q\_\backslash text\{A\}$를 계산하여 공유 비밀 $x\_k$(점의 ''x'' 좌표)를 얻는다. 대부분의 표준화된 프로토콜은 $x\_k$에서 해시 기반 키 파생 함수를 사용하여 대칭 키를 파생한다.
• 공유 비밀은 $d\_\backslash text\{A\}\; \backslash cdot\; Q\_\backslash text\{B\}\; =\; d\_\backslash text\{A\}\; \backslash cdot\; d\_\backslash text\{B\}\; \backslash cdot\; G\; =\; d\_\backslash text\{B\}\; \backslash cdot\; d\_\backslash text\{A\}\; \backslash cdot\; G\; =\; d\_\backslash text\{B\}\; \backslash cdot\; Q\_\backslash text\{A\}$와 같이 양쪽이 동일하게 계산된다.
• 앨리스의 개인 키는 이산 대수 문제를 풀 수 없다면 안전하며, 밥의 개인 키도 마찬가지이다. 공유 비밀은 디피-헬만 문제를 풀 수 없다면 안전하다.
• 공개 키는 정적이거나 일시적('''ECDHE''')일 수 있다. 인증되지 않은 일시적 키는 다른 수단을 통해 진위 보장을 받아야 한다. 중간자 공격을 피하려면 인증이 필요하며, 정적 공개 키는 중간자 공격을 무력화한다.
• 정적 공개 키는 순방향 비밀성이나 키 손상 위장 복원력 등 고급 보안 속성을 제공하지 않는다. 정적 개인 키 소유자는 다른 공개 키를 검증하고, 키 파생 함수를 적용해야 한다.
• 앨리스가 악의적으로 유효하지 않은 곡선 점을 선택하고 밥이 검증하지 않으면, 밥의 개인 키가 노출될 수 있다. 여러 TLS 라이브러리가 이 공격에 취약한 것으로 밝혀졌다.^[4]
• 공유 비밀은 크기가 $(n+1)/2$인 $[0,\; p)$의 하위 집합에서 균일하게 분포되므로, 대칭 키로 직접 사용해서는 안 되며, 키 파생 함수에 대한 엔트로피로 사용될 수 있다.
• 몽고메리 형태 타원 곡선 $E\_\{M,A,B\}$는 $By^2\; =\; x(x^2\; +\; Ax\; +\; 1)$ 방정식을 만족하는 모든 $(x,y)\; \backslash in\; F\_p\; \backslash times\; F\_p$의 집합과 무한대 점 $\backslash infty$로 구성된다.
• 번스타인은 맵 $x\_0$을 도입했다.^[8]
• Curve25519의 경우, $p\; =\; 2^\{255\}\; -\; 19,\; A\; =\; 486662$ 및 $B\; =\; 1$이다.
• Curve448의 경우, $p\; =\; 2^\{448\}\; -\; 2^\{224\}\; -\; 1,\; A\; =\; 156326$ 및 $B\; =\; 1$이다.
• 앨리스와 밥이 통신할 때, 제3자에게 도청될 위험이 있다면, 타원 곡선 파라미터를 결정하고, 비밀 키와 공개 키 쌍을 생성하여 공개 키를 교환한다.
• 앨리스는 $(x\_k,\; y\_k)\; =\; d\_A\; Q\_B$, 밥은 $(x\_k,\; y\_k)\; =\; d\_B\; Q\_A$를 계산하여 공유 비밀 $x\_k$를 얻고, 이를 바탕으로 공통 키를 생성한다.

5. 보안성

타원 곡선 상의 이산 대수 문제를 풀 수 없는 한, 앨리스와 밥 외에 제3자는 앨리스와 밥의 개인 키를 알 수 없다. 마찬가지로 타원 곡선 상의 디피-헬만 문제를 풀 수 없는 한, 통신 경로를 도청하는 제3자는 두 사람이 공유하는 비밀키 $x\_k$ (점의 ''x'' 좌표)를 계산할 수 없다.^[4]

공개 키는 정적(static)이거나 일시적(ephemeral, '''ECDHE'''로 약기)일 수 있다. 일시적 키는 인증되지 않으므로, 인증이 필요한 경우 다른 수단을 통해 중간자 공격을 방지해야 한다. 앨리스나 밥의 공개 키 중 하나가 정적이면 중간자 공격은 불가능하지만, 순방향 비밀성 등 다른 고급 보안 속성은 제공되지 않는다. 정적 개인 키 소유자는 다른 공개 키를 검증하고, 정적 개인 키 정보 유출을 막기 위해 원시 디피-헬만 공유 비밀에 안전한 키 파생 함수를 적용해야 한다.^[20]

공유 비밀은 크기가 $(n+1)/2$인 $[0,\; p)$의 하위 집합에서 균일하게 분포한다. 따라서 비밀은 대칭 키로 직접 사용하지 않고, 키 파생 함수에 대한 엔트로피로 사용될 수 있다.

6. 소프트웨어

• Curve25519는 다니엘 J. 번스타인이 C 언어로 작성한 인기 있는 타원 곡선 매개변수 집합 및 참조 구현이다. 언어 바인딩 및 대체 구현도 사용할 수 있다.
• Curve448은 Rambus(램버스) 암호화 연구소의 마이크 함부르크가 개발한, 잠재적으로 224비트의 보안을 제공하는 타원 곡선이다.
• 라인 메신저 앱(LINE)은 2015년 10월부터 해당 앱을 통해 전송되는 모든 메시지의 "Letter Sealing" 종단 간 암호화에 ECDH 프로토콜을 사용해 왔다.^[16]
• 시그널 프로토콜은 손상 후 보안을 확보하기 위해 ECDH를 사용한다. 이 프로토콜의 구현은 시그널(메신저 앱)(Signal), 왓츠앱(WhatsApp), 페이스북 메신저(Facebook Messenger) 및 스카이프(Skype)에서 찾아볼 수 있다.

참조

_[1] 간행물 Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography http://csrc.nist.gov[...] NIST 2006-03
_[2] 간행물 Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography http://www.secg.org/[...] Certicom Research 2009-05-21
_[3] 간행물 Suite B Implementers' Guide to NIST SP 800-56A http://www.nsa.gov/i[...] NSA Suite B Cryptography 2009-07-28
_[4] 논문 Practical Invalid Curve Attacks on TLS-ECDH https://www.nds.ruhr[...] 2015-09-04
_[5] 웹사이트 Speeding the Pollard and elliptic curve methods of factorization https://www.ams.org/[...] Mathematics of Computation, 48(177):243–264, 1987 1987
_[6] 웹사이트 Montgomery curves and the Montgomery ladder https://eprint.iacr.[...] In Joppe W. Bos and Arjen K. Lenstra, editors, Topics in Computational Number Theory inspired by Peter L. Montgomery, pages 82–115. Cambridge University Press, 2017. 2017
_[7] 논문 Montgomery curves and their arithmetic - the case of large characteristic fields https://link.springe[...] J. Cryptographic Engineering, 8(3):227–240, 2018. 2018-09
_[8] 웹사이트 Can we avoid tests for zero in fast elliptic-curve arithmetic? https://cr.yp.to/ecd[...]
_[9] 서적 Advances in Cryptology — CRYPTO '85 Proceedings In Advances in Cryptology - CRYPTO’85, Santa Barbara, California, USA, August 18-22, 1985, Proceedings, pages 417–426. Springer Berlin Heidelberg, 1985 1986
_[10] 서적 Public Key Cryptography - PKC 2006 In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds) Public Key Cryptography - PKC 2006. Lecture Notes in Computer Science, vol 3958. Springer, Berlin, Heidelberg 2006
_[11] 웹사이트 Monte Carlo methods for index computation mod p https://www.ams.org/[...] Mathematics of Computation, 32:918–924, 1978
_[12] 웹사이트 Ed448-goldilocks, a new elliptic curve https://eprint.iacr.[...] ACR Cryptology ePrint Archive, 2015:625, 2015 2015
_[13] 논문 Security and Efficiency Trade-offs for Elliptic Curve Diffie-Hellman at the 128- and 224-bit Security Levels https://link.springe[...] J Cryptogr Eng 12, 107–121 (2022) 2022
_[14] 논문 Efficient Elliptic Curve Diffie-Hellman Computation at the 256-bit Security Level https://doi.org/10.1[...] 2020
_[15] 웹사이트 Safecurves: choosing safe curves for elliptic- curve cryptography https://safecurves.c[...] 2024-04-15
_[16] 웹사이트 New generation of safe messaging: "Letter Sealing" https://engineering.[...] LINE Corporation 2018-02-05
_[17] 간행물 Special Publication 800-56A, Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography http://csrc.nist.gov[...] NIST 2006-03
_[18] 간행물 Standards for efficient cryptography, SEC 1: Elliptic Curve Cryptography http://www.secg.org/[...] Certicom Research 2000-09-20
_[19] 간행물 Suite B Implementers' Guide to NIST SP 800-56A http://www.nsa.gov/i[...] NSA Suite B Cryptography 2009-07-28
_[20] 논문 An Efficient Protocol for Authenticated Key Agreement http://download.cert[...] Certicom 2012-01-19