Reverse Engineering of Irreducible Polynomials in GF(2^m) Arithmetic

2016/12/14 by Cunxi Yu, Daniel Holcomb, Yu, Cunxi +3
Computer Science · Engineering · #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Formal Methods in Verification #Low-power high-performance VLSI design #Symbolic Computation (cs.SC) #cs.SC

paper · pdf · doi:10.48550/arxiv.1612.04588

6 pages, 4 figures, DATE 2017, Lausanne, Switzerland, March 27-31, 2017

arxiv created 2016/12/14 · openalex publication_date 2016/12/14 · arxiv updated 2016/12/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Current techniques for formally verifying circuits implemented in Galois field (GF) arithmetic are limited to those with a known irreducible polynomial P(x). This paper presents a computer algebra based technique that extracts the irreducible polynomial P(x) used in the implementation of a multiplier in GF(2^m). The method is based on first extracting a unique polynomial in Galois field of each output bit independently. P(x) is then obtained by analyzing the algebraic expression in GF(2^m) of each output bit. We demonstrate that this method is able to reverse engineer the irreducible polynomial of an n-bit GF multiplier in n threads. Experiments were performed on Mastrovito and Montgomery multipliers with different P (x), including NIST-recommended polynomials and optimal polynomials for different microprocessor architectures.

Citations

• Graph-Based Algorithms for Boolean Function Manipulation

Related

• Formal Analysis of Galois Field Arithmetics - Parallel Verification and Reverse Engineering
• Efficient Parallel Verification of Galois Field Multipliers
• Algorithmic Obfuscation over GF(2^m)
• A New Algebraic Method to Search Irreducible Polynomials Using Decimal Equivalents of Polynomials over Galois Field GF(p^q)
• Arithmetic Operators over Finite Field GF(2^m) for Error Correction Codes Application