boolcrypt.findpoly module
Functions to search for binary permutation polynomials.
- boolcrypt.findpoly.str2poly(line, field_var)[source]
Parse an string containing a finite field polynomial.
>>> x = PolynomialRing(get_rijndael_field(), 'x').gen() >>> fpoly = str2poly("53*x^208 + x^13", x) >>> fpoly 53*x^208 + x^13 >>> fpoly.parent() Univariate Polynomial Ring in x over Finite Field in a of size 2^8
- boolcrypt.findpoly.is_permutation_poly(polynomial)[source]
Check whether the input polynomial is a permutation.
>>> x = PolynomialRing(get_rijndael_field(), 'x').gen() >>> is_permutation_poly(x**3) False >>> is_permutation_poly(x**127) True >>> is_permutation_poly(str2poly("(23)*x^7 + x^28", x)) True
- boolcrypt.findpoly.poly2lut_fast(polynomial, field, output_lut)[source]
Return the LUT representation of a permutation polynomial.
>>> field = GF(2**4, repr="int") >>> x = PolynomialRing(field, 'x').gen() >>> output_lut = [None for i in range(2**4)] >>> poly2lut_fast(x, field, output_lut) >>> output_lut [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
- boolcrypt.findpoly.find_krssb(n, d, terms, k, field_var=None, filename=None, verbose=False, print_time=False)[source]
Find all k-rotation-symmetric S-boxes of given algebraic degree.
Find permutations S = sum(a_i + x^i), where a_i^(2^k) = a_i.
Some “left” affine equivalent krssb do not appear in the list, that is, if f(x) and g(x) are two k-rssbb of the same alg_deg and f(x) = A(g(x)), with A affine, then g(x) might not appear.
This function do not return anything (to prevent high memory usage).
Apart from the polynomials, the signature of the function and the leading monomials (e.g., # x^192) is printed to the output.
>>> find_krssb(3, 2, 3, 1, verbose=True) # find_krssb(3, 2, 3, 1) valid_exponents: [6, 5, 4, 3, 2, 1] valid_exponents_lsb_set: {1, 3, 5} subfield: [1] maximal_subfield: {1} # x^3 recursion(x^3, 2, 3, True, False) x^3 + x^2 + x # x^5 recursion(x^5, 2, 1, True, False) x^5 + x^4 + x x^5 + x^3 + x # x^6 recursion(x^6, 2, 0, False, False) x^6 + x^5 + x^4 x^6 + x^3 + x^2 >>> find_krssb(4, 2, 5, 2) # find_krssb(4, 2, 5, 2) # x^3 # x^5 # x^6 # x^9 # x^10 x^10 + 6*x^9 + 7*x^8 + 6*x^6 + 7*x^5 x^10 + 6*x^9 + 6*x^6 + 7*x^5 + x^4 x^10 + 6*x^9 + 6*x^6 + 7*x^5 + 7*x^2 x^10 + 6*x^9 + 6*x^6 + 7*x^5 + x x^10 + 7*x^9 + 6*x^8 + 7*x^6 + 6*x^5 x^10 + 7*x^9 + 7*x^6 + 6*x^5 + x^4 x^10 + 7*x^9 + 7*x^6 + 6*x^5 + 6*x^2 x^10 + 7*x^9 + 7*x^6 + 6*x^5 + x # x^12 x^12 + 6*x^10 + 7*x^8 + 7*x^5 + x^3 x^12 + 6*x^10 + 7*x^5 + 6*x^4 + x^3 x^12 + 6*x^10 + 7*x^5 + x^3 + 7*x^2 x^12 + 6*x^10 + 7*x^5 + x^3 + 6*x x^12 + 7*x^10 + 6*x^8 + 6*x^5 + x^3 x^12 + 7*x^10 + 6*x^5 + 7*x^4 + x^3 x^12 + 7*x^10 + 6*x^5 + x^3 + 6*x^2 x^12 + 7*x^10 + 6*x^5 + x^3 + 7*x x^12 + x^9 + 6*x^8 + x^6 + x^3 x^12 + x^9 + 7*x^8 + x^6 + x^3 x^12 + x^9 + x^6 + 6*x^4 + x^3 x^12 + x^9 + x^6 + 7*x^4 + x^3 x^12 + x^9 + x^6 + x^3 + 6*x^2 x^12 + x^9 + x^6 + x^3 + 7*x^2 x^12 + x^9 + x^6 + x^3 + 6*x x^12 + x^9 + x^6 + x^3 + 7*x
- boolcrypt.findpoly.find_divisors_or_selfequivs(permutation, input_file, output_file=None, deg_remainder=None, deg_other_se=None, side_divisor='both', side_se='both', xor_cts=None, verbose=False, field_var=None, num_char_per_elem=None, time_marks=None)[source]
Find divisors and/or self-equivalences of a permutation.
The list of candidates P can be given as a file containing hex strings or str polynomials. If given as hex strings, the number of characters used element must be given (see hex_string2lut). If given as str polynomials, the variable of the polynomials must also be given.
The permutation S can be given as a LUT, a polynomial or in the same format as the list of candidates.
If side_divisor=”left”, outputs the candidates P such that S = P R. If side_divisor=”right”, outputs the candidates P such that S = R P. In both cases, outputs those P when deg(R) <= deg_remainder.
If side_se=”left”, outputs the candidates P such that S = P S R. If side_se=”right”, outputs the candidates P such that S = R S P. In both cases, outputs those P when deg(R) <= deg_other_se.
If loop_over_all_ct=”left”, for each candidate P, check also k + P(x). If loop_over_all_ct=”right”, for each candidate P, check also P(x+k).
>>> temp_file = sage.all.tmp_filename('testing_find_all_divisor_se', '.txt') >>> find_krssb(n=3, d=2, terms=3, k=1, filename=temp_file) >>> x = PolynomialRing(GF(2**3, repr="int"), "x").gen() >>> # finding left divisors P such that S = P R, with deg(R)<=2 >>> find_divisors_or_selfequivs("x^6", temp_file, deg_remainder=2, side_divisor="left", field_var=x, verbose=True) # found left divisor; deg(R): 2, poly(R): x^6 + x^3 + x^2 x^3 + x^2 + x # found left divisor; deg(R): 2, poly(R): x^6 + x^5 + x^4 x^5 + x^4 + x # found left divisor; deg(R): 2, poly(R): x^6 + x^5 + x^4 + x^3 + x^2 x^5 + x^3 + x # found left divisor; deg(R): 2, poly(R): x^6 + x^5 + x^4 + x^3 + x x^6 + x^5 + x^4 # found left divisor; deg(R): 2, poly(R): x^6 + x^5 + x^3 + x^2 + x x^6 + x^3 + x^2 >>> # finding left self-equivalences P such that S = P S R, with deg(R)<=2 >>> find_divisors_or_selfequivs("x^6", temp_file, deg_other_se=2, side_se="left", field_var=x, verbose=False) [0, 1, 5, 2, 7, 4, 3, 6] [0, 1, 3, 6, 5, 2, 7, 4] [0, 1, 6, 5, 2, 7, 4, 3] [0, 1, 4, 3, 6, 5, 2, 7] [0, 1, 2, 7, 4, 3, 6, 5] >>> x = PolynomialRing(get_rijndael_field(), 'x').gen() >>> temp_file = sage.all.tmp_filename('testing_find_all_divisor_se_part2', '.txt') >>> # find_krssb8b_givaro(d=2, terms=5, k=1, output_filename=temp_file) >>> # finding left divisors P such that x^13 = P R, with deg(R)<=3 >>> # find_divisors_or_selfequivs("x^13", temp_file, deg_remainder=3, side_divisor="left", field_var=x, verbose=True) # found left divisor; deg(R): 3, poly(R): x^80 + x^65 + x^52 + x^20 + x^5 x^5 + x^20 + x^64 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^104 + x^80 + x^65 + x^20 + x^5 x^5 + x^20 + x^32 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^208 + x^80 + x^65 + x^20 + x^5 x^5 + x^16 + x^20 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^161 + x^80 + x^65 + x^20 + x^5 x^5 + x^8 + x^20 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^80 + x^67 + x^65 + x^20 + x^5 x^4 + x^5 + x^20 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^134 + x^80 + x^65 + x^20 + x^5 x^2 + x^5 + x^20 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^80 + x^65 + x^20 + x^13 + x^5 x + x^5 + x^20 + x^65 + x^80 # found left divisor; deg(R): 3, poly(R): x^160 + x^130 + x^40 + x^13 + x^10 x + x^10 + x^40 + x^130 + x^160
- boolcrypt.findpoly.check_permutation(input_file, mode, degree=None, output_file=None, field_var=None, num_char_per_elem=None, verbose=False)[source]
Check properties of permutations given in a file.
The permutation can be given as hex strings or str polynomials. If given as hex strings, the number of characters used element must be given (see hex_string2lut). If given as str polynomials, the variable of the polynomials must also be given.
List of modes:
“is_odd” outputs the permutations that are odd (like the inversion)
“inv_deg_max” outputs the permutations whose inverse degree are greater than the target degree
“inv_deg_min” outputs the permutations whose inverse degree are lower than the target degree
“unique” outputs the list of permutations without duplicates
“invertible” outputs the permutations that are invertible
“linear_repr” outputs the linear representatives, without duplicates
>>> x = PolynomialRing(get_rijndael_field(), 'x').gen() >>> temp_file = sage.all.tmp_filename('testing_check_lut', '.txt') >>> with open(temp_file, "w") as file: ... print("x", file=file) ... print("x", file=file) ... print("x**127", file=file) >>> check_permutation(temp_file, "is_odd", output_file=None, field_var=x) x**127 >>> check_permutation(temp_file, "inv_deg_min", degree=3, output_file=None, field_var=x) # 7 x**127 >>> check_permutation(temp_file, "inv_deg_max", degree=2, output_file=None, field_var=x) # 1 x # 1 x >>> check_permutation(temp_file, "unique", output_file=None, field_var=x) x x**127 >>> x = PolynomialRing(GF(2**4, repr="int"), 'x').gen() >>> cpe = 2 >>> temp_file = sage.all.tmp_filename('testing_check_lut2', '.txt') >>> with open(temp_file, "w") as file: ... print(lut2hex_string(poly2lut(x**2), cpe), file=file) ... print(lut2hex_string(poly2lut(x**3), cpe), file=file) ... print(lut2hex_string(poly2lut(x**6), cpe), file=file) >>> check_permutation(temp_file, "invertible", output_file=None, num_char_per_elem=cpe) 00010405030207060c0d08090f0e0b0a >>> check_permutation(temp_file, "linear_repr", output_file=None, num_char_per_elem=cpe) (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) (16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16)
- boolcrypt.findpoly.polyfile2hex(n, input_file, output_file=None, field_var=None)[source]
Return the hex representation of permutation polynomials.
>>> temp_file = sage.all.tmp_filename('test_poly2hex', '.txt') >>> with open(temp_file, "w") as file: ... print("x", file=file) ... print("x**127", file=file) >>> polyfile2hex(4, temp_file, output_file=None) 000102030405060708090a0b0c0d0e0f 00010b0d090e06070c0508030f02040a
- boolcrypt.findpoly.get_sas_decomposition(exponent, n, degree, max_degree=None)[source]
Find an SAS decomposition of a given power function f(x)=x^exponent, where A is an invertible linear monomial (x^2^i) and the S’s are invertible non-linear monomials with given algebraic degree.
Each decomposition is given by a triplet [a, b, c] where (a, c) are the exponents of the non-linear monomials and b is the exponent of the linear monomial.
>>> decompositions = get_sas_decomposition(127, 8, 3) >>> decompositions[:5] [[13, 1, 49], [13, 2, 152], [13, 4, 76], [13, 8, 38], [13, 16, 19]]
- boolcrypt.findpoly.get_monomial_permutation(n, alg_deg, field=None, ignore_le=False, verbose=False)[source]
Get all permutation monomials in GF(2^n) with given algebraic degree.
>>> get_monomial_permutation(4, 3, ignore_le=True, verbose=True) x^7 found x^11 but is LE to x^7 found x^13 but is LE to x^7 found x^14 but is LE to x^7 [x^7] >>> get_monomial_permutation(4, 3) [x^7, x^11, x^13, x^14] >>> get_monomial_permutation(8, 3, ignore_le=True, verbose=True) x^7 x^11 x^13 found x^14 but is LE to x^7 x^19 found x^22 but is LE to x^11 found x^26 but is LE to x^13 found x^28 but is LE to x^7 x^37 found x^38 but is LE to x^19 found x^41 but is LE to x^37 found x^44 but is LE to x^11 found x^49 but is LE to x^19 found x^52 but is LE to x^13 found x^56 but is LE to x^7 found x^67 but is LE to x^13 found x^73 but is LE to x^37 found x^74 but is LE to x^37 found x^76 but is LE to x^19 found x^82 but is LE to x^37 found x^88 but is LE to x^11 found x^97 but is LE to x^11 found x^98 but is LE to x^19 found x^104 but is LE to x^13 found x^112 but is LE to x^7 found x^131 but is LE to x^7 found x^133 but is LE to x^11 found x^134 but is LE to x^13 found x^137 but is LE to x^19 found x^146 but is LE to x^37 found x^148 but is LE to x^37 found x^152 but is LE to x^19 found x^161 but is LE to x^13 found x^164 but is LE to x^37 found x^176 but is LE to x^11 found x^193 but is LE to x^7 found x^194 but is LE to x^11 found x^196 but is LE to x^19 found x^208 but is LE to x^13 found x^224 but is LE to x^7 [x^7, x^11, x^13, x^19, x^37]
- boolcrypt.findpoly.find_quadratic_permutations(n, strong=False, filename=None)[source]
Find quadratic permutation in ANF form.
If strong=True, find permutations without linear components and with good differential properties. In this cases, LUTs are printed (instead of ANFs) together with their differential uniformity.
>>> find_quadratic_permutations(n=3) [x0, x1, x2] [x0, x1, x0*x1 + x2] [x0, x0*x2 + x1, x2] [x0, x0*x2 + x1, x0*x1 + x0*x2 + x2] [x0, x0*x1 + x0*x2 + x1, x0*x1 + x2] [x0, x0*x1 + x0*x2 + x1, x0*x1 + x0*x2 + x2] [x0 + x1*x2, x1, x2] [x0 + x1*x2, x1, x0*x1 + x1*x2 + x2] [x0 + x1*x2, x0*x1 + x0*x2 + x1, x0*x1 + x0*x2 + x2] [x0 + x1*x2, x0*x1 + x0*x2 + x1, x0*x1 + x1*x2 + x2] [x0 + x1*x2, x0*x2 + x1*x2 + x1, x2] [x0 + x1*x2, x0*x2 + x1*x2 + x1, x0*x1 + x0*x2 + x2] [x0*x1 + x0 + x1*x2, x1, x0*x1 + x2] [x0*x1 + x0 + x1*x2, x1, x0*x1 + x1*x2 + x2] [x0*x1 + x0 + x1*x2, x0*x2 + x1, x0*x1 + x0*x2 + x2] [x0*x1 + x0 + x1*x2, x0*x2 + x1, x0*x1 + x1*x2 + x2] [x0*x1 + x0 + x1*x2, x0*x2 + x1*x2 + x1, x0*x1 + x2] [x0*x1 + x0 + x1*x2, x0*x2 + x1*x2 + x1, x0*x1 + x0*x2 + x2] [x0*x2 + x0 + x1*x2, x0*x2 + x1, x2] [x0*x2 + x0 + x1*x2, x0*x2 + x1, x0*x1 + x1*x2 + x2] [x0*x2 + x0 + x1*x2, x0*x1 + x0*x2 + x1, x0*x1 + x2] [x0*x2 + x0 + x1*x2, x0*x1 + x0*x2 + x1, x0*x1 + x1*x2 + x2] [x0*x2 + x0 + x1*x2, x0*x2 + x1*x2 + x1, x2] [x0*x2 + x0 + x1*x2, x0*x2 + x1*x2 + x1, x0*x1 + x2] >>> find_quadratic_permutations(n=3, strong=True) 2 [0, 1, 2, 5, 4, 7, 3, 6] 2 [0, 1, 2, 7, 4, 3, 5, 6] 2 [0, 1, 2, 6, 4, 3, 7, 5] 2 [0, 1, 2, 6, 4, 7, 5, 3] 2 [0, 1, 2, 7, 4, 6, 3, 5] 2 [0, 1, 2, 5, 4, 6, 7, 3]