🔐 AES(Advanced Encryption Standard)
- 현재 가장 널리 사용되는 대칭 암호
- 공격: 부르트 포스, 분석적 공격 불가 but 부채널 공격 가능
SPN 구조- 블록 크기 : 128비트
- 키 길이 : 128비트，192비트，256비트 세 개 중 가변 사용 가능
- 키 길이에따라 키 스케줄링만 달라지고 나머지 과정은 같음
- 회전의 수는 키 길이에 따라 10에서 14까지 다양
- 키 길이에 따른 라운드 수(Nr)
- AES-128 : 10
- AES-192 : 12
- AES-256 : 14
- 첫 번째 라운드(0)에서는 xor만 수행
- 라운드 수가 10이면 11개의 라운드임 0부터 시작이니까
- 마지막 라운드는 MixColums를 제외한 SubBytes와 ShifhtRows, xor 실행
- 복호화할 때 하기 쉽게 위 아래 대칭 구조임
- 또한 맨 처음과 맨 끝에 xor을 해줌 = 키 화이트닝
- 키 길이에 따른 라운드 수(Nr)
- 각 round는 3개 층, 4개 함수로 구성
- SubByte (비선형 층)
- ShiftRow (linear mixing 층)
- MixColumn (비선형 층)
- AddRoundKey (key addition 층)
- DES 와 비교
- DES 키길이 56 개 작음 break 쉬움 -> AES 개발
- DES(bit단위 permutation)와 달리 SW/HW 둘다 구현 효율성, 안전성 good
- DES와 달리 라운드 수 적음
AES 암호화
- AES 수도 코드
- 평문을 AES는 논리상(실제 아님) 바이트 단위의 2차원 배열로 취급
컴퓨터는 워드단위로 → 4바이트씩 저장 - state : 4x4
- Round-key : 4xNr 바이트
- 평문을 AES는 논리상(실제 아님) 바이트 단위의 2차원 배열로 취급
Cipher(byte in[16], byte out[16], word w[4*(Nr+1)])
begin
byte state[4,4] //hw,sw에서는 실제이러케 안함 걍 이러케 취급한다!!인거임
state = in
// 첫번째 라운드 (Nr =0)은 only xor 연산만
AddRoundKey(state, w[0, 3]) //xor=+ 이기에 ex0을 더함
// 2번째 라운드부터 변환 시행
for round = 1 step 1 to Nr–1 //1~Nr-1동안 라운드 반복
SubBytes(state)
ShiftRows(state)
MixColumns(state)
AddRoundKey(state, w[round*4, round*4+3])
end for
// 맨 마지막 라운드도 쪼끔 다름
SubBytes(state)
ShiftRows(state)
AddRoundKey(state, w[Nr*4, Nr*4+3])
out = state
end
AES SubBytes
- 연산 단위 : byte(8bit)
비선형 층: 역변환 가능- AES는 DES와 달리 fiestal 구조가아니라서 1대1 대응필수임
- 입력 1개 바꿧는데 출력 막 3개씩바뀜
- 128비트 블록을 4x4바이트 배열로 처리
- 입력{xy}를 16진수 S-box table에 따라 바꿈.
- 한 요소의 비트가 하나라도 바뀌면 표에 따라 값이 확바껴 버림
- ㄴ= 한 비트 바뀌면 다바뀜 -> 비선형
- 2 단계의 계산
Finite field(연산의 유한한 공간) GF(2^8) 상에서의 mod 8차 기약다항식 multiplicative inverse 계산- 00은 제외 -> 0은 곱의 역원이 존재하지 않음
- 곱의 역원 : a가 있을 때, a*x = 1 일때, x는 a의 곱의 역원
- 곱셈 역원의 장점 : 다항식(x^3 + x +1)이(=bit가) 조금만 바껴도 그 역원이 확확 바뀜
Affine(x -> +) transformation- 𝑏𝑖′ = 𝑏𝑖 ⊕ 𝑏(( 𝑖+4 )mod 8) ⊕ 𝑏 ((𝑖+5) mod 8) ⊕ 𝑏 ((𝑖+6) mod 8) ⊕ 𝑏 ((𝑖+7) mod 8) ⊕ 𝑐𝑖
- 이때 b0~b7이 입력되는 데이터로 상위비트가 아래에 위치함.
- 위에서 구한 역원을 곱하고 더함(이 더하는 값을 c)
아래 8x8 행렬 친구는 역원을 위 식처럼 쉬프트한 것
= 순환 구조 라서 위 식처럼 나타낼 수 있음
- 𝑏𝑖′ = 𝑏𝑖 ⊕ 𝑏(( 𝑖+4 )mod 8) ⊕ 𝑏 ((𝑖+5) mod 8) ⊕ 𝑏 ((𝑖+6) mod 8) ⊕ 𝑏 ((𝑖+7) mod 8) ⊕ 𝑐𝑖
- 16개의 동일한 S-box
- DES는 서로 다른 8개의 S-box였음
- 유일하게 S-box 역변환 가능
- s-box→ 복잡 -> SW 계산 힘듬 -> 그래서 보통 아래처럼 역원 구하고 어파인한거 미리 다 구한 것을 룩업으로 계산해둠
- 위에서 역원구하고 어파인하고 머시기를 아래 표처럼 미리 계산해둔 것
- ex) 00011111이 들어오면 0001/1111 = 1f -> 아래 표애서 c0
- ex) 00011111이 들어오면 0001/1111 = 1f -> 아래 표애서 c0
AES ShiftRow
- 연산 단위 : 행
linear mixing 층- 계산 방법: S′𝑟,𝑐= S(𝑟,𝑐+𝑟 mod 4) for 0 ≤ 𝑟 < 4 and 0 ≤ 𝑐 < 4
Cyclic shift rows(레프트 로테이션)- 객 행번호 i 마다 왼쪽으로 각행마다 i씩
- 실제 저장단위는 세로가 행임 but -> 그림처럼 우리가 아는 행으으로 쉬프트 하라니까 실제 일반 컴퓨터 연산에선 준내 어려움 → 구현 이슈
AES MixColumn
- 연산 단위 : 열
4x4 행렬 곱비선형 층-> 하나 바뀌니까 열 다 바뀜(확산)- 아래 4x4 행렬은 미리 정해진 값임
- (큰) 조회 테이블로 구현
- 계산 방법
- GF(2^8) 상의 다항식으로 표현
- 아래 s(0,c)가 바뀌면 다바뀜, 영향을 미치는 정도도 다 다름
AES AddRoundKey
- 연산 단위 : 블록(hw), 4byte(sw)
블록 XOR 라운드 키- 키 스케줄 알고리즘에 의해 결정되는 라운드키(하위키)
- 계산 방법 : [s(0,c′), s(1,c′), s(2,c′), s(3,c′)]
= [s(0,c), s(1,c), s(2,c), s(3,c)] ⊕ [𝑤(𝑟𝑜𝑢𝑛𝑑×4+𝑐)]
for 0 ≤ c < 4
AES 키 확장 (Key Expansion)
- 4빝 짜리 키 늘려서 각라운드 사용하니가 키 확장
- 언뜻 보면 feistel구조랑 비슷
- AES-128의 w[i]정의
- Nk 정의
- g 함수의 구성
- RotWord : left circular shift
- SubWord : 각 바이트에 S-box 적용
- XOR with Rcon[i] : [02 ^(𝑖−1), {00} , {00} ,{00}]
- 뭐 얘도 feistal 구조라서 역으로 그냥 올라가도 ㄱㅊ
- 슈도 코드
KeyExpansion(byte key[4*Nk], word w[4*(Nr+1)], Nk)
begin
word temp
i = 0
while (i < Nk)
w[i] = word(key[4*i], key[4*i+1], key[4*i+2], key[4*i+3])
i = i+1
end while
i = Nk
while (i < 4 * (Nr+1)]
temp = w[i-1]
if (i mod Nk = 0) temp = SubWord(RotWord(temp)) xor Rcon[i/Nk]
else if (Nk > 6 and i mod Nk = 4) temp = SubWord(temp)
end if
w[i] = w[i-Nk] xor temp
i = i + 1
end while
endAES 복호화
- 프로세스가 가역적
- MixAddRoundKey의 역은 "mix" 자체의 역이기 때문에 쉬움
- MixColumn은 반전 가능(역은 룩업 테이블로도 구현)
- ShiftRow의 역은 쉬움(순환적으로 다른 방향으로 이동)
- ByteSub은 반전 가능(역은 룩업 테이블로도 구현됨)
- 선형성을 통해 암호화 복호화 구조를 거의 동일했음
- SRs와 SBs의 위치 변경 가능
- 선형성 : 𝑆𝐵𝑠^(−1)(𝑆𝑅𝑠^(−1)(𝑎)) = 𝑆𝑅𝑠^(−1)(𝑆𝐵𝑠^(−1)(a))
- 위를 계산해서 나온 결과를 b라고 가정하면, b xor ek(Nr-i)와 MC^(-1) 위치 변경 가능
- 선형성 : 𝑀𝐶𝑠^(−1)(𝑏⨁𝑒𝑘(𝑁𝑟−𝑖)) = 𝑀𝐶𝑠^(−1)(𝑏) ⨁ 𝑀𝐶𝑠^(−1)(𝑒𝑘(𝑁𝑟−i))
- AES는 연산이 어려움 → sw 환경에서는 보통 SBs,SRs,MCs를 함께 한번에 계산한 테이블을 사용함
- 역순한거는 xor때매 SRs,SBs랑 MCs 역들이 떨어져 있음 → 테이블화 못함
- 선형성을 활용하면 SBs SRs MCs 역들이 다 붙어서 테이블화 가능
- 하드웨어로 구현할거면 그냥 냅다 3번째처럼하면됨 , sw상에서 테이블화해야해서 선형성 이용한거임
- SRs와 SBs의 위치 변경 가능
InvSubBytes (SBs^(-1))
- Affine transformation(+ -> x)의 역 구하기
- multiplicative inverse 계산
- 아묻따 테이블에서 찾기 ㅋㅋ : {xy}의 16진수 S-box^(-1) table
- x는 맨 왼쪽 열, y는 맨위 행에서 찾음
- x는 맨 왼쪽 열, y는 맨위 행에서 찾음
InvShiftRows (SRs^(-1))
- 계산 방법: 𝑠'(𝑟,𝑐−𝑟 mod 4) = 𝑠𝑟,𝑐for 0 < r < 4 and 0 ≤ 𝑐 < 4
- 오른쪽으로 쉬프트
- 오른쪽으로 쉬프트
InvMixColumns (MCs^(-1))
- 계산 방법 :
- 곱해서 단위행렬 나오는 친구가 역행렬
- 얘도 보통 미리 계산해둠 sw편의성 위해, hw도 계산량 많음 숫자 복잡햇
AES 구현 및 평가
- 소프트웨어에서의 구현
- 복잡한 연산으로 인해 SW에서 처리하기 힘듬
- ShiftRows: rotation
- SubBytes: 합성곱, 곱의 역원
- MixColumns: 합성곱
- 속도 향상을 위해 S-box 테이블 처럼 미리 계산된 테이블을 주로 사용
- 복잡한 연산으로 인해 SW에서 처리하기 힘듬
DES VS AES
| 블록 크기 | 키 크기 | Round | 구조 | Transformations | |
|---|---|---|---|---|---|
| DES | 64 bits | 64 bits (사용: 56bits) | 16 | Feistel | IP, E-table, SBs, p-Table, PC1, PC2, ROL/ROR |
| AES | 128 bits | 128, 192, 256 bits | 10,12,14 | SPN | SBs, SRs, MCs, ARKs |
- 라운드 수 : DES(16개) > AES(10,12,14)
- DES : 피에스탈 구조 때메 반만 암호화가됨 -> 단점 : 라운드마다 섞이는(연산)이 되는 범위가 작음
- AES : 전체에 대해서 연산되기 때문에 DES보다 round가 적음
- 라운드 수가 10이면 11개의 라운드임 0부터 시작이니까
- DES 와 달리 키 공간이커서 부르트포스 불가
인생 살자.