FPGA based cryptography computation platform and the basis conversion in composite finite fields
FPGA tabanlı kriptografi işlem platformu ve bileşik sonlu cisimlerde baz dönüşümü
- Tez No: 346023
- Danışmanlar: PROF. DR. ERSAN AKYILDIZ
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Matematik, Electrical and Electronics Engineering, Mathematics
- Anahtar Kelimeler: Composite Finite Fields, basis conversion, Vandermonde matrix, Tate pairing, cryptography, FPGA
- Yıl: 2013
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 65
Özet
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
Özet (Çeviri)
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.
Benzer Tezler
- Compact, flexible and fast coprocessor design for elliptic curve pairing operation on reconfigurable hardware
FPGA üzerinde eliptik eğri pairing operasyonu için esnek, kompakt ve hızlı işlemci tasarımı
ERTUĞRUL MURAT
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERKAY SAVAŞ
- Development of application specific transport triggered processors for post-quantum cryptography algorithms
Post-kuantum kriptografi algoritmaları için uygulamaya özel taşıma tetiklemeli işlemcilerin geliştirilmesi
LATİF AKÇAY
Doktora
İngilizce
2022
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
- Efficient modular multiplication techniques for large integers on FPGAs
FPGA üzerinde geniş tam sayılar için verimli çarpma teknikleri
ERDEM ÖZCAN
Doktora
İngilizce
2019
Elektrik ve Elektronik MühendisliğiGebze Teknik ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. SERDAR SÜER ERDEM
- System on chip implementation of new information hiding method
Yeni bir veri gizleme yönteminin geliştirilmesi ve yongada sistem üzerinde gerçeklenmesi
UTKU ESEN
Yüksek Lisans
İngilizce
2018
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. SIDDIKA BERNA ÖRS YALÇIN
- Constructing cluster of simple FPGA boards for cryptologic computations
Kriptolojik hesaplamalar için, basit SPKD çevrim kartlarından oluşmuş kümelerin gerçeklenmesi
YARKIN DORÖZ
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERKAY SAVAŞ