본문

AES 문서 분석 #1. 데이터의 표현

Advanced Encryption Standard(AES)는 128비트 블록과, 길이가 128, 192 또는 256비트인 키를 사용하는 대칭 블록 암호 알고리즘이다. 이 표준의 모태인 Rijndael에서는 추가적인 블록 크기와 키 길이가 정의되었지만 AES에서는 위에 제시된 범위로 한정되었다. 키의 길이에 따라 AES-128, AES-192, AES-256으로 부를 수 있으며, 기존의 Data Encryption Standard(DES)에서 Feistel 방식을 사용하였던것과는 달리, AES는 non-Feistel 알고리즘에 속한다. 2001년 12월 미국 국립기술표준원(NIST, National Institute of Standards and Technology)에서 FIPS PUB 197으로 공표되었다.




* Rounds

키의 크기가 128, 192, 256일때 각각 10, 12, 14 번의 라운드(Nr)를 사용한다. 물론 모든 경우에서 생성되는 라운드 키 크기는 평문과 암호문 크기와 동일한 128비트이다. 또한 라운드 키의 수는 총 라운드 수보다 하나 더 많다. 위 그림에서 보다시피, 맨처음에 Add round key 과정이 들어가 있기 떄문이다. 각 키는 Knr으로 표현(K0, K1, K2...)하며 word단위(32비트가 모여 이루어 진것으로, 하나의 개체로, 혹은 4바이트(1byte=8bit)의 배열로 나타난다)로 표현되어 128비트일 경우 w[0,3], w[4,7]등으로 표현된다. 여기에서의 라운드 키란, Ciper Key로부터 Key Expansion 과정을 거쳐 생성된 키이다. 



* 데이터 단위


AES는 비트(bit, 'b'로 표기), 바이트(byte=8bit, AES의 기본 단위, 'b'로 표기), 워드(word=4byte, w'로 표기), 블록(block=16byte), 스테이트(state=4word=16byte)의 단위를 사용하여 계산한다. AES는 여러개의 라운드를 사용하며, 각 라운드는 여러개의 단계들로 구성된다. 데이터 블록은 하나의 단계에서 다른 단계로 이동함에 따라 변형되는데, 이때 암호 알고리즘의 시작과 끝의 값을 데이터 블록이라는 용어를 사용하며, 각 단계 전후에 있는 데이터 블록을 스테이트라고 정의한다. 



* The State

AES의 알고리즘은 내부적으로, State라 불리는 바이트의 2차원 배열을 사용하여 동작된다. State는 4개의 바이트열으로 구성되어 있으며 각각은 Nb 바이트를 갖는다. (이때 Nb는 32로 나뉘어진 블록길이를 의미한다) 각각의 원소는 s로 표기되어 r과 c의 첨자를 갖는다.(이 글에서는 첨자쓰기가 번거로워 s[r,c]로 표기함)이때 r은 열을 나타내어 0<=r<4범위를 가지고, c는 행을 나타내어 0<=c<Nb의 범위를 갖는다. 따라서 다음과 같은 표현이 가능하다 s[r,c]=in[r+4c], out[r+4c]=s[r,c]

때때로 스테이트는 각 성분이 워드인 1x4 행 행렬로 표현된다. 이러한 표현은 각 워드를 열행렬로 생각한다면 맟는 표현법이다. 알고리즘이 시작 부분에서 데이터 블록의 바이트들은 하나의 스테이트로 삽입되는데 열단위로 적용된다. 그리고 각 열에 대해서는 위에서 아래로 삽입된다. 


* 유한체(Finite Field)

여기에서 체(field)란, 0으로 나누는 나눗셈을 제외한 사칙연산(四則演算)을 자유로이 할 수 있는 원소의 집합을 나타낸다. 유한체는 유한개의 원소를 갖는 체로서, 암호에서 매우 중요한 구조이다. 갈로하는 유한개의 원소를 갖는 체에 대하여 원소의 개수가 p^n개임을 보였다. 여기서 p는 소수이고 n은 양의 정수이다. 유한체는 보통 갈로아체(Galois field)라고 불리고, GF(p^n)으로 표현한다.


* GF(2^n)체

암호학에서는 흔히 네개의 연산(덧셈, 뺄셈, 곱셈, 나눗셈)을 필요로 한다. 즉, 암호학에서는 체를 사용한다. 그러나 컴퓨터로 연산을 할 때, 양의 정수들은 컴퓨터에 n-비트 워드(여기에서 워드는 4byte를 의미하는것이 아님)들로 저장된다. n은 보통 8, 16, 32, 64이다. 이것은 정수들의 범위가 0에서 2^n-1까지임을 의미한다. 즉, 모듈로는 2^n이다. 이때 원소의 개수가 2^n인 GF(2^n)체를 사용할 수 있다. 이 집합의 원소들은 n-비트 워드들이다. 예를 들어 n=3일때 집합은 다음과 같다. {000,001,010,011,100,101,110,111} 그러나 이 원소들에는 일반적인 네개의 연산들이 적용될 수 없기 때문에(모듈로 2^n은 소수가 아니다) 각 원소들을 0부터 7까지의 정수로 생각할 수 없다. 따라서 n-비트 워드들의 집합과 체에 정의된 성질을 만족하는 새로운 연산을 정의할 필요가 있다.


 XOR  00  01  10  11  XOR  00  01  10  11
 00  00  01  10  11

 00

 00  00  00  00

 01

 01  00  11  10  01  00  01  10  11
 10  10  11  00  01  10  00  10

 11

 01
 11  11  10  01  00  11  00  11  01  10

 Addition (항등원:00)

 Multiplication (항등원:01)


예를 들어 네개의 2-비트 워드들로 구성된 집합{00,01,10,11}인 GF(2^3}체를 정의할 수 있다. 이 체에 대한 덧셈과 곱셈을 그린 위 표에서 보인것처럼 새로이 정의할 수 있다. 각 워드는 그 자신의 덧셈 역원이다. 모든 워드는(00은 제외) 곱셈 역원을 갖고 있다. 곱셈 역원쌍은 {01,01}과 {10,11}이다. 덧셈과 곱셈은 다항식의 형태로 정의한다.


* Byte의 표현

n-비트 워드들 위에서 GF(2^n)의 모든 성질들을 만족하는 덧셈과 곱셈 연산에 대한 규칙을 직접 정의할 수 있지만, n-비트 워드들을 차수 n-1의 다항식 형태로 생각하는것이 훨씬 간단하다. AES 알고리즘에서의 모든 바이트값은 양 괄호로 묶여진 각각의 비트값(0 또는 1)으로 표현될 수 있으며 또한 다항식으로 표현되는 유한체로서 나타날 수 있다. 또한 2개의 nibble로 구분되어 16진수로 표현되기도 한다. ex) {01100011}={63}

x^i는 i번째 항(term)으로 불리고 bi는 i번째 항의 계수(coefficient)로 불린다. 계수가 0이라면 그 항은 쓰지 않고 계수가 1이라면 1은 생략하여 쓴다. 또한 x^0은 1이다. 



참고서적 : 암호학과 네트워크 보안(Cryptography and Network Security)

저작자 표시 비영리 변경 금지
신고

댓글 0

Holic Spirit :: Tistory Edition

design by tokiidesu. powerd by kakao.

티스토리 툴바