sha 256 알고리즘 정리

레퍼런스 문서

http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4.pdf

각 block 내용 및 W[64]의 내용들이 자세하게 나와있음

http://csrc.nist.gov/groups/ST/toolkit/documents/Examples/SHA256.pdf

위와 비슷한 정보 

http://www.iwar.org.uk/comsec/resources/cipher/sha256-384-512.pdf

sha256은 hash 함수의 일종이다

hash 함수라는게 뭐냐면 다 알고 있겠지만 간단히 설명해보겠다

y = x + 2 이런 함수는 y를 알면 x도 알 수 있다

하지만 y = hash(x) 이런 해쉬 함수는 y를 알아도 x를 알 수 없는게 특징이다

그리고 모든 x값에 대해 각기 다른 y값을 내뱉는 특징 때문에 x가 원본임을 증명하는 일종의 시그니쳐로도 사용할 수 있다

(정확하게 말하자면 hash 함수는 단사함수가 아니다. hash collision이 있어서 다른 x임에도 같은 y값이 나오는 경우도 있다.

 hash collision을 피하기 위해선 계산을 더 복잡하게 하면 된다. 적당한 기회 비용을 두고 밀당을 해야한다는 소리)

hash 결과값은 32bit 8개를 병렬로 늘어놓은 값 

32bit x 8 = 256bit 그래서 이름이 sha256이다

원본 메세지의 각 문자(ascii 8bit)를 적당히 잘라 붙이고 쉬프트하고 and, or 등등 해서 512bit 단위의 블럭으로 만들고 이를 볶고 지져 hash를 계산한다

512bit 블럭으로 만들기 위해 크면 자르고(parsing) 모자라면 붙인다(padding)

아래의 공식에 맞춰 hash 계산에 필요한 블럭을 만든다

L + 1 + k = 448mod512

L(data length)는 hash를 만들고 싶은 원본 message의 bit길이 이므로 무조건 8의 배수이다

구현할 때 447bit 이런거 머리 빠지게 고민할 필요 없다

그리고 중요한 정보 - little endian을 기준으로 동작하도록 설계되어있다

x86, arm을 보통 사용하는 우리는 짜증나는 endian 전환을 해야 한다

실제 구현 관련 정리 - 블럭 제작 방법 및 hash 계산 방법

hash 계산 및 업데이트

간단하므로 생략, fips 문서에 나온데로 4개의 절차를 수행하면 된다(복잡해 보이는 시그마 같은거 다 문서에 잘 정의 되어있다)

메세지 길이 = len

case 1. len < 56(448bit)

마지막에 1bit를 추가하고 448bit까지 0으로 채움

그리고 마지막 64bit는 총 메세지 길이(lenx8)를 기록한다

hash 계산, 업데이트

case 2. 56 <= len < 64

마지막에 1bit를 추가하고 512bit까지 0으로 채워 block을 만든다

그리고 hash를 계산, 업데이트 한다

그리고 448bit까지 모두 0으로 채우고 마지막 64bit를 총 메세지 길이(lenx8)를 기록한다

그리고 hash 계산, 업데이트

case 3. len >= 64(512bit 이상)

512bit 씩 block으로 잘라 hash 계산, 업데이트 한다

마지막 남는 메세지는 길이에 따라 case1 혹은 case2와 동일하게 진행

last

계산한 32bit 8개의 값을 나열하면 sha256 완성

기타 유용한 참고 소스 코드

kernel 에 포함된 sha....코드.......이해하기 너무 어려움

openssl 의 crypto/sha에 있는 코드들 추천, 다만 최적화 되어있는 부분은 이해하기 힘듬

https://github.com/b-con/crypto-algorithms 매우 추천 깔끔하게 정리 되어있음