대칭알고리즘 AES ▪ 발표자 : 최명현

DES challenge DES Challenge 일자 해독시간 수상자 비고 I 1997년1월 96일 R.Verser -DESHALL 팀구성 -인터넷의 위력 입증 -약 24.6%의 키 공간 조사 II 1998년1월 41일 Distributed.Net -약 22,000명 참여 -약 50,000 CPU 링크 II-2 1998년7월 56시간 EFF -DES Cracker 라는 칩사용($250,000) -초당 880억개의 키를 조사하는 속도 III 1999년1월 22시간 15분 & Distrubuted.Net -Deep Crack 사용 -약 10만대의 PC 이용 -초당 2,450억개의 키 조사속도

AES (Advanced Encryption Standard) 1997 Aes 알고리즘 공모 • 대칭키 블록 암호 알고리즘 • 입출력 크기 : 128비트 • 키 크기 : 128/192/256비트 1998 15개 후보 알고리즘 선정 1999 다섯개 알고리즘 최종후보 • MARS ,RC6 ,Rijndael ,Serpent , Twofish 2001 Rijndael 채택 • 개발자: J.Daemen, v.Rijmen

AES Pseudo AES(in,out,key) { KeyExpansion(Key,RoundKey) state = in AddRoundKey (state,RoundKey[0]) for round=1 step 1 to Nr-1 SubBytes(stats) ShiftRows(stats) MixColumns(stats) AddRoundKey(stats,RoundKey[i] end for AddRoundKey(stats,RoundKeyp[Nr]) out = stats }

Smplified Rijndael Scheme 암호화 복호화

Rijndeal Structure • 블록사이즈 : 128 비트 , 키 사이즈 : 128/192/256 비트 • 구조 : 10 / 12 / 14 라운드의 SPN 구조 - Byte 단위의 연산을 이용 - 세개의 layer로 구성 14 Nk=8 12 Nk=6 10 Nk=4 Nb=8 Nb=6 Nb=4 Nr Nr : rounds Nb : block size / 32bit Nk : key size / 32bit ► Linear mixing layer 여러 라운드에 걸친 높은 확산 ShiftRow(state) , MixColumn(state) ► Non-linear Layer S-box의 병렬 적용 ByteSub(state) ► Key Addition Layer 중간 state에 라운드 키의 EXOR AddRoundKey(state)

Nb =4 일때의 block state 와 Nk = 4 일때의 key state Rijndael 연산들은 상태(state)라고 하는 2차원 바이트배열에 수행된다 State는 2차원 배열로 구성된다.행은 4행으로 구성되고 , 각 행은 Nb 바이트로 구성된다 . A0,0 A0,1 A0,2 A0,3 A1,1 A1,2 A1,3 A2,0 A2,1 A2,2 A2,3 A3,0 A3,1 A3,2 A3,3 K0,0 K0,1 K0,2 K0,3 K1,1 K1,2 K1,3 K2,0 K2,1 K2,2 K2,3 K3,0 K3,1 K3,2 K3,3 Nb =4 일때의 block state 와 Nk = 4 일때의 key state ex) 128비트 입력 : EA 83 5C F0 04 45 33 2D 65 5D 98 AD 85 96 B0 C5 EA 04 65 85 83 45 5D 96 5C 33 98 B0 F0 2D AD C5

GF(28)에서 곱셈에 대한 역원 ◈곱셈에 대한 역원 찾기 만약 GCD(d,f)=1이라면 그때 d는 modulo f 상에서 곱셈에 대한 역원을 갖는다. 양의 정수 d<f에 대해, dd-1=1 mod f인 d-1<f가 존재 • Extended Euclid(d,f) 1. (X1, X2, X3)<-(1,0,f);(Y1, Y2, Y3)<-(0,1,d) 2. If X3= 0 return X3=GCD(d,f); no inverse 3. If X3 = 1 return Y3=GCD(d,f); Y2=d-1 mod f 4. Q = X3 / Y3 5. (T1, T2, T3) <- (X1-QY1, X2-QY2, X3-QY3) 6. (X1, X2, X3) <- (Y1, Y2, Y3) 7. (Y1, Y2, Y3) <- (T1, T2, T3) 8. Goto 2

GF(28)에서 곱셈에 대한 역원 GCD(95,m(x))=1 m(x)=x8 +x4 +x3+x+1 ex) GF(28) 에서 95의 곱셈에 대한 역구하기 GCD(95,m(x))=1 m(x)=x8 +x4 +x3+x+1 b(x)=x7 +x4 +x2+1 A1(x)=1 , A2(x)=0 , A3(x) = x8 +x4 +x3+x+1 B1(x)=0 , B2(x)=1 , B3(x) = x7 +x4 +x2+1 1.Q(x)=(x8 +x4 +x3+x+1) /(x7 +x4 +x2+1) = x [T1,T2,T3]<-[1-x·0 ,0-x·1 , (x8 +x4 +x3+x+1) –x·(x7 +x4 +x2+1)] A1(x)=0 A2(x)=1 A3(x)=x7 +x4 +x2+1 B1(x)=1 B2(x)=x B3(x)=x5 +x4+1 2.Q(x)= (x7 +x4 +x2+1) / (x5 +x4+1) = x2 +x+1 [T1,T2,T3]<-[0-(x2 +x+1)·1 ,1-(x2 +x+1)·x , (x7 +x4 +x2+1) –(x2 +x+1)·(x5 +x4 +1)] A1(x)=1 A2(x)=x A3(x)=x5 +x4 +1 B1(x)=x2 +x+1 B2(x)=x3+x2 +x+1 B3(x)=x 3.Q(x)=(x5+x4 +1) / x = x4 +x3 [T1,T2,T3]<-[1-(x4 +x3)·(x2 +x+1) ,x-(x4 +x3)·(x3+x2 +x+1) , (x5 +x4 +1) –(x4 +x3)·x] <-[x6 +x3 , x7+x3 +x ,1] A1(x)=x2 +x+1 A2(x)=x3+x2 +x+1 A3(x)=x B1(x)=x6 +x3 B2(x)=x7+x3 +x B3(x)=1 B3(x)=1 이므로 B2(x)=B(x)-1 mod m(x) B2(x)=x7+x3 +x = 8A ∴ 95-1 = 8A

Substitute Bytes Transformation ◈ state 의 각 바이트를 치환 • 각 바이트를 16x16 s-box를 이용하여 치환 • 8비트를 상위 4비트가 행, 하위 4비트가 열로 사용.

Substitute Bytes Transformation • S-box()는 기약다항식 m(x) = x8 +x4 +x3+x+1을 사용하여 구성한다. • 구성방법 • 먼저 s-box()에 00,01,...,FF 순으로 초기화 한다. • 이 값들을 GF(28)에서 곱셈에 대한 역원으로 매핑한다. 00 -> 00 • 한 항의 값이 b7b6b5b4b3b2b1b0 이면 다음 식에 의해 변형된다. bi ’ =bi ⊕ b(i+4)mod 8 ⊕ b(i+6)mod 8 ⊕ b(i+7)mod 8 ⊕ ci i 를 0 ~ 7까지 대입하여 정리하면 아래식이 나온다 . 그리고 뒤에 63은 임의로 주어진 1 바이트 수 이다 . 95 = 95-1 = 8A

S-box

Inverse Substitute Bytes Transformation • Inverse s-box 는 s-box()의 bi ’ =bi ⊕ b(i+4)mod 8 ⊕ b(i+6)mod 8 ⊕ b(i+7)mod 8 ⊕ ci 의 역을 적용한 다음 GF(28)에서 곱셈에 대한 역원으로 구성한다. 역변환은 bi ’ = b(i+2)mod 8 ⊕ b(i+5)mod 8 ⊕ b(i+7)mod 8 ⊕ di 이며 바이트 d는 63의 곱셈에 대한 역원인 05 이다. b´0 b´1 b´2 b´3 b´4 b´5 b´6 b´7 b0 b1 b2 b3 b4 b5 b6 b7 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 = + 1

Inverse S-box

Shift row Transformation • 각행을 행의 index 만큼 왼쪽으로 circular shift 함 .

Mix Column • Mix column에서는 state의 column이 GF()에서의 다항식 a(x)가 고정된 다항식 c(x)에 대해 a(x) ⊕ c(x) mod (x4+1) 연산을 행한다. • c(x) = ’03’ x3 + ’01’ x2 + ’01’ x + ’02’ • d(x) = ’0B’x3 + ’0D’x2 + ’09’x + ’0E’ • m(x) = x4+1 최고차항이 4차 보다 작은 두 다항식 a(x) b(x)가 있다고 가정하면 a(x)= a3x3 +a2x2 +a1x+a0 , b(x)= b3x3 +b2x2 +b1x+b0 이다 c(x)= a(x)b(x) 하면 c(x)= c6x6 +c5x5 +c4x4 +c3x3 +c2x2 +c1x1+c0 c0 = a0•b0 c1 = a1•b0  a0 •b1 c2 = a2•b0  a1•b1  a0•b2 c3 = a3•b0  a2•b1  a1•b2  a0•b3 c4 = a3•b1  a2•b2  a1•b3 c5 = a3•b2  a2•b3 c6 = a3•b3

Mix Column b0 b1 b2 b3 d0 d1 d2 d3 = a0 a3 a2 a1 a1 a0 a3 a2 c(x)의 최고차항이 4보다 크기때문에 mod m(x) 연산을 해주면 그값은 아래와 같다. c(x)mod m(x)= d(x) = d3x3 +d2x2 +d1x+d0 = c3x3 +c2x2+c6x2 +c1x+c5x+c4 +c0 d0 = a0•b0  a3•b1  a2•b2  a1•b3 d1 = a1•b0  a0•b1  a3•b2  a2• b3 d2 = a2•b0  a1•b1  a0•b2  a3• b3 d3 = a3•b0  a2•b1  a1•b2  a0• b3 위 식을 간단히 하면 아래와 같이 된다. b0 b1 b2 b3 d0 d1 d2 d3 = a0 a3 a2 a1 a1 a0 a3 a2 a2 a1 a0 a3 a3 a2 a1 a0 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 d0 d1 d2 d3 = b0 b1 b2 b3

Mix Column 02 03 01 01 01 02 03 01 01 01 02 03 03 01 01 02 87 6E 46 A6 47 37 94 ED =

The round key addition • 라운드 키는 키 스케줄에 의해 생성된 키들과 state의 EXOR 이다.

Key expansion Pseudo code

Key expansion •128 비트 키를 4Nr+4 개의 32비트 워드로 확장