×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 1,485,639명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)


목차


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 :   P 보다 적은 소수(Prime)로, 난수생성기로 생성한다.


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를 생성하기 위한 장비로도 사용되어 집니다.







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


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


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



  1. 대학생 2018.04.17 22:31

    정말 너무 잘보고갑니다 설명 너무 쉽게 잘해주셨네요 아주 많은 도움 되었습니다 감사합니다!!

  2. Realrealife 2018.10.02 19:08 신고

    P 와 Q 를 가지고 R 을 유도하는 중간 과정을 알 수 있을까요?
    1. P 와 Q 를 지나는 직선 을 만들고
    2. secp256k1 곡선에 대입해서 나오는 3차방정식을 풀어서 근을 구하는 고
    3. 배점을 구하는 것에 비해서

    너무 간단하게 유도되었는데 중간 과정이 궁금합니다!!