aes 128 기준 간단 정리
선행 요구 지식
빅엔디안, 리틀엔디안
xor, and, or
4x4 행렬 곱 계산 방법
추가 보너스
galois field 대충 알면 굳
곱연산이 xor 연산으로 대체된다
좋은 자료들
★ 표준 자료집 및 샘플들, 테스트할 때 필요
fips 197
★ 암복호화 시뮬레이션
★ 암복호화 애니메이션 - 이해하는데 크게 도움된다
★ 수학적 내용들이 어떻게 컴퓨터 코드로 변할 수 있는지 정보(이해하기 쉬움 강추)
Galois Field in Cryptography
Christoforus Juan Benvenuto
May 31, 2012
★ 암호화, 복호화 할 때 곱연산을 미리 계산해 표로 만들어 둠
주의사항(삽질 하지 않기 위해 중요!!) - 구현 방법에 따라 필요하지 않은 내용일 수 있으니 참고만 하면 된다
데이터 표현은 다음과 같다
A. 암호화 하고 싶은 문자열
-> "00112233445566778899aabbccddeeff"
B. 바이트 단위로 분리
-> 00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
바이트 단위 예시
0x11
16 진수 -> 2의 4승 -> 숫자 한자리가 4bit -> 그러므로 1바이트는 2자리 숫자(0x00 ~ 0xFF)
C. 수학적 행렬 표현
->
00 44 88 cc
11 55 99 dd
22 66 aa ee
33 77 bb ff
주의 사항☆☆ aes 알고리즘에서는 행을 묶어 연산하지 않고(00 44 88 cc 가 아니라)
열을 묶어 연산을 한다(00 11 22 33) 컴퓨터 코드로 구현시 유의하기 바란다
D. 컴퓨터 배열 표현(각자 구현 방법에 따라 다름)
(인간이 읽기 편한 표현과 다르게 위에서 아래로 세로로 한 묶음임에 주의하라
마치 행렬이 대각선 대칭된 것 같아보이지만 실제로 위와 아래는 같은 행렬이다
물론 이건 각 개인이 어떻게 구현하느냐에 따라 다르다)
->
uint32_t col[4]
col[0] = 0x00112233;
col[1] = 0x44556677;
col[2] = 0x8899aabb;
col[3] = 0xccddeeff;
*** 컴퓨터 내부 메모리 상태(빅엔디안, 리틀엔디안에따라 다름)
little endian - x86, arm이라고 가정
->
uint8_t *ptr = (uint8_t *) col; //32bit 변수인 col을 8bit씩 접근
ptr[0] : 0x33
ptr[1] : 0x22
ptr[2] : 0x11
ptr[3] : 0x00
거꾸로 들어가 있음에 주목하라
참고 - 리틀엔디안, 빅엔디안
-> 괜히 헷갈릴까봐 빼버림, 별 필요도 없음
알고리즘
각 과정에 관한 상세한 설명은 fips 197 문서를 참고하기 바란다
아래는 개략적 흐름을 쉽게 이해하기 위해 간략하게 작성한다
1. key scheduling
2. init round
add round key
3. round (반복)
sub bytes
shift rows
mix columns
add round key
4. final round
sub bytes
shift rows
add round key
1. key scheduling
key expansion, 키확장이라고 불리는 행위를 한다
상대방과 나만 아는 비밀의 키(cipher key, 이하 key라 호칭)를
암호화 과정 때 그대로 쓸 수가 없으니 특별한 연산을 통해 바꾼다
별건 아니고 4x4 행렬의 한 열의 데이터를 회전하고 치환하고 xor 연산 하면 땡이다
왜 scheduling이라고 부르냐면 각 round 때마다 사용할 각각의 key들을 미리 쫙~ 계산해놓기 때문인데
속도나 기타 이유로 key를 미리 계산해서 배열에 저장해두는게 싫으면 라운드 돌때 마다 계산을 해도 ok
2. init round
별거 없다 시작하기 전에 add round key를 한 번 돌려주고 시작한다
add round key
행렬(보통 현재의 상태인 state라고 부른다)과 key(보통 round key라고 부르며 1번의 스케쥴링할 때 미리 구해놓은 제품이다)를
xor하면 끝
3. round
aes 128 기준 9번 반복
반복을 많이 하면 암호화 레벨이 올라간다(오! 간단하다)
sub bytes
행렬의 데이터를 SBOX라고 불리는 배열에서 가져와 치환한다
이 데이터들은 복잡한 다항식을 행렬식으로 바꿔서 풀고 뭐하고 한 의미가 있는 값들이다
shift rows
말 그대로 행렬의 행을 shift 시킨다
mix columns
행렬곱 연산을 수행한다
단. aes에서의 행렬연산은 독특한데 단순히 곱셈이 아니라 여러 조건에 따른 계산식이 존재한다
but 모두 미리 계산되어 간편하게 계산된 배열에서 읽어와서 치환을 하면 된다
(물론 직접 계산하도록 작성해도 좋다)
4. final round
mix columns을 안 하는 것을 제외하고 3번과 동일하다
복호화
이 과정 역시 fips 197을 자세히 참조하기 바란다
1. key scheduling
2. init round
add round key
3. round (반복)
inverted shift rows
inverted sub bytes
add round key
inverted mix columns
4. final round
inverted shift rows
inverted sub bytes
add round key
1. 키 스케쥴링
비슷한데 좀 다르다
암호화 할 때랑 동일하게 계산하는데 사용하는 순서는 반대다
암호화 할 때 마지막에 사용한 key == 복호화 할 때 처음 사용하는 key
복호화 할 때 마지막에 사용한 key == 암호화 할 때 처음 사용하는 key
혹시나 해서 적는데 동일한 SBOX를 사용한다
2. init round
동일하게 add round key를 하는데 key scheduling해서 얻은 마지막 키부터 거꾸로 사용한다
3. inverted shift rows
반대로 쉬프트 한다
inverted sub bytes
inverted sbox 에서 가져와 치환한다(inverted sbox라는 배열이 별도로 있다)
add round key
이건 변한거 없다
inverted mix columns
역행렬을 구하는, 즉 행렬곱 연산을 하는건데 연산꺼리가 훨씬 늘어났다
이거도 그냥 미리 계산된 배열에서 찾아서 쓰면 된다
4. final round
마지막에 사용하는 round key 값은 순수한 암호키다
이하 생략
기타 cbc, ecb 등등에 관해
aes 128 암호화를 돌릴 때 데이터를 4x4 즉 128bit로 넣어줘야하는데
세상 살이가 그리 쉽지 않다 데이터 크기가 128bit보다 적을 수도 있고 클 수도 있다
그럴 때 그 데이터를 어떻게 채우거나(padding) 자를 것인가(parsing)에 관한 기법들이다
wikipedia에 알기 쉽게 정리 되어있다
그냥 그림만 보자 똑같은 크기로 나누거나 적당히 채우거나 그런 내용들이다
aes 암호화 해서 나온 결과를 이전 내용과 xor하거나 등등 그런 소리다
aes 알고리즘을 구현한 다음 천천히 구현거나 필요에 의해 구현하지 않아도 ok
최적화
cpu가 aes가속을 지원하면 어셈블리로 짜서 써도 좋고 그게 아니라면
L, E table에서 곱연산 찾아오는 것도 있고 아니면 0xb, 0xd, 0x9, 0xe, 0x2, 0x3 행렬곱 연산을 미리 계산한거 가져다가 쓸 수도 있다
그 외 register 크기인 32bit 씩 가져다가 한 번에 처리하는 방법도 있고
값 swap 할 때 xor로 swap하는 거나 rotate 최적화 등등
자세한건 openssl 소스 중에 crypto/aes/aes_core.c (맞나?)을 참조해서 분석해보면 좋을 것이다
난 머리가 나빠서 이해를 못하겠따 ㅋㅋ
