Coverage for local/lib/python2.7/site-packages/sage/crypto/mq/rijndael_gf.py : 80%

r""" 

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 

:mod:`Mini-AES <sage.crypto.block_cipher.miniaes>`, 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 :mod:`SR <sage.crypto.mq.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 

:mod:`SR <sage.crypto.mq.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 

:mod:`SR <sage.crypto.mq.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: rcpc = rgf.compose(rgf.shift_rows_poly_constr(), 

....: rgf.mix_columns_poly_constr()) 

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

<BLANKLINE> 

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 

<BLANKLINE> 

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) 

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

<BLANKLINE> 

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

....: rgf.add_round_key_poly_constr(), 

....: f_attr={'round' : 4}, g_attr={'round' : 7}) 

sage: rcpc(1, 2) 

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 

""" 

#***************************************************************************** 

# Copyright (C) 2015 Thomas Gagne <thomasgagne100@gmail.com> 

# 

# This program is free software: you can redistribute it and/or modify 

# it under the terms of the GNU General Public License as published by 

# the Free Software Foundation, either version 2 of the License, or 

# (at your option) any later version. 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from __future__ import print_function, division 

from six import string_types 

from sage.matrix.constructor import matrix 

from sage.matrix.constructor import column_matrix 

from sage.structure.element import Matrix 

from sage.rings.finite_rings.finite_field_constructor import FiniteField 

from sage.rings.integer import Integer 

from sage.structure.sage_object import SageObject 

from sage.matrix.matrix_space import MatrixSpace 

from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing 

class RijndaelGF(SageObject): 

def __init__(self, Nb, Nk, state_chr='a', key_chr='k'): 

r""" 

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) 

""" 

if Nb not in range(4, 9): 

msg = "Block length Nb must be in the range 4 - 8, not {0}" 

raise ValueError(msg.format(Nb)) 

if Nk not in range(4, 9): 

msg = "Key length Nk must be in the range 4 - 8, not {0}" 

raise ValueError(msg.format(Nk)) 

if not isinstance(state_chr, string_types): 

msg = "state_chr must be a string, not {0}" 

raise TypeError(msg.format(state_chr)) 

if not isinstance(key_chr, string_types): 

msg = "key_chr must be a string, not {0}" 

raise TypeError(msg.format(key_chr)) 

self._Nb = Nb 

self._Nk = Nk 

round_num_table = matrix([[10,11,12,13,14], [11,11,12,13,14], 

[12,12,12,13,14], [13,13,13,13,14], 

[14,14,14,14,14]]) 

self._Nr = round_num_table[self._Nb - 4, self._Nk - 4] 

from sage.rings.polynomial.polynomial_ring import polygen 

# Build framework for polynomial creation. 

from sage.rings.finite_rings.integer_mod_ring import Integers 

pgen = polygen(Integers(2)) 

mod = pgen**8 + pgen**4 + pgen**3 + pgen + 1 

self._F = FiniteField(2**8, 'x', modulus=mod) 

state_names = [state_chr + str(i) + str(j) 

for i in range(4) for j in range(self._Nb)] 

subkey_names = [key_chr + str(r) + str(i) + str(j) 

for r in range(self._Nr + 1) for i in range(4) 

for j in range(self._Nb)] 

self._state_PR = PolynomialRing(self._F, len(state_names), state_names) 

self._all_PR = PolynomialRing(self._F, len(state_names + subkey_names), 

state_names + subkey_names) 

self.state_vrs = matrix(4, self._Nb, self._state_PR.gens()) 

self.subkey_vrs_list = list(self._all_PR.gens()[4 * self._Nb:]) 

self.subkey_vrs = [matrix(4, self._Nb, 

self.subkey_vrs_list[(4 * self._Nb)*i : 

(4 * self._Nb)*(i+1)]) 

for i in range(self._Nr)] 

self.key_vrs = column_matrix([ 

self.subkey_vrs[int(i / self._Nb)].column(i % 4) 

for i in range(self._Nk)]) 

self._shiftrows_offsets_E = matrix([[0,1,2,3], [0,1,2,3], [0,1,2,3], 

[0,1,2,4], [0,1,3,4]]) 

self._shiftrows_offsets_D = matrix([[0,-1,-2,-3], [0,-1,-2,-3], 

[0,-1,-2,-3], [0,-1,-2,-4], 

[0,-1,-3,-4]]) 

self._sb_E_coeffs = [self._F("x^2 + 1"), 

self._F("x^3 + 1"), 

self._F("x^7 + x^6 + x^5 + x^4 + x^3 + 1"), 

self._F("x^5 + x^2 + 1"), 

self._F("x^7 + x^6 + x^5 + x^4 + x^2"), 

self._F("1"), 

self._F("x^7 + x^5 + x^4 + x^2 + 1"), 

self._F("x^7 + x^3 + x^2 + x + 1")] 

self._sb_D_coeffs = [self._F("x^2 + 1"), 

self._F("x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x"), 

self._F("x^6 + x^5 + x^4 + x^3 + x^2 + x + 1"), 

self._F("x^6 + x^4 + x^3 + x"), 

self._F("x^6 + x^5 + x^4 + x^3"), 

self._F("x^6 + x^4 + x^3 + 1"), 

self._F("x^7 + x^6 + x^4 + x^3 + x + 1"), 

self._F("x^6 + x^5 + x^3 + x^2 + x")] 

mixcols_E_row = [self._F('x'), self._F('x+1'), self._F('1'), 

self._F('1')] 

self._mixcols_E = matrix([mixcols_E_row[-i:] + mixcols_E_row[:-i] 

for i in range(4)]) 

mixcols_D_row = [self._F('x^3 + x^2 + x'), self._F('x^3 + x + 1'), 

self._F('x^3 + x^2 + 1'), self._F('x^3 + 1')] 

self._mixcols_D = matrix([mixcols_D_row[-i:] + mixcols_D_row[:-i] 

for i in range(4)]) 

# Build the Round_Component_Poly_Constr objects 

self._add_round_key_rcpc = \ 

RijndaelGF.Round_Component_Poly_Constr(self._add_round_key_pc, self, 

"Add Round Key") 

self._sub_bytes_rcpc = \ 

RijndaelGF.Round_Component_Poly_Constr(self._sub_bytes_pc, self, 

"SubBytes") 

self._mix_columns_rcpc = \ 

RijndaelGF.Round_Component_Poly_Constr(self._mix_columns_pc, self, 

"Mix Columns") 

self._shift_rows_rcpc = \ 

RijndaelGF.Round_Component_Poly_Constr(self._shift_rows_pc, self, 

"Shift Rows") 

def __call__(self, text, key, algorithm='encrypt', format='hex'): 

r""" 

Returns the encryption/decryption of ``text`` with key ``key``. 

INPUT: 

- ``text`` -- A plaintext to encrypt or a ciphertext to decrypt. 

- ``key`` -- The key to encrypt/decrypt ``text`` with. 

- ``algorithm`` -- Whether to encrypt or decrypt ``text``. Flag for 

encryption is "encrypt", flag for decryption is "decrypt". 

- ``format`` -- The format of ``text`` and ``key``, either "hex" or 

"binary" 

OUTPUT: 

- The encrypted or decrypted message ``text`` with key ``key``. 

EXAMPLES:: 

sage: from sage.crypto.mq.rijndael_gf import RijndaelGF 

sage: rgf = RijndaelGF(4, 4) 

sage: text = 'ef053f7c8b3d32fd4d2a64ad3c93071a' 

sage: key = '2d7e86a339d9393ee6570a1101904e16' 

sage: rgf(text, key) 

'84e75b142c8fd5a445312c0a9b2d6699' 

sage: rgf(text, key, algorithm='decrypt') 

'9bf83275406304f050c826ca72d035e6' 

We can also use binary strings for ``text`` and ``key``. :: 

sage: text = '11011100011010000011101111011011' * 4 

sage: key = '01000000000011000101101011011110' * 4 

sage: rgf(text, key, format='binary') 

'00011000010110010011100100010111010101001000010010100110101010101111001001100000011111011100100011010001010100110011000111110011' 

sage: rgf(text, key, algorithm='decrypt', format='binary') 

'11000110011001001110000101011101001001010101110001110010000111110000010111111101000011010101101011111100100001010010111000011010' 

""" 

if algorithm == 'encrypt': 

return self.encrypt(text, key, format) 

elif algorithm == 'decrypt': 

return self.decrypt(text, key, format) 

else: 

raise ValueError(("keyword 'algorithm' must be either 'encrypt' " 

"or 'decrypt'")) 

def __repr__(self): 

r""" 

Returns the string representation of ``self``. 

EXAMPLES:: 

sage: from sage.crypto.mq.rijndael_gf import RijndaelGF 

sage: rgf = RijndaelGF(5, 8) 

sage: rgf 

Rijndael-GF block cipher with block length 5, key length 8, and 14 rounds. 

""" 

msg = ("Rijndael-GF block cipher with block length {0}, key length " 

"{1}, and {2} rounds.") 

return msg.format(self._Nb, self._Nk, self._Nr) 

def block_length(self): 

r""" 

Returns 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 

""" 

return self._Nb 

def key_length(self): 

r""" 

Returns 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 

""" 

return self._Nk 

def number_rounds(self): 

r""" 

Returns 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 

""" 

return self._Nr 

def _hex_to_GF(self, H, matrix=True): 

r""" 

Returns a matrix/list of elements of `\GF{2^8}` corresponding to ``H``. 

INPUT: 

- ``H`` -- A hex string where every two hex characters correspond to a 

single element in `\GF{2^8}` 

- ``matrix`` -- (default: ``True``) Returns a list if ``False``; 

returns a state matrix if ``True``. 

OUTPUT: 

- A list of or a state matrix of elements of `\GF{2^8}` where each 

element corresponds to the appropriate hex value in ``H``. In 

particular, every element `a_7x^7 + a_6x^6 + a_5x^5 + a_4x^4 + 

a_3x^3 + a_2x^2 + a_1x^1 + a_0` in `\GF{2^8}` corresponds to the 

8-bit binary string '`a_7a_6a_5a_4a_3a_2a_1a_0`'. 

EXAMPLES:: 

sage: from sage.crypto.mq.rijndael_gf import RijndaelGF 

sage: rgf = RijndaelGF(4, 4) 

sage: state = rgf._hex_to_GF('1147659047cf663b9b0ece8dfc0bf1f0') 

sage: output = rgf.shift_rows(state) 

sage: rgf._GF_to_hex(output) 

'11cfcef0470ef1909b0b653bfc47668d' 

We can output a list instead by setting ``matrix`` to ``False``. :: 

sage: rgf._hex_to_GF('2f', matrix=False) 

[x^5 + x^3 + x^2 + x + 1] 

sage: rgf._hex_to_GF('1a2b0f', matrix=False) 

[x^4 + x^3 + x, x^5 + x^3 + x + 1, x^3 + x^2 + x + 1] 

""" 

if not isinstance(H, string_types) or \ 

any(c not in '0123456789abcdefABCDEF' for c in H): 

raise TypeError("keyword 'H' must be a hex string") 

def hx_to_gf(h): 

return self._F(map(int, bin(int(h, 16))[2:].zfill(8))[::-1]) 

hexes = [H[2 * i] + H[2 * i + 1] for i in range(len(H) // 2)] 

result = [hx_to_gf(h) for h in hexes] 

if matrix: 

return column_matrix(len(result) // 4, 4, result) 

else: 

return result 

def _GF_to_hex(self, GF): 

r""" 

Returns the hex string representation of ``GF``.