안녕하세요. 오늘은 SHA-256 알고리즘에 대해 간단하게 설명하려고 합니다~
이 포스팅에서는 SHA-256 의 수학적인 원리나 구현 최적화 기법에 대해서는 다루지 않습니다.
설명을 위해 최소한으로 작성한 C++ 코드를 통해 SHA-256 의 내부 로직이 어떻게 구성되어 있는지 가볍게 알아보도록 하겠습니다.
SHA-256 이란?
해시 함수중에 하나로서, 해시의 결과가 256bit 입니다. SHA 해시 함수 모음에 속하고 대중적으로 널리쓰이는 해시 함수중에 하나입니다. 특히 최근에는 비트코인을 비롯한 많은 블록체인 시스템에서 SHA-256 을 주로 활용합니다.
SHA-256 알고리즘은 해시 대상 메시지를 전처리하는 단계과 전처리된 메시지를 바탕으로 해시를 계산하는 단계로 나뉩니다. 각 단계에 대해서 알아보도록 하겠습니다.
메시지 전처리
SHA-256 를 적용해야할 데이터를 메시지라고 합니다. 이때 메시지 bit 의 길이가 512의 배수가 되도록 padding 을 추가하는 것이 전처리 단계에서 수행하는 작업입니다.
구체적인 규칙은 아래와 같습니다.
- 원본 메시지의 바로 뒤에 비트 ‘1’ 을 하나 추가한다.
- 메시지의 길이가 512의 배수가 되도록 메시지에 0을 추가한다.
- 메시지의 마지막 64bit에는 원본 메시지의 bit 길이를 적는다.
(출처 : https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf)
이러한 메시지 전처리 단계를 C++ 로 구현하면 아래와 같습니다.
// Add padding to message.
void PreProcess(std::vector<uint8_t>& message)
{
auto L = static_cast<uint64_t>(message.size());
// Append single '1' bit and seven '0' bits.
message.push_back(0b10000000);
// Append (K * 8) '0' bits, where L + 1 + K + 8 is a multiple of 64.
auto K = 64 - (((L % 64) + 9) % 64);
if (K == 64) K = 0;
for (int i = 0; i < K; ++i)
{
message.push_back(0);
}
// Append the bit length of original message.
assert(L <= UINT64_MAX / 8);
uint64_t bitLengthInBigEndian = ChangeEndian(L * 8);
auto ptr = reinterpret_cast<uint8_t*>(&bitLengthInBigEndian);
message.insert(std::end(message), ptr, ptr + 8);
assert(message.size() % 64 == 0);
}
전처리된 메시지 해싱
메시지 전처리가 끝났다면 메시지의 bit 길이는 512의 배수 형태가 되어있을 것입니다.
이러한 전처리된 메시지를 512bit 단위로 쪼개서 여러 개의 chunk 를 만들게 됩니다.
그리고 이러한 chunk 들을 차례대로 순회하면서 특정 연산을 수행하여 최종적인 hash 값을 계산해내게 됩니다.
여기서 초기값 상수 (H0) 는 가장 작은 소수 8개 (2, 3, 5, 7, 11, 13, 17, 19) 에 대해 루트를 씌운 후 소수점 아래자리 32bit 를 추출하면 구할 수 있습니다.
초기값 상수 를 구하는 것을 코드로 작성하면 아래와 같습니다.
std::array<uint32_t, 8> Make_H0()
{
const double kPrimeList[] = { 2, 3, 5, 7, 11, 13, 17, 19 };
static_assert(sizeof(kPrimeList) / sizeof(*kPrimeList) == 8, "");
std::array<uint32_t, 8> H;
for (int i = 0; i < 8; ++i)
{
auto v = std::sqrt(kPrimeList[i]);
v -= static_cast<uint32_t>(v);
v *= std::pow(16, 8);
H[i] = static_cast<uint32_t>(v);
}
return H;
}
그러면 이제 위에서 언급했던 특정 연산 이 무엇인가에 대해 설명해보겠습니다.
하나의 chunk 에 대한 해싱
아래는 위에서 언급한 특정 연산 에 대한 그림입니다.
(출처 : https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml)
저 그림의 각 요소에 대해서 이제부터 하나씩 살펴보도록 하겠습니다.
상수 K
일단 상수 K부터 살펴봅시다.
K는 미리 정해진 상수로서, 가장 작은 소수 64개에 대해 세제곱근을 취한 뒤, 소수점 아래 32bit 를 추출하면 얻을 수 있습니다.
K 를 구하는 코드를 작성하면 아래와 같습니다.
std::array<uint32_t, 64> Make_K()
{
double kPrimeList[] = {
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311
};
static_assert(sizeof(kPrimeList) / sizeof(*kPrimeList) == 64, "");
std::array<uint32_t, 64> K;
for (int i = 0; i < 64; ++i)
{
auto v = std::cbrt(kPrimeList[i]);
v -= static_cast<uint32_t>(v);
v *= std::pow(16, 8);
K[i] = static_cast<uint32_t>(v);
}
return K;
}
W 와 MEXP
이제 W에 대해 살펴봅시다. W는 메시지 청크 (512bit) 를 바탕으로 만들어지는 값입니다.
- 첫 16개 (총 512bit) 는 메시지 청크 (512bit) 를 그대로 가져옵니다.
- 나머지 48개는
MEXP (Message Expansion Function)을 바탕으로 계산합니다.
(출처 : https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml)
W 를 구하는 코드는 아래와 같습니다.
// σ0 (Small Sigma 0)
uint32_t SSigma_0(uint32_t x)
{
return RotateRight(x, 7) ^ RotateRight(x, 18) ^ (x >> 3);
}
// σ1 (Small Sigma 1)
uint32_t SSigma_1(uint32_t x)
{
return RotateRight(x, 17) ^ RotateRight(x, 19) ^ (x >> 10);
}
std::array<uint32_t, 64> Make_W(const uint8_t (&M)[64])
{
std::array<uint32_t, 64> W;
for (int i = 0; i < 16; ++i)
{
W[i] = ChangeEndian(reinterpret_cast<uint32_t const&>(M[i * 4]));
}
for (int i = 16; i < 64; ++i)
{
// MEXP (Message Expansion Function)
W[i] = SSigma_1(W[i - 2]) + W[i - 7] + SSigma_0(W[i - 15]) + W[i - 16];
}
return W;
}
Round Function
이제 마지막으로 해싱 알고리즘의 핵심인 Round Function 에 대해 알아보겠습니다.
(출처 : https://www.cs.rit.edu/~ark/lectures/onewayhash/onewayhash.shtml)
위 그림이 Round Function 의 로직을 설명합니다. 바로 코드를 보여드리겠습니다.
// Σ0 (Big Sigma 0)
uint32_t BSigma_0(uint32_t x)
{
return RotateRight(x, 2) ^ RotateRight(x, 13) ^ RotateRight(x, 22);
}
// Σ1 (Big Sigma 1)
uint32_t BSigma_1(uint32_t x)
{
return RotateRight(x, 6) ^ RotateRight(x, 11) ^ RotateRight(x, 25);
}
// Let X, Y, Z to a bit of x, y, z each.
// If X == 1, take Y. Otherwise take Z.
uint32_t Choose(uint32_t x, uint32_t y, uint32_t z)
{
return (x & y) ^ (~x & z);
}
// Let X, Y, Z to a bit of x, y, z each.
// Take a bit of majority among X, Y, and Z.
uint32_t Majority(uint32_t x, uint32_t y, uint32_t z)
{
return (x & y) ^ (x & z) ^ (y & z);
}
std::array<uint32_t, 8> Round(std::array<uint32_t, 8> const& H, uint32_t K, uint32_t W)
{
std::array<uint32_t, 8> nH; // next H
auto maj = Majority(H[0], H[1], H[2]);
auto ch = Choose(H[4], H[5], H[6]);
auto s = K + BSigma_1(H[4]) + ch + H[7] + W;
nH[0] = BSigma_0(H[0]) + maj + s;
nH[1] = H[0];
nH[2] = H[1];
nH[3] = H[2];
nH[4] = H[3] + s;
nH[5] = H[4];
nH[6] = H[5];
nH[7] = H[6];
return nH;
}
SHA-256 코드
지금까지 살펴본 각 요소들을 (K, W, Round Function) 을 모두 활용하여 SHA-256 를 결과적으로 수행하는 코드를 보여드리겠습니다.
지금까지 제가 청크(chunk) 라고 부르던 것이 아래 코드에서는 block 이라고 네이밍되어 있으니 참고하시기 바랍니다.
std::array<uint32_t, 8> Process(std::vector<uint8_t> const& message)
{
assert(message.size() % 64 == 0);
const auto K = Make_K();
const auto blockCount = message.size() / 64;
auto digest = Make_H0();
for (int i = 0; i < blockCount; ++i)
{
auto W = Make_W(reinterpret_cast<const uint8_t(&)[64]>(message[i * 64]));
auto H = digest;
for (int r = 0; r < 64; ++r)
{
H = Round(H, K[r], W[r]);
}
for (int i = 0; i < 8; ++i)
{
digest[i] += H[i];
}
}
return digest;
}
std::string SHA256(std::vector<uint8_t> message)
{
PreProcess(message);
auto digest = Process(message);
return Hexify(digest);
}
마무리
오늘은 SHA256 알고리즘에 대해서 간단하게 살펴보고 C++ 을 이용해 직접 구현해보았습니다. 전체 소스코드는 여기에서 보실 수 있습니다.
다음에 또 만나요!