Cryptography and Network Security-Ch4

Mathematics of cryptography Part 2: Algebraic Structure

4.1 Algebraic Structure
●five property:
   ●closure (封閉性)
   ●associativity (結合性)
   ●commutativity (交換性)
   ●existence of identity：和任意element 做運算，結果＝那個element。e.g.：加法下的0
   ●existence of inverse：自己和inverse做運算，結果＝ identity
 1. Groups: set of element + operation   (滿足property 1 2 4 5)
    e.g. G = <Zn, +>
   ●Abelian group：滿足交換性
   ●subgroup：subgroup裡的element均屬於group，operation 結果也相同
   ●cyclic subgroup：可以用element的power產生出來
 

※Lagrange' s theorem：H是G的subgroup，
order of H 是order of G的因數
 ●order of a group：產生cycle的最高項
  e.g. G = <Z10*, x>
    ord(1) = 1
    ord(3) = 4
    ord(7) = 4
    ord(9) = 2
  group order：2


  2. Rings：R = <{}, ├, ┤>
     {}為set
     ├ 為operation 1 滿足property 1 2 4 5
     ┤ 為operation 2 滿足property 1 2


  3. Fields：F = <{}, ├, ┤>
     {}為set
     ├ 為operation 1 滿足property 1 2 4 5
     ┤ 為operation 2 滿足property 1 2 3 4 5
    (├的identity 在┤不可有inverse)
  ●Galois Field：GF(p ^n)
    p is prime



4.2 GF(2^n) fields
  ●可以用n-1 degree 的polynomial 表示
   f(x) = a_n-1 x^n-1  + a _n-2 x^n-2+...+a₀x⁰
   e.g. GF(2²)：f(x) = 1x + 0
                                    0      0
                                    0      1
                                    1      1
  ●addition = subtraction = bit-wise XOR
  ●multiplication：相乘結果需用modulus polynomial (irreducible polynomial)去reduce (除以irreducible polynomial取餘數)
  ●inverse of polynomial：
    利用Euclidean algorithm 或將所有table generate出來
    e.g. inverse of x5 modulo x8 + x4 + x3 + x + 1

  ●相乘algorithm：
    e.g. P1 = 000100110, P2 = 10011110, modulus = 100011010

    P2每次向左shift一次
    當上次結果最高位為1時再和modulus做XOR(較低8位)
,   最後將P1為1的那一個結果做XOR (圖中話底線的)
 
 

  ●利用generator 去定義elements of GF(2ⁿ)
{0, g⁰, g¹, g², ..., g^N}, where N = 2ⁿ-2