SHA-256 By Hand - Message Expansion Function

SHA-256 씨리이즈

 

1. SHA-256 Hash Algorithm 2. SHA-256 프로세스 정리 3. SHA-256 By Hand - Message Expansion Function 4. SHA-256 By Hand - Round Function 5. SHA-256 Bitcoin

 

* 사용된 이미지들의 출처: https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml

 

잡담

 

MEXP (Message Expansion Function) 는 생략하고 Round Function 만 할까 했는데

MEXP 도 별도로 언급하고, 손으로 (정확히는 구글시트에 기입) 계산해보려 한다.

- 지식의 저주가 마음에 걸려서 (= 난 이미 알고 있으니, 요건 쉽겠지 했다가 누군가는 또 헤맬 수 있겠다는 생각에)

 

 

큰 그림에서의 MEXP 와 작은 그림에서 MEXP 에서 사용하는 Functions

 

큰 그림

 

1) 입력값 M 은 padding, parsing 을 거치면 512 비트의 블럭(들) 이 된다.

2) 하나의 블럭 (512 비트)를 이용하여 64번의 Round Function 에 각각 32 비트씩의 입력값을 넣어줘야 한다.

3) 하지만 512 비트로는 512 / 32 = 16 번 밖에 넣어줄 수 없다.

4) 그래서 MEXP (Message Expansion Function) 을 이용하여 나머지 64 - 16 = 48 개의 32비트 값을 생성해준다.

 

 

 

 

작은 그림

 

1) 입력값 M 을 padding, parsing 하여 생성된 512 비트 블럭(들)

2) 하나의 블럭을 16개의 32비트 값으로 나누어 W0, W1, …, W15 를 만든다

3) 그리고 이들을 이용하여 W16, W17, …, W63 을 순차적으로 만든다.

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

- W16-2 = W14

- W16-7 = W9

- W16-15 = W1

- W16-16 = W0

5) 예를 들어 W63 를 보면 아래와 같은 값들의 연산으로 만들어내는 것이다.

- W63-2 = W61

- W63-7 = W56

- W63-15 = W48

- W63-16 = W47

 

위에서 만들어낸 4개의 값을 아래의 방법으로 연산하여 W 값을 만들어낸다.

 

 

 

Functions

 

Wi 계산에 사용되는 함수들을 알아보자

 

+ 함수

- 별거 없다. 그냥 모두 더하고 16진수 8자리를 넘어가는 값은 버리는 거다.

- 코딩할때는 대략 모두 더한 값 % 2^32 해주면 되겠다.

 

σ0(X) 함수

 

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

1) 오른쪽으로 7번 rotate 해주고 (이 경우 오른쪽으로 밀린 맨 끝 7 비트는 왼쪽 앞으로 rotate 되어 온다)

2) 오른쪽으로 18번 rotate 해주고 (이 경우 오른쪽으로 밀린 맨 끝 18 비트는 왼쪽 앞으로 rotate 되어 온다)

3) 오른쪽으로 3번 shift 해준 다음 (이 경우 맨 왼쪽 3비트는 0이 된다.)

 

 

σ1(X) 함수

 

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

- rotate, shift 되는 양만 다르지 σ0(X) 함수와 같다.

1) 오른쪽으로 17번 rotate 해주고 (이 경우 오른쪽으로 밀린 맨 끝 17 비트는 왼쪽 앞으로 rotate 되어 온다)

2) 오른쪽으로 19번 rotate 해주고 (이 경우 오른쪽으로 밀린 맨 끝 19 비트는 왼쪽 앞으로 rotate 되어 온다)

3) 오른쪽으로 10번 shift 해준 다음 (이 경우 맨 왼쪽 10비트는 0이 된다.)

 

 

실습전 정답부터 보자

 

abc 를 입력한다고 할때에

 

- SHA-256 을 단계별로 구현해둔 구글시트가 있다. https://goo.gl/Sn8x2r

- 카피본을 만들어 SHA-256 해시 하려는 입력을 "abc" 로 넣어보자

→ Start Here, user interface 시트에서 "abc" 라고 입력을 넣었다. 오른쪽에 노란색으로 하이라이트된 최종 해시값도 보인다.

 

 

 

 

 

이제 input 시트로 가보자

 

- a, b, c 입력값은 ASCII code 로 0x61, 0x62, 0x63 이다.

- 비트로 바꾸면 각각 0110 0001, 0110 0010, 0110 0011 이다. 아래그림 W0 의 값의 시작 24 비트와 일치한다.

- padding 방법에 따라 그다음에 1이 붙고, 나머지는 0으로 채운다.

- 마지막으로 W15 끝자락을 보면 11000 이 있다. 십진수로 바꾸면 24 이다. abc 의 크기 (=비트개수) 이다.

 

- 이렇게 padding 하고 512 비트 크기로 나눈 첫 블록 (이면서 abc 입력 예제에서는 마지막 블록)이 생성되었고,

- 이걸 32 비트씩 쪼개어 W0, W1, …, W15 가 준비되었다.

→ 이걸 MEXP 함수를 먹여 계산한 W16 값이 01100001011000100110001110000000 이다.

 

 

 

실습 - W16 을 계산해보자

 

위 예제에서 확인한 입력값에서 나온 W0, W1, …, W15 과 W16의 값은 아래와 같다.

 

W0	01100001011000100110001110000000
W1	00000000000000000000000000000000
W2	00000000000000000000000000000000
W3	00000000000000000000000000000000
W4	00000000000000000000000000000000
W5	00000000000000000000000000000000
W6	00000000000000000000000000000000
W7	00000000000000000000000000000000
W8	00000000000000000000000000000000
W9	00000000000000000000000000000000
W10	00000000000000000000000000000000
W11	00000000000000000000000000000000
W12	00000000000000000000000000000000
W13	00000000000000000000000000000000
W14	00000000000000000000000000000000
W15	00000000000000000000000000011000
W16	01100001011000100110001110000000

 

이제 실제 계산을 해보자

 

 

 

입력값	- W16-2 = W14 - W16-7 = W9 - W16-15 = W1 - W16-16 = W0
W0	01100001011000100110001110000000
W1	00000000000000000000000000000000
W9	00000000000000000000000000000000
W14	00000000000000000000000000000000

 

σ1(W14) + W9 + σ0(W1) + W0

 

계산한 구글시트 링크: https://goo.gl/ejWgka

→ 실제로 계산하다보니 "abc" 입력은 명확히 계산단계별 의미를 보여주기 적절치 않다는 것을 인지했으나 좀 늦었음. ㅠ,.ㅜ)

 

1) 계산을 위한 값 준비

 

 

2) σ1(W14) 계산

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

 

먼저 rotate 와 shift 만큼 오른쪽으로 자리를 옮기고

 

rotate 는 오른쪽으로 넘치는 비트를 왼쪽의 빈 공간으로 옮기고, shift 는 왼쪽의 빈 공간을 0으로 채운다.

- 그런데 이 예제에서는 rotate 와 shift 의 차이를 볼 수 없다…;;;

 

 

마지막으로, rotate, shift 한 세 값을 XOR 해주면 된다.

 

 

 

3) σ0(W1) 계산

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

 

rotate 와 shift 횟수만 다르고 위과 같은 순서로 계산하면 된다.

 

 

4) 더하기

 

정답과 같은 결과를 확인 할 수 있다.

- W16

0110 0001 0110 0010 0110 0011 1000 0000