Hız odaklı eliptik eğri skaler çarpma işlemi

Abstract

Because of the increasing importance of cyber security in today's world, modern cryptographic applications is to be secure and fast. The aim of thesis is to explore secure and fast implementation techniques of elliptic curve scalar multiplication, the main performance bottleneck of implementations in Elliptic Curve Cryptography. The studies cover two main streams of work. The first one is to pinpoint primes which can be used to provide maximum speed. The other is to develop parallel versions of celebrated Montgomery ladder algorithm. In order to achieve the first aim, a mathematical framework that will parameterize fast primes is proposed. With the help of this framework, the overlooked prime 2^261-2^131-1 which allows fast multiplication is found. It is shown with our implementation that this new prime performs faster than the popular primes 2^251-9 and 2^255-19, which makes it a good candidate for efficient implementations. In addition, a 9-limb representation of the prime 2^255-19 is developed. The new representation performs well on processors with slower integer multiplication circuits. In order to achieve the second aim, the first 4-way parallel version of the Montgomery ladder algorithm is proposed. The proposed algorithm is inert to changes in the elliptic curve parameters such as curve constants and the base point. This makes it a perfect candidate for variable-base variable-scalar multiplication. The algorithm finds immediate application in the contemporary SIMD processors.

Siber güvenliğin günümüz dünyasında artan önemi ile birlikte modern kriptografik uygulamalar güvenli ve hızlı olmalıdır. Bu tezin amacı, eliptik eğri tabanlı kriptografik uygulamaların darboğazı olan eliptik eğri skalar çarpma işleminin güvenli ve hızlı gerçekleştirilmesini sağlamaktır. Bu tezdeki çalışmalar iki ana eksende yürütülmüştür. Birinci safhada, en yüksek hızı sağlamak için kullanılabilecek asal sayılar belirlenmiştir. İkinci safhada ise, Montgomery merdiven algoritmasının paralel versiyonu geliştirilmiştir. Birinci amaca ulaşmak için hızlı asal sayıları belirleyecek matematiksel bir çerçeve önerilmiştir. Bu çerçeve yardımıyla hızlı çarpmaya izin veren ve gözden kaçan 2^261-2^131-1 asal sayısı bulunmuştur. Bu yeni asalın, popüler 2^251-9 ve 2^255-19 asal sayılarından daha hızlı performans gösterdiği gerekçeleriyle gösterilmiştir. Ek olarak, 2^255-19 asalının 9 basamaklı bir temsili geliştirilmiştir. Yeni gösterim, daha yavaş tamsayı çarpma devrelerine sahip işlemcilerde iyi performans göstermektedir. İkinci amaca ulaşmak için Montgomery merdiven algoritmasının ilk 4 yönlü paralel versiyonu önerilmiştir. Önerilen algoritma, eğri sabitleri ve taban noktası gibi eliptik eğri parametrelerindeki değişikliklerden bağımsız çalışmaktadır. Bu da, önerilen metodu değişken-taban değişken-skalar çarpma işlemi için iyi bir aday yapmaktadır. Algoritma, güncel SIMD işlemcilerinde uygulama bulmuştur.