티스토리 뷰

blockchain

SHA-256 프로세스 정리

fistful 2018. 8. 28. 13:11
반응형

SHA-256 씨리이즈

 


잡담

 

그리 똑똑한 머리가 아니라, SHA-256 손으로 계산하는게 어렵지만은 않다는 이야기에

시도하다가 막히고, 포기하려다 조금 더볼까를 며칠 반복하였다.

구글링을 해도 한글로 자료도 없더라. 추측해본바

 

1) 애써 이거 이해할 필요도 없는데 그냥 개념만 이해하고 써먹자는 사람들이 있을꺼고,

2) 휘리릭 이해해버렸는데, ( 사람 입장에서) 이리 쉬운걸 애써 정리할 필요를 못느끼기도 했을거고,

3) (나처럼), 겨우겨우 이해했는데, 지치고 정리까지 엄두나 시간이 안나서 안한게 아닐까 싶다.

 

SHA-256 구글링에서 나온 다양한 포스팅과 유튜브를 들여다 보면서도

막히는 부분이 많았고, 전체적인 그림을 그리기 쉽지 않았다.

 

풀어나는 방법

 

SHA-256 크게 Pre-processing (전처리) 실제적인 Algorithm 으로 나뉘는데,

개인적인 판단으로 Algorithm 에서 부터 풀어나가며 중심을 잡고,

곁다리로 필요한 항목을 붙여나가보겠다.

 

* 전체적인 그림을 그리는데는 아래 링크의 그림들이 도움이 되었다.

여기에 올리는 많은 그림들의 출처도 링크이다.

 

- 링크: https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml

- 검색해보니 로체스터 공과대학으로 나온다.

 

 

Algorithm

 

함수란 y = f(x) 이다. x 넣으면, y 나온다.

SHA-256 y = f(H, W, K) 이다. H 초기값은 상수이고, K 상수이다.

 

 

512 bit 메시지 덩어리

 

나중에 좀더 설명하겠지만,  SHA-256 먹일 메시지 M padding parsing 거쳐 512 bit 블록이 되는데,

블록 하나당 아래와 같은 연산이 이루어지며, 결과는 아래쪽의 Hi+1 (= a, b, c, d, e, f, g, h) 된다.

만약 메시지 M 에서 만들어지는 블록이 10개라면 아래 그림의 연산이 10 일어나는 것이다.

 

 


 

 

그림에서 H, W, K 아래와 같다.

 

- H (= a, b, c, d, e, f, g, h) 256 비트이다.

- a, b, c, d, e, f, g, h 각각 4 바이트 = 32 비트이며, 16진수로 치면 8 자리 숫자이다.

- H0 상수값이고, 이후의 블럭에 적용될 Hi 값은 이전 블럭에서 생성된 Hi-1 값이 된다.

 

- K 32 비트 짜리 값이 64개인 상수값들이다.

- 64번의 Round Function 각각 하나씩의 K값이 순서대로 적용된다.

 

- W 32 비트 짜리 값이 64 이며

- 64번의 Round Function 각각 하나씩의 W값이 순서대로 적용된다.

- W 메시지 블록 Mi 에서 만들어지는데 Mi 32비트 짜리 값이 16개이다.

- 16개를 4배로 부풀려서 64개의 W 값을 만들어내는 것이다. (Message Expansion Function)

 


 

 

H 만드는

 

- H 초기값 H0 또는 이전 블럭에서 만들어진 Hi-1 값이 들어와

- 64번의 round function 거쳐 Hi 값이 생성된다. (그림에서는 Hi, Hi+1 명시되어 있지만 적당히 이해해주시라)

- 그러면 처음 블럭의 처음 W0, K0 함께 Round Function 쓰일 H0 무얼까?

 

H0 상수값이다.

1) 2부터 시작하는 소수 8개를 루트를 씌운

2) 소수점 아래자리 32 비트를 추려낸 것이다.

 

아래는 소수인 2, 3, 5, 7, 11, 13, 17, 19 만들어낸 H0 8 이다.

실제 계산 코드 snippet: https://goo.gl/pFq6Dp

 


 

 

K 만드는

 

- K 64개의 32 바이트 (= 16진수 8) 상수값이며

- 하나의 블럭 계산시 64개가 쓰인다.

- 최초의 H0 상수값이고, 이후에는 계산된 값이 쓰이는 H 와는 달리

- K 64개의 상수값이 항상 변함없이 쓰인다.

 

K 만드는법은 H 제곱근을 쓰는 것과 달리 세제곱근을 사용하는 것만이 다르다.

실제 계산 코드 snippet: https://goo.gl/pFq6Dp

 


 

W 만드는 (+ Pre-Processing)

 

순서와 글의 Level 뒤죽박죽이긴 하지만 W 만드는 법은 Algorithm Pre-Processing 겹쳐 있어서 하나 상위로 빼낸다.

 

 

하나의 블럭을 계산하는데 사용되는 아래 그림의 입력값 중에서

H K 알아보았다. 이제 W 알아보자.

 



 

 

Pre-processing - Padding

 

1. SHA-256 먹이고픈 메시지 M

2. 마지막 64 비트에 메시지 M 크기정보 (=bits) 넣어주고

3. 512 나눠떨어지게 1 하나와 0 들로 채워주는 작업이다.

 

아래 그림을 예로 들어보자.

 

1. 메시지 M  a, b, c 이다.

2. 뒤쪽 64비트에 M 크기 (= bits) 값인 24 넣어주자

3. 메시지 바로 뒤에는 1 하나 써주고, 남은 공백 423 개는 모두 0으로 채워준다.

4. 우리는 방금 메시지 M padding 하여 512 나누어 떨어지는 메시지인 M' 만들었다.

 


 

< 출처: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf >

 

참고1. 예시에서 메시지 M "abc" 이지만, 메시지 M 동영상이라면? M' 512 배수인 크기를 가진 매우 메시지일것이다. 

참고2. 마지막에 길이정보를 넣을까? 이걸 넣지 않으면 메시지 "00" "000" "00000" padding 값이 같아질 것이다.

 

 

Pre-processing - Parsing

 

이제 padding 통해 512 배수만큼의 길이를 가진 메시지 M' 만들어졌다.

1) 이를 512 비트로 나누고, 

2) 다시 512 비트를 32비트씩 16개로 나누는 것이 parsing 이다.

 

 

W 만들기

 

padding parsing 거쳐 만들어진 M' 블럭들의 개수만큼 아래 프로세스가 이루어지게 된다.

 



 

 

M' 블럭은 512 바이트이니 하나의 Round function 에서 쓰이는 32바이트씩 나누면 512/32 = 16 이다.

그런데 그림에는 W 64개가 보인다.

 

1) 16개는 M' 블럭 하나를 그대로 가져다 쓰지만

2) 나머지 64 - 16 = 48 개는 그림의 MEXP (=Message Expansion Function) 으로 만들어낸다.

 

작은 함수들을 따로 묶어서 정리하려 하였는데 잠깐만 언급하자면

 

1) W0 - W15 M' 블럭을 32 비트씩 나눈 16개의 값이다.

2) W16 보면 아래와 같은 값들의 연산으로 만들어내는 것이다.

- W16-2 = W14

- W16-7 = W9

- W16-15 = W1

- W16-16 = W0

3) 이후에 적용되는 σ0, σ1, + 함수는 따로 설명하겠다.



 

 

 

전체 큰그림 다시보기

 

- 컴팩트하게 정리하려 하면서도 이해가 쉽게 하려다보니 글이 너무 늘어지는 같다. (능력의 한계)

- 지금까지의 내용을 정리해보면 아래 그림과 같다.

 

1) 2) H 초기값 H0 K 값은 각각 소수들의 제곱근, 세제곱근의 소수점 아래 값들에서 만들어낸 상수값이다.

3) SHA-256 으로 해싱할 메시지 M padding 되고 parsing 된다.

4) padding, parsing 메시지 M' 블럭들은 다시 Message Expansion Function 통해 64개의 W 값들로 만들어진다

5) 이렇게 만들어진 재료인 H, K, W 값들을, 블럭당 64번의 Round Function 연산을 하는데 집어넣게 되고, 최종적으로 블럭의 H 값이 계산되어 나온다.

 

* Round function 에는 시그마0, 시그마1, Maj, Choose, + 등의 연산이 사용된다.

 

 


 

< 짜집기한 그림 출처들 >

- https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

- https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml

- https://medium.com/biffures/part-5-hashing-with-sha-256-4c2afc191c40

 

 

기타 함수들

 

- 설명이 빠진 함수들이 있다.

- 여기서는 간략한 소개만 하고, 다음 포스팅에서 실제로 하나의 Round function 따라가보면서 이해해보도록 하자

 

Round Function

 

- 다음 포스팅에는 실제 연산을 다룰 예정이니, 좀더 이해를 도울 있겠다.

 

0 <= i  <=63 일때 i번째 Round Function 아래와 같이 이루어진다.

 

1) 입력값은 Ki, Wi H에서 만들어진 a, b, c, d, e, f, g, h

2) Round Function 출력값은 다음 단계의 입력이 되는 a, b, c, d, e, f, g, h 된다.

3) 출력값 b, c, d, f, g, h 각각 입력값 a, b, c, e, f, g 그대로 전달되며

4) 출력값 a e 다양한 연산을 거쳐서 만들어진다.

 


 

 

조그만 함수들

 

포스팅에서 언급된 utility 같이 사용되는 작은 연산들은 아래와 같다.

< 출처: https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml >

Message Expansion Function 쓰임

- σ0(X) = (X right-rotate 7) xor (X right-rotate 18) xor (X right-shift 3)

- σ1(X) = (X right-rotate 17) xor (X right-rotate 19) xor (X right-shift 10)

 

Round Function 쓰임

Σ0(X) = (X right-rotate 2) xor (X right-rotate 13) xor (X right-rotate 22)

Σ1(X) = (X right-rotate 6) xor (X right-rotate 11) xor (X right-rotate 25)

Ch(X,Y,Z) = (X and Y) xor ((not X) and Z)

Maj(X,Y,Z) = (X and Y) xor (X and Z) xor (Y and Z) 

 

아래 설명은 엑셀로 SHA-256 구현한  구글시트 ( https://goo.gl/Sn8x2r ) round 1 sheet 에서 가져왔다.

* Message Expansion Function 부분은 생략.

 

 

Σ0(X) = (X right-rotate 2) xor (X right-rotate 13) xor (X right-rotate 22)

 

- X A 라고 보면

- A 비트를 각각 2, 13, 22 오른쪽으로 옮기고, 넘어가는 비트는 다시 왼쪽에 채워넣는다

- 그리고, 같은 자리의 비트값을 XOR 해준다. 결과적으로는 모두 더해준 다음 첫번째 자리의 비트값만 적어도 된다.

 



 

 

Σ1(X) = (X right-rotate 6) xor (X right-rotate 11) xor (X right-rotate 25)

 

- X E 라고 보면

- E 비트를 각각 6, 11, 25 오른쪽으로 옮기고, 넘어가는 비트는 다시 왼쪽에 채워넣는다.

- 그리고, 같은 자리의 비트값을 XOR 해준다. 결과적으로는 모두 더해준 다음 첫번째 자리의 비트값만 적어도 된다.

 


 

 

Ch(X,Y,Z) = (X and Y) xor ((not X) and Z)

 

- Ch Choose 이다.

- X, Y, Z E, F, G 라고 보면

- E 비트가 1이면 F 값을 취하고, 0이면 G 값을 취하는 것이다.

 


 

Maj(X,Y,Z) = (X and Y) xor (X and Z) xor (Y and Z) 

 

- Maj Majority 보인다. 과반수? 다수결?

- X, Y, Z A, B, C 라고 보면

- A, B, C 비트들이 0 많으면 0, 1 많으면 1 되는 것이다.

 


 

다음 포스팅에는 라운드만 실제로 구글시트에 써가면서 계산해보겠다.


반응형

'blockchain' 카테고리의 다른 글

bitcoin block의 timestamp  (0) 2018.09.07
SHA-256 Bitcoin  (0) 2018.09.01
SHA-256 By Hand - Round Function  (0) 2018.08.31
SHA-256 By Hand - Message Expansion Function  (0) 2018.08.29
SHA-256 프로세스 정리  (0) 2018.08.28
SHA-256 Hash Algorithm  (1) 2018.08.27
댓글
댓글쓰기 폼