Exploring fields with shift registers

The S-Boxes used in the AES algorithm are generated by field extensions of the Galois field over two elements, called GF(2). Therefore, understanding the field extensions provides a method of analysis, potentially efficient implementation, and efficient attacks. Different polynomials can be used to generate the fields, and we explore the set of polynomials x^ 2 + x + a^J over GF(2^n) where a is a primitive element of GF(2^n). The results of this work are the first steps towards a full understanding of the field that AES computation occurs in-GF(2^8). The charts created with the data we gathered detail which power of the current primitive root is equal to previous primitive roots for fields up through GF(2^16) created by polynomials of the form x^2 + x + a^i for a primitive element a. Currently, a C++ program will also provide all the primitive polynomials of the form x^2 + x+ a^i for a primitive element a over the fields through GF(2^32). This work also led to a deeper understanding of certain elements of a field and their equivalent shift register state. In addition, given an irreducible polynomial 2 f(x) = x^2 + a^i x + a^j over GF(2^n), the period (and therefore the primitivity) can be determined by a new theorem without running the shift register generated by f(x).

Department dc:contributor.department

Computer Science (CS)

Grantor dc:publisher

Monterey, CA; Naval Postgraduate School

Year dc:date.issued

2006

Author dc:creator

• Radowicz, Jody L.

Advisors dc:contributor.advisor

• Dinolt, George
• Fredricksen, Harold

Handle dc:identifier.uri

https://hdl.handle.net/10945/2603

OAI identifier oai:identifier

oai:calhoun.nps.edu:10945/2603