S-Boxes and Their Algebraic Representations#

class sage.crypto.sbox.SBox#

Bases: SageObject

A substitution box or S-box is one of the basic components of symmetric key cryptography. In general, an S-box takes \(m\) input bits and transforms them into \(n\) output bits. This is called an \(m \times n\) S-box and is often implemented as a lookup table. These S-boxes are carefully chosen to resist linear and differential cryptanalysis [He2002].

This module implements an S-box class which allows an algebraic treatment and determine various cryptographic properties.

EXAMPLES:

We consider the S-box of the block cipher PRESENT [BKLPPRSV2007]:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2); S
(12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2)
sage: S(1)
5

Note that by default bits are interpreted in big endian order. This is not consistent with the rest of Sage, which has a strong bias towards little endian, but is consistent with most cryptographic literature:

sage: S([0,0,0,1])
[0, 1, 0, 1]

sage: S = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2, big_endian=False)
sage: S(1)
5
sage: S([0,0,0,1])
[1, 1, 0, 0]

Now we construct an SBox object for the 4-bit small scale AES S-Box (cf. sage.crypto.mq.sr):

sage: sr = mq.SR(1,1,1,4, allow_zero_inversions=True)
sage: S = SBox([sr.sub_byte(e) for e in list(sr.k)])
sage: S
(6, 5, 2, 9, 4, 7, 3, 12, 14, 15, 10, 0, 8, 1, 13, 11)

AUTHORS:

  • Rusydi H. Makarim (2016-03-31) : added more functions to determine related cryptographic properties

  • Yann Laigle-Chapuy (2009-07-01): improve linear and difference matrix computation

  • Martin R. Albrecht (2008-03-12): initial implementation

REFERENCES:

autocorrelation_table()#

Return the autocorrelation table corresponding to this S-Box.

for an \(m \times n\) S-Box \(S\), its autocorrelation table entry at row \(a \in \GF{2}^m\) and column \(b \in \GF{2}^n\) (considering their integer representation) is defined as:

\[\sum_{x \in \GF{2}^m} (-1)^{b \cdot S(x) \oplus b \cdot S(x \oplus a)}.\]

Equivalently, the columns \(b\) of autocorrelation table correspond to the autocorrelation spectrum of component function \(b \cdot S(x)\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.autocorrelation_table()                                             # needs sage.combinat
[ 8  8  8  8  8  8  8  8]
[ 8  0  0  0  0  0  0 -8]
[ 8  0 -8  0  0  0  0  0]
[ 8  0  0  0  0 -8  0  0]
[ 8 -8  0  0  0  0  0  0]
[ 8  0  0  0  0  0 -8  0]
[ 8  0  0 -8  0  0  0  0]
[ 8  0  0  0 -8  0  0  0]
boomerang_connectivity_table()#

Return the boomerang connectivity table (BCT) for this S-Box.

Boomerang connectivity matrix of an invertible \(m \times m\) S-Box \(S\) is an \(2^m \times 2^m\) matrix with entry at row \(\Delta_i \in \GF{2}^m\) and column \(\Delta_o \in \GF{2}^m\) equal to

\[|\{ x \in \GF{2}^m | S^{-1}( S(x) \oplus \Delta_o) \oplus S^{-1}( S(x \oplus \Delta_i) \oplus \Delta_o) = \Delta_i\}|.\]

For more results concerning boomerang connectivity matrix, see [CHPSS18]. The algorithm used here is the one from Dunkelman [Du2018].

EXAMPLES:

sage: from sage.crypto.sboxes import PRESENT
sage: PRESENT.boomerang_connectivity_table()
[16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16]
[16  0  4  4  0 16  4  4  4  4  0  0  4  4  0  0]
[16  0  0  6  0  4  6  0  0  0  2  0  2  2  2  0]
[16  2  0  6  2  4  4  2  0  0  2  2  0  0  0  0]
[16  0  0  0  0  4  2  2  0  6  2  0  6  0  2  0]
[16  2  0  0  2  4  0  0  0  6  2  2  4  2  0  0]
[16  4  2  0  4  0  2  0  2  0  0  4  2  0  4  8]
[16  4  2  0  4  0  2  0  2  0  0  4  2  0  4  8]
[16  4  0  2  4  0  0  2  0  2  0  4  0  2  4  8]
[16  4  2  0  4  0  2  0  2  0  0  4  2  0  4  8]
[16  0  2  2  0  4  0  0  6  0  2  0  0  6  2  0]
[16  2  0  0  2  4  0  0  4  2  2  2  0  6  0  0]
[16  0  6  0  0  4  0  6  2  2  2  0  0  0  2  0]
[16  2  4  2  2  4  0  6  0  0  2  2  0  0  0  0]
[16  0  2  2  0  0  2  2  2  2  0  0  2  2  0  0]
[16  8  0  0  8  0  0  0  0  0  0  8  0  0  8 16]
boomerang_uniformity()#

Return the boomerang uniformity

The boomerang uniformity is defined as the highest entry in the boomerang connectivity table, ignoring the first row and column.

EXAMPLES:

sage: from sage.crypto.sboxes import AES
sage: AES.boomerang_uniformity()
6
cnf(xi=None, yi=None, format=None)#

Return a representation of this S-Box in conjunctive normal form.

This function examines the truth tables for each output bit of the S-Box and thus has complexity \(n * 2^m\) for an \(m \times n\) S-Box.

INPUT:

  • xi – (default: 1...m) indices for the input variables

  • yi – (default: m+1 ... m+n) indices for the output variables

  • format – (default: None) output format, see below

FORMATS:

  • None – return a list of tuples of integers where each tuple represents a clause, the absolute value of an integer represents a variable and the sign of an integer indicates inversion

  • symbolic – a string that can be parsed by the SymbolicLogic package

  • dimacs – a string in DIMACS format which is the gold standard for SAT-solver input (cf. http://www.satlib.org/)

  • dimacs_headless – a string in DIMACS format, but without the header; this is useful for concatenation of outputs

EXAMPLES:

We give a very small example to explain the output format:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(1,2,0,3); S
(1, 2, 0, 3)
sage: cnf = S.cnf(); cnf
[(1, 2, -3),  (1, 2, 4),
 (1, -2, 3),  (1, -2, -4),
 (-1, 2, -3), (-1, 2, -4),
 (-1, -2, 3), (-1, -2, 4)]

This output completely describes the S-Box. For instance, we can check that S([0,1]) -> [1,0] satisfies every clause if the first input bit corresponds to the index 1 and the last output bit corresponds to the index 3 in the output.

We can convert this representation to the DIMACS format:

sage: print(S.cnf(format='dimacs'))
p cnf 4 8
1 2 -3 0
1 2 4 0
1 -2 3 0
1 -2 -4 0
-1 2 -3 0
-1 2 -4 0
-1 -2 3 0
-1 -2 4 0

For concatenation we can strip the header:

sage: print(S.cnf(format='dimacs_headless'))
1 2 -3 0
1 2 4 0
1 -2 3 0
1 -2 -4 0
-1 2 -3 0
-1 2 -4 0
-1 -2 3 0
-1 -2 4 0

This might be helpful in combination with the xi and yi parameter to assign indices manually:

sage: print(S.cnf(xi=[10,20],yi=[30,40], format='dimacs_headless'))
10 20 -30 0
10 20 40 0
10 -20 30 0
10 -20 -40 0
-10 20 -30 0
-10 20 -40 0
-10 -20 30 0
-10 -20 40 0

We can also return a string which is parse-able by the SymbolicLogic package:

sage: log = SymbolicLogic()
sage: s = log.statement(S.cnf(format='symbolic'))
sage: log.truthtable(s)[1:]
[['False', 'False', 'False', 'False', 'False'],
 ['False', 'False', 'False', 'True', 'False'],
 ['False', 'False', 'True', 'False', 'False'],
 ['False', 'False', 'True', 'True', 'True'],
 ['False', 'True', 'False', 'False', 'True'],
 ['False', 'True', 'False', 'True', 'True'],
 ['False', 'True', 'True', 'False', 'True'],
 ['False', 'True', 'True', 'True', 'True'],
 ['True', 'False', 'False', 'False', 'True'],
 ['True', 'False', 'False', 'True', 'True'],
 ['True', 'False', 'True', 'False', 'True'],
 ['True', 'False', 'True', 'True', 'True'],
 ['True', 'True', 'False', 'False', 'True'],
 ['True', 'True', 'False', 'True', 'True'],
 ['True', 'True', 'True', 'False', 'True'],
 ['True', 'True', 'True', 'True', 'True']]

This function respects endianness of the S-Box:

sage: S = SBox(1,2,0,3, big_endian=False); S
(1, 2, 0, 3)
sage: cnf = S.cnf(); cnf
[(1, 2, -4), (1, 2, 3),
 (-1, 2, 4), (-1, 2, -3),
 (1, -2, -4), (1, -2, -3),
 (-1, -2, 4), (-1, -2, 3)]

S-Boxes with m!=n also work:

sage: o = list(range(8)) + list(range(8)) sage: shuffle(o) sage: S = SBox(o) sage: S.is_permutation() False

sage: len(S.cnf()) == 3*2^4 True

component_function(b)#

Return a Boolean function corresponding to the component function \(b \cdot S(x)\).

If \(S\) is an \(m \times n\) S-Box, then \(b \in \GF{2}^n\) and \(\cdot\) denotes dot product of two vectors.

INPUT:

  • b – either an integer or a list/tuple/vector of \(\GF{2}\) elements of length self.output_size()

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([7,6,0,4,2,5,1,3])
sage: f3 = S.component_function(3)
sage: f3.algebraic_normal_form()                                            # needs sage.rings.polynomial.pbori
x0*x1 + x0*x2 + x0 + x2

sage: f5 = S.component_function([1, 0, 1])
sage: f5.algebraic_normal_form()                                            # needs sage.rings.polynomial.pbori
x0*x2 + x0 + x1*x2
derivative(u)#

Return the derivative in direction of u

INPUT:

  • u – either an integer or a tuple/list of \(\GF{2}\) elements of length equal to m

The derivative of \(F\) in direction of \(u\) is defined as \(x \mapsto F(x) + F(x + u)\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: s = SBox(0,1,2,3)
sage: s.derivative(1)
(1, 1, 1, 1)
sage: u = [1,0]
sage: s.derivative(u)
(1, 1, 1, 1)
sage: v = vector(GF(2), [1,0])
sage: s.derivative(v)
(1, 1, 1, 1)
sage: s.derivative(4)
Traceback (most recent call last):
...
IndexError: list index out of range
sage: from sage.crypto.sboxes import PRESENT
sage: PRESENT.derivative(1).max_degree() < PRESENT.max_degree()             # needs sage.rings.polynomial.pbori
True
difference_distribution_table()#

Return difference distribution table (DDT) A for this S-box.

The rows of A encode the differences Delta I of the input and the columns encode the difference Delta O for the output. The bits are ordered according to the endianess of this S-box. The value at A[Delta I,Delta O] encodes how often Delta O is the actual output difference given Delta I as input difference.

See [He2002] for an introduction to differential cryptanalysis.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.difference_distribution_table()
[8 0 0 0 0 0 0 0]
[0 2 2 0 2 0 0 2]
[0 0 2 2 0 0 2 2]
[0 2 0 2 2 0 2 0]
[0 2 0 2 0 2 0 2]
[0 0 2 2 2 2 0 0]
[0 2 2 0 0 2 2 0]
[0 0 0 0 2 2 2 2]
sage: S = SBox(7,4,8,6)
sage: S.difference_distribution_table()
[4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 2 0 0 0 0 0 0 0 0 0 0 2 0]
[0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 2]
[0 2 0 0 0 0 0 0 0 0 0 0 2 0 0 0]
differential_branch_number()#

Return differential branch number of this S-Box.

The differential branch number of an S-Box \(S\) is defined as

\[\min_{v, w \neq v} \{ \mathrm{wt}(v \oplus w) + \mathrm{wt}(S(v) \oplus S(w)) \},\]

where \(\mathrm{wt}(x)\) denotes the Hamming weight of vector \(x\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.differential_branch_number()
3
differential_uniformity()#

Return the difference probability of the difference with the highest probability in absolute terms, i.e. how often it occurs in total.

Equivalently, this is equal to the differential uniformity of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_difference_probability_absolute()
2

Note

This code is mainly called internally.

fixed_points()#

Return a list of all fixed points of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.fixed_points()
[0, 1]
from_bits(x, n=None)#

Return integer for bitstring x of length n.

INPUT:

  • x – a bitstring

  • n – bit length (optional)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.from_bits( [1,1,0])
6

sage: S( S.from_bits( [1,1,0] ) )
1
sage: S.from_bits( S( [1,1,0] ) )
1
has_linear_structure()#

Return True if there exists a nonzero component function of this S-Box that has a linear structure.

See also

is_linear_structure(), linear_structures().

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2)
sage: S.has_linear_structure()
True
input_size()#

Return the input size of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0, 3, 2, 1, 1, 3, 2, 0])
sage: S.input_size()
3
interpolation_polynomial(k=None)#

Return a univariate polynomial over an extension field representing this S-box.

If m is the input length of this S-box then the extension field is of degree m.

If the output length does not match the input length then a TypeError is raised.

INPUT:

  • k – (optional) an instance of \(\GF{2^m}\)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: f = S.interpolation_polynomial()
sage: f
(a^2 + a + 1)*x^6 + a^2*x^5 + (a + 1)*x^4 + (a^2 + a)*x^3
 + x^2 + a*x + a^2 + a + 1

sage: a = f.base_ring().gen()

sage: f(0), S(0)
(a^2 + a + 1, 7)

sage: f(a^2 + 1), S(5)
(a^2 + 1, 5)

Note

The method-internal call to the S-box initially used a different endianess for handling finite field elements. This changed in github issue #25633, by calling the S-box directly.

inverse()#

Return the inverse of this S-Box.

Note that the S-Box must be invertible, otherwise it will raise a TypeError.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0, 1, 3, 6, 7, 4, 5, 2])
sage: Sinv = S.inverse()
sage: [Sinv(S(i)) for i in range(8)]
[0, 1, 2, 3, 4, 5, 6, 7]
is_almost_bent()#

Return True if this S-Box is an almost bent (AB) function.

An \(m \times m\) S-Box \(S\), for \(m\) odd, is called almost bent if its nonlinearity is equal to \(2^{m-1} - 2^{(m-1)/2}\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.is_almost_bent()
True
is_apn()#

Return True if this S-Box is an almost perfect nonlinear (APN) function.

An \(m \times m\) S-Box \(S\) is called almost perfect nonlinear if for every nonzero \(\alpha \in \GF{2}^m\) and every \(\beta \in \GF{2}^m\), the equation \(S(x) \oplus S(x \oplus \alpha) = \beta\) has 0 or 2 solutions. Equivalently, the differential uniformity of \(S\) is equal to 2.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.is_apn()
True
sage: S.differential_uniformity()
2
is_balanced()#

Return True if this S-Box is balanced.

An S-Box is balanced if all its component functions are balanced.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.is_balanced()
True
is_bent()#

Return True if this S-Box is bent, i.e. its nonlinearity is equal to \(2^{m-1} - 2^{m/2 - 1}\) where \(m\) is the input size of the S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: R.<x> = GF(2**2, 'a')[]
sage: base = R.base_ring()
sage: a = base.gen()
sage: G = a * x^2 + 1
sage: S = SBox([G(x * y**(14)) for x in sorted(base) for y in sorted(base)])
sage: S.is_bent()
True
sage: S.nonlinearity()
6
sage: S.linear_approximation_table()
[ 8 -2  2 -2]
[ 0 -2  2 -2]
[ 0 -2  2 -2]
[ 0 -2  2 -2]
[ 0 -2  2 -2]
[ 0 -2 -2  2]
[ 0  2  2  2]
[ 0  2 -2 -2]
[ 0 -2  2 -2]
[ 0  2 -2 -2]
[ 0 -2 -2  2]
[ 0  2  2  2]
[ 0 -2  2 -2]
[ 0  2  2  2]
[ 0  2 -2 -2]
[ 0 -2 -2  2]
is_involution()#

Return True if this S-Box is an involution, i.e. the inverse S-Box is equal itself.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([x**254 for x in sorted(GF(2**8))])
sage: S.is_involution()
True
is_linear_structure(a, b)#

Return True if \(a\) is a linear structure of the component function \(b \cdot S(x)\) where S is this \(m \times n\) S-Box.

INPUT:

  • a – either an integer or a tuple of \(\GF{2}\) elements of length equal to the input size of SBox

  • b – either an integer or a tuple of \(\GF{2}\) elements of length equal to the output size of SBox

See also

linear_structures(), has_linear_structure()

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2)
sage: S.component_function(1).autocorrelation()
(16, -16, 0, 0, 0, 0, 0, 0, -16, 16, 0, 0, 0, 0, 0, 0)
sage: S.is_linear_structure(1, 1)
True
sage: S.is_linear_structure([1, 0, 0, 1], [0, 0, 0, 1])
True
sage: S.is_linear_structure([0, 1, 1, 1], 1)
False
is_monomial_function()#

Return True if this S-Box is a monomial/power function.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.is_monomial_function()
False
sage: S_poly = S.interpolation_polynomial(); S_poly
(a + 1)*x^6 + (a^2 + a + 1)*x^5 + (a^2 + a)*x^4
 + (a^2 + 1)*x^3 + a*x^2 + a*x

sage: all([S(x) == S_poly(x) for x in S_poly.base_ring()])
True

sage: S = SBox(0,3,2,1)
sage: S.interpolation_polynomial()
x^2
sage: S.is_monomial_function()
True
is_permutation()#

Return True if this S-Box is a permutation.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.is_permutation()
True

sage: S = SBox(3,2,0,0,2,1,1,3)
sage: S.is_permutation()
False
is_plateaued()#

Return True if this S-Box is plateaued, i.e. for all nonzero \(b \in \GF{2}^n\) the Boolean function \(b \cdot S(x)\) is plateaued.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(0, 3, 1, 2, 4, 6, 7, 5)
sage: S.is_plateaued()
True
linear_approximation_table(scale='absolute_bias')#

Return linear approximation table (LAT) \(A\) for this S-box.

The entry \(A[\alpha,\beta]\) corresponds to the probability \(Pr[\alpha\cdot x = \beta\cdot S(x)]\), where \(S\) is this S-box mapping \(n\)-bit inputs to \(m\)-bit outputs. There are three typical notations for this probability used in the literature:

  • \(Pr[\alpha\cdot x = \beta\cdot S(x)] = 1/2 + e(\alpha, \beta)\), where \(e(\alpha, \beta)\) is called the bias,

  • \(2\cdot Pr[\alpha\cdot x = \beta\cdot S(x)] = 1 + c(\alpha, \beta)\), where \(c(\alpha, \beta) = 2\cdot e(\alpha, \beta)\) is the correlation, and

  • \(2^{(m+1)}\cdot Pr[\alpha\cdot x = \beta\cdot S(x)] = 2^m + \hat{S}(\alpha, \beta)\), where \(\hat{S}(\alpha, \beta)\) is the Fourier coefficient of S.

See [He2002] for an introduction to linear cryptanalysis.

INPUT:

  • scale - string to choose the scaling for the LAT, one of

    • “bias”: elements are \(e(\alpha, \beta)\)

    • “correlation”: elements are \(c(\alpha, \beta)\)

    • “absolute_bias”: elements are \(2^m\cdot e(\alpha, \beta)\) (default)

    • “fourier_coefficient”: elements are \(\hat{S}(\alpha, \beta)\)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: lat_abs_bias = S.linear_approximation_table()
sage: lat_abs_bias
[ 4  0  0  0  0  0  0  0]
[ 0  0  0  0  2  2  2 -2]
[ 0  0 -2 -2 -2  2  0  0]
[ 0  0 -2  2  0  0 -2 -2]
[ 0  2  0  2 -2  0  2  0]
[ 0 -2  0  2  0  2  0  2]
[ 0 -2 -2  0  0 -2  2  0]
[ 0 -2  2  0 -2  0  0 -2]

sage: lat_abs_bias/(1 << S.input_size()) == S.linear_approximation_table(scale="bias")
True

sage: lat_abs_bias/(1 << (S.input_size()-1)) == S.linear_approximation_table(scale="correlation")
True

sage: lat_abs_bias*2 == S.linear_approximation_table(scale="fourier_coefficient")
True

According to this table the first bit of the input is equal to the third bit of the output 6 out of 8 times:

sage: for i in srange(8): print(S.to_bits(i)[0] == S.to_bits(S(i))[2])
False
True
True
True
False
True
True
True
linear_branch_number()#

Return linear branch number of this S-Box.

The linear branch number of an S-Box \(S\) is defined as

\[\begin{split}\min_{\substack{\alpha \neq 0, \beta \\ \mathrm{LAM}(\alpha, \beta) \neq 0}} \{ \mathrm{wt}(\alpha) + \mathrm{wt}(\beta) \},\end{split}\]

where \(\mathrm{LAM}(\alpha, \beta)\) is the entry at row \(\alpha\) and column \(\beta\) of linear approximation matrix correspond to this S-Box. The \(\mathrm{wt}(x)\) denotes the Hamming weight of \(x\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.linear_branch_number()
2
linear_structures()#

Return a list of 3-valued tuple \((b, \alpha, c)\) such that \(\alpha\) is a \(c\)-linear structure of the component function \(b \cdot S(x)\).

A Boolean function \(f : \GF{2}^m \mapsto \GF{2}\) is said to have a \(c\)-linear structure if there exists a nonzero \(\alpha\) such that \(f(x) \oplus f(x \oplus \alpha)\) is a constant function \(c\).

An \(m \times n\) S-Box \(S\) has a linear structure if there exists a component function \(b \cdot S(x)\) that has a linear structure.

The three valued tuple \((b, \alpha, c)\) shows that \(\alpha\) is a \(c\)-linear structure of the component function \(b \cdot S(x)\). This implies that for all output differences \(\beta\) of the S-Box correspond to input difference \(\alpha\), we have \(b \cdot \beta = c\).

See also

is_linear_structure(), has_linear_structure()

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0,1,3,6,7,4,5,2])
sage: S.linear_structures()                                                 # needs sage.combinat
[(1, 1, 1), (2, 2, 1), (3, 3, 1), (4, 4, 1),
 (5, 5, 1), (6, 6, 1), (7, 7, 1)]
linearity()#

Return the linearity of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = mq.SR(1, 4, 4, 8).sbox()
sage: S.linearity()
32
max_degree()#

Return the maximal algebraic degree of all its component functions.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.max_degree()                                                        # needs sage.rings.polynomial.pbori
3
maximal_difference_probability()#

Return the difference probability of the difference with the highest probability in the range between 0.0 and 1.0 indicating 0% or 100% respectively.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_difference_probability()
0.25
maximal_difference_probability_absolute()#

Return the difference probability of the difference with the highest probability in absolute terms, i.e. how often it occurs in total.

Equivalently, this is equal to the differential uniformity of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_difference_probability_absolute()
2

Note

This code is mainly called internally.

maximal_linear_bias_absolute()#

Return maximal linear bias, i.e. how often the linear approximation with the highest bias is true or false minus \(2^{n-1}\).

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_linear_bias_absolute()
2
maximal_linear_bias_relative()#

Return maximal bias of all linear approximations of this S-box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.maximal_linear_bias_relative()
0.25
min_degree()#

Return the minimal algebraic degree of all its component functions.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2])
sage: S.min_degree()                                                        # needs sage.rings.polynomial.pbori
2
nonlinearity()#

Return the nonlinearity of this S-Box.

The nonlinearity of an S-Box is defined as the minimum nonlinearity of all its component functions.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = mq.SR(1,4,4,8).sbox()
sage: S.nonlinearity()
112
output_size()#

Return the output size of this S-Box.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([0, 3, 2, 1, 1, 3, 2, 0])
sage: S.output_size()
2
polynomials(X=None, Y=None, degree=2, groebner=False)#

Return a list of polynomials satisfying this S-box.

First, a simple linear fitting is performed for the given degree (cf. for example [BC2003]). If groebner=True a Groebner basis is also computed for the result of that process.

INPUT:

  • X – (optional) input variables

  • Y – (optional) output variables

  • degree – (default: 2) integer > 0

  • groebner – (default: False) calculate a reduced Groebner basis of the spanning polynomials to obtain more polynomials

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: P = S.ring()

By default, this method returns an indirect representation:

sage: S.polynomials()                                                       # needs sage.libs.singular
[x0*x2 + x1 + y1 + 1,
 x0*x1 + x1 + x2 + y0 + y1 + y2 + 1,
 x0*y1 + x0 + x2 + y0 + y2,
 x0*y0 + x0*y2 + x1 + x2 + y0 + y1 + y2 + 1,
 x1*x2 + x0 + x1 + x2 + y2 + 1,
 x0*y0 + x1*y0 + x0 + x2 + y1 + y2,
 x0*y0 + x1*y1 + x1 + y1 + 1,
 x1*y2 + x1 + x2 + y0 + y1 + y2 + 1,
 x0*y0 + x2*y0 + x1 + x2 + y1 + 1,
 x2*y1 + x0 + y1 + y2,
 x2*y2 + x1 + y1 + 1,
 y0*y1 + x0 + x2 + y0 + y1 + y2,
 y0*y2 + x1 + x2 + y0 + y1 + 1,
 y1*y2 + x2 + y0]

We can get a direct representation by computing a lexicographical Groebner basis with respect to the right variable ordering, i.e. a variable ordering where the output bits are greater than the input bits:

sage: P.<y0,y1,y2,x0,x1,x2> = PolynomialRing(GF(2),6,order='lex')
sage: S.polynomials([x0,x1,x2],[y0,y1,y2], groebner=True)                   # needs sage.libs.singular
[y0 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + 1,
 y1 + x0*x2 + x1 + 1,
 y2 + x0 + x1*x2 + x1 + x2 + 1]
ring()#

Create, return, and cache a polynomial ring for S-box polynomials.

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.ring()
Multivariate Polynomial Ring in x0, x1, x2, y0, y1, y2 over
 Finite Field of size 2
solutions(X=None, Y=None)#

Return a dictionary of solutions to this S-box.

INPUT:

  • X – (optional) input variables

  • Y – (optional) output variables

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox([7,6,0,4,2,5,1,3])
sage: F = S.polynomials()                                                   # needs sage.libs.singular
sage: s = S.solutions()
sage: any(f.subs(_s) for f in F for _s in s)                                # needs sage.libs.singular
False
to_bits(x, n=None)#

Return bitstring of length n for integer x. The returned bitstring is guaranteed to have length n.

INPUT:

  • x – an integer

  • n – bit length (optional)

EXAMPLES:

sage: from sage.crypto.sbox import SBox
sage: S = SBox(7,6,0,4,2,5,1,3)
sage: S.to_bits(6)
[1, 1, 0]

sage: S.to_bits( S(6) )
[0, 0, 1]

sage: S( S.to_bits( 6 ) )
[0, 0, 1]
sage.crypto.sbox.feistel_construction(*args)#

Return an S-Box constructed by Feistel structure using smaller S-Boxes in args. The number of round in the construction is equal to the number of S-Boxes provided as input. For more results concerning the differential uniformity and the nonlinearity of S-Boxes constructed by Feistel structures see [CDL2015].

INPUT:

  • args – a finite iterable SBox objects

EXAMPLES:

Suppose we construct an \(8 \times 8\) S-Box with 3-round Feistel construction from the S-Box of PRESENT:

sage: from sage.crypto.sbox import SBox
sage: s = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2)
sage: from sage.crypto.sbox import feistel_construction
sage: S = feistel_construction(s, s, s)

The properties of the constructed S-Box can be easily examined:

sage: S.nonlinearity()
96
sage: S.differential_branch_number()
2
sage: S.linear_branch_number()
2
sage.crypto.sbox.misty_construction(*args)#

Return an S-Box constructed by MISTY structure using smaller S-Boxes in args.

The number of round in the construction is equal to the number of S-Boxes provided as input. For further result related to the nonlinearity and differential uniformity of the constructed S-Box one may consult [CDL2015].

INPUT:

  • args – a finite iterable SBox objects

EXAMPLES:

We construct an \(8 \times 8\) S-Box using 3-round MISTY structure with the following \(4 \times 4\) S-Boxes \(S1, S2, S3\) (see Example 2 in [CDL2015]):

sage: from sage.crypto.sbox import SBox
sage: S1 = SBox([0x4,0x0,0x1,0xF,0x2,0xB,0x6,0x7,0x3,0x9,0xA,0x5,0xC,0xD,0xE,0x8])
sage: S2 = SBox([0x0,0x0,0x0,0x1,0x0,0xA,0x8,0x3,0x0,0x8,0x2,0xB,0x4,0x6,0xE,0xD])
sage: S3 = SBox([0x0,0x7,0xB,0xD,0x4,0x1,0xB,0xF,0x1,0x2,0xC,0xE,0xD,0xC,0x5,0x5])
sage: from sage.crypto.sbox import misty_construction
sage: S = misty_construction(S1, S2, S3)

The properties of the constructed S-Box can be easily examined:

sage: S.differential_uniformity()
8
sage: S.linearity()
64