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

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

대칭 암호 (Symmetric Ciphers)

대칭 암호(Symmetric Cipher)는 암호화와 복호화(Decryption)에 동일한 키를 사용하는 암호 체계입니다. 송신자와 수신자가 같은 비밀 키를 공유해야 하므로 키 배포 문제가 있지만, 비대칭 암호보다 수천 배 빠르기 때문에 실제 데이터 암호화에 항상 대칭 암호가 사용됩니다. TLS, IPsec, WireGuard, dm-crypt 등 거의 모든 보안 프로토콜에서 핵심 데이터 암호화 계층은 대칭 암호입니다.

대칭 암호는 크게 블록 암호(Block Cipher)와 스트림 암호(Stream Cipher)로 나뉩니다. 블록 암호는 고정 크기(AES: 128비트) 블록 단위로 데이터를 처리하며, 임의 길이 데이터를 다루려면 CBC, CTR 같은 운용 모드가 필요합니다. 스트림 암호는 키에서 연속적인 키스트림(Keystream)을 생성하여 평문과 XOR하므로 별도의 운용 모드 없이 임의 길이를 처리합니다. 리눅스 커널에서는 AES(블록 암호)와 ChaCha20(스트림 암호)이 가장 널리 사용됩니다.

좋은 암호 알고리즘은 두 가지 속성을 갖춰야 합니다. 혼돈(Confusion)은 키와 암호문의 관계를 복잡하게 만드는 것으로, AES에서는 S-Box(비선형 치환)가 이 역할을 합니다. 확산(Diffusion)은 평문의 작은 변화가 암호문 전체에 영향을 미치게 하는 것으로, AES에서는 ShiftRows와 MixColumns가 담당합니다. 이 두 속성의 조합으로 각 라운드를 반복하면 입력과 출력 사이의 통계적 관계가 완전히 파괴됩니다.

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₁₅는 다음과 같이 매핑(Mapping)됩니다.

상태 행렬의 각 바이트 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)로 미리 계산하여 사용합니다.

리눅스 커널의 crypto/aes_generic.c는 S-Box를 미리 계산된 4개의 Te 테이블(각 256×32비트)로 확장하여, SubBytes+ShiftRows+MixColumns를 단일 테이블 룩업 4회로 처리합니다. 이를 T-테이블(T-table) 최적화라 합니다.

/* crypto/aes_generic.c — T-테이블 기반 AES 라운드 최적화 */
/* Te0[x] = S[x].[02,01,01,03] — SubBytes+ShiftRows+MixColumns 통합 */
static const u32 Te0[256] = {
    0xc66363a5U, 0xf87c7c84U, 0xee777799U, 0xf67b7b8dU,
    0xfff2f20dU, 0xd66b6bbdU, 0xde6f6fb1U, 0x91c5c554U,
    /* ... 나머지 248개 엔트리 ... */
};

/* AES-128 1라운드: 4번의 테이블 룩업으로 처리 */
/* s0..s3: 상태 행렬의 4개 열 (각 32비트 워드) */
t0 = Te0[s0 >> 24] ^ Te1[(s1 >> 16) & 0xff] ^
     Te2[(s2 >> 8) & 0xff] ^ Te3[s3 & 0xff] ^ rk[4];
t1 = Te0[s1 >> 24] ^ Te1[(s2 >> 16) & 0xff] ^
     Te2[(s3 >> 8) & 0xff] ^ Te3[s0 & 0xff] ^ rk[5];
t2 = Te0[s2 >> 24] ^ Te1[(s3 >> 16) & 0xff] ^
     Te2[(s0 >> 8) & 0xff] ^ Te3[s1 & 0xff] ^ rk[6];
t3 = Te0[s3 >> 24] ^ Te1[(s0 >> 16) & 0xff] ^
     Te2[(s1 >> 8) & 0xff] ^ Te3[s2 & 0xff] ^ rk[7];

Te0~Te3 각 테이블은 S-Box 출력과 MixColumns 행렬의 서로 다른 행을 사전 결합한 것입니다. Te0[x]는 S(x)에 대해 {02, 01, 01, 03} 열을 곱한 32비트 결과이고, Te1~Te3은 바이트 순환 시프트 변형입니다. 이 방식은 라운드당 16번의 테이블 룩업과 16번의 XOR만으로 SubBytes+ShiftRows+MixColumns+AddRoundKey 전체를 완료합니다.

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) 행렬은 다음과 같습니다.

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 암호화/복호화의 진입점(Entry Point)은 crypto/aes_generic.c의 crypto_aes_encrypt()/crypto_aes_decrypt()입니다. 다음은 커널의 실제 암호화 함수 구조입니다.

/* crypto/aes_generic.c — 커널 AES 암호화 함수 (간략화) */
void crypto_aes_encrypt(struct crypto_tfm *tfm,
                        u8 *out, const u8 *in)
{
    const struct crypto_aes_ctx *ctx = crypto_tfm_ctx(tfm);
    const u32 *rk = ctx->key_enc;  /* 확장 키 (44/52/60 워드) */
    u32 s0, s1, s2, s3, t0, t1, t2, t3;
    int nrounds = ctx->key_length / 4 + 6;  /* 10/12/14 */

    /* 초기 AddRoundKey (K_0) */
    s0 = get_unaligned_be32(in     ) ^ rk[0];
    s1 = get_unaligned_be32(in +  4) ^ rk[1];
    s2 = get_unaligned_be32(in +  8) ^ rk[2];
    s3 = get_unaligned_be32(in + 12) ^ rk[3];
    rk += 4;

    /* 중간 라운드: T-테이블 룩업으로 통합 처리 */
    for (int r = 1; r < nrounds; r++) {
        t0 = Te0[s0 >> 24] ^ Te1[(s1 >> 16) & 0xff] ^
             Te2[(s2 >> 8) & 0xff] ^ Te3[s3 & 0xff] ^ rk[0];
        /* ... t1, t2, t3도 동일 패턴 ... */
        s0 = t0; s1 = t1; s2 = t2; s3 = t3;
        rk += 4;
    }

    /* 마지막 라운드: MixColumns 없이 S-Box만 사용 */
    s0 = (Te2[(t0 >> 24)] & 0xff000000) ^
         (Te3[(t1 >> 16) & 0xff] & 0x00ff0000) ^
         (Te0[(t2 >> 8) & 0xff] & 0x0000ff00) ^
         (Te1[ t3 & 0xff] & 0x000000ff) ^ rk[0];
    /* ... s1, s2, s3 동일 ... */

    put_unaligned_be32(s0, out     );
    put_unaligned_be32(s1, out +  4);
    put_unaligned_be32(s2, out +  8);
    put_unaligned_be32(s3, out + 12);
}

마지막 라운드는 MixColumns가 없으므로, Te 테이블에서 S-Box 바이트만 추출(마스킹)하여 결과를 구성합니다. ctx->key_enc는 crypto_aes_expand_key()로 사전에 확장된 라운드 키 배열이며, ctx->key_dec에는 InvMixColumns가 적용된 복호화용 키가 별도로 저장됩니다.

보안 속성과 알려진 공격

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

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

AES 같은 블록 암호는 한 번에 딱 128비트(16바이트)만 처리할 수 있습니다. 그러나 실제 암호화할 데이터(파일, 네트워크 패킷(Packet) 등)는 대부분 16바이트보다 훨씬 큽니다. 이 문제를 해결하는 것이 운용 모드(Mode of Operation)입니다. 운용 모드는 여러 블록을 어떤 순서와 방식으로 처리할지 정의하며, 모드 선택에 따라 보안성, 성능, 에러 복구 특성이 크게 달라집니다.

운용 모드를 선택할 때 고려해야 할 핵심 속성은 다음과 같습니다.

• 패턴 은닉: 동일한 평문 블록이 동일한 암호문을 만들어서는 안 됩니다
• 병렬 처리: 여러 블록을 동시에 암호화/복호화할 수 있는지 여부
• 임의 접근: 중간 블록만 단독으로 복호화할 수 있는지 여부 (디스크 암호화에 중요)
• 인증: 데이터 변조를 감지할 수 있는지 여부

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

ECB(Electronic Codebook)는 가장 단순한 운용 모드로, 각 블록을 독립적으로 암호화합니다: C_i = E_K(P_i). 하지만 이 단순함이 치명적인 약점입니다 — 동일한 평문 블록은 항상 동일한 암호문을 생성하므로, 원본 데이터의 패턴이 암호문에 그대로 보존됩니다.

CBC (Cipher Block Chaining) 모드

CBC(Cipher Block Chaining)는 ECB의 패턴 보존 문제를 해결하는 가장 직관적인 방식입니다. 핵심 아이디어는 이전 블록의 암호문을 다음 블록의 암호화에 섞는 것입니다. 이렇게 하면 동일한 평문 블록이라도 이전 블록이 다르면 완전히 다른 암호문이 됩니다. 첫 블록에는 이전 암호문이 없으므로, 랜덤한 초기화 벡터(IV, Initialization Vector)를 대신 사용합니다. IV는 비밀일 필요는 없지만, 반드시 매번 새로운 값이어야 합니다.

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

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

CTR (Counter) 모드

CTR(Counter) 모드는 블록 암호를 스트림 암호처럼 사용하는 모드입니다. 평문을 직접 암호화하는 대신, Nonce(Number used Once, 한 번만 사용하는 고유 번호)와 순차적으로 증가하는 카운터(Counter)를 결합한 값을 AES로 암호화하여 키스트림을 만들고, 이를 평문과 XOR합니다. CBC와 달리 각 블록의 키스트림 생성이 완전히 독립적이므로 병렬 처리가 가능하며, 패딩도 불필요합니다.

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

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

XTS (XEX-based Tweaked CodeBook) 모드

디스크 암호화에는 CBC나 CTR과 다른 특수한 요구사항이 있습니다. 디스크는 섹터 단위(보통 512B~4KB)로 임의 접근해야 하므로, 전체 체인을 순회하는 CBC는 부적합합니다. 또한 암호문 크기가 평문과 정확히 같아야 하므로(디스크 섹터 크기 고정), 인증 태그를 붙이는 GCM도 쓸 수 없습니다. XTS(XEX-based Tweaked CodeBook)는 이러한 디스크 암호화의 제약을 해결하기 위해 설계된 IEEE P1619 표준 모드입니다.

XTS의 핵심 아이디어는 트윅(Tweak)입니다. 트윅은 섹터 번호와 블록 인덱스에서 유도되는 값으로, 같은 평문이라도 디스크의 다른 위치에서는 다른 암호문을 생성합니다. 두 개의 키(K₁: 데이터 암호화, K₂: 트윅 암호화)를 사용합니다.

• 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 */
}

운용 모드 비교

리눅스 커널의 블록 암호 운용 모드는 crypto/cbc.c, crypto/ctr.c, crypto/xts.c 등에 구현됩니다. Crypto API의 skcipher 인터페이스를 통해 접근하며, scatterlist 기반 비연속 메모리를 직접 처리합니다.

/* crypto/cbc.c — CBC 모드 암호화 커널 구현 (간략화) */
static int crypto_cbc_encrypt(struct skcipher_request *req)
{
    struct crypto_skcipher *tfm = crypto_skcipher_reqtfm(req);
    struct skcipher_walk walk;
    int err;

    err = skcipher_walk_virt(&walk, req, false);

    while (walk.nbytes) {
        u8 *src = walk.src.virt.addr;
        u8 *dst = walk.dst.virt.addr;
        u8 *iv  = walk.iv;             /* 이전 암호문 블록 (또는 IV) */
        int nbytes = walk.nbytes;

        do {
            crypto_xor(iv, src, bsize);  /* P_i ⊕ C_{i-1} (XOR) */
            crypto_cipher_encrypt_one(cipher, iv, iv); /* E_K() */
            memcpy(dst, iv, bsize);      /* C_i = E_K(P_i ⊕ C_{i-1}) */
            src += bsize;
            dst += bsize;
        } while ((nbytes -= bsize) >= bsize);

        err = skcipher_walk_done(&walk, nbytes);
    }
    return err;
}

/* crypto/ctr.c — CTR 모드 커널 구현 (간략화) */
/* CTR 모드는 카운터를 암호화하여 키스트림 생성 → 평문과 XOR */
static int crypto_ctr_crypt(struct skcipher_request *req)
{
    struct skcipher_walk walk;
    u8 keystream[16];  /* AES 블록 크기 */
    int err;

    err = skcipher_walk_virt(&walk, req, false);

    while (walk.nbytes >= bsize) {
        /* E_K(CTR) → 키스트림 블록 */
        crypto_cipher_encrypt_one(cipher, keystream, walk.iv);
        /* 키스트림 ⊕ 평문 → 암호문 */
        crypto_xor_cpy(walk.dst.virt.addr,
                       walk.src.virt.addr, keystream, bsize);
        /* 카운터 증가 (빅 엔디안) */
        crypto_inc(walk.iv, bsize);  /* CTR++ */
        err = skcipher_walk_done(&walk, walk.nbytes - bsize);
    }
    /* 마지막 부분 블록 처리 (패딩 불필요, 스트림 특성) */
    return err;
}

skcipher_walk은 scatterlist를 순회하며 가상 주소(Virtual Address) 매핑을 관리하는 커널 헬퍼입니다. CBC는 블록 체인 구조상 암호화가 순차적이지만, CTR은 카운터만 증가하므로 이론적으로 병렬화가 가능합니다. 실제로 AES-NI 구현(arch/x86/crypto/aesni-intel_glue.c)은 CTR 모드에서 여러 블록을 파이프라이닝하여 처리합니다.

ChaCha20 스트림 암호 내부 구조

AES가 S-Box(룩업 테이블)와 유한체 곱셈을 사용하는 반면, ChaCha20은 오직 세 가지 기본 산술 연산만으로 동작합니다: ARX = Add(32비트 모듈러 덧셈) + Rotate(비트 회전) + XOR(배타적 논리합). 이 세 연산은 모든 CPU에서 네이티브로 지원되고, 데이터 의존적 분기(Branch)나 메모리 접근이 없으므로 본질적으로 상수 시간(Constant-Time) 실행이 보장됩니다. 즉, AES와 달리 캐시 타이밍 사이드 채널 공격에 면역입니다.

ChaCha20은 Daniel Bernstein이 설계한 스트림 암호(Stream Cipher)입니다. AES-NI 하드웨어 가속이 없는 플랫폼(일부 ARM, MIPS)에서도 AES보다 빠르며, WireGuard VPN과 TLS 1.3의 기본 암호로 채택되었습니다. 리눅스 커널의 CRNG(암호학적 난수 생성기) 내부에서도 ChaCha20이 핵심 스트림 암호로 사용됩니다.

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

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

"expand 32-byte k" ASCII 상수(리틀 엔디안(Endianness))는 아무 의미 없는(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 구현은 lib/crypto/chacha.c에 범용(Generic) 버전이, arch/x86/crypto/chacha_glue.c에 SIMD 최적화 버전이 있습니다. 커널 CRNG(암호학적 난수 생성기)에서도 ChaCha20을 핵심 스트림 암호로 사용합니다.

/* lib/crypto/chacha.c — 커널 ChaCha20 범용 구현 */
void chacha_crypt_generic(u32 *state, u8 *dst,
                         const u8 *src, unsigned int bytes,
                         int nrounds)
{
    u32 buf[CHACHA_BLOCK_SIZE / sizeof(u32)]; /* 64바이트 키스트림 */

    while (bytes >= CHACHA_BLOCK_SIZE) {
        chacha_block_generic(state, buf, nrounds);
        crypto_xor_cpy(dst, src, (u8 *)buf, CHACHA_BLOCK_SIZE);
        bytes -= CHACHA_BLOCK_SIZE;
        src += CHACHA_BLOCK_SIZE;
        dst += CHACHA_BLOCK_SIZE;
        state[12]++;  /* 카운터 증가 (state[12] = counter) */
    }
    if (bytes) {
        /* 마지막 부분 블록: 키스트림 생성 후 필요한 만큼만 XOR */
        chacha_block_generic(state, buf, nrounds);
        crypto_xor_cpy(dst, src, (u8 *)buf, bytes);
    }
}

/* drivers/char/random.c — 커널 CRNG도 ChaCha20 사용 */
/* crng_fast_key_erasure(): ChaCha20으로 난수 생성 후 */
/* 키를 즉시 폐기하여 forward secrecy 보장 */

chacha_block_generic()은 20라운드(ChaCha20) 또는 12라운드(ChaCha12, XChaCha)를 수행합니다. x86에서는 chacha_4block_avx2()가 AVX2 SIMD로 4블록을 동시에 처리하여 처리량(Throughput)을 극대화합니다. 커널 CRNG(drivers/char/random.c)는 ChaCha20으로 난수를 생성한 직후 키를 덮어씀(Fast Key Erasure)으로써, 상태 노출 시에도 이전 출력을 복원할 수 없도록 전방 비밀성(Forward Secrecy)을 보장합니다.

ChaCha20 vs AES 비교

해시(Hash) 함수 (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 구현은 lib/crypto/sha256.c에 있으며, 다음과 같이 압축 함수를 처리합니다.

/* lib/crypto/sha256.c — 커널 SHA-256 압축 함수 (간략화) */
static void sha256_transform(u32 *state, const u8 *input)
{
    u32 a, b, c, d, e, f, g, h;
    u32 W[64], t1, t2;
    int i;

    /* W[0..15]: 입력 블록에서 빅 엔디안으로 추출 */
    for (i = 0; i < 16; i++)
        W[i] = get_unaligned_be32(input + 4 * i);

    /* W[16..63]: σ₀, σ₁ 함수로 확장 */
    for (i = 16; i < 64; i++)
        W[i] = sigma1(W[i - 2]) + W[i - 7] +
               sigma0(W[i - 15]) + W[i - 16];

    /* 작업 변수 초기화: 현재 해시 상태에서 복사 */
    a = state[0]; b = state[1]; c = state[2]; d = state[3];
    e = state[4]; f = state[5]; g = state[6]; h = state[7];

    /* 64라운드 압축 */
    for (i = 0; i < 64; i++) {
        t1 = h + Sigma1(e) + Ch(e, f, g) + SHA256_K[i] + W[i];
        t2 = Sigma0(a) + Maj(a, b, c);
        h = g; g = f; f = e;
        e = d + t1;
        d = c; c = b; b = a;
        a = t1 + t2;
    }

    /* 해시 상태에 누적 덧셈 */
    state[0] += a; state[1] += b; state[2] += c; state[3] += d;
    state[4] += e; state[5] += f; state[6] += g; state[7] += h;
}

x86 시스템에서 SHA-NI 명령어(Intel Goldmont+, AMD Zen+)가 지원되면 arch/x86/crypto/sha256_ni_asm.S의 어셈블리(Assembly) 구현이 우선 사용되어 처리량이 소프트웨어 대비 3~5배 향상됩니다. crypto_shash_update()를 호출하면 커널이 자동으로 최적 구현을 선택합니다.

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

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

SHA-512와 SHA-256 차이점

SHA-512는 SHA-256과 동일한 Merkle-Damgård 구조와 압축 함수 설계를 사용하지만, 모든 연산이 64비트 워드 기반으로 확장됩니다. 64비트 CPU(x86-64, ARM64)에서는 네이티브 64비트 연산을 사용하므로 SHA-256보다 오히려 더 빠른 경우가 많습니다. 반면 32비트 CPU에서는 64비트 연산을 에뮬레이션해야 하므로 상당히 느려집니다. 이런 이유로 리눅스 커널의 모듈 서명은 SHA-512를 기본으로 사용하지만, IMA 등 임베디드 환경도 고려해야 하는 서브시스템은 SHA-256을 사용합니다.

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는 여전히 안전한 것으로 간주됩니다(새 시스템에서는 권장하지 않습니다).

리눅스 커널의 HMAC 구현(crypto/hmac.c)은 ipad/opad 해시 상태를 키 설정 시점에 사전 계산하여 캐싱합니다. 이를 통해 매 HMAC 연산마다 키 패딩을 반복할 필요 없이, 캐싱된 중간 해시 상태에서 즉시 시작할 수 있습니다.

/* crypto/hmac.c — 커널 HMAC 구현 (사전 계산 최적화) */
struct hmac_ctx {
    struct crypto_shash *hash;    /* 기반 해시 (SHA-256 등) */
    u8 ipad_state[];              /* H(K' ⊕ ipad) 중간 상태 */
    u8 opad_state[];              /* H(K' ⊕ opad) 중간 상태 */
};

/* setkey: ipad/opad 해시 상태를 사전 계산 */
static int hmac_setkey(struct crypto_shash *parent,
                      const u8 *inkey, unsigned int keylen)
{
    /* 키가 블록 크기보다 길면 해시 */
    if (keylen > bs)
        crypto_shash_digest(shash, inkey, keylen, ipad);

    /* ipad = K' ⊕ 0x36..., opad = K' ⊕ 0x5C... */
    for (i = 0; i < bs; i++) {
        ipad[i] ^= 0x36;
        opad[i] ^= 0x5C;
    }

    /* 중간 해시 상태 캐싱: init → update(pad) → export */
    crypto_shash_init(shash);
    crypto_shash_update(shash, ipad, bs);
    crypto_shash_export(shash, ipad_state);  /* 상태 저장 */

    crypto_shash_init(shash);
    crypto_shash_update(shash, opad, bs);
    crypto_shash_export(shash, opad_state);  /* 상태 저장 */
    return 0;
}

/* finup: 캐싱된 상태에서 시작하여 HMAC 계산 */
static int hmac_finup(struct shash_desc *pdesc,
                      const u8 *data, unsigned int nbytes,
                      u8 *out)
{
    /* 내부 해시 완료: H(ipad_state || msg) → 다이제스트 */
    crypto_shash_finup(desc, data, nbytes, out);

    /* 외부 해시: opad 상태 복원 → update(내부 해시) → final */
    crypto_shash_import(desc, opad_state);
    return crypto_shash_finup(desc, out, ds, out);
}

이 사전 계산 최적화 덕분에, 동일한 키로 여러 메시지의 HMAC을 계산할 때 키 패딩+해싱 단계를 반복하지 않아 성능이 크게 향상됩니다. IPsec처럼 패킷마다 HMAC을 계산하는 고빈도 환경에서 특히 중요합니다.

인증 암호화 (Authenticated Encryption)

AES-CBC나 AES-CTR 같은 암호화 모드는 데이터를 읽을 수 없게 만들지만(기밀성), 데이터가 변조되었는지는 감지하지 못합니다. 공격자가 암호문의 비트를 뒤집으면, 복호화 결과도 예측 가능하게 변조됩니다(특히 CTR 모드에서 1비트 변경은 평문의 정확히 1비트를 변경합니다). 따라서 암호화와 별도로 MAC(Message Authentication Code)을 붙여 무결성(Integrity)을 검증해야 하는데, 이 조합을 잘못하면 심각한 보안 취약점(Vulnerability)이 발생합니다.

인증 암호화(AEAD, Authenticated Encryption with Associated Data)는 기밀성과 무결성/인증을 하나의 알고리즘으로 동시에 제공합니다. 암호화 결과에 인증 태그(Tag)가 함께 생성되며, 복호화 시 태그가 일치하지 않으면 데이터를 거부합니다. AEAD의 "AD(Associated Data)"는 암호화하지는 않지만 인증은 해야 하는 데이터(예: 패킷 헤더, 프로토콜 버전)를 의미합니다. TLS 1.3, IPsec, WireGuard 등 현대 프로토콜은 모두 AEAD만 허용합니다.

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의 두 핵심 연산은 각각 전용 하드웨어 명령어로 가속됩니다.

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

커널에서 AES-GCM은 crypto/gcm.c에 구현되어 있으며, AEAD 인터페이스(struct aead_request)를 통해 암호화+인증을 한 번의 호출로 처리합니다. IPsec은 RFC 4106 형식을, kTLS는 표준 GCM 형식을 사용합니다.

/* crypto/gcm.c — 커널 GCM AEAD 암호화 (흐름 간략화) */
static int crypto_gcm_encrypt(struct aead_request *req)
{
    struct crypto_gcm_req_priv_ctx *pctx = ...;

    /* 1단계: GHASH(AAD) — 인증 데이터 해싱 */
    gcm_hash_assoc(req, pctx);

    /* 2단계: CTR 모드 암호화 (J₀+1부터 시작) */
    crypto_skcipher_encrypt(skreq);  /* AES-CTR */

    /* 3단계: GHASH(C) — 암호문 해싱 */
    gcm_hash_ciphertext(req, pctx);

    /* 4단계: GHASH(len(A)||len(C)) + E_K(J₀) → 태그 */
    gcm_hash_len_done(req, pctx);

    /* 태그를 암호문 뒤에 붙임 */
    crypto_gcm_encrypt_done(req);
    return 0;
}

/* 복호화 시: 태그 검증 실패하면 -EBADMSG 반환 */
/* → 평문을 0으로 덮어쓰고 호출자에게 오류 전달 */

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는 가장 오래되고 널리 사용되는 비대칭 암호 알고리즘입니다. 1977년 Rivest, Shamir, Adleman이 발표했으며, 큰 수의 소인수 분해가 어렵다는 사실에 기반합니다. 두 큰 소수 p, q를 곱하면 n = p×q를 쉽게 구할 수 있지만, n만 주어졌을 때 p와 q를 찾는 것은 현재 알려진 알고리즘으로 천문학적인 시간이 필요합니다. 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 공격 유형과 방어

커널의 RSA 구현은 crypto/rsa.c에 있으며, MPI(Multi-Precision Integer) 라이브러리(lib/mpi/)를 사용합니다. 모듈 서명 검증(Signature Verification)이 주요 사용처이며, CRT 최적화와 타이밍 공격 방어를 위한 블라인딩(Blinding)을 지원합니다.

/* crypto/rsa.c — 커널 RSA 서명 검증 (간략화) */
static int rsa_verify(struct akcipher_request *req)
{
    struct rsa_mpi_key *pkey = &ctx->key;
    MPI s, m;

    /* 서명값 s를 MPI로 변환 */
    s = mpi_read_raw_from_sgl(req->src, req->src_len);

    /* m = s^e mod n (공개키 연산) */
    m = mpi_alloc(0);
    mpi_powm(m, s, pkey->e, pkey->n);

    /* 결과를 출력 scatterlist에 기록 */
    mpi_write_to_sgl(m, req->dst, req->dst_len, ...);

    mpi_free(s);
    mpi_free(m);
    return 0;
}

/* lib/mpi/mpi-pow.c — 모듈러 거듭제곱 (제곱-곱셈) */
/* mpi_powm(): Montgomery 리덕션 + 슬라이딩 윈도우 최적화 */
/* 2048비트 RSA 검증: ~1,000 op/s (소프트웨어) */

mpi_powm()은 Montgomery 곱셈과 슬라이딩 윈도우 기법으로 최적화된 모듈러 거듭제곱입니다. 커널은 RSA 개인키 연산(서명, 복호화)보다 공개키 연산(검증)을 훨씬 자주 수행합니다 — 부팅 시 수백 개의 모듈 서명을 검증하지만, 서명 생성은 사용자 공간(User Space)에서 처리합니다.

타원 곡선 암호 (Elliptic Curve Cryptography)

타원 곡선 암호(ECC, Elliptic Curve Cryptography)는 RSA에 비해 훨씬 작은 키로 동등한 보안을 제공하는 비대칭 암호 방식입니다. 256비트 ECC 키는 3,072비트 RSA 키와 동등한 128비트 보안을 제공합니다. 키 크기가 작으면 연산 속도, 메모리 사용량, 네트워크 전송량 모두에서 유리하므로, TLS 1.3에서는 ECDHE(타원 곡선 디피-헬먼)가 키 교환의 기본값입니다.

타원 곡선 암호의 보안은 타원 곡선 이산 로그 문제(ECDLP)에 기반합니다. 곡선 위의 기저점(Base Point) G에 정수 d를 곱하여 Q = dG를 계산하는 것은 쉽지만(스칼라 곱셈), Q와 G만 주어졌을 때 d를 역으로 찾는 것은 현재 알려진 알고리즘으로 사실상 불가능합니다. 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)는 타원 곡선 위에서 디피-헬먼 키 교환을 수행합니다.

EdDSA / Ed25519 — 에드워즈 곡선 서명

EdDSA(Edwards-curve Digital Signature Algorithm)는 RFC 8032에 표준화된 타원 곡선 디지털 서명 방식입니다. ECDSA의 단점(랜덤 k 의존성, 복잡한 구현)을 해결하기 위해 Daniel Bernstein이 설계했으며, 결정적(Deterministic) 서명 생성, 빠른 검증, 간결한 구현이 특징입니다. 리눅스 커널에서는 모듈 서명과 IMA 서명의 대안으로 지원됩니다.

Curve25519와 에드워즈 형식

Ed25519는 비꼬인 에드워즈 곡선(Twisted Edwards Curve) -x² + y² = 1 + dx²y² (mod p)를 사용합니다. p = 2²⁵⁵ - 19이며, 기저점(Base Point) B의 위수(Order)는 소수 ℓ입니다. 에드워즈 형식의 점 덧셈 공식은 통합 공식(Unified Formula)으로, P = Q인 경우와 아닌 경우를 분기 없이 동일하게 처리하여 사이드 채널 안전성을 높입니다.

서명 생성과 검증

Ed25519 서명의 핵심 차이점은 난수를 사용하지 않는다는 것입니다. 대신 개인키의 해시에서 nonce를 결정적으로 유도합니다.

Ed25519 서명 생성:
  (a, prefix) = SHA-512(private_key)    -- 64바이트 해시의 전반부=스칼라, 후반부=prefix
  A = aB                                 -- 공개키 (압축된 점)
  r = SHA-512(prefix || M) mod ℓ         -- 결정적 nonce (메시지 의존)
  R = rB                                 -- nonce 점
  S = (r + SHA-512(R || A || M) · a) mod ℓ
  서명 = (R, S)  -- 총 64바이트

Ed25519 서명 검증:
  k = SHA-512(R || A || M) mod ℓ
  SB == R + kA ?                         -- 그룹 방정식 검증

Ed25519의 결정적 nonce 생성은 ECDSA의 가장 위험한 취약점(k 재사용/편향)을 원천적으로 제거합니다. 동일 메시지에 대해 항상 동일한 서명이 생성되므로, 테스트와 재현성도 우수합니다.

커널 Ed25519 구현

리눅스 커널의 Ed25519 구현은 crypto/ecdsasignature.asn1과 crypto/asymmetric_keys/에 있으며, 주로 모듈 서명 검증에 사용됩니다. 서명 검증만 커널에서 수행하고, 서명 생성은 사용자 공간의 sign-file 유틸리티가 담당합니다.

/* crypto/ecrdsa.c 및 asymmetric_keys — 커널 EdDSA 검증 흐름 */
/* 1. 공개키 파싱: ASN.1 DER에서 A (32바이트) 추출 */
/* 2. 서명 파싱: (R, S) 각 32바이트 */
/* 3. 검증 방정식: SB == R + SHA-512(R || A || M) · A */

/* 커널 모듈 서명 검증 사용 예 */
/* kernel/module/signing.c */
static int mod_verify_sig(const void *mod, struct load_info *info)
{
    struct public_key_signature *pks;

    pks = mod_make_digest(info->hdr, info->len);
    return verify_pkcs7_signature(
        mod, modlen,
        info->sig, info->sig_len,
        VERIFY_USE_SECONDARY_KEYRING,
        VERIFYING_MODULE_SIGNATURE,
        NULL, NULL
    );
    /* 내부적으로 RSA-PKCS#1 또는 ECDSA/EdDSA 검증 수행 */
}

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)

암호화의 모든 보안은 궁극적으로 예측 불가능한 난수에 의존합니다. AES 키, RSA 소수, ECDSA의 서명 nonce, TLS의 세션 ID — 이 모든 값이 예측 가능하면 아무리 강력한 알고리즘이라도 무력화됩니다. 암호학에서 "좋은 난수"란 단순히 통계적으로 균일한 것이 아니라, 과거 출력을 모두 관찰해도 다음 출력을 예측할 수 없는 난수입니다. 이를 CSPRNG(Cryptographically Secure Pseudo-Random Number Generator)이라 합니다.

난수 생성의 핵심 개념은 엔트로피(Entropy)입니다. 엔트로피는 "예측 불가능성의 양"을 비트 단위로 측정한 것입니다. 예를 들어 공정한 동전 던지기 1회는 1비트의 엔트로피를, 256면 주사위 1회는 8비트의 엔트로피를 제공합니다. 리눅스 커널은 하드웨어 인터럽트(Interrupt) 타이밍, CPU 타이밍 지터(Jitter), RDRAND 명령어 등 다양한 소스에서 엔트로피를 수집하고, 이를 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)을 엔트로피 소스로 활용합니다. 캐시 미스, 분기 예측(Branch Prediction), TLB 플러시(Flush), 인터럽트 등으로 인해 동일한 연산도 매번 미세하게 다른 시간이 소요됩니다.

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)

암호화 알고리즘은 고품질의 균일 분포(Uniform Distribution) 키를 요구하지만, 실제로 얻어지는 비밀 재료는 대부분 이 조건을 충족하지 못합니다. 예를 들어 ECDH 키 교환의 공유 비밀은 타원 곡선 위의 x좌표로, 비트가 균일하지 않습니다. 사용자 비밀번호는 엔트로피가 매우 낮고(보통 20~40비트), 직접 키로 사용하면 무차별 대입에 취약합니다.

키 유도 함수(KDF, Key Derivation Function)는 이런 부적합한 입력에서 고품질의 암호화 키를 추출하는 함수입니다. KDF는 크게 두 가지로 나뉩니다. HKDF처럼 이미 높은 엔트로피를 가진 입력(ECDH 공유 비밀, 랜덤 시드)에서 여러 키를 유도하는 유형과, PBKDF2/Argon2처럼 낮은 엔트로피 입력(비밀번호)에 의도적 연산 비용을 부과하여 무차별 대입을 지연(Latency)시키는 유형입니다.

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 현대 대안 비교

포스트 양자 암호화 (Post-Quantum Cryptography)

현재 사용되는 RSA, ECDSA, ECDH 등 비대칭 암호 알고리즘은 모두 소인수 분해나 이산 로그 문제의 어려움에 기반합니다. 그런데 충분히 강력한 오류 정정 양자 컴퓨터가 실현되면, Shor 알고리즘이 이 문제들을 다항 시간에 풀 수 있습니다. 따라서 RSA와 타원 곡선 기반 공개키는 장기적으로 구조적인 양자 취약성을 가집니다.

이에 대비하여 NIST는 2024년 8월 13일에 양자 컴퓨터로도 풀기 어려운 새로운 수학 문제에 기반한 포스트 양자 암호화(PQC) 표준 FIPS 203, FIPS 204, FIPS 205를 최종 발표했습니다. 한편, 대칭 암호(AES)와 해시 함수(SHA-256)는 양자 위협이 상대적으로 작습니다. Grover 알고리즘이 보안 강도를 줄이지만, AES-256을 사용하면 장기 보안 마진을 더 넉넉하게 가져갈 수 있습니다.

양자 컴퓨팅 기초 — 왜 기존 암호가 위험한가

포스트 양자 암호를 이해하려면 양자 컴퓨터가 왜 기존 암호를 깰 수 있는지 먼저 알아야 합니다. 핵심은 양자 비트(큐비트, Qubit)의 특성에 있습니다.

큐비트(Qubit)와 양자 중첩

고전 컴퓨터의 비트는 0 또는 1 중 하나의 값만 가집니다. 반면 양자 컴퓨터의 큐비트(Qubit)는 중첩(Superposition) 상태에 놓일 수 있어, 0과 1을 동시에 표현합니다. 비유하자면, 고전 비트가 "앞면" 또는 "뒷면"이 확정된 동전이라면, 큐비트는 공중에서 회전하는 동전처럼 앞면과 뒷면의 가능성을 동시에 품고 있습니다.

핵심은 양자 병렬성(Quantum Parallelism)입니다. n개의 큐비트가 중첩 상태에 있으면, 하나의 연산으로 2ⁿ개의 입력을 동시에 처리할 수 있습니다. 다만 측정 시에는 하나의 결과만 얻을 수 있으므로, 양자 알고리즘의 핵심은 "원하는 답의 확률을 증폭시키는" 기법(양자 간섭)에 있습니다.

Shor 알고리즘 — RSA가 깨지는 원리

RSA의 보안은 "두 큰 소수의 곱 N = p × q에서 p와 q를 찾는 것이 어렵다"는 가정에 기반합니다. 고전 컴퓨터의 최선의 알고리즘(GNFS)도 하위지수(sub-exponential) 시간이 필요합니다. 그런데 Shor 알고리즘은 이를 다항 시간 O(n³)으로 단축합니다.

같은 원리가 ECC(타원 곡선)의 이산 로그 문제와 DH 키 교환에도 적용됩니다. Shor 알고리즘의 변형이 이산 로그 문제도 다항 시간에 풀 수 있으므로, RSA뿐 아니라 현재 사용되는 모든 비대칭 암호가 양자 컴퓨터에 취약합니다.

Grover 알고리즘 — 대칭 암호에 미치는 영향

Grover 알고리즘은 정렬되지 않은 데이터베이스에서 원하는 항목을 √N번 만에 찾는 양자 알고리즘입니다. 암호학에서 이것은 n비트 키를 가진 대칭 암호의 보안 강도를 n/2비트로 줄이는 것을 의미합니다. AES-128의 경우 64비트 보안으로 약화되어 위험하지만, AES-256은 128비트 보안이 유지되므로 양자 시대에도 충분합니다.

PQC 알고리즘 패밀리 분류

양자 컴퓨터에 저항하는 암호 알고리즘은 기반으로 삼는 수학 문제에 따라 크게 네 가지 패밀리로 분류됩니다. 각 패밀리는 서로 다른 보안 가정에 의존하므로, 한 패밀리에서 취약점이 발견되더라도 다른 패밀리는 영향받지 않습니다.

격자 암호의 직관적 이해

NIST PQC 표준의 핵심인 격자(Lattice) 기반 암호를 이해하기 위해 일상적인 비유부터 시작합니다.

이것이 격자 기반 암호가 양자 안전한 핵심 이유입니다. Shor 알고리즘은 주기적 구조(정수의 곱셈 구조, 타원 곡선의 이산 로그)를 이용하지만, 격자 문제에는 Shor가 활용할 수 있는 주기적 구조가 존재하지 않습니다. 현재까지 알려진 최선의 격자 공격 알고리즘은 양자 컴퓨터를 사용하더라도 고전 컴퓨터와 본질적으로 같은 시간 복잡도를 보입니다.

"Harvest Now, Decrypt Later" 위협 모델

양자 컴퓨터가 아직 실현되지 않았더라도 PQC 전환이 급한 이유가 있습니다. "Harvest Now, Decrypt Later"(HNDL) 공격 모델에서 적대자는 현재 암호화된 네트워크 트래픽을 대량으로 수집하여 저장한 뒤, 미래에 충분히 강력한 양자 컴퓨터가 등장하면 이를 복호화합니다. 정부 기밀, 의료 기록, 금융 데이터처럼 10~30년 이상 기밀성이 유지되어야 하는 데이터는 지금 이 순간에도 양자 위협에 노출되어 있습니다.

NIST PQC 표준 알고리즘

알고리즘 선택 가이드 — 언제 무엇을 사용하는가

세 가지 표준은 서로 다른 역할을 담당하므로 경쟁 관계가 아닌 상호 보완 관계입니다. 다음 표는 사용 시나리오별 권장 알고리즘을 정리합니다.

격자 기반 암호의 핵심 — LWE 문제

격자(Lattice) 기반 암호의 보안은 LWE(Learning With Errors) 문제에 기반합니다. 공개 행렬 A와 비밀 벡터 s에 대해, b = As + e (mod q)에서 작은 오차(Error) 벡터 e가 포함된 결과로부터 s를 복원하는 것이 어렵다는 가정입니다.

ML-KEM (CRYSTALS-Kyber) — 키 캡슐화

ML-KEM(Module-Lattice Key Encapsulation Mechanism)은 키 교환에 사용되는 KEM입니다. TLS 1.3과 SSH에서 기존 X25519 키 교환의 대체/보완으로 도입되고 있습니다. ML-KEM-768이 128비트 보안 수준으로 가장 널리 배포됩니다.

LWE가 암호화를 가능하게 하는 원리 — 수치 예시

LWE 수식 b = As + e (mod q)에서 오차 e가 어떻게 보안을 제공하는지, 작은 수치로 직관을 잡아봅니다.

ML-KEM 키 캡슐화 흐름:
  KeyGen():
    (A, t) = 공개키   -- A: 공개 행렬, t = As + e (mod q)
    s = 비밀키         -- 작은 계수 벡터

  Encaps(pk):
    r ← 랜덤
    (u, v) = 암호문    -- u = A^T·r + e₁, v = t^T·r + e₂ + ⌈q/2⌋·m
    K = 공유 비밀 (256비트)

  Decaps(sk, ct):
    m' = v - s^T·u     -- 오차 제거 → 메시지 복원
    K = 공유 비밀 (동일)

ML-KEM-768 파라미터: n=256, k=3, q=3329
  공개키: 1184 바이트, 암호문: 1088 바이트, 공유 비밀: 32 바이트

/* include/crypto/kem.h — KEM API 구조 (향후 커널 통합 시 예상 패턴) */
/* 현재 커널에는 akcipher(비대칭 암호) API가 존재하며,           */
/* ML-KEM 통합 시 아래와 유사한 KEM 전용 인터페이스가 추가될 것입니다 */
struct kem_alg {
    int (*generate_keypair)(struct crypto_kem *tfm,
                           u8 *pk, unsigned int *pk_len,
                           u8 *sk, unsigned int *sk_len);
    int (*encapsulate)(struct crypto_kem *tfm,
                       const u8 *pk, unsigned int pk_len,
                       u8 *ct, unsigned int *ct_len,
                       u8 *ss, unsigned int *ss_len);
    int (*decapsulate)(struct crypto_kem *tfm,
                       const u8 *sk, unsigned int sk_len,
                       const u8 *ct, unsigned int ct_len,
                       u8 *ss, unsigned int *ss_len);
    unsigned int pk_size;    /* ML-KEM-768: 1184 */
    unsigned int sk_size;    /* ML-KEM-768: 2400 */
    unsigned int ct_size;    /* ML-KEM-768: 1088 */
    unsigned int ss_size;    /* 공유 비밀:     32 */
    struct crypto_alg base;
};

/* crypto/testmgr.h — ML-KEM KAT 벡터 구조 (FIPS 203 기반 예시) */
struct kem_testvec {
    const u8 *seed;        /* d || z: 키 생성 시드 (64바이트) */
    const u8 *pk;          /* 기대 공개키 */
    const u8 *sk;          /* 기대 비밀키 */
    const u8 *ct;          /* 기대 암호문 */
    const u8 *ss;          /* 기대 공유 비밀 (32바이트) */
    const u8 *encaps_msg;  /* 캡슐화 난수 입력 (32바이트) */
    unsigned int pk_len;
    unsigned int sk_len;
    unsigned int ct_len;
};

/* NIST ACVP (Automated Cryptographic Validation Protocol) 테스트 벡터로 검증 */
/* 각 벡터는 seed → KeyGen → pk/sk 비교, msg → Encaps → ct/ss 비교,       */
/* sk + ct → Decaps → ss 일치를 확인합니다                                  */

ML-DSA 서명/검증 흐름 (Fiat-Shamir with Aborts):
  KeyGen():
    (A, t) = 공개키     -- A: 공개 행렬, t = As₁ + s₂ (mod q)
    (s₁, s₂) = 비밀키   -- 작은 계수 벡터 쌍

  Sign(sk, msg):
    loop:                -- Aborts: 조건 불충족 시 반복
      y ← 균일 분포 샘플링
      w₁ = HighBits(Ay)         -- 커밋먼트 상위 비트
      c = H(w₁ || msg)          -- 도전값 (해시)
      z = y + c·s₁              -- 응답 벡터
      if ‖z‖∞ ≥ γ₁-β: restart  -- 비밀키 누출 방지 검사
      if ‖LowBits(Ay-c·s₂)‖∞ ≥ γ₂-β: restart
    return σ = (c̃, z, h)

  Verify(pk, msg, σ):
    w'₁ = UseHint(h, Az - ct)   -- 커밋먼트 복원
    c' = H(w'₁ || msg)          -- 도전값 재계산
    return c' == c̃ AND ‖z‖∞ < γ₁-β

ML-DSA-65 파라미터: k=6, l=5, q=8380417, γ₁=2¹⁹
  공개키: 1952B, 서명: 3293B, 비밀키: 4032B (NIST 보안 수준 3)

/* 하이브리드 KDF 결합 패턴 — X25519 + ML-KEM-768 */
/* TLS 1.3 스타일: 두 공유 비밀을 연결 후 HKDF로 키 유도 */
static int hybrid_derive_secret(u8 *session_key,
                                 const u8 *x25519_ss, size_t x25519_len,
                                 const u8 *mlkem_ss, size_t mlkem_len)
{
    u8 combined[64]; /* 32(X25519) + 32(ML-KEM) */
    struct crypto_shash *hmac;
    int err;

    /* 두 공유 비밀을 순서대로 연결 */
    memcpy(combined, x25519_ss, x25519_len);          /* SS₁ */
    memcpy(combined + x25519_len, mlkem_ss, mlkem_len); /* SS₂ */

    /* HKDF-SHA-256으로 세션 키 유도 */
    hmac = crypto_alloc_shash("hmac(sha256)", 0, 0);
    if (IS_ERR(hmac))
        return PTR_ERR(hmac);

    err = hkdf_extract(hmac, combined, sizeof(combined),
                        salt, salt_len, session_key);
    crypto_free_shash(hmac);
    memzero_explicit(combined, sizeof(combined));
    return err;
}

/* crypto/testmgr.c — 셀프테스트 구조체 (AES-GCM 예시) */
static const struct aead_testvec aes_gcm_tv[] = {
    { /* NIST SP 800-38D 테스트 벡터 */
        .key    = "\xfe\xff\xe9\x92\x86\x65\x73\x1c"
                  "\x6d\x6a\x8f\x94\x67\x30\x83\x08",
        .klen   = 16,
        .iv     = "\xca\xfe\xba\xbe\xfa\xce\xdb\xad"
                  "\xde\xca\xf8\x88",
        .input  = "\xd9\x31\x32\x25\xf8\x84\x06\xe5"
                  /* ... 평문 데이터 ... */,
        .result = "\x42\x83\x1e\xc2\x21\x77\x74\x24"
                  /* ... 기대 암호문+태그 ... */,
    },
    /* ... 추가 테스트 벡터들 ... */
};

/* 테스트 실행: alg_test("gcm(aes)", ...) */
/* 1. 키 설정 → 2. 암호화 → 3. 결과 비교 → 4. 복호화 → 5. 역검증 */
/* 한 벡터라도 불일치하면 WARN_ONCE() + 알고리즘 등록 거부 */

/* crypto/testmgr.c — FIPS 모드 테스트 강제 */
static int alg_test(const char *driver, const char *alg,
                    u32 type, u32 mask)
{
    int i = alg_find_test(alg);  /* 테스트 벡터 검색 */

    if (i < 0) {
        if (fips_enabled) {
            /* FIPS 모드: 테스트 벡터 없는 알고리즘 사용 금지 */
            pr_err("alg: %s has no test vectors in FIPS mode\n", alg);
            return -EINVAL;
        }
        return 0;  /* 비FIPS: 테스트 없이 통과 */
    }

    return alg_test_descs[i].test(alg_test_descs + i, driver, type, mask);
}