Efficient systolic multiplications in composite fields for cryptographic systems

Multiplications in finite fields are playing a key role in areas of cryptography and mathematic. We present approaches to exploit systolic architecture for multiplications in composite fields, which are expected to reduce the time-area product substantially. We design a pipelined architecture for multiplications in composite fields \begin{document} $GF({({2^n})^2})$ \end{document}, where \begin{document} $n$ \end{document} is a positive integer. Besides, we design systolic architectures for multiplications and additions in finite fields \begin{document} $GF(2^n)$ \end{document}. By integrating main improvements and other minor optimizations for multiplications in \begin{document} $GF({({2^n})^2})$ \end{document}, the non-pipelined versions of our design takes \begin{document} $8n+4$ \end{document} AND gates and \begin{document} $8n$ \end{document} XOR gates to compute multiplications with the executing time of \begin{document} $nT_{AND}+4nT_{XOR}$ \end{document}, where \begin{document} $T_{AND}$ \end{document} and \begin{document} ${T_{XOR}}$ \end{document} are delays of AND and XOR gates respectively; with the aid of pipelining, the pipelined version of our design has a throughput rate of one result per \begin{document} $2nT_{XOR}$ \end{document}. Other words, the time complexity and area complexity of our design are \begin{document} $O(n)$ \end{document}. Thus, the complexity of time-area product of our design is \begin{document} $O(n^2)$ \end{document}. Experimental results and comparisons show that our design provides significant reductions in executing time and area of multiplications.