들어가기에 앞서 몇 가지 주의사항입니다.

- 주의 1 : 이 글은 9세의 아동(보다 정확하게는 9세의 본인)을 가상의 타겟 독자로 삼고, 타겟 독자를 완전히 이해시키는 것(최소한 각 계산과정을 수행할 수 있게 만드는 것)을 일차적 목표로 하여 작성되었습니다. 따라서 애초에 설명 자체가 불필요한 것을 장황하게 설명하거나, 간단한 수식으로 표현할 수 있는 것을 지나치게 많은 예시를 들어가며 설명하는 경향이 매우 강하며, 통용되는 용어 대신에 dumb-down시킨 창작용어를 쓰는 경우도 많으므로, 간단한 수식과 코드의 이해가 가능하신 분이 이 글을 읽는 것은 시간 낭비입니다.

- 주의 2 : 퇴고 없이 그대로 포스팅하므로, 수많은 문법적 오류, 내용상 오류, 계산 오류 등이 존재할 수 있습니다.


I. 대칭키 방식의 동작 원리

다짜고짜 비트코인에 들어가는 암호화 방식을 설명하기 보다는, 간단한 배경지식에 대해 먼저 이야기한 뒤 비트코인 이야기로 들어가도록 하겠습니다. 원래는 Casesar, Enigma를 거쳐서 들어가려고 했으나, 쓰다보니 귀찮아져서 Enigma는 생략합니다. 대칭키 방식은 암호화에 사용되는 키와 복호화에 사용되는 키가 동일한 것을 의미합니다. 구체적인 것은 예시를 통해 설명하도록 하겠습니다.

1. 치환암호

  A. x글자 밀기형(Caesar cipher)

생각할 수 있는 가장 간단한 암호화 방식 중 하나입니다. 이름에 Caesar가 붙어있는 것은 그 분이 쓰셔서 그렇습니다. 이것은 알파벳을 다른 알파벳으로 치환하는 형태의 substitution cipher(치환암호) 중 하나인데, 그 중에서도 monoalphabetic substitution cipher에 해당하며, 그 중에서도 가장 간단한 형태로 단순히 일정하게 x칸 떨어진 글자를 사용하는 알고리즘입니다. 예를 들어서,

ABCDEFGHIJKLMNOPQRSTUVWXYZ ← Plain
BCDEFGHIJKLMNOPQRSTUVWXYZA ← Cipher

위와 같이 한글자를 옆으로 미는 형태에서 키는 +1이 되고, 이런걸 보통 ROT1(rotate by 1 place)이라고 부릅니다(ROT 형제 중 가장 유명한 것은 ROT13입니다). 위 알고리즘과 키를 이용하여 Plaintext(평문)으로부터 Ciphertext(암호문)을 뽑아보면(=암호화, encryption) 다음과 같습니다.

O say, can you see, by the dawn's early light ← Plaintext
P tbz, dbo zpv tff, cz uif ebxo't fbsmz mjhiu ← Ciphertext

위 암호화 방식을 알고, key(위 경우엔 +1)를 아는 사람은, 전달받은 Ciphertext로부터 Plaintext를 뽑을 수 있습니다(=복호화, decryption). 그러나 이것은 워낙에 간단한 알고리즘이기 때문에, 존재할 수 있는 키가 25개에 없다는 문제가 있습니다(알파벳이 26글자이므로 다른 결과를 내는 rotation이 총 26가지 존재하긴 하지만, 0은 원문 그대로이므로). 더 큰 문제는 키는 물론이고 암호화 알고리즘 자체를 모르는 사람이라 하더라도, 그냥 보다보면 복호화가 가능한 수준이기 때문에 사실상 아무런 보안도 제공하지 못한다는 겁니다.


  B. 조금 더 복잡한 치환암호

그렇다면 다음과 같이 조금 더 복잡한 형태의 치환암호는 어떨까요?

ABCDEFGHIJKLMNOPQRSTUVWXYZ ← Plain
TXNFIGCYRSMZWOEAVBKQJHDLPU ← Cipher 1
WOGCMUBKXZVYRSQFAPJHELITND ← Cipher 2
MJENUQIKYGRFHZOSTBXAVDPLCW ← Cipher 3
...

송수신자가 이런 치환키 300개를 공유한다면, 편지 도입부에 어떤 키를 사용한 것인지 미리 적어두고 암호문을 보내면, 그것을 해독하는 것은 앞서 언급한 x글자 밀기형 치환암호보다는 조금 더 어렵습니다. 하지만 여기에도 문제가 있습니다. 우선 이런 치환암호문을 복호화하려면 송수신자 모두는 이런 키를 공유해야 하는데, 키가 많으면 많을수록 이런 키를 전달하거나 보관하는 과정에서 유출될 가능성이 높아집니다.

게다가 알파벳은 사용빈도가 동일하지가 않습니다. 예를 들어서 영어의 경우, E/T/A 같은 알파벳은 자주 사용되고, Q/Z 같은 알파벳은 거의 사용되지 않습니다. 따라서 암호문이 길면 길수록 -암호문 샘플이 단 한개만 존재한다 하더라도- 연필만 가지고 키를 찾아내는 것이 불가능하지 않습니다.


C. polyalphabetic substitution cipher

이건 여러 형태가 존재할 수 있지만(e.g. 가장 유명한 것 중 하나로 Vigenère cipher), I.1.A.에서 언급한 x글자 밀기형 치환암호를 변형하여 만들어보겠습니다. 앞서 x글자 밀기형 치환암호의 경우 키가 25개만 존재한다고 했지만, 매 글자마다 다른 칸수의 밀기를 하도록 약속한다면, 키의 갯수를 크게 늘릴 수 있습니다.

예를 들어서 키를 4329086579로 정하고,

첫번째 글자는 4칸
두번째 글자는 3칸
세번째 글자는 2칸
네번째 글자는 9칸
다섯번째 글자는 0칸
(중략)
열번째 글자는 9칸

열한번째 글자는 4칸
열두번째글자는 3칸
(후략)

같은 식으로 밀기를 한다고 칩시다. 이렇게 10글자 키를 쓰면 가능한 키가 100억개로 늘어나기 때문에 손으로 모든 조합을 무작정 적어보는 것은 불가능하고, 키의 자리수를 모르는 공격자는 알파벳 빈도 공격을 하기도 어렵습니다. 또한 치환키 300개를 사용할 때보다 수신(예정)자에게 키를 전달하기가 쉬워지고, 외울 수 있을만한 길이이기 때문에 키를 적어둔 쪽지라는 취약점을 없앨 수 있습니다.

즉 별로 중요하지 않은 내용을 1:1 송수신하는 용도로 사용할 때에는 이 정도의 암호화만 하더라도 어느 정도는 쓸만합니다. 하지만 중요한 내용을 다수에게 보내는 용도로 사용하기는 부족함이 너무 많습니다. 우선 100만명이 10자리 숫자를 공유하고 있는데 그 숫자가 새어나가지 않기를 기대할 수는 없죠. 모두가 키를 외우고 있고 적어둔 키가 없어서 그런 메모지 탈취는 불가능하다 하더라도, 그걸 외우고 있는 사람 하나를 잡아서 고문하면 털어놓기 마련입니다.

또 손으로 모든 조합을 하나하나 시도해 볼 수는 없지만, 그렇다고 해서 손으로 해독하는 것이 불가능한 것은 아닙니다. 취약점 중 한가지만 설명해보자면, 이런 암호화 방식에서는 띄어쓰기 위치가 Plaintext와 Ciphertext 양쪽 모두에서 동일하기 때문에, Ciphertext만 봐도 평문버전을 짐작할 수 있는 단어들이 존재합니다. 예를 들어 편지 하단부에 [5글자 띄어쓰기 9글자]가 존재한다면, 이것은 [Yours Sincerely]일 가능성이 상당히 높습니다. 편지 하단부의 [4글자 띄어쓰기 7글자]라면 [Best/Warm/King/Fond] [Regards] 따위일 가능성이 높죠. 그 외에도 글 어디에서든 3글자 단어가 등장하면 the, and, for, not, you, but 같은 단어일 가능성이 높으며, 한글자 단어는 I 아니면 a일 가능성이 높습니다. 이런 조합들로 말이 되는 키 조합을 찾다 보면 결국 깨지기 마련입니다(모든 글자를 다 붙여쓰면 이런 공격이 조금 더 어려워지긴 합니다만, 그럼 키를 알고 있는 사람도 메시지가 짧으면 Pen is broken과 Penis broken을 구별할 수 없는 등의 문제가 발생하는데다, 이게 유일한 공격법인 것도 아니기 때문에 큰 의미가 없습니다).


2. Enigma

독일군이 사용하던 Enigma도 기본적으로 I.1.C.의 일종이고, 더 복잡한 버전에 불과합니다. 자세한 설명은 앞서 언급하였던 대로 생략합니다.


3. 현대의 대칭키 암호화

위와 같이 암호화를 할 때와 복호화를 할 때 동일한 키를 사용하는 것이 대칭키 암호화입니다. 대칭키 암호화 방식 하에서는 통신을 할 사람들 사이에서 키를 안전하게 전달하고 보관하는 것이 중요하며, 키를 갖지 않은 사람이 키를 찾아내는 데 오랜 시간이 걸리도록 디자인되어야 합니다. 그런데 컴퓨터는 전인류를 합친 것보다도 빠른 속도로 시도를 해볼 수 있기 때문에, 현대의 대칭키 암호화 알고리즘들은 상당히 큰 숫자의 키를 사용합니다. 예를 들어서 256bit 키라면 조합이 2^256개 존재하는데, 풀어쓰면
115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,936개이며,

2048bit 키는 조합이 2^2048개가 존재하는데, 풀어쓰면
32,317,006,071,311,007,300,714,876,688,669,951,960,444,102,669,715,484,032,130,345,427,524,655,138,867,890,893,197,201,411,522,913,463,688,717,960,921,898,019,494,119,559,150,490,921,095,088,152,386,448,283,120,630,877,367,300,996,091,750,197,750,389,652,106,796,057,638,384,067,568,276,792,218,642,619,756,161,838,094,338,476,170,470,581,645,852,036,305,042,887,575,891,541,065,808,607,552,399,123,930,385,521,914,333,389,668,342,420,684,974,786,564,569,494,856,176,035,326,322,058,077,805,659,331,026,192,708,460,314,150,258,592,864,177,116,725,943,603,718,461,857,357,598,351,152,301,645,904,403,697,613,233,287,231,227,125,684,710,820,209,725,157,101,726,931,323,469,678,542,580,656,697,935,045,997,268,352,998,638,215,525,166,389,437,335,543,602,135,433,229,604,645,318,478,604,952,148,193,555,853,611,059,596,230,656개 입니다.

비트코인은 대칭키 암호화를 사용하지 않으니 더 이상의 자세한 이야기는 생략하도록 하겠습니다.



II. 공개키(비대칭키) 방식의 동작 원리

공개키 암호 기법은 원본 메시지를 암호화 할 때 사용하는 키와 복호화 할 때 사용하는 키가 다른 방식을 의미합니다. 다시 말해 애초에 키를 2개씩 페어로 생성하여 A키로 암호화 한 것은 B키로만 복호화 할 수 있고, B키로 암호화 한 것은 A키로만 복호화 할 수 있게 하는 겁니다. 이런 키페어 중 B키만을 불특정 다수에게 뿌리고 다닌다면 불특정 다수가 B키를 사용해서 A키를 소유한 사용자만이 복호화할 수 있는 암호 메시지를 만들 수 있게 되며, 역으로 A키를 가진 사람은 A키로 메시지를 암호화해서 뿌리는 방법으로 불특정 다수에게 그 메시지가 A키를 가진 소유자가 작성한 것이라는 것을 입증할 수 있게 됩니다.

그리고 위 특징을 조합하면 불특정인간A(PubA/PrivA 키페어 소유)는 ①불특정인간B(PubB/PrivB 키페어 소유)만이 그 내용을 확인할 수 있으며, ②B가 그것을 보고 A가 쓴 것이 틀림 없다고 확신할 수 있는 암호 메시지를 보낼 수 있게 됩니다(여기서 Pub키는 불특정 다수에게 뿌리고 다니는 키, Priv키는 본인만이 가지고 있는 키를 의미합니다). 구체적으로 A가 원본 메시지를 자신의 PrivA키로 암호화 한 뒤, 그렇게 나온 암호 메시지를 PubB키로 재차 암호화하여, 최종적으로 생성된 암호 메시지를 불특정 다수에게 뿌리는 형태를 생각해보시면 됩니다. 그러면 PrivB키가 없는 다른 모든 불특정 다수의 사람은 이 암호 메시지를 복호화할 수가 없으나, B의 경우 PrivB키를 소유하고 있기 때문에 1차 복호화가 가능하며, 2차 복호화에 필요한 PubA키는 이미 불특정 다수에게 공개되어 있으므로 B도 이걸 가져와서 2차 복호화를 수행할 수 있게 됩니다. 그럼 이 메시지는 B만이 확인할 수 있으며, 또한 B는 이 메시지가 진짜 A가 보낸 메시지가 맞다는 것을 확신할 수 있게 됩니다.

원래는 각종 비대칭키에 대해 자세히 기재한 뒤 비트코인 이야기를 적으려고 했으나, 여기까지 쓰고보니 심경에 변화가 생겼습니다. 사실 구체적으로 비트코인의 암호화가 어떻게 동작하느냐는 트랜잭션을 설명하면서 같이 설명하는 것이 좋기 때문에, 구체적인 내용은 나중에 쓸 트랜잭션 글로 미루고 여기서 이만 줄이겠습니다.



III. 해시 함수

해시 함수는 임의 사이즈의 원본 데이터를 일정한 사이즈의 데이터로 소화시키는 함수입니다. 해시 함수를 통해서 도출되는 일정한 사이즈의 값을 해시 값(또는 해시 코드, 해시 등)이라고 합니다.

해시는 암호와 관련하여 자주 사용되기는 하지만, 암호화의 방식 중 하나인 것은 아닙니다. 암호화를 했다면 키를 가지고 있는 사람은 복호화를 통해 원본 메시지를 복원할 수 있어야 합니다. 하지만 해시함수는 단방향이기 때문에, 해시값으로부터 원본 메시지를 도출할 수 없습니다. 물론 해시함수를 완전 엉터리로 만들면 이런 과정이 일부 가능할 수도 있습니다만, 그런 경우에도 그게 복호화는 아닙니다. 복호화라는 것은 암호문으로부터 원본 메시지를 복원하는 과정인데, 해시값은 애초에 원본 메시지와 1:1로 대응되는 관계가 아니기 때문에, 설사 동일한 해시값이 나오는 어떤 데이터를 찾아내더라도 그게 그 해시값을 만든 사람이 사용한 원본 메시지인지는 알 수 없기 때문입니다.

암호쪽에서 사용되는 해시함수는 해시값으로부터 원본데이터를 도출하기가 어렵다는 것 외에도 몇 가지 특징이 있습니다. 그 중에서 특정한 해시값과 동일한 해시값이 나오는 원본 데이터를 다른 원본 데이터를 찾기가 어렵다는 것, 동일한 해시값이 나오는 서로 다른 원본 데이터를 찾기가 어렵다는 것, 그리고 원본 데이터가 조금만 달라져도 해시값이 완전히 달라진다는 것 정도가 중요한 요소라고 할 수 있습니다. 해시함수는 이런 특징을 살려 암호 저장용이나 무결성 확인용 등으로 자주 사용됩니다.

암호 저장용만 예를 들어보면, 웹사이트에서 회원가입을 받을 때 사용자의 암호를 받아서 원문 그대로 저장하는 경우, 사용자가 서버에 전송하는 과정에서 탈취될 가능성, 서버가 해킹되어서 탈취될 가능성 등 사용자의 암호 원문이 그대로 탈취당할 수 있는 복수의 루트가 존재하게 됩니다. 한 번 원문이 탈취당하면 암호를 돌려쓰는 사람이 많기 때문에 피해가 상당히 커지게 됩니다. 이 때 암호 원문을 받아서 저장하는 대신 그 암호의 해시값을 받아서 저장하면 이런 문제가 많이 해결됩니다. 해시값만 보고는 원문을 찾아낼 수가 없고, 그 해시값과 동일한 해시값이 나오는 다른 원문을 찾기도 어려우니까요. 하지만 이것만으로는 비밀번호로 password나 1q2w3e4r를 쓰는 사람을 구제할 수는 없기 때문에(공격자도 어지간한 원본 암호의 해시값 사전은 기본으로 들고 있는 관계로), 기본이 되어 있는 곳에서는 사용자마다 서로 다른 임의 난수를 첨가하여 해시를 돌린다거나(i.e. salt), 일정한 값을 첨가하여 해시를 돌린다던가(i.e. pepper), 복수의 해시함수를 반복적으로 돌리는 등의 여러 방법을 복합적으로 사용합니다.

해시 함수 이야기는 이쯤에서 줄이고, 이제 구체적인 해시 함수의 동작을 살펴보도록 하겠습니다. 이것저것 다룰까 하다가 비트코인이 쓰는것만 다루는게 나을듯 하여, SHA-256과 RIPEMD-160 이야기를 하면서 관련된 비트코인 이야기를 조금 해보겠습니다.


1. SHA-1

SHA-256을 이야기한다더니 왜 SHA-1이 나오냐 싶으시겠지만, SHA-256 해시 함수를 수식 없이 예시로만 설명하면 길이가 너무 길어집니다. 그래서 조금이라도 더 짧게 끊을 수 있는 SHA-1를 예시를 통해 설명한 뒤, SHA-256는 차이점만 기재하는 방식으로 가겠습니다(그래도 엄청 깁니다).

SHA-1은 최대 2^64-1비트의 원문에서 160 비트(160자리 2진수, 40자리의 16진수)의 해시값을 도출시키는 함수인데,  여기서는 [SHA-1s]라는 스트링의 SHA-1 해시값을 직접 구해보겠습니다.  작업은 원문 - 패딩 (사전작업 1단계) - 파싱 (사전작업 2단계) - 이니셜 해시 밸류 설정 (사전작업 3단계) - 해싱 순서로 진행되며, 예시를 자세히 들다 보니 길이가 어마어마하게 길어졌으니, 간단한 수식 읽기와 산수가 가능하신 분은 NIST의 자료(FIPS 180-4)를 보시는 편이 낫습니다.


A. 원문 메시지

우선 원문 메시지 [SHA-1sTt]를 구성하는 각각의 ASCII 코드는 다음과 같습니다(UTF-8에서도 동일). 참고로 T와 t는 1비트만 다른 동일 알파벳의 대소문자가 이런 연산을 거쳤을 때 얼마나 다른 결과를 나타낼지 상상해보라는 취지로 덧붙인 예시이고, s는 모든 대소문자의 ASCII 코드가 1비트만 다르지는 않다는 것을 보여주기 위한 예시입니다.

알파벳 - Hex - Decimal - Binary
S - 0x53 - 083 - 01010011
H - 0x48 - 072 - 01001000
A - 0x41 - 065 - 01000001
- - 0x2D - 045 - 00101101
1 - 0x31 - 049 - 00110001
s - 0x73 - 115 - 01110011
T - 0x54 - 084 - 01010100
t - 0x74 - 116 - 01110100

우리가 실제로 컴퓨터를 하면서 눈으로 보게 되는 것은 데이터를 다시 디코딩해서 만들어낸 [SHA-1sTt]입니다만, 실제로는 위 바이너리 형태로 저장 혹은 연산이 이뤄집니다. 그러니 원형으로 만들어서 계산을 해야 합니다.


B. 패딩 (사전작업 1단계)

위 2진수를 1바이트 단위로 보기좋게 한칸씩 띄어서 순서대로 늘어놓으면 다음과 같이 됩니다.
01010011 01001000 01000001 00101101 00110001 01110011 01010100 01110100

그 뒤에 1을 붙여서 아래와 같이 만듭니다.
01010011 01001000 01000001 00101101 00110001 01110011 01010100 01110100
1

이제 1 뒤에 0개 이상 512개 미만의 0을 붙여서 길이가 448mod512(=448)가 되도록 만듭니다. 위 예시의 경우 패딩용 1까지 포함해 65자리이니 0이 383개 필요하며, 뒤에 붙이면 이런 모양이 됩니다.
01010011 01001000 01000001 00101101 00110001 01110011 01010100 01110100
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

이제 [메시지 사이즈](위 예시의 경우 64자리이니 2진수 01000000)를 뒤에 붙여서 아래와 같이 512비트의 [블록]을 만듭니다. SHA-1의 경우 메시지 사이즈의 표기는 64비트로 하고, 뒷쪽부터 합니다. 원본 메시지가 512비트보다 길었던 경우에는 원본 메시지를 잘라서 512비트 단위 블록을 여러개 만들고, 마지막으로 남은 덩어리가 이런 모양이 됩니다. 마지막으로 남은 덩어리의 데이터가 447자리면 1과 메시지 사이즈를 붙여서 바로 끝나는 것이고, 448자리면 1 뒤에 511개의 0이 들어간 뒤 메시지 사이즈가 붙으며, 메시지가 512비트의 정배수라 마지막 덩어리에 1밖에 없으면 447개의 0을 붙이고 메시지 사이즈를 넣은 것이 마지막 블록이 됩니다.

01010011 01001000 01000001 00101101 00110001 01110011 01010100 01110100
11000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000000

이렇게 완성된 [512비트 블록(들)]은 80라운드짜리 연산을 수행하는 기본단위가 됩니다.


C. 파싱 (사전 작업 2단계)

우선 위 512비트 블록을 32비트 단위로 쪼개서, 16개의 32비트 [words]를 만듭니다(너무 기니까 앞으로는 가급적이면 binary words 옆에 붙여놓은 hex 버전의 words로 표기하겠습니다). 이런 32비트 words들이 앞으로 있을 각 연산의 기본 단위가 됩니다.

M0_1 - 01010011 01001000 01000001 00101101 - 5348412D
M1_1 - 00110001 01110011 01010100 01110100 - 31735474
M2_1 - 10000000 00000000 00000000 00000000 - 80000000
M3_1 - 00000000 00000000 00000000 00000000 - 00000000
M4_1 - 00000000 00000000 00000000 00000000 - 00000000
M5_1 - 00000000 00000000 00000000 00000000 - 00000000
M6_1 - 00000000 00000000 00000000 00000000 - 00000000
M7_1 - 00000000 00000000 00000000 00000000 - 00000000
M8_1 - 00000000 00000000 00000000 00000000 - 00000000
M9_1 - 00000000 00000000 00000000 00000000 - 00000000
M10_1 - 00000000 00000000 00000000 00000000 - 00000000
M11_1 - 00000000 00000000 00000000 00000000 - 00000000
M12_1 - 00000000 00000000 00000000 00000000 - 00000000
M13_1 - 00000000 00000000 00000000 00000000 - 00000000
M14_1 - 00000000 00000000 00000000 00000000 - 00000000
M15_1 - 00000000 00000000 00000000 01000000 - 00000040

위 예시에서는 블록이 하나밖에 없어서 이게 끝이지만, 512비트 블록이 N개 있는 경우 다음과 같이 16N개의 words를 만드시면 됩니다.

M0_1 , M1_1 , ... , M15_1,
M0_2 , M1_2 , ... , M15_2,
...
M0_N , M1_N , ... , M15_N


D. 초기 해시값 설정 (사전작업 3단계)

SHA-1에서는 Initial hash value를 다음과 같이 설정합니다.

H0_0 = 67452301
H1_0 = EFCDAB89
H2_0 = 98BADCFE
H3_0 = 10325476
H4_0 = C3D2E1F0

앞으로 이 값에 계속 일정한 방식으로 계산을 반복해서 최종적인 160비트 (16진수 40자리) 해시값을 뽑게 됩니다.


E. 해싱

우선 Mt_i 블록을 Wt에 복사합니다 (블록은 워드가 16개 존재하니, t는 0부터 15까지)

W0 = M0_1 - 5348412D
W1 = M1_1 - 31735474
W2 = M2_1 - 80000000
W3 = M3_1 - 00000000
W4 = M4_1 - 00000000
W5 = M5_1 - 00000000
W6 = M6_1 - 00000000
W7 = M7_1 - 00000000
W8 = M8_1 - 00000000
W9 = M9_1 - 00000000
W10 = M10_1 - 00000000
W11 = M11_1 - 00000000
W12 = M12_1 - 00000000
W13 = M13_1 - 00000000
W14 = M14_1 - 00000000
W15 = M15_1 - 00000040

이제 16≤t≤79 구간의 Wt를 만들어야 합니다. 계산은 Wt = ROTL1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16)으로 합니다. 여기서 ROTL1은 바이너리 기준으로 왼쪽으로 한 칸 밀고, 왼쪽에 있던 것이 삐져나오면 그만큼 맨 오른쪽으로 이동시킨다는 뜻이고, XOR(Exclusive OR)은 바이너리 기준 둘 중 하나만 1인 경우에 1을 출력하고 그렇지 않은 경우에는 0을 출력하는 연산입니다(같으면 0, 다르면 1이라고 보아도 됩니다). 예를 들어서 01110011과 10100011의 XOR은 다음과 같은 결과값을 출력합니다.

______01110011
______10100011
XOR = 11010000

이제 아래와 같이 W16부터 W79까지 값을 계산합니다.

W16 = ROTL1(W13 XOR W8 XOR W2 XOR W0) = ROTL1(00000000 XOR 00000000 XOR 00000000 XOR 5348412D) = ROTL1(5348412D)
     = ROTL1(01010011 01001000 01000001 00101101) = 10100110 10010000 10000010 01011010 = A690825A
W17 = ROTL1(W14 XOR W9 XOR W3 XOR W1) = ROTL1(31735474) = 01100010 11100110 10101000 11101000 = 62E6A8E8
W18 = 00000081
W19 = 4D2104B7
W20 = C5CD51D0
W21 = 00000102
W22 = 9A42096E
W23 = 8B9AA321
W24 = 4D2106B3
W25 = F149430D
W26 = 17354741
W27 = 00000408
W28 = 690825BA
W29 = 2E6A8C06
W30 = 79A51E7A
W31 = 00E85C67
W32 = 8BB610DF
W33 = 4E57E251
W34 = A42094EF
W35 = 8D2E22C5
W36 = F1A13EAA
W37 = 03A17594
W38 = 47D066C4
W39 = 173505C3
W40 = A4064973
W41 = F19D8721
W42 = 9A51E7AF
W43 = 0E85C770
W44 = 21230496
W45 = 6EE484B5
W46 = 768D5E23
W47 = F1537EC6
W48 = CAE893ED
W49 = 88D2332C
W50 = 7D066658
W51 = 95C40798
W52 = 3F00DFA8
W53 = 0EED2574
W54 = 013EEC18
W55 = 51F64718
W56 = F4A4308B
W57 = EDE93ECA
W58 = 2F0584F3
W59 = 0202E9AC
W60 = 0A8F77AF
W61 = 7CBEB7E9
W62 = 7EB390F5
W63 = 45F0FABA
W64 = 7FE8E5AE
W65 = 1C993517
W66 = 51E78F72
W67 = CD865DDD
W68 = 5050E210
W69 = E484B5EE
W70 = 8D5E2376
W71 = 537EC2F1
W72 = 819BC870
W73 = FC59820E
W74 = 4E277DBE
W75 = 654397D0
W76 = B06B0E89
W77 = 27DB0A07
W78 = D28d83FB
W79 = 74F807AB

그리고 H0(i-1), H1(i-1), H2(i-1), H3(i-1), H4(i-1)을 a,b,c,d,e에 각각 복사합니다.

a = H0_0 = 67452301
b = H1_0 = EFCDAB89
c = H2_0 = 98BADCFE
d = H3_0 = 10325476
e = H4_0 = C3D2E1F0

여기까지 했으면 준비작업은 끝났고, 이제 본격적인 계산에 들어갑니다. 복잡한 것은 아니고 t=0부터 시작해서 t=79이 될때까지

1. T에다가 ①a값을 좌측으로 5 이동시킨 값 + ②ft(b,c,d) + ③e + ④Kt + ⑤Wt를 합한 값을 넣음
2. e에다가 d 값을 넣음
3. d에다가 c 값을 넣음
4. c에다가 b를 좌측으로 30 이동시킨 값을 넣음(ROTL30(b))
5. b에다가 a를 넣음
6. a에다가 T를 넣음

위 여섯가지 작업을 t를 하나씩 올려가며 총 80번 반복해서 수행하면 됩니다. 여기서 ft(b,c,d)라는 것은 t 값에 따라서 다음과 같이 다른 연산을 수행하는 함수이며,

0≤t≤19 - (b AND c) XOR (NOTb AND d)
20≤t≤39 - b XOR c XOR d
40≤t≤59 - (b AND c) XOR (b AND d) XOR (c AND d)
60≤t≤79 - b XOR c XOR d

AND 연산은 다음과 같이 입력된 동일기리 바이너리의 값이 둘 다 1이면 1을, 그 외에는 0을 출력하는 연산이고,

______01110011
______10100011
AND = 00000011

NOT 연산은 다음과 같이 입력을 역으로 뒤집는 연산입니다.

______01110011
NOT = 10001100

마지막으로 Kt는 t값에 따라서 다음과 같이 일정한 값을 가지는 상수입니다.

0≤t≤19 - 5A827999
20≤t≤39 - 6ED9EBA1
40≤t≤59 - 8F1BBCDC
60≤t≤79 - CA62C1D6


예시를 다 적기에는 가망이 없어보이죠? 라운드별 결과만 정리하면 아래와 같이 됩니다.

a 0 : 0xf2fcd9e0 | b 0 : 0x67452301 | c 0 : 0x7bf36ae2 | d 0 : 0x98badcfe | e 0 : 0x10325476
a 1 : 0xf7bf5d9f | b 1 : 0xf2fcd9e0 | c 1 : 0x59d148c0 | d 1 : 0x7bf36ae2 | e 1 : 0x98badcfe
a 2 : 0xc4fc7557 | b 2 : 0xf7bf5d9f | c 2 : 0x3cbf3678 | d 2 : 0x59d148c0 | e 2 : 0x7bf36ae2
a 3 : 0xb303a3cb | b 3 : 0xc4fc7557 | c 3 : 0xfdefd767 | d 3 : 0x3cbf3678 | e 3 : 0x59d148c0
a 4 : 0x11b7933e | b 4 : 0xb303a3cb | c 4 : 0xf13f1d55 | d 4 : 0xfdefd767 | e 4 : 0x3cbf3678
a 5 : 0xcc236d38 | b 5 : 0x11b7933e | c 5 : 0xecc0e8f2 | d 5 : 0xf13f1d55 | e 5 : 0xfdefd767
a 6 : 0xbd68848c | b 6 : 0xcc236d38 | c 6 : 0x846de4cf | d 6 : 0xecc0e8f2 | e 6 : 0xf13f1d55
a 7 : 0x9db40d4f | b 7 : 0xbd68848c | c 7 : 0x3308db4e | d 7 : 0x846de4cf | e 7 : 0xecc0e8f2
a 8 : 0x2ed2eccd | b 8 : 0x9db40d4f | c 8 : 0x2f5a2123 | d 8 : 0x3308db4e | e 8 : 0x846de4cf
a 9 : 0xe866cb10 | b 9 : 0x2ed2eccd | c 9 : 0xe76d0353 | d 9 : 0x2f5a2123 | e 9 : 0x3308db4e
a10 : 0xc1acb867 | b10 : 0xe866cb10 | c10 : 0x4bb4bb33 | d10 : 0xe76d0353 | e10 : 0x2f5a2123
a11 : 0x0ea13307 | b11 : 0xc1acb867 | c11 : 0x3a19b2c4 | d11 : 0x4bb4bb33 | e11 : 0xe76d0353
a12 : 0x202e9121 | b12 : 0x0ea13307 | c12 : 0xf06b2e19 | d12 : 0x3a19b2c4 | e12 : 0x4bb4bb33
a13 : 0xdc42fbb1 | b13 : 0x202e9121 | c13 : 0xc3a84cc1 | d13 : 0xf06b2e19 | e13 : 0x3a19b2c4
a14 : 0xed64d0b1 | b14 : 0xdc42fbb1 | c14 : 0x480ba448 | d14 : 0xc3a84cc1 | e14 : 0xf06b2e19
a15 : 0x4332626f | b15 : 0xed64d0b1 | c15 : 0x7710beec | d15 : 0x480ba448 | e15 : 0xc3a84cc1
a16 : 0x90134b85 | b16 : 0x4332626f | c16 : 0x7b59342c | d16 : 0x7710beec | e16 : 0x480ba448
a17 : 0x7eeef427 | b17 : 0x90134b85 | c17 : 0xd0cc989b | d17 : 0x7b59342c | e17 : 0x7710beec
a18 : 0xaab9fa9e | b18 : 0x7eeef427 | c18 : 0x6404d2e1 | d18 : 0xd0cc989b | e18 : 0x7b59342c
a19 : 0x5e40df0a | b19 : 0xaab9fa9e | c19 : 0xdfbbbd09 | d19 : 0x6404d2e1 | e19 : 0xd0cc989b
a20 : 0xde964ccd | b20 : 0x5e40df0a | c20 : 0xaaae7ea7 | d20 : 0xdfbbbd09 | e20 : 0x6404d2e1
a21 : 0xd0fd75e3 | b21 : 0xde964ccd | c21 : 0x979037c2 | d21 : 0xaaae7ea7 | e21 : 0xdfbbbd09
a22 : 0xec2e743a | b22 : 0xd0fd75e3 | c22 : 0x77a59333 | d22 : 0x979037c2 | e22 : 0xaaae7ea7
a23 : 0x5bba65d8 | b23 : 0xec2e743a | c23 : 0xf43f5d78 | d23 : 0x77a59333 | e23 : 0x979037c2
a24 : 0x3a8c9f92 | b24 : 0x5bba65d8 | c24 : 0xbb0b9d0e | d24 : 0xf43f5d78 | e24 : 0x77a59333
a25 : 0x3deb59d6 | b25 : 0x3a8c9f92 | c25 : 0x16ee9976 | d25 : 0xbb0b9d0e | e25 : 0xf43f5d78
a26 : 0xcf23670b | b26 : 0x3deb59d6 | c26 : 0x8ea327e4 | d26 : 0x16ee9976 | e26 : 0xbb0b9d0e
a27 : 0xb3f95574 | b27 : 0xcf23670b | c27 : 0x8f7ad675 | d27 : 0x8ea327e4 | e27 : 0x16ee9976
a28 : 0x3cf5f001 | b28 : 0xb3f95574 | c28 : 0xf3c8d9c2 | d28 : 0x8f7ad675 | e28 : 0x8ea327e4
a29 : 0x99f0fa75 | b29 : 0x3cf5f001 | c29 : 0x2cfe555d | d29 : 0xf3c8d9c2 | e29 : 0x8f7ad675
a30 : 0x99dcabe1 | b30 : 0x99f0fa75 | c30 : 0x4f3d7c00 | d30 : 0x2cfe555d | e30 : 0xf3c8d9c2
a31 : 0x99547125 | b31 : 0x99dcabe1 | c31 : 0x667c3e9d | d31 : 0x4f3d7c00 | e31 : 0x2cfe555d
a32 : 0x02ba600c | b32 : 0x99547125 | c32 : 0x66772af8 | d32 : 0x667c3e9d | e32 : 0x4f3d7c00
a33 : 0xfd1ab0b2 | b33 : 0x02ba600c | c33 : 0x66551c49 | d33 : 0x66772af8 | e33 : 0x667c3e9d
a34 : 0x1f652c49 | b34 : 0xfd1ab0b2 | c34 : 0x00ae9803 | d34 : 0x66551c49 | e34 : 0x66772af8
a35 : 0xeb05f779 | b35 : 0x1f652c49 | c35 : 0xbf46ac2c | d35 : 0x00ae9803 | e35 : 0x66551c49
a36 : 0xc81c4e37 | b36 : 0xeb05f779 | c36 : 0x47d94b12 | d36 : 0xbf46ac2c | e36 : 0x00ae9803
a37 : 0x8a4dd078 | b37 : 0xc81c4e37 | c37 : 0x7ac17dde | d37 : 0x47d94b12 | e37 : 0xbf46ac2c
a38 : 0xb4af869d | b38 : 0x8a4dd078 | c38 : 0xf207138d | d38 : 0x7ac17dde | e38 : 0x47d94b12
a39 : 0x6664ce57 | b39 : 0xb4af869d | c39 : 0x2293741e | d39 : 0xf207138d | e39 : 0x7ac17dde
a40 : 0x2d0465b6 | b40 : 0x6664ce57 | c40 : 0x6d2be1a7 | d40 : 0x2293741e | e40 : 0xf207138d
a41 : 0x7970f266 | b41 : 0x2d0465b6 | c41 : 0xd9993395 | d41 : 0x6d2be1a7 | e41 : 0x2293741e
a42 : 0xe728c72f | b42 : 0x7970f266 | c42 : 0x8b41196d | d42 : 0xd9993395 | e42 : 0x6d2be1a7
a43 : 0xc9377f54 | b43 : 0xe728c72f | c43 : 0x9e5c3c99 | d43 : 0x8b41196d | e43 : 0xd9993395
a44 : 0x400ffccd | b44 : 0xc9377f54 | c44 : 0xf9ca31cb | d44 : 0x9e5c3c99 | e44 : 0x8b41196d
a45 : 0x649f327f | b45 : 0x400ffccd | c45 : 0x324ddfd5 | d45 : 0xf9ca31cb | e45 : 0x9e5c3c99
a46 : 0xa83ba551 | b46 : 0x649f327f | c46 : 0x5003ff33 | d46 : 0x324ddfd5 | e46 : 0xf9ca31cb
a47 : 0xf1be1719 | b47 : 0xa83ba551 | c47 : 0xd927cc9f | d47 : 0x5003ff33 | e47 : 0x324ddfd5
a48 : 0x9c3900ef | b48 : 0xf1be1719 | c48 : 0x6a0ee954 | d48 : 0xd927cc9f | e48 : 0x5003ff33
a49 : 0xe840da4b | b49 : 0x9c3900ef | c49 : 0x7c6f85c6 | d49 : 0x6a0ee954 | e49 : 0xd927cc9f
a50 : 0x6994bb16 | b50 : 0xe840da4b | c50 : 0xe70e403b | d50 : 0x7c6f85c6 | e50 : 0x6a0ee954
a51 : 0xadd4d0e0 | b51 : 0x6994bb16 | c51 : 0xfa103692 | d51 : 0xe70e403b | e51 : 0x7c6f85c6
a52 : 0xf03a7071 | b52 : 0xadd4d0e0 | c52 : 0x9a652ec5 | d52 : 0xfa103692 | e52 : 0xe70e403b
a53 : 0x46b96789 | b53 : 0xf03a7071 | c53 : 0x2b753438 | d53 : 0x9a652ec5 | e53 : 0xfa103692
a54 : 0x1c0d051f | b54 : 0x46b96789 | c54 : 0x7c0e9c1c | d54 : 0x2b753438 | e54 : 0x9a652ec5
a55 : 0x6b550ab4 | b55 : 0x1c0d051f | c55 : 0x51ae59e2 | d55 : 0x7c0e9c1c | e55 : 0x2b753438
a56 : 0x75e4954a | b56 : 0x6b550ab4 | c56 : 0xc7034147 | d56 : 0x51ae59e2 | e56 : 0x7c0e9c1c
a57 : 0xf8ad8af6 | b57 : 0x75e4954a | c57 : 0x1ad542ad | d57 : 0xc7034147 | e57 : 0x51ae59e2
a58 : 0x7d463bdf | b58 : 0xf8ad8af6 | c58 : 0x9d792552 | d58 : 0x1ad542ad | e58 : 0xc7034147
a59 : 0x99e666b4 | b59 : 0x7d463bdf | c59 : 0xbe2b62bd | d59 : 0x9d792552 | e59 : 0x1ad542ad
a60 : 0x8aa8cef5 | b60 : 0x99e666b4 | c60 : 0xdf518ef7 | d60 : 0xbe2b62bd | e60 : 0x9d792552
a61 : 0x325108c0 | b61 : 0x8aa8cef5 | c61 : 0x267999ad | d61 : 0xdf518ef7 | e61 : 0xbe2b62bd
a62 : 0xc4e3a73d | b62 : 0x325108c0 | c62 : 0x62aa33bd | d62 : 0x267999ad | e62 : 0xdf518ef7
a63 : 0x029cd60f | b63 : 0xc4e3a73d | c63 : 0x0c944230 | d63 : 0x62aa33bd | e63 : 0x267999ad
a64 : 0x6f3dd9c1 | b64 : 0x029cd60f | c64 : 0x7138e9cf | d64 : 0x0c944230 | e64 : 0x62aa33bd
a65 : 0xb091e0c7 | b65 : 0x6f3dd9c1 | c65 : 0xc0a73583 | d65 : 0x7138e9cf | e65 : 0x0c944230
a66 : 0x19bcb1fb | b66 : 0xb091e0c7 | c66 : 0x5bcf7670 | d66 : 0xc0a73583 | e66 : 0x7138e9cf
a67 : 0x6cb1ec19 | b67 : 0x19bcb1fb | c67 : 0xec247831 | d67 : 0x5bcf7670 | e67 : 0xc0a73583
a68 : 0x1ff01c50 | b68 : 0x6cb1ec19 | c68 : 0xc66f2c7e | d68 : 0xec247831 | e68 : 0x5bcf7670
a69 : 0x4fb5308d | b69 : 0x1ff01c50 | c69 : 0x5b2c7b06 | d69 : 0xc66f2c7e | e69 : 0xec247831
a70 : 0xbd3eba4e | b70 : 0x4fb5308d | c70 : 0x07fc0714 | d70 : 0x5b2c7b06 | e70 : 0xc66f2c7e
a71 : 0x9f8d47bb | b71 : 0xbd3eba4e | c71 : 0x53ed4c23 | d71 : 0x07fc0714 | e71 : 0x5b2c7b06
a72 : 0x8203ee38 | b72 : 0x9f8d47bb | c72 : 0xaf4fae93 | d72 : 0x53ed4c23 | e72 : 0x07fc0714
a73 : 0x7265b713 | b73 : 0x8203ee38 | c73 : 0xe7e351ee | d73 : 0xaf4fae93 | e73 : 0x53ed4c23
a74 : 0x83dd7f6a | b74 : 0x7265b713 | c74 : 0x2080fb8e | d74 : 0xe7e351ee | e74 : 0xaf4fae93
a75 : 0x0fac12fc | b75 : 0x83dd7f6a | c75 : 0xdc996dc4 | d75 : 0x2080fb8e | e75 : 0xe7e351ee
a76 : 0xd7f86aee | b76 : 0x0fac12fc | c76 : 0xa0f75fda | d76 : 0xdc996dc4 | e76 : 0x2080fb8e
a77 : 0x858e4627 | b77 : 0xd7f86aee | c77 : 0x03eb04bf | d77 : 0xa0f75fda | e77 : 0xdc996dc4
a78 : 0xa036aa10 | b78 : 0x858e4627 | c78 : 0xb5fe1abb | d78 : 0x03eb04bf | e78 : 0xa0f75fda
a79 : 0x1ac2c392 | b79 : 0xa036aa10 | c79 : 0xe1639189 | d79 : 0xb5fe1abb | e79 : 0x03eb04bf

이제 마지막으로 a,b,c,d,e를 초반에 설정했던 이니셜 밸류에다가 더해서 새로운 H값을 만듭니다.

H0_i = a + H0_(i-1)
H1_i = b + H1_(i-1)
H2_i = c + H2_(i-1)
H3_i = d + H3_(i-1)
H4_i = e + H4_(i-1)

이 과정을 반복해서 마지막에 나온 H0_i, H1_i, H2_i, H3_i, H4_i 값을 순서대로 늘어놓으면 그게 곧 160비트짜리 SHA-1 해시값이 됩니다. 위 예시는 블록이 하나짜리라서 아래처럼 한번에 끝이지만, 원본 데이터가 1MB만 되더라도 블록이 1만개 이상 나옵니다.

H0_1 = 1AC2C392 + 67452301 = 8207E693
H1_1 = A036AA10 + EFCDAB89 = 190045599 (←이렇게 32비트를 초과하는 경우 맨 앞을 버립니다)
H2_1 = E1639189 + 98BADCFE = 17A1E6E87 (←상동)
H3_1 = B5FE1ABB + 10325476 = C6306F31
H4_1 = 03EB04BF + C3D2E1F0 = C7BDE6AF


F. 결과

8207E693900455997A1E6E87C6306F31C7BDE6AF

이제 속도 이야기를 잠깐 해보면, 사람이 위 연산을 암산 or 손과 메모지 or 사칙연산만 가능한 단순 계산기만 들고 직접 수행하는 경우, 시간이 얼마나 걸릴까요? 위 예시와 같이 1블록짜리 단순한 예제라 하더라도, 1시간 안에 정확한 값을 구했다면 상당히 빠른 축에 속할 것이고, 꽤 많은 분들은 시간이 수십시간씩 주어지고 계산기가 있는 조건에서도 정확한 값 구하기에 계속 실패할 가능성이 높을겁니다.

그런데 CPU의 경우 이 정도 크기(단일블록)의 원본 메시지를 해싱한다면 이보다 조금 더 복잡한 SHA-256 해시(SHA-1 대비 약 2-3배쯤 비싼 연산임)를 돌려도 초당 1억개 이상 계산할 수 있으며, GPU의 SHA-1 해시레이트는 이미 초당 100억개의 영역에 있습니다. 그리고 비트코인 마이닝에서는 이런 GPU가 너무 느려서 쓸모가 없는 수준입니다. 소비전력 1kW짜리 ASIC 마이너들은 초당 10-20조개의 SHA-256 해시를 처리할 수 있거든요.

고로 컴퓨터 시대에서는 단순히 사람에게 불가능하다는 것은 정말 아무런 의미가 없고, 컴퓨터에게도 ①특정 해시값을 보고 원본 메시지를 찾기나(이에 대한 내성을 preimage resistance라 합니다), ②특정한 원본 메시지와 동일한 해시값이 나오는 다른 메시지 찾기(이에 대한 내성을 second-preimage resistance라 합니다) 그리고 ③동일한 해시값이 나오는 두 개의 다른 원본 메시지 찾기(collision resistance)에 지나치게 오랜 시간을 필요로 하는 것이어야만 암호용 혹은 위변조확인용 등으로 사용되기에 적합한 알고리즘이라고 할 수 있습니다(그리고 용도에 따라 다르긴 합니다만, 일반적으로 '지나치게 오랜 시간'은 3년 혹은 100만년 같은 것을 이야기하는 것이 아니고, 100억짜리 컴퓨터로 10^40년 같은 것을 의미합니다).

하지만 컴퓨터 자체가 상당히 빠른 속도로 발전하는데다, 공략시간을 큰 폭으로 단축시킬 수 있는 취약점(들)이 존재할 수 있기 때문에, 안전하다고 여겨졌던 것도 시간이 흐르면서 위험한 것으로 확인되는 경우가 있습니다. 예를 들어서 MD5는 90년대에 안전하다고 여겨졌던 알고리즘이지만 2000년대 들어 완전한 충돌공격이 발표되면서 salt나 pepper를 활용하는 시스템이라도 지속적인 MD5의 사용은 권장하지 못할만한 일이 되어버렸고, SHA-1도 작년에 CWI와 Google에서 충돌공격을 발표하면서 그런 대열에 합류하고 있습니다(다만 위 취약점은 아주 제한적인 ③에 가까운 것이라서, 이런 문제가 있다고 해서 ②가 된다는 보장은 없습니다). 비트코인이 쓰는 SHA-256의 경우에는 아직까지는 이 정도 상태입니다.


2. SHA-256

SHA-256은 비트코인에서 여러 용도로 사용되는데, 이름에서 느껴지는 것처럼 256bit 해시값이 나오는 함수입니다. 가능한 원문의 길이는 SHA-1과 동일(2^64-1비트)하며, 블록사이즈도 동일한 512비트입니다. 차이점으로는 ①5x32비트로 시작해서 160비트(5x32) 결과물을 내는 SHA-1과 달리 8x32비트로 시작해서 256비트(8x32비트)를 낸다는 점, ②개별 라운드에서 t값에 따라 4가지 함수만을 사용하는 SHA-1과 달리 6가지 함수가 존재한다는 점, ③각 함수에서 사용하는 연산도 XOR/AND/NOT/ROTL 외에 ROTL/SHR 등이 추가된다는 점 등이 있습니다. SHA-1에서 충분히 자세하게 예시를 들었기 때문에 구체적인 내용은 NIST의 자료(FIPS 180-4)를 보고 직접 파악할 수 있을만한 상태가 되었다고 판단되므로, 자세한 내용은 생략하고 이 파트에서는 비트코인에서 SHA-256가 쓰이는 지점을 사용 분야별로 나눠서 설명해보도록 하겠습니다.

  A. 마이닝

SHA-256은 비트코인의 여러 부분에서 쓰이지만 가장 중요한 것은 마이닝입니다. 나중에 마이닝을 다룰 때 더 자세하게 쓰겠지만, 마이닝은 각 사용자들이 발생시킨 트랜잭션을 블록체인에 기록하여 각 주소의 UTXO(i.e. 일반적인 사용자들이 '잔고'로 인식하는 것)를 이동시켜 주는 역할을 수행합니다.

마이닝이 그럼 구체적으로 무슨 작업을 통해 트랜잭션을 블록체인에 기록하는 것이냐? 간략하게 말하면 무작위 원본메시지를 반복해서 SHA-256 해시를 돌리면서, 일정한 SHA-256 해시값이 도출되는 원본 메시지를 찾는 겁니다. 아까 SHA-256은 안전하다고 했는데 이렇게 원본 메시지를 찾을 수 있으면 망한거 아니냐 같은 생각이 드시는 분도 있겠지만, SHA-256 자체는 초당 10-20조개의 해시를 처리하는 마이너가 백만대 이상 붙어있는 지금 현재의 Bitcoin network로도 원본 메시지를 찾아낼 가망이 전혀 없습니다. 비트코인 네트워크 해시레이트 20 EH/s는 상당히 큰 수이긴 합니다만(20,000,000,000,000,000,000해시/초), 이건 brute force로 특정 SHA-256 해시값이 도출되는 원본 메시지를 찾거나, 해시충돌이 나오는 다른 원본 메시지를 찾는 것은 영영 불가능(10분마다 찾는 것은 고사하고)하다고 말해도 될만큼 여전히 충분히 느린 속도이기 때문입니다(2^128이 그만큼 큰 수이므로).

자세한 것은 나중에 마이닝 파트를 쓰게 되면 거기서 다룰테니, 여기서는 개괄적으로만 살펴보겠습니다. 우선 비트코인의 블록은 블록사이즈(4바이트) + 블록헤더(80바이트) + 포함된 트랜잭션 수(1-9바이트) + 트랜잭션묶음(최대 1MB-4B-80B-1B)으로 구성되는데, 마이너들이 구하고자 하는 블록의 해시값이라는 것은 블록 전체를 원본 메시지로 하는 SHA-256 해시값이 아니고, 그 블록 앞쪽에 위치한 80바이트를 차지하는 블록헤더만을 원본 메시지로 하는 SHA-256 해시값입니다.

블록헤더는 ①블록 버전(4바이트), ②바로 전 블록헤더의 해시값(32바이트)(이처럼 이전 블록의 값을 연쇄적으로 포함시켜가며 후속 블록을 생성하므로, 일련의 블록으로 구성된 블록[체인]이 됩니다), ③이 블록헤더의 해시값이 넘어서는 안 되는 값 nBits(4바이트), ④이 블록에 포함된 트랜잭션들의 Merkle root 해시값(32바이트), ⑤마이너가 해싱을 시작한 유닉스 시간(4바이트), ⑥이런 조건을 만족시키기 위해서 변경시키는 값 Nonce(4바이트)로 구성되어 있습니다.

헤더를 구성하는 6가지 요소 중, ①블록 버전은 이 차트에서 보이는 것처럼 현재로썬 사실상 0x20000000로 고정되어 있다고 보시면 되고(블록 버전은 현재 적용받는 룰을 표시한 것으로, 마이너들의 룰 투표기 역할도 수행하나, 여기선 자세한 설명을 생략하고 BIP0009,BIP0034 링크로 대체), ②이전 블록헤더를 원본메시지로 하는 SHA-256 해시값도 마이너들이 서로 다른 블록을 잡고 계속 각기 다른 블록에 대한 후속 블록을 만들고 있지 않는 이상 동시에 한개만 존재할 수 있습니다. ③nBits는 난이도 조정용으로 들어가 있는 수치인데 -자세한 것은 아래에서 다루기로 하고- 일단 여기서 중요한 것은 비트코인의 난이도(nBits)가 매 2,016 블록을 주기로 재설정된다는 것입니다. 그러니 한 번 정해지면 약 2주간은 nBits에 변동이 없습니다(블록 생성 주기가 평균 10분이므로).

결국 위 ①②③ 3가지는 사실상 고정된 상수입니다. 마이너가 하는 것은 나머지 3가지 요소, 그러니까 ④Nonce, ⑤타임스탬프, ⑥Merkle root 해시값을 이리저리 조정해가면서 자기 블록의 SHA-256 해시값이 난이도 타겟상 조건을 만족시키도록 만드는 겁니다. 마이너가 조정하는 3가지 요소에 대해서 먼저 간략히 살펴본 후, nBits에 대해서 설명해보도록 하겠습니다.

④Nonce는 애초부터 brute-force로 조건을 만족시키는 해시값을 찾기 위해 0부터 하나씩 올려가면서 시도해보라고 주는 부분입니다. 그런데 용량이 4바이트(32비트)에 불과하기 때문에(즉 4,294,967,296개의 값만 존재함), 지금과 같은 난이도에서는 가능한 모든 Nonce 값을 다 돌려보더라도(ASIC 마이너 한대가 0.0003초만에 할 수 있는 연산), 조건을 충족시키는 값이 나올 가능성이 거의 없습니다. 그러니까 다른 요소들도 계속 바꿔가면서 해시값을 찾아나가게 됩니다.

⑤타임스탬프의 경우 별 의미는 없고 그냥 마이너가 자기가 해싱을 시작한 시간이라고 보고한 유닉스 시간인데(따로 검증해 보는 것이 아님), 제약조건은 딱 2개밖에 없습니다. 하나는 이전 11개 블록의 타임스탬프 중간값보다는 커야지 네트워크에서 받아들여질 수 있다는 것이고, 다른 너무 먼 미래의 시간을 쓰면 노드들에게 받아들여지지 않을 수 있다는 겁니다. 그러니까 타임스탬프도 -위 두가지 조건을 만족시키는 범위 내에서- 해시값 찾기 용으로 적당히 바꿀 수 있습니다. 그리고 해시레이트가 딱 42.94억/초 짜리 컴퓨터라면 그냥 매 초마다 새로운 타임스탬프를 이용해서 모든 Nonce를 돌려보면 딱 맞습니다. 하지만 컴퓨터가 압도적으로 빠르면(e.g. ASIC은 모든 Nonce의 계산을 0.0003초만에 끝냄) 타임스탬프를 너무 자주 바꿔야 하는데, 그러다 보면 위 제약조건에서 벗어날 수가 있으니 이쪽을 수정하기보다는 Merkle root쪽 해시값 변경을 사용합니다.

⑥Merkle root는 마이너가 블록에 포함시킬 모든 트랜잭션을 연쇄적으로 해싱하여 구해낸 최종적인 단일 해시값을 의미합니다. 사용자들이 비트코인 네트워크에 트랜잭션을 브로드캐스팅하면 이것들은 마이너에 의해 블록에 포함되기 전까지는 계속 mempool을 떠돌게 되는데, 마이너는 이렇게 떠도는 트랜잭션 중에서 자기가 블록에 포함시키고 싶은 트랜잭션을 고를 수 있습니다(주로 수수료를 높게 쓴 트랜잭션부터 순서대로 집어갑니다). 이렇게 포함시키고 싶은 트랜잭션을 약 1MB어치 정도 모았으면(1MB 블록에는 보통 수천개의 트랜잭션이 포함됩니다), 우선 모든 트랜잭션을 SHA-256로 두바퀴씩 돌려서(더블 SHA-256) 각각 해시값을 구합니다(i.e. SHA256(SHA256(각 트랜잭션)) 같은 형태로). 그렇게 나온 해시값을 2개씩 묶어서 다시 더블 SHA-256 해시값을 구하고, 다시 그걸 2개씩 묶어서 더블 SHA-256 해시값을 구하는 것을 반복하다 보면 결국 1개의 해시가 남는데, 이게 Merkle root 해시입니다.

왜 이런 방식을 사용하냐면, 통짜 해시보다 더 효율이 좋기 때문입니다. 예를 들어서 어떤 1MB 블록에 기본형에 가까운 190바이트 근처의 트랜잭션이 총 4,000개 가량 포함되었는데, 특정한 트랜잭션이 이 블록에 포함되었는지 여부를 검증하고자 한다고 칩시다. Merkle tree 방식에서는 트랜잭션 4천개짜리 블록이라면 트리가 13단계로 구성되는데(2^12=4096이므로), 이걸 검증하는 사람은 4,000개의 트랜잭션 전체에 대해 해시값을 구해볼 필요가 없습니다. 본인이 검증해보고자 하는 트랜잭션이 Merkle root 바로 아래 단계에 있는 경우 딱 1회의 더블 SHA-256 해싱을 통해 블록에 포함되었다는 것을 검증할 수 있고, 트리의 맨 아랫 단계에 들어가 있는 경우에도 총 12라운드의 더블 SHA-256 해싱을 통해 검증이 가능하니까요. 그리고 이처럼 최악의 경우라 하더라도 이렇게 해싱해야 하는 총 원본메시지 용량이 1KB 미만이 됩니다. 전체를 묶어서 해시를 돌리는 경우 횟수는 한번이지만 원본 메시지 용량이 1MB라서 더 많은 연산을 필요로 하게 됩니다(아까 설명한 SHA-1의 동작원리를 고려해서, 원본 메시지의 크기에 따른 연산량을 생각해보세요).

아무튼 마이너들은 블록에 포함시키고 싶은 트랜잭션 자체를 계속 바꿔가며 새로운 Merkle root값을 뽑아낼 수도 있습니다만, 선별한 트랜잭션들을 그대로 둔 채 해시값만 바꿀 수도 있습니다. 블록 안에는 반드시 마이너가 생성한 Coinbase 트랜잭션(coinbase 트랜잭션은 블록리워드를 지급하는 트랜잭션인데, 마이너가 자기 지갑에 지급하도록 생성합니다)이 맨 먼저 들어가는데, 이 트랜잭션은 마이너가 생성하는 것이니까 다 돌렸는데도 안 나오면 새로 트랜잭션을 만들어서 새 Coinbase 트랜잭션을 포함시킨 버전으로 Merkle root 해시값을 뽑으면 해시값이 바뀌게 됩니다.

이제 구체적으로 찾아야 하는 해시값의 조건을 설명하기 위해 nBits로 돌아가보겠습니다. 마이너들이 저렇게 변수들을 바꿔가며 찾으려고 하는 것은 [특정한 값]과 같거나 낮은 값의 해시값이 도출되는 원본 메시지(=블록헤더)입니다. 원본 메시지의 증감에 따른 해시값의 변화를 미리 예측할 방법이 없으니 무작위로 하나하나 다 바꿔가면서 찾는 것이죠. 여기서 이 [특정한 값]을 표현하는 것이 바로 nBits입니다.

예를 들어서 50만번째 블록을 보면(Block Height 499,999), 블록(헤더)의 해시값이 0000000000000000007962066dcd6675830883516bcf40047d42740a85eb2919입니다. 그리고 앞블록과 뒷블록도 이와 동일하게 블록 해시값이 18개의 0으로 시작합니다. 하나만 있어도 이상한 일인데, 3개가 연속으로 18개의 0으로 시작한다는 것은 자연적으로 일어날 가능성이 사실상 없습니다. 그럼 왜 이런 일이 일어났는가? nBits가 찾으라고 지시한 해시값이 (대충) 18개의 0으로 시작하는 해시값이기 때문입니다.

그런데 앞서도 언급했지만 nBits는 4바이트(32비트)입니다. 해시값은 256비트이므로, 목표가 되는 값을 32비트의 공간에 그대로 적을 수가 없습니다. 그래서 일정한 방식으로 인코딩한 값을 사용하며, 이것이 바로 nBits입니다. 구체적으로 위 50만번째 블록이 생성되던 당시의 nBits 값인 0x18009645를 예시로 하여 설명하겠습니다. 우선 nBits를 아래와 같이 두개로 쪼갭니다.

0x18
0x009645

이건 0x18바이트(10진수로는 24바이트, 0x18=24)의 숫자 중에서, 앞이 0x009645로 시작하는 수를 의미합니다. 즉 풀어쓰면

0x[009645]000000000000000000000000000000000000000000 (=48자리, 24바이트)보다 작은 값을 구하는 것이 목표라는 말이고,

가장 큰 256비트 수(2^256-1)와 나란히 놓고 앞에 0을 집어넣어보면 이런 모양이 됩니다.

0x0000000000000000009645000000000000000000000000000000000000000000
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF (=2^256-1)

그럼 이제 실제로 block height 499995-500005(모두 동일한 nBits 0x18009645를 공유하는 블록들)의 해시값과 위 숫자를 비교해봅시다.

0x0000000000000000009645000000000000000000000000000000000000000000 ← nBits에서 지정된 난이도 타겟

0x0000000000000000003a82a2e245d6a8be618045510e65eadce1eaa517a90845 ← Block Height 499,995의 해시값
0x00000000000000000001ddd1c1a1855e09ff84e2d2b5987cf165fcfbe8054bb3 ← Block Height 499,996의 해시값
0x00000000000000000034749458f656a299e5ec743fd856e5d2c3f1d51dd21dc6 ← Block Height 499,997의 해시값
0x00000000000000000085d465bc594e9d6d5664dfedb8dea5eedb55871248f3ec ← Block Height 499,998의 해시값
0x0000000000000000007962066dcd6675830883516bcf40047d42740a85eb2919 ← Block Height 499,999의 해시값
0x00000000000000000024fb37364cbf81fd49cc2d51c09c75c35433c3a1945d04 ← Block Height 500,000의 해시값
0x0000000000000000005c9959b3216f8640f94ec96edea69fe12ad7dee8b74e92 ← Block Height 500,001의 해시값
0x000000000000000000877d93d1412ca671750152ba0862db95f073b82c04b191 ← Block Height 500,002의 해시값
0x0000000000000000005467c7a728a3dcb17080d5fdca330043d51e298374f30e ← Block Height 500,003의 해시값
0x0000000000000000005d4da5924742e6d6372745f15c39feb05cf9b2e49e646d ← Block Height 500,004의 해시값
0x0000000000000000007150115460d0e92093aa937a913072d768f8136e289c2d ← Block Height 500,005의 해시값

즉 네트워크 해시레이트가 낮아지면 2016블록 주기로 점차 허용되는 값의 크기를 키워서(즉 정답이 나올 확률을 높게 만들어서) 그렇게 낮은 해시레이트에서도 10분에 한번쯤 답이 나오게 만들고, 네트워크 해시레이트가 높아지면 점차 허용되는 값의 크기를 낮춰서 10분에 한번쯤 답이 나오게 만드는 것이 nBits의 역할입니다. 풀버전 SHA-256을 깨는건 해시값으로 0x0이 64개가 나오는 원본 메시지를 찾으라는 것과 같은 의미입니다.


  B. 기타 사용례

여기까지 써놓고 보니 이렇게 두서 없이 작성하는 것에 회의가 느껴지네요. 나머지 SHA-256이 사용되는 부분들과 RIPEMD-160 관련 이야기는 나중에 파트별로 나눠서 쓸 때 기재하도록 하겠습니다.



IV. 비트코인 지갑주소의 생성방식

1. 서

원래는 이 부분에서 서명이 어떤식으로 동작하는가 따위를 다루려고 했습니다만, II. 에서 언급한 바와 같이 이런 내용은 이 후 새로 작성할 글에서 트랜잭션의 전체적인 개요를 다루면서 함께 설명하는 것이 나을 것 같아서 때려치우고 그냥 비트코인 지갑주소 생성방식이나 적어보도록 하겠습니다.


2. Private Key

  A. 생성방식

  비트코인의 private key는 무작위 256bit 숫자를 바탕으로 생성됩니다. 256bit는 2진수 256자리 숫자라는 뜻이고, 실제로는 16진수 형태의 키를 사용하기 때문에 64자리(2^256=16^64)입니다(byte로는 1 byte=8 bits, 256/8=32이므로, 32 bytes). 0 이상 2^256 이하의 모든 숫자가 허용되는 것은 아니지만 대부분의 숫자가 허용되는 ECDSA 키이며, 보다 구체적으로

0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0001부터
FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4140까지가 허용됩니다.

이런 Private Key는 무작위 수를 프로그램이 생성하는 방법으로 만들 수도 있고(초기 버전에서 사용하던 방식), 그냥 손으로 0과 1을 랜덤으로 256개 적어서 만들 수도 있고, 일정한 시드를 바탕으로 순차적으로 생성하도록 만들 수도 있는데(후기 버전에서 추가된 방식, BIP 0032), 마지막에 언급한 HD wallet은 별로 중요한 것이 아니니까 자세한 설명은 나중에 키 파트를 쓰게 되면 거기서 하겠습니다.


  B. Private Key ↔ Wallet Import Format

실제로 지갑 프로그램들에서 export/import 할 때 사용하는 키는 위와 같은 원형의 private key가 아니고, 그것을 일정한 방식으로 인코딩한 포맷(Wallet Import Format)입니다. 이러한 WIF는 다음과 같은 방식으로 생성됩니다.

우선 사용자가 가진 private key(랜덤 2^256 숫자) 앞에다가 2자리 버전넘버 80을 붙이고(, 뒤에다 2자리 압축플래그 01을 붙여서)(optional), extended key(A)를 만듭니다. 그 뒤에 A를 SHA256로 해싱하여 새로운 해시값(B)를 구하고, 그 해시값(B)를 다시 SHA256로 해싱하여 최종적인 해시(C)를 구합니다. 그 뒤 이 해시값(C)의 첫 8글자를 딴 뒤(D), D를 A 뒤에다 체크섬으로 붙여서 E를 만듭니다. 그 다음 이 E에다 Base58 encoding(대소문자 26x2개와 숫자 10개에서 헷갈리는 대문자 I와 소문자 l, 그리고 숫자 0과 대문자 O를 제외한 58개의 알파벳과 숫자만으로 표현하는 것)을 해주면, 일반적으로 지갑 프로그램 들에서 사용하는 Wallet Import Format(F)가 됩니다.

위 내용을 예시를 통해 다시 적어보겠습니다. 우선 10진수 1234를 private key로 쓰는 경우, 이것은 16진수로 4D2이고, 다음과 같은 모양입니다.
00000000000000000000000000000000000000000000000000000000000004D2

여기에 앞에 2자리 버전넘버 80을 붙이면 다음의 값이 나오고,
8000000000000000000000000000000000000000000000000000000000000004D2

뒤에다가 2자리 압축플래그를 붙이면(optional) 다음의 extended key(A)가 나옵니다.
8000000000000000000000000000000000000000000000000000000000000004D201

위 extended key(A)의 SHA256 해시값(B)은 다음과 같고,
59B7F043A57BC13AEE2DFF8AF9CFD99B24809863A62B25C2F9FE22BB043B8DBA

위 해시값(B)의 SHA256 해시값(C)은 다음과 같으며,
C4528359AFF45376A2676957C4056062EB5B352CA2C044BD133AEB5CEA128167

위 값의 앞 4바이트(C4528359)를 따서(D), extended key(A) 뒤에다 붙이면 다음과 같은 형태(E)가 됩니다.
8000000000000000000000000000000000000000000000000000000000000004D201C4528359

그 다음 이 값(E)을 Base58 encoding을 해주면, 다음과 같은 형태의 Wallet Import Format(F)이 완성됩니다.
KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYjgd9M7rFUHdsRju8r4

역순으로 Base58 decoding - 뒤 8글자 삭제 - 앞 2글자(+뒤 2글자 삭제, optional) 삭제를 하면 원본 private key가 됩니다. 왜 이런 방식을 쓰느냐? 짧아서 보기 좋은 것도 있긴 하지만, 주로 오타 등의 방지용입니다. 보다시피 체크섬이 있어서 오타나 복붙 실수를 하면 확인이 가능하거든요. 그 외에도 Compressed public key와 연계된 private key의 base 58 encoding은 메인넷의 경우 항상 L 혹은 K로 시작하고(테스트넷은 c) 항상 52글자이며, Uncompressed public key와 연계된 private key의 base 58 encoding은 메인넷의 경우 항상 5로 시작하고(테스트넷은 9) 항상 51글자라는 특징이 있습니다.

아무튼 위 WIF가 [dumpprivkey 지갑주소] 명령어를 쳤을 때 나오는 키입니다.


  C. Mini Private Key → Private Key

Mini Private Key는 더 짧은 형태의 Private Key입니다. Mini Private Key는 ①대문자 S로 시작하는, ②30글자의 Base58 코드 중, ③뒤에 물음표 [?]를 붙인 스트링을 SHA256로 해싱했을 때 첫 바이트가 [00]이 나오는 것을 의미하며, 이렇게 해싱되어 나온 값이 Private Key가 됩니다. 다시 말해 Mini Private Key로부터 Private Key를 추출하는 과정은 일방통행이기 때문에, Private Key를 먼저 만든 뒤 Mini Private Key를 생성할 수는 없고, 먼저 위 조건을 만족시키는 Mini Private Key를 찾은 후 Private Key를 생성하여 사용하는 형태가 됩니다.

Private Key 대비 길이가 약 58% 수준이니 그냥 암기를 통해서 보관할 때 까먹기 위협에 대해 좀 더 안전하고(51-52글자보다는 30글자를 까먹을 확률이 낮으니), 눈으로 제대로 입력하였는지 확인하기가 용이하며, QR이나 바코드 등으로 만들었을 때 동일 수준의 밀도나 error correction이라면 더 작아지기 때문에 더 작게 인쇄할 수 있다는 등의 장점이 있습니다만, 그렇게 널리 사용되지는 않습니다.


  D. Brian Wallet → Private Key

또 다른 변형으로는 Brain wallet이 있는데, 기본적으로는 IV.2.C.와 같으나 자기가 외우기 쉬운 문자열을 택해서 그걸 원본으로 사용한다는 점이 다릅니다. 예를 들어서 성경 New International Version (NIV)의 Luke 23:41은

We are punished justly, for we are getting what our deeds deserve. But this man has done nothing wrong.

인데, 위 스트링의 SHA256 해시값은 다음과 같습니다.

0DC181342B7F271DCE9DC37255EC154B6DB5DC281B09487C7B853EA5CE8CC495

이런 식으로 도출된 해시값을 그대로 Private Key로 쓰는 겁니다(위 Private Key와 compressed public key 페어의 WIF는 KwgT5maRmxAiXo6ksCPJew6srJz1DrkRwdwEiAnTKhMHjhKBi1Ek, 비트코인 주소는 1MSLFtcGqtDqXSs2LPahBjmY3iN7ABJmQV가 됩니다).

이 방식에는 문제점이 여러가지가 있는데, 우선 위와 같이 책에서 추출하는 경우 같은 책이라도 버전이나 판본에 따라서 내용이 달라지는 경우가 꽤 있습니다. 그런데 해시 함수는 내용이 아주 조금만 바뀌어도 결과물이 완전히 달라지기 때문에, 자기가 특정 책의 희귀 판본에서 문구를 추출하였는데, 추출한 위치의 내용이 향후 판본에서 변경되었고, 자기가 추출한 책을 보관하고 있지 않은 경우(게다가 정확한 판본을 모르는 경우), 추출 위치를 기억함에도 불구하고 회수를 못 하는 경우가 발생할 수 있습니다.

또 자기가 초기 해시값 도출 과정에서 오타를 냈었던 경우