S-Boxes and Their Algebraic Representations

class sage.crypto.sbox.SBox[source]

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

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

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

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]

>>> from sage.all import *
>>> S([Integer(0),Integer(0),Integer(0),Integer(1)])
[0, 1, 0, 1]

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

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

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)

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

sr = mq.SR(1,1,1,4, allow_zero_inversions=True)
S = SBox([sr.sub_byte(e) for e in list(sr.k)])
S

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()[source]

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]

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> 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]

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

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]

>>> from sage.all import *
>>> from sage.crypto.sboxes import PRESENT
>>> 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]

from sage.crypto.sboxes import PRESENT
PRESENT.boomerang_connectivity_table()
boomerang_uniformity()[source]

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

>>> from sage.all import *
>>> from sage.crypto.sboxes import AES
>>> AES.boomerang_uniformity()
6

from sage.crypto.sboxes import AES
AES.boomerang_uniformity()
cnf(xi=None, yi=None, format=None)[source]

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 – string that can be parsed by the SymbolicLogic package

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

  • dimacs_headless – 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)]

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(1),Integer(2),Integer(0),Integer(3)); S
(1, 2, 0, 3)
>>> 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)]

from sage.crypto.sbox import SBox
S = SBox(1,2,0,3); S
cnf = S.cnf(); cnf

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

>>> from sage.all import *
>>> 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

print(S.cnf(format='dimacs'))

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

>>> from sage.all import *
>>> 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

print(S.cnf(format='dimacs_headless'))

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

>>> from sage.all import *
>>> print(S.cnf(xi=[Integer(10),Integer(20)],yi=[Integer(30),Integer(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

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

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']]

>>> from sage.all import *
>>> log = SymbolicLogic()
>>> s = log.statement(S.cnf(format='symbolic'))
>>> log.truthtable(s)[Integer(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']]

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

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)]

>>> from sage.all import *
>>> S = SBox(Integer(1),Integer(2),Integer(0),Integer(3), big_endian=False); S
(1, 2, 0, 3)
>>> 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 = SBox(1,2,0,3, big_endian=False); S
cnf = S.cnf(); cnf

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)[source]

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

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

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

from sage.crypto.sbox import SBox
S = SBox([7,6,0,4,2,5,1,3])
f3 = S.component_function(3)
f3.algebraic_normal_form()                                            # needs sage.rings.polynomial.pbori
f5 = S.component_function([1, 0, 1])
f5.algebraic_normal_form()                                            # needs sage.rings.polynomial.pbori
derivative(u)[source]

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

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

from sage.crypto.sbox import SBox
s = SBox(0,1,2,3)
s.derivative(1)
u = [1,0]
s.derivative(u)
v = vector(GF(2), [1,0])
s.derivative(v)
s.derivative(4)
from sage.crypto.sboxes import PRESENT
PRESENT.derivative(1).max_degree() < PRESENT.max_degree()             # needs sage.rings.polynomial.pbori
difference_distribution_table()[source]

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]

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> 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]
>>> S = SBox(Integer(7),Integer(4),Integer(8),Integer(6))
>>> 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]

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

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

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

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

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

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

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

Note

This code is mainly called internally.

fixed_points()[source]

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 sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0),Integer(1),Integer(3),Integer(6),Integer(7),Integer(4),Integer(5),Integer(2)])
>>> S.fixed_points()
[0, 1]

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

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

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

>>> S( S.from_bits( [Integer(1),Integer(1),Integer(0)] ) )
1
>>> S.from_bits( S( [Integer(1),Integer(1),Integer(0)] ) )
1

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

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

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

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0), Integer(3), Integer(2), Integer(1), Integer(1), Integer(3), Integer(2), Integer(0)])
>>> S.input_size()
3

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

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)

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> f = S.interpolation_polynomial()
>>> 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

>>> a = f.base_ring().gen()

>>> f(Integer(0)), S(Integer(0))
(a^2 + a + 1, 7)

>>> f(a**Integer(2) + Integer(1)), S(Integer(5))
(a^2 + 1, 5)

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

Note

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

inverse()[source]

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]

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

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0),Integer(1),Integer(3),Integer(6),Integer(7),Integer(4),Integer(5),Integer(2)])
>>> S.is_almost_bent()
True

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0),Integer(1),Integer(3),Integer(6),Integer(7),Integer(4),Integer(5),Integer(2)])
>>> S.is_apn()
True
>>> S.differential_uniformity()
2

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

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

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

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

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]

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> R = GF(Integer(2)**Integer(2), 'a')['x']; (x,) = R._first_ngens(1)
>>> base = R.base_ring()
>>> a = base.gen()
>>> G = a * x**Integer(2) + Integer(1)
>>> S = SBox([G(x * y**(Integer(14))) for x in sorted(base) for y in sorted(base)])
>>> S.is_bent()
True
>>> S.nonlinearity()
6
>>> 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]

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([x**Integer(254) for x in sorted(GF(Integer(2)**Integer(8)))])
>>> S.is_involution()
True

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

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

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

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0),Integer(1),Integer(3),Integer(6),Integer(7),Integer(4),Integer(5),Integer(2)])
>>> S.is_monomial_function()
False
>>> 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

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

>>> S = SBox(Integer(0),Integer(3),Integer(2),Integer(1))
>>> S.interpolation_polynomial()
x^2
>>> S.is_monomial_function()
True

from sage.crypto.sbox import SBox
S = SBox([0,1,3,6,7,4,5,2])
S.is_monomial_function()
S_poly = S.interpolation_polynomial(); S_poly
all([S(x) == S_poly(x) for x in S_poly.base_ring()])
S = SBox(0,3,2,1)
S.interpolation_polynomial()
S.is_monomial_function()
is_permutation()[source]

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

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

>>> S = SBox(Integer(3),Integer(2),Integer(0),Integer(0),Integer(2),Integer(1),Integer(1),Integer(3))
>>> S.is_permutation()
False

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(0), Integer(3), Integer(1), Integer(2), Integer(4), Integer(6), Integer(7), Integer(5))
>>> S.is_plateaued()
True

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> lat_abs_bias = S.linear_approximation_table()
>>> 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]

>>> lat_abs_bias/(Integer(1) << S.input_size()) == S.linear_approximation_table(scale='bias')
True

>>> lat_abs_bias/(Integer(1) << (S.input_size()-Integer(1))) == S.linear_approximation_table(scale='correlation')
True

>>> lat_abs_bias*Integer(2) == S.linear_approximation_table(scale='fourier_coefficient')
True

from sage.crypto.sbox import SBox
S = SBox(7,6,0,4,2,5,1,3)
lat_abs_bias = S.linear_approximation_table()
lat_abs_bias
lat_abs_bias/(1 << S.input_size()) == S.linear_approximation_table(scale='bias')
lat_abs_bias/(1 << (S.input_size()-1)) == S.linear_approximation_table(scale='correlation')
lat_abs_bias*2 == S.linear_approximation_table(scale='fourier_coefficient')

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

>>> from sage.all import *
>>> for i in srange(Integer(8)): print(S.to_bits(i)[Integer(0)] == S.to_bits(S(i))[Integer(2)])
False
True
True
True
False
True
True
True

for i in srange(8): print(S.to_bits(i)[0] == S.to_bits(S(i))[2])
linear_branch_number()[source]

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

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

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

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)]

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0),Integer(1),Integer(3),Integer(6),Integer(7),Integer(4),Integer(5),Integer(2)])
>>> 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)]

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = mq.SR(Integer(1), Integer(4), Integer(4), Integer(8)).sbox()
>>> S.linearity()
32

from sage.crypto.sbox import SBox
S = mq.SR(1, 4, 4, 8).sbox()
S.linearity()
max_degree()[source]

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

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

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> S.maximal_difference_probability()
0.25

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

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

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

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

Note

This code is mainly called internally.

maximal_linear_bias_absolute()[source]

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> S.maximal_linear_bias_absolute()
2

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> S.maximal_linear_bias_relative()
0.25

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

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

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

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = mq.SR(Integer(1),Integer(4),Integer(4),Integer(8)).sbox()
>>> S.nonlinearity()
112

from sage.crypto.sbox import SBox
S = mq.SR(1,4,4,8).sbox()
S.nonlinearity()
output_size()[source]

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox([Integer(0), Integer(3), Integer(2), Integer(1), Integer(1), Integer(3), Integer(2), Integer(0)])
>>> S.output_size()
2

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

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 – boolean (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()

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

from sage.crypto.sbox import SBox
S = SBox(7,6,0,4,2,5,1,3)
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]

>>> from sage.all import *
>>> 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]

S.polynomials()                                                       # needs sage.libs.singular

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]

>>> from sage.all import *
>>> P = PolynomialRing(GF(Integer(2)),Integer(6),order='lex', names=('y0', 'y1', 'y2', 'x0', 'x1', 'x2',)); (y0, y1, y2, x0, x1, x2,) = P._first_ngens(6)
>>> 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]

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

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

>>> from sage.all import *
>>> from sage.crypto.sbox import SBox
>>> S = SBox(Integer(7),Integer(6),Integer(0),Integer(4),Integer(2),Integer(5),Integer(1),Integer(3))
>>> S.ring()
Multivariate Polynomial Ring in x0, x1, x2, y0, y1, y2 over
 Finite Field of size 2

from sage.crypto.sbox import SBox
S = SBox(7,6,0,4,2,5,1,3)
S.ring()
solutions(X=None, Y=None)[source]

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

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

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

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

INPUT:

  • x – 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]

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

>>> S.to_bits( S(Integer(6)) )
[0, 0, 1]

>>> S( S.to_bits( Integer(6) ) )
[0, 0, 1]

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

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)

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

from sage.crypto.sbox import SBox
s = SBox(12,5,6,11,9,0,10,13,3,14,15,8,4,7,1,2)
from sage.crypto.sbox import feistel_construction
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

>>> from sage.all import *
>>> S.nonlinearity()
96
>>> S.differential_branch_number()
2
>>> S.linear_branch_number()
2

S.nonlinearity()
S.differential_branch_number()
S.linear_branch_number()
sage.crypto.sbox.misty_construction(*args)[source]

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)

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

from sage.crypto.sbox import SBox
S1 = SBox([0x4,0x0,0x1,0xF,0x2,0xB,0x6,0x7,0x3,0x9,0xA,0x5,0xC,0xD,0xE,0x8])
S2 = SBox([0x0,0x0,0x0,0x1,0x0,0xA,0x8,0x3,0x0,0x8,0x2,0xB,0x4,0x6,0xE,0xD])
S3 = SBox([0x0,0x7,0xB,0xD,0x4,0x1,0xB,0xF,0x1,0x2,0xC,0xE,0xD,0xC,0x5,0x5])
from sage.crypto.sbox import misty_construction
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

>>> from sage.all import *
>>> S.differential_uniformity()
8
>>> S.linearity()
64

S.differential_uniformity()
S.linearity()