Rijndael-GF#
Rijndael-GF is an algebraic implementation of the AES cipher which seeks to provide a fully generalized algebraic representation of both the whole AES cipher as well as its individual components.
This class is an algebraic implementation of the Rijndael-GF extension of the
AES cipher, as described in [DR2002]. The AES cipher itself is defined to
operate on a state in \((\GF{2})^{8 n_t}\) where
\(n_t \in \{16, 20, 24, 28, 32\}\). Rijndael-GF is a generalization of AES which
allows for operations in \((\GF{2^8})^{n_t}\), enabling more algebraically
sophisticated study of AES and its variants. This implementation of
Rijndael-GF is suitable for learning purposes, for comparison to other
algebraic ciphers, and for studying various techniques of algebraic
cryptanalysis of AES. This cipher is different from
Mini-AES
, which is a
teaching tool for beginners to understand the basic structure of AES.
An algebraic implementation of Rijndael-GF is achieved by recognizing that
for each round component function \(\phi\) of AES (SubBytes, ShiftRows, etc.)
operating on state matrices, every entry of the output matrix \(B = \phi(A)\) is
representable as a polynomial with variables being the entries of the input
state matrix \(A\). Correspondingly, this implementation of Rijndael-GF provides
a RijndaelGF.Round_Component_Poly_Constr
class which allows for creation
of these such polynomials. For each round component function \(\phi\) of
Rijndael-GF there exists a Round_Component_Poly_Constr
object with a
__call__
method of the form __call__(i, j)
which returns a polynomial
representing \(\phi(A)_{i,j}\) in terms of the entries of \(A\).
There additionally are various methods provided which allow for easy polynomial
evaluation and for simple creation of Round_Component_Poly_Constr
objects
representing more complex aspects of the cipher.
This approach to implementing Rijndael-GF bears some similarity to the
multivariate quadratic (MQ) systems utilized in SR
,
in that the MQ systems also seek to describe the AES cipher as a system of
algebraic equations. Despite this initial similarity though, Rijndael-GF and
SR
are quite different as this implementation
seeks to provide a fully generalized algebraic representation of both the
whole AES cipher as well as its individual components, while
SR
is instead 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.
AUTHORS:
Thomas Gagne (2015-06): initial version
EXAMPLES:
We build Rijndael-GF with a block length of 4 and a key length of 6:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF
sage: rgf = RijndaelGF(4, 6)
We can encrypt plaintexts and decrypt and ciphertexts by calling the
encrypt
and decrypt
methods or by calling the Rijndael-GF object
explicitly. Note that the default input format is a hex string.
sage: plaintext = '00112233445566778899aabbccddeeff'
sage: key = '000102030405060708090a0b0c0d0e0f1011121314151617'
sage: rgf.encrypt(plaintext, key)
'dda97ca4864cdfe06eaf70a0ec0d7191'
sage: rgf.decrypt('dda97ca4864cdfe06eaf70a0ec0d7191', key)
'00112233445566778899aabbccddeeff'
We can also use binary strings as input and output.
sage: plain = '11101011100111110000000111001100' * 4
sage: key = '01100010111101101000110010111010' * 6
sage: ciphertext = rgf(plain, key, format='binary')
sage: ciphertext
'11010011000010011010110001000011101110110100110100110010011011111100011011100111110011100111010011001110110100011100000011111011'
sage: rgf(ciphertext, key, algorithm='decrypt', format='binary') == plain
True
[DR2002] demonstrates an example of encryption which takes the plaintext ‘3243f6a8885a308d313198a2e0370734’ and the key ‘2b7e151628aed2a6abf7158809cf4f3c’ and returns the ciphertext ‘3902dc1925dc116a8409850b1dfb9732’. We can use this example to demonstrate the correctness of this implementation:
sage: rgf = RijndaelGF(4, 4) # change dimensions for this example
sage: plain = '3243f6a8885a308d313198a2e0370734'
sage: key = '2b7e151628aed2a6abf7158809cf4f3c'
sage: expected_ciphertext = '3925841d02dc09fbdc118597196a0b32'
sage: rgf.encrypt(plain, key) == expected_ciphertext
True
sage: rgf = RijndaelGF(4, 6) # revert to previous dimensions
To build polynomials representing entries of the output matrix \(B = \phi(A)\)
for any round component function \(\phi\), each of the round component functions
(SubBytes, ShiftRows, and MixColumns) have a Round_Component_Poly_Constr
object associated with it for building polynomials. These objects can be
accessed by calling their getter functions: rgf.sub_bytes_poly()
,
rgf.shift_rows_poly()
, and rgf.mix_columns_poly()
. Each returned
object has a __call__
method which takes an index i,j
and an
algorithm
flag (‘encrypt’ or ‘decrypt’) and returns a polynomial
representing \(\phi(A)_{i,j}\) in terms of the entries of \(A\), where \(A\) is an
arbitrary state matrix and \(\phi\) is the round component function associated
with that particular Round_Component_Poly_Constr
object. Some of these
objects’ __call__
methods also have additional keywords to modify their
behavior, and so we describe the usage of each object below.
rgf.shift_rows_poly()
and rgf.mix_columns_poly()
do not have any
additional keywords for their __call__
methods and we can call them as
such:
sage: sr_pc = rgf.shift_rows_poly_constr()
sage: sr_pc(1, 2)
a13
sage: sr_pc(2, 3, algorithm='decrypt')
a21
sage: mc_pc = rgf.mix_columns_poly_constr()
sage: mc_pc(1, 2)
a02 + x*a12 + (x + 1)*a22 + a32
sage: mc_pc(2, 3, algorithm='decrypt')
(x^3 + x^2 + 1)*a03 + (x^3 + 1)*a13 + (x^3 + x^2 + x)*a23 + (x^3 + x + 1)*a33
rgf.sub_bytes_poly()
has a single keyword no_inversion=False
, which
when set to True
returns only the affine transformation step of SubBytes.
Below describes the usage of rgf.sub_bytes_poly()
sage: sb_pc = rgf.sub_bytes_poly_constr()
sage: sb_pc(1, 2)
(x^2 + 1)*a12^254 +
(x^3 + 1)*a12^253 +
(x^7 + x^6 + x^5 + x^4 + x^3 + 1)*a12^251 +
(x^5 + x^2 + 1)*a12^247 +
(x^7 + x^6 + x^5 + x^4 + x^2)*a12^239 +
a12^223 +
(x^7 + x^5 + x^4 + x^2 + 1)*a12^191 +
(x^7 + x^3 + x^2 + x + 1)*a12^127 +
(x^6 + x^5 + x + 1)
sage: sb_pc(2, 3, no_inversion=True)
(x^7 + x^3 + x^2 + x + 1)*a23^128 +
(x^7 + x^5 + x^4 + x^2 + 1)*a23^64 +
a23^32 +
(x^7 + x^6 + x^5 + x^4 + x^2)*a23^16 +
(x^5 + x^2 + 1)*a23^8 +
(x^7 + x^6 + x^5 + x^4 + x^3 + 1)*a23^4 +
(x^3 + 1)*a23^2 +
(x^2 + 1)*a23 +
(x^6 + x^5 + x + 1)
Because of the order of the affine transformation and the inversion step in
SubBytes, calling rgf.sub_bytes_poly()(i, j, algorithm='decrypt')
results
in a polynomial with thousands of terms which takes a very long time to
compute. Hence, when using the decryption version of rgf.sub_bytes_poly()
with the intention of evaluating the polynomials it constructs, it is
recommended to first call rgf.sub_bytes_poly()(i, j, algorithm='decrypt',
no_inversion=True)
to get a polynomial representing only the inverse affine
transformation, evaluate this polynomial for a particular input block, then
finally perform the inversion step after the affine transformation polynomial
has been evaluated.
sage: inv_affine = sb_pc(1, 2, algorithm='decrypt', no_inversion=True)
sage: state = rgf._hex_to_GF('ff87968431d86a51645151fa773ad009')
sage: evaluated = inv_affine(state.list())
sage: result = evaluated * -1
sage: rgf._GF_to_hex(result)
'79'
We can see how the variables of these polynomials are organized in \(A\):
sage: rgf.state_vrs
[a00 a01 a02 a03]
[a10 a11 a12 a13]
[a20 a21 a22 a23]
[a30 a31 a32 a33]
The final Round_Component_Poly_Constr
object we have not discussed yet is
add_round_key_poly
, which corresponds to the AddRoundKey round component
function. This object differs from the other Round_Component_Poly_Constr
objects in that it returns polynomials with variables being entries of an
input state \(A\) as well as entries of various subkeys. Since there are \(N_r\)
subkeys to choose from, add_round_key_poly
has a keyword of round=0
to
select which subkey to use variables from.
sage: ark_pc = rgf.add_round_key_poly_constr()
sage: ark_pc(1, 2)
a12 + k012
sage: ark_pc(1, 2, algorithm='decrypt')
a12 + k012
sage: ark_pc(2, 3, round=7)
a23 + k723
We can see how key variables are organized in the original key (the key used to build the rest of the subkeys) below. Note that because key variables are subkey entries, if the key length is longer than the block length we will have entries from multiple subkeys in the original key matrix.
sage: rgf.key_vrs
[k000 k001 k002 k003 k100 k101]
[k010 k011 k012 k013 k110 k111]
[k020 k021 k022 k023 k120 k121]
[k030 k031 k032 k033 k130 k131]
We can evaluate any of these constructed polynomials for a particular input state (in essence, calculate \(\phi(A)_{i,j}\)) as such:
sage: rgf = RijndaelGF(4, 6)
sage: state = rgf._hex_to_GF('fe7b5170fe7c8e93477f7e4bf6b98071')
sage: poly = mc_pc(3, 2, algorithm='decrypt')
sage: poly(state.list())
x^7 + x^6 + x^5 + x^2 + x
We can use the apply_poly
method to build a matrix whose \(i,j\) th
entry equals the polynomial phi_poly(i, j)
evaluated for a particular input
state, where phi_poly
is the Round_Component_Poly_Constr
object
associated with the round component function \(\phi\). Essentially,
apply_poly
calculates \(\phi(A)\), where \(A\) is our input state.
Calling apply_poly
is equivalent to applying the round component function
associated this Round_Component_Poly_Constr
object to \(A\).
sage: state = rgf._hex_to_GF('c4cedcabe694694e4b23bfdd6fb522fa')
sage: result = rgf.apply_poly(state, rgf.sub_bytes_poly_constr())
sage: rgf._GF_to_hex(result)
'1c8b86628e22f92fb32608c1a8d5932d'
sage: result == rgf.sub_bytes(state)
True
Alternatively, we can pass a matrix of polynomials as input to apply_poly
,
which will then return another matrix of polynomials. For example,
rgf.state_vrs
can be used as input to make each i,j
th entry of the
output matrix equal phi_poly_constr(i, j)
, where phi_poly_constr
is
our inputted Round_Component_Poly_Constr
object. This matrix can then be
passed through again and so on, demonstrating how one could potentially build
a matrix of polynomials representing the entire cipher.
sage: state = rgf.apply_poly(rgf.state_vrs, rgf.shift_rows_poly_constr())
sage: state
[a00 a01 a02 a03]
[a11 a12 a13 a10]
[a22 a23 a20 a21]
[a33 a30 a31 a32]
sage: rgf.apply_poly(state, rgf.add_round_key_poly_constr())
[a00 + k000 a01 + k001 a02 + k002 a03 + k003]
[a11 + k010 a12 + k011 a13 + k012 a10 + k013]
[a22 + k020 a23 + k021 a20 + k022 a21 + k023]
[a33 + k030 a30 + k031 a31 + k032 a32 + k033]
For any of these Round_Component_Poly_Constr
objects, we can change the
keywords of its __call__
method when apply_poly
invokes it by passing
apply_poly
a dictionary mapping keywords to their values.
sage: rgf.apply_poly(rgf.state_vrs, rgf.add_round_key_poly_constr(),
....: poly_constr_attr={'round': 5})
[a00 + k500 a01 + k501 a02 + k502 a03 + k503]
[a10 + k510 a11 + k511 a12 + k512 a13 + k513]
[a20 + k520 a21 + k521 a22 + k522 a23 + k523]
[a30 + k530 a31 + k531 a32 + k532 a33 + k533]
We can build our own Round_Component_Poly_Constr
objects which correspond
to the composition of multiple round component functions with the compose
method. To do this, if we pass two Round_Component_Poly_Constr
objects
to compose
where the first object corresponds to the round component
function \(f\) and the second to the round component function \(g\), compose
will return a new Round_Component_Poly_Constr
object corresponding to the
function \(g \circ f\). This returned Round_Component_Poly_Constr
object
will have the arguments of __call__(row, col, algorithm='encrypt')
and
when passed an index i,j
will return \(g(f(A))_{i,j}\) in terms of the
entries of \(A\).
sage: # needs sage.libs.gap
sage: rcpc = rgf.compose(rgf.shift_rows_poly_constr(),
....: rgf.mix_columns_poly_constr()); rcpc
A polynomial constructor of a round component of Rijndael-GF block cipher
with block length 4, key length 6, and 12 rounds.
sage: rcpc(2, 1)
a01 + a12 + x*a23 + (x + 1)*a30
sage: state = rgf._hex_to_GF('afb73eeb1cd1b85162280f27fb20d585')
sage: result = rgf.apply_poly(state, rcpc)
sage: new_state = rgf.shift_rows(state)
sage: new_state = rgf.mix_columns(new_state)
sage: result == new_state
True
sage: rcpc = rgf.compose(rgf.mix_columns_poly_constr(),
....: rgf.shift_rows_poly_constr())
sage: result = rgf.apply_poly(state, rcpc, algorithm='decrypt')
sage: new_state = rgf.mix_columns(state, algorithm='decrypt')
sage: new_state = rgf.shift_rows(new_state, algorithm='decrypt')
sage: new_state == result
True
Alternatively, we can use compose
to build the polynomial output of
a Round_Component_Poly_Constr
object corresponding to the composition of
multiple round functions like above without having to explicitly build our
own Round_Component_Poly_Constr
object. To do this, we simply make the
first input a Round_Component_Poly_Constr
object corresponding to a
round component function \(f\) and make the second input a polynomial
representing \(g(A)_{i,j}\) for a round component function \(g\). Given this,
compose
will return a polynomial representing \(g(f(A))_{i,j}\) in terms
of the entries of \(A\).
sage: poly = rgf.mix_columns_poly_constr()(0, 3); poly
x*a03 + (x + 1)*a13 + a23 + a33
sage: rgf.compose(rgf.sub_bytes_poly_constr(), poly)
(x^3 + x)*a03^254 +
(x^3 + x^2 + x + 1)*a13^254 +
(x^2 + 1)*a23^254 +
(x^2 + 1)*a33^254 +
(x^4 + x)*a03^253 +
(x^4 + x^3 + x + 1)*a13^253 +
(x^3 + 1)*a23^253 +
(x^3 + 1)*a33^253 +
(x^7 + x^6 + x^5 + x^3 + 1)*a03^251 +
(x^4)*a13^251 +
(x^7 + x^6 + x^5 + x^4 + x^3 + 1)*a23^251 +
(x^7 + x^6 + x^5 + x^4 + x^3 + 1)*a33^251 +
(x^6 + x^3 + x)*a03^247 +
(x^6 + x^5 + x^3 + x^2 + x + 1)*a13^247 +
(x^5 + x^2 + 1)*a23^247 +
(x^5 + x^2 + 1)*a33^247 +
(x^7 + x^6 + x^5 + x^4 + x + 1)*a03^239 +
(x^2 + x + 1)*a13^239 +
(x^7 + x^6 + x^5 + x^4 + x^2)*a23^239 +
(x^7 + x^6 + x^5 + x^4 + x^2)*a33^239 +
x*a03^223 +
(x + 1)*a13^223 +
a23^223 +
a33^223 +
(x^6 + x^5 + x^4 + 1)*a03^191 +
(x^7 + x^6 + x^2)*a13^191 +
(x^7 + x^5 + x^4 + x^2 + 1)*a23^191 +
(x^7 + x^5 + x^4 + x^2 + 1)*a33^191 +
(x^2 + 1)*a03^127 +
(x^7 + x^3 + x)*a13^127 +
(x^7 + x^3 + x^2 + x + 1)*a23^127 +
(x^7 + x^3 + x^2 + x + 1)*a33^127 +
(x^6 + x^5 + x + 1)
If we use algorithm='decrypt'
as an argument to compose
, then the
value of algorithm
will be passed directly to the first argument of
compose
(a Round_Component_Poly_Constr
object) when it is called,
provided the second argument is a polynomial. Setting this flag does nothing
if both arguments are Round_Component_Poly_Constr
objects, since the
returned Round_Component_Poly_Constr
object’s __call__
method must have
its own algorithm
keyword defaulted to ‘encrypt’.
sage: # needs sage.libs.gap
sage: poly = rgf.shift_rows_poly_constr()(2, 1)
sage: rgf.compose(rgf.mix_columns_poly_constr(), poly, algorithm='decrypt')
(x^3 + x^2 + 1)*a03 + (x^3 + 1)*a13 + (x^3 + x^2 + x)*a23 + (x^3 + x + 1)*a33
sage: state = rgf._hex_to_GF('80121e0776fd1d8a8d8c31bc965d1fee')
sage: with_decrypt = rgf.compose(rgf.sub_bytes_poly_constr(),
....: rgf.shift_rows_poly_constr(),
....: algorithm='decrypt')
sage: result_wd = rgf.apply_poly(state, with_decrypt)
sage: no_decrypt = rgf.compose(rgf.sub_bytes_poly_constr(),
....: rgf.shift_rows_poly_constr())
sage: result_nd = rgf.apply_poly(state, no_decrypt)
sage: result_wd == result_nd
True
We can also pass keyword dictionaries of f_attr
and g_attr
to
compose
to make f
and g
use those keywords during polynomial
creation.
sage: rcpc = rgf.compose(rgf.add_round_key_poly_constr(), # needs sage.libs.gap
....: rgf.add_round_key_poly_constr(),
....: f_attr={'round': 4}, g_attr={'round': 7})
sage: rcpc(1, 2) # needs sage.libs.gap
a12 + k412 + k712
In addition to building polynomial representations of state matrices, we can
also build polynomial representations of elements of the expanded key with the
expand_key_poly
method. However, since the key schedule is defined
recursively, it is impossible to build polynomials for the key schedule in
the same manner as we do for the round component functions. Consequently,
expand_round_key_poly()
is not a Round_Component_Poly_Constr
object.
Instead, expand_key_poly
is a method which takes an index i,j
and a
round number round
, and returns a polynomial representing the \(i,j\) th
entry of the round
th round key. This polynomial’s variables are entries
of the original key we built above.
sage: rgf.expand_key_poly(1, 2, 0)
k012
sage: rgf.expand_key_poly(1, 1, 1)
k111
sage: rgf.expand_key_poly(1, 2, 1)
(x^2 + 1)*k121^254 +
(x^3 + 1)*k121^253 +
(x^7 + x^6 + x^5 + x^4 + x^3 + 1)*k121^251 +
(x^5 + x^2 + 1)*k121^247 +
(x^7 + x^6 + x^5 + x^4 + x^2)*k121^239 +
k121^223 +
(x^7 + x^5 + x^4 + x^2 + 1)*k121^191 +
(x^7 + x^3 + x^2 + x + 1)*k121^127 +
k010 +
(x^6 + x^5 + x)
Since expand_key_poly
is not actually a
Round_Component_Poly_Constr
object, we cannot use it as input to
apply_poly
or compose
.
sage: rgf.apply_poly(state, rgf.expand_key_poly)
Traceback (most recent call last):
...
TypeError: keyword 'poly_constr' must be a Round_Component_Poly_Constr
sage: rgf.compose(rgf.expand_key_poly, rgf.sub_bytes_poly_constr())
Traceback (most recent call last):
...
TypeError: keyword 'f' must be a Round_Component_Poly_Constr
- class sage.crypto.mq.rijndael_gf.RijndaelGF(Nb, Nk, state_chr='a', key_chr='k')#
Bases:
SageObject
An algebraically generalized version of the AES cipher.
INPUT:
Nb
– The block length of this instantiation. Must be between 4 and 8.Nk
– The key length of this instantiation. Must be between 4 and 8.state_chr
– The variable name for polynomials representing elements from state matrices.key_chr
– The variable name for polynomials representing elements of the key schedule.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(6, 8) sage: rgf Rijndael-GF block cipher with block length 6, key length 8, and 14 rounds.
By changing
state_chr
we can alter the names of variables in polynomials representing elements from state matrices.sage: rgf = RijndaelGF(4, 6, state_chr='myChr') sage: rgf.mix_columns_poly_constr()(3, 2) (x + 1)*myChr02 + myChr12 + myChr22 + x*myChr32
We can also alter the name of variables in polynomials representing elements from round keys by changing
key_chr
.sage: rgf = RijndaelGF(4, 6, key_chr='myKeyChr') sage: rgf.expand_key_poly(1, 2, 1) (x^2 + 1)*myKeyChr121^254 + (x^3 + 1)*myKeyChr121^253 + (x^7 + x^6 + x^5 + x^4 + x^3 + 1)*myKeyChr121^251 + (x^5 + x^2 + 1)*myKeyChr121^247 + (x^7 + x^6 + x^5 + x^4 + x^2)*myKeyChr121^239 + myKeyChr121^223 + (x^7 + x^5 + x^4 + x^2 + 1)*myKeyChr121^191 + (x^7 + x^3 + x^2 + x + 1)*myKeyChr121^127 + myKeyChr010 + (x^6 + x^5 + x)
- class Round_Component_Poly_Constr(polynomial_constr, rgf, round_component_name=None)#
Bases:
SageObject
An object which constructs polynomials representing round component functions of a RijndaelGF object.
INPUT:
polynomial_constr
– A function which takes an indexrow,col
and returns a polynomial representing therow,col
th entry of a matrix after a specific round component function has been applied to it. This polynomial must be in terms of entries of the input matrix to that round component function and of entries of various subkeys.polynomial_constr
must have arguments of the formpolynomial_constr(row, col, algorithm='encrypt', **kwargs)
and must be able to be called aspolynomial_constr(row, col)
.rgf
– The RijndaelGF object whose state entries are represented by polynomials returned frompolynomial_constr
.round_component_name
– The name of the round component function this object corresponds to as a string. Used solely for display purposes.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: rcpc = RijndaelGF.Round_Component_Poly_Constr( ....: rgf._shift_rows_pc, rgf, "Shift Rows") sage: rcpc A polynomial constructor for the function 'Shift Rows' of Rijndael-GF block cipher with block length 4, key length 4, and 10 rounds.
If \(\phi\) is the round component function to which this object corresponds to, then
__call__(i,j)
\(= \phi(A)_{i,j}\), where \(A\) is an arbitrary input matrix. Note that the polynomial returned by__call__(i,j)
will be in terms of the entries of \(A\).sage: rcpc = RijndaelGF.Round_Component_Poly_Constr( ....: rgf._mix_columns_pc, rgf, "Mix Columns") sage: poly = rcpc(1, 2); poly a02 + x*a12 + (x + 1)*a22 + a32 sage: state = rgf._hex_to_GF('d1876c0f79c4300ab45594add66ff41f') sage: result = rgf.mix_columns(state) sage: result[1,2] == poly(state.list()) True
Invoking this objects
__call__
method passes its arguments directly topolynomial_constr
and returns the result. In a sense,Round_Component_Poly_Constr
acts as a wrapper for thepolynomial_constr
method and helps ensure that eachRound_Component_Poly_Constr
object will act similarly.sage: all(rgf._mix_columns_pc(i, j) == rcpc(i, j) ....: for i in range(4) for j in range(4)) True
Since all keyword arguments of
polynomial_constr
must have a default value except forrow
andcol
, we can always call aRound_Component_Poly_Constr
object by__call__(row, col)
. Because of this, methods such asapply_poly
andcompose
will only call__call__(row, col)
when passed aRound_Component_Poly_Constr
object. In order to change this object’s behavior and force methods such asapply_poly
to use non-default values for keywords we can pass dictionaries mapping keywords to non-default values as input toapply_poly
andcompose
.sage: rgf.apply_poly(rgf.state_vrs, ....: rgf.add_round_key_poly_constr(), ....: poly_constr_attr={'round': 9}) [a00 + k900 a01 + k901 a02 + k902 a03 + k903] [a10 + k910 a11 + k911 a12 + k912 a13 + k913] [a20 + k920 a21 + k921 a22 + k922 a23 + k923] [a30 + k930 a31 + k931 a32 + k932 a33 + k933]
sage: fn = rgf.compose(rgf.add_round_key_poly_constr(), # needs sage.libs.gap ....: rgf.add_round_key_poly_constr(), ....: f_attr={'round': 3}, g_attr={'round': 7}) sage: fn(2, 3) # needs sage.libs.gap a23 + k323 + k723
Because all
Round_Component_Poly_Constr
objects are callable as__call__(row, col, algorithm)
,__call__
will check the validity of these three arguments automatically. Any other keywords, however, must be checked inpolynomial_constr
.sage: def my_poly_constr(row, col, algorithm='encrypt'): ....: return x * rgf._F.one() # example body with no checks sage: rcpc = RijndaelGF.Round_Component_Poly_Constr( ....: my_poly_constr, rgf, "My Poly Constr") sage: rcpc(-1, 2) Traceback (most recent call last): ... ValueError: keyword 'row' must be in range 0 - 3 sage: rcpc(1, 2, algorithm=5) Traceback (most recent call last): ... ValueError: keyword 'algorithm' must be either 'encrypt' or 'decrypt'
- add_round_key(state, round_key)#
Return the round-key addition of matrices
state
andround_key
.INPUT:
state
– The state matrix to haveround_key
added to.round_key
– The round key to add tostate
.
OUTPUT:
A state matrix which is the round key addition of
state
andround_key
. This transformation is simply the entrywise addition of these two matrices.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: state = rgf._hex_to_GF('36339d50f9b539269f2c092dc4406d23') sage: key = rgf._hex_to_GF('7CC78D0E22754E667E24573F454A6531') sage: key_schedule = rgf.expand_key(key) sage: result = rgf.add_round_key(state, key_schedule[0]) sage: rgf._GF_to_hex(result) '4af4105edbc07740e1085e12810a0812'
- add_round_key_poly_constr()#
Return the
Round_Component_Poly_Constr
object corresponding to AddRoundKey.EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: ark_pc = rgf.add_round_key_poly_constr() sage: ark_pc A polynomial constructor for the function 'Add Round Key' of Rijndael-GF block cipher with block length 4, key length 4, and 10 rounds. sage: ark_pc(0, 1) a01 + k001
When invoking the returned object’s
__call__
method, changing the value ofalgorithm='encrypt'
does nothing, since the AddRoundKey round component function is its own inverse.sage: with_encrypt = ark_pc(1, 1, algorithm='encrypt') sage: with_decrypt = ark_pc(1, 1, algorithm='decrypt') sage: with_encrypt == with_decrypt True
When invoking the returned object’s
__call__
method, one can change the round subkey used in the returned polynomial by changing theround=0
keyword.sage: ark_pc(2, 1, round=7) a21 + k721
When passing the returned object to methods such as
apply_poly
andcompose
, we can make these methods use a non-default value forround=0
by passing in a dictionary mappinground
to a different value.sage: rgf.apply_poly(rgf.state_vrs, ark_pc, ....: poly_constr_attr={'round': 6}) [a00 + k600 a01 + k601 a02 + k602 a03 + k603] [a10 + k610 a11 + k611 a12 + k612 a13 + k613] [a20 + k620 a21 + k621 a22 + k622 a23 + k623] [a30 + k630 a31 + k631 a32 + k632 a33 + k633]
sage: rcpc = rgf.compose(ark_pc, ark_pc, # needs sage.libs.gap ....: f_attr={'round': 3}, g_attr={'round': 5}) sage: rcpc(3, 1) # needs sage.libs.gap a31 + k331 + k531
- apply_poly(state, poly_constr, algorithm='encrypt', keys=None, poly_constr_attr=None)#
Return a state matrix where
poly_method
is applied to each entry.INPUT:
state
– The state matrix over \(\GF{2^8}\) to whichpoly_method
is applied to.poly_constr
– TheRound_Component_Poly_Constr
object to build polynomials during evaluation.algorithm
– (default: “encrypt”) Passed directly torcpc
to select encryption or decryption. The encryption flag is “encrypt” and the decrypt flag is “decrypt”.keys
– (default: None) An array of \(N_r\) subkey matrices to replace any key variables in any polynomials returned bypoly_method
. Must be identical to the format returned byexpand_key
. If any polynomials have key variables andkeys
is not supplied, the key variables will remain as-is.poly_constr_attr
– (default:None) A dictionary of keyword attributes to pass torcpc
when it is called.
OUTPUT:
A state matrix in \(\GF{2^8}\) whose \(i,j\) th entry equals the polynomial
poly_constr(i, j, algorithm, **poly_constr_attr)
evaluated by setting its variables equal to the corresponding entries ofstate
.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: state = rgf._hex_to_GF('3b59cb73fcd90ee05774222dc067fb68') sage: result = rgf.apply_poly(state, rgf.shift_rows_poly_constr()) sage: rgf._GF_to_hex(result) '3bd92268fc74fb735767cbe0c0590e2d'
Calling
apply_poly
with theRound_Component_Poly_Constr
object of a round component (e.g.sub_bytes_poly
) is identical to calling that round component function itself.sage: state = rgf._hex_to_GF('4915598f55e5d7a0daca94fa1f0a63f7') sage: apply_poly_result = rgf.apply_poly(state, ....: rgf.sub_bytes_poly_constr()) sage: direct_result = rgf.sub_bytes(state) sage: direct_result == apply_poly_result True
If the
Round_Component_Poly_Constr
object’s__call__
method returns a polynomial with state variables as well as key variables, we can supply a list of \(N_r\) round keyskeys
whose elements are evaluated as the key variables. If this is not provided, the key variables will remain as is.:sage: state = rgf._hex_to_GF('14f9701ae35fe28c440adf4d4ea9c026') sage: key = rgf._hex_to_GF('54d990a16ba09ab596bbf40ea111702f') sage: keys = rgf.expand_key(key) sage: result = rgf.apply_poly(state, ....: rgf.add_round_key_poly_constr(), ....: keys=keys) sage: result == rgf.add_round_key(state, key) True sage: rgf.apply_poly(state, rgf.add_round_key_poly_constr())[0,0] k000 + (x^4 + x^2)
We can change the value of the keywords of
poly_constr
‘s__call__
method whenapply_poly
calls it by passing in a dictionarypoly_constr_attr
mapping keywords to their values.sage: rgf.apply_poly(rgf.state_vrs, ....: rgf.add_round_key_poly_constr(), ....: poly_constr_attr={'round': 5}) [a00 + k500 a01 + k501 a02 + k502 a03 + k503] [a10 + k510 a11 + k511 a12 + k512 a13 + k513] [a20 + k520 a21 + k521 a22 + k522 a23 + k523] [a30 + k530 a31 + k531 a32 + k532 a33 + k533]
- block_length()#
Return the block length of this instantiation of Rijndael-GF.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 6) sage: rgf.block_length() 4
- compose(f, g, algorithm='encrypt', f_attr=None, g_attr=None)#
Return a
Round_Component_Poly_Constr
object corresponding to \(g \circ f\) or the polynomial output of this object’s__call__
method.INPUT:
f
– ARound_Component_Poly_Constr
object corresponding to a round component function \(f\).g
– ARound_Component_Poly_Constr
object corresponding to a round component function \(g\) or a polynomial output of this object’s__call__
method.algorithm
– (default: “encrypt”) Whetherf
andg
should use their encryption transformations or their decryption transformations. Does nothing ifg
is aRound_Component_Poly_Constr
object. The encryption flag is “encrypt” and the decryption flag is “decrypt”.f_attr
– (default: None) A dictionary of keyword attributes to pass tof
when it is called.g_attr
– (default: None) A dictionary of keyword attributes to pass tog
when it is called. Does nothing ifg
is a polynomial.
OUTPUT:
If
g
is aRound_Component_Poly_Constr
object corresponding to a round component function \(g\), thencompose
returns aRound_Component_Poly_Constr
corresponding to the round component function \(g \circ f\), where \(f\) is the round component function corresponding to the first argumentf
. On the other hand, ifg
\(= g(A)_{i,j}\) for a round component function \(g\), thencompose
returns \(g(f(A))_{i,j}\), where \(A\) is an arbitrary input state matrix.
EXAMPLES:
This function allows us to determine the polynomial representations of entries across multiple round functions. For example, if we wanted a polynomial representing the
1,3
entry of a matrix after we first apply ShiftRows and then MixColumns to that matrix, we do:sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: mcp = rgf.mix_columns_poly_constr()(1, 3); mcp a03 + x*a13 + (x + 1)*a23 + a33 sage: result = rgf.compose(rgf.shift_rows_poly_constr(), mcp) sage: result a03 + x*a10 + (x + 1)*a21 + a32
We can test the correctness of this:
sage: state = rgf._hex_to_GF('fa636a2825b339c940668a3157244d17') sage: new_state = rgf.shift_rows(state) sage: new_state = rgf.mix_columns(new_state) sage: result(state.list()) == new_state[1,3] True
We can also use
compose
to build a newRound_Component_Poly_Constr
object corresponding to the composition of multiple round functions as such:sage: fn = rgf.compose(rgf.shift_rows_poly_constr(), # needs sage.libs.gap ....: rgf.mix_columns_poly_constr()) sage: fn(1, 3) # needs sage.libs.gap a03 + x*a10 + (x + 1)*a21 + a32
If we use
compose
to make a newRound_Component_Poly_Constr
object, we can use that object as input toapply_poly
andcompose
:sage: state = rgf._hex_to_GF('36400926f9336d2d9fb59d23c42c3950') sage: result = rgf.apply_poly(state, fn) # needs sage.libs.gap sage: rgf._GF_to_hex(result) 'f4bcd45432e554d075f1d6c51dd03b3c' sage: new_state = rgf.shift_rows(state) sage: new_state = rgf.mix_columns(new_state) sage: result == new_state True
sage: fn2 = rgf.compose(rgf.sub_bytes_poly_constr(), fn) # needs sage.libs.gap
If the second argument is a polynomial, then the value of
algorithm
is passed directly to the first argument \(f\) during evaluation. However, if the second argument is aRound_Component_Poly_Constr
object, changingalgorithm
does nothing since the returned object has its ownalgorithm='encrypt'
keyword.sage: f = rgf.compose(rgf.sub_bytes_poly_constr(), # needs sage.libs.gap ....: rgf.mix_columns_poly_constr(), ....: algorithm='decrypt') sage: g = rgf.compose(rgf.sub_bytes_poly_constr(), # needs sage.libs.gap ....: rgf.mix_columns_poly_constr()) sage: all(f(i,j) == g(i,j) for i in range(4) for j in range(4)) # needs sage.libs.gap True
We can change the keyword attributes of the
__call__
methods off
andg
by passing dictionariesf_attr
andg_attr
tocompose
.sage: fn = rgf.compose(rgf.add_round_key_poly_constr(), # needs sage.libs.gap ....: rgf.add_round_key_poly_constr(), ....: f_attr={'round': 4}, g_attr={'round': 7}) sage: fn(1, 2) # needs sage.libs.gap a12 + k412 + k712
- decrypt(ciphertext, key, format='hex')#
Return the ciphertext
ciphertext
decrypted with the keykey
.INPUT:
ciphertext
– The ciphertext to be decrypted.key
– The key to decryptciphertext
with.format
– (default:hex
) The string format that bothciphertext
andkey
must be in, either “hex” or “binary”.
OUTPUT:
A string in the format
format
ofciphertext
decrypted with keykey
.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: key = '2dfb02343f6d12dd09337ec75b36e3f0' sage: ciphertext = '54d990a16ba09ab596bbf40ea111702f' sage: expected_plaintext = '1e1d913b7274ad9b5a4ab1a5f9133b93' sage: rgf.decrypt(ciphertext, key) == expected_plaintext True
We can also decrypt messages using binary strings.
sage: key = '00011010000011100011000000111101' * 4 sage: ciphertext = '00110010001110000111110110000001' * 4 sage: expected_plaintext = ('101111111010011100111100101010100111' ....: '1111010000101101100001101000000000000000010000000100111011' ....: '0100001111100011010001101101001011') sage: result = rgf.decrypt(ciphertext, key, format='binary') sage: result == expected_plaintext True
- encrypt(plain, key, format='hex')#
Return the plaintext
plain
encrypted with the keykey
.INPUT:
plain
– The plaintext to be encrypted.key
– The key to encryptplain
with.format
– (default:hex
) The string format ofkey
andplain
, either “hex” or “binary”.
OUTPUT:
A string of the plaintext
plain
encrypted with the keykey
.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: key = 'c81677bc9b7ac93b25027992b0261996' sage: plain = 'fde3bad205e5d0d73547964ef1fe37f1' sage: expected_ciphertext = 'e767290ddfc6414e3c50a444bec081f0' sage: rgf.encrypt(plain, key) == expected_ciphertext True
We can encrypt binary strings as well.
sage: key = '10010111110000011111011011010001' * 4 sage: plain = '00000000101000000000000001111011' * 4 sage: expected_ciphertext = ('11010111100100001010001011110010111' ....: '1110011000000011111100100011011100101000000001000111000010' ....: '00100111011011001000111101111110100') sage: result = rgf.encrypt(plain, key, format='binary') sage: result == expected_ciphertext True
- expand_key(key)#
Return the expanded key schedule from
key
.INPUT:
key
– The key to build a key schedule from. Must be a matrix over \(\GF{2^8}\) of dimensions \(4 \times N_k\).
OUTPUT:
A length \(Nr\) list of \(4 \times N_b\) matrices corresponding to the expanded key. The \(n\) th entry of the list corresponds to the matrix used in the
add_round_key
step of the \(n\) th round.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 6) sage: key = '331D0084B176C3FB59CAA0EDA271B565BB5D9A2D1E4B2892' sage: key_state = rgf._hex_to_GF(key) sage: key_schedule = rgf.expand_key(key_state) sage: rgf._GF_to_hex(key_schedule[0]) '331d0084b176c3fb59caa0eda271b565' sage: rgf._GF_to_hex(key_schedule[6]) '5c5d51c4121f018d0f4f3e408ae9f78c'
- expand_key_poly(row, col, round)#
Return a polynomial representing the
row,col
th entry of theround
th round key.INPUT:
row
– The row position of the element represented by this polynomial.col
– The column position of the element represented by this polynomial.
OUTPUT:
A polynomial representing the
row,col
th entry of theround
th round key in terms of entries of the input key.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: rgf.expand_key_poly(1, 2, 0) k012 sage: rgf.expand_key_poly(1, 2, 1) (x^2 + 1)*k023^254 + (x^3 + 1)*k023^253 + (x^7 + x^6 + x^5 + x^4 + x^3 + 1)*k023^251 + (x^5 + x^2 + 1)*k023^247 + (x^7 + x^6 + x^5 + x^4 + x^2)*k023^239 + k023^223 + (x^7 + x^5 + x^4 + x^2 + 1)*k023^191 + (x^7 + x^3 + x^2 + x + 1)*k023^127 + k010 + k011 + k012 + (x^6 + x^5 + x)
It should be noted that
expand_key_poly
cannot be used withapply_poly
orcompose
, sinceexpand_key_poly
is not aRound_Component_Poly_Constr
object.sage: rgf.compose(rgf.sub_bytes_poly_constr(), rgf.expand_key_poly) Traceback (most recent call last): ... TypeError: keyword 'g' must be a Round_Component_Poly_Constr or a polynomial over Finite Field in x of size 2^8 sage: state = rgf._hex_to_GF('00000000000000000000000000000000') sage: rgf.apply_poly(state, rgf.expand_key_poly) Traceback (most recent call last): ... TypeError: keyword 'poly_constr' must be a Round_Component_Poly_Constr
- key_length()#
Return the key length of this instantiation of Rijndael-GF.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 8) sage: rgf.key_length() 8
- mix_columns(state, algorithm='encrypt')#
Return the application of MixColumns to the state matrix
state
.INPUT:
state
– The state matrix to apply MixColumns to.algorithm
– (default: “encrypt”) Whether to perform the encryption version of MixColumns, or its decryption inverse. The encryption flag is “encrypt” and the decryption flag is “decrypt”.
OUTPUT:
The state matrix over \(\GF{2^8}\) which is the result of applying MixColumns to
state
.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: state = rgf._hex_to_GF('cd54c7283864c0c55d4c727e90c9a465') sage: result = rgf.mix_columns(state) sage: rgf._GF_to_hex(result) '921f748fd96e937d622d7725ba8ba50c' sage: decryption = rgf.mix_columns(result, algorithm='decrypt') sage: decryption == state True
- mix_columns_poly_constr()#
Return a
Round_Component_Poly_Constr
object corresponding to MixColumns.EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: mc_pc = rgf.mix_columns_poly_constr() sage: mc_pc A polynomial constructor for the function 'Mix Columns' of Rijndael-GF block cipher with block length 4, key length 4, and 10 rounds. sage: mc_pc(1, 2) a02 + x*a12 + (x + 1)*a22 + a32 sage: mc_pc(1, 0, algorithm='decrypt') (x^3 + 1)*a00 + (x^3 + x^2 + x)*a10 + (x^3 + x + 1)*a20 + (x^3 + x^2 + 1)*a30
The returned object’s
__call__
method has no additional keywords, unlikesub_bytes_poly_constr()
andadd_round_key_poly_constr()
.
- number_rounds()#
Return the number of rounds used in this instantiation of Rijndael-GF.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(5, 4) sage: rgf.number_rounds() 11
- shift_rows(state, algorithm='encrypt')#
Return the application of ShiftRows to the state matrix
state
.INPUT:
state
– A state matrix over \(\GF{2^8}\) to which ShiftRows is applied to.algorithm
– (default: “encrypt”) Whether to perform the encryption version of ShiftRows or its decryption inverse. The encryption flag is “encrypt” and the decryption flag is “decrypt”.
OUTPUT:
A state matrix over \(\GF{2^8}\) which is the application of ShiftRows to
state
.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: state = rgf._hex_to_GF('adcb0f257e9c63e0bc557e951c15ef01') sage: result = rgf.shift_rows(state) sage: rgf._GF_to_hex(result) 'ad9c7e017e55ef25bc150fe01ccb6395' sage: decryption = rgf.shift_rows(result, algorithm='decrypt') sage: decryption == state True
- shift_rows_poly_constr()#
Return a
Round_Component_Poly_Constr
object corresponding to ShiftRows.EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: sr_pc = rgf.shift_rows_poly_constr() sage: sr_pc(3, 0) a33 sage: sr_pc(2, 1, algorithm='decrypt') a23
The returned object’s
__call__
method has no additional keywords, unlikesub_bytes_poly_constr()
andadd_round_key_poly_constr
.
- sub_bytes(state, algorithm='encrypt')#
Return the application of SubBytes to the state matrix
state
.INPUT:
state
– The state matrix to apply SubBytes to.algorithm
– (default: “encrypt”) Whether to apply the encryption step of SubBytes or its decryption inverse. The encryption flag is “encrypt” and the decryption flag is “decrypt”.
OUTPUT:
The state matrix over \(\GF{2^8}\) where SubBytes has been applied to every entry of
state
.
EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: state = rgf._hex_to_GF('d1c4941f7955f40fb46f6c0ad68730ad') sage: result = rgf.sub_bytes(state) sage: rgf._GF_to_hex(result) '3e1c22c0b6fcbf768da85067f6170495' sage: decryption = rgf.sub_bytes(result, algorithm='decrypt') sage: decryption == state True
- sub_bytes_poly_constr()#
Return the
Round_Component_Poly_Constr
object corresponding to SubBytes.EXAMPLES:
sage: from sage.crypto.mq.rijndael_gf import RijndaelGF sage: rgf = RijndaelGF(4, 4) sage: sb_pc = rgf.sub_bytes_poly_constr(); sb_pc A polynomial constructor for the function 'SubBytes' of Rijndael-GF block cipher with block length 4, key length 4, and 10 rounds. sage: sb_pc(2, 3) (x^2 + 1)*a23^254 + (x^3 + 1)*a23^253 + (x^7 + x^6 + x^5 + x^4 + x^3 + 1)*a23^251 + (x^5 + x^2 + 1)*a23^247 + (x^7 + x^6 + x^5 + x^4 + x^2)*a23^239 + a23^223 + (x^7 + x^5 + x^4 + x^2 + 1)*a23^191 + (x^7 + x^3 + x^2 + x + 1)*a23^127 + (x^6 + x^5 + x + 1)
The returned object’s
__call__
method has an additional keyword ofno_inversion=False
, which causes the returned polynomial to represent only the affine transformation step of SubBytes.sage: sb_pc(1, 0, no_inversion=True) (x^7 + x^3 + x^2 + x + 1)*a10^128 + (x^7 + x^5 + x^4 + x^2 + 1)*a10^64 + a10^32 + (x^7 + x^6 + x^5 + x^4 + x^2)*a10^16 + (x^5 + x^2 + 1)*a10^8 + (x^7 + x^6 + x^5 + x^4 + x^3 + 1)*a10^4 + (x^3 + 1)*a10^2 + (x^2 + 1)*a10 + (x^6 + x^5 + x + 1)
We can build a polynomial representing the inverse transformation by setting the keyword
algorithm='decrypt'
. However, the order of the affine transformation and the inversion step in SubBytes means that this polynomial has thousands of terms and is very slow to compute. Hence, if one wishes to build the decryption polynomial with the intention of evaluating that polynomial for a particular input, it is strongly recommended to first callsb_pc(i, j, algorithm='decrypt', no_inversion=True)
to build a polynomial representing only the inverse affine transformation, evaluate this polynomial for your intended input, then finally calculate the inverse of the result.sage: poly = sb_pc(1, 2, algorithm='decrypt', no_inversion=True) sage: state = rgf._hex_to_GF('39daee38f4f1a82aaf432410c36d45b9') sage: result = poly(state.list()) sage: rgf._GF_to_hex(result * -1) '49'
When passing the returned object to
apply_poly
andcompose
, we can make those methods change the keywordno_inversion
of this object’s__call__
method by passing the dictionary{'no_inversion': True}
to them.sage: result = rgf.apply_poly(state, sb_pc, ....: poly_constr_attr={'no_inversion': True}) sage: rgf._GF_to_hex(result) '961c72894526f746aa85fc920adcc719'
sage: rcpc = rgf.compose(sb_pc, rgf.shift_rows_poly_constr(), # needs sage.libs.gap ....: f_attr={'no_inversion': True})
Note that if we set
algorithm='decrypt'
forapply_poly
, it will perform the necessary performance enhancement described above automatically. The structure ofcompose
, however, unfortunately does not allow this enhancement to be employed.