[정보보호] 모듈러 연산, 갈로아 필드

※복습

- 대칭키 : 치환, 전치 두가지만 있으면 됨

    > 치환: 교체(ex. S-Box)

    > 전치: 순서 교체

 

 

#유클리드 호제법

    > 최대공약수 찾기 -> gcd(a, b)

 

#모듈러 연산

1. 법

- a % n 수행시 n = 법

- a % n == b % n 이라면, a≡b(mod n) -> a, b는 법 n에 대해 합동

- a ≡ 0 (mod n) 이면, n | a임

 

- 유클리드 호제법에 대한 재고

> 재귀함수로 구현 가능

 

- 확장 유클리드 호제법

    > 최대공약수 d 뿐만 아니라 ax+by=d=gcd(a, b)를 만족하는 x와 y를 구할 수 있음

    > x, y의 부호가 다른 것은 자명

    > a=42, b=30일때 x, y는? (gcd(42, 30)=6 임에 주목)

 

#군(groups), 환(rings), 체(fields)

1. 군(groups)

- 군 G는 {G, ●}로 정의

- 이항연산 원소의 집합임

2. 순환군(Cyclic Groups)

- 군 원소의 지수연산은 그룹 연산자의 반복이라고 정의

    > ex: a^3 = a ● a ● a

- a^0 = e 라는 항등원 정의

- 군 G의 모든 원소가 G의 임의의 원소의 멱승 연산 a^k(k는 정수)의 형태로 표현이 가능한 경우 군 G는 순환군임

- 이때의 원소 a를 군G의 생성자(generator)라고 함

 

3. 환(Rings)

- 2개 이상의 이항연산(가법과 승법)을 가지는 원소의 집합

4. 체(Fields)

- 정역(integral domain)의 성질을 포함

 

#GF(p)상의 유한체

1. 위수 p인 유한체

- 유한체는 암호학 분야에서 유용하게 활용

- 유한체의 위수(체의 원소의 개수)는 소인수의 멱승인 p^n이어야 함

- GF는 갈로아 필드(Galois field)라고 함

- GF(p^n)으로 표기함

- 주로 GF(p), GF(2^n)의 유한체 사용

 

#산술다항식(Polynomial Arithmetic)

- 하나의 미지수 x를 갖는 다항식이 존재할 때, 산술다항식은 세가지로 구분

1. 대수의 기본 규칙을 따르는 일반적인 산술 다항식

2. GF(p) 유한체 내의 원소들을 다항식의 계수로 사용하고, 각 계수들은 모듈러 p연산으로 수행되는 다항식

3. GF(p) 유한체 내의 원소들을 다항식의 계수로 사용하고, 최고차항이 n인 다항식 m(x)의 모듈러 연산으로 수행되는 산술다항식

 

#GF(2^n)상에서의 유한체

1. 동기

- 공개키와 대칭키를 포함한 모든 암호 알고리즘은 정수의 산술연산으로 이루어짐

- 산술연산을 효율적으로 구현하기 위해 정수 사용(n비트 워드를 표현하기 위해 0~2^n -1 범위의 정수 사용)

2. 모듈러 다항식 연산

- Zp상에서 n-1차 또는 미만의 차수를 갖는 모든 다항식 집합 S에서, 각가 다항식은 다음과 같은 형식

- 여기서 각각의 ai는 집합 (0, 1, ..., p-1}의 원소들 중 하나를 사용하며, 다항식 집합 S에서 총 p^n개의 서로 다른 다항식을 만들 수 있음

예제: GF(2^3) mod (x^3 + x + 1) -> 로 제목 수정

 

※5장 - AES

#핵심

- DES를 대체하는 블럭암호, 상업적 용도

> 128비트 블록 사이즈 사용

> 128, 192, 256비트를 key size로 사용

- Feistel 구조를 사용하지 않지만, 각 라운드는 4가지 암호화 과정

> 바이트 치환 변환

> 행 이동

> 열 혼합

> 라운드 키 더하기

 

#AES와 유한체 집합

- AES는 8비트를 기본 단위로 동작하며 덧셈, 곱셈, 나눗셈 연산을 유한체를 바탕으로 연산

 

#유한체 연산

- Rijndael 알고리즘 개발자들은 더 이상 약분할 수 없는 8차 다항식 30개를 선택하여 사용

 

#유한체의 집합 S의 수학적 연산 정의

#AES 구조

1. 일반 구조

- 암호화 복호화 과정에서 128비트 블록 쓰이며, 4*4의 바이트 행렬로 나타냄

- 블록은 상태 배열로 복사되며 암/복호화 각 단계에서 수정되어 쓰이고 마지막 단계에서 출력 행렬로 복사됨

- 키는 비트 행렬로 나타내어지며, 키 스케줄러 연산에 따라 확장

- 128비트 키의 확장에 대해 보여줌

- 행렬 안에서 1워드로 4비트가 할당, 총 스케줄러는 128비트 키에서 44워드 생성

 

#AES 파라미터

- N라운드로 이뤄진 암호화에서 라운드 수는 키 길이에 의존

 

#AES 암호화 및 복호화

 

#AES 변환 기능들

1. 바이트 치환 변환

- AES는 S-Box라 불리는 바이트 값들의 16*16 행렬을 저으이

- 256가지의 모든 가능한 8비트 값의 순열을 포함

- 상태 배열의 각 개별 바이트는 다음과 같은 방법으로 대응

> 순서에 전혀 관계 없이 바뀌니까 '치환'임

 

2. 행 이동 변환

3. 열 혼합 변환

 

4. 열 혼합 변환 상태 배열

5. 더하기 라운드 키 변환

 

#AES 키 확장

- 4워드(16바이트)의 입력을 받아 44워드(176바이트)의 선형 배열로 확장

- 키는 확장된 키의 첫 4워드로 복사

- 추가되는 워드 w[i]는 직전 워드 w[i-1]와 4개 이전 워드 w[i-1]에 의해 결정

    > 이전 4워드 중 3개는 단순 XOR

    > 첫 번째 워드에서는 4번째 XOR을 수행하기 전에, 순환이동, S-Box, 이전 라운드 상수와의 XOR연산 수행

 

#키 확장 원리

 

#AES 복호화

 

#AES 구현