코딩 더 매트릭스 - 2장 필드 (2)

필립 클라인의 저서 코딩 더 매트릭스 2장 필드 중 갈루아 필드

1. $GF(2)$를 알아보고 간단한 암호 체계에 적용해 봅니다.
2. 네트워크 코딩에 $GF(2)$를 적용한 예를 살펴봅니다.

$GF(2)$

$GF(2)$는 갈루아 필드를 간략하게 표현한 것입니다. $GF(2)$의 산술연산은 두개의 표로 요약할 수 있습니다.

덧셈의 결과는 $modulo 2$입니다. 따라서 각자릿수의 덧셈은 윗자릿수에 영향을 주지 않습니다. 뺄셈은 덧셈과 동일합니다. 1의 음수는 1, 0의 음수는 0입니다. 소스파일에서 Python에서 $GF(2)$의 연산을 사용할 수 있도록 GF2.py 파일을 제공하고 있습니다. 소스 코드를 살펴보면 대수의 사칙연산들을 모두 $GF(2)$의 정의에 맞게 오버라이드 하고 있습니다. 예를 들어 덧셈 연산 $+$는 다음과 같이 오버라이드 합니다.

class One:
	def __add__(self, other): return self if other == 0 else 0

아래는 몇가지 연산을 실행한 예시입니다.

>>> from GF2 import one
>>> one * one
one
>>> one + one
0
>>> one + 0
one
>>> 0 - one
one

$GF(2)$의 덧셈을 1장에서 살펴봤던 메시지 암호화에 적용해 보겠습니다. 앨리스와 밥이 $n$비트의 평문을 $n$비트의 키값으로 암호화 합니다. 예를 들어 평문이 $1010 1011$, 키값이 $0101 0011$이라면 암호문은 $1111 1000$가 됩니다. 밥은 앨리스가 보낸 암호문에서 키값을 뺌으로서 평문을 얻을 수 있습니다. 이 암호체계는 키값 중 하나의 비트라도 바뀌면 암호문이 바뀌므로 단사함수이면서 전사함수 입니다. 따라서 암복호는 서로 역함수이고 확률분포 상 균등합니다. 한편 이 암호체계는 키값을 모르더라도 brute force로 평문을 추정할 수 있습니다. $10101\text{ }00100\text{ }10101\text{ }01011\text{ }11001\text{ }00011\text{ }01011\text{ }10101\text{ }00100\text{ }11001\text{ }11010$ 위와 같은 암호문이 주어지고 5비트의 각 시퀀스는 알파벳에 매핑된다고 가정해 보겠습니다. 암호문을 풀기위한 프로시저가 다음과 같은 순서를 따르면 좋을 것 같습니다.

1. 암호문의 한 시퀀스(5비트)를 $GF(2)$로 변환합니다.
2. 시퀀스에서 키값 후보를 뺍니다

3. 뺄셈연산한 결과가 26

   • 미만이라면 알파벳 a의 ascii값인 97을 더해 추정 문자열에 concat합니다.
   • 이상이라면 띄어쓰기 문자를 추정 문자열에 concat합니다.
4. 각각의 시퀀스에 대해 3의 과정을 반복합니다.
5. 각각의 키값 후보에 대해 2 ~ 4 과정을 반복합니다.

아래는 위의 과정을 코드로 옮긴 것입니다.

from GF2 import one


# 십진수를 이진수로 변환하는 과정입니다.
# 다만 2로 나눈 나머지가 1일 경우 GF2 의 one을 사용합니다.
def int_to_GF(num):
    l = []

    while num != 0:
        if num % 2 == 1:
            l.append(one)
        else:
            l.append(0)
        num //= 2
    while len(l) < 5:
        l.append(0)
    return list(reversed(l))


# GF(2) 의 one과 0로 이루어진 배열을 십진수로 변환한 뒤
# a의 ascii 값 97을 이용해 문자를 구합니다.
def GF_to_char(gf):
    num = 0
    i = 0

    while i < 5:
        num += 0 if gf[i] == 0 else 2 ** (4 - i)
        i += 1
    return chr(num + 97) if num < 26 else ' '


# GF2 의 뻴셈연산
def substract(a, b):
    return [x - y for x, y in zip(a, b)]

encrypted = [0b10101, 0b00100, 0b10101, 0b01011, 0b11001, 0b00011, 0b01011, 0b10101, 0b00100, 0b11001, 0b11010]

for i in range(32):
    str_ = ''
    key = int_to_GF(i)
    for c in encrypted:
        c_to_gf = int_to_GF(c)
        ch = GF_to_char(substract(c_to_gf, key))
        str_ += ch
    print('key: ', key, '평문: ', str_)

책의 예시이기도 한 위 암호문을 풀기위해 코드를 실행하면 다음과 같은 결과를 보여줍니다.

...
key:  [0, one, one, 0, one] 평문:  yjyguogyjux
key:  [0, one, one, one, 0] 평문:   k fxnf kxu
key:  [0, one, one, one, one] 평문:   l ewme lwv
key:  [one, 0, 0, 0, 0] 평문:  fuf jt fujk
key:  [one, 0, 0, 0, one] 평문:  eve is evil	# 평문으로 추정됨
key:  [one, 0, 0, one, 0] 평문:  hwhzlrzhwli
key:  [one, 0, 0, one, one] 평문:  gxgykqygxkj
key:  [one, 0, one, 0, 0] 평문:  bqb nx bqno
...

네트워크 코딩

위 그래프에서 노드 $S$는 데이터 $p_1$과 $p_2$를 노드 $d_1$과 $d_2$에게 전달해야 합니다. 라우팅 노드 $r_n$은 한번에 하나의 데이터만 처리할 수 있습니다. 만약 $r_3$가 $p_1$을 받게 되면 $d_1$는 $p_2$를 받을 수 없습니다. 두 개의 데이터를 전달하려면 한 데이터를 먼저 전달한 후 다음 데이터를 전달해야 하는데 이때 지연 시간이 발생합니다. 왼쪽 그래프는 그 상황을 잘 보여주고 있습니다. $GF(2)$를 적용하면 이 문제를 해결할 수 있습니다. 네트워크 노드들은 약간의 계산을 할 수 있습니다. 라우팅 노드 $r_3$ 는 간단한 덧셈으로 데이터 $p_1$과 $p_2$를 이용해 $p_3 = p_1 + p_2$을 만들어 이후 노드들에게 전달합니다. 최종 노드 $d_1$과 $d_2$는 뺄셈을 이용해 자신이 가지지 못했던 데이터를 얻을 수 있습니다. 이런 개념을 네트워크 코딩이라고 합니다.