boolcrypt.utilities module

Basic utilities of boolcrypt.

boolcrypt.utilities.get_smart_print(filename)

Return a print-like function.

boolcrypt.utilities.get_rijndael_field(name='a')

Return the finite field used in AES

>>> get_rijndael_field().modulus()
x^8 + x^4 + x^3 + x + 1

boolcrypt.utilities.matrix2poly(bin_matrix, field=None, poly_ring=None)

Return the linearized polynomial given by the binary matrix.

>>> matrix2poly(sage.all.identity_matrix(GF(2), 4), GF(2**4))
x
>>> # See In How Many Ways Can You Write Rijndael?
>>> entries = [
... [1, 0, 0, 0, 1, 1, 1, 1], [1, 1, 0, 0, 0, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1, 1], [1, 1, 1, 1, 0, 0, 0, 1],
... [1, 1, 1, 1, 1, 0, 0, 0], [0, 1, 1, 1, 1, 1, 0, 0], [0, 0, 1, 1, 1, 1, 1, 0], [0, 0, 0, 1, 1, 1, 1, 1]]
>>> bin_matrix = sage.all.matrix(GF(2), 8, 8, entries)
>>> ct = get_rijndael_field().fetch_int(vector2int([1, 1, 0 ,0, 0, 1, 1, 0]))
>>> poly = matrix2poly(bin_matrix, get_rijndael_field()) + ct
>>> poly
143*x^128 + 181*x^64 + x^32 + 244*x^16 + 37*x^8 + 249*x^4 + 9*x^2 + 5*x + 99
>>> [hex(c.integer_representation()) for c in poly.coefficients()]  # [ct term, ..., leading coeff]
['0x63', '0x5', '0x9', '0xf9', '0x25', '0xf4', '0x1', '0xb5', '0x8f']

Sources:

• https://ask.sagemath.org/question/40008/how-can-we-make-the-aes-s-box-using-lagrange-interpolation/

boolcrypt.utilities.matrix2anf(bin_matrix, bool_poly_ring=None, input_vars=None, bin_vector=None)

Return the ANF (the canonical components) of a given matrix.

If bool_poly_ring is given, the list input_vars can be given as a list of Boolean variables, strings or input variable indices. Otherwise, input_vars is given as a a list of Boolean variables.

>>> anf = matrix2anf(sage.all.identity_matrix(GF(2), 4, 4), bin_vector=[0, 1, 0, 1])
>>> for p in anf: print(p)
x0
x1 + 1
x2
x3 + 1
>>> bool_poly_ring = BooleanPolynomialRing(names=('a','b','c','d','y0','y1','y2','y3'))
>>> a, b, c, d, y0, y1, y2, y3 = bool_poly_ring.gens()
>>> symbolic_matrix = sage.all.matrix(2, 2, [[a, b], [c, d]])
>>> symbolic_matrix
[a b]
[c d]
>>> anf = matrix2anf(symbolic_matrix, bool_poly_ring, input_vars=[y0, y1, y2, y3])
>>> for p in anf: print(p)
a*y0 + b*y1
c*y0 + d*y1

boolcrypt.utilities.matrix2lut(bin_matrix, bin_vector=None)

Return the LUT of a given matrix.

>>> matrix2lut(sage.all.identity_matrix(GF(2), 4, 4), bin_vector=sage.all.vector(GF(2), [1, 0, 0, 0]))
[1, 0, 3, 2, 5, 4, 7, 6, 9, 8, 11, 10, 13, 12, 15, 14]

boolcrypt.utilities.poly2matrix(lin_poly)

Return the binary matrix given by the linearized polynomial.

>>> x = PolynomialRing(GF(2**4), 'x').gen()
>>> poly2matrix(x)
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
>>> x = PolynomialRing(get_rijndael_field(), 'x').gen()
>>> # See In How Many Ways Can You Write Rijndael
>>> poly2matrix(x**2)
[1 0 0 0 1 0 1 0]
[0 0 0 0 1 0 1 1]
[0 1 0 0 0 1 0 0]
[0 0 0 0 1 1 1 1]
[0 0 1 0 1 0 0 1]
[0 0 0 0 0 1 1 0]
[0 0 0 1 0 1 0 0]
[0 0 0 0 0 0 1 1]

boolcrypt.utilities.lut2matrix(lut, return_ct=False)

Return the binary matrix given by the LUT

>>> x = PolynomialRing(GF(2**4), 'x').gen()
>>> lut2matrix(poly2lut(x))
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
>>> lut2matrix(poly2lut(x + 1), return_ct=True)
[[0 1 1 1]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1], (1, 0, 0, 0)]
>>> x = PolynomialRing(get_rijndael_field(), 'x').gen()
>>> lut2matrix(poly2lut(x**2))  # See In How Many Ways Can You Write Rijndael
[1 0 0 0 1 0 1 0]
[0 0 0 0 1 0 1 1]
[0 1 0 0 0 1 0 0]
[0 0 0 0 1 1 1 1]
[0 0 1 0 1 0 0 1]
[0 0 0 0 0 1 1 0]
[0 0 0 1 0 1 0 0]
[0 0 0 0 0 0 1 1]

boolcrypt.utilities.hex_string2lut(s, num_char_per_elem)

Return the LUT given as a compact hex string.

>>> s = "6512304789ABCDEF"
>>> lut = hex_string2lut(s, 1)
>>> lut
[6, 5, 1, 2, 3, 0, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> [hex(x) for x in lut]
['0x6', '0x5', '0x1', '0x2', '0x3', '0x0', '0x4', '0x7', '0x8', '0x9', '0xa', '0xb', '0xc', '0xd', '0xe', '0xf']
>>> assert lut == hex_string2lut("0x6512304789ABCDEF", 1)
>>> assert lut == hex_string2lut("0x060501020300040708090a0b0c0d0e0f", 2)

boolcrypt.utilities.lut2hex_string(lut, num_char_per_elem, prefix0x=False)

Return the hex string representation.

>>> lut = [6, 5, 1, 2, 3, 0, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> lut2hex_string(lut, 1)
'6512304789abcdef'
>>> assert lut2hex_string(lut, 2, True) == "0x060501020300040708090a0b0c0d0e0f"

boolcrypt.utilities.lut2poly(lut, field_var=None)

Return the polynomial representation of a given LUT.

>>> lut2poly(get_lut_inversion(4))
x^14
>>> field_var = PolynomialRing(get_rijndael_field(), 'y').gen()
>>> lut2poly(get_lut_inversion(8, field_var.base_ring()), field_var)
y^254

boolcrypt.utilities.lut2anf(lut, bool_poly_ring=None, num_inputs=None, num_outputs=None)

Return the ANF (the canonical components) of a function given as a LUT.

>>> for p in lut2anf(get_lut_inversion(4)): print(p)
x0*x1*x2 + x0*x2 + x0 + x1*x2*x3 + x1*x2 + x1 + x2 + x3
x0*x1*x3 + x0*x1 + x0*x2 + x1*x2 + x1*x3 + x3
x0*x1 + x0*x2*x3 + x0*x2 + x0*x3 + x2 + x3
x0*x3 + x1*x2*x3 + x1*x3 + x1 + x2*x3 + x2 + x3
>>> bpr = BooleanPolynomialRing(3, 'x')
>>> for p in lut2anf([0] * (2**3), bool_poly_ring=bpr): print(p)
0
0
0
>>> # more inputs that outputs
>>> lut = [[bpr("x0*x1 + x0 + x1")(*v), bpr("x0")(*v)] for v in sage.all.VectorSpace(GF(2), 3)]
>>> for p in lut2anf([vector2int(v) for v in lut]): print(p)
x0*x1 + x0 + x1
x0
0
>>> for p in lut2anf([vector2int(v) for v in lut], num_outputs=2): print(p)
x0*x1 + x0 + x1
x0
>>> # more outputs than inputs
>>> lut = [[bpr("x0")(*v), bpr("x1")(*v), bpr("x2")(*v), bpr("x0*x1 + x2")(*v), ] for v in sage.all.VectorSpace(GF(2), 3)]
>>> # for p in lut2anf([vector2int(v) for v in lut]): print(p)  # AssertionError
>>> for p in lut2anf([vector2int(v) for v in lut], num_outputs=4): print(p)
x0
x1
x2
x0*x1 + x2

boolcrypt.utilities.poly2lut(polynomial)

Return the LUT representation of a permutation polynomial.

>>> x = PolynomialRing(GF(2**4, repr="int"), 'x').gen()
>>> poly2lut(x)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> from sage.crypto.sboxes import AES
>>> poly = AES.interpolation_polynomial()
>>> poly2lut(poly) == list(AES)
True

boolcrypt.utilities.anf2lut(anf)

Return the LUT representation of a permutation given by its ANF.

>>> x0, x1, x2, x3 = BooleanPolynomialRing(4, 'x').gens()
>>> anf2lut([x0, x1, x2, x3])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> anf2lut(lut2anf(get_lut_inversion(4))) == get_lut_inversion(4)
True

boolcrypt.utilities.anf2matrix(anf, input_vars=None)

Return the binary index_input_vars of the vectorial Boolean function given in ANF.

If the anf is symbolic, index_input_vars must be given. The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

>>> x, y = BooleanPolynomialRing(names="x, y").gens()
>>> anf2matrix([x + y, x])
[1 1]
[1 0]
>>> x, y, a, b, c = BooleanPolynomialRing(names="x, y, a, b, c").gens()
>>> anf = [0*x + (a + b)*y, c*x + y]
>>> anf2matrix(anf, (0, 1))
[    0 a + b]
[    c     1]

boolcrypt.utilities.get_ct_coeff(anf, input_vars=None)

Return the binary constant of the vectorial Boolean function given in ANF.

If the anf is symbolic, index_input_vars must be given. The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

>>> from sage.crypto.sboxes import AES
>>> hex(vector2int(get_ct_coeff(lut2anf(list(AES)))))
'0x63'
>>> x, y, a, b, c = BooleanPolynomialRing(names="x, y, a, b, c").gens()
>>> anf = [x + x*a + x*b + x*y*(a*b + c) + (a*b*c), y + 1 + a + b + c]
>>> get_ct_coeff(anf, [x, y])
(a*b*c, a + b + c + 1)

boolcrypt.utilities.int2vector(x, size)

Return the integer associated to the given binary vector.

>>> pprint.pprint([int2vector(i, 3) for i in range(2**3)])
[(0, 0, 0),
 (1, 0, 0),
 (0, 1, 0),
 (1, 1, 0),
 (0, 0, 1),
 (1, 0, 1),
 (0, 1, 1),
 (1, 1, 1)]

boolcrypt.utilities.vector2int(v)

Return the binary vector associated to the given integer.

>>> vectors = sage.all.VectorSpace(GF(2), 3).list()
>>> vectors
[(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0), (0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 1, 1)]
>>> [vector2int(v) for v in vectors]
[0, 1, 2, 3, 4, 5, 6, 7]
>>> assert all([i == vector2int(int2vector(i, 4)) for i in range(2**4)])

boolcrypt.utilities.test_conversion(iterations=100)

Test the conversion functions

>>> test_conversion(100)
True

boolcrypt.utilities.get_lut_inversion(n, field=None)

Return the LUT representing the inversion of GF(2**n).

>>> lut = get_lut_inversion(4)
>>> lut
[0, 1, 9, 14, 13, 11, 7, 6, 15, 2, 12, 5, 10, 4, 3, 8]
>>> lut2poly(lut)
x^14

boolcrypt.utilities.invert_lut(lut)

Return the inverse of a LUT

>>> invert_lut([0, 1, 2, 3])
[0, 1, 2, 3]
>>> invert_lut(get_lut_inversion(4)) == get_lut_inversion(4)
True
>>> invert_lut(get_lut_inversion(9)) == get_lut_inversion(9)
True

boolcrypt.utilities.get_bitsize(lut)

Return the bitsize of the given permutation.

>>> get_bitsize(get_lut_inversion(4))
4

boolcrypt.utilities.is_invertible(lut)

Return whether the function is a permutation.

>>> is_invertible(get_lut_inversion(3))
True
>>> is_invertible([0, 1, 2, 0])
False
>>> is_invertible(get_lut_inversion(9))
True
>>> is_invertible([0 for i in range(2**9)])
False
>>> is_invertible([0, 1, 2, 4])
False

boolcrypt.utilities.str2bp(my_str, bpr_gens_dict)

Fast conversion of a string to a Boolean polynomial given the gens of a BooleanPolynomialRing.

>>> bpr = BooleanPolynomialRing(names="x, y")
>>> str2bp("x + y", bpr.gens_dict())
x + y

boolcrypt.utilities.get_num_inputs_anf(anf)

Return the number of inputs of the given vectorial anf

boolcrypt.utilities.is_balanced(anf)

Return whether the anf is balanced.

>>> is_balanced(lut2anf(get_lut_inversion(4)))
True
>>> bpr = BooleanPolynomialRing(n=4, names="x")
>>> is_balanced([bpr("x0*x1 + x0*x2 + x1*x2")])  # only 3-var 2-deg-homo balanced
True
>>> is_balanced([bpr("x0*x1 + x0*x2 + x0*x3 + x1*x2 + x1*x3")])
True
>>> is_balanced([bpr("x0*x1")])
False
>>> is_balanced([bpr("x0*x1 + x0*x2")])
False

boolcrypt.utilities.get_anf_coeffmatrix_str(anf, input_vars=None, full_repr=None)

Return the coefficient matrix of a (symbolic) anf as a string.

If the anf is symbolic, input_vars must be given. The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

If the anf is symbolic and the number of symbolic coefficients is greater than 32, then instead of the coefficient matrix, a short string representation of the ANF is returned (unless full_repr is True).

>>> x, y, z = BooleanPolynomialRing(names="x, y, z").gens()
>>> f0 = x*y*z + x*y + x*z + y*z + x + y + z + 1
>>> f1 =         x*y +     + y*z + x +   + z + 1
>>> f2 = 0*x
>>> [f0, f1, f2]
[x*y*z + x*y + x*z + x + y*z + y + z + 1, x*y + x + y*z + z + 1, 0]
>>> get_anf_coeffmatrix_str([f0, f1, f2])
[x*y*z|  x*y   x*z   y*z|    x     y     z|    1]
[-----+-----------------+-----------------+-----]
[    1|    1     1     1|    1     1     1|    1]
[    0|    1     0     1|    1     0     1|    1]
[    0|    0     0     0|    0     0     0|    0]
>>> names = "x, y, z, ax, ay, az, a"
>>> x, y, z, ax, ay, az, a = BooleanPolynomialRing(names=names).gens()
>>> f0 = ax*x + ay*y + az*z
>>> f1 =    x +      + z
>>> f2 = 0*x
>>> get_anf_coeffmatrix_str([f0, f1, f2], input_vars=[x, y, z])
[ x  y  z]
[--------]
[ax ay az]
[ 1  0  1]
[ 0  0  0]
>>> vars = BooleanPolynomialRing(names=["x0", "x1"] + ["a" + str(i) for i in range(32)]).gens()
>>> anf = [vars[0]*sage.all.prod(vars[2:2+32]), vars[1]*vars[-2] + vars[-1]]
>>> print(get_anf_coeffmatrix_str(anf, input_vars=["x0", "x1"]))  
[
    BooleanPolynomial(x0, a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, a21, a22, a23, a24, a25, a26, a27, a28, a29, a30, a31)
    x1*a30 + a31
]

boolcrypt.utilities.pretty_poly(polynomial, ignore_coefficients=False)

Return a string representation of a finite field polynomial where the coefficients are represented as integers.

>>> F = GF(2**8, 'z')
>>> x = PolynomialRing(F, 'x').gen()
>>> polynomial = F.fetch_int(1) + F.fetch_int(2) * x + F.fetch_int(4) * x**2
>>> polynomial
z^2*x^2 + z*x + 1
>>> pretty_poly(polynomial)
'4*x^2 + 2*x + 1'

boolcrypt.utilities.normalize_poly(polynomial)

Return the normalized representation of a polynomial.

Given f(x) = sum_{i=0}_{n} a_i x^i, return g(x) = c f(x + b) + d, such that g(0) = 0, g is monic, and g doesn’t have x^{n-1} term (if n != 0 mod p for n = deg(f) and GF(p**r)).

>>> F = GF(2**4, 'z')
>>> x = PolynomialRing(F, 'x').gen()
>>> normalize_poly(F.fetch_int(2) * x**2 + 1)
x^2
>>> normalize_poly(F.fetch_int(2) * x**3 + x**2 + 1)
x^3 + (z^3 + z^2 + 1)*x

See also Section 1.5 of arXiv:1211.6044 [math.NT]

boolcrypt.utilities.pretty_container_with_matrices(matrices)

Print a sequence of matrices each one in a different line, similar to IPython.

boolcrypt.utilities.get_canonical_matrix(rank, nrows, ncols=None)

Return the canonical matrix with given rank over GF(2).

The square canonical matrix of rank r is the following matrix

( I_r 0 ) ( 0 O_n-r )

Note that any matrix of dimension (n,m) and rank r is matrix equivalent to the canonical matrix of same dimension and rank k.

>>> get_canonical_matrix(1, nrows=2, ncols=2)
[1|0]
[-+-]
[0|0]
>>> get_canonical_matrix(2, nrows=4, ncols=5)
[1 0|0 0 0]
[0 1|0 0 0]
[---+-----]
[0 0|0 0 0]
[0 0|0 0 0]

boolcrypt.utilities.find_monomial_matrices(n, field=None, condition=None, verbose=False)

Find the binary matrices corresponding to the polynomials a*x^(2^i) verifying some condition.

>>> n = 4
>>> condition = lambda m: m.column(0)[1:].is_zero() and m.submatrix(1, 1, n-1, n-1).is_invertible()
>>> matrices = find_monomial_matrices(4, condition=condition)
>>> print(pretty_container_with_matrices(matrices))  # not necessary in IPython
[
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1],
[1 0 1 0]
[0 0 1 0]
[0 1 0 1]
[0 0 0 1],
[1 1 1 1]
[0 1 0 1]
[0 0 1 1]
[0 0 0 1],
[1 1 0 0]
[0 0 1 1]
[0 1 0 0]
[0 0 0 1]
]

boolcrypt.utilities.lin_poly2pseudocirc_matrix(polynomial)

Return the pseudo-circulant matrix associated to a linearized polynomial.

A linearized polynomial is invertible iff its associated matrix is non-singular.

>>> n = 4
>>> z0 = GF(2**n).gen()
>>> R = PolynomialRing(GF(2**n), 'x')
>>> x = R.gen()
>>> lin_poly2pseudocirc_matrix(x + z0*x**2 + (z0 + 1)*x**4)
[       1        0       z4 z4^2 + 1]
[      z4        1        0     z4^2]
[  z4 + 1     z4^2        1        0]
[       0 z4^2 + 1   z4 + 1        1]
>>> for _ in range(100):
...     poly = R.random_element()
...     poly -= poly.constant_coefficient()
...     assert lin_poly2pseudocirc_matrix(poly).is_invertible() == poly2matrix(poly).is_invertible()

boolcrypt.utilities.compose_lut(left, right)

Return the LUT representing F(G(x)).

F and G can be given as LUTs, matrices or affine functions, but one of them should be given as a LUT.

>>> compose_lut(get_lut_inversion(4), get_lut_inversion(4))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> rm = sage.all.random_matrix(GF(2), 4, 4, algorithm="unimodular")
>>> compose_lut(matrix2lut(rm), rm.inverse())
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> compose_lut([rm.inverse(), rm.inverse() * sage.all.vector([1, 0, 0, 0])], [x.__xor__(1) for x in matrix2lut(rm)])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
>>> lut = get_lut_inversion(4)
>>> field = GF(2**4, repr="int")
>>> right_self = field.fetch_int(3) * PolynomialRing(field, 'x').gen()
>>> left_self = right_self
>>> left_self(lut2poly(lut)(right_self))  # checking is a self_equivalence
x^14
>>> right_self, left_self = poly2matrix(right_self), poly2matrix(left_self)
>>> lut2poly(compose_lut(left_self, compose_lut(lut, right_self)))
x^14

boolcrypt.utilities.compose_affine(left_matrix, left_ct, right_matrix, right_ct)

Return the composition of two affine functions as a (matrix, vector) pair.

>>> left_rot = sage.all.matrix.circulant(sage.all.vector(GF(2), [0,0,0,1]))
>>> compose_affine(left_rot.inverse(), 1, left_rot, 1)
[[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1], (1, 0, 0, 1)]

boolcrypt.utilities.compose_lut_matrix(lut, bin_matrix, bin_ct=0)

Return the LUT representing F A, F given as a lut and A given as a pair of a binary matrix and a binary constant

boolcrypt.utilities.compose_matrix_lut(bin_matrix, lut, bin_ct=0)

Return the LUT representing A F, F given as a lut and A given as a pair of a binary matrix and a binary constant

boolcrypt.utilities.substitute_anf(anf, replacement, output_bool_poly_ring)

Substitute variables from the given anf according to the given dictionary.

>>> B = BooleanPolynomialRing(4, "x")
>>> x0, x1, x2, x3 = B.gens()
>>> identity = [x0, x1, x2, x3]
>>> for p in substitute_anf(identity, {x0:x0, x3:x3}, B): print(p)
x0
x1
x2
x3
>>> inv_anf = lut2anf(get_lut_inversion(4))
>>> B = inv_anf[0].parent()
>>> for p in substitute_anf(inv_anf, {B.gens()[0]: B(0)}, B): print(p)
x1*x2*x3 + x1*x2 + x1 + x2 + x3
x1*x2 + x1*x3 + x3
x2 + x3
x1*x2*x3 + x1*x3 + x1 + x2*x3 + x2 + x3

boolcrypt.utilities.compose_anf_fast(left_anf, right_anf)

Compose two functions compatible given by their anf.

The output size of right_anf must be the same as the input size of left_anf.

>>> x0, x1, x2, x3 = BooleanPolynomialRing(4, "x").gens()
>>> identity = BooleanPolynomialVector([x0, x1, x2, x3])
>>> for p in compose_anf_fast(identity, identity): print(p)
x0
x1
x2
x3
>>> inversion = lut2anf(get_lut_inversion(4))
>>> for p in compose_anf_fast(inversion, inversion): print(p)
x0
x1
x2
x3

boolcrypt.utilities.concatenate_lut(left_lut, right_lut)

Return the concatenation of two permutations F || G given by their lut.

>>> n = 3
>>> identity = [i for i in range(2**n)]
>>> for p in lut2anf(concatenate_lut(identity, identity)): print(p)
x0
x1
x2
x3
x4
x5
>>> inversion = get_lut_inversion(n)
>>> for p in lut2anf(inversion): print(p)
x0 + x1*x2 + x1 + x2
x0*x1 + x2
x0*x2 + x1 + x2
>>> for p in lut2anf(concatenate_lut(inversion, inversion)): print(p)
x0 + x1*x2 + x1 + x2
x0*x1 + x2
x0*x2 + x1 + x2
x3 + x4*x5 + x4 + x5
x3*x4 + x5
x3*x5 + x4 + x5

boolcrypt.utilities.concatenate_anf(left_anf, right_anf, prefix='x', input_vars_left=None, input_vars_right=None)

Return the concatenation of two functions given by their anf

By default, the input variables of the concatenation are set to x0, x1, … If prefix=None, the input variables are set to the input variables of left concatenated to the input variables of right (assuming they don’t collide).

If left/right are symbolic anf, input_vars_left/right must be given.

The lists input_vars_* can be given as a list of Boolean variables or strings.

>>> x, = BooleanPolynomialRing(1, "x").gens()
>>> concatenation = concatenate_anf([x], [x])
>>> list(concatenation)
[x0, x1]
>>> concatenation[0].parent()
Boolean PolynomialRing in x0, x1
>>> left_anf, right_anf = [BooleanPolynomialRing(1, "x")("x")], [BooleanPolynomialRing(1, "y")("y")]
>>> concatenation = concatenate_anf(left_anf, right_anf, prefix=None)
>>> list(concatenation)
[x, y]
>>> concatenation[0].parent()
Boolean PolynomialRing in x, y
>>> x, a, b = BooleanPolynomialRing(3, "x, a, b").gens()
>>> concatenation = concatenate_anf([x + a], [x + a*b], input_vars_left=[x], input_vars_right=["x"])
>>> list(concatenation)
[x0 + a, x1 + a*b]
>>> concatenation[0].parent()
Boolean PolynomialRing in x0, x1, a, b

boolcrypt.utilities.concatenate_anf_fast(*list_anfs)

Return the concatenation of several non-symbolic functions given by their anf-

The inputs of each function must be x0, x1, …

>>> x0, = BooleanPolynomialRing(1, "x0").gens()
>>> list(concatenate_anf_fast([x0], [x0], [x0], [x0]))
[x0, x1, x2, x3]

boolcrypt.utilities.get_upper_bound_monomials(alg_deg, domain, int2log2=False)

Return the maximum number of monomials a function can have with given algebraic degree.

If the domain is GF(2)**n, return the maximum number of GF(2) monomials of a component. If the domain is GF(2**n), return the maximum number of GF(2**n) monomials of the univariate representation.

>>> get_upper_bound_monomials(7, GF(2)**8)
255
>>> get_upper_bound_monomials(7, GF(2**8), int2log2=True)
7
>>> n, d = 4, 2
>>> p = sage.all.BooleanPolynomialRing(4, 'x').random_element(d, terms=sage.all.Infinity)
>>> len(p) <= get_upper_bound_monomials(d, GF(2)**n)
True

boolcrypt.utilities.get_upper_bound_gf2_splitdegree_monomials(nx, ny, dx, dy, dxy, int2log2=False)

Return the maximum number of monomials a bit-function with split degree.

Return the maximum number of monomoials of a (nx,ny)-bit function f(x, y) with x-degree dx and y-degree dy and mixed degree dxy.

>>> get_upper_bound_monomials(4, GF(2)**8)
163
>>> get_upper_bound_gf2_splitdegree_monomials(4, 4, 2, 2, 4)
121
>>> get_upper_bound_gf2_splitdegree_monomials(4, 4, 4, 1, 4)
76

boolcrypt.utilities.get_megabyte_size_anf(n, d, m=None)

Return the maximum megabytes size of a system of m Boolean functions, where each n-bit Boolean function is of degree d.

This is assuming we represent the coefficient of a monomial of each Boolean function with a unique n-bit integer.

boolcrypt.utilities.get_megabyte_size_splitdegree_anf(nx, ny, dx, dy, dxy, m=None)

Return the maximum megabytes size of a system of m Boolean functions, where each (nx, ny)-bit Boolean function is of x-degree dx and y-degree dy and mixed degree dxy.

This is assuming we represent the coefficient of a monomial of each Boolean function with a unique n-bit integer.

boolcrypt.utilities.get_algebraic_degree(lut, only_maximum=True)

Return the maximum and minumum algebraic degree of the canonical components of a permutation.

>>> get_algebraic_degree(get_lut_inversion(4))
3
>>> get_algebraic_degree(get_lut_inversion(8), only_maximum=False)
(7, 7)
>>> get_algebraic_degree(get_lut_inversion(9), only_maximum=False)
(8, 8)

boolcrypt.utilities.get_all_algebraic_degrees(lut)

Return the algebraic degree of all components of a permutation.

>>> lut = get_lut_inversion(4)
>>> get_all_algebraic_degrees(lut)
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
>>> import collections
>>> print(collections.Counter(get_all_algebraic_degrees(lut)))
Counter({3: 15})

boolcrypt.utilities.get_differential_uniformity(lut)

See sage.crypto.sbox.Sbox.maximal_difference_probability_absolute

In other words, the biggest entry in the DDT table for a non-zero differential.

>>> get_differential_uniformity(get_lut_inversion(4))
4
>>> get_differential_uniformity(get_lut_inversion(8))
4

boolcrypt.utilities.get_linearity(lut)

See sage.crypto.sbox.Sbox.maximal_linear_bias_absolute

In other words, the biggest entry in the LAT table for a non-zero input mask.

>>> get_linearity(get_lut_inversion(4))
4
>>> get_linearity(get_lut_inversion(8))
16

boolcrypt.utilities.has_linear_structures(lut)

See sage.crypto.sbox.Sbox.has_linear_structures

>>> from sage.crypto.sboxes import AES, PRESENT
>>> has_linear_structures(list(AES))
False
>>> has_linear_structures(list(PRESENT))
True

boolcrypt.utilities.get_all_components(lut)

Return all components (in ANF) of a permutation.

>>> pprint.pprint(get_all_components(get_lut_inversion(4)))
{1: x0*x1*x2 + x0*x2 + x0 + x1*x2*x3 + x1*x2 + x1 + x2 + x3,
 2: x0*x1*x3 + x0*x1 + x0*x2 + x1*x2 + x1*x3 + x3,
 3: x0*x1*x2 + x0*x1*x3 + x0*x1 + x0 + x1*x2*x3 + x1*x3 + x1 + x2,
 4: x0*x1 + x0*x2*x3 + x0*x2 + x0*x3 + x2 + x3,
 5: x0*x1*x2 + x0*x1 + x0*x2*x3 + x0*x3 + x0 + x1*x2*x3 + x1*x2 + x1,
 6: x0*x1*x3 + x0*x2*x3 + x0*x3 + x1*x2 + x1*x3 + x2,
 7: x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x0*x2 + x0*x3 + x0 + x1*x2*x3 + x1*x3 + x1 + x3,
 8: x0*x3 + x1*x2*x3 + x1*x3 + x1 + x2*x3 + x2 + x3,
 9: x0*x1*x2 + x0*x2 + x0*x3 + x0 + x1*x2 + x1*x3 + x2*x3,
 10: x0*x1*x3 + x0*x1 + x0*x2 + x0*x3 + x1*x2*x3 + x1*x2 + x1 + x2*x3 + x2,
 11: x0*x1*x2 + x0*x1*x3 + x0*x1 + x0*x3 + x0 + x2*x3 + x3,
 12: x0*x1 + x0*x2*x3 + x0*x2 + x1*x2*x3 + x1*x3 + x1 + x2*x3,
 13: x0*x1*x2 + x0*x1 + x0*x2*x3 + x0 + x1*x2 + x1*x3 + x2*x3 + x2 + x3,
 14: x0*x1*x3 + x0*x2*x3 + x1*x2*x3 + x1*x2 + x1 + x2*x3 + x3,
 15: x0*x1*x2 + x0*x1*x3 + x0*x2*x3 + x0*x2 + x0 + x2*x3 + x2}

boolcrypt.utilities.get_symbolic_anf(degree, num_inputs, num_outputs, ct_terms=True, prefix_inputs='x', prefix_coeffs='a', coeff2ct=None, coeff2expr=None, bpr=None, return_varnames=False)

Return an ANF with symbolic coefficients given as Boolean variables.

Parameters

• prefix_inputs (-) – the prefix string to label the input variables of the ANF.

• prefix_coeffs (-) – the prefix string to label the coefficients of the ANF.

• degree (-) – the algebraic degree of the ANF.

• ct_terms (-) – whether to consider constant terms

• num_inputs (-) – the dimension of the ANF

• num_outputs – the dimension of the ANF

• coeff2ct (-) – a dictionary mapping string/Boolean coefficient labels to constants to replace those coefficients to fixed values.

• coeff2expr (-) – a dictionary mapping string/Boolean coefficient labels to Boolean to replace those coefficients to Boolean expressions (bpr must be given)

• bpr (-) – if given, each ANF component is an element of given Boolean poly ring

• return_varnames (-) – if True, return the varnames of the parent BooleanPolynomialRing of the symbolic anf.

>>> get_anf_coeffmatrix_str(get_symbolic_anf(1, 3, 3), input_vars=[0, 1, 2])
[  x0   x1   x2|   1]
[--------------+----]
[a0_0 a0_1 a0_2|  a0]
[a1_0 a1_1 a1_2|  a1]
[a2_0 a2_1 a2_2|  a2]
>>> anf = get_symbolic_anf(2, 3, 1, ct_terms=False, prefix_inputs="y",
...     prefix_coeffs="b", coeff2ct={"b0_0": 1})
>>> get_anf_coeffmatrix_str(anf, input_vars=[0, 1, 2])
[ y0*y1  y0*y2  y1*y2|    y0     y1     y2]
[--------------------+--------------------]
[b0_0_1 b0_0_2 b0_1_2|     1   b0_1   b0_2]
>>> bpr = BooleanPolynomialRing(names=["x0", "a0_0", "b"])
>>> anf = get_symbolic_anf(1, 1, 1, ct_terms=False, prefix_inputs="x",
...     prefix_coeffs="a", coeff2expr={"a0_0": "b"}, bpr=bpr)
>>> get_anf_coeffmatrix_str(anf, input_vars=["x0"])
[x0]
[--]
[ b]
>>> get_symbolic_anf(1, 3, 3, return_varnames=True)
['x0', 'x1', 'x2', 'a0_0', 'a0_1', 'a0_2', 'a0', 'a1_0', 'a1_1', 'a1_2', 'a1', 'a2_0', 'a2_1', 'a2_2', 'a2']

boolcrypt.utilities.get_symbolic_coeff(bool_poly, input_vars, monomial)

Return the symbolic coefficient of a symbolic Boolean polynomial.

A symbolic Boolean function is a Boolean function of the form f(x1, dots, xn-1, a1, dots,), where xi are the inputs and ai are parameters.

Given a monomial x_i1 * dots * x_ir, it returns the symbolic coefficient (in terms of ai) of the monomial x_i1 * dots * x_ir.

It is assumed the given monomial only contains input_vars variables.

The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

>>> x, y, a, b, c = BooleanPolynomialRing(names="x, y, a, b, c").gens()
>>> poly = x + x*a + x*b + x*y*(a*b + c) + (a*b*c)
>>> get_symbolic_coeff(poly, ("x", "y"), "x")
a + b + 1
>>> get_symbolic_coeff(poly, (x, y, a, b, c), x)
1
>>> poly.monomial_coefficient(x)
1
>>> get_symbolic_coeff(poly, [0, 1], 1)
a*b*c

boolcrypt.utilities.get_all_symbolic_coeff(bool_poly, input_vars, ignore_terms_of_deg_strictly_less=0)

Return all the symbolic coefficients of a symbolic Boolean polynomial.

A symbolic Boolean function is a Boolean function of the form f(x1, dots, xn-1, a1, dots,), where xi are the inputs and ai are parameters.

It returns a dictionary with entries (X, A), where X is a monomial with input vars and A is a polynomial of symbolic variables corresponding to the monomial X. For example, the entry (x_0*x_1, a_0a_1+_a2), means the symbolic polynomial contains the monomial (a_0a_1+_a2) * x_0_x1 (after grouping).

By default, the ct terms are always returned in the dictionary mapping the monomial to the coefficients.

The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

>>> x, y, a, b, c = BooleanPolynomialRing(names="x, y, a, b, c").gens()
>>> poly = x + x*a + x*b + x*y*(a*b + c) + (a*b*c)
>>> poly
x*y*a*b + x*y*c + x*a + x*b + x + a*b*c
>>> get_all_symbolic_coeff(poly, (0, 1))
{x*y: a*b + c, x: a + b + 1, 1: a*b*c}
>>> get_all_symbolic_coeff(poly, (x, y))
{x*y: a*b + c, x: a + b + 1, 1: a*b*c}
>>> get_all_symbolic_coeff(poly, ("x", "y"), ignore_terms_of_deg_strictly_less=1)
{x*y: a*b + c, x: a + b + 1}
>>> get_all_symbolic_coeff(poly, (0, 1, 2, 3, 4))
{x*y*a*b: 1, x*y*c: 1, x*a: 1, x*b: 1, x: 1, a*b*c: 1}

boolcrypt.utilities.get_symbolic_alg_deg(bool_poly, input_vars)

“Return the algebraic degree of a symbolic Boolean function.

A symbolic Boolean function is a Boolean function of the form f(x1, dots, xn-1, a1, dots,), where xi are the inputs and ai are parameters (not necessarily ordered).

The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

>>> x, a, b = BooleanPolynomialRing(names="x, a, b").gens()
>>> get_symbolic_alg_deg(x + a * b, [0])
1
>>> get_symbolic_alg_deg(x + a * b, [x])
1
>>> (x + a * b).degree()
2

boolcrypt.utilities.simplify_symbolic_matrix(matrix, prefix='x')

Return a symbolic matrix where each symbolic coeff is replaced by a symbolic var.

>>> a, b, c, d = BooleanPolynomialRing(names=('a','b','c','d')).gens()
>>> matrix = sage.all.matrix(2, 3, [[a*b, a*b + c, 0], [a*b, d, 1]])
>>> simplify_symbolic_matrix(matrix)
[x0 x1  0]
[x0 x2  1]

boolcrypt.utilities.simplify_symbolic_anf(anf, input_vars, prefix='a', order='lex')

Return a symbolic anf where each symbolic coeff is replaced by a symbolic var.

The list input_vars can be given as a list of Boolean variables, strings or input variable indices.

>>> x, y, z, a, b, c = BooleanPolynomialRing(names="x, y, z, a, b, c").gens()
>>> f0 = a*x*y*z + b*x*y + c*y*z + (a+b)*x + (b+c)*z + a*b*c
>>> f1 = a*b*c*x*y*z + x*y + y*z + (b+c)*x + (a+b)*z + 1
>>> simplify_symbolic_anf([f0, f1], [x, y, z])
[x*y*z*a0 + x*y*a1 + x*a2 + y*z*a3 + z*a4 + a5, x*y*z*a5 + x*y + x*a4 + y*z + z*a2 + 1]
>>> simplify_symbolic_anf([f0, f1], ["x", "y", "z"], order="deglex")
[x*y*z*a0 + x*y*a1 + x*a3 + y*z*a2 + z*a4 + a5, x*y*z*a5 + x*y + x*a4 + y*z + z*a3 + 1]