[SHA-256] 코드 및 알고리즘 분석 - (4)

이제 소스 코드를 분석하는 마지막 글이다.

SHA-256 함수의 가장 핵심적인 부분이라고 말할 수 있는 SHA-Transform() 함수를 분석하겠다.

(전체 코드는 KSIA에서 다운로드할 수 있습니다.)

 

---

1. 매크로(define) 함수

#define RR(x, n)		ROTR_ULONG(x, n)
#define SS(x, n)		(x >> n)

#define Ch(x, y, z)		((x & y) ^ ((~x) & z))
#define Maj(x, y, z)		((x & y) ^ (x & z) ^ (y & z))
#define Sigma0(x)		(RR(x,  2) ^ RR(x, 13) ^ RR(x, 22))
#define Sigma1(x)		(RR(x,  6) ^ RR(x, 11) ^ RR(x, 25))

#define RHO0(x)		(RR(x,  7) ^ RR(x, 18) ^ SS(x,  3))
#define RHO1(x)		(RR(x, 17) ^ RR(x, 19) ^ SS(x, 10))

코드에 등장하는 여러가지 함수는 다음과 같이 KISA_256.c 코드의 윗부분에 정의되어 있다.

 

 

2. SHA256_Transform()

void SHA256_Transform(ULONG_PTR Message, ULONG_PTR ChainVar)
{
	ULONG a, b, c, d, e, f, g, h, T1, X[64];
	ULONG j;

#define FF(a, b, c, d, e, f, g, h, j) {				\
	T1 = h + Sigma1(e) + Ch(e, f, g) + SHA256_K[j] + X[j];		\
	d += T1;							\
	h = T1 + Sigma0(a) + Maj(a, b, c);				\
}

#if defined(BIG_ENDIAN)
	#define GetData(x)	x
#else
	#define GetData(x)	ENDIAN_REVERSE_ULONG(x)
#endif

	for (j = 0; j < 16; j++)
		X[j] = GetData(Message[j]);

	for (j = 16; j < 64; j++)
		X[j] = RHO1(X[j - 2]) + X[j - 7] + RHO0(X[j - 15]) + X[j - 16];

	a = ChainVar[0];
	b = ChainVar[1];
	c = ChainVar[2];
	d = ChainVar[3];
	e = ChainVar[4];
	f = ChainVar[5];
	g = ChainVar[6];
	h = ChainVar[7];

	for (j = 0; j < 64; j += 8)
	{
		FF(a, b, c, d, e, f, g, h, j + 0);
		FF(h, a, b, c, d, e, f, g, j + 1);
		FF(g, h, a, b, c, d, e, f, j + 2);
		FF(f, g, h, a, b, c, d, e, j + 3);
		FF(e, f, g, h, a, b, c, d, j + 4);
		FF(d, e, f, g, h, a, b, c, j + 5);
		FF(c, d, e, f, g, h, a, b, j + 6);
		FF(b, c, d, e, f, g, h, a, j + 7);
	}

	ChainVar[0] += a;
	ChainVar[1] += b;
	ChainVar[2] += c;
	ChainVar[3] += d;
	ChainVar[4] += e;
	ChainVar[5] += f;
	ChainVar[6] += g;
	ChainVar[7] += h;
}

해시값을 만드는 핵심적인 부분으로,

간단히 말하면 메시지를 여러 수식을 통해 섞고 섞어서 해시값을 생성하는 것이다.

 

👇해시값을 계산하는 알고리즘은 아래 글에서 자세히 설명하였으니 참고 바란다!

[SHA-256] 코드 및 알고리즘 분석 - (5)

 

c언어 코드로 만들어진 해시 계산 알고리즘을 살펴보면 기존의 알고리즘과 비교할 때 다른 곳은 다 똑같은데 다른 부분이 하나 있다.

바로, for문 !!

	for (j = 0; j < 64; j += 8)
	{
		FF(a, b, c, d, e, f, g, h, j + 0);
		FF(h, a, b, c, d, e, f, g, j + 1);
		FF(g, h, a, b, c, d, e, f, j + 2);
		FF(f, g, h, a, b, c, d, e, j + 3);
		FF(e, f, g, h, a, b, c, d, j + 4);
		FF(d, e, f, g, h, a, b, c, j + 5);
		FF(c, d, e, f, g, h, a, b, j + 6);
		FF(b, c, d, e, f, g, h, a, j + 7);
	}

FF() 함수 알고리즘

for문 안에 8줄의 FF()함수가 있다. FF() 함수 하나의 알고리즘은 위의 그림과 같다.

 

for문을 분석해보자

(※ 이때 j는 메시지 배열의 번호를 뜻하는 것이므로 이를 제외하고 생각하기로 하자)

 

• for문 안에서 직접 j에0부터 7까지 더하고, 반복문이 실행될 때마다 j에 8을 더하는 형식을 가지고 있다.
• for문 안에서 8개의 FF() 함수는 rotate shift right 형태로 변수가 옮겨지고 있다.

 

1. FF(a, b, c, d, e, f, g, h, j)를 실행한다.

실행된 후 값이 바뀐 값은 d와 h이다.

d = d + T1, h = T1 + T2 

( Sigma0(a) + Maj(a, b, c)를 T2라 가정 )

 

2. FF(h, a, b, c, d, e, f, g)를 실행한다.

첫번째 FF()함수 실행으로 d와 h의 값이 변경되었으므로

두번째 FF()함수 실행문은 FF((T1+T2), a, b, c, (d+T1), e, f, g) 와 같다.

 

---

- 출처 -

https://seed.kisa.or.kr/kisa/Board/21/detailView.do