[Cryptography] 3. Basic Design Ideas for One-Key Cipher

One Key Cipher 시스템을 이해하기 위해서, 반드시 잘 숙지해야 할 개념들이다. 

 

◉ Abelian Group

 

앞서 잠깐 Abelian group에 대해서 간략하게 공부하였는데, 정의를 다시 내려보자.

 

Abelian group : 어떤 집합 A의 원소들이, 단항연산자 ✤ 에 대해서 아래 규칙을 만족하면, Abelian group 이라고 하자. 

 

1. 모든 원소들은 ✤ 에 대해 닫혀있다.

2. 모든 원소들은 ✤에 대한 결합법칙이 성립한다.

3. 모든 원소들은 ✤에 대한 교환법칙이 성립한다.

4. ✤에 대한 항등원이 존재한다.

5. ✤에 대한 역원이 존재한다.

 

위 다섯가지 규칙을 만족하는 집합 A에 대해서, (A,✤) 을 finite Abelian group이라고 정의한다.

 

e.g) Abelian group 의 예시 :  p가 소수인 Zp={0,1,2,...p-1} 에서 (Zp,✪p) 

 - (✪p 는 modulo addition p 연산, 예를들어 2✪p3= 2+3(modp) )

이때 항등원은 0 이된다. 

 

❖ 암호학에서 자주 쓰이는 Abelian Group 

자주 쓰이는 Abelian Group 

 

1. Linear & non Linear Function

 어떤 함수 f의 정의역과 공역이 모두 Abelian Group (A,✤) ->(B,✥)  이고, 다음을 만족하면, f는 linear 하다.

 

모든 x,y ∈ A에 대해서,  f(x✤y) = f(x)✥f(y) 

 

또, linear 함수 f에 대해서, g=f+b (b는 상수) 를 만족하는 함수 g 를 Affine Function 이라고 한다.

 

Affine function 예시 : g = x1 + x2+ x3+ x4 + 1; 

 

non Linear function은 affine이 아닌 function이다.

 

non linear function 예시 : f(x1,x2,x3,x4) = x1 + x2 + x3 + x4 +x1x2x3x4 (더하기와 곱셈은 modular 2연산이라고 가정할때) 

 

암호학에서는 마치 사람이 뼈 와 살이라는 너무나도 다른 물질로 구성되듯이, linear 과 non linear 이 모두 쓰인다.

 

2. Shannon’s confusion and diffusion

 

- Diffusion : Plaintext(Message) 이나 key(암호)를 한 bit 바꿨을때, Ciphertext(암호문) 이 달라지는 정도

 

위키피디아에서는, Plaintext와 Ciphertext 와의 관계를 감추기 위한 성질이라고 한다.

 

당연하지만 diffusion이 클수록, 암호의 보안은 높아진다. Diffusion을 AES 에서는 Mixed Column 연산을 사용하여 구현하였으며, diffusion 자체는 Linear function의 특성을 사용하여 구현한다.

 

- Confusion : Confusion means that each binary digit (bit) of the ciphertext should depend on several parts of the key, obscuring the connections between the two. 즉, Ciphertext의 한 bit가 여러 key bit에 의해 결정

 

위키피디아에서는, Ciphertext 와 Key 와의 관계를 감추기 위한 성질이라고 한다.

 

Plaintext 한 블럭, Ciphertext 한 블럭을 가지고있을때, 한블럭이 128 비트라고 가정하면, 128개의 Equation이 있다. 만약, 이 128개의 Equation을 해커가 다 알고있을때, 연립방정식을 쉽게 풀어서 답을 찾아낸다면, 함수는 Confusion이 나쁘다고 볼 수 있다.

 

즉, 해커가 연립방정식을 못풀게 하는것이 목표이므로, Confusion은 Non linear 함수를 사용해서 구현한다.

3. Basic design ideas of one-key ciphers

 

- 암호화 함수 Ek 와 복호화 함수 Dk 는, 다음과 같은 성질을 만족해야 이상적이다.

 

 a. Diffusion 과 Confusion이 좋다.

 b. Software, Hardware 에서 execution 및 implementation이 빠르다.

 

위 두 원칙을 실현하기 위해서, 함수는 다음과 같은 구조를 따르며, 이는 대부분의 암호/복호 화 함수들의 구조이다.

 

✥ 간단한 함수 fk() 에 대해서,

 

가장 많이쓰이는 암호화 함수의 구조

이때 kn 은 원본 key를 key expand algorithm에 의해서 만들어낸 개별 라운드 binary string 들이고, 다음 게시물에서 다룬다.

 

위 구조는,

사람이 적으로부터 내 몸을 방어해야되는데, 성능 좋은 방어구가 없어서, 싸구려 셔츠를 매우 많이 겹쳐입는 구조에 비유할 수 있다.

 

4. The finite field GF(2^8).

 

GF(2) 의 GF 는 galois finite field 의 약자로, 유한개의 원소를 갖는 finite field 로, 내부에서 대수적 구조를 형성할 수 있는 group이다.

 

AES에서 써먹을 GF(2^8) 에대해서만 살펴보면,

 

GF(2^8)

 

위와 같으며, 원소는 a0...a7 이 0또는 1 이라는 값을 가질수 있다고 할때 2^8개의 원소가 있는 것을 알 수 있다.

 

 

이 GF(2^8)은, addition 에대해 닫혀있음은 자명하고,

 

아래와 같은 p(x), 다항식에서 소수같은(인수분해가 안되는)

 

 

modular p(x) multiplication에 대해서도 닫혀있다. 

 

따라서 (GF(2^8),+,x) 인데,

 

y ∈ GF(2^8) 일때, 아래 식은 GF(2^8)->GF(2^8) 일대일 대응인 non linear함수다. 

 

 

위 식은 AES 에서 non linearity를 확보하는데 사용되는 중요한 함수로, AES의 각 Round에서 Switching byte 연산을 할때 필요한 함수이다.