요약
AES 암호는 원소가 256개인 유한체 GF(2⁸)의 덧셈과 곱셈 위에 세워져 있습니다.
알래스카 페어뱅크스 대학교의 롤러 교수가 2015년 봄학기 암호학 강의용으로 쓴 노트입니다. 갈루아 유한체(원소 수가 유한한 수 체계)를 바이트 연산으로 풀어 설명하고, 그것이 AES의 각 단계에 어떻게 쓰이는지 보여 줍니다.
왜 중요한가
- 추상대수 개념을 XOR와 비트 시프트 몇 줄로 옮겨, AES가 바이트 단위로 깔끔하게 돌아가는 이유를 보여 줍니다.
- 덧셈과 곱셈만 쓰면 선형 암호에 그친다는 점을 들어, 나눗셈과 행 뒤섞기를 함께 쓰는 설계 의도를 설명합니다.
핵심 내용
- GF(2⁸)에서는 덧셈과 뺄셈이 모두 XOR입니다. 자리올림이 없어 결과가 늘 1바이트 안에 머뭅니다.
- 곱셈은 다항식 곱셈으로 하고, 넘치는 차수는 AES가 정한 기약다항식 0x11b로 줄입니다.
- 나눗셈은 계산이 어려워, 원소가 256개뿐인 점을 이용해 역원 표나 로그 표를 미리 만들어 씁니다.
- AES 한 라운드는 SubBytes(역원을 이용한 바이트 치환), ShiftRows(행 회전), MixColumns(열 섞기), AddRoundKey(키 XOR)로 이뤄집니다.
- 유한체를 쓰는 이유로 값의 크기 유지, 모든 연산의 역연산 존재, 1830년대부터 다져진 수학을 꼽습니다.
HN 반응
- 요즘 AES는 주로 CTR 모드(키스트림을 만들어 XOR하는 방식)로 써서 복호화에 역연산이 필요 없다는 지적에, 다른 용도도 많다는 반론이 붙었습니다.
- 예전에는 표 조회로 AES를 구현했지만, 타이밍 공격(실행 시간 차로 키를 캐는 공격)이 알려진 뒤 CPU에 AES 전용 명령이 생겼다는 보충도 있었습니다.
다만 요즘 AES 사용 방식에서는 이 특성이 사실상 중요하지 않다는 점은 짚어 둘 만합니다. 블록 암호를 CTR 모드로 쓰기 때문입니다. CTR에서는 블록 암호로 긴 키스트림 바이트(거의 일회용 패드 키나 다름없습니다)를 만들고, 이 키스트림을 평문과 XOR해서 암호문을 얻습니다. 암호문에서 평문으로 되돌릴 때도 같은 키스트림으로 똑같은 XOR 연산을 하면 되므로, AES 역연산은 필요 없습니다.
AES는 CTR 모드 암호화 말고도 훨씬 다양한 곳에 쓰입니다.
아니요, 안 그래요. AES는 사실상 AES-CTR, AES-GCM, AES-CTR-DRBG에만 쓰이거든요. FAEST가 표준화되면 또 모르겠지만요?
와, 제 대학 교수님 중 한 분이네요! GF2^8은 RAID6 이상이나 리드 솔로몬 부호에도 아주 유용합니다.
예전에는 이 사이트의 곱셈표처럼 MixColumns와 SubBytes 계산용 AES 룩업 테이블을 만드는 게 현실적인 방법이었습니다. 그러다 djb가 원격 타이밍 공격을 찾아냈고, 그래서 프로세서들이 하드웨어 AES 명령어를 구현하기 시작했습니다.
저도 HN 첫 페이지에서
uaf.edu링크를 보고 반가웠는데, 글쓴이가 로러 박사님이라는 걸 알고는 더 반가웠어요. 그분의 x86 어셈블리 수업은 제가 대학에서 들은 수업 중 단연 손꼽히게 좋았습니다.차수가 n 미만(최대 n−1)인 다항식과 동등해야 하지 않나요?
이 글이 인기를 끄는 건 이 분야에서 최근에 수학적 발견이 있었기 때문인가요?
다항식과 동등하다는 게 "이상하다"는 말이 맞나 싶은데요. 애초에 갈루아가 하려던 일이 바로 그거 아니었나요? 고차 다항식의 해석적 풀이가 불가능하다는 것이나 정칠각형을 작도할 수 없다는 것 같은, 다항식에 관한 사실을 증명하는 일 말이에요.
저는 "weirdly"를 "뜻밖에도"로 읽었어요. 그러니까 "예상하지 못했겠지만 그래도 사실이고, 그 뒤에는 깊은 이론이 있다"는 뜻으로요.
조금은 그렇죠. 똑같지는 않지만 어느 정도는 그렇다고 쓴 댓글을 지웠는데, 그 관계를 직접 알아내는 일은 정말 보람 있어요.