암호화 알고리즘 내부 구조 (Cryptographic Algorithm Internals)

AES, SHA-256, RSA, ECDSA 등 리눅스 커널에서 사용되는 핵심 암호화 알고리즘의 내부 동작을 구현 수준으로 심층 분석합니다. 각 알고리즘의 수학적 기반, 라운드 변환, 키 스케줄, 보안 속성을 상세히 다룹니다.

대칭 암호 (Symmetric Ciphers)

대칭 암호(Symmetric Cipher)는 암호화와 복호화에 동일한 키를 사용하는 암호 체계입니다. 블록 암호(Block Cipher)는 고정 크기 블록 단위로 데이터를 처리하며, 스트림 암호(Stream Cipher)는 키스트림(Keystream)을 생성하여 평문과 XOR합니다. 리눅스 커널에서는 AES(블록 암호)와 ChaCha20(스트림 암호)이 가장 널리 사용됩니다.

AES (Advanced Encryption Standard) 내부 구조

AES(Advanced Encryption Standard)는 2001년 NIST가 FIPS 197로 표준화한 대칭 블록 암호입니다. 벨기에 암호학자 Joan Daemen과 Vincent Rijmen이 설계한 Rijndael(레인달) 알고리즘을 기반으로 하며, 128비트 블록 크기에 128/192/256비트 키를 지원합니다. AES-128은 10라운드, AES-192는 12라운드, AES-256은 14라운드를 수행합니다.

각 라운드는 4가지 변환으로 구성됩니다: SubBytes(바이트 치환), ShiftRows(행 시프트), MixColumns(열 혼합), AddRoundKey(라운드 키 XOR). 마지막 라운드에서는 MixColumns를 생략합니다. 이 4가지 변환의 조합이 혼돈(Confusion)과 확산(Diffusion)을 제공하여 암호학적 강도를 보장합니다.

상태 행렬(State Matrix)과 128비트 블록

AES는 128비트(16바이트) 입력을 4×4 바이트 행렬(상태 행렬, State Matrix)로 배치하여 처리합니다. 바이트는 열 우선(Column-Major) 순서로 배치됩니다. 입력 바이트 b₀, b₁, ..., b₁₅는 다음과 같이 매핑됩니다.

상태 행렬의 각 바이트 S[r][c]는 유한체(Finite Field) GF(2⁸) 위의 원소로 취급됩니다. GF(2⁸)는 기약 다항식(Irreducible Polynomial) x⁸ + x⁴ + x³ + x + 1 (16진수 0x11B)을 사용합니다. 이 유한체에서의 덧셈은 XOR, 곱셈은 다항식 곱셈 후 기약 다항식으로 나눈 나머지입니다.

SubBytes — S-Box 치환

SubBytes 변환은 상태 행렬의 각 바이트를 S-Box(Substitution Box)를 통해 독립적으로 치환합니다. S-Box는 비선형(Non-linear) 변환으로, AES의 혼돈(Confusion) 속성을 제공합니다. 수학적으로 S-Box는 두 단계로 구성됩니다.

1. GF(2⁸) 역원(Multiplicative Inverse) — 입력 바이트의 유한체 역원을 구합니다. 0의 역원은 0으로 정의합니다.
2. 아핀 변환(Affine Transformation) — 역원 결과에 GF(2) 위의 아핀 변환을 적용합니다.

아핀 변환은 다음과 같습니다: b'_i = b_i ⊕ b_{(i+4) mod 8} ⊕ b_{(i+5) mod 8} ⊕ b_{(i+6) mod 8} ⊕ b_{(i+7) mod 8} ⊕ c_i (여기서 c = 0x63). 실제 구현에서는 256바이트 룩업 테이블(Lookup Table)로 미리 계산하여 사용합니다.

S-Box의 비선형성은 선형 공격(Linear Cryptanalysis)과 차분 공격(Differential Cryptanalysis)에 대한 저항성의 핵심입니다. AES S-Box는 가능한 최대 비선형성(Maximum Non-linearity)에 가까운 값을 가집니다.

ShiftRows — 행 순환 시프트

ShiftRows는 상태 행렬의 각 행을 왼쪽으로 순환 시프트합니다. 행 0은 시프트하지 않고, 행 1은 1바이트, 행 2는 2바이트, 행 3은 3바이트 왼쪽으로 시프트합니다. 이 변환은 열 간 바이트 확산(Diffusion)을 제공하여, SubBytes에서 생긴 변화가 여러 열로 퍼지게 합니다.

MixColumns — 열 혼합 (GF(2⁸) 곱셈)

MixColumns는 상태 행렬의 각 열을 GF(2⁸) 위의 고정 다항식과 곱하여 변환합니다. 이 변환은 한 열 내의 4바이트를 서로 혼합하여 확산(Diffusion) 속성을 제공합니다. 곱셈에 사용되는 고정 MDS(Maximum Distance Separable) 행렬은 다음과 같습니다.

┌           ┐   ┌           ┐   ┌           ┐
│ s'₀  │   │ 02 03 01 01 │   │ s₀  │
│ s'₁  │ = │ 01 02 03 01 │ × │ s₁  │   (GF(2⁸) 위의 행렬 곱셈)
│ s'₂  │   │ 01 01 02 03 │   │ s₂  │
│ s'₃  │   │ 03 01 01 02 │   │ s₃  │
└           ┘   └           ┘   └           ┘

GF(2⁸) 위의 곱셈에서 {02}를 곱하는 연산을 xtime이라 합니다. xtime(a)는 a를 1비트 왼쪽 시프트한 후, 최상위 비트가 1이었다면 기약 다항식 0x1B를 XOR합니다. {03}을 곱하는 것은 xtime(a) ⊕ a와 동일합니다.

/* GF(2^8)에서 {02} 곱셈: xtime */
static inline uint8_t xtime(uint8_t a)
{
    return (a << 1) ^ ((a & 0x80) ? 0x1B : 0x00);
}

/* MixColumns: 한 열(4바이트) 변환 */
void mix_column(uint8_t *col)
{
    uint8_t a = col[0], b = col[1], c = col[2], d = col[3];
    uint8_t t = a ^ b ^ c ^ d;  /* 공통 XOR 항 */

    col[0] = a ^ xtime(a ^ b) ^ t;  /* 2a + 3b + c + d */
    col[1] = b ^ xtime(b ^ c) ^ t;  /* a + 2b + 3c + d */
    col[2] = c ^ xtime(c ^ d) ^ t;  /* a + b + 2c + 3d */
    col[3] = d ^ xtime(d ^ a) ^ t;  /* 3a + b + c + 2d */
}

AddRoundKey — 라운드 키 XOR

AddRoundKey는 상태 행렬과 라운드 키(Round Key)를 바이트 단위로 XOR합니다. 라운드 키는 키 스케줄(Key Schedule)을 통해 원래 키에서 확장된 서브키입니다. 이 변환은 유일하게 키를 사용하는 단계로, 키 없이는 역변환이 불가능합니다.

/* AddRoundKey: 상태와 라운드 키 XOR */
void add_round_key(uint8_t state[4][4], const uint32_t *round_key)
{
    for (int c = 0; c < 4; c++) {
        uint32_t rk = round_key[c];
        state[0][c] ^= (rk >> 24) & 0xFF;
        state[1][c] ^= (rk >> 16) & 0xFF;
        state[2][c] ^= (rk >>  8) & 0xFF;
        state[3][c] ^= (rk      ) & 0xFF;
    }
}

키 스케줄(Key Schedule) — 128/192/256비트

AES 키 스케줄은 원래 암호화 키에서 각 라운드에 사용할 라운드 키를 생성합니다. AES-128은 4워드(128비트) 키에서 44워드(11개 라운드 키)를, AES-256은 8워드(256비트) 키에서 60워드(15개 라운드 키)를 생성합니다.

키 확장의 핵심 연산은 RotWord(1바이트 순환 시프트), SubWord(각 바이트를 S-Box로 치환), Rcon(라운드 상수 XOR)입니다.

/* AES-128 키 확장 (Nk=4, Nr=10, 총 44워드) */
void key_expansion_128(const uint8_t key[16], uint32_t w[44])
{
    /* 처음 4워드: 원래 키 복사 */
    for (int i = 0; i < 4; i++)
        w[i] = GET_U32_BE(key, 4 * i);

    for (int i = 4; i < 44; i++) {
        uint32_t temp = w[i - 1];

        if (i % 4 == 0) {
            /* RotWord: [a,b,c,d] → [b,c,d,a] */
            temp = (temp << 8) | (temp >> 24);
            /* SubWord: 각 바이트를 S-Box로 치환 */
            temp = sub_word(temp);
            /* Rcon XOR: 라운드 상수 */
            temp ^= rcon[i / 4 - 1];  /* rcon = {01,02,04,08,10,20,40,80,1B,36} */
        }

        w[i] = w[i - 4] ^ temp;
    }
}

/* AES-256 키 확장 (Nk=8): i%8==4일 때 추가 SubWord */
/* AES-192 키 확장 (Nk=6): 구조는 동일하되 i%6==0일 때 변환 */

AES-256에서는 추가로 i % 8 == 4인 경우에도 SubWord를 적용합니다. 이는 256비트 키의 확산을 강화하기 위한 것입니다. Rcon(라운드 상수)은 GF(2⁸)에서 {02}의 거듭제곱입니다: Rcon = {01, 02, 04, 08, 10, 20, 40, 80, 1B, 36}.

AES 전체 라운드 흐름

AES 암호화의 전체 흐름은 다음과 같습니다: 초기 AddRoundKey → (Nr-1)회 메인 라운드 → 마지막 라운드(MixColumns 생략). AES-128의 경우 총 10라운드를 수행합니다.

복호화(Decryption) — 역변환 순서

AES 복호화는 각 변환의 역을 역순으로 적용합니다: InvShiftRows(오른쪽 시프트), InvSubBytes(역 S-Box), InvMixColumns(역 MDS 행렬), AddRoundKey(XOR은 자기 자신의 역).

역 MDS 행렬의 계수는 {0E, 0B, 0D, 09}로, 정방향보다 계산 비용이 높습니다. 동치 역 암호(Equivalent Inverse Cipher) 최적화를 사용하면, 라운드 키에 InvMixColumns를 미리 적용하여 암호화와 동일한 구조를 사용할 수 있습니다. 이 최적화는 AES-NI 하드웨어 명령어(AESIMC)로도 지원됩니다.

/* AES 복호화: 역변환 순서 */
void aes_decrypt(const uint8_t *ct, uint8_t *pt, const uint32_t *rk, int nr)
{
    uint8_t state[4][4];
    bytes_to_state(ct, state);

    add_round_key(state, rk + nr * 4);  /* 마지막 라운드 키부터 역순 */

    for (int r = nr - 1; r >= 1; r--) {
        inv_shift_rows(state);   /* InvShiftRows: 오른쪽 순환 시프트 */
        inv_sub_bytes(state);    /* InvSubBytes: 역 S-Box 치환 */
        add_round_key(state, rk + r * 4);
        inv_mix_columns(state);  /* InvMixColumns: 역 MDS 행렬 */
    }
    /* 마지막 라운드 (InvMixColumns 없음) */
    inv_shift_rows(state);
    inv_sub_bytes(state);
    add_round_key(state, rk);

    state_to_bytes(state, pt);
}

/* InvMixColumns: 역 MDS 행렬 곱셈 */
/* 계수: {0E, 0B, 0D, 09} — xtime 반복 조합으로 계산 */
/* 0E = xtime(xtime(xtime(a))) ^ xtime(xtime(a)) ^ xtime(a) */

보안 속성과 알려진 공격

AES는 2001년 표준화 이후 실질적으로 깨진 적이 없습니다. 알려진 최선의 공격은 다음과 같습니다.

블록 암호 운용 모드 (Block Cipher Modes of Operation)

블록 암호는 고정 크기(AES: 128비트) 블록만 처리할 수 있으므로, 임의 길이 데이터를 암호화하려면 운용 모드(Mode of Operation)가 필요합니다. 운용 모드는 블록 간의 관계를 정의하며, 각 모드는 병렬성, 에러 전파, 패딩 필요성 등에서 서로 다른 특성을 가집니다.

ECB (Electronic Codebook) — 사용 금지 모드

ECB 모드는 각 블록을 독립적으로 암호화합니다: C_i = E_K(P_i). 동일한 평문 블록은 동일한 암호문을 생성하므로, 패턴이 보존됩니다. ECB로 이미지를 암호화하면 원본의 윤곽이 그대로 드러나는 것이 대표적인 예입니다. ECB는 단일 블록 암호화(예: 키 래핑) 이외의 용도로 사용해서는 안 됩니다.

CBC (Cipher Block Chaining) 모드

CBC 모드는 이전 암호문 블록을 다음 평문 블록과 XOR한 후 암호화합니다. 첫 블록에는 초기화 벡터(IV, Initialization Vector)를 사용합니다.

• 암호화: C_i = E_K(P_i ⊕ C_i-1), C₀ = IV
• 복호화: P_i = D_K(C_i) ⊕ C_i-1

암호화는 블록 간 의존성으로 직렬화되지만, 복호화는 병렬 수행이 가능합니다. 블록 크기의 배수가 아닌 데이터는 패딩(PKCS#7)이 필요합니다.

CTR (Counter) 모드

CTR 모드는 블록 암호를 스트림 암호처럼 사용합니다. Nonce와 카운터를 결합한 값을 암호화하여 키스트림을 생성하고, 이를 평문과 XOR합니다.

• 암호화/복호화: C_i = P_i ⊕ E_K(Nonce ∥ Counter_i)

모든 블록이 독립적이므로 완전한 병렬 처리가 가능하며, 패딩이 불필요합니다. 그러나 동일한 키-Nonce 조합의 재사용은 치명적입니다 — 두 암호문을 XOR하면 두 평문의 XOR이 노출됩니다.

XTS (XEX-based Tweaked CodeBook) 모드

XTS 모드는 디스크 암호화에 특화된 모드로, IEEE P1619 표준입니다. 두 개의 키(K₁: 데이터 암호화, K₂: 트윅 암호화)를 사용하며, 섹터 번호를 트윅(Tweak)으로 활용합니다.

• T = E_K2(섹터번호) × α^j (GF(2¹²⁸)에서 α = {02})
• C_j = E_K1(P_j ⊕ T) ⊕ T

트윅은 동일한 평문이 다른 위치에서 다른 암호문을 생성하게 하며, 디스크의 각 섹터가 독립적으로 접근 가능합니다. 리눅스 dm-crypt와 fscrypt에서 xts(aes)로 사용됩니다.

XTS의 핵심은 트윅 값이 블록 위치에 따라 변하므로, 동일한 평문이라도 디스크의 다른 위치에서는 완전히 다른 암호문을 생성한다는 점입니다. α 곱셈은 GF(2¹²⁸)에서의 {02} 곱셈으로, 1비트 시프트와 조건부 XOR(0x87)로 효율적으로 계산됩니다. 마지막 불완전 블록은 CTS(Ciphertext Stealing)로 처리합니다.

/* XTS 트윅 업데이트: T = T × α in GF(2^128) */
static void xts_tweak_next(uint8_t *T)
{
    int carry = 0;
    for (int i = 0; i < 16; i++) {
        int next_carry = (T[i] >> 7) & 1;
        T[i] = (T[i] << 1) | carry;
        carry = next_carry;
    }
    if (carry)
        T[0] ^= 0x87;  /* GF(2^128) 기약 다항식: x^128 + x^7 + x^2 + x + 1 */
}

운용 모드 비교

ChaCha20 스트림 암호 내부 구조

ChaCha20은 Daniel Bernstein이 설계한 스트림 암호(Stream Cipher)로, ARX(Add-Rotate-XOR) 연산만 사용합니다. S-Box가 없어 타이밍 공격에 본질적으로 안전하며, AES-NI가 없는 플랫폼에서도 AES보다 빠릅니다. WireGuard, TLS 1.3에서 ChaCha20-Poly1305 AEAD로 널리 사용됩니다.

초기 상태 행렬 (4×4 워드)

ChaCha20의 상태는 16개의 32비트 워드로 구성된 4×4 행렬입니다.

상태 행렬 (512비트 = 16 × 32비트):
┌──────────┬──────────┬──────────┬──────────┐
│ "expa"   │ "nd 3"   │ "2-by"   │ "te k"   │  ← 상수 (0x61707865, 0x3320646E, ...)
├──────────┼──────────┼──────────┼──────────┤
│ Key[0]   │ Key[1]   │ Key[2]   │ Key[3]   │  ← 키 전반부 (128비트)
├──────────┼──────────┼──────────┼──────────┤
│ Key[4]   │ Key[5]   │ Key[6]   │ Key[7]   │  ← 키 후반부 (128비트)
├──────────┼──────────┼──────────┼──────────┤
│ Counter  │ Nonce[0] │ Nonce[1] │ Nonce[2] │  ← 카운터(32비트) + Nonce(96비트)
└──────────┴──────────┴──────────┴──────────┘

"expand 32-byte k" ASCII 상수(리틀 엔디안)는 아무 의미 없는(Nothing-up-my-sleeve) 숫자로, 설계자가 의도적으로 약점을 심지 않았음을 보여줍니다.

쿼터 라운드(Quarter Round) 함수

ChaCha20의 핵심은 쿼터 라운드(QR) 함수입니다. 4개의 32비트 워드 (a, b, c, d)에 대해 ARX 연산을 수행합니다.

/* ChaCha20 쿼터 라운드 */
#define QR(a, b, c, d) do { \
    a += b; d ^= a; d = ROTL32(d, 16); \
    c += d; b ^= c; b = ROTL32(b, 12); \
    a += b; d ^= a; d = ROTL32(d,  8); \
    c += d; b ^= c; b = ROTL32(b,  7); \
} while (0)

키스트림 생성과 암호화

/* ChaCha20 블록 함수: 512비트 키스트림 블록 생성 */
void chacha20_block(const uint32_t input[16], uint32_t output[16])
{
    uint32_t x[16];
    memcpy(x, input, sizeof(x));

    /* 20라운드 = 10 더블 라운드 */
    for (int i = 0; i < 10; i++) {
        /* 컬럼 라운드 */
        QR(x[0], x[4], x[ 8], x[12]);
        QR(x[1], x[5], x[ 9], x[13]);
        QR(x[2], x[6], x[10], x[14]);
        QR(x[3], x[7], x[11], x[15]);
        /* 대각선 라운드 */
        QR(x[0], x[5], x[10], x[15]);
        QR(x[1], x[6], x[11], x[12]);
        QR(x[2], x[7], x[ 8], x[13]);
        QR(x[3], x[4], x[ 9], x[14]);
    }

    /* 최종: 초기 상태와 워드별 덧셈 */
    for (int i = 0; i < 16; i++)
        output[i] = x[i] + input[i];  /* 모듈러 2^32 덧셈 */
}

/* 암호화: 키스트림 ⊕ 평문 */
/* 카운터를 1씩 증가시키며 다음 64바이트 블록 생성 */

ChaCha20 vs AES 비교

해시 함수 (Hash Functions)

암호학적 해시 함수(Cryptographic Hash Function)는 임의 길이 입력에서 고정 길이 출력(다이제스트, Digest)을 생성하는 일방향 함수입니다. 역상 저항성(Preimage Resistance), 제2 역상 저항성(Second Preimage Resistance), 충돌 저항성(Collision Resistance)의 세 가지 보안 속성을 만족해야 합니다.

SHA-256 내부 구조

SHA-256은 SHA-2 계열에 속하며, NIST FIPS 180-4에 표준화되어 있습니다. 32비트 워드 기반으로 동작하며, 256비트(32바이트) 다이제스트를 생성합니다. 리눅스 커널에서 IMA, 모듈 서명, dm-verity, fscrypt 등 광범위하게 사용됩니다.

Merkle-Damgård 구성

SHA-256은 Merkle-Damgård 구성을 사용합니다. 메시지를 512비트 블록으로 분할하고, 각 블록을 압축 함수(Compression Function)에 순차적으로 투입합니다. 이전 블록의 출력(256비트 체이닝 값)이 다음 블록의 입력이 됩니다.

전처리 — 패딩과 메시지 스케줄

패딩: 메시지 끝에 1비트(0x80)를 추가하고, 메시지 길이가 512의 배수 - 64비트가 될 때까지 0을 채운 후, 원래 메시지 길이를 64비트 빅 엔디안으로 추가합니다.

메시지 스케줄(Message Schedule): 각 512비트 블록에서 64개의 32비트 워드 W[0..63]을 생성합니다.

/* 메시지 스케줄 확장 */
/* W[0..15]: 입력 블록에서 직접 추출 (빅 엔디안) */
for (int t = 16; t < 64; t++) {
    uint32_t s0 = ROTR(W[t-15], 7) ^ ROTR(W[t-15], 18) ^ (W[t-15] >> 3);   /* σ₀ */
    uint32_t s1 = ROTR(W[t-2], 17) ^ ROTR(W[t-2], 19)  ^ (W[t-2] >> 10);   /* σ₁ */
    W[t] = W[t-16] + s0 + W[t-7] + s1;
}

압축 함수(Compression Function) — 64라운드

압축 함수는 8개의 32비트 작업 변수 a, b, c, d, e, f, g, h를 이전 해시값(H_i-1)으로 초기화한 후, 64라운드에 걸쳐 업데이트합니다.

/* SHA-256 라운드 함수 핵심 연산 */
#define Ch(e,f,g)   ((e & f) ^ (~e & g))
#define Maj(a,b,c)  ((a & b) ^ (a & c) ^ (b & c))
#define Sigma0(a)   (ROTR(a, 2) ^ ROTR(a, 13) ^ ROTR(a, 22))   /* Σ₀ */
#define Sigma1(e)   (ROTR(e, 6) ^ ROTR(e, 11) ^ ROTR(e, 25))   /* Σ₁ */

/* 한 라운드 (t = 0..63) */
uint32_t T1 = h + Sigma1(e) + Ch(e, f, g) + K[t] + W[t];
uint32_t T2 = Sigma0(a) + Maj(a, b, c);

h = g;
g = f;
f = e;
e = d + T1;    /* d에 T1을 더해서 새로운 e */
d = c;
c = b;
b = a;
a = T1 + T2;   /* T1 + T2가 새로운 a */

/* 64라운드 완료 후: H_i[j] = H_{i-1}[j] + 작업변수[j] */

초기값과 라운드 상수

SHA-256의 초기 해시값 H₀은 처음 8개 소수(2, 3, 5, 7, 11, 13, 17, 19)의 제곱근 소수 부분에서 유도됩니다. 64개의 라운드 상수 K[t]는 처음 64개 소수의 세제곱근 소수 부분입니다.

/* SHA-256 초기 해시값 (처음 8개 소수의 √ 소수 부분) */
uint32_t H[8] = {
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
};

/* SHA-256 라운드 상수 (처음 64개 소수의 ∛ 소수 부분) */
uint32_t K[64] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5,
    0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    /* ... 나머지 56개 ... */
};

충돌 저항성과 길이 확장 공격

SHA-256의 충돌 저항성은 생일 공격(Birthday Attack)에 의해 2¹²⁸으로 바운드됩니다. 현재까지 이론적으로나 실용적으로 SHA-256 충돌은 발견되지 않았습니다.

SHA-512와 SHA-256 차이점

SHA-512는 SHA-256과 동일한 구조를 사용하지만, 64비트 워드 기반으로 동작합니다.

SHA-384는 SHA-512의 절삭(Truncated) 변형으로, 다른 초기값을 사용하고 출력을 384비트로 자릅니다. SHA-512/256은 SHA-512 기반이지만 256비트 출력을 제공하며, SHA-256보다 길이 확장 공격에 강합니다.

HMAC (Hash-based Message Authentication Code) 구성

HMAC은 해시 함수를 기반으로 메시지 인증 코드(MAC)를 생성하는 구성입니다. RFC 2104에 정의되며, 리눅스 커널에서 kTLS, IPsec, DRBG, fscrypt 키 유도 등에 광범위하게 사용됩니다.

ipad/opad 이중 해싱 구조

HMAC의 정의는 다음과 같습니다.

HMAC(K, M) = H((K' ⊕ opad) ∥ H((K' ⊕ ipad) ∥ M))

K' = H(K)       만약 |K| > 블록 크기 (SHA-256: 512비트)
K' = K ∥ 0...0  만약 |K| ≤ 블록 크기 (0으로 패딩)

ipad = 0x36 반복 (블록 크기만큼)
opad = 0x5C 반복 (블록 크기만큼)

HMAC 보안 증명과 PRF 속성

HMAC의 보안은 기반 해시 함수의 압축 함수가 PRF(Pseudorandom Function)일 때 증명됩니다. Bellare(1996)의 증명에 따르면, 압축 함수가 PRF이면 HMAC도 PRF입니다. 이는 해시 함수 전체의 충돌 저항성이 깨져도 HMAC은 안전할 수 있음을 의미합니다 — 실제로 MD5의 충돌 저항성은 깨졌지만 HMAC-MD5는 여전히 안전한 것으로 간주됩니다(새 시스템에서는 권장하지 않습니다).

인증 암호화 (Authenticated Encryption)

인증 암호화(AEAD, Authenticated Encryption with Associated Data)는 기밀성과 무결성/인증을 동시에 제공합니다. 별도의 암호화+MAC 조합보다 안전하고 효율적이며, 현대 프로토콜(TLS 1.3, IPsec, WireGuard)의 표준입니다.

AES-GCM 심층 분석

GCM(Galois/Counter Mode)은 CTR 모드 암호화와 GHASH 인증을 결합한 AEAD 모드입니다. NIST SP 800-38D에 표준화되어 있으며, 하드웨어 가속(AES-NI + PCLMULQDQ)으로 매우 높은 처리량을 제공합니다.

GHASH — GF(2¹²⁸) 곱셈

GHASH는 GF(2¹²⁸) 위의 곱셈 기반 범용 해시 함수입니다. 기약 다항식은 x¹²⁸ + x⁷ + x² + x + 1이며, 해시 키 H = E_K(0¹²⁸)를 사용합니다.

/* GF(2^128) 곱셈: shift-and-XOR */
void gf128_mul(uint8_t *X, const uint8_t *Y)
{
    uint8_t Z[16] = {0};  /* 결과 */
    uint8_t V[16];
    memcpy(V, Y, 16);

    for (int i = 0; i < 128; i++) {
        /* X의 i번째 비트가 1이면 Z ^= V */
        if (X[i / 8] & (0x80 >> (i % 8)))
            xor_block(Z, V);

        /* V를 오른쪽 1비트 시프트 (MSB가 1이면 기약 다항식 XOR) */
        int msb = V[15] & 1;
        for (int j = 15; j > 0; j--)
            V[j] = (V[j] >> 1) | (V[j-1] << 7);
        V[0] >>= 1;
        if (msb)
            V[0] ^= 0xE1;  /* x^128 + x^7 + x^2 + x + 1의 상위 8비트 */
    }
    memcpy(X, Z, 16);
}

/* GHASH: 순차적 multiply-XOR 누적 */
/* GHASH(H, A, C):
 *   X_0 = 0^128
 *   X_i = (X_{i-1} XOR block_i) * H   (GF(2^128)에서)
 *   마지막: len(A)||len(C) 블록으로 마무리 */

태그 계산 전체 흐름

GCM 암호화+태그 생성의 전체 흐름입니다.

하드웨어 가속 매핑

AES-GCM의 두 핵심 연산은 각각 전용 하드웨어 명령어로 가속됩니다.

상세한 하드웨어 가속 아키텍처는 Crypto API의 AES-NI 섹션을 참고하세요.

ChaCha20-Poly1305 심층 분석

ChaCha20-Poly1305는 ChaCha20 스트림 암호와 Poly1305 MAC을 결합한 AEAD 구성입니다. RFC 8439에 표준화되어 있으며, WireGuard와 TLS 1.3에서 AES-GCM의 대안으로 사용됩니다.

Poly1305 MAC — 소수체 연산

Poly1305는 소수 p = 2¹³⁰ - 5 위의 다항식 평가(Polynomial Evaluation) MAC입니다. 메시지를 16바이트 블록으로 나누고, 각 블록을 정수로 해석하여 누적합니다.

/* Poly1305 MAC 핵심 연산 (간략화) */
/* r: 인증 키 (128비트, 클램핑됨), s: 일회용 키 (128비트) */
/* p = 2^130 - 5 */

accumulator = 0
for each 16-byte block m_i:
    n = le_bytes_to_num(m_i) + (1 << (8 * block_len))  /* 상위 비트 1 추가 */
    accumulator = (accumulator + n) * r  mod p

tag = (accumulator + s) mod 2^128  /* 하위 128비트 */

r 클램핑(Clamping): 효율적인 모듈러 리덕션을 위해 r의 특정 비트를 0으로 클리어합니다. 클램핑 마스크: 0x0ffffffc0ffffffc0ffffffc0fffffff. 이는 보안을 해치지 않으면서 곱셈 결과의 크기를 제한합니다.

AEAD 결합 프로토콜 (RFC 8439)

비대칭 암호 내부 구조 (Asymmetric Cryptography)

비대칭 암호(Public-Key Cryptography)는 공개키(Public Key)와 개인키(Private Key)의 쌍을 사용합니다. 키 교환, 디지털 서명, 암호화에 사용되며, 보안은 수학적 난제(소인수 분해, 이산 로그, 타원 곡선 이산 로그)에 기반합니다.

RSA 심층 분석

RSA 수학 — 모듈러 거듭제곱

RSA의 수학적 기반은 오일러 정리(Euler's Theorem)입니다.

• 키 생성: 큰 소수 p, q 선택 → n = p·q, φ(n) = (p-1)(q-1) → e 선택 (보통 65537) → d = e^-1 mod φ(n)
• 암호화: c = m^e mod n
• 복호화: m = c^d mod n
• 서명: s = m^d mod n
• 검증: m = s^e mod n

모듈러 거듭제곱은 제곱-곱셈 알고리즘(Square-and-Multiply)으로 효율적으로 계산합니다.

/* 모듈러 거듭제곱: base^exp mod mod (MSB-first) */
uint64_t mod_exp(uint64_t base, uint64_t exp, uint64_t mod)
{
    uint64_t result = 1;
    base %= mod;

    for (int i = 63; i >= 0; i--) {  /* MSB부터 */
        result = (result * result) % mod;      /* 항상 제곱 */
        if (exp & (1ULL << i))
            result = (result * base) % mod;    /* 비트가 1이면 곱셈 */
    }
    return result;
}
/* 실제 구현은 다중 정밀도(multi-precision) 정수 라이브러리 필요 */

키 생성 — 소수 선택과 CRT 최적화

RSA 키 생성에서 소수 판정은 밀러-라빈(Miller-Rabin) 확률적 소수 판정법을 사용합니다. CRT(Chinese Remainder Theorem) 최적화는 복호화/서명 속도를 약 4배 향상시킵니다.

/* CRT 최적화 복호화 */
/* 사전 계산: dp = d mod (p-1), dq = d mod (q-1), qinv = q^(-1) mod p */
uint64_t rsa_decrypt_crt(uint64_t c, rsa_key *key)
{
    uint64_t m1 = mod_exp(c, key->dp, key->p);  /* c^dp mod p */
    uint64_t m2 = mod_exp(c, key->dq, key->q);  /* c^dq mod q */

    /* CRT 재결합 */
    int64_t h = (key->qinv * ((int64_t)m1 - m2)) % key->p;
    if (h < 0) h += key->p;

    return m2 + key->q * h;  /* m = m2 + q * h */
}
/* n 비트 거듭제곱 대신 n/2 비트 거듭제곱 2회 → ~4배 빠름 */

OAEP 패딩 (Optimal Asymmetric Encryption Padding)

원시 RSA(Textbook RSA)는 결정적(Deterministic)이고 변조 가능(Malleable)하므로 안전하지 않습니다. OAEP(PKCS#1 v2.2)는 무작위 시드를 사용하여 동일한 평문도 매번 다른 암호문을 생성합니다.

RSA 공격 유형과 방어

타원 곡선 암호 (Elliptic Curve Cryptography)

타원 곡선 암호(ECC)는 유한체 위의 타원 곡선에서 이산 로그 문제(ECDLP)의 어려움에 기반합니다. RSA보다 훨씬 작은 키로 동등한 보안을 제공합니다 (256비트 ECC ≈ 3072비트 RSA).

타원 곡선 수학 — 점 덧셈과 스칼라 곱셈

소수체(Prime Field) F_p 위의 단축 바이에르슈트라스(Short Weierstrass) 곡선: y² = x³ + ax + b (mod p)

점 덧셈 (P + Q = R): P = (x₁, y₁), Q = (x₂, y₂)일 때, 기울기 λ = (y₂ - y₁) / (x₂ - x₁) mod p, R = (λ² - x₁ - x₂, λ(x₁ - x_R) - y₁) mod p

점 더블링 (2P): λ = (3x₁² + a) / (2y₁) mod p

스칼라 곱셈 (kP): 더블-앤-애드(Double-and-Add) 알고리즘으로 O(log k)번의 점 연산으로 계산합니다. 이것이 공개키 = 개인키 × G의 계산 방법입니다.

/* 스칼라 곱셈: double-and-add (간략화) */
EC_POINT scalar_mul(const BIGNUM *k, const EC_POINT *P, const EC_GROUP *group)
{
    EC_POINT result = POINT_AT_INFINITY;  /* 항등원 */

    for (int i = BN_num_bits(k) - 1; i >= 0; i--) {
        result = point_double(result, group);  /* 항상 더블링 */
        if (BN_is_bit_set(k, i))
            result = point_add(result, P, group);  /* 비트=1이면 덧셈 */
    }
    return result;
}
/* 주의: 실제 구현은 사이드 채널 방어를 위해 Montgomery ladder 사용 */

점 덧셈의 기하학적 의미는 곡선 위의 두 점을 잇는 직선이 곡선과 만나는 세 번째 교점을 x축 대칭한 것입니다. 유한체에서는 실수 좌표 대신 모듈러 산술을 사용하지만 대수적 공식은 동일합니다. 나눗셈은 모듈러 역원으로 계산하며, 확장 유클리드 알고리즘이나 페르마 소정리(a^p-2 mod p)를 사용합니다.

/* 타원 곡선 점 덧셈 (Fp, 아핀 좌표, 간략화) */
void ec_point_add(const EC_POINT *P, const EC_POINT *Q, EC_POINT *R,
                  const BIGNUM *a, const BIGNUM *p)
{
    BIGNUM lambda, t;

    if (ec_point_is_infinity(P)) { *R = *Q; return; }
    if (ec_point_is_infinity(Q)) { *R = *P; return; }

    if (BN_cmp(P->x, Q->x) == 0) {
        if (BN_cmp(P->y, Q->y) != 0) {
            ec_point_set_infinity(R);  /* P + (-P) = O */
            return;
        }
        /* 점 더블링: λ = (3x² + a) / (2y) mod p */
        BN_mod_sqr(&t, P->x, p);         /* x² */
        BN_mod_mul_word(&t, 3);           /* 3x² */
        BN_mod_add(&t, &t, a, p);        /* 3x² + a */
        BIGNUM dy; BN_mod_add(&dy, P->y, P->y, p);  /* 2y */
        BN_mod_inverse(&dy, &dy, p);     /* (2y)⁻¹ */
        BN_mod_mul(&lambda, &t, &dy, p); /* λ */
    } else {
        /* 점 덧셈: λ = (y₂ - y₁) / (x₂ - x₁) mod p */
        BIGNUM dy, dx;
        BN_mod_sub(&dy, Q->y, P->y, p);
        BN_mod_sub(&dx, Q->x, P->x, p);
        BN_mod_inverse(&dx, &dx, p);
        BN_mod_mul(&lambda, &dy, &dx, p);
    }
    /* x_R = λ² - x₁ - x₂, y_R = λ(x₁ - x_R) - y₁ */
    BN_mod_sqr(&R->x, &lambda, p);
    BN_mod_sub(&R->x, &R->x, P->x, p);
    BN_mod_sub(&R->x, &R->x, Q->x, p);
    BN_mod_sub(&t, P->x, &R->x, p);
    BN_mod_mul(&R->y, &lambda, &t, p);
    BN_mod_sub(&R->y, &R->y, P->y, p);
}

주요 곡선 매개변수

Curve25519는 Daniel Bernstein이 설계했으며, 상수 시간 구현이 용이하도록 Montgomery 래더(Ladder) 스칼라 곱셈을 사용합니다. 스칼라 클램핑으로 소그룹 공격을 구조적으로 방지합니다.

ECDSA 서명 생성/검증

서명 생성: 개인키 d, 메시지 해시 z = H(M)

1. 무작위 k 선택 (1 ≤ k ≤ n-1), R = kG, r = R.x mod n
2. s = k^-1(z + r·d) mod n
3. 서명 = (r, s)

서명 검증: 공개키 Q = dG

1. u₁ = z·s^-1 mod n, u₂ = r·s^-1 mod n
2. P = u₁·G + u₂·Q
3. P.x mod n == r이면 유효

ECDH 키 교환

ECDH(Elliptic Curve Diffie-Hellman)는 타원 곡선 위에서 디피-헬먼 키 교환을 수행합니다.

Diffie-Hellman 키 교환

고전 DH — 이산 로그 기반

고전 Diffie-Hellman은 소수 p와 생성자(Generator) g를 사용합니다. Alice는 a를 선택하여 A = g^a mod p를 보내고, Bob은 b를 선택하여 B = g^b mod p를 보냅니다. 공유 비밀은 S = g^ab mod p = A^b = B^a입니다.

그룹 매개변수와 보안 강도

난수 생성 내부 구조 (Random Number Generation)

암호학적으로 안전한 난수(CSPRNG)는 키 생성, Nonce 생성, 초기화 벡터 생성의 기반입니다. 리눅스 커널의 난수 시스템은 하드웨어 엔트로피 소스에서 수집한 엔트로피를 DRBG로 확장하여 사용합니다.

DRBG (Deterministic Random Bit Generator)

DRBG는 NIST SP 800-90A에 표준화된 결정적 난수 생성기입니다. 시드(Seed)에서 결정적으로 출력을 생성하되, 시드의 엔트로피가 충분하면 출력이 진정한 난수와 구별 불가능합니다.

CTR-DRBG — AES 기반 결정적 난수

CTR-DRBG는 AES-CTR을 기반으로 합니다. 내부 상태는 키(K)와 값(V)의 쌍입니다.

/* CTR-DRBG 생성 (간략화) */
struct ctr_drbg_state {
    uint8_t key[32];    /* AES-256 키 */
    uint8_t V[16];      /* 128비트 카운터 */
    int reseed_counter;
};

void ctr_drbg_generate(struct ctr_drbg_state *s, uint8_t *out, size_t len)
{
    uint8_t temp[len];
    size_t offset = 0;

    while (offset < len) {
        increment_counter(s->V);  /* V++ (빅 엔디안) */
        aes_encrypt(s->key, s->V, temp + offset);  /* E_K(V) */
        offset += 16;
    }
    memcpy(out, temp, len);

    /* 상태 업데이트: 출력을 사용하여 K, V 갱신 */
    ctr_drbg_update(s, NULL);
    s->reseed_counter++;
}

/* Reseed: 새 엔트로피로 K, V 업데이트 */
/* 최대 2^48 요청 후 반드시 reseed 필요 */

HMAC-DRBG — HMAC 기반 결정적 난수

HMAC-DRBG는 HMAC을 기반으로 하며, 블록 암호 없이 해시 함수만으로 구현 가능합니다. 리눅스 커널에서 ECDSA의 결정적 k 생성(RFC 6979)에 사용됩니다.

/* HMAC-DRBG 상태 업데이트 */
void hmac_drbg_update(uint8_t *K, uint8_t *V, const uint8_t *data, size_t len)
{
    /* K = HMAC(K, V || 0x00 || data) */
    K = hmac(K, V || 0x00 || data);
    V = hmac(K, V);

    if (data != NULL) {
        K = hmac(K, V || 0x01 || data);
        V = hmac(K, V);
    }
}

/* 생성: V = HMAC(K, V) 반복 → 출력 후 상태 업데이트 */

CTR-DRBG vs HMAC-DRBG 비교

Jitter RNG — CPU 타이밍 지터 기반 엔트로피

엔트로피 추정 원리

Jitter RNG는 CPU 실행 시간의 미세한 변동(Jitter)을 엔트로피 소스로 활용합니다. 캐시 미스, 분기 예측, TLB 플러시, 인터럽트 등으로 인해 동일한 연산도 매번 미세하게 다른 시간이 소요됩니다.

TSC(Time Stamp Counter)를 읽어 메모리 접근 연산의 실행 시간 차이(delta)를 수집하고, 반복 카운트 테스트(Repetition Count Test)와 적응적 비율 테스트(Adaptive Proportion Test)로 엔트로피 품질을 검증합니다.

컨디셔닝 함수

수집된 원시 샘플은 LFSR(Linear Feedback Shift Register) 기반 컨디셔닝으로 압축됩니다. 오버샘플링 비율(Oversampling Factor)은 보통 64:1 이상으로, 64개의 원시 샘플에서 1비트의 엔트로피를 추출합니다. 이는 보수적인 추정치로, 실제 엔트로피는 더 높을 수 있습니다.

Jitter RNG의 보안성은 Stephan Müller의 수학적 분석(SP 800-90B 기반)에 의해 검증되었으며, 리눅스 커널 5.0부터 CRNG의 부팅 초기 엔트로피 소스로 사용됩니다. RDRAND/RDSEED 하드웨어 RNG가 신뢰할 수 없는 환경(가상 머신, 에뮬레이터)에서도 엔트로피를 제공할 수 있는 소프트웨어 기반 대안입니다.

상세한 커널 RNG 아키텍처(ChaCha20 CRNG, 엔트로피 풀 등)는 Crypto API의 RNG 섹션과 hwrng 문서를 참고하세요.

키 유도 함수 (Key Derivation Functions)

키 유도 함수(KDF)는 비밀 재료(Secret Material)에서 하나 이상의 암호화 키를 유도합니다. 공유 비밀(ECDH 결과)이나 비밀번호처럼 직접 키로 사용하기에 부적합한 입력에서 고품질 키를 추출합니다.

HKDF (HMAC-based Key Derivation Function)

HKDF는 RFC 5869에 정의된 2단계 KDF입니다. 높은 엔트로피의 입력(ECDH 공유 비밀 등)에서 키를 유도할 때 사용됩니다.

Extract — 엔트로피 집중

PRK = HMAC-Hash(salt, IKM). 입력 키 재료(IKM)의 엔트로피를 고정 길이 PRK(Pseudorandom Key)로 집중합니다. salt는 선택적이지만, 도메인 분리와 엔트로피 추출의 견고성을 높여줍니다.

Expand — 키 재료 확장

PRK에서 원하는 길이의 OKM(Output Keying Material)을 생성합니다.

/* HKDF-Expand: PRK에서 OKM 확장 */
int hkdf_expand(const uint8_t *prk, size_t prk_len,
                const uint8_t *info, size_t info_len,
                uint8_t *okm, size_t okm_len)
{
    uint8_t T[HASH_LEN];
    size_t t_len = 0, offset = 0;
    int n = (okm_len + HASH_LEN - 1) / HASH_LEN;

    if (n > 255) return -EINVAL;  /* 최대 255 × HashLen */

    for (uint8_t i = 1; i <= n; i++) {
        /* T(i) = HMAC(PRK, T(i-1) || info || i) */
        hmac_init(prk, prk_len);
        if (t_len > 0) hmac_update(T, t_len);
        hmac_update(info, info_len);
        hmac_update(&i, 1);
        hmac_final(T);
        t_len = HASH_LEN;

        size_t copy = min(HASH_LEN, okm_len - offset);
        memcpy(okm + offset, T, copy);
        offset += copy;
    }
    return 0;
}

커널 내 HKDF 사용 사례: fscrypt(마스터 키 → 파일별 키), kTLS(TLS 1.3 키 스케줄), WireGuard(Noise 프로토콜 체이닝 키). 구현은 fs/crypto/hkdf.c에 있습니다.

PBKDF2 (Password-Based Key Derivation Function 2)

PBKDF2(RFC 8018)는 비밀번호에서 암호화 키를 유도하는 함수입니다. 의도적으로 높은 계산 비용(반복)을 적용하여 무차별 대입을 지연시킵니다.

반복(Iteration)과 솔팅(Salting)

PBKDF2(Password, Salt, c, dkLen):
    for i = 1 to ceil(dkLen / hLen):
        U₁ = PRF(Password, Salt ∥ INT_32_BE(i))
        U₂ = PRF(Password, U₁)
        ...
        U_c = PRF(Password, U_{c-1})
        T_i = U₁ ⊕ U₂ ⊕ ... ⊕ U_c   (XOR 누적)

    DK = T₁ ∥ T₂ ∥ ... 의 처음 dkLen 바이트

솔트: 최소 128비트(16바이트) 권장. 레인보우 테이블 방어 및 동일 비밀번호의 도메인 분리. 반복 횟수: OWASP(2023)는 HMAC-SHA-256 기준 최소 600,000회를 권장합니다.

PBKDF2 vs 현대 대안 비교

알고리즘 종합 비교

서로 다른 유형의 암호 알고리즘은 보안 강도, 성능 특성, 적용 환경이 상이합니다. 이 섹션에서는 대칭/비대칭/해시 알고리즘의 보안 수준 대응 관계, 실측 성능, 커널 서브시스템별 권장 알고리즘을 종합적으로 비교합니다.

보안 강도 수준 비교

암호학적 보안 강도는 "보안 비트(Security Bits)"로 표현됩니다. n비트 보안이란, 최선의 알려진 공격이 약 2ⁿ번의 연산을 요구한다는 의미입니다. 서로 다른 유형의 알고리즘이 동일한 보안 수준을 달성하기 위해 필요한 키 크기는 상이하며, 특히 ECC의 효율성이 두드러집니다. 128비트 보안에서 RSA는 3072비트가 필요하지만 ECC는 256비트면 충분합니다.

성능 특성 비교

커널 서브시스템별 알고리즘 선택 가이드

다음 표는 리눅스 커널의 주요 보안 서브시스템별 권장 알고리즘과 Crypto API 이름을 정리합니다. 알고리즘 선택 기준은 보안 강도, 하드웨어 가속 가용성, 프로토콜 표준 준수입니다.

관련 문서

• Linux Crypto Framework — 커널 암호화 API 사용법 및 구현 상세
• 커널 보안 — 리눅스 커널 보안 메커니즘 종합
• 하드웨어 난수 생성기 — hwrng & QRNG
• Key Retention Service — 커널 키 관리
• TPM 2.0 — 신뢰 플랫폼 모듈
• WireGuard — ChaCha20-Poly1305 VPN
• kTLS — 커널 TLS 오프로드
• IPsec & xfrm — IP 보안 프로토콜
• 네트워크 보안 — 네트워크 계층 보안

외부 참고 자료

• FIPS 197 — AES (Advanced Encryption Standard) — NIST AES 표준 사양서입니다
• FIPS 180-4 — Secure Hash Standard (SHA) — SHA-1, SHA-256, SHA-512 등 해시 표준입니다
• FIPS 186-5 — Digital Signature Standard (DSS) — RSA, ECDSA, EdDSA 디지털 서명 표준입니다
• NIST SP 800-38A — Block Cipher Modes — ECB, CBC, CTR 등 블록 암호 운용 모드 가이드입니다
• NIST SP 800-38D — GCM Mode — Galois/Counter Mode (GCM) 사양입니다
• RFC 7539 — ChaCha20 and Poly1305 — ChaCha20-Poly1305 AEAD 알고리즘 사양입니다
• RFC 8032 — Edwards-Curve Digital Signature (EdDSA) — Ed25519/Ed448 알고리즘 사양입니다
• RFC 5869 — HKDF (HMAC-based Key Derivation Function) — HKDF 키 유도 함수 사양입니다
• ChaCha — Daniel J. Bernstein — ChaCha 스트림 암호 설계자의 원본 논문 페이지입니다
• NIST Post-Quantum Cryptography — 포스트 양자 암호화 표준화 프로젝트입니다
• Kernel Crypto API Documentation — 이 알고리즘들이 구현된 커널 Crypto API 공식 문서입니다
• Linux 커널 crypto/ 소스 코드 — AES, SHA, RSA 등 알고리즘 커널 구현체입니다