아이고
MixClumns를 계산하다가 얼굴이 시뻘게지는 경험을 하고 다시는 잊지 않고자 정리한다.
AES란 128비트, 192비트, 256비트 등 가변 길이의 키를 사용가능한 대칭키 알고리즘이다.
지금까지 알려진 모든 공격법에 대해 안전하고 효율적이라고 한다.
AES알고리즘의 작동법은 다음의 수상한 exe파일을 다운받아 볼 수 있다.
절대 악성파일이 아니나..... 찝찝하신 분들은 안받으시면 되겠다. 이 말을 해서 더 찝찝한것같긴 하지만,,,
내가 정리한 바로는 이런 식이다.
여기서 우리는 128비트의 키길이를 사용할 것이므로, For문 내부를 9번 반복을 하게된다.
나머지 1번은 MixColumn을 제외한 Sub Byte, Shift Row, Add Round키를 수행하며 도합 (9+1)번 수행한다.
참고로 192bit는 12번, 256bit는 14번 반복한다고 한다.
SubByte나 ShiftRow는 각각 대체하거나 왼쪽 쉬프트를 하는 것이라 이해가 바로 되는데,
MixColumn부분을 아~~ 행렬곱하면 되겠구나~~하고 계산을 해보면... 본인처럼 카페에서 2시간동안 비트연산을 하게 될 것이다. 정답은 하나도 맞지 않는..
그래서!! MixColumn을 정리하려고 한다.
https://www.angelfire.com/biz7/atleast/mix_columns.pdf
이 월런공 공대에 다니는 학생의 과제를 보고 정리한 글이다!!
Thankyou, Kit Choy Xintong.
남의 과제를 보고 이해할 수 있는 세상에 태어나 행복하다!
우선, 아까 공유했던 exe파일의 MixColumn예시는 다음과 같다.
다운받아서 실행해보면 아시겠지만, 엄청 얼렁뚱땅 넘어간다.
우선 미리 알아야 할 대전제는,
AES알고리즘에서 덧셈은 XOR로 대체된다는 것이다.
MixColumn은 기본적으로 행렬 연산을 한다고 했다.
그러면, 다음 계산을 해야 04가 나올 것이다.
(앞에 0x를 붙인 수는 16진수란 표기다! 예를 들어, 0x30은 16진수로 30이다.)
(0xD4 * 2) ⊕ (0xBF * 3) ⊕ (0x5D * 1) ⊕ (0x30 * 1)
계산기를 꺼내 프로그래머용으로 바꾸고...
똑딱똑딱하면...답이 04가 안된다!!!!!
이는 특별한 연산법이 있기 때문이다.
각 괄호마다 계산을 천천히 해보자~!!
1. (0xD4 * 2) 계산 하기
우선 계산에 앞서, 우리는 16진수의 0xD4를 2진수로 변환할 것이다.
이유는 나중에 XOR연산을 쉽게 하기 위해서이다.
D4 = 1101 0100
이제 우리는 8비트의 2진수를 얻었다. 그럼 이제 2를 곱해주기만 하면 된다.
2진수 연산에서 2를 곱하는 것은 Left Shift 1을 해주면 되므로 이 괄호는 계산이 끝난다!
는 뻥이다. 그렇게 간단하지 않다.
2로 곱하기 전 최상위 왼쪽 비트가 1인 경우, 0001 1011을 XOR연산해줘야 한다.
중요하니깐 한번 더 써야징
~2로 곱할때만 적용~
2로 곱하기 전(그러니까 왼쪽 쉬프트 1을 하기 전)의 최상위 왼쪽 비트가 1이라면,
(1) 왼쪽 Shift를 해주고,
(2) 0001 1011을 XOR연산 해주어야 한다!
아니 왜 하필 0001 1011이지?? 검색해보았지만 명쾌한 답은 없었다... 궁금하신 분은 더보기를 클릭해주세요.
일단 이 과제를 수행한 학생은 책에서 그렇게 써있다고 했고...
비슷한 의문을 가진 사람이 질문했던 글이 이곳에 있다.
https://security.stackexchange.com/questions/57253/how-to-do-rijndael-mixcolumns-step
How to do Rijndael MixColumns step
I am trying to go through all of the the steps in the Rijndael Encryption Algorithm using pencil and paper. I have been using http://www.formaestudio.com/rijndaelinspector/archivos/
security.stackexchange.com
답변자는 GF(2^m)과 관련있어보인다고 했다.
음 일단 끄덕하고 넘어가도록 한다.
나중에 이해되는 것도 있으니까!
나중에 이해된다면 다시 정리하도록 하겠다.
다시 계산으로 돌아가면, 다음과 같이 계산할 수 있겠다.
0xDF * 2 = 1101 0100 << 1
= 1010 1000 XOR 0001 1011
= 1011 0011(정답)
XOR계산이 헷갈리시는 분을 위해 다시 정리하자면,
1이 홀수개일때 답이 1인 계산이라고 생각하면 편하다.
1010 1000
0001 1011(XOR)
-----------------------
1011 0011
2. (0xBF * 3)계산하기
0XBF를 아까 했던 것 처럼, 2진수로 변환하자.
0xBF = 1011 1111
이번에는 3을 곱해줘야 한다. 3을 곧바로 곱해주면 될 것 같지만.. 우리는 덧셈을 할 때 XOR연산을 적용중이고, 3을 바로 곱해버리면 AES세계관에 문제가 생긴다.
3을 2진수 형식으로 바꾸어주자.
3 = 11(2)
= 10 XOR 01
이제 계산할 수 있겠다.
0xBF * 3 = {1011 1111} * {10 XOR 01}
= {1011 1111 * 10} XOR {1011 1111 * 01}
= {1011 1111 * 10} XOR {1011 1111}
={0111 1110 XOR 0001 1011} XOR {1011 1111}
={0110 0101} XOR {1011 1111}
=1101 1010(정답)
※이 색깔 부분이 이해되지 않으신 분은 [1. 0xD4 *2 계산하기] 부분 참고
3. (0x5D * 1) 와 (0x30 * 1) 계산.
이 부분은 1을 곱하는 부분이므로, 각각 2진수 변환만 해주면 되겠다.
0x5D = 0101 1101
0x30 = 0011 0000
4. 이제 계산!
앞서 1~3번에서 우리가 XOR할 연산을 구했다. 그러면 XOR을 해서 답인 04가 나오나 보자!
1011 0011
1101 1010
0101 1101
0011 0000 (XOR) <-XOR연산은 1이 홀수개일 경우 1
--------------------
0000 0100
= 04(16진수로 변환시)
우리가 원했던 04를 얻을 수 있었다.
그럼, MixColumn정리 끄읕~~!!!
아 시원~~하다!!
'내가 배운 것들' 카테고리의 다른 글
| [SSL 보안을 알아보자] 1. 대칭키와 비대칭키 암호화 (0) | 2023.03.10 |
|---|---|
| [JAVA&OOP] 1~2강. 자바의 쓰임새와 객체에 대해서 (0) | 2021.03.03 |
