타원 곡선 암호학(Elliptic Curve Cryptography)

 

---

목차

 

1. 타원 곡선 암호학이란?
2. 타원 곡선 암호학 이용
3. 갈루아 필드 상에서의 타원 곡선(Elliptic Curves Over GF(p))

 

4. ECC 에서의 Private-Key 와 Public-Key
5. 갈루아 필드 상에서의 암호화 / 복호화
6. ECC를 이용할 때 주의할 점

---

 

 

1. 타원 곡선 암호학이란?

 

비트코인은 디지털 서명 암호기술로, 공개키 암호기술 구현 방식의 한 종류인, ECC(Elliptic Curve Cryptography : 타원곡선 암호기술) 방식에 속하는 ECDSA(Elliptic Curve Digital Signature Algorithm) 암호 알고리즘을 사용하고 있고, 
비트코인 시스템의 Security 는 ECDSA 암호 알고리즘의 Security 에 의해 결정되어 지며, ECDSA 암호 알고리즘의 Security 는 사용되는 개인키(Private-Key)의 Security에 의해 결정되어 진다.
이러한 타원 곡선 암호학(Elliptic Curve Cryptography)은 줄여서 ECC라고 한다.

https://blog.naver.com/aepkoreanet/221178375642

 

 

타원 곡선 암호학은 아래와 같은 수식을 가지게 된다.

 

 

 

가장 유명한 그래프꼴은 위와 같으며 비트코인에서 쓰이는 scep256k1 curve 그래프는 a = 0, b = 7인 그래프를 이용한다.

 

 

 

 

이제 위의 그래프로 우리는 암호학에 접근해보고자 한다.

 

 

이때 타원 곡선 암호학을 쓰는 가장 큰 이유는

RSA나 ElGamal과 같은 기존 공개 키 암호 방식에 비하여 보다 짧은 키를 사용하면서도 그와 비슷한 수준의 안전성을 제공한다는 것이다.

 

타원 곡선 암호학(ECC)를 쓰기 유용할 때

 

계산 능력이 제한적일 때 (무선 장치, PC 카드) 집적 회로 공간이 제한될 때 (무선 장치, PC 카드) 빠른 속도를 필요로 할 때 서명, 검증 또는 인증이 필요할 때

서명 된 메시지를 저장하거나 전송 할 때 (특히 짧은 메시지의 경우). 대역폭이 제한될 때 (무선 통신 및 일부 컴퓨터 네트워크).

 

 

 

 

 

 

2. 타원 곡선 암호학 이용

 

 

이제 이 타원 곡선을 이용하여 P1, P2, P3를 정의해보자.

 

 

 

 

만약 P1과 P2가 그래프 위의 선상에 있다면, 우리는 P1 + P2 = P3이라고 정의 할 수 있다.

 

이때 '+'는 우리가 알고있는 1+2 = 3일때 +가 아닌 여기서만의 부호 역할을 한다.

 

+로 쓰는 이유는 추후 알게 될 것이지만, 교환법칙, 결합법칙이 만족되기 때문에 저렇게 쓴다.

 

 

1. P1과 P2를 가지는 직선을 하나 그어보자.  

 

2. 직선을 그었을 때 새롭게 만나는 점에서 x축을 기준으로 직선을 그었을 때 만나는 또다른 점이 P3가 된다.

 

 

이제 이를 공식화 시켜보자.

 

P(x1, y1) 그리고 Q(x2, y2)가 E 상에 존재하고 있을 때 R(x3, y3) = P + Q가 된다.

 

 

 

 

1. P != Q일때 (Addition)

 

 

 

 

 

2. P == Q일때 (Doubling)

 

 

(위에서 a는 y^2 = x^3 + ax + b의 a이다.)

 

 

 

 

 

 

3. 갈루아 필드 상에서의 타원 곡선(Elliptic Curves Over GF(p))

 

갈루아 필드 상에서의 타원 곡선을 확인해보자.

 

이때 갈루아 필드는 유한 체를 의미하고 유한 체는 유한개의 원소를 가지는 체를 의미한다.

 

즉, x와 y의 좌표계가 무한하지 않고 유한하게 한정된 곳에서 바라보는 것이다.

 

이때 갈루아 필드를 만들기 위해 modular을 이용하면 되고 mod P를 할 때 P는 소수로 정의한다.

 

한번 정의를 해보자.

 

 

 

 

이때 갈루아 필드의 예시를 한번 들어보자.

 

 

 

위의 그래프가 뭔지 한번 파악해보자.

 

만약 x = 9라고할 때 y^2  mod 23 = (729+ 9) mod 23 = 738 mod 23 = 2이다.

 

이때 만족하는 y는 5*5 mod 23 = 2이므로 y는 5가 될 수 있다.

 

다른것들도 이와 같이 한번 해보자.

 

 

이때 갈루아 필드의 p가 조금만 더 커지면 우리는 y를 쉽게 찾을 수 없게 된다.

 

따라서 이를 통해 암호학에 적용 할 수 있게 된다.

 

 

 

 

 

4. ECC 에서의 Private-Key 와 Public-Key
Private-Key d :   Private-Key는 P보다 작은 소수일 필요는 없으며, 안전한 난수 생성기를 사용하여 무작위성을 보장하고, 충분히 긴 길이를 가져야 합니다.

 

Public-Key Q :  Q(x , y) = d x G(x0 , y0) 즉, 타원곡선의 '+'으로 만들어진다.
“d x G” 란 “G를 d번 더한 값”을 의미 한다.( Q = G + G + …….G + G +G )

 

G는 이미 알려져 있고, Q는 키 생성후 공개되어 진다. 하지만, G 와 Q를 안다고 해서, d 값을 유추해 내기가 굉장히 어렵다. 
이것을 ECDLP(Elliptic Curve Discrete Logarithm Problem)라고 부르며, 
이러한 속성으로 인해 공개키 암호기술로 사용되어지게 되었다.https://blog.naver.com/aepkoreanet/221178375642

 

 

 

실제로 이제 어떻게 계산하는지 한번 해보자.

 

우리는 현재 G(α) = (2,7)이라고 가정하고(지금부터 G를 α로 쓰겠습니다.)

 

2α = (x2, y2)를 계산해보자. 

 

우선 처음에 값은 하나밖에 없으니 doubling으로 들어간다.

 

 

이때 람다식을 구할 때 확장 유클리드 알고리즘을 이용하여 람다를 구할 수 있다.

http://www.crocus.co.kr/1231

 

 

(13을 11로 나누면 2가 되고 14 mod 11을 하면 3^(-1)이 됨을 알 수 있다.)

(이때 곱셈으로 변한 값을 mod 11씩 해주면 3^(-1) mod 11 은 4임을 알 수 있다.

 

 

이제 우리는 α, 2α, 3α, ... , kα를 구할 수 있게 된다.

 

이때 k*α는 '+'혹은 2α 공식을 이용하여 구할 수 있게 된다.

 

비밀키 * α = 공개키

α = (2,7)  2α = (5,2)  3α = (8,3)

4α = (10,2)  5α = (3,6)  6α = (7,9)

7α = (7,2)  8α = (3,5)  9α = (10,9)

10α = (8,8)  11α = (5,9)  12α = (2,4)

 

 

 

 

 

5. 갈루아 필드 상에서의 암호화 / 복호화

 

 

 

위와 같이 갈루아 필드 상의 타원 곡선이 존재하고

 

공개키 α = (2,7)인 상태에서 어떤 사람 A가 B에게 x(10,9)라는 평문을 보내고 싶어한다.

 

A가 선택한 비밀키 pk = 7이라 가정하자.

 

그리고 A가 선택한 난수 k = 3이라 가정하자.

 

 

이제 ECC에서 암호화 공식은 다음과 같다.

 

 

y1과 y2를 구할 것인데 그전에 β를 구해보자.

 

β는 위의 식에 나와있듯이 pk * α이다.

 

y1 = k*α이고 ( k는 Random Value, α는 공개키 )

y2 = x + k*β이 된다. ( x는 Plaintext )

 

 

위의 k, α, x 및 addition, doubling을 우리는 알고 있으니 y1, y2를 구할 수 있다.

 

 

 

이제 이 y = (y1,y2)를 B에게 보내면 B는 다음과 같이 복호화 과정을 거치면 된다.

 

 

복호화 공식은 x = y2 - pk*y1이고 여기서 pk = 7이니 x = y2 - 7*y1이 된다.

 

 

 

 

 

 

6. ECC를 이용할 때 주의할 점

 

난수 생성기(Random Number Generator) 의 중요성RSA에 비교한 ECC의 약점은, 사용되는 Private-Key의 bit수가 적다는 것입니다. Private-Key는 난수 생성기를 통해서 만들어지기 때문에, 품질이 떨어진(?) 난수 생성기를 사용할 경우는, 공격자에 의해 Private-Key가 예측될 수 있다고 합니다. 2013년도에, 안드로이드폰에 저장된 비트코인지갑이 털리는 사건이 발생 했는 데, 원인은 안드로이폰에서 동작되는 난수 생성기(Random Number Generator)를 사용했기 때문이라고 보도 되었습니다. 공격자가 비트코인주소에 대응되는 Private-Key를 예측했기 때문이라고 하였습니다. ECDSA 암호 알고리즘의 Security 는, 사용되는 개인키(Private-Key)의 Security에 의해 좌우 되므로, Private-Key를 예측할 수 없도록 Random하게 생성해야 합니다. 즉 예측할 수 없는 Random Number를 가지고 Private-Key를 생성해야 합니다. 참고로, HSM 장비는 H/W적으로 Random Number를 Generator하는 기능을 제공하고 있으므로, 예측하기 어려운 Private-Key를 생성하기 위한 장비로도 사용되어 집니다.

https://blog.naver.com/aepkoreanet/221178375642

 

 

---

 

추가적으로 ECC에 대해 더 공부해보고 싶으시다면 아래 참고 사이트를 이용해 보시면 좋을 것 같습니다.

 

https://steemit.com/kr/@icoreport/key-2-ecc

 

https://blog.naver.com/aepkoreanet/221178375642