AES
AES란?
Advanced Encryption Standard의 약자이다. DES가 취약성, 속도, 점점 더 커지는 데이터의 용량을 따라가지 못하는 입력 비트 제한 등의 이유로 사용하기 어려워지자 새로 공모한 보안 표준이다.
조건
- 입력 비트 128비트 이상
- Triple DES보다 좋아야 함
- 구조와 디자인을 전부 공개해야 함
- C와 JAVA 모두 적용 가능
현재 AES로 Rijndael 알고리즘을 사용한다.
Rijndael알고리즘의 특징
- 128비트 데이터, 128/192/256 비트 키
- Feistel cipher는 데이터를 반 나눠서 절반은 round 함수로 변조하고 절반은 그대로 쓴다. 하지만 Rijndael 알고리즘은 데이터 전체를 암호화하므로 좀 더 적극적이다.
- key길이가 길어질수록 round횟수가 많아지므로 key를 줄였다.
- key size 128, 192, 256에 따라 round 횟수도 10, 12, 14회로 변한다.
하지만 블록 사이즈는 항상 128비트로 고정이다.
SPN network
AES에서 substitution과 permutation을 수행하기 위해 사용하는 네트워크이다.
모든 라운드 함수의 구성요소가 invertable하다.
Rapid diffusion
입력 데이터에 작은 변화가 있을 때, 이 변화가 전체 데이터에 빠르게 퍼져나간다.
AES의 라운드 구성
Initial round
AddRoudKey
128비트 입력값을 테이블 형태로 만든다. 이 테이블을 state라고 하자.
state는 열을 우선적으로 채운다.
initial round에서는 state를 만들고 키를 XOR하는 단계만 거친다.
rounds
SubBytes + ShiftRows + MixColumns + AddRoundKey
암호화를 진행한다.
Final round
SubBytes + ShiftRows + AddRoundKey
final round에서는 복호화를 쉽게 하기 위해 mixcolumn을 의도적으로 1회 뺐다.
특히 mixcolumn은 diffusion(확산)에 쓰이는 알고리즘인데,
마지막 라운드에 올 때 쯤에는 이미 충분히 diffusion이 일어나서 한 번 생략해도 된다.
Algebraic Structure
수 집합에 대해 특정 연산이 특정 규칙을 따르는 수체계이다.
따라서 어떤 집합에 대해 + 어떤 연산이 + 무슨 규칙을 가졌는지 가 중요하다.
크게
그룹,링,필드가 있다.
그룹
이항 연산에 대해 다음 조건을 만족한다.
- 닫힘성
집합 안의 두 요소로 계산했을 때 결과값이 집합 안에 있어야 한다. 예를 들어 정수+정수를 해서 나온 결과도 정수인 경우 닫힘성이 보장된다.
- 결합법칙 성립
- 항등원, 역원 존재
그룹에서 교환법칙이 성립하면 아벨리안 그룹이 된다.
예를 들어 <GF(2), +> 라는 구조가 있다고 하자.
GF(2)는 0과 1만 있는 집합이며 갈로아필드이기 때문에 +는 XOR이라는 뜻이다.
닫힘성 : 0과 1로 어떤 XOR을 취해도 결과는 0또는 1만 나온다.
결합법칙 : 0 XOR (1 XOR 1) = (0 XOR 1) XOR 1
항등원 : a XOR 0 = 0 이므로 0이 항등원
역원 : a XOR a = 0 이므로 자기자신이 역원
- a XOR b = b XOR a 로 교환법칙이 성립하므로 아벨리안 그룹이다.
cyclic group
순환군은 하나의 원소에 반복적인 연산을 취해서 집합 내 모든 원소를 만들 수 있는 그룹을 의미한다.
이 때 원소를 만드는 데 쓰이는 하나의 원소를 Generator라고 한다.
예를 들어 <Z₆, +>의 원소는 6개(0,1,2,3,4,5)이고 generator는 1 또는 5이다.
(Z₆)에서 2를 쓰면 2^0 mod 6 = 0, 2^1 mod 6 = 2, 2^2 mod 6 = 4로 3, 5등이 만들어지지 않는다.
하지만 1을 쓰면 1^0 mod 6 = 0, 1^1 mod 6 = 1, 1^2 mod 6 = (1+1) mod 6 = 2로 모든 요소를 다 만들 수 있다.
Order
그룹 G의 원소의 개수를 말한다.
element에 대한 order는 연산했을 때 항등원이 튀어나오는 제일 작은 양수
예를 들어 ord(1)의 경우 1^0 mod 10=1, 1^1 mod10 = 1, 1^2 mod 10 = 1 이므로 항등인 답변이 나오게 하는 제일 작은 양수는 1이다.
따라서 ord(1) = 1이다.
Ring
< R, ＋, × >
집합의 원소와 연산자 2개를 제공한다.
조건
1. R은 덧셈에 대해 abelian그룹이다.
2. 곱셈에 대해 닫혀있다.
3. 곱셈에 대해 결합법칙이 성립한다.
4. 분배법칙이 성립한다.
(곱셈에 대한 교환법칙까지 성립하면 commutative ring이다.)
Field
Ring처럼 연산자가 2개 주어지고, 이 두 개의 연산자(덧셈연산자와 곱셈연산자)에 대해서 모두 abelian 그룹이 성립하는 것을 field라고 한다.
예외사항 : 덧셈에 대한 항등원이 0이어야 한다는 조건은 무시해도 됨
Finite Field
Field의 원소의 개수가 유한할 때 finite라고 한다. 갈로아 필드라고도 부른다.
Finite Field의 원소의 개수는 반드시 p의 n승 포맷으로 표현되어야 한다. (p는 소수)
예시
GF(2)는 finite field이다. 따라서 GF(2) =< {0, 1}, +, x >
addition, multiplication을 할 때 연산 결과를 항등식으로 만드는 값이 0~1 구간 내에 존재하기 때문이다.
컴퓨터 상에서 n개의 비트로 표현가능한 정보의 양을 알기 위해서 n개의 비트를 갈로아 필드의 2^n개 원소에 1대1 매칭을 시켜서 ..??
갈로아 필드를 사용하는 이유
암호화 과정에서 암호를 만들고 다시 평문으로 돌릴 수 있어야 함(invertable).
암호화하기 위해 원소를 매핑시키는 공간을 AES에서 갈로아 필드로 정한 것
n-bit word를 나타내는 다항식을 작성할 때 GF(2^n) 필드를 활용할 수 있다.
GF(2^n)의 원소를 다항식으로 표현하면 각 항의 계수가 0 또는 1뿐이고 최고차항의 지수는 n-1이다.
ex)
0011 -> 0x^3+0x^2+x^1+1 = x+1
addition
XOR 기호를 활용하여 연산한다.
ex)
(x^5 + x^2 + x) XOR (x^3 + x^2 + 1)
= 100110 XOR 001101 = 101011
= x^5 + x^3 + x + 1
이 수식을 풀어서 생각해보면 같은 차수가 있을 때 지우는 계산이 된다. 따라서 다항식 계산에서 덧셈과 뺄셈은 같은 결과가 나온다는 것을 알 수 있다. 갈로아 필드라서 다항식의 계수가 0또는 1이므로 마이너스를 쓸 수는 없지만, 만약 뺄셈이 필요하다면 그냥 덧셈으로 계산하면 된다.
왜 덧셈이 아니라 XOR이죠
1+1로 2가 되면 modular연산으로 나눠지면서 0이 되기 때문에 계산 결과를 보면 XOR을 수행한 것과 같다.
multiplication
modulus polynomial(=irreducible, prime)
x^5 * x^5 = x^10이다.
하지만 GF(2^5)에서 x^10은 비트 수를 초과하기 때문에 표현할 수 없다.
이런 현상을 막기 위해 다시 차수를 내려주는 것을 modulus polynomial이라고 한다.
modulus polynomial은 각 차수마다 여러개 존재할 수 있다. 정확한 의미는 자기보다 작은 차수의 다항식으로 나누어떨어지지 않는 다항식을 말한다.
예를 들어 1차식에서는 x+1, x등이 있다.
ex) GF(2^8)에서
(x^5 + x^2 + x) × (x^7 + x^4 + x^3 + x^2 + x) 를
irreducible polynomial (x^8 + x^4 + x^3 + x + 1)을 이용하여 계산해보자.
- 곱 계산 -> x^12 + x^7 + x^2 (덧셈=>뺄셈)
- 차수 줄이기 -> 계산한 값을 irreducible로 나누면 몫이 x^4 + 1,
줄여진 식은 x^5 + x^3 + x^2 + x + 1
t = t1 + g*t2
역원 구하는 부분 다시보기
computational considerations
multiplication
어떤 다항식에 x를 곱하는 것은 shift left를 1회 수행하는 것과 같다.
msb가 1이 되어서 비트 개수 범위를 벗어나면 irreducible polynomial과 XOR을 수행한다.
shift left와 XOR을 이용해서 표현할 수 있다.
다항식 P에 대해 x^n P = x^(n-1) P x이므로 x^(n-1)P를 shift left한 값과 같다.
이런 식으로 반복하다 보면 x^n * P는 P에
①shift left를 반복
하고 bit carry가 발생할 때만 irreducible polynomial과
②XOR 계산을 수행
하는 식으로 구할 수 있다.
Encryption
Affine transformation
입력 바이트 x에 대하여 x의 역원을 이용해서 y = S(x) = Ax^-1 + b 를 구한다.
입력값은 8비트이기 때문에
역원을 구할 때 GF(2^8)에서 irreducible은 x^8 + x^4 + x^3 + x + 1을 사용한다.
input: 95
역원: 95^(-1) -> 8A
95 - 1001 0101 -> x^7 + x^4 + x^2 + 1
irreducible polynomial을 이 다항식으로 나눔 -> 몫: x, 나머지: x^5 + x^4 + 1
t = t1 + q * t2
나머지가 0이 될 때까지 shift
invSubBytes
IS(y) = (A^(-1)(y+b))^(-1) = 1/(y/A + b/A)
ShiftRows
첫 번째 행은 그대로, 두 번째 행은 한 칸, 세 번째 행은 두 칸...으로 옮기는 암호화 방식이다. shift row을 활용해서 column뿐만 아니라 row도 섞을 수 있다.
MixColumns
1열 column을 곱해서 원래 column의 전체 값을 하나로 압축한다,
a b c d x A
e f g h x B
x y z t x C
-> x만 변조해도 전체 행의 값이 달라짐
AddRoundkey
128-bit -> XOR
11개의 addroundkey(round는 10개)가 필요하다.
이전 바이트에 대해서 rotate -> xbox -> round constant에 쓰이고 4개 중에서 3개는 XOR에 쓰인다.
라운드별로 shift left 몇 번 할 것인지 정한 상수를 RCon이라고 하고 RCon[j]처럼 나타낸다. RoundConstant는 4바이트이다.
Decryption
subBytes와 ShiftRow의 순서가 바뀌어도 연산 결과는 바뀌지 않는다.
마지막 round key와 첫 번째 free round key는 mixColumn에 영향을 받지 않는다.
polynomial 연산, mixcolumn 행렬연산
