boolcrypt.equivalence module

Find whether two functions are linear/affine equivalent and count the number of linear/affine self-equivalences.

For equivalence-based functions solved via a functional equation with a SAT solver, see functionalequation.py

boolcrypt.equivalence.has_affine_but_no_linear_se(lut, verbose=False, number_self_ae=None, len_common_reprs=None)

Check whether the permutation has affine but no linear self equivalences.

>>> lut = get_lut_inversion(3)
>>> has_affine_but_no_linear_se(lut) is None
True
>>> new_lut = [0 ^ lut[i ^ 1] for i in range(len(lut))]
>>> has_affine_but_no_linear_se(new_lut) is None
True
>>> from boolcrypt.sboxes import high_se_4bit_sboxes
>>> has_affine_but_no_linear_se(high_se_4bit_sboxes[-1])
True

boolcrypt.equivalence.get_common_linear_reprs(lut, verbose=False, debug=False)

Return the common linear representatives between F(x + c) and F(x) + d.

It return a dictionary with entries lr -> (left_cts, right_cts) where

• lr is a linear representative

• left_cts are those constants c such that c + F has representative lr

• right_cts are those constants c such that F(x + c) has representative lr

If for some lr, left_cts or right_cts is empty, lr is not included in the dictionary.

>>> lut = get_lut_inversion(4)
>>> get_common_linear_reprs(lut, verbose=True)
for i in (0,), i + F(x) is linear equivalent to F(x + 0)
{(0, 1, 2, 3, 4, 6, 8, 11, 5, 14, 15, 7, 12, 10, 13, 9): ((0,), (0,))}
>>> get_common_linear_reprs([0 ^ lut[i ^ 1] for i in range(len(lut))])  
{(1, 0, 2, 3, 4, 6, 8, 11, 5, 13, 7, 12, 9, 15, 14, 10):
((0,), (0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15))}
>>> get_common_linear_reprs([1 ^ lut[i ^ 0] for i in range(len(lut))])  
{(1, 0, 2, 3, 4, 6, 8, 11, 5, 12, 7, 13, 14, 9, 10, 15):
((0, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15), (0,))}
>>> get_common_linear_reprs([2 ^ lut[i ^ 5] for i in range(len(lut))])  
{(1, 0, 2, 4, 3, 5, 8, 15, 6, 10, 11, 14, 13, 9, 12, 7): ((0, 1, 5, 15), (0, 1, 3, 11)),
(1, 0, 2, 4, 3, 6, 8, 15, 5, 13, 7, 10, 14, 12, 11, 9): ((3, 7, 8, 12), (4, 7, 13, 14)),
(1, 0, 2, 4, 3, 6, 8, 12, 5, 14, 13, 15, 10, 7, 9, 11): ((4, 10, 11, 14), (2, 8, 9, 10)),
(1, 0, 2, 3, 4, 6, 8, 11, 5, 14, 7, 15, 13, 10, 9, 12): ((6, 13), (6, 15)),
(0, 1, 2, 3, 4, 6, 8, 11, 5, 12, 13, 7, 15, 9, 14, 10): ((9,), (12,))}

boolcrypt.equivalence.get_number_self_le(lut)

Return the number of self linear equivalences.

>>> get_number_self_le([0, 1, 2, 3])
6
>>> get_number_self_le(get_lut_inversion(4))
60
>>> from sage.crypto.sboxes import PRESENT
>>> get_number_self_le(list(PRESENT))
1
>>> get_number_self_le(get_lut_inversion(7))
889
>>> get_number_self_le(get_lut_inversion(8))
2040
>>> from sage.crypto.sboxes import AES
>>> get_number_self_le(list(AES))
8

boolcrypt.equivalence.get_number_self_ae(lut, common_reprs=None, verbose=False, debug=False)

Return the number of affine self-equivalences.

For 8-bit functions or bigger, it can take more than 1 minute.

>>> get_number_self_ae([0, 1, 2, 3])
24
>>> get_number_self_ae(get_lut_inversion(4))
60
>>> from sage.crypto.sboxes import PRESENT
>>> get_number_self_ae(list(PRESENT))
4
>>> get_number_self_ae(get_lut_inversion(7))  
889
>>> from sage.crypto.sboxes import AES
>>> get_number_self_ae(list(AES))  
2040

boolcrypt.equivalence.get_all_self_le(lut, return_matrices=False)

Return all the linear self-equivalences as pairs of LUTs or GF(2)-matrices.

>>> get_all_self_le([0, 1, 2, 3])[-1]
[[0, 3, 2, 1], [0, 3, 2, 1]]
>>> right, left = get_all_self_le([0, 1, 2, 3], return_matrices=True)[-1]
>>> sage.all.block_matrix(1, 2, [right, left])
[1 0|1 0]
[1 1|1 1]
>>> matrix2lut(right), matrix2lut(left)
([0, 3, 2, 1], [0, 3, 2, 1])
>>> right, left = get_all_self_le(get_lut_inversion(4), return_matrices=True)[-1]
>>> sage.all.block_matrix(1, 2, [right, left])
[1 1 1 1|1 1 1 1]
[1 0 0 0|1 0 0 0]
[1 1 0 0|1 1 0 0]
[1 1 1 0|1 1 1 0]
>>> from sage.crypto.sboxes import AES
>>> sage.all.block_matrix(1, 2, get_all_self_le(list(AES), return_matrices=True)[-1])  
[0 1 0 0 0 1 1 1|1 1 0 0 1 1 0 1]
[0 0 1 1 0 0 1 1|1 0 1 1 0 1 1 1]
[0 1 1 1 0 0 1 1|0 1 0 1 1 0 1 1]
[0 0 0 1 0 0 0 0|1 0 0 1 1 0 1 1]
[0 0 1 1 0 1 1 0|0 0 1 1 1 0 0 0]
[1 1 0 0 0 0 1 1|0 1 0 0 1 0 0 0]
[1 0 0 0 1 1 0 0|1 1 0 0 0 1 0 1]
[0 1 1 1 1 0 0 0|1 1 1 0 0 1 1 1]

boolcrypt.equivalence.get_all_self_ae(lut, return_lut=False, verbose=False, debug=False)

Return all the affine self-equivalences as LUTS or (matrix, vector) pairs.

>>> get_all_self_ae([0, 1, 2, 3], return_lut=True)[-1]
[[3, 1, 2, 0], [3, 1, 2, 0]]
>>> right, left = get_all_self_ae([0, 1, 2, 3])[-1]
>>> to_m = sage.all.matrix
>>> sage.all.block_matrix(2, 2, [right[0], left[0], to_m(right[1]), to_m(left[1])])
[0 1|0 1]
[1 0|1 0]
[---+---]
[1 1|1 1]
>>> right, left = get_all_self_ae([0, 1, 2, 3])[-1]
>>> sage.all.block_matrix(2, 2, [right[0], left[0], to_m(right[1]), to_m(left[1])])
[0 1|0 1]
[1 0|1 0]
[---+---]
[1 1|1 1]
>>> from sage.crypto.sboxes import PRESENT
>>> self_ae = get_all_self_ae(list(PRESENT))
>>> for r, l in self_ae: print(sage.all.block_matrix(2, 2, [r[0], l[0], to_m(r[1]), to_m(l[1])]))
[1 0 0 0|1 0 0 0]
[0 1 0 0|0 1 0 0]
[0 0 1 0|0 0 1 0]
[0 0 0 1|0 0 0 1]
[-------+-------]
[0 0 0 0|0 0 0 0]
[1 0 0 0|1 0 0 0]
[0 0 1 0|0 0 0 1]
[0 1 0 0|0 0 1 0]
[0 0 0 1|0 1 0 0]
[-------+-------]
[1 1 1 1|0 0 1 0]
[1 0 0 0|1 0 0 0]
[0 0 1 0|0 1 0 0]
[0 1 0 0|0 1 1 1]
[0 1 1 1|0 0 0 1]
[-------+-------]
[0 0 0 1|1 1 0 1]
[1 0 0 0|1 0 0 0]
[0 1 0 0|0 0 0 1]
[0 0 1 0|0 1 1 1]
[0 1 1 1|0 1 0 0]
[-------+-------]
[1 1 1 0|1 1 1 1]

boolcrypt.equivalence.check_self_le_lut(lut, right_le=None, left_le=None, affine=False, return_missing=None)

Check that the given right-left pair is a linear SE of the given lut.

If return_missing is True, it returns the right (left) SE part if the left (right) SE is given. In that case, if raises an Exception if the input half pair is not a SE.

>>> lut = [0, 1, 2, 3]
>>> right, left = [0, 3, 2, 1], [0, 3, 2, 1]
>>> check_self_le_lut(lut, right, left)
True
>>> check_self_le_lut(lut, right_le=right) and check_self_le_lut(lut, left_le=left)
True
>>> check_self_le_lut(lut, right_le=right, return_missing=True)
[0, 3, 2, 1]
>>> lut = get_lut_inversion(4)
>>> right, left = get_all_self_le(lut)[-1]
>>> check_self_le_lut(lut, right, left)
True
>>> check_self_le_lut(lut, right_le=right) and check_self_le_lut(lut, left_le=left)
True

boolcrypt.equivalence.check_self_ae_lut(lut, right_le=None, left_le=None, return_missing=None)

Check that the given right-left pair is an affine SE of the given lut.

If return_missing is True, it returns the right (left) SE part if the left (right) SE is given. In that case, if raises an Exception if the input half pair is not a SE.

>>> lut = [0, 1, 2, 3]
>>> right, left = [3, 1, 2, 0], [3, 1, 2, 0]
>>> check_self_ae_lut(lut, right, left)
True
>>> check_self_ae_lut(lut, right_le=right) and check_self_ae_lut(lut, left_le=left)
True
>>> check_self_ae_lut(lut, left_le=left, return_missing=True)
[3, 1, 2, 0]
>>> from sage.crypto.sboxes import PRESENT
>>> lut = list(PRESENT)
>>> right, left = get_all_self_ae(lut)[-1]
>>> check_self_ae_lut(lut, right, left)
True
>>> check_self_ae_lut(lut, right_le=right) and check_self_ae_lut(lut, left_le=left)
True

boolcrypt.equivalence.check_self_le_anf(anf, right_le_anf=None, left_le_anf=None, anf_inv=None, input_anf_vars=None, input_right_vars=None, input_left_vars=None, input_inv_vars=None, affine=False)

Check that the given right-left pair is a linear SE of the given anf.

If a function is symbolic, its input variables must be given as a list of Boolean variables or strings.

If right or left is not given, the inverse of anf must be given.

If both right and left are given, this function can also check for non-linear self-equivalences.

>>> from boolcrypt.utilities import lut2anf
>>> anf = lut2anf([0, 1, 2, 3])
>>> right, left = lut2anf([0, 3, 2, 1]), lut2anf([0, 3, 2, 1])
>>> check_self_le_anf(anf, right, left)
True
>>> check_self_le_anf(anf, right, None, anf) and check_self_le_anf(anf, None, left, anf)
True
>>> anf = lut2anf(get_lut_inversion(4))
>>> right, left = get_all_self_le(get_lut_inversion(4))[-1]
>>> right, left = lut2anf(right), lut2anf(left)
>>> check_self_le_anf(anf, right, left)
True
>>> check_self_le_anf(anf, right, None, anf) and check_self_le_anf(anf, None, left, anf)
True

boolcrypt.equivalence.check_self_ae_anf(anf, right_ae_anf=None, left_ae_anf=None, anf_inv=None, input_anf_vars=None, input_right_vars=None, input_left_vars=None, input_inv_vars=None)

Check that the given right-left pair is an affine SE of the given anf.

If a function is symbolic, its input variables must be given as a list of Boolean variables or strings.

If right or left is not given, the inverse of anf must be given.

If both right and left are given, this function can also check for non-linear self-equivalences.

>>> from boolcrypt.utilities import lut2anf
>>> anf = lut2anf([0, 1, 2, 3])
>>> right, left = lut2anf([3, 1, 2, 0]), lut2anf([3, 1, 2, 0])
>>> check_self_ae_anf(anf, right, left)
True
>>> check_self_ae_anf(anf, right, None, anf) and check_self_ae_anf(anf, None, left, anf)
True
>>> from sage.crypto.sboxes import PRESENT
>>> lut = list(PRESENT)
>>> anf = lut2anf(lut)
>>> anf_inv = lut2anf(invert_lut(lut))
>>> right, left = get_all_self_ae(lut, return_lut=True)[-1]
>>> right, left = lut2anf(right), lut2anf(left)
>>> check_self_ae_anf(anf, right, left)
True
>>> check_self_ae_anf(anf, right, None, anf_inv) and check_self_ae_anf(anf, None, left, anf_inv)
True

boolcrypt.equivalence.are_linear_equivalent_lut(f, g)

Return a pair of invertible matrices (a,b) such that f = b g a.

The permutations f, g are given as LUT.

If no such pair exists, return an empty list.

>>> are_linear_equivalent_lut([0, 1, 2, 3], [0, 1, 2, 3])
[[0, 1, 2, 3], [0, 1, 2, 3]]
>>> are_linear_equivalent_lut([0, 1, 2, 3], [x.__xor__(1) for x in [0, 1, 2, 3]])
[]
>>> are_linear_equivalent_lut(list(range(2**4)), get_lut_inversion(4))
[]
>>> repr_inv = [0, 1, 2, 3, 4, 6, 8, 11, 5, 14, 15, 7, 12, 10, 13, 9]
>>> right, left = are_linear_equivalent_lut(repr_inv, get_lut_inversion(4))
>>> right, left
([0, 1, 7, 6, 5, 4, 2, 3, 12, 13, 11, 10, 9, 8, 14, 15], [0, 1, 12, 13, 14, 15, 2, 3, 9, 8, 5, 4, 7, 6, 11, 10])
>>> repr_inv == compose_lut(left, compose_lut(get_lut_inversion(4), right))
True

boolcrypt.equivalence.are_affine_equivalent_lut(f, g)

Return a pair of affine permutations (a,b) such that f = b g a.

The permutations f,g are given as LUT.

If no such pair exists, return an empty list.

>>> are_affine_equivalent_lut([0, 1, 2, 3], [0, 1, 2, 3])
[[0, 1, 2, 3], [0, 1, 2, 3]]
>>> are_affine_equivalent_lut([0, 1, 2, 3], [x.__xor__(1) for x in [0, 1, 2, 3]])
[[0, 3, 1, 2], [3, 1, 0, 2]]
>>> are_affine_equivalent_lut(list(range(2**4)), get_lut_inversion(4))
[]
>>> from sage.crypto.sboxes import SERPENT_S3, Golden_S0
>>> are_affine_equivalent_lut(list(SERPENT_S3), list(Golden_S0))
[[13, 2, 15, 0, 3, 12, 1, 14, 4, 11, 6, 9, 10, 5, 8, 7], [7, 11, 6, 10, 0, 12, 1, 13, 8, 4, 9, 5, 15, 3, 14, 2]]

boolcrypt.equivalence.check_ccz_equivalence_anf(f, g, a, g_implicit=False, f_input_vars=None, g_input_vars=None, a_input_vars=None)

Check whether A(Graph(f)) = Graph(g).

Graph(f) is is the set of points {(x, f(x))}, and similar for Graph(g). However, if g_implicit=True, Graph(g) is built as {(x, y) : g(x, y) = 0}.

The admissible mapping A can be given in ANF, as a matrix or as a pair (matrix, vector).

If F = G, this methods checks whether A is a CCZ self-equivalence.

>>> from boolcrypt.utilities import lut2anf
>>> from sage.crypto.sbox import SBox
>>> # CCZ of inversion found with sboxU.ccz_equivalent_permutations
>>> f = lut2anf([0, 15, 9, 7, 4, 14, 1, 3, 10, 6, 13, 2, 8, 5, 11, 12])
>>> g = lut2anf(get_lut_inversion(4))
>>> am = [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1,
... 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1,
... 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1]
>>> am = sage.all.matrix(GF(2), 4*2, 4*2, am)
>>> check_ccz_equivalence_anf(f, g, am)
True
>>> boolean_vars = sage.all.BooleanPolynomialRing(8, 'x').gens()
>>> iv, ov = boolean_vars[:4], boolean_vars[4:]
>>> iv, ov = list(reversed(iv)), list(reversed(ov))  # polynomials() takes x0 as MSB
>>> g_implicit = SBox(get_lut_inversion(4)).polynomials(iv, ov, groebner=True)
>>> check_ccz_equivalence_anf(f, g_implicit, am, g_implicit=True)
True
>>> # Graph-SE found with sat.find_ccz_equivalence
>>> f = lut2anf((0, 1, 2, 3, 4, 6, 7, 5))
>>> am = [0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
...       0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0,]
>>> am = sage.all.matrix(GF(2), 3*2, 3*2, am)
>>> check_ccz_equivalence_anf(f, f, am)
True
>>> check_ccz_equivalence_anf(f, f, am, f_input_vars=["x0", "x1", "x2"],
...     g_input_vars=["x0", "x1", "x2"], a_input_vars=["x" + str(i) for i in range(6)])
True