Formal Analysis of Galois Field Arithmetic Circuits-Parallel Verification and Reverse Engineering
Formal Analysis of Galois Field Arithmetic Circuits-Parallel Verification and Reverse Engineering
复制标题
伽罗瓦域算术电路的形式分析-并行验证与逆向工程
DOI：
--
复制
发表时间：
2018
影响因子：
2.9
通讯作者：
M. Ciesielski
中科院分区：
文献类型：
--
作者：
Cunxi Yu;M. Ciesielski
Galois Field（GF）算术电路在通信，信号处理和安全工程中找到了许多应用。 GF电路的形式验证技术稀缺，仅限于具有主要输入和输出的位置的电路。他们还需要了解不可约多的多项式<inline-formula> <tex-math notegy =“ latex”> $ {p（x）} $ </tex-math> </tex-math> </inline-formula>，影响最终硬件实现。本文介绍了一种计算机代数技术，该技术执行GF的验证和反向工程（<inline-Formula> <tex-Math Notegy =“ LATEX”> $ {2^{M}}} $ </tex-Math> </inline-公式>）乘数直接来自门级实现。该方法基于以平行方式提取独特的不可约多项式，并分为三个步骤：1）确定输出位的位位置； 2）确定输入位的位位置； 3）提取设计中使用的不可约多项式。我们证明了此方法能够反向工程GF（<inline-Formula> <tex-Math notegy =“ latex”> $ {2^{m}} $ </tex-math> </inline-formula>）乘数在<inline-formula> <tex-math notegy =“ latex”> $ {m} $ </tex-math> </inline-formula>线程。在合成<Italic> mastrovito </italic>和<Italic> Montgomery </Italic>具有不同<inline-formula> <inline-formula> <tex-math notegy =“ latex”> $ {p（x）$ {p（x）$ </tex $ </tex </tex </tex -math> </inline-formula>，包括NIST-强制性的多项式，表明该方法的效率很高。
Galois field (GF) arithmetic circuits find numerous applications in communications, signal processing, and security engineering. Formal verification techniques of GF circuits are scarce and limited to circuits with known bit positions of the primary inputs and outputs. They also require knowledge of the irreducible polynomial <inline-formula> <tex-math notation="LaTeX">${P(x)}$ </tex-math></inline-formula>, which affects final hardware implementation. This paper presents a computer algebra technique that performs verification and reverse engineering of GF(<inline-formula> <tex-math notation="LaTeX">${2^{m}}$ </tex-math></inline-formula>) multipliers directly from the gate-level implementation. The approach is based on extracting a unique irreducible polynomial in a parallel fashion and proceeds in three steps: 1) determine the bit position of the output bits; 2) determine the bit position of the input bits; and 3) extract the irreducible polynomial used in the design. We demonstrate that this method is able to reverse engineer GF(<inline-formula> <tex-math notation="LaTeX">${2^{m}}$ </tex-math></inline-formula>) multipliers in <inline-formula> <tex-math notation="LaTeX">${m}$ </tex-math></inline-formula> threads. Experiments performed on synthesized <italic>Mastrovito</italic> and <italic>Montgomery</italic> multipliers with different <inline-formula> <tex-math notation="LaTeX">${P(x)}$ </tex-math></inline-formula>, including NIST-recommended polynomials, demonstrate high efficiency of the proposed method.