Small Scale Variants of the AES (SR) Polynomial System Generator#

Sage supports polynomial system generation for small scale (and full scale) AES variants over \(\GF{2}\) and \(\GF{2^e}\). Also, Sage supports both the specification of SR as given in the papers [CMR2005] and [CMR2006] and a variant of SR* which is equivalent to AES.

SR is a family of parameterizable variants of the AES suitable as a framework for comparing different cryptanalytic techniques that can be brought to bear on the AES. It is different from Mini-AES, whose purpose is as a teaching tool to help beginners understand the basic structure and working of the full AES.

AUTHORS:

  • Martin Albrecht (2008,2009-01): usability improvements

  • Martin Albrecht (2007-09): initial version

  • Niles Johnson (2010-08): (Issue #3893) random_element() should pass on *args and **kwds.

EXAMPLES:

We construct SR(1,1,1,4) and study its properties.

sage: sr = mq.SR(1, 1, 1, 4)

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4))

n is the number of rounds, r the number of rows in the state array, c the number of columns in the state array, and e the degree of the underlying field.

sage: sr.n, sr.r, sr.c, sr.e
(1, 1, 1, 4)

>>> from sage.all import *
>>> sr.n, sr.r, sr.c, sr.e
(1, 1, 1, 4)

By default variables are ordered reverse to as they appear, e.g.:

sage: print(sr.R.repr_long())
Polynomial Ring
  Base Ring : Finite Field in a of size 2^4
       Size : 20 Variables
   Block  0 : Ordering : deglex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002, k003

>>> from sage.all import *
>>> print(sr.R.repr_long())
Polynomial Ring
  Base Ring : Finite Field in a of size 2^4
       Size : 20 Variables
   Block  0 : Ordering : deglex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002, k003

However, this can be prevented by passing in reverse_variables=False to the constructor.

For SR(1, 1, 1, 4) the ShiftRows matrix isn’t that interesting.:

sage: sr.ShiftRows
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

>>> from sage.all import *
>>> sr.ShiftRows
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

Also, the MixColumns matrix is the identity matrix.:

sage: sr.MixColumns
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

>>> from sage.all import *
>>> sr.MixColumns
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

Lin, however, is not the identity matrix.:

sage: sr.Lin
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

>>> from sage.all import *
>>> sr.Lin
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

M and Mstar are identical for SR(1, 1, 1, 4):

sage: sr.M
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

>>> from sage.all import *
>>> sr.M
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

sage: sr.Mstar
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

>>> from sage.all import *
>>> sr.Mstar
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

However, for larger instances of SR Mstar is not equal to M:

sage: sr = mq.SR(10,4,4,8)
sage: sr.Mstar == ~sr.MixColumns * sr.M
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(10),Integer(4),Integer(4),Integer(8))
>>> sr.Mstar == ~sr.MixColumns * sr.M
True

We can compute a Groebner basis for the ideals spanned by SR instances to recover all solutions to the system.:

sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True)
sage: K = sr.base_ring()
sage: a = K.gen()
sage: K = [a]
sage: P = [1]
sage: F,s = sr.polynomial_system(P=P, K=K)                                          # needs sage.rings.polynomial.pbori
sage: F.groebner_basis()                                                            # needs sage.rings.polynomial.pbori
[k100, k101 + 1, k102, k103 + k003,
 x100 + 1, x101 + k003 + 1, x102 + k003 + 1,
 x103 + k003, w100, w101, w102 + 1, w103 + k003 + 1,
 s000 + 1, s001 + k003, s002 + k003, s003 + k003 + 1,
 k000, k001, k002 + 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(1),Integer(1),Integer(1),Integer(4), gf2=True, polybori=True)
>>> K = sr.base_ring()
>>> a = K.gen()
>>> K = [a]
>>> P = [Integer(1)]
>>> F,s = sr.polynomial_system(P=P, K=K)                                          # needs sage.rings.polynomial.pbori
>>> F.groebner_basis()                                                            # needs sage.rings.polynomial.pbori
[k100, k101 + 1, k102, k103 + k003,
 x100 + 1, x101 + k003 + 1, x102 + k003 + 1,
 x103 + k003, w100, w101, w102 + 1, w103 + k003 + 1,
 s000 + 1, s001 + k003, s002 + k003, s003 + k003 + 1,
 k000, k001, k002 + 1]

Note that the order of k000, k001, k002 and k003 is little endian. Thus the result k002 + 1, k001, k000 indicates that the key is either \(a\) or \(a+1\). We can verify that both keys encrypt P to the same ciphertext:

sage: sr(P,[a])
[0]
sage: sr(P,[a+1])
[0]

>>> from sage.all import *
>>> sr(P,[a])
[0]
>>> sr(P,[a+Integer(1)])
[0]

All solutions can easily be recovered using the variety function for ideals.:

sage: I = F.ideal()                                                                  # needs sage.rings.polynomial.pbori
sage: for V in I.variety():                                                          # needs sage.rings.polynomial.pbori sage.symbolic
....:    for k,v in sorted(V.items()):
....:       print("{} {}".format(k, v))
....:    print("\n")
k003 0
k002 1
k001 0
k000 0
s003 1
s002 0
s001 0
s000 1
w103 1
w102 1
w101 0
w100 0
x103 0
x102 1
x101 1
x100 1
k103 0
k102 0
k101 1
k100 0

k003 1
k002 1
k001 0
k000 0
s003 0
s002 1
s001 1
s000 1
w103 0
w102 1
w101 0
w100 0
x103 1
x102 0
x101 0
x100 1
k103 1
k102 0
k101 1
k100 0

>>> from sage.all import *
>>> I = F.ideal()                                                                  # needs sage.rings.polynomial.pbori
>>> for V in I.variety():                                                          # needs sage.rings.polynomial.pbori sage.symbolic
...    for k,v in sorted(V.items()):
...       print("{} {}".format(k, v))
...    print("\n")
k003 0
k002 1
k001 0
k000 0
s003 1
s002 0
s001 0
s000 1
w103 1
w102 1
w101 0
w100 0
x103 0
x102 1
x101 1
x100 1
k103 0
k102 0
k101 1
k100 0
<BLANKLINE>
k003 1
k002 1
k001 0
k000 0
s003 0
s002 1
s001 1
s000 1
w103 0
w102 1
w101 0
w100 0
x103 1
x102 0
x101 0
x100 1
k103 1
k102 0
k101 1
k100 0

We can also verify the correctness of the variety by evaluating all ideal generators on all points.:

sage: for V in I.variety():                                                          # needs sage.rings.polynomial.pbori sage.symbolic
....:     for f in I.gens():
....:         if f.subs(V) != 0:
....:            print("epic fail")

>>> from sage.all import *
>>> for V in I.variety():                                                          # needs sage.rings.polynomial.pbori sage.symbolic
...     for f in I.gens():
...         if f.subs(V) != Integer(0):
...            print("epic fail")

Note that the S-Box object for SR can be constructed with a call to sr.sbox():

sage: sr = mq.SR(1,1,1,4, gf2=True, polybori=True)
sage: S = sr.sbox()

>>> from sage.all import *
>>> sr = mq.SR(Integer(1),Integer(1),Integer(1),Integer(4), gf2=True, polybori=True)
>>> S = sr.sbox()

For example, we can now study the difference distribution table of S:

sage: S.difference_distribution_table()
[16  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  2  2  2  2  0  0  0  2  0  0  0  2  4  0  0]
[ 0  2  0  4  2  2  2  0  0  2  0  0  0  0  0  2]
[ 0  2  4  0  0  2  0  0  2  2  0  2  0  0  2  0]
[ 0  0  2  0  4  2  0  0  0  0  2  0  2  0  2  2]
[ 0  0  0  2  0  0  0  2  4  2  0  0  2  0  2  2]
[ 0  4  0  0  0  2  0  2  0  2  2  0  2  2  0  0]
[ 0  2  0  0  0  0  2  0  0  0  0  2  4  2  2  2]
[ 0  2  2  0  0  0  2  2  2  0  2  0  0  0  0  4]
[ 0  0  2  2  0  0  0  0  0  2  2  4  0  2  0  2]
[ 0  0  2  0  2  0  2  2  0  4  0  2  2  0  0  0]
[ 0  0  0  0  2  0  2  0  2  2  4  0  0  2  2  0]
[ 0  0  0  2  0  4  2  0  2  0  2  2  2  0  0  0]
[ 0  0  0  0  2  2  0  4  2  0  0  2  0  2  0  2]
[ 0  0  2  2  0  2  4  2  0  0  0  0  0  2  2  0]
[ 0  2  0  2  2  0  0  2  0  0  2  2  0  0  4  0]

>>> from sage.all import *
>>> S.difference_distribution_table()
[16  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[ 0  2  2  2  2  0  0  0  2  0  0  0  2  4  0  0]
[ 0  2  0  4  2  2  2  0  0  2  0  0  0  0  0  2]
[ 0  2  4  0  0  2  0  0  2  2  0  2  0  0  2  0]
[ 0  0  2  0  4  2  0  0  0  0  2  0  2  0  2  2]
[ 0  0  0  2  0  0  0  2  4  2  0  0  2  0  2  2]
[ 0  4  0  0  0  2  0  2  0  2  2  0  2  2  0  0]
[ 0  2  0  0  0  0  2  0  0  0  0  2  4  2  2  2]
[ 0  2  2  0  0  0  2  2  2  0  2  0  0  0  0  4]
[ 0  0  2  2  0  0  0  0  0  2  2  4  0  2  0  2]
[ 0  0  2  0  2  0  2  2  0  4  0  2  2  0  0  0]
[ 0  0  0  0  2  0  2  0  2  2  4  0  0  2  2  0]
[ 0  0  0  2  0  4  2  0  2  0  2  2  2  0  0  0]
[ 0  0  0  0  2  2  0  4  2  0  0  2  0  2  0  2]
[ 0  0  2  2  0  2  4  2  0  0  0  0  0  2  2  0]
[ 0  2  0  2  2  0  0  2  0  0  2  2  0  0  4  0]

or use S to find alternative polynomial representations for the S-Box.:

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

sage: S.interpolation_polynomial()
(a^2 + 1)*x^14 + a^2*x^13 + x^12 + a^2*x^11 + a*x^10 + (a^3 + a)*x^9 +
(a^3 + 1)*x^7 + (a^3 + a^2 + a)*x^6 + a^2*x^5 + (a + 1)*x^4 + a^2*x^3 +
(a^3 + a^2 + a)*x^2 + (a^3 + 1)*x + a^2 + a

>>> from sage.all import *
>>> S.polynomials(degree=Integer(3))                                                        # needs sage.libs.singular
[x0*x1 + x1*x2 + x0*x3 + x0*y2 + x1 + y0 + y1 + 1,
 x0*x1 + x0*x2 + x0*y0 + x0*y1 + x0*y2 + x1 + x2 + y0 + y1 + y2,
 x0*x1 + x0*x2 + x0*x3 + x1*x3 + x0*y0 + x1*y0 + x0*y1 + x0*y3,
 x0*x1 + x0*x2 + x0*x3 + x1*x3 + x0*y0 + x1*y1 + x0*y3 + x1 + y0 + y1 + 1,
 x0*x1 + x0*x2 + x0*y2 + x1*y2 + x0*y3 + x0 + x1,
 x0*x3 + x1*x3 + x0*y1 + x0*y2 + x1*y3 + x0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x0*x1 + x1*x3 + x2*x3 + x0*y0 + x0*y2 + x0*y3 + x2 + y0 + y3,
 x0*x1 + x0*x2 + x0*x3 + x1*x3 + x2*y0 + x0*y2 + x0 + x2 + x3 + y3,
 x0*x3 + x1*x3 + x0*y0 + x2*y1 + x0*y2 + x3 + y3,
 x0*x1 + x0*x2 + x0*y0 + x0*y1 + x2*y2 + x0*y3 + x1 + y0 + y1 + 1,
 x0*x3 + x1*x3 + x0*y0 + x0*y1 + x0*y3 + x2*y3 + y0 + y3,
 x0*x1 + x0*x2 + x3*y0 + x0*y1 + x0*y3 + y0,
 x0*y0 + x0*y1 + x3*y1 + x0 + x2 + y0 + y3,
 x0*y0 + x3*y2 + y0,
 x0*x1 + x0*x2 + x0*x3 + x1*x3 + x0*y0 + x0*y2 + x3*y3 + y0,
 x0*x2 + x0*x3 + x0*y1 + y0*y1 + x0*y3 + x2 + x3 + y3,
 x0*x2 + x0*y0 + y0*y2 + x0*y3 + x0 + y0,
 x0*x1 + x0*x2 + x1*x3 + x0*y2 + y0*y3 + y0,
 x0*x1 + x0*y0 + y1*y2 + x0*y3 + x1 + x2 + y0 + 1,
 x0*x2 + x1*x3 + x0*y1 + x0*y2 + x0*y3 + y1*y3 + x0 + y0 + y3,
 x0*x1 + x0*x2 + x0*x3 + x0*y1 + x0*y2 + x0*y3 + y2*y3 + x0 + x1 + x2 + x3 + y1 + y3 + 1,
 x0*x1*x2 + x0*x3 + x0*y0 + x0*y1 + x0*y2 + x0,
 x0*x1*x3 + x0*x2 + x0*x3 + x0*y1 + x0*y3 + x0,
 x0*x1*y0 + x0*x1 + x0*y0 + x0,
 x0*x1*y1,
 x0*x1*y2 + x0*x2 + x0*y2 + x0*y3 + x0,
 x0*x1*y3 + x0*x1 + x0*x3 + x0*y0 + x0*y1 + x0*y2 + x0,
 x0*x2*x3 + x0*x1 + x0*x3 + x0*y1 + x0*y2 + x0*y3 + x0,
 x0*x2*y0 + x0*x1 + x0*x2 + x0*x3 + x0*y1 + x0*y2,
 x0*x2*y1 + x0*x2 + x0*x3 + x0*y0 + x0*y1 + x0*y2 + x0,
 x0*x2*y2 + x0*x2 + x0*y3 + x0,
 x0*x2*y3 + x0*x2 + x0*y3 + x0,
 x0*x3*y0 + x0*x1 + x0*x2 + x0*y0 + x0*y1 + x0*y3,
 x0*x3*y1 + x0*x2 + x0*y1 + x0*y3 + x0,
 x0*x3*y2,
 x0*x3*y3 + x0*x1 + x0*y1 + x0*y2 + x0*y3 + x0,
 x0*y0*y1 + x0*y1,
 x0*y0*y2 + x0*x2 + x0*y3 + x0,
 x0*y0*y3 + x0*x1 + x0*x3 + x0*y0 + x0*y1 + x0*y2 + x0*y3 + x0,
 x0*y1*y2 + x0*x2 + x0*y3 + x0,
 x0*y1*y3 + x0*x3 + x0*y0 + x0*y2 + x0*y3,
 x0*y2*y3 + x0*y2,
 x1*x2*x3 + x0*x1 + x1*x3 + x0*y0 + x0*y1 + x2 + x3 + y3,
 x1*x2*y0 + x0*x1 + x1*x3 + x0*y0 + x0*y1 + x2 + x3 + y3,
 x1*x2*y1 + x0*x1 + x1*x3 + x0*y0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x1*x2*y2 + x0*x1 + x0*y0 + x0*y1 + x0 + x1 + y0 + y1 + 1,
 x1*x2*y3 + x0*x1 + x1*x3 + x0*y0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x1*x3*y0 + x0*x1 + x0*x2 + x0*x3 + x1*x3 + x0*y0 + x0*y1 + x0*y3,
 x1*x3*y1 + x0*x2 + x0*x3 + x0*y3 + x2 + x3 + y3,
 x1*x3*y2 + x0*x2 + x0*x3 + x1*x3 + x0*y1 + x0*y3 + x0,
 x1*x3*y3 + x0*x1 + x0*x2 + x0*x3 + x0*y0 + x0*y1 + x0*y3,
 x1*y0*y1 + x0*x2 + x0*x3 + x0*y3 + x2 + x3 + y3,
 x1*y0*y2 + x0*x2 + x0*x3 + x1*x3 + x0*y1 + x0*y3 + x0,
 x1*y0*y3,
 x1*y1*y2 + x0*x1 + x0*x2 + x0*x3 + x1*x3 + x0*y0 + x0*y3 + x1 + y0 + y1 + 1,
 x1*y1*y3 + x0*x1 + x1*x3 + x0*y0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x1*y2*y3 + x0*x1 + x0*x2 + x1*x3 + x0*y0 + x0*y2 + x0*y3 + x0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x2*x3*y0 + x0*x1 + x0*x3 + x1*x3 + x0*y2 + x0*y3 + x2 + x3 + y3,
 x2*x3*y1 + x0*y1 + x0*y2 + x0*y3 + x3 + y0,
 x2*x3*y2 + x1*x3 + x0*y1 + x0 + x2 + x3 + y3,
 x2*x3*y3,
 x2*y0*y1 + x0*x2 + x0*x3 + x0*y0 + x0*y1 + x0*y2 + x0,
 x2*y0*y2 + x0*x2 + x1*x3 + x0*y1 + x0*y3 + x2 + x3 + y3,
 x2*y0*y3 + x0*x2 + x0*y3 + x0,
 x2*y1*y2 + x0*x1 + x0*x2 + x1*x3 + x0*y0 + x0*y3 + x0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x2*y1*y3 + x0*x3 + x1*x3 + x0*y0 + x0*y1 + x0*y3 + y0 + y3,
 x2*y2*y3 + x0*x1 + x0*x2 + x1*x3 + x0*y0 + x0*y3 + x0 + x1 + x2 + x3 + y0 + y1 + y3 + 1,
 x3*y0*y1 + x0*x3 + x0*y1 + x0 + x2 + x3 + y3,
 x3*y0*y2 + x0*y0 + y0,
 x3*y0*y3 + x1*x3 + x0*y1 + x0*y2 + x0*y3 + y0,
 x3*y1*y2 + x0*x2 + x0*x3 + x0*y3 + x2 + x3 + y3,
 x3*y1*y3 + x0*x2 + x0*x3 + x0*y0 + x0*y2 + x0,
 x3*y2*y3 + x0*x2 + x0*x3 + x1*x3 + x0*y0 + x0*y1 + x0*y3 + x0 + y0,
 y0*y1*y2 + x0*x3 + x0 + x2 + x3 + y3,
 y0*y1*y3 + x0*x3 + x0*y0 + x0*y2 + x0*y3,
 y0*y2*y3 + x0*x3 + x1*x3 + x0*y0 + x0*y1 + y0,
 y1*y2*y3 + x0*x1 + x0*x2 + x1*x3 + x0*y0 + x0*y3 + x0 + x1 + x2 + x3 + y0 + y1 + y3 + 1]

>>> S.interpolation_polynomial()
(a^2 + 1)*x^14 + a^2*x^13 + x^12 + a^2*x^11 + a*x^10 + (a^3 + a)*x^9 +
(a^3 + 1)*x^7 + (a^3 + a^2 + a)*x^6 + a^2*x^5 + (a + 1)*x^4 + a^2*x^3 +
(a^3 + a^2 + a)*x^2 + (a^3 + 1)*x + a^2 + a

The SR_gf2_2 gives an example how use alternative polynomial representations of the S-Box for construction of polynomial systems.

REFERENCES:

class sage.crypto.mq.sr.AllowZeroInversionsContext(sr)[source]#

Bases: object

Temporarily allow zero inversion.

sage.crypto.mq.sr.SR(n=1, r=1, c=1, e=4, star=False, **kwargs)[source]#

Return a small scale variant of the AES polynomial system constructor subject to the following conditions:

INPUT:

  • n – the number of rounds (default: 1)

  • r – the number of rows in the state array (default: 1)

  • c – the number of columns in the state array (default: 1)

  • e – the exponent of the finite extension field (default: 4)

  • star – determines if SR* or SR should be constructed (default: False)

  • aes_mode – as the SR key schedule specification differs slightly from the AES key schedule, this parameter controls which schedule to use (default: True)

  • gf2 – generate polynomial systems over \(\GF{2}\) rather than over \(\GF{2^e}\) (default: False)

  • polybori – use the BooleanPolynomialRing as polynomial representation (default: True, \(\GF{2}\) only)

  • order – a string to specify the term ordering of the variables (default: deglex)

  • postfix – a string which is appended after the variable name (default: ‘’)

  • allow_zero_inversions – a boolean to control whether zero inversions raise an exception (default: False)

  • correct_only – only include correct inversion polynomials (default: False, \(\GF{2}\) only)

  • biaffine_only – only include bilinear and biaffine inversion polynomials (default: True, \(\GF{2}\) only)

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4)
sage: ShiftRows = sr.shift_rows_matrix()
sage: MixColumns = sr.mix_columns_matrix()
sage: Lin = sr.lin_matrix()
sage: M = MixColumns * ShiftRows * Lin
sage: print(sr.hex_str_matrix(M))
 5 1 C 5
 2 2 1 F
 A 4 4 1
 1 8 3 3

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4))
>>> ShiftRows = sr.shift_rows_matrix()
>>> MixColumns = sr.mix_columns_matrix()
>>> Lin = sr.lin_matrix()
>>> M = MixColumns * ShiftRows * Lin
>>> print(sr.hex_str_matrix(M))
 5 1 C 5
 2 2 1 F
 A 4 4 1
 1 8 3 3

sage: sr = mq.SR(1, 2, 1, 4)
sage: ShiftRows = sr.shift_rows_matrix()
sage: MixColumns = sr.mix_columns_matrix()
sage: Lin = sr.lin_matrix()
sage: M = MixColumns * ShiftRows * Lin
sage: print(sr.hex_str_matrix(M))
 F 3 7 F A 2 B A
 A A 5 6 8 8 4 9
 7 8 8 2 D C C 3
 4 6 C C 5 E F F
 A 2 B A F 3 7 F
 8 8 4 9 A A 5 6
 D C C 3 7 8 8 2
 5 E F F 4 6 C C

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(1), Integer(4))
>>> ShiftRows = sr.shift_rows_matrix()
>>> MixColumns = sr.mix_columns_matrix()
>>> Lin = sr.lin_matrix()
>>> M = MixColumns * ShiftRows * Lin
>>> print(sr.hex_str_matrix(M))
 F 3 7 F A 2 B A
 A A 5 6 8 8 4 9
 7 8 8 2 D C C 3
 4 6 C C 5 E F F
 A 2 B A F 3 7 F
 8 8 4 9 A A 5 6
 D C C 3 7 8 8 2
 5 E F F 4 6 C C

sage: sr = mq.SR(1, 2, 2, 4)
sage: ShiftRows = sr.shift_rows_matrix()
sage: MixColumns = sr.mix_columns_matrix()
sage: Lin = sr.lin_matrix()
sage: M = MixColumns * ShiftRows * Lin
sage: print(sr.hex_str_matrix(M))
 F 3 7 F 0 0 0 0 0 0 0 0 A 2 B A
 A A 5 6 0 0 0 0 0 0 0 0 8 8 4 9
 7 8 8 2 0 0 0 0 0 0 0 0 D C C 3
 4 6 C C 0 0 0 0 0 0 0 0 5 E F F
 A 2 B A 0 0 0 0 0 0 0 0 F 3 7 F
 8 8 4 9 0 0 0 0 0 0 0 0 A A 5 6
 D C C 3 0 0 0 0 0 0 0 0 7 8 8 2
 5 E F F 0 0 0 0 0 0 0 0 4 6 C C
 0 0 0 0 A 2 B A F 3 7 F 0 0 0 0
 0 0 0 0 8 8 4 9 A A 5 6 0 0 0 0
 0 0 0 0 D C C 3 7 8 8 2 0 0 0 0
 0 0 0 0 5 E F F 4 6 C C 0 0 0 0
 0 0 0 0 F 3 7 F A 2 B A 0 0 0 0
 0 0 0 0 A A 5 6 8 8 4 9 0 0 0 0
 0 0 0 0 7 8 8 2 D C C 3 0 0 0 0
 0 0 0 0 4 6 C C 5 E F F 0 0 0 0

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(2), Integer(4))
>>> ShiftRows = sr.shift_rows_matrix()
>>> MixColumns = sr.mix_columns_matrix()
>>> Lin = sr.lin_matrix()
>>> M = MixColumns * ShiftRows * Lin
>>> print(sr.hex_str_matrix(M))
 F 3 7 F 0 0 0 0 0 0 0 0 A 2 B A
 A A 5 6 0 0 0 0 0 0 0 0 8 8 4 9
 7 8 8 2 0 0 0 0 0 0 0 0 D C C 3
 4 6 C C 0 0 0 0 0 0 0 0 5 E F F
 A 2 B A 0 0 0 0 0 0 0 0 F 3 7 F
 8 8 4 9 0 0 0 0 0 0 0 0 A A 5 6
 D C C 3 0 0 0 0 0 0 0 0 7 8 8 2
 5 E F F 0 0 0 0 0 0 0 0 4 6 C C
 0 0 0 0 A 2 B A F 3 7 F 0 0 0 0
 0 0 0 0 8 8 4 9 A A 5 6 0 0 0 0
 0 0 0 0 D C C 3 7 8 8 2 0 0 0 0
 0 0 0 0 5 E F F 4 6 C C 0 0 0 0
 0 0 0 0 F 3 7 F A 2 B A 0 0 0 0
 0 0 0 0 A A 5 6 8 8 4 9 0 0 0 0
 0 0 0 0 7 8 8 2 D C C 3 0 0 0 0
 0 0 0 0 4 6 C C 5 E F F 0 0 0 0
class sage.crypto.mq.sr.SR_generic(n=1, r=1, c=1, e=4, star=False, **kwargs)[source]#

Bases: MPolynomialSystemGenerator

Small Scale Variants of the AES.

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4)
sage: ShiftRows = sr.shift_rows_matrix()
sage: MixColumns = sr.mix_columns_matrix()
sage: Lin = sr.lin_matrix()
sage: M = MixColumns * ShiftRows * Lin
sage: print(sr.hex_str_matrix(M))
 5 1 C 5
 2 2 1 F
 A 4 4 1
 1 8 3 3

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4))
>>> ShiftRows = sr.shift_rows_matrix()
>>> MixColumns = sr.mix_columns_matrix()
>>> Lin = sr.lin_matrix()
>>> M = MixColumns * ShiftRows * Lin
>>> print(sr.hex_str_matrix(M))
 5 1 C 5
 2 2 1 F
 A 4 4 1
 1 8 3 3
add_round_key(d, key)[source]#

Perform the AddRoundKey operation on d using key.

INPUT:

  • d – state array or something coercible to a state array

  • key – state array or something coercible to a state array

EXAMPLES:

sage: sr = mq.SR(10, 4, 4, 4)
sage: D = sr.random_state_array()
sage: K = sr.random_state_array()
sage: sr.add_round_key(D, K) == K + D
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(4), Integer(4), Integer(4))
>>> D = sr.random_state_array()
>>> K = sr.random_state_array()
>>> sr.add_round_key(D, K) == K + D
True
base_ring()[source]#

Return the base field of self as determined by self.e.

EXAMPLES:

sage: sr = mq.SR(10, 2, 2, 4)
sage: sr.base_ring().polynomial()
a^4 + a + 1

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(2), Integer(2), Integer(4))
>>> sr.base_ring().polynomial()
a^4 + a + 1

The Rijndael polynomial:

sage: sr = mq.SR(10, 4, 4, 8)
sage: sr.base_ring().polynomial()
a^8 + a^4 + a^3 + a + 1

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(4), Integer(4), Integer(8))
>>> sr.base_ring().polynomial()
a^8 + a^4 + a^3 + a + 1
block_order()[source]#

Return a block order for self where each round is a block.

EXAMPLES:

sage: sr = mq.SR(2, 1, 1, 4)
sage: sr.block_order()
Block term order with blocks:
(Degree lexicographic term order of length 16,
 Degree lexicographic term order of length 16,
 Degree lexicographic term order of length 4)

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(1), Integer(1), Integer(4))
>>> sr.block_order()
Block term order with blocks:
(Degree lexicographic term order of length 16,
 Degree lexicographic term order of length 16,
 Degree lexicographic term order of length 4)

sage: P = sr.ring(order='block')
sage: print(P.repr_long())
Polynomial Ring
  Base Ring : Finite Field in a of size 2^4
       Size : 36 Variables
   Block  0 : Ordering : deglex
              Names    : k200, k201, k202, k203, x200, x201, x202, x203, w200, w201, w202, w203, s100, s101, s102, s103
   Block  1 : Ordering : deglex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
   Block  2 : Ordering : deglex
              Names    : k000, k001, k002, k003

>>> from sage.all import *
>>> P = sr.ring(order='block')
>>> print(P.repr_long())
Polynomial Ring
  Base Ring : Finite Field in a of size 2^4
       Size : 36 Variables
   Block  0 : Ordering : deglex
              Names    : k200, k201, k202, k203, x200, x201, x202, x203, w200, w201, w202, w203, s100, s101, s102, s103
   Block  1 : Ordering : deglex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
   Block  2 : Ordering : deglex
              Names    : k000, k001, k002, k003
hex_str(M, typ='matrix')[source]#

Return a hex string for the provided AES state array/matrix.

INPUT:

  • M – state array

  • typ – controls what to return, either ‘matrix’ or ‘vector’ (default: 'matrix')

EXAMPLES:

sage: sr = mq.SR(2, 2, 2, 4)
sage: k = sr.base_ring()
sage: A = matrix(k, 2, 2, [1, k.gen(), 0, k.gen()^2])
sage: sr.hex_str(A)
' 1 2 \n 0 4 \n'

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(2), Integer(4))
>>> k = sr.base_ring()
>>> A = matrix(k, Integer(2), Integer(2), [Integer(1), k.gen(), Integer(0), k.gen()**Integer(2)])
>>> sr.hex_str(A)
' 1 2 \n 0 4 \n'

sage: sr.hex_str(A, typ='vector')
'1024'

>>> from sage.all import *
>>> sr.hex_str(A, typ='vector')
'1024'
hex_str_matrix(M)[source]#

Return a two-dimensional AES-like representation of the matrix M.

That is, show the finite field elements as hex strings.

INPUT:

  • M – an AES state array

EXAMPLES:

sage: sr = mq.SR(2, 2, 2, 4)
sage: k = sr.base_ring()
sage: A = matrix(k, 2, 2, [1, k.gen(), 0, k.gen()^2])
sage: sr.hex_str_matrix(A)
' 1 2 \n 0 4 \n'

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(2), Integer(4))
>>> k = sr.base_ring()
>>> A = matrix(k, Integer(2), Integer(2), [Integer(1), k.gen(), Integer(0), k.gen()**Integer(2)])
>>> sr.hex_str_matrix(A)
' 1 2 \n 0 4 \n'
hex_str_vector(M)[source]#

Return a one-dimensional AES-like representation of the matrix M.

That is, show the finite field elements as hex strings.

INPUT:

  • M – an AES state array

EXAMPLES:

sage: sr = mq.SR(2, 2, 2, 4)
sage: k = sr.base_ring()
sage: A = matrix(k, 2, 2, [1, k.gen(), 0, k.gen()^2])
sage: sr.hex_str_vector(A)
'1024'

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(2), Integer(4))
>>> k = sr.base_ring()
>>> A = matrix(k, Integer(2), Integer(2), [Integer(1), k.gen(), Integer(0), k.gen()**Integer(2)])
>>> sr.hex_str_vector(A)
'1024'
is_state_array(d)[source]#

Return True if d is a state array, i.e. has the correct dimensions and base field.

EXAMPLES:

sage: sr = mq.SR(2, 2, 4, 8)
sage: k = sr.base_ring()
sage: sr.is_state_array( matrix(k, 2, 4) )
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(4), Integer(8))
>>> k = sr.base_ring()
>>> sr.is_state_array( matrix(k, Integer(2), Integer(4)) )
True

sage: sr = mq.SR(2, 2, 4, 8)
sage: k = sr.base_ring()
sage: sr.is_state_array( matrix(k, 4, 4) )
False

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(4), Integer(8))
>>> k = sr.base_ring()
>>> sr.is_state_array( matrix(k, Integer(4), Integer(4)) )
False
key_schedule(kj, i)[source]#

Return \(k_i\) for a given \(i\) and \(k_j\) with \(j = i-1\).

EXAMPLES:

sage: sr = mq.SR(10, 4, 4, 8, star=True, allow_zero_inversions=True)
sage: ki = sr.state_array()
sage: for i in range(10):
....:     ki = sr.key_schedule(ki, i+1)
sage: print(sr.hex_str_matrix(ki))
B4 3E 23 6F
EF 92 E9 8F
5B E2 51 18
CB 11 CF 8E

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(4), Integer(4), Integer(8), star=True, allow_zero_inversions=True)
>>> ki = sr.state_array()
>>> for i in range(Integer(10)):
...     ki = sr.key_schedule(ki, i+Integer(1))
>>> print(sr.hex_str_matrix(ki))
B4 3E 23 6F
EF 92 E9 8F
5B E2 51 18
CB 11 CF 8E
key_schedule_polynomials(i)[source]#

Return polynomials for the \(i\)-th round of the key schedule.

INPUT:

  • i – round (\(0 \leq i \leq n\))

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=False)

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True, polybori=False)

The 0-th subkey is the user provided key, so only conjugacy relations or field polynomials are added.:

sage: sr.key_schedule_polynomials(0)
(k000^2 + k000, k001^2 + k001, k002^2 + k002, k003^2 + k003)

>>> from sage.all import *
>>> sr.key_schedule_polynomials(Integer(0))
(k000^2 + k000, k001^2 + k001, k002^2 + k002, k003^2 + k003)

The 1-th subkey is derived from the user provided key according to the key schedule which is non-linear.:

sage: sr.key_schedule_polynomials(1)
(k100 + s000 + s002 + s003,
 k101 + s000 + s001 + s003 + 1,
 k102 + s000 + s001 + s002 + 1,
 k103 + s001 + s002 + s003 + 1,
 k100^2 + k100, k101^2 + k101, k102^2 + k102, k103^2 + k103,
 s000^2 + s000, s001^2 + s001, s002^2 + s002, s003^2 + s003,
 s000*k000 + s000*k003 + s001*k002 + s002*k001 + s003*k000,
 s000*k000 + s000*k001 + s001*k000 + s001*k003 + s002*k002 + s003*k001,
 s000*k001 + s000*k002 + s001*k000 + s001*k001 + s002*k000 + s002*k003 + s003*k002,
 s000*k000 + s000*k001 + s000*k003 + s001*k001 + s002*k000 + s002*k002 + s003*k000 + k000,
 s000*k002 + s001*k000 + s001*k001 + s001*k003 + s002*k001 + s003*k000 + s003*k002 + k001,
 s000*k000 + s000*k001 + s000*k002 + s001*k002 + s002*k000 + s002*k001 + s002*k003 + s003*k001 + k002,
 s000*k001 + s001*k000 + s001*k002 + s002*k000 + s003*k001 + s003*k003 + k003,
 s000*k000 + s000*k002 + s000*k003 + s001*k000 + s001*k001 + s002*k002 + s003*k000 + s000,
 s000*k001 + s000*k003 + s001*k001 + s001*k002 + s002*k000 + s002*k003 + s003*k001 + s001,
 s000*k000 + s000*k002 + s001*k000 + s001*k002 + s001*k003 + s002*k000 + s002*k001 + s003*k002 + s002,
 s000*k001 + s000*k002 + s001*k000 + s001*k003 + s002*k001 + s003*k003 + s003,
 s000*k002 + s001*k001 + s002*k000 + s003*k003 + 1)

>>> from sage.all import *
>>> sr.key_schedule_polynomials(Integer(1))
(k100 + s000 + s002 + s003,
 k101 + s000 + s001 + s003 + 1,
 k102 + s000 + s001 + s002 + 1,
 k103 + s001 + s002 + s003 + 1,
 k100^2 + k100, k101^2 + k101, k102^2 + k102, k103^2 + k103,
 s000^2 + s000, s001^2 + s001, s002^2 + s002, s003^2 + s003,
 s000*k000 + s000*k003 + s001*k002 + s002*k001 + s003*k000,
 s000*k000 + s000*k001 + s001*k000 + s001*k003 + s002*k002 + s003*k001,
 s000*k001 + s000*k002 + s001*k000 + s001*k001 + s002*k000 + s002*k003 + s003*k002,
 s000*k000 + s000*k001 + s000*k003 + s001*k001 + s002*k000 + s002*k002 + s003*k000 + k000,
 s000*k002 + s001*k000 + s001*k001 + s001*k003 + s002*k001 + s003*k000 + s003*k002 + k001,
 s000*k000 + s000*k001 + s000*k002 + s001*k002 + s002*k000 + s002*k001 + s002*k003 + s003*k001 + k002,
 s000*k001 + s001*k000 + s001*k002 + s002*k000 + s003*k001 + s003*k003 + k003,
 s000*k000 + s000*k002 + s000*k003 + s001*k000 + s001*k001 + s002*k002 + s003*k000 + s000,
 s000*k001 + s000*k003 + s001*k001 + s001*k002 + s002*k000 + s002*k003 + s003*k001 + s001,
 s000*k000 + s000*k002 + s001*k000 + s001*k002 + s001*k003 + s002*k000 + s002*k001 + s003*k002 + s002,
 s000*k001 + s000*k002 + s001*k000 + s001*k003 + s002*k001 + s003*k003 + s003,
 s000*k002 + s001*k001 + s002*k000 + s003*k003 + 1)
mix_columns(d)[source]#

Perform the MixColumns operation on d.

INPUT:

  • d – state array or something coercible to a state array

EXAMPLES:

sage: sr = mq.SR(10, 4, 4, 4)
sage: E = sr.state_array() + 1; E
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(4), Integer(4), Integer(4))
>>> E = sr.state_array() + Integer(1); E
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

sage: sr.mix_columns(E)
[    a a + 1     1     1]
[    1     a a + 1     1]
[    1     1     a a + 1]
[a + 1     1     1     a]

>>> from sage.all import *
>>> sr.mix_columns(E)
[    a a + 1     1     1]
[    1     a a + 1     1]
[    1     1     a a + 1]
[a + 1     1     1     a]
new_generator(**kwds)[source]#

Return a new SR instance equal to this instance except for the parameters passed explicitly to this function.

INPUT:

  • **kwds – see the SR constructor for accepted parameters

EXAMPLES:

sage: sr = mq.SR(2,1,1,4); sr
SR(2,1,1,4)
sage: sr.ring().base_ring()
Finite Field in a of size 2^4

>>> from sage.all import *
>>> sr = mq.SR(Integer(2),Integer(1),Integer(1),Integer(4)); sr
SR(2,1,1,4)
>>> sr.ring().base_ring()
Finite Field in a of size 2^4

sage: sr2 = sr.new_generator(gf2=True); sr2
SR(2,1,1,4)
sage: sr2.ring().base_ring()
Finite Field of size 2
sage: sr3 = sr2.new_generator(correct_only=True)
sage: len(sr2.inversion_polynomials_single_sbox())
20
sage: len(sr3.inversion_polynomials_single_sbox())
19

>>> from sage.all import *
>>> sr2 = sr.new_generator(gf2=True); sr2
SR(2,1,1,4)
>>> sr2.ring().base_ring()
Finite Field of size 2
>>> sr3 = sr2.new_generator(correct_only=True)
>>> len(sr2.inversion_polynomials_single_sbox())
20
>>> len(sr3.inversion_polynomials_single_sbox())
19
polynomial_system(P=None, K=None, C=None)[source]#

Return a polynomial system for this small scale AES variant for a given plaintext-key pair.

If neither P, K nor C are provided, a random pair (P, K) will be generated. If P and C are provided no K needs to be provided.

INPUT:

  • P – vector, list, or tuple (default: None)

  • K – vector, list, or tuple (default: None)

  • C – vector, list, or tuple (default: None)

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True)
sage: P = sr.vector([0, 0, 1, 0])
sage: K = sr.vector([1, 0, 0, 1])
sage: F, s = sr.polynomial_system(P, K)                                     # needs sage.rings.polynomial.pbori

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True, polybori=True)
>>> P = sr.vector([Integer(0), Integer(0), Integer(1), Integer(0)])
>>> K = sr.vector([Integer(1), Integer(0), Integer(0), Integer(1)])
>>> F, s = sr.polynomial_system(P, K)                                     # needs sage.rings.polynomial.pbori

This returns a polynomial system:

sage: F                                                                     # needs sage.rings.polynomial.pbori
Polynomial Sequence with 36 Polynomials in 20 Variables

>>> from sage.all import *
>>> F                                                                     # needs sage.rings.polynomial.pbori
Polynomial Sequence with 36 Polynomials in 20 Variables

and a solution:

sage: s  # random -- maybe we need a better doctest here?                   # needs sage.rings.polynomial.pbori
{k000: 1, k001: 0, k003: 1, k002: 0}

>>> from sage.all import *
>>> s  # random -- maybe we need a better doctest here?                   # needs sage.rings.polynomial.pbori
{k000: 1, k001: 0, k003: 1, k002: 0}

This solution is not the only solution that we can learn from the Groebner basis of the system.

sage: F.groebner_basis()[-3:]                                               # needs sage.rings.polynomial.pbori
[k000 + 1, k001, k003 + 1]

>>> from sage.all import *
>>> F.groebner_basis()[-Integer(3):]                                               # needs sage.rings.polynomial.pbori
[k000 + 1, k001, k003 + 1]

In particular we have two solutions:

sage: len(F.ideal().variety())                                              # needs sage.rings.polynomial.pbori
2

>>> from sage.all import *
>>> len(F.ideal().variety())                                              # needs sage.rings.polynomial.pbori
2

In the following example we provide C explicitly:

sage: C = sr(P,K)
sage: F,s = sr.polynomial_system(P=P, C=C)                                   # needs sage.rings.polynomial.pbori
sage: F                                                                      # needs sage.rings.polynomial.pbori
Polynomial Sequence with 36 Polynomials in 20 Variables

>>> from sage.all import *
>>> C = sr(P,K)
>>> F,s = sr.polynomial_system(P=P, C=C)                                   # needs sage.rings.polynomial.pbori
>>> F                                                                      # needs sage.rings.polynomial.pbori
Polynomial Sequence with 36 Polynomials in 20 Variables

Alternatively, we can use symbols for the P and C. First, we have to create a polynomial ring:

sage: # needs sage.rings.polynomial.pbori
sage: sr = mq.SR(1, 1, 1, 4, gf2=True, polybori=True)
sage: R = sr.R
sage: vn = sr.varstrs("P",0,1,4) + R.variable_names() + sr.varstrs("C",0,1,4)
sage: R = BooleanPolynomialRing(len(vn),vn)
sage: sr.R = R

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True, polybori=True)
>>> R = sr.R
>>> vn = sr.varstrs("P",Integer(0),Integer(1),Integer(4)) + R.variable_names() + sr.varstrs("C",Integer(0),Integer(1),Integer(4))
>>> R = BooleanPolynomialRing(len(vn),vn)
>>> sr.R = R

Now, we can construct the purely symbolic equation system:

sage: # needs sage.rings.polynomial.pbori
sage: C = sr.vars("C",0); C
(C000, C001, C002, C003)
sage: P = sr.vars("P",0)
sage: F,s = sr.polynomial_system(P=P,C=C)
sage: F
Polynomial Sequence with 36 Polynomials in 28 Variables
sage: F.part(0)
(P000 + w100 + k000, P001 + w101 + k001, P002 + w102 + k002, P003 + w103 + k003)
sage: F.part(-2)
(k100 + x100 + x102 + x103 + C000, k101 + x100 + x101 + x103 + C001 + 1, ...)

>>> from sage.all import *
>>> # needs sage.rings.polynomial.pbori
>>> C = sr.vars("C",Integer(0)); C
(C000, C001, C002, C003)
>>> P = sr.vars("P",Integer(0))
>>> F,s = sr.polynomial_system(P=P,C=C)
>>> F
Polynomial Sequence with 36 Polynomials in 28 Variables
>>> F.part(Integer(0))
(P000 + w100 + k000, P001 + w101 + k001, P002 + w102 + k002, P003 + w103 + k003)
>>> F.part(-Integer(2))
(k100 + x100 + x102 + x103 + C000, k101 + x100 + x101 + x103 + C001 + 1, ...)

We show that the (returned) key is a solution to the returned system:

sage: sr = mq.SR(3,4,4,8, star=True, gf2=True, polybori=True)
sage: while True:  # workaround (see :issue:`31891`)                         # needs sage.rings.polynomial.pbori
....:     try:
....:         F, s = sr.polynomial_system()
....:         break
....:     except ZeroDivisionError:
....:         pass
sage: F.subs(s).groebner_basis()    # long time                             # needs sage.rings.polynomial.pbori
Polynomial Sequence with 1248 Polynomials in 1248 Variables

>>> from sage.all import *
>>> sr = mq.SR(Integer(3),Integer(4),Integer(4),Integer(8), star=True, gf2=True, polybori=True)
>>> while True:  # workaround (see :issue:`31891`)                         # needs sage.rings.polynomial.pbori
...     try:
...         F, s = sr.polynomial_system()
...         break
...     except ZeroDivisionError:
...         pass
>>> F.subs(s).groebner_basis()    # long time                             # needs sage.rings.polynomial.pbori
Polynomial Sequence with 1248 Polynomials in 1248 Variables
random_element(elem_type='vector', *args, **kwds)[source]#

Return a random element for self. Other arguments and keywords are passed to random_* methods.

INPUT:

  • elem_type – either ‘vector’ or ‘state array’ (default: 'vector')

EXAMPLES:

sage: sr = mq.SR()
sage: sr.random_element().parent()
Full MatrixSpace of 4 by 1 dense matrices over Finite Field in a of size 2^4
sage: sr.random_element('state_array').parent()
Full MatrixSpace of 1 by 1 dense matrices over Finite Field in a of size 2^4

>>> from sage.all import *
>>> sr = mq.SR()
>>> sr.random_element().parent()
Full MatrixSpace of 4 by 1 dense matrices over Finite Field in a of size 2^4
>>> sr.random_element('state_array').parent()
Full MatrixSpace of 1 by 1 dense matrices over Finite Field in a of size 2^4

Passes extra positional or keyword arguments through:

sage: sr.random_element(density=0)
[0]
[0]
[0]
[0]

>>> from sage.all import *
>>> sr.random_element(density=Integer(0))
[0]
[0]
[0]
[0]
random_state_array(*args, **kwds)[source]#

Return a random element in MatrixSpace(self.base_ring(), self.r, self.c).

EXAMPLES:

sage: sr = mq.SR(2, 2, 2, 4)
sage: sr.random_state_array().parent()
Full MatrixSpace of 2 by 2 dense matrices over Finite Field in a of size 2^4

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(2), Integer(4))
>>> sr.random_state_array().parent()
Full MatrixSpace of 2 by 2 dense matrices over Finite Field in a of size 2^4
random_vector(*args, **kwds)[source]#

Return a random vector as it might appear in the algebraic expression of self.

EXAMPLES:

sage: mq.SR(2, 2, 2, 4).random_vector().parent()
Full MatrixSpace of 16 by 1 dense matrices over Finite Field in a of size 2^4

>>> from sage.all import *
>>> mq.SR(Integer(2), Integer(2), Integer(2), Integer(4)).random_vector().parent()
Full MatrixSpace of 16 by 1 dense matrices over Finite Field in a of size 2^4

Note

\(\phi\) was already applied to the result.

ring(order=None, reverse_variables=None)[source]#

Construct a ring as a base ring for the polynomial system.

By default, variables are ordered in the reverse of their natural ordering, i.e. the reverse of as they appear.

INPUT:

  • order – a monomial ordering (default: None)

  • reverse_variables – reverse rounds of variables (default: True)

The variable assignment is as follows:

  • \(k_{i,j,l}\) – subkey round \(i\) word \(j\) conjugate/bit \(l\)

  • \(s_{i,j,l}\) – subkey inverse round \(i\) word \(j\) conjugate/bit \(l\)

  • \(w_{i,j,l}\) – inversion input round \(i\) word \(j\) conjugate/bit \(l\)

  • \(x_{i,j,l}\) – inversion output round \(i\) word \(j\) conjugate/bit \(l\)

Note that the variables are ordered in column major ordering in the state array and that the bits are ordered in little endian ordering.

For example, if \(x_{0,1,0}\) is a variable over \(\GF{2}\) for \(r=2\) and \(c=2\) then refers to the most significant bit of the entry in the position (1,0) in the state array matrix.

EXAMPLES:

sage: sr = mq.SR(2, 1, 1, 4)
sage: P = sr.ring(order='block')
sage: print(P.repr_long())
Polynomial Ring
  Base Ring : Finite Field in a of size 2^4
       Size : 36 Variables
   Block  0 : Ordering : deglex
              Names    : k200, k201, k202, k203, x200, x201, x202, x203, w200, w201, w202, w203, s100, s101, s102, s103
   Block  1 : Ordering : deglex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
   Block  2 : Ordering : deglex
              Names    : k000, k001, k002, k003

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(1), Integer(1), Integer(4))
>>> P = sr.ring(order='block')
>>> print(P.repr_long())
Polynomial Ring
  Base Ring : Finite Field in a of size 2^4
       Size : 36 Variables
   Block  0 : Ordering : deglex
              Names    : k200, k201, k202, k203, x200, x201, x202, x203, w200, w201, w202, w203, s100, s101, s102, s103
   Block  1 : Ordering : deglex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003
   Block  2 : Ordering : deglex
              Names    : k000, k001, k002, k003
round_polynomials(i, plaintext=None, ciphertext=None)[source]#

Return list of polynomials for a given round \(i\).

If i == 0 a plaintext must be provided, if i == n a ciphertext must be provided.

INPUT:

  • i – round number

  • plaintext – optional plaintext (mandatory in first round)

  • ciphertext – optional ciphertext (mandatory in last round)

OUTPUT: tuple

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4)
sage: k = sr.base_ring()
sage: p = [k.random_element() for _ in range(sr.r*sr.c)]
sage: sr.round_polynomials(0, plaintext=p)
(w100 + k000..., w101 + k001..., w102 + k002..., w103 + k003...)

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4))
>>> k = sr.base_ring()
>>> p = [k.random_element() for _ in range(sr.r*sr.c)]
>>> sr.round_polynomials(Integer(0), plaintext=p)
(w100 + k000..., w101 + k001..., w102 + k002..., w103 + k003...)
sbox(inversion_only=False)[source]#

Return an S-Box object for this SR instance.

INPUT:

  • inversion_only – do not include the \(\GF{2}\) affine map when computing the S-Box (default: False)

EXAMPLES:

sage: sr = mq.SR(1,2,2,4, allow_zero_inversions=True)
sage: S = sr.sbox(); S
(6, 11, 5, 4, 2, 14, 7, 10, 9, 13, 15, 12, 3, 1, 0, 8)

sage: sr.sub_byte(0)
a^2 + a
sage: sage_eval(str(sr.sub_byte(0)), {'a':2})
6
sage: S(0)
6

sage: sr.sub_byte(1)
a^3 + a + 1
sage: sage_eval(str(sr.sub_byte(1)), {'a':2})
11
sage: S(1)
11

sage: sr = mq.SR(1,2,2,8, allow_zero_inversions=True)
sage: S = sr.sbox(); S
(99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43,
254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240,
173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38,
54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4,
199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39,
178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214,
179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91,
106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251,
67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81,
163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16,
255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196,
167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42,
144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58,
10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121,
231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234,
101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198,
232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102,
72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225,
248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206,
85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65,
153, 45, 15, 176, 84, 187, 22)

sage: sr.sub_byte(0)
a^6 + a^5 + a + 1

sage: sage_eval(str(sr.sub_byte(0)), {'a':2})
99
sage: S(0)
99

sage: sr.sub_byte(1)
a^6 + a^5 + a^4 + a^3 + a^2

sage: sage_eval(str(sr.sub_byte(1)), {'a':2})
124

sage: S(1)
124

sage: sr = mq.SR(1,2,2,4, allow_zero_inversions=True)
sage: S = sr.sbox(inversion_only=True); S
(0, 1, 9, 14, 13, 11, 7, 6, 15, 2, 12, 5, 10, 4, 3, 8)

sage: S(0)
0
sage: S(1)
1

sage: S(sr.k.gen())
a^3 + a + 1

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

>>> sr.sub_byte(Integer(0))
a^2 + a
>>> sage_eval(str(sr.sub_byte(Integer(0))), {'a':Integer(2)})
6
>>> S(Integer(0))
6

>>> sr.sub_byte(Integer(1))
a^3 + a + 1
>>> sage_eval(str(sr.sub_byte(Integer(1))), {'a':Integer(2)})
11
>>> S(Integer(1))
11

>>> sr = mq.SR(Integer(1),Integer(2),Integer(2),Integer(8), allow_zero_inversions=True)
>>> S = sr.sbox(); S
(99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43,
254, 215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240,
173, 212, 162, 175, 156, 164, 114, 192, 183, 253, 147, 38,
54, 63, 247, 204, 52, 165, 229, 241, 113, 216, 49, 21, 4,
199, 35, 195, 24, 150, 5, 154, 7, 18, 128, 226, 235, 39,
178, 117, 9, 131, 44, 26, 27, 110, 90, 160, 82, 59, 214,
179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 177, 91,
106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251,
67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81,
163, 64, 143, 146, 157, 56, 245, 188, 182, 218, 33, 16,
255, 243, 210, 205, 12, 19, 236, 95, 151, 68, 23, 196,
167, 126, 61, 100, 93, 25, 115, 96, 129, 79, 220, 34, 42,
144, 136, 70, 238, 184, 20, 222, 94, 11, 219, 224, 50, 58,
10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 228, 121,
231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234,
101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198,
232, 221, 116, 31, 75, 189, 139, 138, 112, 62, 181, 102,
72, 3, 246, 14, 97, 53, 87, 185, 134, 193, 29, 158, 225,
248, 152, 17, 105, 217, 142, 148, 155, 30, 135, 233, 206,
85, 40, 223, 140, 161, 137, 13, 191, 230, 66, 104, 65,
153, 45, 15, 176, 84, 187, 22)

>>> sr.sub_byte(Integer(0))
a^6 + a^5 + a + 1

>>> sage_eval(str(sr.sub_byte(Integer(0))), {'a':Integer(2)})
99
>>> S(Integer(0))
99

>>> sr.sub_byte(Integer(1))
a^6 + a^5 + a^4 + a^3 + a^2

>>> sage_eval(str(sr.sub_byte(Integer(1))), {'a':Integer(2)})
124

>>> S(Integer(1))
124

>>> sr = mq.SR(Integer(1),Integer(2),Integer(2),Integer(4), allow_zero_inversions=True)
>>> S = sr.sbox(inversion_only=True); S
(0, 1, 9, 14, 13, 11, 7, 6, 15, 2, 12, 5, 10, 4, 3, 8)

>>> S(Integer(0))
0
>>> S(Integer(1))
1

>>> S(sr.k.gen())
a^3 + a + 1
sbox_constant()[source]#

Return the S-Box constant which is added after \(L(x^{-1})\) was performed. That is 0x63 if e == 8 or 0x6 if e == 4.

EXAMPLES:

sage: sr = mq.SR(10, 1, 1, 8)
sage: sr.sbox_constant()
a^6 + a^5 + a + 1

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(1), Integer(1), Integer(8))
>>> sr.sbox_constant()
a^6 + a^5 + a + 1
shift_rows(d)[source]#

Perform the ShiftRows operation on d.

INPUT:

  • d – state array or something coercible to a state array

EXAMPLES:

sage: sr = mq.SR(10, 4, 4, 4)
sage: E = sr.state_array() + 1; E
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(4), Integer(4), Integer(4))
>>> E = sr.state_array() + Integer(1); E
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]

sage: sr.shift_rows(E)
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]

>>> from sage.all import *
>>> sr.shift_rows(E)
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
[1 0 0 0]
state_array(d=None)[source]#

Convert the parameter to a state array.

INPUT:

  • d – a matrix, a list, or a tuple (default: None)

EXAMPLES:

sage: sr = mq.SR(2, 2, 2, 4)
sage: k = sr.base_ring()
sage: e1 = [k.from_integer(e) for e in range(2*2)]; e1
[0, 1, a, a + 1]
sage: e2 = sr.phi( Matrix(k, 2*2, 1, e1) )
sage: sr.state_array(e1) # note the column major ordering
[    0     a]
[    1 a + 1]
sage: sr.state_array(e2)
[    0     a]
[    1 a + 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(2), Integer(2), Integer(4))
>>> k = sr.base_ring()
>>> e1 = [k.from_integer(e) for e in range(Integer(2)*Integer(2))]; e1
[0, 1, a, a + 1]
>>> e2 = sr.phi( Matrix(k, Integer(2)*Integer(2), Integer(1), e1) )
>>> sr.state_array(e1) # note the column major ordering
[    0     a]
[    1 a + 1]
>>> sr.state_array(e2)
[    0     a]
[    1 a + 1]

sage: sr.state_array()
[0 0]
[0 0]

>>> from sage.all import *
>>> sr.state_array()
[0 0]
[0 0]
sub_byte(b)[source]#

Perform SubByte on a single byte/halfbyte b.

A ZeroDivision exception is raised if an attempt is made to perform an inversion on the zero element. This can be disabled by passing allow_zero_inversion=True to the constructor. A zero inversion can result in an inconsistent equation system.

INPUT:

  • b – an element in self.base_ring()

EXAMPLES:

The S-Box table for \(\GF{2^4}\):

sage: sr = mq.SR(1, 1, 1, 4, allow_zero_inversions=True)
sage: for e in sr.base_ring():
....:    print('% 20s % 20s'%(e, sr.sub_byte(e)))
                0              a^2 + a
                a              a^2 + 1
              a^2                    a
              a^3              a^3 + 1
            a + 1                  a^2
          a^2 + a          a^2 + a + 1
        a^3 + a^2                a + 1
      a^3 + a + 1            a^3 + a^2
          a^2 + 1        a^3 + a^2 + a
          a^3 + a    a^3 + a^2 + a + 1
      a^2 + a + 1              a^3 + a
    a^3 + a^2 + a                    0
a^3 + a^2 + a + 1                  a^3
    a^3 + a^2 + 1                    1
          a^3 + 1        a^3 + a^2 + 1
                1          a^3 + a + 1

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), allow_zero_inversions=True)
>>> for e in sr.base_ring():
...    print('% 20s % 20s'%(e, sr.sub_byte(e)))
                0              a^2 + a
                a              a^2 + 1
              a^2                    a
              a^3              a^3 + 1
            a + 1                  a^2
          a^2 + a          a^2 + a + 1
        a^3 + a^2                a + 1
      a^3 + a + 1            a^3 + a^2
          a^2 + 1        a^3 + a^2 + a
          a^3 + a    a^3 + a^2 + a + 1
      a^2 + a + 1              a^3 + a
    a^3 + a^2 + a                    0
a^3 + a^2 + a + 1                  a^3
    a^3 + a^2 + 1                    1
          a^3 + 1        a^3 + a^2 + 1
                1          a^3 + a + 1
sub_bytes(d)[source]#

Perform the non-linear transform on d.

INPUT:

  • d – state array or something coercible to a state array

EXAMPLES:

sage: sr = mq.SR(2, 1, 2, 8, gf2=True)
sage: k = sr.base_ring()
sage: A = Matrix(k, 1, 2 , [k(1), k.gen()])
sage: sr.sub_bytes(A)
[  a^6 + a^5 + a^4 + a^3 + a^2 a^6 + a^5 + a^4 + a^2 + a + 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(1), Integer(2), Integer(8), gf2=True)
>>> k = sr.base_ring()
>>> A = Matrix(k, Integer(1), Integer(2) , [k(Integer(1)), k.gen()])
>>> sr.sub_bytes(A)
[  a^6 + a^5 + a^4 + a^3 + a^2 a^6 + a^5 + a^4 + a^2 + a + 1]
varformatstr(name, n=None, rc=None, e=None)[source]#

Return a format string which is understood by print et al.

If a numerical value is omitted, the default value of self is used. The numerical values (n, rc, e) are used to determine the width of the respective fields in the format string.

INPUT:

  • name – name of the variable

  • n – number of rounds (default: None)

  • rc – number of rows * number of cols (default: None)

  • e – exponent of base field (default: None)

EXAMPLES:

sage: sr = mq.SR(1, 2, 2, 4)
sage: sr.varformatstr('x')
'x%01d%01d%01d'
sage: sr.varformatstr('x', n=1000)
'x%03d%03d%03d'

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(2), Integer(4))
>>> sr.varformatstr('x')
'x%01d%01d%01d'
>>> sr.varformatstr('x', n=Integer(1000))
'x%03d%03d%03d'
variable_dict()[source]#

Return a dictionary to access variables in self.R by their names.

EXAMPLES:

sage: sr = mq.SR(1,1,1,4)
sage: sr.variable_dict()
{'k000': k000,
 'k001': k001,
 'k002': k002,
 'k003': k003,
 'k100': k100,
 'k101': k101,
 'k102': k102,
 'k103': k103,
 's000': s000,
 's001': s001,
 's002': s002,
 's003': s003,
 'w100': w100,
 'w101': w101,
 'w102': w102,
 'w103': w103,
 'x100': x100,
 'x101': x101,
 'x102': x102,
 'x103': x103}

sage: sr = mq.SR(1,1,1,4,gf2=True)
sage: sr.variable_dict()                                                    # needs sage.rings.polynomial.pbori
{'k000': k000,
 'k001': k001,
 'k002': k002,
 'k003': k003,
 'k100': k100,
 'k101': k101,
 'k102': k102,
 'k103': k103,
 's000': s000,
 's001': s001,
 's002': s002,
 's003': s003,
 'w100': w100,
 'w101': w101,
 'w102': w102,
 'w103': w103,
 'x100': x100,
 'x101': x101,
 'x102': x102,
 'x103': x103}

>>> from sage.all import *
>>> sr = mq.SR(Integer(1),Integer(1),Integer(1),Integer(4))
>>> sr.variable_dict()
{'k000': k000,
 'k001': k001,
 'k002': k002,
 'k003': k003,
 'k100': k100,
 'k101': k101,
 'k102': k102,
 'k103': k103,
 's000': s000,
 's001': s001,
 's002': s002,
 's003': s003,
 'w100': w100,
 'w101': w101,
 'w102': w102,
 'w103': w103,
 'x100': x100,
 'x101': x101,
 'x102': x102,
 'x103': x103}

>>> sr = mq.SR(Integer(1),Integer(1),Integer(1),Integer(4),gf2=True)
>>> sr.variable_dict()                                                    # needs sage.rings.polynomial.pbori
{'k000': k000,
 'k001': k001,
 'k002': k002,
 'k003': k003,
 'k100': k100,
 'k101': k101,
 'k102': k102,
 'k103': k103,
 's000': s000,
 's001': s001,
 's002': s002,
 's003': s003,
 'w100': w100,
 'w101': w101,
 'w102': w102,
 'w103': w103,
 'x100': x100,
 'x101': x101,
 'x102': x102,
 'x103': x103}
vars(name, nr, rc=None, e=None)[source]#

Return a list of variables in self.

INPUT:

  • name – variable name

  • nr – number of round to create variable strings for

  • rc – number of rounds * number of columns in the state array (default: None)

  • e – exponent of base field (default: None)

EXAMPLES:

sage: sr = mq.SR(10, 1, 2, 4)
sage: sr.vars('x', 2)
(x200, x201, x202, x203, x210, x211, x212, x213)

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(1), Integer(2), Integer(4))
>>> sr.vars('x', Integer(2))
(x200, x201, x202, x203, x210, x211, x212, x213)
varstr(name, nr, rc, e)[source]#

Return a string representing a variable for the small scale AES subject to the given constraints.

INPUT:

  • name – variable name

  • nr – number of round to create variable strings for

  • rc – row*column index in state array

  • e – exponent of base field

EXAMPLES:

sage: sr = mq.SR(10, 1, 2, 4)
sage: sr.varstr('x', 2, 1, 1)
'x211'

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(1), Integer(2), Integer(4))
>>> sr.varstr('x', Integer(2), Integer(1), Integer(1))
'x211'
varstrs(name, nr, rc=None, e=None)[source]#

Return a list of strings representing variables in self.

INPUT:

  • name – variable name

  • nr – number of round to create variable strings for

  • rc – number of rows * number of columns in the state array (default: None)

  • e – exponent of base field (default: None)

EXAMPLES:

sage: sr = mq.SR(10, 1, 2, 4)
sage: sr.varstrs('x', 2)
('x200', 'x201', 'x202', 'x203', 'x210', 'x211', 'x212', 'x213')

>>> from sage.all import *
>>> sr = mq.SR(Integer(10), Integer(1), Integer(2), Integer(4))
>>> sr.varstrs('x', Integer(2))
('x200', 'x201', 'x202', 'x203', 'x210', 'x211', 'x212', 'x213')
class sage.crypto.mq.sr.SR_gf2(n=1, r=1, c=1, e=4, star=False, **kwargs)[source]#

Bases: SR_generic

Small Scale Variants of the AES polynomial system constructor over \(\GF{2}\). See help for SR.

EXAMPLES:

sage: sr = mq.SR(gf2=True)
sage: sr
SR(1,1,1,4)

>>> from sage.all import *
>>> sr = mq.SR(gf2=True)
>>> sr
SR(1,1,1,4)
antiphi(l)[source]#

The operation \(\phi^{-1}\) from [MR2002] or the inverse of self.phi.

INPUT:

  • l – a vector in the sense of self.is_vector

EXAMPLES:

sage: sr = mq.SR(gf2=True)
sage: A = sr.random_state_array()
sage: sr.antiphi(sr.phi(A)) == A                                            # needs sage.libs.gap
True

>>> from sage.all import *
>>> sr = mq.SR(gf2=True)
>>> A = sr.random_state_array()
>>> sr.antiphi(sr.phi(A)) == A                                            # needs sage.libs.gap
True
field_polynomials(name, i, l=None)[source]#

Return list of field polynomials for a given round i and name name.

INPUT:

  • name – variable name

  • i – round number

  • l – length of variable list (default: None = r*c)

EXAMPLES:

sage: sr = mq.SR(3, 1, 1, 8, gf2=True, polybori=False)
sage: sr.field_polynomials('x', 2)
[x200^2 + x200, x201^2 + x201,
 x202^2 + x202, x203^2 + x203,
 x204^2 + x204, x205^2 + x205,
 x206^2 + x206, x207^2 + x207]

>>> from sage.all import *
>>> sr = mq.SR(Integer(3), Integer(1), Integer(1), Integer(8), gf2=True, polybori=False)
>>> sr.field_polynomials('x', Integer(2))
[x200^2 + x200, x201^2 + x201,
 x202^2 + x202, x203^2 + x203,
 x204^2 + x204, x205^2 + x205,
 x206^2 + x206, x207^2 + x207]

sage: sr = mq.SR(3, 1, 1, 8, gf2=True, polybori=True)
sage: sr.field_polynomials('x', 2)
[]

>>> from sage.all import *
>>> sr = mq.SR(Integer(3), Integer(1), Integer(1), Integer(8), gf2=True, polybori=True)
>>> sr.field_polynomials('x', Integer(2))
[]
inversion_polynomials(xi, wi, length)[source]#

Return polynomials to represent the inversion in the AES S-Box.

INPUT:

  • xi – output variables

  • wi – input variables

  • length – length of both lists

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 8, gf2=True)
sage: xi = sr.vars('x', 1)                                                  # needs sage.rings.polynomial.pbori
sage: wi = sr.vars('w', 1)                                                  # needs sage.rings.polynomial.pbori
sage: sr.inversion_polynomials(xi, wi, len(xi))[:3]                         # needs sage.rings.polynomial.pbori
[x100*w100 + x100*w102 + x100*w103 + x100*w107 + x101*w101 + x101*w102 + x101*w106 + x102*w100 + x102*w101 + x102*w105 + x103*w100 + x103*w104 + x104*w103 + x105*w102 + x106*w101 + x107*w100,
 x100*w101 + x100*w103 + x100*w104 + x101*w100 + x101*w102 + x101*w103 + x101*w107 + x102*w101 + x102*w102 + x102*w106 + x103*w100 + x103*w101 + x103*w105 + x104*w100 + x104*w104 + x105*w103 + x106*w102 + x107*w101,
 x100*w102 + x100*w104 + x100*w105 + x101*w101 + x101*w103 + x101*w104 + x102*w100 + x102*w102 + x102*w103 + x102*w107 + x103*w101 + x103*w102 + x103*w106 + x104*w100 + x104*w101 + x104*w105 + x105*w100 + x105*w104 + x106*w103 + x107*w102]

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(8), gf2=True)
>>> xi = sr.vars('x', Integer(1))                                                  # needs sage.rings.polynomial.pbori
>>> wi = sr.vars('w', Integer(1))                                                  # needs sage.rings.polynomial.pbori
>>> sr.inversion_polynomials(xi, wi, len(xi))[:Integer(3)]                         # needs sage.rings.polynomial.pbori
[x100*w100 + x100*w102 + x100*w103 + x100*w107 + x101*w101 + x101*w102 + x101*w106 + x102*w100 + x102*w101 + x102*w105 + x103*w100 + x103*w104 + x104*w103 + x105*w102 + x106*w101 + x107*w100,
 x100*w101 + x100*w103 + x100*w104 + x101*w100 + x101*w102 + x101*w103 + x101*w107 + x102*w101 + x102*w102 + x102*w106 + x103*w100 + x103*w101 + x103*w105 + x104*w100 + x104*w104 + x105*w103 + x106*w102 + x107*w101,
 x100*w102 + x100*w104 + x100*w105 + x101*w101 + x101*w103 + x101*w104 + x102*w100 + x102*w102 + x102*w103 + x102*w107 + x103*w101 + x103*w102 + x103*w106 + x104*w100 + x104*w101 + x104*w105 + x105*w100 + x105*w104 + x106*w103 + x107*w102]
inversion_polynomials_single_sbox(x=None, w=None, biaffine_only=None, correct_only=None)[source]#

Return inversion polynomials of a single S-Box.

INPUT:

  • xi – output variables

  • wi – input variables

  • length – length of both lists

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 8, gf2=True)
sage: len(sr.inversion_polynomials_single_sbox())
24
sage: len(sr.inversion_polynomials_single_sbox(correct_only=True))
23
sage: len(sr.inversion_polynomials_single_sbox(biaffine_only=False))
40
sage: len(sr.inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True))
39


sage: sr = mq.SR(1, 1, 1, 8, gf2=True)
sage: l0 = sr.inversion_polynomials_single_sbox(); len(l0)
24
sage: l1 = sr.inversion_polynomials_single_sbox(correct_only=True); len(l1)
23
sage: l2 = sr.inversion_polynomials_single_sbox(biaffine_only=False); len(l2)
40
sage: l3 = sr.inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True); len(l3)
39

sage: set(l0) == set(sr._inversion_polynomials_single_sbox())
True
sage: set(l1) == set(sr._inversion_polynomials_single_sbox(correct_only=True))
True
sage: set(l2) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False))
True
sage: set(l3) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True))
True

sage: sr = mq.SR(1, 1, 1, 4, gf2=True)
sage: l0 = sr.inversion_polynomials_single_sbox(); len(l0)
12
sage: l1 = sr.inversion_polynomials_single_sbox(correct_only=True); len(l1)
11
sage: l2 = sr.inversion_polynomials_single_sbox(biaffine_only=False); len(l2)
20
sage: l3 = sr.inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True); len(l3)
19

sage: set(l0) == set(sr._inversion_polynomials_single_sbox())
True
sage: set(l1) == set(sr._inversion_polynomials_single_sbox(correct_only=True))
True
sage: set(l2) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False))
True
sage: set(l3) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True))
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(8), gf2=True)
>>> len(sr.inversion_polynomials_single_sbox())
24
>>> len(sr.inversion_polynomials_single_sbox(correct_only=True))
23
>>> len(sr.inversion_polynomials_single_sbox(biaffine_only=False))
40
>>> len(sr.inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True))
39


>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(8), gf2=True)
>>> l0 = sr.inversion_polynomials_single_sbox(); len(l0)
24
>>> l1 = sr.inversion_polynomials_single_sbox(correct_only=True); len(l1)
23
>>> l2 = sr.inversion_polynomials_single_sbox(biaffine_only=False); len(l2)
40
>>> l3 = sr.inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True); len(l3)
39

>>> set(l0) == set(sr._inversion_polynomials_single_sbox())
True
>>> set(l1) == set(sr._inversion_polynomials_single_sbox(correct_only=True))
True
>>> set(l2) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False))
True
>>> set(l3) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True))
True

>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True)
>>> l0 = sr.inversion_polynomials_single_sbox(); len(l0)
12
>>> l1 = sr.inversion_polynomials_single_sbox(correct_only=True); len(l1)
11
>>> l2 = sr.inversion_polynomials_single_sbox(biaffine_only=False); len(l2)
20
>>> l3 = sr.inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True); len(l3)
19

>>> set(l0) == set(sr._inversion_polynomials_single_sbox())
True
>>> set(l1) == set(sr._inversion_polynomials_single_sbox(correct_only=True))
True
>>> set(l2) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False))
True
>>> set(l3) == set(sr._inversion_polynomials_single_sbox(biaffine_only=False, correct_only=True))
True
is_vector(d)[source]#

Return True if the given matrix satisfies the conditions for a vector as it appears in the algebraic expression of self.

INPUT:

  • d – matrix

EXAMPLES:

sage: sr = mq.SR(gf2=True)
sage: sr
SR(1,1,1,4)
sage: k = sr.base_ring()
sage: A = Matrix(k, 1, 1, [k.gen()])
sage: B = sr.vector(A)
sage: sr.is_vector(A)
False
sage: sr.is_vector(B)
True

>>> from sage.all import *
>>> sr = mq.SR(gf2=True)
>>> sr
SR(1,1,1,4)
>>> k = sr.base_ring()
>>> A = Matrix(k, Integer(1), Integer(1), [k.gen()])
>>> B = sr.vector(A)
>>> sr.is_vector(A)
False
>>> sr.is_vector(B)
True
lin_matrix(length=None)[source]#

Return the Lin matrix.

If no length is provided, the standard state space size is used. The key schedule calls this method with an explicit length argument because only self.r S-Box applications are performed in the key schedule.

INPUT:

  • length – length of state space (default: None)

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4, gf2=True)
sage: sr.lin_matrix()
[1 0 1 1]
[1 1 0 1]
[1 1 1 0]
[0 1 1 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4), gf2=True)
>>> sr.lin_matrix()
[1 0 1 1]
[1 1 0 1]
[1 1 1 0]
[0 1 1 1]
mix_columns_matrix()[source]#

Return the MixColumns matrix.

EXAMPLES:

sage: sr = mq.SR(1, 2, 2, 4, gf2=True)
sage: s = sr.random_state_array()
sage: r1 = sr.mix_columns(s)
sage: r2 = sr.state_array(sr.mix_columns_matrix() * sr.vector(s))
sage: r1 == r2
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(2), Integer(4), gf2=True)
>>> s = sr.random_state_array()
>>> r1 = sr.mix_columns(s)
>>> r2 = sr.state_array(sr.mix_columns_matrix() * sr.vector(s))
>>> r1 == r2
True
phi(l, diffusion_matrix=False)[source]#

The operation \(\phi\) from [MR2002]

Given a list/matrix of elements in \(\GF{2^e}\), return a matching list/matrix of elements in \(\GF{2}\).

INPUT:

  • l – element to perform \(\phi\) on.

  • diffusion_matrix – if True, the given matrix l is transformed to a matrix which performs the same operation over \(\GF{2}\) as l over \(\GF{2^n}\) (default: False).

EXAMPLES:

sage: sr = mq.SR(2, 1, 2, 4, gf2=True)
sage: k = sr.base_ring()
sage: A = matrix(k, 1, 2, [k.gen(), 0] )
sage: sr.phi(A)                                                             # needs sage.libs.gap
[0 0]
[0 0]
[1 0]
[0 0]

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(1), Integer(2), Integer(4), gf2=True)
>>> k = sr.base_ring()
>>> A = matrix(k, Integer(1), Integer(2), [k.gen(), Integer(0)] )
>>> sr.phi(A)                                                             # needs sage.libs.gap
[0 0]
[0 0]
[1 0]
[0 0]
shift_rows_matrix()[source]#

Return the ShiftRows matrix.

EXAMPLES:

sage: sr = mq.SR(1, 2, 2, 4, gf2=True)
sage: s = sr.random_state_array()
sage: r1 = sr.shift_rows(s)
sage: r2 = sr.state_array( sr.shift_rows_matrix() * sr.vector(s) )
sage: r1 == r2
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(2), Integer(4), gf2=True)
>>> s = sr.random_state_array()
>>> r1 = sr.shift_rows(s)
>>> r2 = sr.state_array( sr.shift_rows_matrix() * sr.vector(s) )
>>> r1 == r2
True
vector(d=None)[source]#

Constructs a vector suitable for the algebraic representation of SR.

INPUT:

  • d – values for vector (default: None)

EXAMPLES:

sage: sr = mq.SR(gf2=True)
sage: sr
SR(1,1,1,4)
sage: k = sr.base_ring()
sage: A = Matrix(k, 1, 1, [k.gen()])
sage: sr.vector(A)
[0]
[0]
[1]
[0]

>>> from sage.all import *
>>> sr = mq.SR(gf2=True)
>>> sr
SR(1,1,1,4)
>>> k = sr.base_ring()
>>> A = Matrix(k, Integer(1), Integer(1), [k.gen()])
>>> sr.vector(A)
[0]
[0]
[1]
[0]
class sage.crypto.mq.sr.SR_gf2_2(n=1, r=1, c=1, e=4, star=False, **kwargs)[source]#

Bases: SR_gf2

This is an example how to customize the SR constructor.

In this example, we replace the S-Box inversion polynomials by the polynomials generated by the S-Box class.

inversion_polynomials_single_sbox(x=None, w=None, biaffine_only=None, correct_only=None, groebner=False)[source]#

Return inversion polynomials of a single S-Box.

INPUT:

  • x – output variables (default: None)

  • w – input variables (default: None)

  • biaffine_only – ignored (always False)

  • correct_only – ignored (always True)

  • groebner – precompute the Groebner basis for this S-Box (default: False).

EXAMPLES:

sage: from sage.crypto.mq.sr import SR_gf2_2
sage: e = 4
sage: sr = SR_gf2_2(1, 1, 1, e)
sage: P = PolynomialRing(GF(2),['x%d'%i for i in range(e)] + ['w%d'%i for i in range(e)],order='lex')
sage: X,W = P.gens()[:e],P.gens()[e:]
sage: sr.inversion_polynomials_single_sbox(X, W, groebner=True)             # needs sage.libs.singular
[x0 + w0*w1*w2 + w0*w1 + w0*w2 + w0*w3 + w0 + w1 + w2,
 x1 + w0*w1*w3 + w0*w3 + w0 + w1*w3 + w1 + w2*w3,
 x2 + w0*w2*w3 + w0*w2 + w0 + w1*w2 + w1*w3 + w2*w3,
 x3 + w0*w1*w2 + w0 + w1*w2*w3 + w1*w2 + w1*w3 + w1 + w2 + w3]

sage: from sage.crypto.mq.sr import SR_gf2_2
sage: e = 4
sage: sr = SR_gf2_2(1, 1, 1, e)
sage: sr.inversion_polynomials_single_sbox()                                # needs sage.libs.singular
[w3*w1 + w3*w0 + w3*x2 + w3*x1 + w3 + w2*w1 + w1 + x3 + x2 + x1,
 w3*w2 + w3*w1 + w3*x3 + w2 + w1 + x3,
 w3*w2 + w3*w1 + w3*x2 + w3 + w2*x3 + x2 + x1,
 w3*w2 + w3*w1 + w3*x3 + w3*x2 + w3*x1 + w3 + w2*x2 + w0 + x3 + x2 + x1 + x0,
 w3*w2 + w3*w1 + w3*x1 + w3*x0 + w2*x1 + w0 + x3 + x0,
 w3*w2 + w3*w1 + w3*w0 + w3*x2 + w3*x1 + w2*w0 + w2*x0 + w0 + x3 + x2 + x1 + x0,
 w3*w2 + w3*x1 + w3 + w2*w0 + w1*w0 + w1 + x3 + x2,
 w3*w2 + w3*w1 + w3*x1 + w1*x3 + x3 + x2 + x1,
 w3*x3 + w3*x2 + w3*x0 + w3 + w1*x2 + w1 + w0 + x2 + x0,
 w3*w2 + w3*w1 + w3*x2 + w3*x1 + w1*x1 + w1 + w0 + x2 + x0,
 w3*w2 + w3*w1 + w3*w0 + w3*x3 + w3*x1 + w2*w0 + w1*x0 + x3 + x2,
 w3*w2 + w3*w1 + w3*x2 + w3*x1 + w3*x0 + w3 + w1 + w0*x3 + x3 + x2,
 w3*w2 + w3*w1 + w3*w0 + w3*x3 + w3 + w2*w0 + w1 + w0*x2 + x3 + x2,
 w3*w0 + w3*x2 + w2*w0 + w0*x1 + w0 + x3 + x1 + x0,
 w3*w0 + w3*x3 + w3*x0 + w2*w0 + w1 + w0*x0 + w0 + x3 + x2,
 w3*w2 + w3 + w1 + x3*x2 + x3 + x1,
 w3*w2 + w3*x3 + w1 + x3*x1 + x3 + x2,
 w3*w2 + w3*w0 + w3*x3 + w3*x2 + w3*x1 + w0 + x3*x0 + x1 + x0,
 w3*w2 + w3*w1 + w3*w0 + w3*x3 + w1 + w0 + x2*x1 + x2 + x0,
 w3*w2 + w2*w0 + w1 + x3 + x2*x0,
 w3*x3 + w3*x1 + w2*w0 + w1 + x3 + x2 + x1*x0 + x1]

>>> from sage.all import *
>>> from sage.crypto.mq.sr import SR_gf2_2
>>> e = Integer(4)
>>> sr = SR_gf2_2(Integer(1), Integer(1), Integer(1), e)
>>> P = PolynomialRing(GF(Integer(2)),['x%d'%i for i in range(e)] + ['w%d'%i for i in range(e)],order='lex')
>>> X,W = P.gens()[:e],P.gens()[e:]
>>> sr.inversion_polynomials_single_sbox(X, W, groebner=True)             # needs sage.libs.singular
[x0 + w0*w1*w2 + w0*w1 + w0*w2 + w0*w3 + w0 + w1 + w2,
 x1 + w0*w1*w3 + w0*w3 + w0 + w1*w3 + w1 + w2*w3,
 x2 + w0*w2*w3 + w0*w2 + w0 + w1*w2 + w1*w3 + w2*w3,
 x3 + w0*w1*w2 + w0 + w1*w2*w3 + w1*w2 + w1*w3 + w1 + w2 + w3]

>>> from sage.crypto.mq.sr import SR_gf2_2
>>> e = Integer(4)
>>> sr = SR_gf2_2(Integer(1), Integer(1), Integer(1), e)
>>> sr.inversion_polynomials_single_sbox()                                # needs sage.libs.singular
[w3*w1 + w3*w0 + w3*x2 + w3*x1 + w3 + w2*w1 + w1 + x3 + x2 + x1,
 w3*w2 + w3*w1 + w3*x3 + w2 + w1 + x3,
 w3*w2 + w3*w1 + w3*x2 + w3 + w2*x3 + x2 + x1,
 w3*w2 + w3*w1 + w3*x3 + w3*x2 + w3*x1 + w3 + w2*x2 + w0 + x3 + x2 + x1 + x0,
 w3*w2 + w3*w1 + w3*x1 + w3*x0 + w2*x1 + w0 + x3 + x0,
 w3*w2 + w3*w1 + w3*w0 + w3*x2 + w3*x1 + w2*w0 + w2*x0 + w0 + x3 + x2 + x1 + x0,
 w3*w2 + w3*x1 + w3 + w2*w0 + w1*w0 + w1 + x3 + x2,
 w3*w2 + w3*w1 + w3*x1 + w1*x3 + x3 + x2 + x1,
 w3*x3 + w3*x2 + w3*x0 + w3 + w1*x2 + w1 + w0 + x2 + x0,
 w3*w2 + w3*w1 + w3*x2 + w3*x1 + w1*x1 + w1 + w0 + x2 + x0,
 w3*w2 + w3*w1 + w3*w0 + w3*x3 + w3*x1 + w2*w0 + w1*x0 + x3 + x2,
 w3*w2 + w3*w1 + w3*x2 + w3*x1 + w3*x0 + w3 + w1 + w0*x3 + x3 + x2,
 w3*w2 + w3*w1 + w3*w0 + w3*x3 + w3 + w2*w0 + w1 + w0*x2 + x3 + x2,
 w3*w0 + w3*x2 + w2*w0 + w0*x1 + w0 + x3 + x1 + x0,
 w3*w0 + w3*x3 + w3*x0 + w2*w0 + w1 + w0*x0 + w0 + x3 + x2,
 w3*w2 + w3 + w1 + x3*x2 + x3 + x1,
 w3*w2 + w3*x3 + w1 + x3*x1 + x3 + x2,
 w3*w2 + w3*w0 + w3*x3 + w3*x2 + w3*x1 + w0 + x3*x0 + x1 + x0,
 w3*w2 + w3*w1 + w3*w0 + w3*x3 + w1 + w0 + x2*x1 + x2 + x0,
 w3*w2 + w2*w0 + w1 + x3 + x2*x0,
 w3*x3 + w3*x1 + w2*w0 + w1 + x3 + x2 + x1*x0 + x1]
class sage.crypto.mq.sr.SR_gf2n(n=1, r=1, c=1, e=4, star=False, **kwargs)[source]#

Bases: SR_generic

Small Scale Variants of the AES polynomial system constructor over \(\GF{2^n}\).

antiphi(l)[source]#

The operation \(\phi^{-1}\) from [MR2002] or the inverse of self.phi.

INPUT:

EXAMPLES:

sage: sr = mq.SR()
sage: A = sr.random_state_array()
sage: sr.antiphi(sr.phi(A)) == A
True

>>> from sage.all import *
>>> sr = mq.SR()
>>> A = sr.random_state_array()
>>> sr.antiphi(sr.phi(A)) == A
True
field_polynomials(name, i, l=None)[source]#

Return list of conjugacy polynomials for a given round i and name name.

INPUT:

  • name – variable name

  • i – round number

  • l – r*c (default: None)

EXAMPLES:

sage: sr = mq.SR(3, 1, 1, 8)
sage: sr.field_polynomials('x', 2)
[x200^2 + x201,
x201^2 + x202,
x202^2 + x203,
x203^2 + x204,
x204^2 + x205,
x205^2 + x206,
x206^2 + x207,
x207^2 + x200]

>>> from sage.all import *
>>> sr = mq.SR(Integer(3), Integer(1), Integer(1), Integer(8))
>>> sr.field_polynomials('x', Integer(2))
[x200^2 + x201,
x201^2 + x202,
x202^2 + x203,
x203^2 + x204,
x204^2 + x205,
x205^2 + x206,
x206^2 + x207,
x207^2 + x200]
inversion_polynomials(xi, wi, length)[source]#

Return polynomials to represent the inversion in the AES S-Box.

INPUT:

  • xi – output variables

  • wi – input variables

  • length – length of both lists

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 8)
sage: R = sr.ring()
sage: xi = Matrix(R, 8, 1, sr.vars('x', 1))
sage: wi = Matrix(R, 8, 1, sr.vars('w', 1))
sage: sr.inversion_polynomials(xi, wi, 8)
[x100*w100 + 1,
x101*w101 + 1,
x102*w102 + 1,
x103*w103 + 1,
x104*w104 + 1,
x105*w105 + 1,
x106*w106 + 1,
x107*w107 + 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(8))
>>> R = sr.ring()
>>> xi = Matrix(R, Integer(8), Integer(1), sr.vars('x', Integer(1)))
>>> wi = Matrix(R, Integer(8), Integer(1), sr.vars('w', Integer(1)))
>>> sr.inversion_polynomials(xi, wi, Integer(8))
[x100*w100 + 1,
x101*w101 + 1,
x102*w102 + 1,
x103*w103 + 1,
x104*w104 + 1,
x105*w105 + 1,
x106*w106 + 1,
x107*w107 + 1]
is_vector(d)[source]#

Return True if d can be used as a vector for self.

EXAMPLES:

sage: sr = mq.SR()
sage: sr
SR(1,1,1,4)
sage: k = sr.base_ring()
sage: A = Matrix(k, 1, 1, [k.gen()])
sage: B = sr.vector(A)
sage: sr.is_vector(A)
False
sage: sr.is_vector(B)
True

>>> from sage.all import *
>>> sr = mq.SR()
>>> sr
SR(1,1,1,4)
>>> k = sr.base_ring()
>>> A = Matrix(k, Integer(1), Integer(1), [k.gen()])
>>> B = sr.vector(A)
>>> sr.is_vector(A)
False
>>> sr.is_vector(B)
True
lin_matrix(length=None)[source]#

Return the Lin matrix.

If no length is provided, the standard state space size is used. The key schedule calls this method with an explicit length argument because only self.r S-Box applications are performed in the key schedule.

INPUT:

  • length – length of state space (default: None)

EXAMPLES:

sage: sr = mq.SR(1, 1, 1, 4)
sage: sr.lin_matrix()
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(1), Integer(1), Integer(4))
>>> sr.lin_matrix()
[          a^2 + 1                 1         a^3 + a^2           a^2 + 1]
[                a                 a                 1 a^3 + a^2 + a + 1]
[          a^3 + a               a^2               a^2                 1]
[                1               a^3             a + 1             a + 1]
mix_columns_matrix()[source]#

Return the MixColumns matrix.

EXAMPLES:

sage: sr = mq.SR(1, 2, 2, 4)
sage: s = sr.random_state_array()
sage: r1 = sr.mix_columns(s)
sage: r2 = sr.state_array(sr.mix_columns_matrix() * sr.vector(s))
sage: r1 == r2
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(2), Integer(4))
>>> s = sr.random_state_array()
>>> r1 = sr.mix_columns(s)
>>> r2 = sr.state_array(sr.mix_columns_matrix() * sr.vector(s))
>>> r1 == r2
True
phi(l)[source]#

The operation \(\phi\) from [MR2002]

Projects state arrays to their algebraic representation.

INPUT:

  • l – element to perform \(\phi\) on.

EXAMPLES:

sage: sr = mq.SR(2, 1, 2, 4)
sage: k = sr.base_ring()
sage: A = matrix(k, 1, 2, [k.gen(), 0] )
sage: sr.phi(A)
[      a       0]
[    a^2       0]
[  a + 1       0]
[a^2 + 1       0]

>>> from sage.all import *
>>> sr = mq.SR(Integer(2), Integer(1), Integer(2), Integer(4))
>>> k = sr.base_ring()
>>> A = matrix(k, Integer(1), Integer(2), [k.gen(), Integer(0)] )
>>> sr.phi(A)
[      a       0]
[    a^2       0]
[  a + 1       0]
[a^2 + 1       0]
shift_rows_matrix()[source]#

Return the ShiftRows matrix.

EXAMPLES:

sage: sr = mq.SR(1, 2, 2, 4)
sage: s = sr.random_state_array()
sage: r1 = sr.shift_rows(s)
sage: r2 = sr.state_array( sr.shift_rows_matrix() * sr.vector(s) )
sage: r1 == r2
True

>>> from sage.all import *
>>> sr = mq.SR(Integer(1), Integer(2), Integer(2), Integer(4))
>>> s = sr.random_state_array()
>>> r1 = sr.shift_rows(s)
>>> r2 = sr.state_array( sr.shift_rows_matrix() * sr.vector(s) )
>>> r1 == r2
True
vector(d=None)[source]#

Constructs a vector suitable for the algebraic representation of SR, i.e. BES.

INPUT:

  • d – values for vector, must be understood by self.phi (default:None)

EXAMPLES:

sage: sr = mq.SR()
sage: sr
SR(1,1,1,4)
sage: k = sr.base_ring()
sage: A = Matrix(k, 1, 1, [k.gen()])
sage: sr.vector(A)
[      a]
[    a^2]
[  a + 1]
[a^2 + 1]

>>> from sage.all import *
>>> sr = mq.SR()
>>> sr
SR(1,1,1,4)
>>> k = sr.base_ring()
>>> A = Matrix(k, Integer(1), Integer(1), [k.gen()])
>>> sr.vector(A)
[      a]
[    a^2]
[  a + 1]
[a^2 + 1]
sage.crypto.mq.sr.test_consistency(max_n=2, **kwargs)[source]#

Test all combinations of r, c, e and n in (1, 2) for consistency of random encryptions and their polynomial systems. \(\GF{2}\) and \(\GF{2^e}\) systems are tested. This test takes a while.

INPUT:

  • max_n – maximal number of rounds to consider (default: 2)

  • kwargs – are passed to the SR constructor