AES 암호화 알고리즘에서 가장 이해하기 어려운 부분이 있습니다. 바로 MixColumns 과정입니다. 찾아보니 AES 알고리즘에 대해 설명할 때 보통 이 과정에서 필요한 Matrix 값만 알려주고 넘어갔으며, 이 값이 쓰이는 행렬의 곱(Matrix multiplication) 과정은 설명하지 않았습니다. 이 부분을 이해하는데 대부분 해외 자료들을 사용하였습니다. 설명에 앞서 AES MixColumns에서의 행렬의 곱과 선형대수(linear algebra)에서의 행렬의 곱과는 큰 틀은 같지만 세부 계산에서 차이가 있습니다.
Matrix multiplication 계산에 대해 모르시는 분들은 위의 그림을 보고 이해하시면 됩니다. 우리가 하는 MixColumns 계산도 큰 틀은 위의 그림과 같기 때문에 똑같은 방식으로 큰 틀은 계산 하시면 됩니다. ( 이해가 안가시는 분은 Matrix multiplication 을 검색하시면 됩니다. ) 문제는 위의 그림에서 0 x a11, 0 x a12, ... 과 같은 세부과정이 일반계산과 다릅니다.
MixColumns Process pdf (1)
MixColumns Process pdf (2)
- MixColumns에서 곱셈은 왼쪽 방향 쉬프트 연산으로 대체합니다. ( 2의 차수를 비트 수로 )
- 곱셈을 할 때 입력값의 msb(최상위 비트)의 값이 1일 때 왼쪽 방향으로 특정 비트 값 만큼 쉬프트 연산을 한 뒤, xor 0001 1011 연산을 해줍니다.
- 덧셈은 xor 연산으로 대체합니다.
MixColumns 과정에서 세부적인 계산을 할 때 위의 세 가지만 명심하시면 됩니다. 이해할 때 참고하였던 두 pdf를 올려두었습니다. 첫 번째 pdf로 설명을 해보겠습니다.
다음과 같이 있을 때 { 04 = (02 x d4) + (03 x bf) + (01 x 5d) + (01 x 30) } 입니다. 먼저 (02 x d4)를 계산하겠습니다.
16진수를 계산을 위해 2진수로 고쳐줍니다. 여기에 2를 곱하므로 왼쪽으로 1비트만큼 쉬프트 연산을 해줘야 함을 알 수 있습니다.
다음 그림을 보면 곱셈을 왜 왼쪽 쉬프트 연산으로 표현할 수 있는지 알 수 있습니다. ( 만약 3과 같은 홀수를 곱해야 할 경우는 ( 2 + 1 )로 바꿔서 연산 할 수 있습니다. ) d4의 2진수를 보면 msb의 값이 1임을 알 수 있습니다. 앞에서 설명했다시피 msb의 값이 1이므로 왼쪽 쉬프트 연산을 한 후 0001 1011 xor 연산을 해줘야 합니다. 왜냐하면 d4의 상태 ( msb의 값이 1인 상태 )에서 왼쪽으로 1만큼 쉬프트 연산을 할 경우 110101000(9비트가 되므로), 8비트 안에 값을 다 표현하지 못하게 됩니다. (msb에 1이라는 값이 있었으므로 9비트 자리로 가서 1이 잘려버림) 즉 8비트를 초과하게 되는 것 입니다. 이때 8비트인 GF(2^8)에서 사용하는 1과 본인 외에 나누어지지 않는 기약방정식(irreducible polynomial)으로 모듈러 연산을 하게 됩니다. GF(2^8) 일 때 사용하는 기약 방정식은 다음과 같습니다.
다음의 그림을 부분만 참고해서 잠깐 예시를 들면 1000 0001 ( x^7 + 1 그림으로 따지면 x^7 + x^-1 이 되어야 하지만 x^-1이 있을경우 더러워지므로)에서 2를 곱해야 하는 상황이라 생각해봅시다. 바이너리에서 2는 자릿수 하나이므로 곱하면 1 0000 0010 (x^8 + x)가 되어버립니다. 8비트 (x^7이 최대차수)를 초과해버렸으므로 GF(2^8)에서 기약 다항식인 1 0001 1011 (x^8 + x^4 + x^3 + x + 1)으로 모듈러 연산을 하면 0001 1001 (x^4 + x^3 + 1)이 됩니다. 그러나 이 값은 0000 0010 (x^8 + x 에서 8비트 초과 항은 제거한 x)에서 0001 1011 (기약 다항식에서 초과항을 제거한 x^4 + x^3 + x + 1)을 xor 한 값과 결과가 같습니다. 따라서 8비트를 초과할 경우 0001 1011을 xor 해주는 것 입니다. 따라서 덧셈을 xor로 표현할 수 있다는 것 또한 설명할 수 있습니다. 다시 pdf의 예시로 돌아갑니다.
따라서 위의 그림과 같이 (02 x d4) = 1011 0011이 됩니다.
다음은 (03 x bf)입니다. bf를 계산을 위해 2진수 바이너리로 변환해줍니다.
03 = ( 2 + 1 )이므로 덧셈은 xor로 변환 가능하므로 10 xor 01이 됩니다. 이제 (03 x bf) 연산을 해주겠습니다.
결과 값이 1101 1010 임을 알 수 있습니다. 이제 { 04 = (02 x d4) + (03 x bf) + (01 x 5d) + (01 x 30) } 이 식 중에 (01 x 5d) + (01 x 30) 이 부분만 남았습니다. 5d와 30을 2진수로 나타내줍니다.
10진수든 2진수든 1을 곱하면 자신이 되므로 더 이상의 계산은 필요가 없습니다. 이제 4개의 값들을 더해서 04가 나오는지 확인만 해주면 됩니다.
다음과 같이 구한 4개의 값들을 더하면 04가 나옵니다.
따라서 다음의 66, 81, e5도 앞의 계산들과 같은 방식으로 해주면 값을 구할 수 있습니다. AES 암호화 알고리즘에서 MixColumns 과정을 자세하게 알아보았습니다. 더 자세하게는 아까 GF(2^8)에서 갈루아 필드, 유한체와 같은 수학적 배경지식이 필요합니다. 수학적 배경지식과 전반적으로 이해하는데 있어서 pdf 외에 참고했던 사이트들을 걸어놓겠습니다. 더 궁금하신 분들은 참고하시는 것도 좋습니다.
http://www.ktword.co.kr/test/view/view.php?m_temp1=3857
유한체
Finite Field, Galois Field, Galois Finite Field 유한체, 갈로아체, 갈로이스체, 갈로아 유한체(2023-10-21)
www.ktword.co.kr
https://stackoverflow.com/questions/66897660/questions-about-aes-irreducible-polynomials
questions about AES irreducible polynomials
For galois field GF(2^8), the polynomial's format is a7x^7+a6x^6+...+a0. For AES, the irreducible polynomial is x^8+x^4+x^3+x+1. Apparently, the max power in GF(2^8) is x^7, but why the max power of
stackoverflow.com
'security > crypto' 카테고리의 다른 글
| [Dreamhack] Basic_Crypto1 풀이 (0) | 2023.11.11 |
|---|---|
| [Dreamhack] Textbook-DH 풀이 (0) | 2023.11.10 |
| [암호학 이론] AES 암호화 알고리즘 (0) | 2023.11.03 |
| [암호학 이론] Feistel cipher (1) | 2023.11.01 |
| [암호학 이론] DES 암호화 알고리즘 (0) | 2023.10.31 |
