Group, Finite Fields, Polynomial GCD, 다항식을 bit string으로 계산

Groups(G)

• : 집합과 연산(·) 한 가지를 합쳐서 정의
• 연산(·)이 덧셈인 경우 additive group이라고 부른다. 곱셈인 경우 multiplicative group.
• Group은 하단의 A1~A4의 성질을 만족한다..
  • (A1) Closure
    • a와 b가 G에 속하면, a·b는 G에 속한다.
    • 집합의 원소와 관계가 있는 원소가 항상 그 집합에 속한다는 성질
  • (A2) Associative(결합 법칙)이 성립
    • a·(b·c)=(a·b)·c  for all a, b, c in G
  • (A3) Identity element(항등원)이 존재
    • a가 G에 속할 때, a·e = e·a = a라면 e는 G에 속한다.
    • 항등원 e를 가지는 것
  • (A4) Inverse element(역원)이 존재
    • 각 a가 G에 속할 때, a·$a^{-1}$ = $a^{-1}$·a = e를 만족하는 G에 속하는 $a^{-1}$가 있다.
    • 즉, 역원 $a^{-1}$을 가진다.
• Abelian group
  • (A5) Commutative(교환 법칙)이 성립하는 그룹
    • a·b = b·a for all a, b in G
• 이러한 그룹이 유한개의 원소로 이루어져 있다면 -> finite group / 무한개로 이루어졌다면 -> infinite group

 

Cyclic Group

• 그룹 연산자를 반복하여 exponentiation을 정의
  • $a^3$ = a·a·a
  • 위 경우는 연산자를 곱셈으로 본 것
• $a^0$ = e를 항등원이라고 정의한다.
• $a^{-n}$ = $(a')^n$인 a'는 그룹 내 a의 역원이라고 정의한다.
  • $a^{-n}$을 a의 역원인 $a^{-1}$의 n승으로 나타낼 수 있다. -> $(a^{-1})^n$ 
• Cyclic Group: G에 속하는 어떤 원소 a가 $a^k$형태로 G의 모든 원소들을 나타낼 수 있으면, 해당 그룹을 Cyclic group이라고 부른다.
  • 여기서 a는 G를 generate 한다고 하고, a를 G의 generator라고 부른다.
• cyclic group은 항상 abelian이고 finite 또는 infinite하다.
  • cyclic group은 항상 교환 법칙이 성립함.

• 위 사진을 예로 들어보자.
• Modulo 19이기 때문에 Group은 {0, 1, ..., 18}이 된다.
• a가 2인 경우, $a^k$형태로 Group에 속하는 모든 값들을 표현할 수 있으므로 2를 G의 generator라고 할 수 있다.

  

 

Fields

• 집합과 두 가지 이진 연산(덧셈, 곱셈)을 정의
• field는 {F, +, *}로 표현한다.
• field는 다음의 공리를 만족한다.
  • (A1~A5)
    • 덧셈과 곱셈에 대해 abelian group(교환 법칙 성립)이 된다.
    • 즉, 사칙연산이 잘 구해지는 구조이다.
    • 예:
      • a+b -> a-(-b)
        • 뺄셈은 덧셈에 대한 항등원을 더하는 것과 같다.
      • a/b -> a*$b^{-1}$ 
        • 나눗셈이란 곱셈에 대한 역원을 곱하는 것과 같다.
  • No zero divisors
    • a, b가 F에 속하고 ab=0이면 a=0 또는 b=0이다.
  • Distributive law(분배 법칙)
    • a·(b+c) = a·b+a·c
• 즉, Field란 덧셈과 곱셈에 대해 각각 group이면서 분배 법칙이 되는 것!
• 주의! 
  • 모든 정수의 집합은 field가 아니다. 왜냐하면, 모든 원소가 곱셈의 역원을 가지는 것이 아니기 때문이다.
    • "곱셈의 역원을 가진다" => [a*a mod n =1]를 성립해야 함. 
    • 위 문장이 성립하려면 a와 n이 서로소 이어야 한다. 
  • 예: 3의 덧셈에 대한 역원 -3은 정수들의 집합에 들어 있지만, 3의 곱셈에 대한 역원인 1/3은 집합에 들어가지 않는다.

 

Field 타입

 

Finite Field = Galois Field(GF)

• GF(p): Prime field 
  • 원소의 개수가 소수 개다.
• GF($p^2$): Binary field
• finite field가 되려면 유한한 원소의 개수가 $p^n$ 형태로만 된다. 
  • 예: [GF(15) -> 원소 개수가 15개인 finite field]는 존재하지 않는다. 

 

 

덧셈(-W)에 대해서는 역원이 항상 존재하지만,

곱셈($W^{-1}$)에 대해서는 역원이 항상 존재하지는 않는다.

 

 

역원이 언제 존재하는가?

• 역원을 구하려는 원소가 mudulo와 서로소가 되면 역원이 존재한다.
• 모든 원소가 역원이 존재하게 하려면 modulo가 소수이면 된다.
• modulo가 소수이면 모든 원소와 서로소이기 때문

 

 

덧셈, 곱셈에 대해 닫혀있고(A1)

결합 법칙 성립하고(A2)

항등원 1을 모두 가지고(A3)

0을 제외한 모든 원소가 역원을 가진다(A4)

-> 덧셈에 대해서도 곱셈에 대해서도 group이다.

 

교환 법칙도 성립한다.

ex) 3+5 mod 7 = 5+3 mod 7

-> Abelian group이기도 하다.

 

 

또한 분배 법칙도 성립한다. 

-> 즉, Field일 모든 조건을 만족한다. {0, 1, ..., 6}인 이 집합은 덧셈 또는 곱셈 mod 7에 대해 field가 되고, 원소가 7개로 유한하기 때문에 finite field가 된다.

 

 

Finite field: Prime field vs Binary Field

• GF($p^n$) 
• Prime field: n=1인 GF($p$)
  • 공개 키(public key) 암호에서 많이 쓰임
• Binary Field: p=2인 GF($2^n$)
  • 소수를 2로 고정
  • AES에서 사용

 

왜 Binary Field를 쓰는가?

• 예를 들어, plaintext 64bit가 들어왔다고 하자.
• 보통 이것을 8 bit 단위로 잘라서 round function을 돌리게 된다.
• 8bit는 00000000 ~ 11111111로 256가지의 조합이 된다.
• 만약 이것을 prime field로 다루게 하려면
  • 위 범위(8 bits)에 있는 값을 가지고 (mod p)연산을 해서 결과를 얻게 된다.
  • 이 modulus가 될 수 있는 숫자는 소수이기 때문에, 0 ~ 255을 다 다룰 수 없다.
    • 256이 소수가 아니기 때문
  • modulus가 소수가 되게 하려면 257이 돼야 하는데, 그러면 00000000부터 100000000(256)까지의 숫자를 다뤄야 한다. 즉, 우리가 익숙해 있는 binary data 구조와 맞지 않다.
  • 즉, 우리가 원하는 것은 데이터가 정확히 0부터 255까지(256 종류)를 가지고 연산을 하고 싶은 것.
    • 그러려면 modulus가 256이어야 한다. 하지만 256은 소수가 아니기 때문에 prime field가 안된다.
    • 하지만 256은 $2^8$로 표현할 수 있다. 즉, 원소의 개수가 256개짜리 finite field가 존재하는 것은 확실
• 이렇게 binary field형식을 사용하면 prime field처럼 modular연산이 어려워진다. 이를 위해 polynomial 연산을 사용한다.

 

Polynomial Division

• f(x) = q(x)g(x) + r(x)
  • r(x): f(x)를 g(x)로 나눈 나머지
  • r(x) = f(x) mod g(x)
• r(x)가 0이라면
  • g(x)|f(x)
  • g(x)를 f(x)의 factor(인자) 또는 divisor(약수)라고 할 수 있다.
• 다항식(polynomial) f(x)
  • "어떤 다항식 f(x)가 field에 대해 irreducible하다"의 뜻은 다음과 같다.
  • f(x)가 자기보다 작은 차수인 두 다항식의 곱으로 표현될 수 없다는 뜻
  • 이 성질(irreducible polynomial)은 소수랑 비슷한 느낌이라 prime polynomial이라고도 부른다.

 

Polynomial GCD

• [GCD(a(x), b(x)) = c(x)]의 조건
  • c(x)는 a(x)와 b(x) 둘 다 나눈다.
  • a(x)와 b(x)의 모든 공약수는 c(x)의 약수이다.
• Extended Euclidean algorithm을 이용하면 irreducible polynomial의 역원을 찾을 수 있다.
• GF(2)이므로 모든 연산에 (mod 2)가 취해진다.
  • (mod 2)를 취하면
  • a+b (mod 2) = a-b (mod 2)이고, 이는 a XOR b와 같다.
  • 즉, x와 -x가 같음
  • 예: 3 mod 2 =1, -3 mod 2 = 1
  • 예2: 3+5 mod 2 = 1 -> (011 xor 101) mod 2 = 110 mod 2 = 1
• Extended Euclidean algorithm의 자세한 설명 및 풀이: 

2020/10/22 - [Computer Security] - 역원 구하기 - Euclidean Algorithm / Extended Euclidean Algorithm

 

 

 

 

modulus가 다항식인 경우 다음과 같이 연산할 수 있다.

 

• 덧셈은 XOR과 같기 때문에 자기 자신과 더하면 항상 0이다.
• modulo ($x^3+x+1$) -> modulus가 3차 항이므로 GF(3)이다.
• 다항식 주변에 보이는 bit에 주목해보자.
  • 다항식의 계수가 1 또는 0이라면 사진에 나와있는 것과 같이 다항식을 bit string으로 표현할 수 있다.
    • 예: $x^3+x+1 $ = 1011
  • 곱셈에 대해 연산할 때, 다항식을 bit string으로 변환 후, shift와 XOR 연산하여 결과를 구할 수 있다.
    • 예:

다항식 형태 그대로 계산한 방법

다항식을 bit string으로 변환 후 푸는 방법

 

 

출처:

- [Cryptography and Network Security: Principles and Practices]