파이썬으로 배우는 블록체인 구조와 이론-2장 암호기술(2)
05.공개키 기반 암호기술
공개키(혹은 비대칭키) 기반 암호 방식은 개인키(private key)와 공개키(public key)를 이용
개인키와 공개키는 특별한 관계를 맺은 쌍으로 구성
개인키는 개인이 보관하고 공개키는 타인에게 공개
공개키 암호 방식을 이용하면 키를 전달할 필요가 없어 대칭키 암호 방식의 근본적인 문제를 해결
인증 문제나 부인 방지 문제도 해결
동작방식
- 송신자-A와 수신자-B는 각각 자신의 개인키와 공개키를 가지고 있고, 공개키는 누구나 알 수 있게 공개한다
- 송신자-A가 수신자-B에게 암호문을 보낼 때, 공개키 목록에 공개된 수신자-B의 공개키로 암호문을 만든 후 수신자-B에게 암호문을 전달한다
- 수신자-B는 이 암호문을 자신의 개인키로 풀 수 있다(복호화)
- 이 암호문은 오직 수신자-B만 풀 수 있다.
공개키 방식은 어떠한 키도 전달되지 않는다
RSA 알고리즘
1978년 라이베스트, 샤미르, 애들먼(Rivest, Shamir, Addleman)이 제안
어떤 수를 두 개의 큰 소수(prime number)로 분해하는 것은 대단히 어렵다는 원리를 이용
예시
공개키 (7,187) 개인키 (23,187)
원문인 88을 공개키로 암호화해 암호문인 11을 만든 후 다시 암호문 11에 개인키를 적용해 원문인 88을 만든 것
Diffie-Helllman Key 교환 알고리즘(DHKE)
1976년 휫필드 디피(W. Diffie)와 마틴 헬만(M. E. Hellman)이 제안
각자의 개인키와 공개키를 이용해 공통의 키를 만드는 알고리즘
예시
송신자(Alice)와 수신자(Bob)는 사전에 정의된 정보 (G, p)를 이용해 각자의 개인키와 공개키, 그리고 공통키를 만든다
G와 p는 표준 문서에 정의된 큰 값의 소수
a와 b는 2부터 (p-2) 사이의 임의의 수를 랜덤하게 선택한 값
각자의 개인키인 a와 b로 각자의 공개키 A와 B를 생성
G와 p를 알고 있고, 자신의 개인키인 a와 b도 알고 있으므로 공개키 A와 B를 계산할 수 있다
공개키 A와 B는 서로에게 알려준다
Elgamal 알고리즘
1985년 타헤르 엘가말(Taher Elgamal)이 제안
DHKE와 유사하지만, 암호문을 보낼 때마다 키를 바꿀 수 있어 더욱 안전한 방식
임시키(ephemeral key)와 마스킹키(masking key)를 만들어 마스킹키로 문서를 암호화하는 방식
마스킹키가 계속 바뀌기 때문에 동일한 문서라도 암호문을 보낼 때마다 암호문이 바뀐다
Square-and-Multiply 알고리즘(공개키 계산)
DHKE에서 대단히 큰 수를 이용해 공개키를 만들 때 Square-and-Multiply 알고리즘을 사용하면 쉽게 계산할 수 있다
예시
3을 234번 곱한 후 15로 나눈 나머지 값을 구하는 문제
개인키를 알고 있으면 이 알고리즘으로 공개키를 쉽게 계산할 수 있다
실제는 대단히 큰 수를 사용하기 때문에 이렇게 개인키를 알아내는 것은 현실적으로 불가능
타원곡선암호 알고리즘(Elliptic Curve Cryptography: ECC)
1985년 닐 코블리츠(Neal Koblitz)와 빅터 S. 밀러(Victor S. Miller)가 제안
작은 수로 키를 만들어도 RSA만큼의 성능을 지닌 매우 우수한 암호기술
계산 속도도 빠르고 안전성도 높다
타원곡선상의 점들을 연산하는 규칙을 정의하고(덧셈 규칙), 특정 위치의 점을 여러 번 더해서 개인키와 공개키를 만든다
덧셈 연산자(Addition operator)
덧셈 연산자
타원곡선상의 서로 다른 두 점 P와 Q의 덧셈은 P와 Q를 잇는 선을 연장해 타원곡선과 만나는 점을 찾고, 그 점이 x축과 대칭인 점 R로 정의(R = P + Q)
doubling 연산자
한 점 P에 대해 P를 두 배 하려면 (2P), P + P로 표시하고 (P=Q), 점 P에 접하는 접선이 타원곡선과 만나는 점을 찾고, 그 점이 x축과 대칭인 점으로 정의
실제 ECC에서 계산
개인키, 공개키 생성
ECC의 표준문서에는 타원곡선의 함수식 (a, b, p)과, 곡선상의 한 점인 G(base point or generator), 그리고 순환군의 점의 개수인 N이 정의 돼 있다. 이를 도메인 파라미터(domain parameter)라 한다.
ECC 도메인 파라미터를 참조해 개인키와 공개키를 만든다
ECC로 개인키와 공개키를 만드는 방법
- N보다 작은 임의의 수를 선택하면 이 값이 개인키다(d)
d * G를 계산한 값이 공개키다(K)
d * G는 위에서 정의한 덧셈 연산자를 사용해서 G를 d번 더한다는 의미
Double-and-Add 알고리즘
Square-and-multiply 알고리즘과 유사한 방식으로 계산
예시
개인키-26
비트 값이 ‘1’이면 Double(2배 연산)을 적용한 후 Add(G를 포함)를 적용한다
비트값이 ‘0’이면 Double만 적용한다
Square-and-Multiply 알고리즘과 마찬가지로 실제는 대단히 큰 수를 사용하기 때문에 개인키를 찾아내는 것은 현실적으로 불가능하다
06.해시(Hash) 알고리즘
해시(hash)
문서의 내용을 고정된 길이의 어떤 데이터로 변환하는 것을 말한다
암호적 목적(데이터의 위·변조, 무결성 검출 등)으로 사용될 수도 있고, 비암호 목적(파일 다운로드 오류 검출 등)으로 사용될 수도 있다
해시 함수
문서를 변환하는 함수이다
단방향적 특징을 갖기 때문에 문서로부터 해시 값을 생성할 수는 있지만, 해시 값으로 원래 문서를 생성할 수는 없다.
동작원리는 블록 암호와 유사한 방식으로 문서를 블록으로 나눠서 각 블록의 데이터를 뒤섞거나 XOR 등의 연산을 수행하는 것
해시충돌(collision)
서로 다른 문서의 해시 값이 우연히 같은 경우가 발생하는 경우
확률은 대단히 낮다
변형된 데이터는 문서의 지문 같은 역할로 다이제스트(digest) 혹은 해시 값(hash value)이라 한다.
문서의 일부가 바뀌면 해시 값이 완전히 바뀌므로 문서가 조작됐는지 여부를 쉽게 확인할 수 있다
해시 함수의 조건
문서 = x, 해시 함수 = h, 해시 값 = z = h(x)일 때 x를 z의 프리이미지(preimage)라 한다
해시 함수 h는 일대일 함수가 아니므로 동일한 해시 값 z를 갖는 문서 x가 여러 개 존재할 수 있다
1. 프리이미지 저항성(preimage resistance or one-wayness) : 해시 값 z로 문서 x를 찾는 것이 어려워야 한다. 이것은 해시의 단방향적 성질이다
2. 제2 프리미이지 저항성(second preimage resistance or weak collision resistance) : 문서 x가 주어졌을 때 해시 값 z를 갖는 또 다른 문서 x를 발견하는 것이 어려워야 한다
3. 충돌 저항성(strong collision resistance) : 동일한 해시 값 z를 갖는 임의의 두 문서 x1, x2를 찾는 것이 어려워야 한다
해시 알고리즘의 종류
MD5 : 1991년 라이베스트(Rivest)가 만든 128비트 알고리즘
SHA-1 : 1995년 미국 NIST에서 표준으로 채택한 160비트 알고리즘
RIPEMD160 : 1996년 한스 도버틴(Hans Dobbertin) 등이 만든 160비트 알고리즘
SHA-256, 384, 512 : 2002년 미국 NIST에서 표준으로 채택한 256, 384, 512비트 알고리즘
MD5, SHA-1은 충돌 저항성이 낮아 현재는 SHA-256 이상이 널리 사용되고 있다
RIPEMD160은 비트코인의 공개키 해시를 계산할 때 사용된다
비트코인에 적용된 해시 함수
- 블록 헤더의 내용에 SHA-256 알고리즘을 2번 적용해 헤더의 해시 값을 만든다(double-SHA-256). 헤더의 해시는 이전 블록을 가리키는 포인터로 사용되고(블록체인), Bits 값과 비교해 채굴자가 생성한 블록의 유효성을 검증할 때도 사용된다.
- 트랜잭션의 내용에 double-SHA-256을 적용해 트랜잭션의 해시 값을 만든다. 이 값은 트랜잭션 입력부에 기록된 UTXO 트랜잭션을 가리키는 포인터로 사용된다(트랜잭션 체인). 트랜잭션 해시 값은 일반적으로 특정 트랜잭션을 찾는 ID로 사용된다.
- 블록 바디에 기록된 모든 트랜잭션과 위트니스(witness)의 내용에 double-SHA-256을 적용해 해시 값을 만든다. 이 값은 머클트리를 만들 때 사용된다. 또한 머클트리의 하위 노드들로 상위 노드를 만들 때도 double-SHA-256이 사용된다.
- 지갑 애플리 케이션은 타원곡선암호로 개인키와 공개키를 만들고, 공개키에 double-SHA-256과 RIPEMD160을 적용해 공개키 해시 값을 계산한다. 그리고 공개키 해시 값으로 지갑 주소를 만든다.
각 알고리즘은 문서(message) 길이에 상관없이 고정된 크기의 해시 값을 생성
Message의 마지막 부분이 마침표에서 물음표로 바뀌었을 뿐인데 각 해시 값은 완전히 달라진 것을 확인할 수 있다.
07.전자서명
전자서명은 공개키 기반 암호기술을 이용해 디지털 문서에 대한 인증(Authentication)과 부인 방지(Nonrepudiation)를 목적으로 사용된다
인증 기능-디지털 문서를 생성한 사람이 자기가 이 문서를 생성했음을 증명할 수 있고, 이 문서를 받은 사람은 이를 검증할 수 있다
부인방지 기능-문서를 생성한 사람이 자기가 생성한 것이 아니라고 부인할 수 없다
비트코인에서 자신이 코인의 소유주임을 증명하고 다른 사람들이 이를 검증할 때 사용
개인키를 가지고 있는 사람만이 전자 서명을 만들어 낼 수 있으므로 본인 인증(Authentication)이 가능하고, 서명한 사람이 자신이 생성한 문서가 아니라고 부인할 수도 없다(Nonrepudiation)
타원곡선 전자서명 알고리즘(ECDSA)
ECDSA(Ellliptic Curve Digital Signature Algorithm)는 타원곡선을 이용한 전자서명 알고리즘이다
※이미지 출처 : 파이썬으로 배우는 블록체인 구조와 이론(위키북스)
