-
블록암호: AESDreamHack/암호학 2024. 2. 22. 23:28
AES는 아직까지는 취약점이 드라나지 않았다고 한다.
네트워크 패킷이 오가는 WLAN에서도 데이터를 암호화 할때
암호화 모드가 TKIP, AES, TKIP&AES 3가지를 현재 사용하기도 하므로
알아둬야한다.
다음 포스팅은 추가적으로 TKIP에 대해서 해야겠다.
이전에 설명한 DES와 달리 AES는 페이스텔 구조가 아닌 SPN 구조를 갖게 된다.
페이스텔은 평서문을 2개의 L과 R로 나눈 후에 R에만 라운드 함수를 적용시켰지만,
SPN 구조는 평서문을 여러개의 단위로 나눈 후 나눠진 각 단위에 모두 라운드 함수를 적용시킨다.
추가적으로 P-Box를 더하여
S-Box로 값을 치환
P-Box로 값을 전치하게 된다.
https://skogkatt.tistory.com/entry/P-Box-S-Box
P-Box, S-Box
P-Box 문자의 자리를 변경하는 전치 암호 장치 단순(Straight) , 축소(Compression), 확장(Expansion) 세 방식이 존재한다. Straight P-Box 입력받은 데이터의 순서를 바꿔 똑같은 길이의 데이터로 변환하는 가장
skogkatt.tistory.com
P-Box는 종류가 3가지인데
1대1 대응하는 Straight P-Box
N대1 대응하는 Compression P-Box
1대N 대응하는 Expansion P-Box가 있다.
드림핵에 나온 SPN 구조는 Straight P-Box로 보인다.
아마 P-Box의 종류는 ⊕ (XOR) 연산에 의해서
K(키 값) = S-Box 이후의 값 이면 Straight P-Box
K(키 값) < S-Box 이후의 값 이면 Compression P-Box
K(키 값) > S-Box 이후의 값 이면 Expansion P-Box 가 되는듯하다.
( ⊕ (XOR) 연산하려면 K(키 값)과 같게 맞춰줘야하니까)
DES는 64비트 크기의 평서문을 암호화하는 알고리즘이지만AES는 128비트 크기의 평서문을 암호화하는 알고리즘이다.추가적으로 다른 점은 키의 길이에 따라서 라운드 수가 달라진다는 것이다.
키의 길이 라운드 수 128비트 192비트 256비트 10 12 14 DES의 특징은
● 평서문을 64비트의 블록단위로 취급
● 32비트 블록을 2개로 나누어
● 8바이트(64비트)의 비밀키 중 패러티 비트를 제외한 56비트의 값을 이용하여 16개의 48비트의 키를 만들어서
● 16번의 라운드를 거쳐서 암호화하였지만
AES는
● 평서문을 128비트의 블록단위로 취급
● 128비트의 블록을 여러개로 나누고
● 128비트,192비트, 256비트 크기의 비밀키를 통해서
● 10, 12, 14번의 라운드를 거쳐서 암호화한다.
AES128을 기준으로 해보자
1. 평서문을 상태 배열화
입력 1F3CF203B211C5AA6EB27A45E4D98130 은 총 16바이트(128비트) 인 평서문이다.
이를 상태 배열로 구성해주면
요런식으로 나온다. 이후에는
AddRoundKey 함수 1회 이후
SubBytes 함수
ShiftRows 함수
MixColumns 함수
AddRoundKey 함수
4개의 함수를 1개의 라운드로 취급하여 적용한다.
※ 드림핵과 병행해서 보질 않겠다. 순서를 드림핵과는 다르게 진행해서 설명하려고한다.
2. AddRoundKey 함수
사진에서 AddRoundKey 함수를 먼저 진행시키므로 무슨 함수인지 확인을 해야한다.
사실 되게 간단하다.
상태 배열(16bytes)를 키(16bytes)와 ⊕(XOR) 연산해준다.
0x63 ⊕ 0x21
0110 0011
0010 0001 을 XOR 연산하게 되면
0100 0010 (0x42) 값이 나온다. ㅇㅇ
근데 궁금한 점은 라운드마다 키 값이 어떻게 나오냐는거다.
2-1. Key Schedule
처음에 나온 키 값이 드림핵에서 나온 예시대로라고한다면,
2B 28 AB 09 7E AE F7 CF 15 D2 15 4F 16 A6 88 3C 이렇게 생겼다고 치자.
이 중에 1개의 열을 기준으로 나눌 수 있다.
2B 7E 15 16 을 w0 (0번째 열)이라고 할 수 있다.
전체적인 AES 알고리즘 과정 중에 Key schedule 과정을 끼워넣은 그림은 이러하다.
그림이 난잡해서 미안하다. 위는 평서문을 상태배열화 -> Addround Key -> [Subbytes -> ShiftRows -> Mixcolums -> AddroundKeys] -> .... 과정이고,
아래는 Addround Key 과정에서 쓰이는 키 값을 조정하는 Key schedule 과정이다.
그림처럼 Key schedule 과정은 Rotword -> Subword -> Rcon 과정을 거쳐서 다음 라운드에 쓰일 키를 만들어낸다.
(아 그리고 키 값은 예시를 들기위해서 쉽게 만들었지만 이제부터 과정을 연산할 때는 위에서 말한 것처럼 드림핵의 키 값을 사용할 것이다.)
이제 제대로 설명하겠다.
더보기
일단 (i >= 4) 이라는 정수 i에 대해서
Wi = Rcon(Subword(Rotword(Wi-1))) ⊕ Wi-4 이다.
i 값을 4라고 설정하고 구해보도록하자.
W4 = Rcon(Subword(Rotword(W3))) ⊕ W0
이렇게 나온다.
먼저 W3 값은 위에서 나왔듯이
09 CF 4F 3C 2-1-1. Rotword
Rotword는 단순하게 위로 순환 시프트 연산을 이행하는 것이다.
위의 W3 값을 이용해 Rotword(W3) 값은 이렇게 나오게된다.
CF 4F 3C 09 2-1-2. Subword
Subword는 앞서 사용했던 S-Box를 이용해서 치환을 진행해준다.
위의 값은 아래의 S-Box를 통해서
이렇게 치환될 것이다.
8A 84 EB 01 여기서 사용되는 S-Box는 레달 S-Box라고 불리우며,
GF(갈루아 필드) 라는 유한체로 표현한 것인데,
이거 이해해보려고 노력하고, 이대 수학과인 채린이한테도 물어보고 했지만...
너무 알아야할게 많음
추상대수학을 공부해야해서 AES 중 Mixcolum 과정도 그렇고 그냥 넘어가야한다.
나중에 Mixcolum 과정에서 0x1B 연산이 이해안되더라도 그런가보다하고 넘어가야한다...
여기까지의 값은 Subword(Rotword(W3)) 이다.
2-1-3. Rcon
Rcon은
R이라는 집합 값에서 R[i/4 - 1] 값을 골라서 여태까지의 값의 최상단 값과 XOR하는 과정인데,
R = [01, 02, 04, 08, 10, 20, 40, 80, 1B, 36] 이다.
i 값은 4이므로,
R[0] = R0 이므로 01 값을 XOR 해준다.
8A ⊕ 01 84 EB 01 이렇게 되면 값은
8B 84 EB 01 이 된다.
여기까지의 값은 Rcon(Subword(Rotword(W3))) 이다.
2-1-4. W0 와 ⊕ 연산
W4 = Rcon(Subword(Rotword(W3))) ⊕ W0 이 최종적인 W4를 구하는 방법이므로
마지막으로 W0과 ⊕ 연산 해주면 W4를 구하게 된다.
8B ⊕ 2B 84 ⊕ 7E EB ⊕ 15 01 ⊕ 16 을 연산해주면?
A0 FA FE 17 이 최종 W4 값이 된다.
Key schdule을 이해했으니 AddroundKey를 적용하면
1F 3C F2 03 2B 28 AB 09 B2 11 C5 AA ⊕ 7E AE F7 CF 6E B2 7A 45 15 D2 15 4F E4 D9 81 30 16 A6 88 3C 의 연산을 거쳐서
34 14 59 0A CC BF 32 65 7B 60 6F 0A F2 7F 09 0C 결과가 나오게된다.
이제부터 나오는 Subbytes, ShiftRows, MixColumns 연산과정이다.
MixColumns까지 연산한 최종값은 어차피 아래에 자세한 연산과정에서 나온다. 걱정안해도된다. 3. Subbytes 함수
Subbytes는 앞에 Key Schedule에서 사용한 레인달 S-Box를 사용하여 치환하는 과정이다.
34 14 59 0A CC BF 32 65 7B 60 6F 0A F2 7F 09 0C 치환해주면
18 FA CB 67 4B 08 23 4D 21 D0 A8 67 89 D2 01 FE 이 된다.
4. ShiftRows 함수
ShiftRows도 간단하다
0번째 행은 0번 좌시프트 연산
1번째 행은 1번 좌시프트 연산
2번째 행은 2번 좌시프트 연산
3번째 행은 3번 좌시프트 연산 진행한다.
18 FA CB 67 4B 08 23 4D 21 D0 A8 67 89 D2 01 FE 이랬던 값이
18 FA CB 67 08 23 4D 4B A8 67 21 D0 FE 89 D2 01 이 된다.
5. MixColumns 함수
MixColumns 과정이 제일 어려웠다...
왜냐하면 우리가 사용하는 행렬은 1개의 원소 값이 1바이트로 이루어져있는데,
행렬곱을 진행하는 MixColumns 과정을 거치다보면 FF 이상의 값이 나오는 경우도 있어서 이다.
이걸 이해하려고 앞서말한 갈루아 필드에 대해서 공부해봤지만 기항다항식이 왜 곱셈이 되는지 모르겠어서 포기함.
그냥 외우고 넘어가야겠따...
자! MixColumns는 특정 행렬과 이전까지 구했던 값을 1개의 열로 나누어서 4x1 행렬곱을 진행하는 과정이다.
MixColumns에서 사용되는 특정 행렬은
02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 이다.
W0 값을 사용하여 연산과정을 행렬곱으로 표현하면
02 03 01 01 18 01 02 03 01 X 08 01 01 02 03 A8 03 01 01 02 FE 이렇게된다.
여기서 문제는 (어떠한 값) X 01 값은 그대로 (어떠한 값)이 나오지만
02나 03을 곱하게 되는 경우에 FF 값을 넘어가게되는 경우는 연산을 다르게 해줘야한다고한다.
2를 곱하는 경우에 FF를 넘기는 경우에는
예를 들어 기존의 값이 1101 0001 인데 X2를 연산하게 된다면
좌시프트 후 추가된 공간은 0으로 채워준다
1010 0010 이런식으로
그 후에 0x1B 값을 ⊕ 연산해주면 된다.
왜 0x1B인지는 그냥 넘어가기로했따....
3을 곱하는 경우에 FF르 넘기는 경우에는
N X 03 = N X {(0000 0001 ⊕ 0000 0010)}
= (N X 0000 0001) ⊕ (N X 0000 0010) 으로 연산해주면 된다.
https://newstein03.tistory.com/1
AES ( Advanced Encryption Standard ) 암/복호화 알고리즘
1. AES 란? AES (Advanced Encryption Standard) 란 표준 암호화 알고리즘으로 Rijmen과 Daemen이 개발한 Rijndael 알고리즘이 AES 공모에서 선정되면서 AES로 암호화 표준이 되었다. AES 알고리즘은 128비트 단위로 이
newstein03.tistory.com
이 분이 설명한거 보고 이해해보려고하는데...어렵다...
자 연산의 결과는
7E 15 42 71 이렇게 된다.
직접 손으로 계산해봐서 정확할지는 장담 못하겠지만...
맞겠지
이렇게해서 MixColumns를 통해서 각 열의 값을 바꿔주면 된다.
6. round 진행
AES-128을 기준으로 했으니
10번의 라운드를 거친다.
처음에 2번 과정을 한번만하고
3 -> 4 > 5 -> 2의 과정을 10번 반복하겠다고 생각할 것이다.
처음부터 과정을 설명하면
2(AddroundKey) -> 3(Subbytes) -> 4(ShiftRows) -> 5(Mixcolumns) -> 2(AddroundKey) -> 3(Subbytes) -> 4(ShiftRows) -> 5(Mixcolumns) -> 2(AddroundKey) -> ......... -> 3(Subbytes) -> 4(ShiftRows) -> 5(Mixcolumns) -> 2(AddroundKey) 에서 끝날 것 같지만
실제로 마지막 10번째 라운드는 3->4->2로 끝난다.
2(AddroundKey) -> 3(Subbytes) -> 4(ShiftRows) -> 5(Mixcolumns) -> 2(AddroundKey) -> 3(Subbytes) -> 4(ShiftRows) -> 5(Mixcolumns) -> 2(AddroundKey) -> ......... -> 3(Subbytes) -> 4(ShiftRows) -> 2(AddroundKey) 이렇게이다.
어렵진 않은데 머릿 속으로 생각하니까 좀 복잡하네....