뇌로그

비트코인(Bitcoin)

 블록체인 기술을 기반으로 만들어진 온라인 암호화폐이다. 2008년 10월 사토시 나카모토라는 가명을 쓰는 프로그래머가 개발하여, 2009년 1월 프로그램 소스를 배포했다. 중앙은행이 없이 전 세계적 범위에서 P2P 방식으로 개인들 간에 자유롭게 송금 등의 금융거래를 할 수 있게 설계되어 있다. -위키백과

비트코인의 기술의 핵심은 역시 블록체인이다. 블록체인을 이해하기 전에 알아야할 용어 몇가지 소개한다.

1) 공개키 암호화 방식

공개키 암호방식은 두 개의 키를 이용한다. 하나는 비밀키이고 또 하나는 공개키 이다. 공개키는 말 그대로 누구나 확인할 수 있고, 비밀키는 자신 이외에 아무도 모른 다는 것을 전제로 한다. 평문을 공개키로 암호화 하면 복호화는 개인키로만 가능하다. 따라서 A가 B에게 문서를 보낼 때, B의 공개키로 암호화 하여 보내고 B는 암호화된 문서를 자신의 개인키로 복호화 하여 내용을 확인 할 수 있다. 마찬가지로 B가 A에게 문서를 보낼 때는 A의 공개키로 암호화 한다.

2) 디지털 서명

서명은 '행위자가 자기의 동일성을 표시하고 책임을 분명하게 하기 위하여 성명을 쓰는 일'을 의미한다. 즉 자신이 했음을 보증하는 것을 말한다. 도장, 싸인과 같은 것이 알날로그 서명의 예이다. 그렇다면 디지털 상에서 어떤 행위를 자신이 했음을 보증하는 방법이 무엇일까? 바로 디지털 서명이다.

 서명은 위에서 설명한 공개키와 개인키가 사용된다. 평문을 M, 해쉬함수를 H, 암호화를 E, 복호화를 D라고 할때, 서명이 필요한 평문을 전송을 위해 개인키로 암호화 한 E[H(M)] 의 암호문을 만든다. 그리고 M과 E[H(M)] 를 함께 전송한다. 받는이는 E[H(M)] 을 보낸이의 공개키로 복호화 한 D[E[H(M)]] = H(M)  ‥‥‥ (1) 을 만들고, 같이 전송받은 평문에 해쉬함수를 취한 H(M) ‥‥‥ (2)를 만들고, (1) 과  (2)를 비교하여 일치하는지 검사한다. 이로써 전송한 사람이 작성하였음을 검증하고 중간에 변조되지 않았음을 확인할 수 있다.  이러한 디지털 서명은 우리가 많이 사용하는 공인인증서에 적용되고 있다.

비트코인

이제 비트코인의 시스템을 알아보자. 비트코인을 좀 들어본 사람이면 트랜젝션(Transaction)이라는 용어를 들어보았을 텐데, 간단하게 말하면 비트코인 거래내역 단위를 의미한다. A가 B에게 1BTC를 전송하면 하나의 트랜젝션이 발생하게 된다.

이때, 비트코인은 이러한 트랜젝션 중 위조된 트랜젝션, 잘못된 트랜젝션, 중복된 트랜젝션 등을 자체적으로 검증하는 시스템을 가지고 있다.  이 원리는 아래와 같다.

'n-1번째의 트랜젝션과 받는이의 공개키'를 송신자의 개인키로 서명한다. 이로 써 누구나 n-1번째 사람이 n 번째 사람에게 이체했음을 'n-1번째 사람의 공개키'로 검증할 수 있다. 이런 구조가 끊임 없이 반복되고 있다.

그러나 누군가 나서서 이러한 검증연산을 컴퓨터로 하기 전에는 옳은 트랜젝션인지 알 수 가 없다. 그래서 비트코인에 채굴이라는 시스템이 있다.

 위 그림에서 Tx는 각 트랜젝션을 의미한다. 블록에는 검증해야할 여러 트랜젝션들과 이전블록의 해쉬값, 타임스탬프가 들어간다. 이때, (이전 해쉬값, 트랜젝션 루트, 타임스탬프, Nonce)에 해쉬함수를 취해 E보다 작은 값을 가지게 하는 Nonce를 찾는 것이 채굴의 과정이다. 여기서 E는 목표 값(현재 기준 약 2^192)보다 낮은 값이 나올 때까지, 'SHA256 해싱'을 반복한다. 이를 만족하는 Nonce값은 여러개가 나올 수 있는데, 해쉬결과를 더 작게하는 Nonce가 우선순위를 갖는다.

이러한 블록은 10분에 1개씩 생겨나게 되고 블록의 Nonce를 찾은 채굴자에게 비트코인 보상이 주어지게 된다. 처음에는 블록당 50개의 비트코인이 보상으로 주어졌으나 210,000개의 블록마다 보상에 반감기가 적용되어 2013년에는 25개의 블록이 보상으로 주어졌고, 2020년에는 6.25개의 비트코인이 보상으로 주어질 것으로 본다. 비트코인의 총 발행량은 2100만개로 제한되어있어서 2140년쯤 모두 채굴되지만, 거래 수수료 또한 채굴자가 받을 수 있어서 비트코인의 시스템을 지속 될 수 있게 하였다.

DES

블록암호의 일종으로, 미국 NBS (National Bureau of Standards, 현재  NIST)에서 국가 표준으로 정한 암호이다. DES는 대칭키암호이며, 56비트의 키를 사용한다.

64비트 블럭 암호 알고리즘. 56비트 키를 사용(64비트 중 8비트는 parity check로 사용)

라운드 수 : 16

DES 심플버전

키생성 과정

가운데 키 생성과정 보자. 예를들어 여기서 1 0 0 1 0 0 1 1 1 0 의 10bit 키 입력이 들어가게 되면,

P10

P10에 의해서 0 0 0 1 1  0 1 1 1 0 가 출력된다. 이를 반씩 나누어 0 0 0 1 1 / 0 1 1 1 0 가 되고

P8

P8을 통해 1 1 1 1 1 0 0 0 의 8bit 키 K1이 생성된다.

K2 생성도 이와 같다.

8bit의 평문은 IP를 거치게되는데,

IP

이 과정을 예를 들면, 1 0 1 0 1 1 0 0 이 입력 0 1 1 1 0 0 1 0 가 출력되는 것이다.

fk의 내부는 아래와 같다.

E/P에서는 4bit입력에 대한 8bit출력으로  확장과 치환이 일어난다.

여기까지 DES의 심플 버전이었다.

DES의 심플버전은 8비트로 2단계처리 밖에 안하지만, 실제 DES는 64비트, 16단계 처리를 한다. F함수또한 4비트가아닌 32비트연산이다.

블록 암호 기법

 큰 데이터를 블록 단위로 나누어 블록별로 암호화를 한다.

블록 암호와 스트림 암호의 비교

블록 암호

N비트 평문 입력으로 N비트의 암호문을 출력한다.

역으로 N비트의 암호문으로 N비트의 평문을 출력한다.

총 2^n 가지의 서로 다른 블록이 존재할 수 있다.

N이 4일때의 블록치환. 4비트의 입력으로 16개의 값 중 하나를 선택하고, 내부 치환에 의해 16개의 값중 하나에 대응한 4비트를 출력하게 된다.

ex) 1111(입력) = 15 -> 7 = 0111(출력)

블록이 작으면 취약. 크면 클수록 암호화 강도는 높하짐. 그러나 작은 블록이 구현과 성능면에서  유리하다. 적당한 크기의 N을 설정해야 한다.

Feistel 암호방식

Feistel 암호 방식은 현재 사용하고 있는 대부분의 중요한 대칭 블록 암호 의 기본구조이다. 치환과 순열을 번갈아 가면서 수행하는 암호방식으로 혼돈(confusion) 과 확산(diffusion)이 적용된다. 확산은 각 평문의 숫자가 다수의 암호문 숫자 값에 영향을 주는 것을 말하고, 혼돈은 암호문의 통계적 구조와 암호 키 값 사이의 관계를 복잡하게 만드는 것을 말한다.

암호화 반복구조

복호화 반복구조

평문 블록(W)을 L0(W/2)와 R0(W/2) 로 분할처리한다. K로 부터 유도된 n개의 키(K0~Kn)를 사용한다. n회의 동일한 반복구조를 실행한다.

각 반복구조는 오른쪽 R0에 함수 F를 적용하고, 왼쪽의 L0와 XOR(이때 치환작용이 적용) 을 한다. 좌우 양쪽 결과를 교환(순열작용 적용)한다.

AES

 많은 플랫폼위에서 속도 그리고 코드압축성이 좋아 효율적인 암호방식. 벨기에의 2명의 암호학자, 존 대먼과, 빈센트 라이먼이 만든 암호화 알고리즘이다.

프로세스

State - AddRoundKey - {SubBytes - ShiftRows - MixColumns - AddRoundKey}:9 - SubBytes - ShiftRows - AddRoundKey

AddRoundKey

• 라운드 키는 각 State에 bitwise XOR로 적용한다.
• 사이퍼 키로부터 키 스케줄러를 통해 라운드 키 생성
• 라운드 키의 길이는 평문 블록길이와 같다.

SubBytes

• 각 바이트 단위 요소에 적용되는 비선형 대체 연산

ShiftRows

• 첫 번째 행은 회전하지 않고, 두 번째 행은 좌로 1byte, 세 번째 행은 좌로 2bytes, 네 번째 행은 좌로 3bytes만큼 이동한다.

MixColumns

• State의 각 열에 대하여 행렬곱셈을 수행한다.

a0 * [2 3 1 1] = r0
a1 * [1 2 3 1] = r1
a2 * [1 1 2 3] = r2
a3 * [3 1 1 2] = r3

여기서 r값들을 구하려면, 이런 식으로 해야한다.

r0 = (a0 * 2) + (a1 * 3) + (a2 * 1) + (a3 * 1).
r1 = (a0 * 1) + (a1 * 2) + (a2 * 3) + (a3 * 1).
r2 = (a0 * 1) + (a1 * 1) + (a2 * 2) + (a3 * 3).
r3 = (a0 * 3) + (a1 * 1) + (a2 * 1) + (a3 * 2).

여기서의 곱셈은  Exclusive-OR(XOR) 이다.

출처: https://namu.wiki/w/AES [나무위키]