SHA-256 Hash Algorithm

개요

 

*  총 5번의 포스팅으로 나눠서 아래 내용을 다룰 예정이다.

 

- 블록체인, 그 중에서도 비트코인에서 사용되는 SHA-256 해시함수에 대해 알아보고

- 전체적인 계산 프로세스를 정리한 다음

- 손으로 (정확히는 구글시트에) MEXP 와 한 라운드 계산을 해본다.

- 마지막으로, 실제 비트코인 블럭의 해시 계산을 해본다

 

 

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

 

 

주요 참고출처

 

- SHA 공식 문서: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf - 계산과정: https://medium.com/biffures/part-5-hashing-with-sha-256-4c2afc191c40 - 전체 이해에 도움이 되는 그림 많음: https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml - 손으로 직접 풀어보기 - 포스팅: http://www.righto.com/2014/09/mining-bitcoin-with-pencil-and-paper.html - 유튜브: https://youtu.be/y3dqhixzGVo - 엑셀로 풀어보기 - 원문: https://goo.gl/Sn8x2r - 테스트를 위한 카피본: https://goo.gl/A85Y6x

 

 

SHA (Secure Hash Algorithm)

 

- NSA 에서 만튼 암호학적 해시함수들의 총칭

- SHA-1 과 SHA-256 이 많이 쓰인다.

- SHA-0, SHA-1 에 대한 공격 이미 발견되었다.

- SHA-2 는 발견되지 않았지만 SHA-1 과 비슷한 방법들을 쓰기에 발견될 가능성이 있음

 

 

 

< 출처: https://goo.gl/hHXTMg >

 

 

- 입력메시지가 들어오면 크기에 상관없이 해시값 크기만큼의 비트로 계산된다.

- 예를 들어 SHA-256 의 경우는 최대 2^64 크기까지의 입력을 받아서 256 bit 크기의 해시값을 출력한다.

- 길이한계는 입력받을 수 있는 메시지의 2의 승수를 의미한다. 예를 들어 SHA-256 은 2^64 크기의 입력값을 받을 수 있다.

 

< 출처: https://www.wikiwand.com/ko/SHA >

 

(참고) 2^64 비트란 얼마나 큰 크기일까?

- 계산: https://goo.gl/uFRZCh

- 2014년 페이스북 data warehouse 용량의 7배

 

 

HASH 함수의 핵심 요건

 

공식적으로 명시된 것에 더하여, 몇몇 중요 특징을 적어본다.

 

1) 역상(pre-image) - 해시값에서 입력값을 역방향으로 찾는 것이 계산적으로 불가능해야 한다.   2) 제2역상(2nd preimage) - 하나의 입력값으로 계산한 해시값과 같은 해시값을 생성하는 다른 입력값을 찾는것이 계산적으로 불가능해야 한다. - 약한 충돌 저항성 (Weak collision resistance) 이라고도 한다.   3) 충돌쌍(collision) -  같은 해시값을 내는 두 개의 입력값을 찾는 것이 계산적으로 불가능해야 한다. 2) 와의 미묘한 차이에 주의 - 강한 충돌 저항성 (Strong collision resistance) 이라고도 한다.   4) 계산비용 - 해시함수의 계산비용이 적게 들어야 한다. (= 메모리도 적게먹고, 계산시간도 적게들어야 한다.) - 블록체인에서는 이전의 블록들이 문제없는지 검산을 하는데, 이때 계산비용이 많이 들어서는 안된다.   5) Avalanche Effect - 입력값이 조금만 바뀌어도, 입력값의 차이를 유추하기 불가능할 정도의 전혀 다른 해시값이 나와야 한다. (아래그림 참고) - 이때문에 2) 3) 같은 특성을 만족하게 된다.

 

 

 

< 출처: https://www.wikiwand.com/en/Cryptographic_hash_function >