## sbk.gf_util

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 ``` ```# This file is part of the sbk project # https://github.com/mbarkhau/sbk # # Copyright (c) 2019-2021 Manuel Barkhau (mbarkhau@gmail.com) - MIT License # SPDX-License-Identifier: MIT """Galois Field arithmetic functions.""" import typing as typ from . import gf_lut # https://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael's_finite_field # # x**8 + x**4 + x**3 + x + 1 (0b100011011 = 0x11B) # # Rijndael uses the characteristic 2 finite field with 256 elements, which can # also be called the Galois field GF(2**8). It employs the following reducing # polynomial for multiplication: # # For example, 0x53 * 0xCA = 0x01 in Rijndael's field because # # 0x53 = 0b01010011 # 0xCA = 0b11001010 # # (x6 + x4 + x + 1)(x7 + x6 + x3 + x) # = (x13 + x12 + x9 + x7) + (x11 + x10 + x7 + x5) + (x8 + x7 + x4 + x2) + (x7 + x6 + x3 + x) # = x13 + x12 + x9 + x11 + x10 + x5 + x8 + x4 + x2 + x6 + x3 + x # = x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x # and # # x13 + x12 + x11 + x10 + x9 + x8 + x6 + x5 + x4 + x3 + x2 + x # mod x8 + x4 + x3 + x1 + 1 # = (0b11111101111110 mod 100011011) = 0x3F7E mod 0x011B = 0x0001 # # , which can be demonstrated through long division (shown using binary # notation, since it lends itself well to the task. Notice that exclusive OR # is applied in the example and not arithmetic subtraction, as one might use # in grade-school long division.): # # 11111101111110 (mod) 100011011 # ^10001101100000 # 1110000011110 # ^1000110110000 # 110110101110 # ^100011011000 # 10101110110 # ^10001101100 # 100011010 # ^100011011 # 1 # The multiplicative inverse for an element a of a finite field can be calculated # a number of different ways: # # Since the nonzero elements of GF(p^n) form a finite group with respect to multiplication, # a^((p^n)−1) = 1 (for a != 0), thus the inverse of a is a^((p^n)−2). RIJNDAEL_REDUCING_POLYNOMIAL = 0x011B def div_slow(a: int, b: int) -> int: # long division val = a divisor = b assert divisor > 0 while divisor < val: divisor = divisor << 1 mask = 1 while mask < divisor: mask = mask << 1 mask = mask >> 1 while divisor > 0xFF: if (val & mask) > 0: val = val ^ divisor divisor = divisor >> 1 mask = mask >> 1 return val DIV_LUT: typ.Dict[int, int] = {} def div(a: int, b: int) -> int: assert 0 <= a < 65536, a assert b > 0, b key = a * 65536 + b if key not in DIV_LUT: DIV_LUT[key] = div_slow(a, b) return DIV_LUT[key] def div_by_rrp(val: int) -> int: return div(val, RIJNDAEL_REDUCING_POLYNOMIAL) def mul_slow(a: int, b: int) -> int: res = 0 while a > 0: if a & 1 != 0: res = res ^ b a = a // 2 b = b * 2 return div_by_rrp(res) def mul(a: int, b: int) -> int: assert 0 <= a < 256, a assert 0 <= b < 256, b mul_lut = gf_lut.MUL_LUT if not mul_lut: gf_lut.init_mul_lut() return mul_lut[a][b] def pow_slow(a: int, b: int) -> int: res = 1 n = b while n > 0: res = mul(res, a) n -= 1 return res def inverse_slow(val: int) -> int: """Calculate multiplicative inverse in GF(256). Since the nonzero elements of GF(p^n) form a finite group with respect to multiplication, a^((p^n)−1) = 1 (for a != 0) thus the inverse of a is a^((p^n)−2). """ if val == 0: return 0 exp = 2 ** 8 - 2 inv = pow_slow(val, exp) assert mul(val, inv) == 1 return inv def inverse(val: int) -> int: return gf_lut.MUL_INVERSE_LUT[val] # The Euclidean GCD algorithm is based on the principle that the # greatest common divisor of two numbers does not change if the larger # number is replaced by its difference with the smaller number. For # example, # # GCD(252) == 21 # 252 = 21 × 12 # GCD(105) == 21 # 105 = 21 × 5 # # also # # GCD(252 − 105) == 21 # GCD(147) == 21 # # Since this replacement reduces the larger of the two numbers, # repeating this process gives successively smaller pairs of numbers # until the two numbers become equal. When that occurs, they are the # GCD of the original two numbers. # # By reversing the steps, the GCD can be expressed as a sum of the two # original numbers each multiplied by a positive or negative integer, # e.g., 21 = 5 × 105 + (−2) × 252. The fact that the GCD can always be # expressed in this way is known as Bézout's identity. class XGCDResult(typ.NamedTuple): g: int s: int # sometimes called x t: int # sometimes called y def xgcd(a: int, b: int) -> XGCDResult: """Extended euclidien greatest common denominator.""" # pylint: disable=unpacking-non-sequence if a == 0: return XGCDResult(b, 0, 1) g, s, t = xgcd(b % a, a) q = b // a res = XGCDResult(g=g, s=t - q * s, t=s) assert res.s * a + res.t * b == res.g return res ```