NUMBER THEORY FINITE FIELDS
groups이란 우리말로 군, 군체를 말한다. group으로 구분지어 나누는 것은 앞으로 나올 개념을 적용시키는데 중요하다. 군체를 이루는 집합에서 임의의 원소 a, b에 대해서 2항 연산을 " · " 이라고 할때 group(G)으로 분류되려면 아래의 4가지 조건을 만족해야 한다. 이 중에서 5번까지 모두 만족시키는 group를 Abelian Group이라고 한다.
- A1: Closure
a, b가 G의 원소 일때, a · b 또한 G의 원소이다.
- A2: Associative
a, b, c가 G의 원소 일때, a · (b · c) = (a · b) · c를 만족한다.
- A3: Identity Element
a가 G의 원소 일때, a · e = e · a 를 만족시키는 원소 e가 G에 존재한다.
- A4: Inverse Element
a가 G의 원소이고 e가 Identity Element일 때, a · b = b · a = e 를 만족시키는 원소 b가 G에 존재한다.
- A5: commutative
a, b가 임의의 G의 원소 일때, a · b = b · a 를 만족한다.
Cyclic Group는 Group의 성질 5가지를 모두 만족하는 Abelian group중에서 G의 모든 원소가 반복적인 2항 연산을 " · "을 했을때 나오는 group를 말한다. 예를 들면 
는 G = { x | x 는 1, 2, ..., 18}에 대해서 cyclic group을 만족한다.
group가 한가지 연산을 가지고 몇가지 성질을 만족하는 집합이라면, Field는 두가지 연산을 두고 조건을 만족하는 집합을 말한다. Field(F)를 만족하기 위해서는 아래와 같은 조건을 만족해야 한다.
- A1-A5
Abelian group을 만족한다.
- No Zero Divisors
a, b가 F의 원소 일때, ab = 0이면 a = 0 또는 b = 0이다.
- Distrubutive Law
분배법칙이 성립한다.
즉 원론적으로 field는 덧셈, 뺄셈, 나눗셈, 곱셈이 해당 집합을 벗어나지 않고 연산이 가능한 집합을 말한다. 유리수, 실수, 복소수 집합은 field이다. 하지만 정수는 곱셈에 대해서 group을 이루지 못하여 field에 해당하지 않는 집합이다.
field에는 복소수, 유리수처럼 원소가 유한하게 많은 field가 있다. 이에 대비되는 field로 원소의 갯수가 유한한 갯수를 갖는 집합이 있다. 17세기의 프랑스 수학자 에바리스트 갈루아가 finite field를 정의해다. 이런 finite field 중에는 원소의 갯수가 prime p에 의해서 정해진다. 이를 갈루아의 이름을 따서 GF(p)와 GF(
)로 구분지을 수 있다.
Addition modulo 7 & Multiplication modulo 7 & Additive and multiplicative inverses modulo 7
위의 경우는 [{0, 1, 2, 3, 4, 5, 6}, + mod7, * mod 7]로 정의 할 수 있는 GF(7)이다.
prime field vs binary field ()
DES나 AES-128등의 cipher 방식은 64bits, 128bits의 길이를 갖는 key를 이용한다. 이는 모두 binary의 exponential의 형태이다. 따라서 prime field를 이용할 때와 binary key를 이용하는 것에는 큰 차이가 생긴다. AES-256의 예를 들어 설명해보자. AES-256은 256bits의 길이를 갖는 key를 이용하여 암호화하는 체계이다. 256bits의 key는 8bits 단위로 16묶음으로 나뉘어져 처리되는데 finite field의 크기가 binary형태가 아니라면 자료가 갖는 bits의 형태가 유지되지 못한다. Binary field를 이용하면 현대 컴퓨터가 갖는 특징을 잘 반영할 수 있다는 장점이 있다.
polynomial arithmetic modulo (
) over GF(
) addition & multiplication
정수에서 적용하던 유클리드 알고리즘을 다항식(polynomial)에 적용하는 방법이다. 따라서 finite field에 대해 적용하려면 modulo에 들어가는 다항식은 정수의 prime과 같이 irreducible이어야 한다. 즉 정수부분에서 인수분해가 불가능해야한다. 이때 다항식에 대한 modular reduction은 계수를 modulo 2를 적용하여 구할 수 있다. 또한 -1은 modulo2에 대해서 1과 동치이므로 -1은 +1로 표기한다. 예시를 들어보자면 
, 
과 같은 결과를 얼을 수 있다.
위 두 표는 같은 내용을 담고 있다. GF()으로 표기한 표의 숫자가 만약 6이라면 0b110을 뜻하고 이는 
을 뜻하고 3이라면 0b011을 뜻하고 이는 
를 뜻한다.
GF()에 대해서 additive와 muliplicative reserves를 모두 구하면 아래와 같다.
위에서 어렵고 복잡하게 설명되었던 모든 내용이 컴퓨터 위에서는 간단한 일련의 shift와 XOR연산으로 비교적 간단하게 구현가능하다.
을 계산하는 방법을 보자
라는 사실을 이용하면 다음과 같이 계산된다.
이를 컴퓨터의 가장 기본적인 연산인 shift와 XOR를 이용하면 아래와 같이 표현된다.
0b0101 X 0b0111 mod(0b1011)
1000 = 0011
101 X 001 = 101
101 X 010 = 010 XOR 011 = 001
101 X 100 = 010
101 X 111
= 101 X (001 XOR 010 XOR 100)
= 101 XOR 001 XOR 010
= 110
Extended Euclidean Algorithm for Binary Polynomials은 우선 정수 범위에서 사용하는 Extended Euclid 알고리즘을 binary polinomial으로 확장한 것이다. 다항식에서의 각 항을 binary표기법의 각 bit로 두어 계산하는 방식이다. 아래는 강의를 듣고 적은 과제를 위한 배경지식을 요약한 자료이다.
polynomial arithmetic modulo () over GF() addition & multiplication
정수에서 적용하던 유클리드 알고리즘을 다항식(polynomial)에 적용하는 방법이다. 따라서 finite field에 대해 적용하려면 modulo에 들어가는 다항식은 정수의 prime과 같이 irreducible이어야 한다. 즉 정수부분에서 인수분해가 불가능해야한다. 이때 다항식에 대한 modular reduction은 계수를 modulo 2를 적용하여 구할 수 있다. 또한 -1은 modulo2에 대해서 1과 동치이므로 -1은 +1로 표기한다. 예시를 들어보자면 , 과 같은 결과를 얼을 수 있다.
위 두 표는 같은 내용을 담고 있다. GF()으로 표기한 표의 숫자가 만약 6이라면 0b110을 뜻하고 이는 을 뜻하고 3이라면 0b011을 뜻하고 이는 를 뜻한다.
GF()에 대해서 additive와 muliplicative reserves를 모두 구하면 아래와 같다.
위에서 어렵고 복잡하게 설명되었던 모든 내용이 컴퓨터 위에서는 간단한 일련의 shift와 XOR연산으로 비교적 간단하게 구현가능하다.
을 계산하는 방법을 보자
라는 사실을 이용하면 다음과 같이 계산된다.
이를 컴퓨터의 가장 기본적인 연산인 shift와 XOR를 이용하면 아래와 같이 표현된다.
0b0101 X 0b0111 mod(0b1011)
1000 = 0011
101 X 001 = 101
101 X 010 = 010 XOR 011 = 001
101 X 100 = 010
101 X 111
= 101 X (001 XOR 010 XOR 100)
= 101 XOR 001 XOR 010
= 110
위에서 정리한 배경지식을 코드로 표현하였다.
"""
get_polynomial_str_from_binary
2진수로 표현된 binary polynomial을 polynomial representation으로 바꿈
For example, f(z) = z^5 + z^2 + 1 <=> f = 0b100101
"""
def get_polynomial_str_from_binary(f):
polys = []
for i, v in enumerate(reversed(bin(f)[2:])):
if v == '1':
polys.insert(0, (i, v))
return " + ".join(["z^{}".format(i) for i, v in polys])
def is_carry(a):
return a & 0x100
"""
multiple_binary_polynomial
the case of GF(2^8) and the number of bits of n is 9-bits. (e.g. AES)
"""
def multiple_binary_polynomial(a, b, n):
overflow = n & 0xff # pre-computation for mod operation (simple)
sub_multiples = [0] * 8 # pre-computation table for `a`
sub_multiples[0] = a
for digit in range(1, 8):
sub_multiples[digit] = sub_multiples[digit - 1] << 1
if is_carry(sub_multiples[digit]):
sub_multiples[digit] &= 0xff
sub_multiples[digit] ^= overflow
result = 0
for digit in range(8):
mask = 1 << digit
if b & mask != 0:
result ^= sub_multiples[digit]
return result
"""
get_degree_polynomials
이진 다항식의 계수(최고차항)을 구함
"""
m = 32 # 32bit
def get_degree_polynomials(bp):
for i in reversed(range(m)): # from m-1 down to 0
if (bp & (1 << i)) != 0:
return i
return 0
"""
my_shift
j만큼 v에 곱하는 함수
"""
def my_shift(a, j, v):
for _ in range(j):
v = v << 1
v ^= a
return v & 0xff
"""
extended_euclid_binary
return (d, g, h) such that a * g + b * h = d = gcd(a, b)
loop invariant :
a * g_1 + b * h_1 = u
a * g_2 + b * h_2 = v
"""
def extended_euclid_binary(a, b):
u, v = a, b
g_1, h_1 = 1, 0
g_2, h_2 = 0, 1
while u != 0:
degree_difference = get_degree_polynomials(u) - get_degree_polynomials(v)
if degree_difference < 0:
u, v = v, u
g_1, g_2 = g_2, g_1
h_1, h_2 = h_2, h_1
degree_difference = -degree_difference
u = my_shift(u, degree_difference, v)
g_1 = my_shift(g_1, degree_difference, g_2)
h_1 = my_shift(h_1, degree_difference, h_2)
return v, g_2, h_2
"""
Inversion for binary polynomials using extended euclidean algorithm
returns a^-1 mod n. (n should be irreducible.)
"""
def bin_inv(a, n):
d, g, h = extended_euclid_binary(a, n)
return g
if __name__ == "__main__":
print("deg(10) = {}".format(get_degree_polynomials(10)))
# f(z) = z^8 + z^4 + z^3 + z + 1. f(z) is irreducible.
print(get_polynomial_str_from_binary(0b100011011))
# the example on 4th slide
print(get_polynomial_str_from_binary(multiple_binary_polynomial(0b01010111, 0b10000011, 0b100011011)))
# Inversion test
d, g, h = extended_euclid_binary(128, 0b100011011)
print(d, "|", get_polynomial_str_from_binary(g), "|", get_polynomial_str_from_binary(h))
print(get_polynomial_str_from_binary(bin_inv(128, 0b100011011)))
print(get_polynomial_str_from_binary(multiple_binary_polynomial(128, 131, 0b100011011)))