A High performance arithmetic library to implement various cryptographic algorithms

Abstract

Sonlu cisimler kriptolojinin temeleni oluşturan önemli cebirsel yapılardır. Tümkriptografik algoritmalar sonlu cisimlerin cebirsel özellikleri üzerine kuruludur. Özellikle,bu cebirsel yapılar üzerinde tanımlı eliptik eğriler, eliptik eğriler kriptosistemi adlı çokyaygın bir kriptosistem türü oluşturmaktadır. Kısaca kriptografik sistem yzılım veyadonanım düzeyinde gerçekleştirilen ve belli bir öntanımlanmış güvenlik koşuluna uygun birservis türüdür. Güvenlik herhangi bir kriptogrfik sistemin en önemli kriteridir. Fakat, busistemin yüksek performans sergileyebilmesi ve kullanışlı hale gelebilmesi için sisteminyazılım veya donanım düzeyinde etkin bir şekilde gerçekleştirilmesi gerekmektedir.Bir p asal sayı için, üzerinde modüler toplama ve çarpma işlemleri tanımlanmış olan0 ve p ? 1 arasındaki sayılar kümesi asal cisim oluşturmaktadır. Bu sayılar genel amaçlıbilgisayrda kolayaca ifade edilebileceği gibi de cisim üzerinde tanımlanmış aritmetikişlemler için de hızlı kod geliştirilebilir. Bu tezde biz asal cisimler üzerinde yogunlaşıyoruz.Asal cisimler aritmetiğini gerçekleştiren çok-duyarlıklı genel-amaçlı bilgisayar için kodgeliştirilmiştir. Bazı işlemler için birden fazla algoritmalar için kod gelişririlmiştir vebunların zamanlaması kıyaslanmıştır. Ayrıca, asal cisimler üzerinde tanımlı eliptik eğrileraritmetiği için kod geliştirilmiştir. Son olarak bu kodlar kullanarak eliptik eğri dijital imzaalgoritması için kod geliştirilmiştir.Anahtar Kelimeler: Sonlu Cisim Aritmetiği, Eliptik Eğrilere Dayalı Kriptografi, BüyükSayı Aritmetiği, Açık Anahtar Kriptografi, Dijital İmza.

A finite field is an algebraic structure that plays an important role in theoreticalfoundation of cryptography. Almost all cryptographic algorithms are based on theproperties of finite fields. In particular, elliptic curves combined with finite fields form anew type of cryptosystem called an elliptic curve cryptosystem. A cryptographic systemcan be regarded as a set of facilities implemented at hardware or software level and satisfiespredefined requirements for information security. Security is the most obvious quality ofany cryptosystem. However, an efficient implementation of a cryptosystem is alsoimportant in order to achieve a high performance.A prime field GF(p) is a finite field with prime number of elements that arerepresented as integers between 0 and the prime number p with respect to modular additionand multiplication operations. This fact makes it possible to implement prime fieldarithmetic operations efficiently on a general-purpose computer since elements of a primefield can be represented on a general-purpose computer as an array of integers. In thisthesis, we concentrate on prime fields. We implemented multiprecision algorithmsperforming prime field arithmetic suitable for a general-purpose computer. For someoperations multiple algorithms were considered and implemented. Their performance wasmeasured and compared. In addition, we implemented arithmetic operations defined onpoints of elliptic curves over finite fields and the elliptic curve digital signature algorithm.Keywords: Finite Field Arithmetic, Elliptic Curve Cryptography, MultiprecisionArithmetic, Public Key Cryptography, Digital Signature.