매일 쓰는 AES, 그 안을 들여다본 적 있나요?
HTTPS로 웹사이트에 접속할 때, 노트북 디스크를 암호화할 때, 와이파이에 접속할 때, 이 모든 순간에 AES(Advanced Encryption Standard)가 일하고 있어요. 2001년 미국 표준으로 채택된 이후 사실상 전 세계 대칭키 암호의 표준이 됐죠.
그런데 우리는 보통 라이브러리 함수 한 줄로 AES를 쓰고 끝내요. 알래스카 페어뱅크스 대학(UAF)의 컴퓨터 보안 강의 노트가 그 안쪽을 깔끔하게 정리하고 있는데, 핵심은 갈루아 체(Galois Field, 유한체)라는 수학이에요. 이름은 무섭지만 개발자에게 익숙한 비트 연산으로 풀어보면 의외로 친근하거든요.
유한체가 뭐냐면: 닫힌 세계의 사칙연산
유한체는 원소 개수가 정해져 있고, 그 안에서 사칙연산을 해도 결과가 항상 그 세계 안에 머무는 수 체계예요. 가장 쉬운 예가 시계 산수예요. 7로 나눈 나머지만 쓰는 세계라면 5 + 4 = 2가 되죠. 7 같은 소수로 나눈 나머지 세계에서는 0이 아닌 모든 수가 나눗셈 역원을 가져서 깔끔한 체가 돼요.
문제는 컴퓨터의 기본 단위인 1바이트가 256개 값이라는 점이에요. 256은 소수가 아니라서 그냥 mod 256을 쓰면 2 × 128 = 0이 되어버리고, 2로 나누는 연산이 정의되지 않아요. 암호에 쓰기엔 구멍이 생기는 거죠.
해결책: 바이트를 다항식으로 보기
그래서 등장하는 게 GF(2⁸)예요. 발상의 전환은 바이트를 숫자가 아니라 다항식으로 보는 것이에요. 예를 들어 0x57은 이진수로 01010111이니까 각 비트를 계수로 삼아 x⁶ + x⁴ + x² + x + 1로 봐요. 계수는 0 아니면 1이고, 계수끼리는 mod 2로 계산해요.
이렇게 보면 덧셈은 그냥 XOR이 돼요. 1 + 1 = 0이라 자리올림이 없거든요. 재밌는 건 빼기도 XOR이라는 점이에요. 더하기와 빼기가 같은 연산인 세계죠.
곱셈은 다항식끼리 곱한 뒤, 차수가 8 이상으로 넘어가면 AES가 정한 다항식 x⁸ + x⁴ + x³ + x + 1(16진수로 0x11B)로 나눈 나머지를 취해요. 이 다항식은 더 이상 인수분해되지 않는 '기약다항식'으로, 정수 세계의 소수 역할을 해요. 덕분에 0이 아닌 모든 바이트가 곱셈 역원을 갖게 돼요.
코드로 보면 더 쉬워요: xtime
구현에서는 'x를 곱하는 연산', 즉 2를 곱하는 xtime이 핵심 빌딩 블록이에요.
uint8_t xtime(uint8_t b) { return (b << 1) ^ ((b & 0x80) ? 0x1B : 0x00); }
왼쪽으로 한 칸 시프트해서 x를 곱하고, 원래 최상위 비트가 1이었다면 차수가 8로 넘친 거니까 0x1B를 XOR해서 나머지를 맞춰줘요. 다른 곱셈은 이걸 조합하면 돼요. AES 표준 문서(FIPS-197)에 나오는 0x57 × 0x13을 계산해볼게요.
0x57 × 0x02 = 0xAE0x57 × 0x04 = 0x47(넘침 발생, 0x1B를 XOR)0x57 × 0x08 = 0x8E0x57 × 0x10 = 0x07(다시 넘침)- 0x13 = 0x10 ⊕ 0x02 ⊕ 0x01이니까, 결과는
0x07 ⊕ 0xAE ⊕ 0x57 = 0xFE
AES에서 갈루아 체가 쓰이는 곳
AES는 16바이트 블록을 4×4 행렬로 놓고 SubBytes, ShiftRows, MixColumns, AddRoundKey 네 단계를 키 길이에 따라 10·12·14라운드 반복해요. 이 중 세 곳에 갈루아 체가 들어가요.
SubBytes(S-box): 각 바이트를 GF(2⁸)의 곱셈 역원으로 바꾼 뒤 아핀 변환을 한 번 더 거쳐요. 역원 함수는 입출력 관계가 극도로 비선형적이라 선형·차분 공격 같은 수학적 공격을 막아주는 핵심 장치예요. 0은 역원이 없으니 0으로 두는데, 그래서 S-box(0x00) = 0x63이 나와요.
MixColumns: 각 열의 4바이트를 고정 행렬과 GF(2⁸)에서 곱해요. 행렬 원소가 01, 02, 03뿐이라 ×2는 xtime(b), ×3은 xtime(b) ^ b로 끝나요. 한 바이트만 바뀌어도 열 전체가 바뀌게 만드는 '확산' 역할이에요.
AddRoundKey와 키 스케줄: 라운드 키를 섞는 XOR은 GF 덧셈 그 자체고, 키 확장에 쓰는 라운드 상수(01, 02, 04, …, 80, 1B, 36)도 x의 거듭제곱이에요. 80 다음이 100이 아니라 1B인 이유, 이제 보이시죠?
실무에서 알아둘 포인트
첫째, 직접 구현해서 프로덕션에 쓰지 마세요. 교과서처럼 S-box를 테이블 룩업으로 구현하면 CPU 캐시 접근 패턴으로 키가 새는 캐시 타이밍 공격에 취약해요. 요즘 CPU에는 AES-NI나 ARM Crypto Extension 같은 전용 명령어가 있으니 검증된 라이브러리를 쓰는 게 정답이에요.
둘째, 갈루아 체는 AES에서 끝나지 않아요. AES-GCM 모드의 인증 태그는 GF(2¹²⁸) 곱셈으로 계산되고, QR코드와 RAID-6의 리드-솔로몬 오류정정도 GF(2⁸)를 써요. 단, 이쪽은 기약다항식으로 0x11D를 쓴다는 차이가 있어요.
셋째, 공공 프로젝트를 하는 한국 개발자라면 국산 표준 암호 ARIA도 만나게 될 거예요. ARIA 역시 AES와 같은 SPN 구조에 GF(2⁸) 역원 기반 S-box를 쓰기 때문에, AES를 이해하면 ARIA 명세도 훨씬 수월하게 읽혀요. 손으로 직접 부딪혀보고 싶다면 cryptopals 챌린지를 추천해요.
마무리
핵심 한 줄: AES의 안전성은 '바이트를 다항식으로 보는' 갈루아 체 수학 위에 서 있고, 그 연산은 결국 시프트와 XOR이에요.
여러분은 암호 알고리즘의 내부 원리를 어디까지 알아야 한다고 생각하세요? 라이브러리만 잘 쓰면 충분할까요, 아니면 이런 기초 지식이 실무에서 도움이 된 경험이 있으신가요?
🔗 출처: Hacker News