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

Abstract

Bu tezde eliptik ve hipereliptic eğri tabanlı protokoller başta olmak üzere donanım tabanlı kriptografik algoritmaların işlem platformlarına odaklandık. Hipereliptik eğri tabanlı Tate Pairing işlemlerinin özellikle donanımsal uygulamalarını verimli hale getirmeye çalıştık. Bunun için $/mathbb{F}_q, q=p^{2pn}$ şeklindeki sonlu cisimlerini verimli uygulamaya çalıştık. Bu cisimleri $f(x) = x^p - x - a $ formundaki indirgenemez polinomlarla temsil edebileceğimizi gözlemledik. Bu temsil şeklini kullanarak cismin normal bazını oluşturmak, normal bazdan $/mathbb{F}_q$'ın polinom bazına geçiş matrisini ve de tersini oluştumak için bir yol bulduk. Burada önemli nokta bu matrisi ve tersini hiç bellek kullanmadan hızlı bir şekilde elde edilebiliyor olmasıdır. Daha sonra bu çalışmada geliştirdiğimiz teknikleri I.Duursma, H.S.Lee tarafından /cite{z13}'da önerilen algoritmaya, S.Kwon'un /cite{z20}'da değiştirdiği algoritmaya ve /cite{z}'de önerilen donanım uygulaması şemasına uyguladık. Bu hızlı şekildeki baz değişimini kullanarak pairing işlem maliyetlerini azalttığımız gibi, bileşik sonlu cisim yapıları tabanlı diğer algoritmaların da maliyetlerini de önemli bir boyutta azaltabileceğimizi gördük. Kısacası, herhangi bir asal için $/mathbb{F}_q, q=p^{2pn}$ türündeki sonlu cisimlerde polinom bazından normal baza ve tersine geçişi hiç bellek kullanmadan hızlı bir şekilde yapmak için yeni bir yol gösterdik ve bu dönüşümleri yaparak Tate pairing işlem maliyetini /%49.5 kadar azalttık. İkinci olarak FPGA tabanlı kriptografinin bir parçası olarak kriptografik algoritmaları FPGA'lerde uyguladık, FPGA'lerin içindeki diğer çekirdeklerle ve Microblaze işlemci kullanarak FPGA dışarsındaki ek birimlerle bütünleştirdik. Ayrıca p=7 için /cite{z}'dekinden /%31 daha hızlı asal cisim çarpımını uyguladık ve bu çarpımı kullanarak /cite{z}'deki Tate pairing algoritmasını /%17 daha hızlı hale getirdik. Son olarak, NIST'in ECDSA ve AES-128'de kullanılmak üzere tavsiye ettiği K-163 eliptik eğrisi ve SHA-1 protokollerinde kullanılan ikili cisimler üzerinde modüler çarpma, toplama, tersini alma ve hızlı kare alma işlemlerini de referans olması için var olan FPGA platformunda uyguladık.Anahtar Kelimeler : Kompozit Finite Field, temel dönüşüm, Vandermonde matris, Tate pairing, kriptografi, FPGA

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.Keywords: Composite Finite Fields, basis conversion, Vandermonde matrix, Tatepairing, cryptography, FPGA