SHA-256 구현

안녕하세요. 오늘은 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 코드

지금까지 살펴본 각 요소들 (H, 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++ 을 이용해 직접 구현해보았습니다. 전체 소스코드는 여기에서 보실 수 있습니다.
다음에 또 만나요!

참고 자료

이 포스팅은 삼성 소프트웨어 멤버십 기술 블로그에 동시에 포스팅됩니다.

이 블로그 검색

Taeguk's Blog