Class SBox

Construct a substitution box (S-box) for a given lookup table
$S$.

INPUT:
    S -- a finite iterable defining the S-box with integer
          elements
    big_endian -- controls whether bits shall be ordered in
                  big endian order (default: True)

EXAMPLE:
    We construct a 3-bit S-box where e.g. the bits (0,0,1) are
    mapped to (1,1,1).

    sage: S = mq.SBox(7,6,0,4,2,5,1,3); S
    (7, 6, 0, 4, 2, 5, 1, 3)

    sage: S(0)
    7

Overrides: object.__init__

EXAMPLE:
    sage: mq.SBox(7,6,0,4,2,5,1,3) #indirect doctest
    (7, 6, 0, 4, 2, 5, 1, 3)

Return the lenght of input bit strings.

EXAMPLE:
    sage: len(mq.SBox(7,6,0,4,2,5,1,3))
    3

S-boxes are considered to be equal if all construction
parameters match.

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: loads(dumps(S)) == S
    True

Return bitstring of length $n$ for integer $x$. The returned
bitstring is guaranteed to have length \code{n}.

INPUT:
    x -- an integer
    n -- bit length (optional)

EXAMPLE:
    sage: S = mq.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]

Return integer for bitstring $x$ of length $n$.

INPUT:
    x -- a bitstring
    n -- bit length (optional)

EXAMPLE:
    sage: S = mq.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

Apply subsitution to X.

If X is a list it is interpreted as sequence of bits depending
on the bit order of this S-box.

INPUT:
    X -- either an integer or a tuple of GF(2) elements of
         length \code{len(self)}

EXAMPLE:
    sage: S = mq.SBox([7,6,0,4,2,5,1,3])
    sage: S(7)
    3

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

    sage: S[0]
    7

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

See as \code{self.__call__}.

EXAMPLE:
    sage: S = mq.SBox([7,6,0,4,2,5,1,3])
    sage: S[7]
    3

Return \code{True} if this S-Box is a permutation.

EXAMPLE:
     sage: S = mq.SBox(7,6,0,4,2,5,1,3)
     sage: S.is_permutation()
     True

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

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: [e for e in S]
    [7, 6, 0, 4, 2, 5, 1, 3]

Return difference distribition matrix $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]$ encoded how
often $\Delta O$ is the actual output difference given $\Delta
I$ as input difference.

EXAMPLE:
   sage: S = mq.SBox(7,6,0,4,2,5,1,3)
   sage: S.difference_distribution_matrix()
   [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]

REFERENCES: Howard M. Heys, A Tutorial on Linear and
Differential Cryptanalysis, Cryptologia, v.XXVI n.3,
p.189-221, July 2002

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

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: S.maximal_difference_probability_absolute()
    2

NOTE: This code is called internally.

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

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: S.maximal_difference_probability()
    0.25

Return linear approximation matrix $A$ for this S-box.

Let $i_b$ be the $b$-th bit of $i$ and $o_b$ the $b$-th bit of
$o$. Then $v = A[i,o]$ encodes the bias of the equation
#\Sigma i_b * x_i == \Sigma o_b * y_i$ if $x_i$ and $y_i$
represent the input and output variables of the S-box.

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: S.linear_approximation_matrix()
    [ 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]

    According to this matrix 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

REFERENCES: Howard M. Heys, A Tutorial on Linear and
Differential Cryptanalysis, Cryptologia, v.XXVI n.3,
p.189-221, July 2002

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

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: S.maximal_linear_bias_absolute()
    2

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

EXAMPLE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: S.maximal_linear_bias_relative()
    0.25

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

EXAMPLE:
    sage: S = mq.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

Return a dictionary of solutions to this S-box.

INPUT:
    X -- input variables (default: None)
    Y -- output variables (default: None)

EXAMPLE:
    sage: S = mq.SBox([7,6,0,4,2,5,1,3])
    sage: F = S.polynomials()
    sage: s = S.solutions()
    sage: any(f.subs(_s) for f in F for _s in s)
    False

Return a list of polynomials satisfying this S-box.

If \code{groebner=False} these polynomials are at most of
degree \code{degree}. Otherwise the highest degree equals the
highest degree of the reduced Groebner basis.

INPUT:
    X -- input variables
    Y -- output variables
    degree -- integer > 0 (default: 2)
    groebner -- calucalate a reduced Groebner basis of the
                spanning polynomials to obtain more
                polynomials (default: False)

EXAMPLES:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: P = S.ring()

By default, this method returns an indirect representation.

    sage: S.polynomials()
    [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 orderings 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)
    [y2 + x0 + x1*x2 + x1 + x2 + 1,
     y1 + x0*x2 + x1 + 1,
     y0 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + 1]

REFERENCES: A. Biryukov and C. D. Canniere, Block Ciphers and
Systems of Quadratic Equations, Fast Software Encryption 2003, LNCS
2887, pp. 274-289, Springer-Verlag, 2003.

Return an 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
\code{TypeError} is raised.

INPUT:
    k -- an instance of GF($2^m$) (default: None)

EXAMPE:
    sage: S = mq.SBox(7,6,0,4,2,5,1,3)
    sage: f = S.interpolation_polynomial()
    sage: f
    x^6 + a*x^5 + (a + 1)*x^4 + (a^2 + a + 1)*x^3
      + (a^2 + 1)*x^2 + (a + 1)*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)