Boolean functions - Cryptography (original) (raw)
Those functions are used for example in LFSR based ciphers like the filter generator or the combination generator.
This module allows to study properties linked to spectral analysis, and also algebraic immunity.
EXAMPLES:
Sage
sage: # needs sage.rings.finite_rings sage: R. = GF(2^8,'a')[] sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction(x^254); B # the Boolean function Tr(x^254) Boolean function with 8 variables sage: B.nonlinearity() 112 sage: B.algebraic_immunity() # needs sage.rings.polynomial.pbori 4
Python
from sage.all import *
needs sage.rings.finite_rings
R = GF(Integer(2)Integer(8),'a')['x']; (x,) = R._first_ngens(1) from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction(xInteger(254)); B # the Boolean function Tr(x^254) Boolean function with 8 variables B.nonlinearity() 112 B.algebraic_immunity() # needs sage.rings.polynomial.pbori 4
AUTHOR:
- Rusydi H. Makarim (2016-10-13): add functions related to linear structures
- Rusydi H. Makarim (2016-07-09): add is_plateaued()
- Yann Laigle-Chapuy (2010-02-26): add basic arithmetic
- Yann Laigle-Chapuy (2009-08-28): first implementation
class sage.crypto.boolean_function.BooleanFunction[source]¶
Bases: SageObject
This module implements Boolean functions represented as a truth table.
We can construct a Boolean Function from either:
- an integer – the result is the zero function with
xvariables; - a list – it is expected to be the truth table of the result. Therefore it must be of length a power of 2, and its elements are interpreted as Booleans;
- a string – representing the truth table in hexadecimal;
- a Boolean polynomial – the result is the corresponding Boolean function;
- a polynomial \(P\) over an extension of \(\GF{2}\) – the result is the Boolean function with truth table
(Tr(P(x)) for x in GF(2^k))
EXAMPLES:
from the number of variables:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: BooleanFunction(5) Boolean function with 5 variables
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction BooleanFunction(Integer(5)) Boolean function with 5 variables
from a truth table:
Sage
sage: BooleanFunction([1,0,0,1]) Boolean function with 2 variables
Python
from sage.all import * BooleanFunction([Integer(1),Integer(0),Integer(0),Integer(1)]) Boolean function with 2 variables
note that elements can be of different types:
Sage
sage: B = BooleanFunction([False, sqrt(2)]); B # needs sage.symbolic Boolean function with 1 variable sage: [b for b in B] # needs sage.symbolic [False, True]
Python
from sage.all import * B = BooleanFunction([False, sqrt(Integer(2))]); B # needs sage.symbolic Boolean function with 1 variable [b for b in B] # needs sage.symbolic [False, True]
from a string:
Sage
sage: BooleanFunction("111e") Boolean function with 4 variables
Python
from sage.all import * BooleanFunction("111e") Boolean function with 4 variables
from a sage.rings.polynomial.pbori.BooleanPolynomial:
Sage
sage: R.<x,y,z> = BooleanPolynomialRing(3) # needs sage.rings.polynomial.pbori sage: P = x*y # needs sage.rings.polynomial.pbori sage: BooleanFunction(P) # needs sage.rings.polynomial.pbori Boolean function with 3 variables
Python
from sage.all import * R = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)# needs sage.rings.polynomial.pbori P = x*y # needs sage.rings.polynomial.pbori BooleanFunction(P) # needs sage.rings.polynomial.pbori Boolean function with 3 variables
from a polynomial over a binary field:
Sage
sage: R. = GF(2^8,'a')[] # needs sage.rings.finite_rings sage: B = BooleanFunction(x^7); B # needs sage.rings.finite_rings Boolean function with 8 variables
Python
from sage.all import * R = GF(Integer(2)Integer(8),'a')['x']; (x,) = R._first_ngens(1)# needs sage.rings.finite_rings B = BooleanFunction(xInteger(7)); B # needs sage.rings.finite_rings Boolean function with 8 variables
two failure cases:
Sage
sage: BooleanFunction(sqrt(2)) # needs sage.symbolic Traceback (most recent call last): ... TypeError: unable to init the Boolean function
sage: BooleanFunction([1, 0, 1]) Traceback (most recent call last): ... ValueError: the length of the truth table must be a power of 2
Python
from sage.all import * BooleanFunction(sqrt(Integer(2))) # needs sage.symbolic Traceback (most recent call last): ... TypeError: unable to init the Boolean function
BooleanFunction([Integer(1), Integer(0), Integer(1)]) Traceback (most recent call last): ... ValueError: the length of the truth table must be a power of 2
absolut_indicator(*args, **kwds)[source]¶
Deprecated: Use absolute_indicator() instead. See Issue #28001 for details.
absolute_autocorrelation()[source]¶
Return the absolute autocorrelation of the function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sage: sorted(B.absolute_autocorrelation().items()) [(0, 33), (8, 58), (16, 28), (24, 6), (32, 2), (128, 1)]
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sorted(B.absolute_autocorrelation().items()) [(0, 33), (8, 58), (16, 28), (24, 6), (32, 2), (128, 1)]
Return the absolute indicator of the function.
The absolute indicator is defined as the maximal absolute value of the autocorrelation.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sage: B.absolute_indicator() 32
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") B.absolute_indicator() 32
The old method’s name contained a typo, it is deprecated:
Sage
sage: B.absolut_indicator() doctest:warning ... DeprecationWarning: absolut_indicator is deprecated. Please use absolute_indicator instead. See https://github.com/sagemath/sage/issues/28001 for details. 32
Python
from sage.all import * B.absolut_indicator() doctest:warning ... DeprecationWarning: absolut_indicator is deprecated. Please use absolute_indicator instead. See https://github.com/sagemath/sage/issues/28001 for details. 32
absolute_walsh_spectrum()[source]¶
Return the absolute Walsh spectrum fo the function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sage: sorted(B.absolute_walsh_spectrum().items()) [(0, 64), (16, 64)]
sage: B = BooleanFunction("0113077C165E76A8") sage: B.absolute_walsh_spectrum() {8: 64}
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sorted(B.absolute_walsh_spectrum().items()) [(0, 64), (16, 64)]
B = BooleanFunction("0113077C165E76A8") B.absolute_walsh_spectrum() {8: 64}
Return the algebraic degree of this Boolean function.
The algebraic degree of a Boolean function is defined as the degree of its algebraic normal form. Note that the degree of the constant zero function is defined to be equal to \(-1\).
EXAMPLES:
Sage
sage: # needs sage.rings.polynomial.pbori sage: from sage.crypto.boolean_function import BooleanFunction sage: B.<x0, x1, x2, x3> = BooleanPolynomialRing() sage: f = BooleanFunction(x1x2 + x1x2*x3 + x1) sage: f.algebraic_degree() 3 sage: g = BooleanFunction([0, 0]) sage: g.algebraic_degree() -1
Python
from sage.all import *
needs sage.rings.polynomial.pbori
from sage.crypto.boolean_function import BooleanFunction B = BooleanPolynomialRing(names=('x0', 'x1', 'x2', 'x3',)); (x0, x1, x2, x3,) = B._first_ngens(4) f = BooleanFunction(x1x2 + x1x2*x3 + x1) f.algebraic_degree() 3 g = BooleanFunction([Integer(0), Integer(0)]) g.algebraic_degree() -1
algebraic_immunity(annihilator=False)[source]¶
Return the algebraic immunity of the Boolean function.
This is the smallest integer \(i\) such that there exists a nontrivial annihilator for self or ~self.
INPUT:
annihilator– boolean (default:False); ifTrue, returns also an annihilator of minimal degree
EXAMPLES:
Sage
sage: # needs sage.rings.polynomial.pbori sage: from sage.crypto.boolean_function import BooleanFunction sage: R.<x0,x1,x2,x3,x4,x5> = BooleanPolynomialRing(6) sage: B = BooleanFunction(x0x1 + x1x2 + x2x3 + x3x4 + x4x5) sage: B.algebraic_immunity(annihilator=True) (2, x0x1 + x1x2 + x2x3 + x3x4 + x4x5 + 1) sage: B[0] += 1 sage: B.algebraic_immunity() 2
sage: # needs sage.rings.finite_rings sage.rings.polynomial.pbori sage: R. = GF(2^8,'a')[] sage: B = BooleanFunction(x^31) sage: B.algebraic_immunity() 4
Python
from sage.all import *
needs sage.rings.polynomial.pbori
from sage.crypto.boolean_function import BooleanFunction R = BooleanPolynomialRing(Integer(6), names=('x0', 'x1', 'x2', 'x3', 'x4', 'x5',)); (x0, x1, x2, x3, x4, x5,) = R._first_ngens(6) B = BooleanFunction(x0x1 + x1x2 + x2x3 + x3x4 + x4x5) B.algebraic_immunity(annihilator=True) (2, x0x1 + x1x2 + x2x3 + x3x4 + x4x5 + 1) B[Integer(0)] += Integer(1) B.algebraic_immunity() 2
needs sage.rings.finite_rings sage.rings.polynomial.pbori
R = GF(Integer(2)Integer(8),'a')['x']; (x,) = R._first_ngens(1) B = BooleanFunction(xInteger(31)) B.algebraic_immunity() 4
algebraic_normal_form()[source]¶
Return the sage.rings.polynomial.pbori.BooleanPolynomialcorresponding to the algebraic normal form.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction([0,1,1,0,1,0,1,1]) sage: P = B.algebraic_normal_form(); P # needs sage.rings.polynomial.pbori x0x1x2 + x0 + x1*x2 + x1 + x2 sage: [P(*ZZ(i).digits(base=2, padto=3)) for i in range(8)] # needs sage.rings.polynomial.pbori [0, 1, 1, 0, 1, 0, 1, 1]
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction([Integer(0),Integer(1),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1)]) P = B.algebraic_normal_form(); P # needs sage.rings.polynomial.pbori x0x1x2 + x0 + x1*x2 + x1 + x2 [P(*ZZ(i).digits(base=Integer(2), padto=Integer(3))) for i in range(Integer(8))] # needs sage.rings.polynomial.pbori [0, 1, 1, 0, 1, 0, 1, 1]
annihilator(d, dim=False)[source]¶
Return (if it exists) an annihilator of the boolean function of degree at most \(d\), that is a Boolean polynomial \(g\) such that
\[f(x)g(x) = 0 \forall x.\]
INPUT:
d– integerdim– boolean (default:False); ifTrue, return also the dimension of the annihilator vector space
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: f = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sage: f.annihilator(1) is None # needs sage.rings.polynomial.pbori True sage: g = BooleanFunction(f.annihilator(3)) # needs sage.rings.polynomial.pbori sage: set(fi*g(i) for i,fi in enumerate(f)) # needs sage.rings.polynomial.pbori {0}
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction f = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") f.annihilator(Integer(1)) is None # needs sage.rings.polynomial.pbori True g = BooleanFunction(f.annihilator(Integer(3))) # needs sage.rings.polynomial.pbori set(fi*g(i) for i,fi in enumerate(f)) # needs sage.rings.polynomial.pbori {0}
Return the autocorrelation of the function, defined by
\[\Delta_f(j) = \sum_{i\in\{0,1\}^n} (-1)^{f(i)\oplus f(i\oplus j)}.\]
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("03") sage: B.autocorrelation() (8, 8, 0, 0, 0, 0, 0, 0)
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("03") B.autocorrelation() (8, 8, 0, 0, 0, 0, 0, 0)
correlation_immunity()[source]¶
Return the maximum value \(m\) such that the function is correlation immune of order \(m\).
A Boolean function is said to be correlation immune of order\(m\) if the output of the function is statistically independent of the combination of any \(m\) of its inputs.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sage: B.correlation_immunity() 2
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") B.correlation_immunity() 2
Return the derivative in direction of u.
INPUT:
u– either an integer or a tuple/list of \(\GF{2}\) elements of length equal to the number of variables
The derivative of \(f\) in direction of \(u\) is defined as\(x \mapsto f(x) + f(x + u)\).
EXAMPLES:
Sage
sage: # needs sage.rings.polynomial.pbori sage: from sage.crypto.boolean_function import BooleanFunction sage: f = BooleanFunction([0,1,0,1,0,1,0,1]) sage: f.derivative(1).algebraic_normal_form() 1 sage: u = [1,0,0] sage: f.derivative(u).algebraic_normal_form() 1 sage: v = vector(GF(2), u) # needs sage.modules sage: f.derivative(v).algebraic_normal_form() # needs sage.modules 1 sage: f.derivative(8).algebraic_normal_form() Traceback (most recent call last): ... IndexError: index out of bound
Python
from sage.all import *
needs sage.rings.polynomial.pbori
from sage.crypto.boolean_function import BooleanFunction f = BooleanFunction([Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(1)]) f.derivative(Integer(1)).algebraic_normal_form() 1 u = [Integer(1),Integer(0),Integer(0)] f.derivative(u).algebraic_normal_form() 1 v = vector(GF(Integer(2)), u) # needs sage.modules f.derivative(v).algebraic_normal_form() # needs sage.modules 1 f.derivative(Integer(8)).algebraic_normal_form() Traceback (most recent call last): ... IndexError: index out of bound
has_linear_structure()[source]¶
Return True if this function has a linear structure.
An \(n\)-variable Boolean function \(f\) has a linear structure if there exists a nonzero \(a \in \GF{2}^n\) such that\(f(x \oplus a) \oplus f(x)\) is a constant function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0]) sage: f.has_linear_structure() True sage: f.autocorrelation() (16, -16, 0, 0, 0, 0, 0, 0, -16, 16, 0, 0, 0, 0, 0, 0) sage: g = BooleanFunction([0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1]) sage: g.has_linear_structure() False sage: g.autocorrelation() (16, 4, 4, 4, 4, -4, -4, -4, -4, 4, -4, -4, -4, 4, -4, -4)
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction f = BooleanFunction([Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)]) f.has_linear_structure() True f.autocorrelation() (16, -16, 0, 0, 0, 0, 0, 0, -16, 16, 0, 0, 0, 0, 0, 0) g = BooleanFunction([Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(1), Integer(0), Integer(1), Integer(1)]) g.has_linear_structure() False g.autocorrelation() (16, 4, 4, 4, 4, -4, -4, -4, -4, 4, -4, -4, -4, 4, -4, -4)
Return True if the function takes the value True half of the time.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction(1) sage: B.is_balanced() False sage: B[0] = True sage: B.is_balanced() True
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction(Integer(1)) B.is_balanced() False B[Integer(0)] = True B.is_balanced() True
Return True if the function is bent.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("0113077C165E76A8") sage: B.is_bent() True
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("0113077C165E76A8") B.is_bent() True
is_linear_structure(val)[source]¶
Return True if val is a linear structure of this Boolean function.
INPUT:
val– either an integer or a tuple/list of \(\GF{2}\) elements of length equal to the number of variables
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0]) sage: f.is_linear_structure(1) True sage: l = [1, 0, 0, 1] sage: f.is_linear_structure(l) True sage: v = vector(GF(2), l) sage: f.is_linear_structure(v) True sage: f.is_linear_structure(7) False sage: f.is_linear_structure(20) # parameter is out of range Traceback (most recent call last): ... IndexError: index out of range sage: v = vector(GF(3), [1, 0, 1, 1]) sage: f.is_linear_structure(v) Traceback (most recent call last): ... TypeError: base ring of input vector must be GF(2) sage: v = vector(GF(2), [1, 0, 1, 1, 1]) sage: f.is_linear_structure(v) Traceback (most recent call last): ... TypeError: input vector must be an element of a vector space with dimension 4 sage: f.is_linear_structure('X') # failure case Traceback (most recent call last): ... TypeError: cannot compute is_linear_structure() using parameter X
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction f = BooleanFunction([Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)]) f.is_linear_structure(Integer(1)) True l = [Integer(1), Integer(0), Integer(0), Integer(1)] f.is_linear_structure(l) True v = vector(GF(Integer(2)), l) f.is_linear_structure(v) True f.is_linear_structure(Integer(7)) False f.is_linear_structure(Integer(20)) # parameter is out of range Traceback (most recent call last): ... IndexError: index out of range v = vector(GF(Integer(3)), [Integer(1), Integer(0), Integer(1), Integer(1)]) f.is_linear_structure(v) Traceback (most recent call last): ... TypeError: base ring of input vector must be GF(2) v = vector(GF(Integer(2)), [Integer(1), Integer(0), Integer(1), Integer(1), Integer(1)]) f.is_linear_structure(v) Traceback (most recent call last): ... TypeError: input vector must be an element of a vector space with dimension 4 f.is_linear_structure('X') # failure case Traceback (most recent call last): ... TypeError: cannot compute is_linear_structure() using parameter X
Return True if this function is plateaued, i.e. its Walsh transform takes at most three values \(0\) and \(\pm \lambda\), where \(\lambda\) is some positive integer.
EXAMPLES:
Sage
sage: # needs sage.rings.polynomial.pbori sage: from sage.crypto.boolean_function import BooleanFunction sage: R.<x0, x1, x2, x3> = BooleanPolynomialRing() sage: f = BooleanFunction(x0*x1 + x2 + x3) sage: f.walsh_hadamard_transform() (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, -8) sage: f.is_plateaued() True
Python
from sage.all import *
needs sage.rings.polynomial.pbori
from sage.crypto.boolean_function import BooleanFunction R = BooleanPolynomialRing(names=('x0', 'x1', 'x2', 'x3',)); (x0, x1, x2, x3,) = R._first_ngens(4) f = BooleanFunction(x0*x1 + x2 + x3) f.walsh_hadamard_transform() (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, -8) f.is_plateaued() True
Return True if the function is symmetric, i.e. invariant under permutation of its input bits.
Another way to see it is that the output depends only on the Hamming weight of the input.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction(5) sage: B[3] = 1 sage: B.is_symmetric() False sage: V_B = [0, 1, 1, 0, 1, 0] sage: for i in srange(32): B[i] = V_B[i.popcount()] sage: B.is_symmetric() True
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction(Integer(5)) B[Integer(3)] = Integer(1) B.is_symmetric() False V_B = [Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0)] for i in srange(Integer(32)): B[i] = V_B[i.popcount()] B.is_symmetric() True
Return all linear structures of this Boolean function as a vector subspace of \(\GF{2}^n\).
EXAMPLES:
Sage
sage: # needs sage.modules sage: from sage.crypto.boolean_function import BooleanFunction sage: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0]) sage: LS = f.linear_structures() sage: LS.dimension() 2 sage: LS.basis_matrix() [1 0 0 0] [0 0 0 1] sage: LS.list() [(0, 0, 0, 0), (1, 0, 0, 0), (0, 0, 0, 1), (1, 0, 0, 1)]
Python
from sage.all import *
needs sage.modules
from sage.crypto.boolean_function import BooleanFunction f = BooleanFunction([Integer(0), Integer(1), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(1), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0)]) LS = f.linear_structures() LS.dimension() 2 LS.basis_matrix() [1 0 0 0] [0 0 0 1] LS.list() [(0, 0, 0, 0), (1, 0, 0, 0), (0, 0, 0, 1), (1, 0, 0, 1)]
Return the nonlinearity of the function.
This is the distance to the linear functions, or the number of output ones need to change to obtain a linear function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction(5) sage: B[1] = B[3] = 1 sage: B.nonlinearity() 2 sage: B = BooleanFunction("0113077C165E76A8") sage: B.nonlinearity() 28
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction(Integer(5)) B[Integer(1)] = B[Integer(3)] = Integer(1) B.nonlinearity() 2 B = BooleanFunction("0113077C165E76A8") B.nonlinearity() 28
The number of variables of this function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: BooleanFunction(4).nvariables() 4
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction BooleanFunction(Integer(4)).nvariables() 4
Return the maximum value \(m\) such that the function is resilient of order \(m\).
A Boolean function is said to be resilient of order \(m\) if it is balanced and correlation immune of order \(m\).
If the function is not balanced, we return \(-1\).
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("077CE5A2F8831A5DF8831A5D077CE5A26996699669699696669999665AA5A55A") sage: B.resiliency_order() 3
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("077CE5A2F8831A5DF8831A5D077CE5A26996699669699696669999665AA5A55A") B.resiliency_order() 3
sum_of_square_indicator()[source]¶
Return the sum of square indicator of the function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") sage: B.sum_of_square_indicator() 32768
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0") B.sum_of_square_indicator() 32768
truth_table(format='bin')[source]¶
The truth table of the Boolean function.
INPUT:
format– string representing the desired format; can be either'bin'– (default) we return a tuple of Boolean values'int'– we return a tuple of 0 or 1 values'hex'– we return a string representing the truth table in hexadecimal
EXAMPLES:
Sage
sage: # needs sage.rings.polynomial.pbori sage: from sage.crypto.boolean_function import BooleanFunction sage: R.<x,y,z> = BooleanPolynomialRing(3) sage: B = BooleanFunction(xyz + z + y + 1) sage: B.truth_table() (True, True, False, False, False, False, True, False) sage: B.truth_table(format='int') (1, 1, 0, 0, 0, 0, 1, 0) sage: B.truth_table(format='hex') '43'
sage: BooleanFunction('00ab').truth_table(format='hex') # needs sage.rings.polynomial.pbori '00ab'
sage: # needs sage.rings.polynomial.pbori sage: H = '0abbacadabbacad0' sage: len(H) 16 sage: T = BooleanFunction(H).truth_table(format='hex') sage: T == H True sage: H = H * 4 sage: T = BooleanFunction(H).truth_table(format='hex') sage: T == H True sage: H = H * 4 sage: T = BooleanFunction(H).truth_table(format='hex') sage: T == H True sage: len(T) 256 sage: B.truth_table(format='oct') Traceback (most recent call last): ... ValueError: unknown output format
Python
from sage.all import *
needs sage.rings.polynomial.pbori
from sage.crypto.boolean_function import BooleanFunction R = BooleanPolynomialRing(Integer(3), names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3) B = BooleanFunction(xyz + z + y + Integer(1)) B.truth_table() (True, True, False, False, False, False, True, False) B.truth_table(format='int') (1, 1, 0, 0, 0, 0, 1, 0) B.truth_table(format='hex') '43'
BooleanFunction('00ab').truth_table(format='hex') # needs sage.rings.polynomial.pbori '00ab'
needs sage.rings.polynomial.pbori
H = '0abbacadabbacad0' len(H) 16 T = BooleanFunction(H).truth_table(format='hex') T == H True H = H * Integer(4) T = BooleanFunction(H).truth_table(format='hex') T == H True H = H * Integer(4) T = BooleanFunction(H).truth_table(format='hex') T == H True len(T) 256 B.truth_table(format='oct') Traceback (most recent call last): ... ValueError: unknown output format
walsh_hadamard_transform()[source]¶
Compute the Walsh Hadamard transform \(W\) of the function \(f\).
\[W(j) = \sum_{i\in\{0,1\}^n} (-1)^{f(i)\oplus i \cdot j}\]
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: R. = GF(2^3,'a')[] # needs sage.rings.finite_rings sage: B = BooleanFunction(x^3) # needs sage.rings.finite_rings sage: B.walsh_hadamard_transform() # needs sage.rings.finite_rings (0, -4, 0, 4, 0, 4, 0, 4)
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction R = GF(Integer(2)Integer(3),'a')['x']; (x,) = R._first_ngens(1)# needs sage.rings.finite_rings B = BooleanFunction(xInteger(3)) # needs sage.rings.finite_rings B.walsh_hadamard_transform() # needs sage.rings.finite_rings (0, -4, 0, 4, 0, 4, 0, 4)
class sage.crypto.boolean_function.BooleanFunctionIterator[source]¶
Bases: object
Iterator through the values of a Boolean function.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction(3) sage: type(B.iter()) <class 'sage.crypto.boolean_function.BooleanFunctionIterator'>
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction(Integer(3)) type(B.iter()) <class 'sage.crypto.boolean_function.BooleanFunctionIterator'>
sage.crypto.boolean_function.random_boolean_function(n)[source]¶
Return a random Boolean function with \(n\) variables.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import random_boolean_function sage: B = random_boolean_function(9) sage: B.nvariables() 9 sage: while not (210 < B.nonlinearity() < 220): ....: B = random_boolean_function(9)
Python
from sage.all import * from sage.crypto.boolean_function import random_boolean_function B = random_boolean_function(Integer(9)) B.nvariables() 9 while not (Integer(210) < B.nonlinearity() < Integer(220)): ... B = random_boolean_function(Integer(9))
sage.crypto.boolean_function.unpickle_BooleanFunction(bool_list)[source]¶
Specific function to unpickle Boolean functions.
EXAMPLES:
Sage
sage: from sage.crypto.boolean_function import BooleanFunction sage: B = BooleanFunction([0,1,1,0]) sage: loads(dumps(B)) == B # indirect doctest True
Python
from sage.all import * from sage.crypto.boolean_function import BooleanFunction B = BooleanFunction([Integer(0),Integer(1),Integer(1),Integer(0)]) loads(dumps(B)) == B # indirect doctest True