FGPA based cryptography computation platform and the basis conversion in composite finite fields

Sial, Muhammad Riaz
In the study of this thesis work we focused on the hardware based cryptographic algorithms computation platform, especially for elliptic-curve and hyper-elliptic curve based protocols. We worked for making the hyperelliptic curve based Tate Pairing computation efficient specially for hardware implementations. To achieve this one needs to make the underlying finite field arithmetic implementations efficient. For this we study the finite fields of type $\mathbb{F}_q, q=p^{2pn}$ from the efficient implementation point of view. We found that we can represent these fields with irreducible polynomials in the form $f(x) = x^p - x - a $ over $\mathbb{F}_{p^{2pn}}$ . By using this representation we have found a way of constructing normal basis for the field, together with transmission matrix between normal basis and Polynomial Basis of $\mathbb{F}_q$ and vice versa. The key point is that this matrix and its inverse can be computed very efficiently without any memory requirement. Then we imply the techniques developed in this work on the Tate pairing computation algorithm proposed by I.Duursma, H.S.Lee in \cite{z13} and modified by S.Kwon \cite{z20} and hardware implementation scheme proposed in \cite{z}. We found that by introduction of such efficient conversion of basis we can significantly reduce the pairing computation cost as well as the cost of other algorithms based on such composite finite field structures. In short we give a new efficient way of conversion from polynomial to normal basis and vice versa with zero memory complexity in the finite fields of type $\mathbb{F}_q, q=p^{2pn}$ for any prime and we reduce the Tate pairing computation cost by 49.5\% after applying such conversions. Secondly as part of the FPGA based cryptography platform we have implemented cryptographic algorithms in FPGA, integrated it with other cores inside FPGA and accessories outside FPGA using Microblaze processor. We also give an efficient implementation of prime field multiplication for p = 7, which is 31\% faster than the one in \cite{z} and by using this multiplier Tate-pairing algorithm in \cite{z} can be made 17\% more efficient. We also implemented modular multiplication, addition, inversion and efficient squaring modules over binary fields needed to implement protocols based on NIST recommended elliptic curve K-163 and SHA-1 to use it for ECDSA and AES-128 for reference purpose to run over existing FPGA platform.
Citation Formats
M. R. Sial, “FGPA based cryptography computation platform and the basis conversion in composite finite fields,” Ph.D. - Doctoral Program, Middle East Technical University, 2013.