boolcrypt.cczselfequivalence module
Find self-equivalences of a function by finding the self-equivalences of its graph (i.e., also called graph automorphisms) parametrized by a CCZ-equivalent function with lower degree.
- boolcrypt.cczselfequivalence.find_self_equivalence(ccz_anf, admissible_mapping, ccz_anf_implicit=False, right_se_degree=1, inv_left_se_degree=1, se_ct_terms=True, ignore_diagonal_equations=False, add_invertibility_equations=True, ignore_determinant_equation=False, check_se=True, bpr=None, ccz_se_anf=None, prefix_se_coeffs='c', input_ccz_anf_vars=None, anf=None, input_anf_vars=None, num_input_anf_vars=None, return_ccz_se=False, verbose=False, debug=False, filename=None, **solve_args)[source]
Find a SE of F by finding a SE of the graph of G.
Let F be the function (optionally) given by
anfand G its CCZ-equivalent function through theadmissible_mappingL, that is, Graph(F)=L(Graph(G)). F (if given) and G must be in ANF form, but L can be given in ANF, as a matrix, or as a (matrix, vector) pair. If F is not given, its number of input variables must be given innum_input_anf_vars.Graph(F) is defined as usual, {(x, y): for all x, y=F(x)}. If ccz_anf_implicit=False, Graph(G) is defined similarly as Graph(F): Otherwise, Graph(G)={(x, y): G(x, y)=0} if ccz_anf_implicit=True.
This methods finds a self-equivalence (SE) (A, B) with given degrees of F (a pair of permutations (A,B) such that B F A = F) by finding a SE (an automorphism) of the graph of F parametrized by G. A is also called a right SE and B a left SE. If no solution is found, None is returned.
If the SE degrees are both 1 and se_ct_terms=True (resp. False), this method finds an affine (resp. linear) SE.
This methods returns SE (A, B) by finding a Graph(G)-SE C=(c_0, c_1) s.t. L C L^{-1} is diagonal and can be written as L C L^{-1} = (A, B^(-1)). This is done by solving the functional eq. G(c_0(u, G(u))) = c_1(u, G(u))) if ccz_anf_implicit=False, or D G C = C (D invertible, D(0)=0) if ccz_anf_implicit=True. When ccz_anf_implicit=True, this method is not complete, meaning that not all the Graph(G)-SE can be found from the equation G C = C.
The ANF of C can be optionally given in ccz_se_anf to speed up this method. Otherwise, it will be created using get_symbolic_anf.
If return_ccz_se=False, the SE of F are returned. However, the left SE B are not given in the output, but their inverses B^(-1). If return_ccz_se=True, instead of returning the SE (A, B), the Graph(G)-self-equivalences C are returned instead.
If check_se=True, checks that the found SE (A, B) are indeed SE of F.
If add_invertibility_equations=True, the equations that impose (A, B) to be invertible are added to the system of equations. In this case and if right_se_degree=1, the constraint
det(A)=1is added, otherwise (if inv_left_se_degree=1), the constraintdet(B^(-1))=1. If add_invertibility_equations=True and ignore_determinant_equation=False, then the high-degree equation involving the determinant is not added (and only some necessary but not sufficient constraints from_get_lowdeg_inv_equationsare added).input_ccz_anf_vars and input_anf_vars are two lists with the inputs vars (containing Boolean variables or strings) of the given G and F (not needed for non-symbolic anfs).
A Boolean polynomial ring bpr can be given to determine the term order. Otherwise, lexicographic order will be used (x0 > x1 > …, F0 > F1 > … > G0 > G1 > … ).
If ignore_diagonal_equations is True, the constraints that ensured that L C L^{-1} is diagonal and with proper degrees are ignored. In this case, add_invertibility_equations must be False.
Named arguments from
**solve_argsare passed to solve_functional_equation(). In particular, if return_mode and num_sat_solutions are not given, only one solution is found and the ANF of A and B^(-1) are given.>>> from boolcrypt.utilities import lut2anf, get_lut_inversion, anf2lut, invert_lut >>> from boolcrypt.equivalence import check_self_le_lut >>> f = lut2anf(get_lut_inversion(4)) >>> g = lut2anf([0, 15, 9, 7, 4, 14, 1, 3, 10, 6, 13, 2, 8, 5, 11, 12]) >>> 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) >>> a, b_inv = find_self_equivalence(g, am, anf=f, se_ct_terms=False, ... only_linear_fixed_vars=True, verbose=True) finding SE (A, B) of F through the graph of G with deg(A), deg(B^(-1)) degrees (1, 1) - F: [x0*x1*x2 x0*x1*x3 x0*x2*x3 x1*x2*x3| x0*x1 x0*x2 x0*x3 x1*x2 x1*x3 x2*x3| x0 x1 x2 x3] [-----------------------------------+-----------------------------------------------------+-----------------------------------] [ 1 0 0 1| 0 1 0 1 0 0| 1 1 1 1] [ 0 1 0 0| 1 1 0 1 1 0| 0 0 0 1] [ 0 0 1 0| 1 1 1 0 0 0| 0 0 1 1] [ 0 0 0 1| 0 0 1 0 1 1| 0 1 1 1] - G (CCZ-equivalent of F): [x0*x1*x2 x0*x1*x3 x0*x2*x3 x1*x2*x3| x0*x1 x0*x2 x0*x3 x1*x2 x1*x3 x2*x3| x0 x1 x2 x3] [-----------------------------------+-----------------------------------------------------+-----------------------------------] [ 1 0 0 0| 1 1 1 0 0 0| 1 1 0 0] [ 0 1 0 0| 0 0 1 0 1 1| 1 0 0 1] [ 0 0 1 0| 0 1 0 1 1 1| 1 0 1 0] [ 1 0 0 1| 0 0 0 1 1 0| 1 1 0 1] ... | computing C - C (self-equivalence of Graph(G)): [ x0 x1 x2 x3 x4 x5 x6 x7] [-----------------------------------------------] [ca0_0 ca0_1 ca0_2 ca0_3 ca0_4 ca0_5 ca0_6 ca0_7] [ca1_0 ca1_1 ca1_2 ca1_3 ca1_4 ca1_5 ca1_6 ca1_7] [ca2_0 ca2_1 ca2_2 ca2_3 ca2_4 ca2_5 ca2_6 ca2_7] [ca3_0 ca3_1 ca3_2 ca3_3 ca3_4 ca3_5 ca3_6 ca3_7] [cb0_0 cb0_1 cb0_2 cb0_3 cb0_4 cb0_5 cb0_6 cb0_7] [cb1_0 cb1_1 cb1_2 cb1_3 cb1_4 cb1_5 cb1_6 cb1_7] [cb2_0 cb2_1 cb2_2 cb2_3 cb2_4 cb2_5 cb2_6 cb2_7] [cb3_0 cb3_1 cb3_2 cb3_3 cb3_4 cb3_5 cb3_6 cb3_7] number of C input variables: 8 number of symbolic coefficients: 64 ... | getting equations from L C L^(-1) = diagonal - L C L^(-1) (L admissible mapping L(Graph(G)=Graph(F)): [...] ... | finding fixed variables and reducing initial and diagonal equations reducing 32 equations with mode gauss and degrees (d,#) Counter({1: 32}) gauss-reduction obtained 32 equations with degrees (d,#) Counter({1: 32}) found 32 fixed variables, resulting in 0 equations > repeating find_fixed_vars with initial reduction_mode gauss > last find_fixed_vars call found 0 new fixed variables and removed 0 equations - L C L^(-1) (reduced by initial and diagonal equations): [...] ... | adding invertibility equations over L C L^(-1) added 1 invertibility equations ... | solving the Graph(G)-self-equivalence functional equation ... ... | parsing and checking the Graph(G)-self-equivalence solutions Solution 1 out of 1: - L C L^(-1): [...] - SE (A, B) of F: - A: [...] - B^(-1): [...] ... | returning outputs with mode='list_anfs' >>> bpr = BooleanPolynomialRing(4, 'x') >>> a = anf2lut([bpr(component) for component in a]) >>> b = invert_lut(anf2lut([bpr(component) for component in b_inv])) >>> check_self_le_lut(get_lut_inversion(4), right_le=a, left_le=b) True >>> from sage.crypto.sbox import SBox >>> f = lut2anf((0, 1, 2, 3, 4, 6, 7, 5)) # 12 LSE >>> boolean_vars = sage.all.BooleanPolynomialRing(3*2, 'x').gens() >>> iv, ov = boolean_vars[:3], boolean_vars[3:] >>> iv, ov = list(reversed(iv)), list(reversed(ov)) # polynomials() takes x0 as MSB >>> g = SBox((0, 1, 2, 3, 4, 6, 7, 5)).polynomials(iv, ov, groebner=True) >>> am = sage.all.identity_matrix(GF(2), 3*2) >>> fixed_vars = dict([('cb2_2', 0), ('cb2_1', 0), ('cb2_0', 0), ('cb1_2', 0), ('cb1_1', 0), ('cb1_0', 0), ... ('cb0_1', 0), ('cb0_0', 0), ('ca2_5', 0), ('ca2_4', 0), ('ca2_3', 0), ('ca1_5', 0), ('ca1_4', 0), ... ('ca0_5', 0), ('ca0_4', 0), ('ca0_3', 0), ('ca2_0', 0), ('ca2_1', 0), ('ca2_2', 1), ('cb2_3', 0), ... ('cb0_2', 0), ('ca1_3', 0), ('cb2_4', 0), ('cb2_5', 1), ('cd2_0', 0), ('cd2_1', 0), ('cd2_2', 1)]) >>> [a, b_inv], eqs, num_sols = find_self_equivalence(g, am, num_input_anf_vars=3, ccz_anf_implicit=True, ... se_ct_terms=False, reduction_mode=None, only_linear_fixed_vars=True, return_mode="symbolic_anf", ... num_sat_solutions=12+1, return_total_num_solutions=True, initial_fixed_vars=fixed_vars, ... verbose=True, debug=True) ignoring add_invertibility_equations when ccz_anf_implicit is True finding SE (A, B) of F through the graph of G with deg(A), deg(B^(-1)) degrees (1, 1) - F: [] - G (CCZ-implicit-equivalent of F): [x3*x5 x4*x5| x0 x1 x2 x3 x4 x5] [-----------+-----------------------------------] [ 0 1| 1 0 0 1 0 0] [ 1 1| 0 1 0 0 1 0] [ 0 0| 0 0 1 0 0 1] ... | computing C - C (self-equivalence of Graph(G)): [ x0 x1 x2 x3 x4 x5] [-----------------------------------] [ca0_0 ca0_1 ca0_2 0 0 0] [ca1_0 ca1_1 ca1_2 0 0 0] [ 0 0 1 0 0 0] [ 0 0 0 cb0_3 cb0_4 cb0_5] [ 0 0 0 cb1_3 cb1_4 cb1_5] [ 0 0 0 0 0 1] input variables (6): ['x0', 'x1', 'x2', 'x3', 'x4', 'x5'] symbolic coefficients (45): ['ca0_0', ..., 'cd2_2'] Boolean PolynomialRing in x0, x1, x2, x3, x4, x5, ca0_0, ..., cd2_2 initial fixed vars (27): cb2_2 <- 0 ... cd2_2 <- 1 - D (from G = D G C): [ x0 x1 x2] [-----------------] [cd0_0 cd0_1 cd0_2] [cd1_0 cd1_1 cd1_2] [ 0 0 1] ... | getting equations from L C L^(-1) = diagonal - L C L^(-1) (L admissible mapping L(Graph(G)=Graph(F)): [ x0 x1 x2 x3 x4 x5] [-----------------------------------] [ca0_0 ca0_1 ca0_2 0 0 0] [ca1_0 ca1_1 ca1_2 0 0 0] [ 0 0 1 0 0 0] [ 0 0 0 cb0_3 cb0_4 cb0_5] [ 0 0 0 cb1_3 cb1_4 cb1_5] [ 0 0 0 0 0 1] equations from L C L^(-1) = diagonal: no equations added from L C L^(-1) = diagonal ... | finding fixed variables and reducing initial and diagonal equations - L C L^(-1) (reduced by initial and diagonal equations): [ x0 x1 x2 x3 x4 x5] [-----------------------------------] [ca0_0 ca0_1 ca0_2 0 0 0] [ca1_0 ca1_1 ca1_2 0 0 0] [ 0 0 1 0 0 0] [ 0 0 0 cb0_3 cb0_4 cb0_5] [ 0 0 0 cb1_3 cb1_4 cb1_5] [ 0 0 0 0 0 1] ... | solving the Graph(G)-self-equivalence functional equation removing from initial_fixed_vars cd2_0 <- 0 removing from initial_fixed_vars cd2_1 <- 0 removing from initial_fixed_vars cd2_2 <- 1 ... ... | parsing and checking the Graph(G)-self-equivalence solutions finding a solution of the remaining 3 equations for checking cb0_5*cd1_1 + cb1_5*cd1_0 + cb1_5*cd1_1 + cd0_2 cd1_0*cd1_1 + cd1_0 + cd1_1 + 1 cb0_5*cd1_0 + cb0_5*cd1_1 + cb1_5*cd1_0 + cd1_2 - solution: {cd1_2: 0, cd1_1: 0, cd1_0: 1, cd0_2: 0, cb1_5: 0, cb0_5: 0} Solution 1 out of 1: - L C L^(-1): [ x0 x1 x2 x3 x4 x5] [-----------------------------------------------------------------------------------] [ cd1_1 cd1_0 cb0_5 + cb1_5 0 0 0] [ cd1_0 cd1_0 + cd1_1 cb0_5 0 0 0] [ 0 0 1 0 0 0] [ 0 0 0 cd1_1 cd1_0 cb0_5] [ 0 0 0 cd1_0 cd1_0 + cd1_1 cb1_5] [ 0 0 0 0 0 1] - L C L^(-1) (with {cd1_2: 0, cd1_1: 0, cd1_0: 1, cd0_2: 0, cb1_5: 0, cb0_5: 0}): [x0 x1 x2 x3 x4 x5] [-----------------] [ 0 1 0 0 0 0] [ 1 1 0 0 0 0] [ 0 0 1 0 0 0] [ 0 0 0 0 1 0] [ 0 0 0 1 1 0] [ 0 0 0 0 0 1] - SE (A, B) of F: - A: [ x0 x1 x2] [-----------------------------------------] [ cd1_1 cd1_0 cb0_5 + cb1_5] [ cd1_0 cd1_0 + cd1_1 cb0_5] [ 0 0 1] - B^(-1): [ x0 x1 x2] [-----------------------------------------] [ cd1_1 cd1_0 cb0_5] [ cd1_0 cd1_0 + cd1_1 cb1_5] [ 0 0 1] - SE (A, B) of F (with {cd1_2: 0, cd1_1: 0, cd1_0: 1, cd0_2: 0, cb1_5: 0, cb0_5: 0}): - A: [x0 x1 x2] [--------] [ 0 1 0] [ 1 1 0] [ 0 0 1] - B^(-1): [x0 x1 x2] [--------] [ 0 1 0] [ 1 1 0] [ 0 0 1] ... | returning outputs with mode='symbolic_anf' >>> get_anf_coeffmatrix_str(a, ["x" + str(i) for i in range(3)]) [ x0 x1 x2] [-----------------------------------------] [ cd1_1 cd1_0 cb0_5 + cb1_5] [ cd1_0 cd1_0 + cd1_1 cb0_5] [ 0 0 1] >>> get_anf_coeffmatrix_str(b_inv, ["x" + str(i) for i in range(3)]) [ x0 x1 x2] [-----------------------------------------] [ cd1_1 cd1_0 cb0_5] [ cd1_0 cd1_0 + cd1_1 cb1_5] [ 0 0 1] >>> for eq in eqs: print(eq) cb0_5*cd1_1 + cb1_5*cd1_0 + cb1_5*cd1_1 + cd0_2 cd1_0*cd1_1 + cd1_0 + cd1_1 + 1 cb0_5*cd1_0 + cb0_5*cd1_1 + cb1_5*cd1_0 + cd1_2 >>> num_sols 12