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

Module: sage.crypto.mq.sr

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

Sage support 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 paper and a variant of SR* which is equivalent to AES.

Author: Martin Albrecht (malb@informatik.uni-bremen.de) (2007-09) initial version

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. $ 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: sr.R
Multivariate Polynomial Ring in k100, k101, k102, k103, x100, x101, x102,
x103, w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002,
k003 over Finite Field in a of size 2^4

For SR(1, 1, 1, 4) the ShiftRows matrix isn't that interresting:

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]

TESTS:

sage: sr == loads(dumps(sr))
True

REFERENCES: C. Cid , S. Murphy, and M.J.B. Robshaw; Small Scale Variants of the AES; in Proceedings of Fast Software Encryption 2005, LNCS 3557; Springer 2005; available at http://www.isg.rhul.ac.uk/ sean/smallAES-fse05.pdf

C. Cid , S. Murphy, and M.J.B. Robshaw; Algebraic Aspects of the Advanced Encryption Standard; Springer 2006;

Module-level Functions

SR( [n=1], [r=1], [c=1], [e=4], [star=False])

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^n)$ (default: False)
order
- a string to specify the term ordering of the variables
postfix
- a string which is appended after the variable name (default: '')
allow_zero_inversions
- a boolean to controll whether zero inversions raise an exception (default: False)
correct_only
- only include correct inversion polynomials (default: False, GF2 only)
biaffine_only
- only include bilinear and biaffine inversion polynomials (default: True, GF2 only)

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

class SR_generic
SR_generic( self, [n=1], [r=1], [c=1], [e=4], [star=False])

Small Scale Variants of the AES.

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

Functions: add_round_key,$ \,$ base_ring,$ \,$ block_order,$ \,$ hex_str,$ \,$ hex_str_matrix,$ \,$ hex_str_vector,$ \,$ is_state_array,$ \,$ key_schedule,$ \,$ key_schedule_polynomials,$ \,$ mix_columns,$ \,$ polynomial_system,$ \,$ random_element,$ \,$ random_state_array,$ \,$ random_vector,$ \,$ ring,$ \,$ round_polynomials,$ \,$ sbox_constant,$ \,$ shift_rows,$ \,$ state_array,$ \,$ sub_byte,$ \,$ sub_bytes,$ \,$ varformatstr,$ \,$ vars,$ \,$ varstrs

add_round_key( self, d, key)

Perform the AddRoundKey operation on d using key.

Input:

d
- state arrary or something coercable to an state array
key
- state arrary or something coercable to an state array

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

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

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

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

sage: sr = mq.SR(2, 1, 1, 4)
sage: sr.block_order()
degrevlex(16),degrevlex(16),degrevlex(4) term order

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 : degrevlex
              Names    : k200, k201, k202, k203, x200, x201, x202, x203,
w200, w201, w202, w203, s100, s101, s102, s103
   Block  1 : Ordering : degrevlex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103,
w100, w101, w102, w103, s000, s001, s002, s003
   Block  2 : Ordering : degrevlex
              Names    : k000, k001, k002, k003

hex_str( self, 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')

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( self, 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

            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 
 0 4 
'

hex_str_vector( self, 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

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( self, d)

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

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( self, kj, i)

Return $ k_i$ for a given $ i$ and $ k_j$ with $ j = i-1$ .

TESTS:

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( self, i)

Return polynomials for the $ i$ -th round of the key schedule.

Input:

i
- round (0 <= i <= n)

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

The 0-th subkey is the user provided key, so only conjugacy relations 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 + s003*k000 + s002*k001 + s001*k002 +
s000*k003, s000*k000 + s001*k000 + s000*k001 + s003*k001 +
s002*k002 + s001*k003, s001*k000 + s002*k000 + s000*k001 +
s001*k001 + s000*k002 + s003*k002 + s002*k003, s002*k000 +
s001*k001 + s000*k002 + s003*k003 + 1, s000*k000 +
s002*k000 + s003*k000 + s000*k001 + s001*k001 + s002*k002
+ s000*k003 + k000, s001*k000 + s003*k000 + s001*k001 +
s002*k001 + s000*k002 + s003*k002 + s001*k003 + k001,
s000*k000 + s002*k000 + s000*k001 + s002*k001 + s003*k001
+ s000*k002 + s001*k002 + s002*k003 + k002, s001*k000 +
s002*k000 + s000*k001 + s003*k001 + s001*k002 + s003*k003
+ k003, s000*k000 + s001*k000 + s003*k000 + s001*k001 +
s000*k002 + s002*k002 + s000*k003 + s000, s002*k000 +
s000*k001 + s001*k001 + s003*k001 + s001*k002 + s000*k003
+ s002*k003 + s001, s000*k000 + s001*k000 + s002*k000 +
s002*k001 + s000*k002 + s001*k002 + s003*k002 + s001*k003
+ s002, s001*k000 + s000*k001 + s002*k001 + s000*k002 +
s001*k003 + s003*k003 + s003]

mix_columns( self, d)

Perform the MixColumns operation on d.

Input:

d
- state arrary or something coercable to an state array

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]

polynomial_system( self, [P=None], [K=None])

Return a MPolynomialSystem for self for a given plaintext-key pair.

If none are provided a random pair will be generated.

Input:

P
- vector, list, or tuple (default: None)
K
- vector, list, or tuple (default: None)

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)

This returns a polynomial system

sage: F
Polynomial System with 56 Polynomials in 20 Variables

and a solution:

sage: s
{k000: 1, k001: 0, k002: 0, k003: 1}

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

sage: F.groebner_basis()[:4]
[k003 + 1, k001, k000 + 1, s003 + k002]

In particular we have two solutions

sage: len(F.ideal().variety())
2

random_element( self, [elem_type=vector])

Return a random element for self.

Input:

elem_type
- either 'vector' or 'state array' (default: 'vector')

sage: sr = mq.SR()
sage: sr.random_element()
[  a^3 + a + 1]
[      a^3 + 1]
[a^3 + a^2 + 1]
[a^3 + a^2 + a]
sage: sr.random_element('state_array')
[a + 1]

random_state_array( self)

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

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

random_vector( self)

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

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

NOTE: Phi was already applied to the result.

ring( self, [order=None])

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

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

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 : degrevlex
              Names    : k200, k201, k202, k203, x200, x201, x202, x203,
w200, w201, w202, w203, s100, s101, s102, s103
   Block  1 : Ordering : degrevlex
              Names    : k100, k101, k102, k103, x100, x101, x102, x103,
w100, w101, w102, w103, s000, s001, s002, s003
   Block  2 : Ordering : degrevlex
              Names    : k000, k001, k002, k003

round_polynomials( self, 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: MPolynomialRoundSystem

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 + (a^2 + 1), w101 + k001 + (a), w102 + k002 + (a^2), w103 +
k003 + (a + 1)]

sbox_constant( self)

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

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

shift_rows( self, d)

Perform the ShiftRows operation on d.

Input:

d
- state arrary or something coercable to an state array

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( self, [d=None])

Convert the parameter to a state array.

Input:

d
- None, a matrix, a list, or a tuple

sage: sr = mq.SR(2, 2, 2, 4)
sage: k = sr.base_ring()
sage: e1 = [k.fetch_int(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( self, 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 will result in an inconsisten equation system.

Input:

b
- an element in self.base_ring()

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( self, d)

Perform the non-linear transform on d.

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]

Input:

d
- state array or something coercable to a state array

varformatstr( self, name, [n=None], [rc=None], [e=None])

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

If a numberical 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)

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'

vars( self, name, nr, [rc=None], [e=None])

Return a list ofvariables 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
e
- exponent of base field

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

varstrs( self, 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 rounds * number of columns in the state array
e
- exponent of base field

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

Special Functions: __call__,$ \,$ __cmp__,$ \,$ __init__,$ \,$ _insert_matrix_into_matrix,$ \,$ _repr_

__call__( self, P, K)

Encrypts the plaintext $ P$ using the key $ K$ .

Both must be given as state arrays or coercable to state arrays.

INPUTS: P - plaintext as state array or something coercable to a state array K - key as state array or something coercable to a state array

TESTS: The official AES test vectors:

sage: sr = mq.SR(10, 4, 4, 8, star=True, allow_zero_inversions=True)
sage: k = sr.base_ring()
sage: plaintext = sr.state_array([k.fetch_int(e) for e in range(16)])
sage: key = sr.state_array([k.fetch_int(e) for e in range(16)])
sage: print sr.hex_str_matrix( sr(plaintext, key) )
0A 41 F1 C6 
94 6E C3 53 
0B F0 94 EA 
B5 45 58 5A

Brian Gladman's development vectors (dev_vec.txt):

sage: sr = mq.SR(10, 4, 4, 8, star=True, allow_zero_inversions=True, aes_mode=True)
sage: k = sr.base_ring()
sage: plain = '3243f6a8885a308d313198a2e0370734'
sage: key = '2b7e151628aed2a6abf7158809cf4f3c'
sage: set_verbose(2)
sage: cipher = sr(plain, key)
R[01].start   193DE3BEA0F4E22B9AC68D2AE9F84808
R[01].s_box   D42711AEE0BF98F1B8B45DE51E415230
R[01].s_row   D4BF5D30E0B452AEB84111F11E2798E5
R[01].m_col   046681E5E0CB199A48F8D37A2806264C
R[01].k_sch   A0FAFE1788542CB123A339392A6C7605
R[02].start   A49C7FF2689F352B6B5BEA43026A5049
R[02].s_box   49DED28945DB96F17F39871A7702533B
R[02].s_row   49DB873B453953897F02D2F177DE961A
R[02].m_col   584DCAF11B4B5AACDBE7CAA81B6BB0E5
R[02].k_sch   F2C295F27A96B9435935807A7359F67F
R[03].start   AA8F5F0361DDE3EF82D24AD26832469A
R[03].s_box   AC73CF7BEFC111DF13B5D6B545235AB8
R[03].s_row   ACC1D6B8EFB55A7B1323CFDF457311B5
R[03].m_col   75EC0993200B633353C0CF7CBB25D0DC
R[03].k_sch   3D80477D4716FE3E1E237E446D7A883B
R[04].start   486C4EEE671D9D0D4DE3B138D65F58E7
R[04].s_box   52502F2885A45ED7E311C807F6CF6A94
R[04].s_row   52A4C89485116A28E3CF2FD7F6505E07
R[04].m_col   0FD6DAA9603138BF6FC0106B5EB31301
R[04].k_sch   EF44A541A8525B7FB671253BDB0BAD00
R[05].start   E0927FE8C86363C0D9B1355085B8BE01
R[05].s_box   E14FD29BE8FBFBBA35C89653976CAE7C
R[05].s_row   E1FB967CE8C8AE9B356CD2BA974FFB53
R[05].m_col   25D1A9ADBD11D168B63A338E4C4CC0B0
R[05].k_sch   D4D1C6F87C839D87CAF2B8BC11F915BC
R[06].start   F1006F55C1924CEF7CC88B325DB5D50C
R[06].s_box   A163A8FC784F29DF10E83D234CD503FE
R[06].s_row   A14F3DFE78E803FC10D5A8DF4C632923
R[06].m_col   4B868D6D2C4A8980339DF4E837D218D8
R[06].k_sch   6D88A37A110B3EFDDBF98641CA0093FD
R[07].start   260E2E173D41B77DE86472A9FDD28B25
R[07].s_box   F7AB31F02783A9FF9B4340D354B53D3F
R[07].s_row   F783403F27433DF09BB531FF54ABA9D3
R[07].m_col   1415B5BF461615EC274656D7342AD843
R[07].k_sch   4E54F70E5F5FC9F384A64FB24EA6DC4F
R[08].start   5A4142B11949DC1FA3E019657A8C040C
R[08].s_box   BE832CC8D43B86C00AE1D44DDA64F2FE
R[08].s_row   BE3BD4FED4E1F2C80A642CC0DA83864D
R[08].m_col   00512FD1B1C889FF54766DCDFA1B99EA
R[08].k_sch   EAD27321B58DBAD2312BF5607F8D292F
R[09].start   EA835CF00445332D655D98AD8596B0C5
R[09].s_box   87EC4A8CF26EC3D84D4C46959790E7A6
R[09].s_row   876E46A6F24CE78C4D904AD897ECC395
R[09].m_col   473794ED40D4E4A5A3703AA64C9F42BC
R[09].k_sch   AC7766F319FADC2128D12941575C006E
R[10].s_box   E9098972CB31075F3D327D94AF2E2CB5
R[10].s_row   E9317DB5CB322C723D2E895FAF090794
R[10].k_sch   D014F9A8C9EE2589E13F0CC8B6630CA6
R[10].output  3925841D02DC09FBDC118597196A0B32
sage: set_verbose(0)

__cmp__( self, other)

Two generators are considered equal if they agree on all parameters passed to them during construction.

sage: sr1 = mq.SR(2, 2, 2, 4)
sage: sr2 = mq.SR(2, 2, 2, 4)
sage: sr1 == sr2
True

sage: sr1 = mq.SR(2, 2, 2, 4)
sage: sr2 = mq.SR(2, 2, 2, 4, gf2=True)
sage: sr1 == sr2
False

_insert_matrix_into_matrix( self, dst, src, row, col)

Insert matrix src into matrix dst starting at row and col.

Input:

dst
- a matrix
src
- a matrix
row
- offset row
col
- offset columns

sage: sr = mq.SR(10, 4, 4, 4)
sage: a = sr.k.gen()
sage: A = sr.state_array() + 1; A
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
sage: B = Matrix(sr.base_ring(), 2, 2, [0, a, a+1, a^2]); B
[    0     a]
[a + 1   a^2]
sage: sr._insert_matrix_into_matrix(A, B, 1, 1)
[    1     0     0     0]
[    0     0     a     0]
[    0 a + 1   a^2     0]
[    0     0     0     1]

_repr_( self)

sage: sr = mq.SR(1, 2, 2, 4); sr #indirect doctest
SR(1,2,2,4)
sage: sr = mq.SR(1, 2, 2, 4, star=True); sr
SR*(1,2,2,4)

Class: SR_gf2

class SR_gf2
SR_gf2( self, [n=1], [r=1], [c=1], [e=4], [star=False])

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

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

Functions: antiphi,$ \,$ field_polynomials,$ \,$ inversion_polynomials,$ \,$ inversion_polynomials_single_sbox,$ \,$ is_vector,$ \,$ lin_matrix,$ \,$ mix_columns_matrix,$ \,$ phi,$ \,$ shift_rows_matrix,$ \,$ vector

antiphi( self, l)

Inverse of self.phi.

Input:

l
- a vector in the sense of self.is_vector

sage: sr = mq.SR(gf2=True)
sage: A = sr.random_state_array()
sage: A
[a^3 + a + 1]
sage: sr.antiphi(sr.phi(A)) == A
True

field_polynomials( self, name, i, [l=None])

Return list of field polynomials for a given round - given by its number $ i$ - and name.

Input:

name
- variable name
i
- round number
l
- length of variable list (default:None => r*c)

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( self, 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

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

inversion_polynomials_single_sbox( self, [x=None], [w=None], [biaffine_only=None], [correct_only=None])

Generator for S-Box inversion polynomials of a single sbox.

Input:

x
- output variables (default: None)
w
- input variables (default: None)
biaffine_only
- only include biaffine polynomials (default: object default)
correct_only
- only include correct polynomials (default: object default)

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

is_vector( self, 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

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( self, [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)

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

Return the MixColumns matrix.

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( self, l, [diffusion_matrix=False])

Given a list/matrix of elements in $ \GF (2^n)$ 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).

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)
[0 0]
[0 0]
[1 0]
[0 0]

shift_rows_matrix( self)

Return the ShiftRows matrix.

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( self, [d=None])

Constructs a vector suitable for the algebraic representation of SR.

Input:

d
- values for vector(default:None)

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]

Special Functions: __init__,$ \,$ _mul_matrix,$ \,$ _square_matrix

_mul_matrix( self, x)

Given an element $ x$ in self.base_ring() return a matrix which performs the same operation on a when interpreted over $ GF(2)^e$ as $ x$ over $ GF(2^e)$ .

Input:

x
- an element in self.base_ring()

sage: sr = mq.SR(gf2=True)
sage: a = sr.k.gen()
sage: A = sr._mul_matrix(a^2+1)
sage: sr.antiphi( A *  sr.vector([a+1]) ) 
[a^3 + a^2 + a + 1]

sage: (a^2 + 1)*(a+1)
a^3 + a^2 + a + 1

_square_matrix( self)

Return a matrix of dimension self.e x self.e which performs the squaring operation over $ \GF (2^n)$ on vectors of length e.

sage: sr = mq.SR(gf2=True)
sage: a = sr.k.gen()
sage: S = sr._square_matrix()
sage: sr.antiphi( S *  sr.vector([a^3+1]) ) 
[a^3 + a^2 + 1]

sage: (a^3 + 1)^2
a^3 + a^2 + 1

Class: SR_gf2n

class SR_gf2n
Small Scale Variants of the AES polynomial system constructor over $ \GF (2^n)$ .

Functions: antiphi,$ \,$ field_polynomials,$ \,$ inversion_polynomials,$ \,$ is_vector,$ \,$ lin_matrix,$ \,$ mix_columns_matrix,$ \,$ phi,$ \,$ shift_rows_matrix,$ \,$ vector

antiphi( self, l)

Inverse of self.phi.

Input:

l
- a vector in the sense of self.is_vector

sage: sr = mq.SR()
sage: A = sr.random_state_array()
sage: A
[a^3 + a + 1]
sage: sr.antiphi(sr.phi(A)) == A
True

field_polynomials( self, name, i, [l=None])

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

Input:

name
- variable name
i
- round number
l
- r*c (default:None)

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( self, 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

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( self, d)

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

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( self, [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)

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

Return the MixColumns matrix.

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( self, l)

Projects state arrays to their algebraic representation.

Input:

l
- element to perform phi on.

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

Return the ShiftRows matrix.

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( self, [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)

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]

See About this document... for information on suggesting changes.