[Blockchain] Elliptic Curve Cryptography(ECC)

jinny

Published in

None

9 min readJul 24, 2019

안녕하세요. 휴먼스케이프 개발팀 인턴 jinny입니다.

이 글은 공개 키 암호 알고리즘 중 하나인 Elliptic Curve Cryptography(ECC, 타원 곡선 암호)를 소개하고, 이더리움에서 ECC가 어떻게 사용되는지에 대해 설명합니다.

글은 크게 다음의 흐름으로 진행됩니다.

공개 키 암호시스템 (Public key cryptography)

2. Elliptic Curve Cryptography (ECC, 타원 곡선 암호)

3. secp256k1 Elliptic Curve

4. ECC in Ethereum

1. 공개 키 암호시스템 (Public key cryptography)

공개 키 암호시스템이란 암호시스템의 한 종류로, 대칭 키 암호와 달리 통신 주체끼리 사전에 비밀 키를 나누어 가지지 않아도 안전한 통신이 가능합니다.

대칭 키 암호 방식은 N명의 통신 주체가 모두 서로 메시지를 주고받으려면 n(n-1)/2=O(N²) 만큼의 키가 필요합니다. 그러나 공개 키 암호 방식은 N개의 통신 주체가 각각 자신의 public key와 private key만 가지면 되기 때문에, 2N=O(N)개의 키만으로 모든 통신 주체가 서로 메시지를 주고받을 수 있습니다.

이처럼 공개 키 암호화 방식에서는 각 통신 주체가 2개의 키 — public key와 private key를 가집니다.

public key : private key로부터 생성되며 다른 사람에게 공개됩니다.
private key : 공개 키 암호 방식에서 보안성을 제공하는 핵심요소로서, 자신의 private key가 타인에게 노출되어서는 안됩니다.

공개 키 암호시스템의 보안성 혹은 안전성은 public key로부터 private key를 유추해내기 어렵다는 것을 의미합니다.

공개 키 암호시스템은 특정 수신자만 메시지를 볼 수 있도록 메시지를 암호화하거나, 메시지 발신자를 인증하기 위한 디지털 서명에 사용됩니다.

메시지 암호화

메시지 암호화란 특정 수신자만 메시지를 볼 수 있도록 메시지를 암호화하는 것입니다. Alice가 Bob에게 메시지를 전송하는 경우, 메시지가 Bob의 public key로 암호화되면 Bob이 아닌 다른 네트워크 참여자는 메시지를 열어볼 수 없습니다. 메시지를 열어보기 위해서는 Bob의 private key로 메시지를 복호화해야하기 때문입니다.

디지털 서명 (Digital Signature)

디지털 서명이란 메시지의 발신자가 A임을 증명하기 위해 메시지에 A의 서명을 남기는 것입니다. 메시지는 발신자 A의 private key로 암호화(서명)되고, 수신자는 암호화된 메시지를 A의 public key로 복호화하여 메시지가 A로부터 전송되었음을 검증할 수 있습니다.

2. Elliptic Curve Cryptography (ECC, 타원 곡선 암호)

Elliptic Curve Cryptography(ECC, 타원 곡선 암호)는 공개 키 암호 알고리즘 중 하나로, 어려운 이산대수문제에 기반하여 안전성을 제공합니다. ECC는 과거의 RSA 알고리즘과 비교했을 때 같은 키 길이에 대해 더 강력한 보안성을 제공합니다. 즉, 더 짧은 키 길이로 비슷한 수준의 보안성을 제공합니다.

그렇다면 ECC에서 사용하는 Elliptic Curve(타원 곡선)이란 무엇일까요?

Elliptic Curve (타원 곡선)

수학에서 Elliptic Curve(타원 곡선)은 다음 방정식을 만족하는 대수 곡선을 말합니다.

y²=x³+ax+b

타원 곡선에서 덧셈 연산 정의

타원 곡선 위의 서로 다른 두 점 A, B에 대하여 A+B=C는 다음과 같이 정의됩니다.

A+B=C
타원 곡선 상의 서로 다른 두 점 A, B를 지나는 직선을 그었을 때, 이 직선이 타원 곡선과 만나는 또다른 점을 C’이라 하자. C는 C’과 x축 대칭인 타원 곡선 상의 점이다.

타원 곡선에서 곱셈 연산 정의

타원 곡선 위의 점 P와 상수 k에 대하여 k*P는 다음과 같이 정의됩니다.

k*P=P+P+…+P

곱셈은 덧셈을 반복적으로 수행한 것과 같습니다. 이 곱셈 연산은 ECC에서 private key로부터 public key를 생성할 때 사용됩니다.

여기서 주의할 점은, 공개 키 암호시스템에서 타원 곡선은 실수가 아닌 유한체 안에서 정의된다는 것입니다. 유한체는 원소의 개수가 유한한 체를 의미합니다. 이 방정식을 실수 공간에서 고려한다면 곡선으로 표현되지만, 공개 키 암호화에서 타원 곡선은 실수가 아닌 유한체 GF(p)={0,1,…,p-1} 안에서 정의됩니다. 따라서 그래프는 곡선이 아니라 scattered points의 집합으로 표현되고, 방정식은 좌변과 우변에 modular 연산을 취합니다.

3. secp256k1 Elliptic Curve

비트코인과 이더리움은 elliptic curve로 secp256k1 표준을 사용합니다. secp256k1에서 제안하는 타원 곡선 방정식은 다음과 같습니다.

y²=x³+7

이 타원곡선은 유한체 GF(p)={0,1,…,p-1} 안에서 정의되므로, 방정식을 다음과 같이 바꿔쓸 수 있습니다.

y² mod p= (x³+7) mod p
,where p= 2²⁵⁶–2³²–2⁹–2⁸–2⁷–2⁶–2⁴–1 (32byte)

유한체 안에서의 타원곡선 덧셈,곱셈연산은 실수공간 타원곡선에서의 정의와 같습니다. 다만 가능한 점의 좌표값이 유한하게 제한됩니다.

4. ECC in Ethereum

public key generation

public key는 private key로부터 생성됩니다. private key는 32byte의 랜덤 넘버이고, 이를 k라고 한다면 퍼블릭 키 PK는 다음과 같이 구할 수 있습니다.

k*G = G+G+G+…+G = (x1,y1)
PK = 04 + x1 + y1 (여기서 +는 concatenation을 의미합니다.)

여기서 G는 secp256k1 표준에서 정의한 base point 입니다. base point G를 시작점으로 k번 덧셈 연산을 한 결과좌표값으로 PK를 구할 수 있습니다. 덧셈 결과 좌표가 (x1,y1) 일 때, x1과 y1을 concatenation한 64byte 수에 04를 prefix로 붙인 것이 public key가 됩니다.

여기서 주목할 점은 PK로부터 k를 역산할 수 없다는 것입니다. 타원 곡선의 곱셈 연산은 one-way function으로, division 연산은 어렵습니다. k*G와 G를 알 때 k값을 구하는 문제를 타원 곡선 이산대수 문제라고 하며, 타원 곡선 이산대수 문제의 어려움은 ECC로 생성된 public key로부터 private key를 효율적으로 구할 수 없도록 안전성을 제공합니다.

Elliptic Curve Digital Signature Algorithm (ECDSA)

A가 B에게 이더를 전송하기 위해 트랜잭션을 생성한다고 가정해 봅시다. 만약 이 트랜잭션을 발생시킨 주체가 A가 맞다는 것을 증명하는 수단이 없다면 어떻게 될까요? 아무나 A를 가장하여 이더를 전송할 수 있게 되고, 이것은 자신의 지갑으로 원하는 만큼의 이더를 전송하는 악의적인 행동을 가능하게 합니다. 이러한 행위를 방지하려면, 이더를 전송할 권한을 트랜잭션에 표시하고, 권한이 올바른지 검증하는 proof of authorization 과정이 필요합니다.

이더리움에서는 ECC를 사용하여 트랜잭션에 서명을 합니다. 이 서명은 이더를 전송할 권한을 표시하는 역할을 합니다. address A에서 B로 송금하는 경우 해당 트랜잭션에 A의 private key로 서명을 하고, A의 public key를 사용해서 트랜잭션의 서명이 A의 것이 맞는지 검증할 수 있습니다.

결국 서명과 검증 과정을 통해 계정 소유자만이 이더를 전송할 수 있습니다. 또한 A가 B에게 이더를 전송했음에도 불구하고, A가 이 사실을 부인하는 것을 방지합니다. (guarantees non-repudiation)

아래 그림은 ECDSA의 전체 과정을 나타낸 그림입니다. 서명과 검증 과정에서 ECC 곱셈 연산이 사용되는 것을 확인할 수 있습니다.

감사합니다.

[참고자료]

공개 키 암호 방식, wiki
Mastering Ethereum, by Gavin Wood; Andreas M. Antonopoulos, O’Reilly Media, Inc., 2018 — chapter4 Cryptography and chapter6 Transactions

[이미지 출처]

Get to know us better!
Join our official channels below.

Telegram(EN) : t.me/Humanscape
KakaoTalk(KR) : open.kakao.com/o/gqbUQEM
Website : humanscape.io
Medium : medium.com/humanscape-ico
Facebook : www.facebook.com/humanscape
Twitter : twitter.com/Humanscape_io
Reddit : https://www.reddit.com/r/Humanscape_official
Bitcointalk announcement : https://bit.ly/2rVsP4T
Email : support@humanscape.io