juliusgeo/binary_finite_field_arithmetic.py

## binary_finite_field_arithmetic.py
from dataclasses import dataclass
from functools import reduce

@dataclass
class bff:
    """
    An implementation of binary finite field arithmetic on fields of order 2^n using integers and bitwise operators.


    Adaptation of algorithms in:
        https://en.m.wikiversity.org/wiki/Reed–Solomon_codes_for_coders
        https://gist.github.com/matejker/e88719bf5fd0e0e41eeeaa917a0ff583
    """
    a: int  # our polynomial
    n: int  # the value 2^n
    r: int  # an irreducible polynomial over GF(2^n)

    def __add__(self, other):
        return bff(self.a ^ other.a, self.n)

    # russian peasant multiplication algorithm
    def __mul__(self, other):
        x, y, r = self.a, other.a, 0
        while y:
            r = (r, r ^ x)[y & 1]
            y >>= 1
            x <<= 1
            x = (x, x ^ self.r)[bool(x & (self.n))]
        return bff(r, self.n, self.r)

    # fermat's lil theorem
    def __pow__(self, pow: int):
        prod = bff(1, self.n, self.r)
        while pow != 0:
            if pow & 1:
                prod *= self
            pow >>= 1
            self *= self
        return prod

    def __invert__(self):
        return self ** (self.n-2)

    def __truediv__(self, other):
        return self * ~other

    def __len__(self):
        return int.bit_length(self.a)

    def __repr__(self):
        return f"element polynomial: {self.a}, GF(2^{self.n}), irreducible polynomial: {self.r}"

    def affine(self, affine_mat, affine_c):
        multiplicand = [int(i) for i in list(bin(self.a)[2:])][::-1]
        res = [sum([(i * n) for i, n in zip(row, multiplicand)])%2 for row in affine_mat]
        res = [(i+j)%2 for i, j in zip(res, affine_c)][::-1]
        return bff(reduce(lambda x, y: 2*x+y, res), self.n, self.r)


def aff_from_col(col):
    aff = [col]
    for a in col[::-1]:
        col = [a] + col[:-1]
        aff.append(col)
    return list(zip(*aff))


def generate_s_box():
    return list(zip(*[['0x%02x' % (~bff((i<<4)+j, 256, r=0b100011011)).affine(aff_from_col([1, 1, 1, 1, 1, 0, 0, 0]), [1, 1, 0, 0, 0, 1, 1, 0]).a for i in range(0x0, 0x10)] for j in range(0x0, 0x10)]))


def generate_inv_s_box():
    return list(zip(*[['0x%02x' % (~(bff((i<<4)+j, 256, r=0b100011011).affine(aff_from_col([0, 1, 0, 1, 0, 0, 1, 0]), [1, 0, 1, 0, 0, 0, 0, 0]))).a for i in range(0x0, 0x10)] for j in range(0x0, 0x10)]))


# helper functions
def pprint_box(box):
    print("   ", )
    axis = ['0x%02x' % i for i in range(0x0, 0x10)][::-1]
    print("     ", ', '.join(axis[::-1]))
    for row in box:
        print(axis[-1] + ",", ', '.join(row))
        axis.pop(-1)


if __name__ == "__main__":
    pprint_box(generate_s_box())
    pprint_box(generate_inv_s_box())
	from dataclasses import dataclass
	from functools import reduce

	@dataclass
	class bff:
	"""
	An implementation of binary finite field arithmetic on fields of order 2^n using integers and bitwise operators.


	Adaptation of algorithms in:
	https://en.m.wikiversity.org/wiki/Reed–Solomon_codes_for_coders
	https://gist.github.com/matejker/e88719bf5fd0e0e41eeeaa917a0ff583
	"""
	a: int # our polynomial
	n: int # the value 2^n
	r: int # an irreducible polynomial over GF(2^n)

	def __add__(self, other):
	return bff(self.a ^ other.a, self.n)

	# russian peasant multiplication algorithm
	def __mul__(self, other):
	x, y, r = self.a, other.a, 0
	while y:
	r = (r, r ^ x)[y & 1]
	y >>= 1
	x <<= 1
	x = (x, x ^ self.r)[bool(x & (self.n))]
	return bff(r, self.n, self.r)

	# fermat's lil theorem
	def __pow__(self, pow: int):
	prod = bff(1, self.n, self.r)
	while pow != 0:
	if pow & 1:
	prod *= self
	pow >>= 1
	self *= self
	return prod

	def __invert__(self):
	return self ** (self.n-2)

	def __truediv__(self, other):
	return self * ~other

	def __len__(self):
	return int.bit_length(self.a)

	def __repr__(self):
	return f"element polynomial: {self.a}, GF(2^{self.n}), irreducible polynomial: {self.r}"

	def affine(self, affine_mat, affine_c):
	multiplicand = [int(i) for i in list(bin(self.a)[2:])][::-1]
	res = [sum([(i * n) for i, n in zip(row, multiplicand)])%2 for row in affine_mat]
	res = [(i+j)%2 for i, j in zip(res, affine_c)][::-1]
	return bff(reduce(lambda x, y: 2*x+y, res), self.n, self.r)


	def aff_from_col(col):
	aff = [col]
	for a in col[::-1]:
	col = [a] + col[:-1]
	aff.append(col)
	return list(zip(*aff))


	def generate_s_box():
	return list(zip(*[['0x%02x' % (~bff((i<<4)+j, 256, r=0b100011011)).affine(aff_from_col([1, 1, 1, 1, 1, 0, 0, 0]), [1, 1, 0, 0, 0, 1, 1, 0]).a for i in range(0x0, 0x10)] for j in range(0x0, 0x10)]))


	def generate_inv_s_box():
	return list(zip(*[['0x%02x' % (~(bff((i<<4)+j, 256, r=0b100011011).affine(aff_from_col([0, 1, 0, 1, 0, 0, 1, 0]), [1, 0, 1, 0, 0, 0, 0, 0]))).a for i in range(0x0, 0x10)] for j in range(0x0, 0x10)]))


	# helper functions
	def pprint_box(box):
	print(" ", )
	axis = ['0x%02x' % i for i in range(0x0, 0x10)][::-1]
	print(" ", ', '.join(axis[::-1]))
	for row in box:
	print(axis[-1] + ",", ', '.join(row))
	axis.pop(-1)


	if __name__ == "__main__":
	pprint_box(generate_s_box())
	pprint_box(generate_inv_s_box())