Elliptic curve pairing-based cryptography

Abstract

Bu tezde, eliptik eğriler üzerindeki eşleme tabanlı kriptografiyi teorik ve uygulama açısından inceliyoruz. Bu bağlamda, ilk olarak eşleme tabanlı kriptografide kullanılan, adına eşlemeye uygun denilen elliptik eğrileri çalışıyoruz. Bu eğrileri oluşturulma yöntemlerine göre sınıflan-dırıyor ve detaylı olarak açıklıyoruz.Koblitz ve Menezes'in yaptıkları çalışmadan esinlenerek, boyutu asal $q$ olan sonlu cisim $/mathbb{F}_{q}$ üzerinde tanımlı $y^{2}=x^{3}-c$ biçimindeki eliptik eğrileri çalışıyoruz ve bu eğrilerin $/mathbb{F}_{q}$ üzerindeki nokta sayılarını net olarak hesaplıyoruz. Bunun yanısıra, boyutu $q=27A^{2}+1$ biçiminde olan $/mathbb{F}_{q}$ üzerinde tanımlı $y^{2}=x^{3}-1$ eliptik eğrisinin gömme derecesinin $k=1$ olduğunu ve yapmış olduğumuz sınıflandırmada bu eğrinin Scott-Barreto ailesinin bir üyesi olduğunu gösteriyoruz. Son olarak, eşleme tabanlı kriptografik protokollerde kullanılan $y^{2}=x^{3}-1$ eğrisinin üzerinde tanımlı olduğu $/mathbb{F}_{q}$ cisminin boyutunu temsil eden $q=27A^{2}+1$ biçimindeki asallara, güvenlik seviyesi 128-, 192- ya da 256-bitlik AES anahtarlarına denk olacak şekilde örnekler veriyoruz.Uygulama açısından, eşleme hesaplamanın en önemli bölümlerinden birisi de son üs alma işlemidir. Bu bağlamda, son üs alma işeminin, lineer yineleme bağıntısıyla nasıl bağlantılı olduğunu gösteriyoruz. Bunun yanısıra, son üs almayı hesaplayan bir algoritma bulmanın, ilgili lineer yineleme bağıntısının genel terimini hesaplayan algoritmayı bulmaya karşılık geldiğini veriyoruz. Ayrıca, şimdiye kadar literatürde çalışılmış bütün işleri listeliyor ve ilgili lineer yineleme bağıntısının etkili bir biçimde nasıl hesaplandığını ifade ediyoruz.

In this thesis, we explore the pairing-based cryptography on elliptic curves from the theoretical and implementation point of view. In this respect, we first study so-called pairing-friendly elliptic curves used in pairing-based cryptography. We classify these curves according to their construction methods and study them in details.Inspired of the work of Koblitz and Menezes, we study the elliptic curves in the form $y^{2}=x^{3}-c$ over the prime field $/mathbb{F}_{q}$ and compute explicitly the number of points $/#E(/mathbb{F}_{q})$. In particular, we show that the elliptic curve $y^{2}=x^{3}-1$ over $/mathbb{F}_{q}$ for the primes $q$ of the form $27A^{2}+1$ has an embedding degree $k=1$ and belongs to Scott-Barreto families in our classification. Finally, we give examples of those primes $q$ for which the security level of the pairing-based cryptographic protocols on the curve $y^{2}=x^{3}-1$ over $/mathbb{F}_{q}$ is equivalent to 128-, 192-, or 256-bit AES keys.From the implementation point of view, it is well-known that one of the most important part of the pairing computation is final exponentiation. In this respect, we show explicitly how the final exponentiation is related to the linear recurrence relations. In particular, this correspondence gives that finding an algoritm to compute final exponentiation is equivalent to finding an algorithm to compute the $m$-th term of the associated linear recurrence relation. Furthermore, we list all those work studied in the literature so far and point out how the associated linear recurrence computed efficiently.