Ask Your Question
2

How to express unknown coefficients in GF(2^8)?

asked 2018-12-15 17:32:46 +0100

rlsw gravatar image

updated 2018-12-15 18:12:29 +0100

I want to make computations in GF(2^8) using the Rijndael modulus X^8+X^4+X^3+X+1 and with unknown elements of GF(2^8).

For example, I need a polynomial x which is defined as x = x_7 * X^7 + x_6 * X^6 + x_5 * X^7 + ... + x_0

x.coefficients() should return [x_0, x_1, x_2, x_3, x_4, ...]

If I for example add x to y, I would expect that the result would be a term like (x_7+y_7) * X^7 + (x_6+y_6)*X^6 + ...

I tried the following:

sage: pgen = polygen(Integers(2))
sage: modulus = pgen()**8 + pgen()**4 + pgen()**3 + pgen() + 1
sage: F = FiniteField(2**8, 'X', modulus = modulus)
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: uF = PolynomialRing(F, 16, x_coeffs + y_coeffs); uF
Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field in a of size 2^8

sage: poly_x = uF(x_0 * X^0 + x_1 * X^1 + x_2 * X^2 + x_3 * X^3 + x_4 * X^4 + x_5 * X^5 + x_6 * X^6 + x_7 * X^7)
sage: poly_y = uF(y_0 * X^0 + y_1 * X^1 + y_2 * X^2 + y_3 * X^3 + y_4 * X^4 + y_5 * X^5 + y_6 * X^6 + y_7 * X^7)

(which is very much like I found it in the sources of sage.crypto.mq.rijndael_gf.RijndaelGF)

But the coefficients of poly_x and poly_y are not the variables x_0, x_1 etc. but the X^0, X^1, etc...

I also tried:

sage: F = GF(2^8, 'X')
sage: X = F.gen()
X
sage: x_coeffs = list(var('x_%d' % i) for i in range(8))
sage: y_coeffs = list(var('y_%d' % i) for i in range(8))
sage: poly_x = 0*X
sage: type(poly_x)
<type 'sage.rings.finite_rings.element_givaro.FiniteField_givaroElement'>
sage: for i in xrange(8):
....:     poly_x += x_coeffs[i] * X^i
....:
sage: poly_x
x_0 + X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7
sage: type(poly_x)
<type 'sage.symbolic.expression.Expression'>
sage: poly_x.coefficients()
[[X*x_1 + X^2*x_2 + X^3*x_3 + X^4*x_4 + X^5*x_5 + X^6*x_6 + X^7*x_7, 0],
 [1, 1]]

which is also not what I want. Also, expressions like the follow lead to an error:

sage: F(x_1*X)
TypeError: unable to coerce <type 'sage.symbolic.expression.Expression'>

How can I express unknown elements with unknown coefficients?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2018-12-15 18:30:17 +0100

rburing gravatar image

updated 2018-12-15 18:59:33 +0100

In your attempt the ring containing X is the base ring over which you build a polynomial ring, but you want it the other way around. You could work in the ring $(\mathbb{F}_2[x_0,\ldots,x_7,y_0,\ldots,y_7])[X]/(X^8+X^4+X^3+X+1)$:

sage: S = PolynomialRing(GF(2), names=['x_{}'.format(d) for d in range(8)] + ['y_{}'.format(d) for d in range(8)]); S
Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field of size 2
sage: S.inject_variables()
Defining x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7
sage: T.<Y> = PolynomialRing(S); T
Univariate Polynomial Ring in Y over Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field of size 2
sage: U.<X> = T.quotient(Y^8+Y^4+Y^3+Y+1); U
Univariate Quotient Polynomial Ring in X over Multivariate Polynomial Ring in x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7, y_0, y_1, y_2, y_3, y_4, y_5, y_6, y_7 over Finite Field of size 2 with modulus Y^8 + Y^4 + Y^3 + Y + 1
sage: x = x_0 + x_1*X + x_2*X^2 + x_3*X^3 + x_4*X^4 + x_5*X^5 + x_6*X^6 + x_7*X^7
sage: y = y_0 + y_1*X + y_2*X^2 + y_3*X^3 + y_4*X^4 + y_5*X^5 + y_6*X^6 + y_7*X^7
sage: x.list()
[x_0, x_1, x_2, x_3, x_4, x_5, x_6, x_7]
sage: x + y
(x_7 + y_7)*X^7 + (x_6 + y_6)*X^6 + (x_5 + y_5)*X^5 + (x_4 + y_4)*X^4 + (x_3 + y_3)*X^3 + (x_2 + y_2)*X^2 + (x_1 + y_1)*X + x_0 + y_0
sage: (x + y).list()
[x_0 + y_0,
 x_1 + y_1,
 x_2 + y_2,
 x_3 + y_3,
 x_4 + y_4,
 x_5 + y_5,
 x_6 + y_6,
 x_7 + y_7]

Here I use .list() instead of .coefficients() because we are in a quotient ring; you could also do .lift().coefficients().

Note that the $x_i$ and $y_i$ do not behave exactly like elements of $\mathbf{F}_2$ in the sense that $x_i^2 \neq x_i$ etc.

edit flag offensive delete link more

Comments

1

thank you so much! this is exactly what I need

rlsw gravatar imagerlsw ( 2018-12-15 19:16:38 +0100 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-12-15 17:32:46 +0100

Seen: 549 times

Last updated: Dec 15 '18