CODEWITHSUNDEEP
pythonaesfinite-field
mark
mark

Reputation: 371

pyfinite gives wrong result for multiplication in field GF(2^8)

I am using pyfinte to calculate multiplication for AES over the field it uses which is F(2^8) but when I do as following:

from pyfinite import ffield

a = 0xbf
b = 0x03
F = ffield.FField(8)
c = F.Multiply(a, b)
print(hex(c))

the actual result is 0xdc but it should be 0xda here is how I solve it by hand:

0xbf*0x03 = 0xbf * 0x02 + 0xbf * 0x01 = 0b10111111 * 0x02 + 0xbf = 0b01111110 + 0x1B + 0xbf = 0b11011010 = 0xda

here is better format of my hand soloving:

enter image description here

so where is the wrong? is it on my solving by hand? or in pyfinite? how to solve this?

Upvotes: 2

Views: 1384

Answers (2)

Matt Hostetter
Matt Hostetter

Reputation: 580

The issue is that AES uses an irreducible, but not primitive, polynomial for its extension field. Most extension fields use a primitive polynomial so that x is a primitive element of the field. I imagine that's what pyfinite has as its default.

Instead, AES uses x^8 + x^4 + x^3 + x + 1 as its irreducible polynomial and has x + 1 as a primitive element (or generator of the multiplicative group).

While I don't know the details of pyfinite, I created a similar library galois that extends NumPy arrays to operate over Galois fields. It supports arbitrarily-sized array arithmetic, linear algebra on Galois field matrices, polynomials over Galois field, and more. The library is written in Python but JIT compiled using Numba so the array arithmetic is as fast as native NumPy.

Here is an example doing what you desired.

In [1]: import galois                                                                                                                                                                          

In [2]: GF = galois.GF(2**8, irreducible_poly=0x11b)                                                                                                                                           

In [3]: print(GF.properties)                                                                                                                                                                   
GF(2^8):
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: x^8 + x^4 + x^3 + x + 1
  is_primitive_poly: False
  primitive_element: x + 1

In [4]: a = GF(0xbf); a                                                                                                                                                                        
Out[4]: GF(191, order=2^8)

In [5]: b = GF(0x03); b                                                                                                                                                                        
Out[5]: GF(3, order=2^8)

In [6]: a * b                                                                                                                                                                                  
Out[6]: GF(218, order=2^8)

In [7]: 0xda                                                                                                                                                                                   
Out[7]: 218

Upvotes: 0

glibdud
glibdud

Reputation: 7850

I'm not intimately familiar with AES, but from the link you provided it appears that the generator polynomial for the field is 0x11b. By default, pyfinite uses a different generator, which will produce different multiplication results:

>>> f = ffield.FField(8)
>>> hex(f.generator)
'0x11d'

If you specify the generator when you create the field object, you get the result you're expecting:

>>> f = ffield.FField(8, gen=0x11b, useLUT=0)
>>> hex(f.Multiply(0xbf, 0x03))
'0xda'

Upvotes: 3

Related Questions