SHA-256 By Hand - Round 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 

전체 흐름 복습

 

이제 핵심이랄 수 있는 Round Function 에 들어가기 전에

전체 흐름을 흝어보고, Round Function 의 위치를 알아보자.

 

1) SHA-256 을 먹이고 싶은 메시지 M 이 있다.

2) Padding

- 메시지 M 에 1 하나 붙이고 0을 쭈욱 단 다음에 M 의 길이정보를 마지막 64비트에 넣은 M' 를 만든다.

- M' 는 512 비트 * n 개 만큼의 길이이다.

3) Parsing

- 하나의 512 비트를 블록이라 한다.

- 이것을 32비트 x 16개로  나눈다.

4) Round Function

- 하나의 블록단위로 Round Function 을 64번 먹인다.

- 준비물은 이전블록에서 가져온 H (맨 처음 H는 상수값, 32비트 8개)

- 언제나 64번 먹일 수 있게 준비된 K (32비트 상수값 64개)

- 그리고 하나의 블록의 32비트 16개를 MEXP 를 먹여 64개로 뻥튀기한 W

→ H, K, W 들을 64번 Round Function 에 먹여서 H' 를 만들어낸다.

→ 이 H'는 다음 블록 Round Function 의 첫 H가 된다.

5) 맨 마지막에 나오는 H' 가 바로 입력된 M 을 SHA-256 먹인 해시값이다.

 

 

 

 

해봅시다용

 

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

- 이것의 카피본을 만들고 입력값을 넣어보자.

- 저번 포스팅에서는 "abc"를 넣었지만

- 이번에는 좀 긴 걸 넣어보자

바람이 분다 서러운 마음에  텅 빈 풍경이 불어온다  머리를 자르고 돌아오는 길에  내내 글썽이던 눈물을 쏟는다  하늘이 젖는다  어두운 거리에 찬 빗방울이 떨어진다  무리를 지으며  따라오는 비는 내게서 먼 것 같아  이미 그친 것 같아    세상은 어제와 같고 시간은 흐르고 있고  나만 혼자 이렇게 달라져 있다  바람에 흩어져 버린  허무한 내 소원들은 애타게 사라져간다  바람이 분다  시린 한기 속에 지난 시간을 되돌린다  여름 끝에 선  너의 뒷모습이 차가웠던 것 같아  다 알 것 같아  내게는 소중해했던 잠 못 이루던 날들이  너에겐 지금과 다르지 않았다  사랑은 비극이어라 그대는 내가 아니다  추억은 다르게 적힌다   나의 이별은  잘 가라는 인사도 없이 치러진다  세상은 어제와 같고 시간은 흐르고 있고  나만 혼자 이렇게 달라져 있다  내게는 천금같았던 추억이 담겨져 있던  머리위로 바람이 분다  눈물이 흐른다

 

넣은 결과

 

- 오른쪽에 만들어진 해시가 보인다. 63337C029EA109700472740397FF1C6BCD89688DD018584D13FC17D72714308C

 

 

 

W 확인

 

- 이소라 노래가사 입력에 대한 padding, parsing 된 이후의 첫 블록으로 만들어진 첫 W 값을 확인해보자 (input Sheet)

- 아래 W0 값이 보인다. 20000000  

 

 

 

본격적인 Round Function 계산

 

계산순서는 다음과 같다.

 

1) 그냥 한자리씩 옯기는 값들

- New b = a

- New c = b

- New d = c

- New f = e

- New g = f

- New h = g

 

2) (편의를 위해) 중간단계 T1 을 구해보자면

- T1 = Σ0(a)  + Maj(a,b,c)

- Σ0(a) 는 a 값을 2, 13, 22 만큼 오른쪽으로 돌린 다음에, 그 세 값에 1이 홀수이면 1이고, 0이거나 짝수이면 0인것이다.

- Maj(a,b,c) 는 a, b, c 의 같은 위치 비트가 1이 많으면 1, 0이 많으면 0인 거다.

 

3) (편의를 위해) 중간단계 T2 를 구해보자면

- T2 = Σ1(e)  + Ch(e,f,g) + h + W0 + K0

- Σ1(e) 는 e 값을 6, 11, 25 만큼 오른쪽으로 돌린 다음에, 그 세 값에 1이 홀수이면 1이고, 0이거나 짝수이면 0인것이다.

- Ch(e,f,g) 는 e가 1이면 f 값을 선택 (Choose), 0이면 g 값을 선택하는 것이다.

- W0 값은 위에서 계산하였고, K0 은 주어진 상수값

 

4) New a값 계산하기

- New a = T1 + T2

 

5) New e 값 계산하기

- New e = T2 + d

 

 

 

 

 

1) round 1 을 보면 우리의 입력값 W0을 확인할 수 있다.

 

 

2) 새로운 b, c, d, f, g, h 값은 이전 값들에서 그냥 가져오면 된다.

 

 

 

3) T1 을 계산하자면

 

- 빨간색이  Σ0(a) 계산이고 CE20B47E

- 파란색이 Maj(a,b,c) 계산이다. 3A6FE667

- 이 둘을 더한게 T1 인데 여기서는 나중에 나오는 T2 까지 계산해서 다 더해버렸다.

→ 계산해보면 T1 은 두 값을 더한뒤 맨 위로 캐리된 값을 버리면 된다. 0xCE20B47E + 0x3A6FE667 = 0x08909AE5

https://goo.gl/AkieUD

 

 

4) T2 를 계산하자면

 

- 빨간색이  Σ1(e) 계산이고 0x3587272B

- 파란색이 Maj(a,b,c) 계산이다. 0x1F85C98C

- 이 둘에다가 h 값 (=초기값 H0의 8번째 값) 0x5BE0CD19, W0 값 0x20000000, K0  값 0x428a2f98 을 더해주면 된다.

→ T2 를 계산해보면 모두 더한 뒤 위로 캐리된 값을 버리면 된다.

→ 0x3587272B + 0x1F85C98C + 0x5BE0CD19 + 0x20000000 + 0x428a2f98 =  0x1377ED68

https://goo.gl/CAXnw5

 

 

 

5) New a 와 New e 계산

 

- New a = T1 + T2 = 0x08909AE5 + 0x1377ED68 = 0x1C08884D

- https://goo.gl/BGjE69

 

- New e = T2 + d = 0x1377ED68 + 0xA54FF53A = 0xB8C7E2A2

- https://goo.gl/vhoNzi