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): (github 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)

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)

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

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]

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]

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]

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]

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]

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

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]

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]

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

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

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

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]

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

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

REFERENCES:

• [CMR2005]

• [CMR2006]

• [MR2002]

class sage.crypto.mq.sr.AllowZeroInversionsContext(sr)

Bases: object

Temporarily allow zero inversion.

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

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

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

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

class sage.crypto.mq.sr.SR_generic(n=1, r=1, c=1, e=4, star=False, **kwargs)

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

add_round_key(d, key)

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

base_ring()

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

The Rijndael polynomial:

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

block_order()

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)

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

hex_str(M, typ='matrix')

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'

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

hex_str_matrix(M)

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'

hex_str_vector(M)

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'

is_state_array(d)

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

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

key_schedule(kj, i)

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

key_schedule_polynomials(i)

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)

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)

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)

mix_columns(d)

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]

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]

new_generator(**kwds)

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

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

polynomial_system(P=None, K=None, C=None)

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

This returns a polynomial system:

sage: 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}

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]

In particular we have two solutions:

sage: 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

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

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, ...)

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

random_element(elem_type='vector', *args, **kwds)

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

Passes extra positional or keyword arguments through:

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

random_state_array(*args, **kwds)

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

random_vector(*args, **kwds)

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

Note

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

ring(order=None, reverse_variables=None)

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

round_polynomials(i, plaintext=None, ciphertext=None)

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

sbox(inversion_only=False)

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

sbox_constant()

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

shift_rows(d)

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]

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

state_array(d=None)

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]

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

sub_byte(b)

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

sub_bytes(d)

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]

varformatstr(name, n=None, rc=None, e=None)

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'

variable_dict()

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}

vars(name, nr, rc=None, e=None)

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)

varstr(name, nr, rc, e)

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'

varstrs(name, nr, rc=None, e=None)

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

class sage.crypto.mq.sr.SR_gf2(n=1, r=1, c=1, e=4, star=False, **kwargs)

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)

antiphi(l)

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

field_polynomials(name, i, l=None)

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]

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

inversion_polynomials(xi, wi, length)

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]

inversion_polynomials_single_sbox(x=None, w=None, biaffine_only=None, correct_only=None)

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

is_vector(d)

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

lin_matrix(length=None)

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]

mix_columns_matrix()

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

phi(l, diffusion_matrix=False)

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]

shift_rows_matrix()

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

vector(d=None)

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]

class sage.crypto.mq.sr.SR_gf2_2(n=1, r=1, c=1, e=4, star=False, **kwargs)

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)

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]

class sage.crypto.mq.sr.SR_gf2n(n=1, r=1, c=1, e=4, star=False, **kwargs)

Bases: SR_generic

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

antiphi(l)

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

INPUT:

• l – a vector in the sense of is_vector()

EXAMPLES:

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

field_polynomials(name, i, l=None)

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]

inversion_polynomials(xi, wi, length)

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]

is_vector(d)

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

lin_matrix(length=None)

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]

mix_columns_matrix()

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

phi(l)

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]

shift_rows_matrix()

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

vector(d=None)

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]

sage.crypto.mq.sr.test_consistency(max_n=2, **kwargs)

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