Defining AES MixColumns in Sage

msdousti
13 ●1 ●1 ●3

AES is a famous cipher. It has an operation called MixColumns (See Wikipedia entry Rijndael MixColumns) where operations take place over finite fields.

Actually, there's a specific polynomial $a(x) = a_3x^{3}+a_2x^{2}+a_1x+a_0$ whose coefficients belong to $GF(2^8)$ . MixColumns is defined between $a(x)$ and any polynomial $b(x) = b_{3}x^{3}+b_{2}x^{2}+b_{1}x+b_{0}$ (whose coefficients belong to $GF(2^8)$ as well): It first multiplies $a(x)$ by $b(x)$ (where the algebraic rules between coefficients are governed by $GF(2^8)$ ), and then computes the remainder modulo $x^4 + 1$ .

I tried to mimic the operations in Sage as follows:

R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1))
T.<z> = QuotientRing(S, S.ideal(y^4+1))

But Sage displays an error on the last line. The error seems to be originating from the introduction of z. If I replace the last line with, say, T = QuotientRing(S, S.ideal(y^4+1)), the error goes away. Yet this is not what I intended.

Furthermore, the command S.ideal(y^4+1) outputs:

Principal ideal (1) of Univariate Quotient Polynomial Ring in y over Finite Field of size 2 with modulus x^8 + x^4 + x^3 + x + 1

I don't understand why its is the principal ideal (1) rather than the principal ideal (y^4+1).

answered 7 years ago

vdelecroix
7640 ●20 ●85 ●168 http://www.labri.fr/pe...

updated 7 years ago

With your code S = GF(256) is a field and y its generator

sage: R.<x> = PolynomialRing(GF(2), 'x')
sage: S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1))
sage: S.is_field()
True
sage: S.cardinality()
256
sage: y^8 + y^4 + y^3 + y + 1      # defining polynomial
0

In particular

sage: S.ideal(1) == S.ideal(y) == S.ideal(y^4 + 1)
True

What you want to consider is a different object, namely GF(256)[y], and for that you need to construct a polynomial ring over GF(256). The construction R.<x> in Sage does not build a polynomial ring but simply assign to x the generator of R.

link

Comments

Thanks a lot. Could you please answer the first part, too: ln short, how can I define $GF(256)[x] / \langle x^4 + 1 \rangle$ in Sage? I mean, as stated in the question, addition and multiplication of polynomials with coefficients in $GF(256)$ modulo $x^4+1$ .

msdousti ( 7 years ago )

I tried to be clearer.

vdelecroix ( 7 years ago )

Thanks again. Let me just confirm my understanding: Sage does not provide a way for defining $GF(256)[x] / \langle x^4 + 1 \rangle$ , right?

msdousti ( 7 years ago )

What's wrong with

sage: R.<x> = PolynomialRing(GF(256), 'x')
sage: R.quotient(x^4 + 1)
Univariate Quotient Polynomial Ring in xbar over Finite Field in z8 of size 2^8 with modulus x^4 + 1

vdelecroix ( 7 years ago )

It must work, but it does not (to my surprise). In your definition, $R$ is the ring of polynomials with coefficients over $GF(256)$ , but sage treats it as the ring of polynomials with coefficients over $GF(2)$ ! Just enter something like 5*x in sage, and it interprets this polynomial as x. Or enter x+x, and sage outputs 0.

msdousti ( 7 years ago )

see more comments

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Defining AES MixColumns in Sage

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Defining AES MixColumns in Sage savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

Defining AES MixColumns in Sage