Hardware design of K2RED modular multiplication algorithm used in number theoretic transform for post quantum cryptography and homomorphic encryption
Post kuantum kriptografi ve homomorfik şifreleme için sayı teorik dönüşümünde kullanılan K2RED modüler çarpma algoritmasının donanım tasarımı
- Tez No: 864196
- Danışmanlar: PROF. DR. SIDDIKA BERNA ÖRS YALÇIN
- Tez Türü: Yüksek Lisans
- Konular: Bilim ve Teknoloji, Elektrik ve Elektronik Mühendisliği, Science and Technology, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2024
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Elektronik Mühendisliği Bilim Dalı
- Sayfa Sayısı: 87
Özet
Kuantum bilgisayar teknolojisinin hızlı gelişmeleri ışığında, donanımsal kriptografi araştırmacıları geleneksel şifreleme sistemlerine yönelik oluşan yakın tehdidi ele almak amacıyla post-kuantum kriptografi alanında çalışmalar yapmaktadırlar. Kuantum bilgisayarlar pratik uygulamaya yaklaştıkça, mevcut şifreleme protokollerinin güvenlik temelleri tehlike altında kalacaktır. Bu yeni şifreleme tekniklerinin güçlü ve zayıf yönlerini değerlendirerek, amacımız, devam eden dijital iletişimin post-kuantum dönemindeki güvenliğini ve gizliliğini sağlayan donanımda gerçeklenebilir, kuantum dirençli şifreleme donanımlarının geliştirilmesine katkıda bulunmaktır. Bu nedenle, Ulusal Standartlar ve Teknoloji Enstitüsü (NIST), kuantum saldırılarına dayanıklı algoritmalar tasarlamayı amaçlayan Post-Kuantum Şifreleme Standartlaştırma Sürecini başlatmıştır. Bu çağrının yapılmasının ardından ilk etapta 69 farklı algoritma sunulmuştur. Bu başvurular NIST'in belirlediği komitenin değerlendirmesine sunulmuştur. Bu komite güvenlik, donanımda gerçeklenebilme, kuantum dirençli olması bakımından algoritmaları değerlendirmiştir. Şu anda, bu süreç dört anahtar kapsülleme mekanizması ve üç dijital imza yöntemini içeren sona erme aşamasına ilerlemiştir. NIST'in bu çağrıyı açmasının önemli bir diğer nedeni ise bu alanda yapılacak çalışmalarla kuantum çağının güvenliği konusunda bir farkındalık oluşturmaktır. Çalışmaya başlama motivasyonundan bahsedecek olursak; gelecekte kullanımı artacağı ve dijital ortamda kullanılacağı düşünülen kuantum bilgisayarların yüksek işleme kapasitesiyle oluşacak güvenlik zaafiyetinin önlenmesi için ortaya konulan kriptografik algoritmaların günümüz donanımlarında gerçeklenmesi ve bu sayede dijital güvenliğin sağlanmasıdır. Bu amaçla NIST'in açtığı çağrı sonucunda belirlediği algoritmaların FPGA donanımı üzerinde gerçeklenmesi için çalışmaya başlanılmıştır ve devamında PQC ve Homomorfik Şifreleme algoritmalarındaki modüler aritmetik işlemlerinde artan verimlilik ihtiyacını tanıyarak, seçilen post-kuantum şifreleme algoritmalarının modern cihazlara sorunsuz entegrasyonunu sağlamak üzerine odaklanmaktadır. Modüler aritmetikte yaygın olarak kullanılan teknikler genellikle Barrett ve Montgomery'nin indirgeme yöntemlerine dayanmakta, bunlara ek olarak geleneksel indirgeme yöntemlerini değiştirmeyi amaçlayan önerilen birkaç alternatif bulunmaktadır. Bu modüler indirgeme algoritmaları, Rivest-Shamir-Adleman (RSA), Eliptik Eğri Şifreleme (ECC) gibi şifreleme protokollerinde de kullanılmaktadır. Ancak, Kuantum Bilgisayar tekniklerinin ortaya çıkması, araştırmacılarda veri gizliliği konusunda endişeye yol açmıştır. Bu sebeple araştırmacılar yeni ve etkin modüler indirgeme yöntemleri geliştirmek üzere çalışmalar yapmaktadır. Artan veri gizliliği zorlukları, özellikle ağa bağlı cihazların yaygınlaşmasıyla birlikte, Post-Kuantum Kriptografiyi mevcut tüm dijital aygıtlara entegre etmenin zorunlu hale gelmesine yol açmaktadır. Aksi takdirde kuantum bilgisayarların kullanımının yaygınlaşmasıyla üçüncü şahıslar mevcut güvenlik algoritmalarını çok kısa zaman periyotlarında aşabilecektir. Post-Kuantum Kriptografi'de ve diğer kriptografik algoritmalarda kullanılan modüler indirgeme modülleri (Barrett, Montgomery, Plantard, K^2RED) aynı zamanda donanım kaynaklarını en etkili şekilde kullanmalıdır. Bunun nedeni ise günümüzde ağa bağlanan cihazların hayatımızda geniş yer edinmesidir. Bu cihazlar hem maliyet bakımından hem de alan bakımından fazla yer kaplamamaktadır. Bu sebeple kuantuma dirençli algoritmaların olabilecek en hızlı, en az donanım kullanan veya en az alan kaplayan ve en maliyet etkin bir biçimde tasarlanması gerekmektedir. Kuantum bilgisayarların ortaya çıkmasıyla bu cihazların güvenliği sağlanması için bahsedilen bu kriterler mümkün olduğunca sağlanmalıdır. Aksi durumda veri güvenliği ağa bağlı tüm cihazlarda sürekli risk altında olacaktır. Tezde yapılan çalışmalarda, ilk olarak, Post-Kuantum Kriptografi alanında belirlenen algoritmalar üzerine bir literatür araştırması yapılmıştır. Bu araştırmalar sırasında, gerek NIST'in başlattığı çağrıya dönüş olarak yapılan çalışmalarda çoğunlukla tercih edilmesi gerekse NIST'in finale kalan son 7 algoritmanın 5'inin kafes tabanlı şifreleme yöntemine dayalı algoritmaların seçilmesi bu yöntemin geliştirmeye açık olduğu görülmüştür. Bu algoritmaların güvenlik ihtiyaçlarına göre donanımda uygulanması gerekmektedir. Bu sebeple donanımda gerçekleme çalışmalarının yapılarak bu alanda ortaya çıkan ihtiyaçları ve darboğazların görülmesi ve bunlara karşı çözüm yollarının geliştirilmesi amaçlanmıştır. Bu işlemi FPGA üzerinde gerçekleştirmek düşünülmüştür çünkü paralel işleme yapma yeteneğine sahiptir ve donanım tasarım süreçleri yazılım tabanlıdır. Aynı zamanda, literatür çalışmalarında, kafes tabanlı algoritmaların FPGA üzerinde gerçeklenmesinin yaygın olduğu görülmüştür. NIST tarafından seçilen kafes tabanlı algoritmaların ve homomorfik şifrelemede kullanılan kafes tabanlı şifreleme yönteminin uygulanması başlamıştır. Bu aşamada, algoritmaların adımlarını takip ederken ortak bir adımla karşılaşılmıştır. Bu adım Sayı Teorik Teorem (NTT) adı verilen bir adımdır. Bu, Galois Alanında yapılan bir tür Hızlı Fourier Dönüşümdür ve matematiksel tanım açısından ortaklıklara sahiptir çünkü NTT işlemi, bu algoritmalarda en çok kullanılan birimlerdendir ve bu adımda yapılacak optimizasyonlar (hızlandırma, alan azaltma gibi) sistem genelinde performansı arttırmada kilit bir rol oynamaktadır. Bu işlemin temeline inildiğinde ise çarpma, toplama, çıkarma ve modüler indirgeme gibi temel matematiksel işlemler olduğu görülmüştür. Bu tip işlemlerle ilgili yapılan çalışmalara bakıldığında günümüzde kullanılan modüler indirgeme yöntemlerinin ve yenilikçi çalışmaların yapıldığı görülmüştür. Bu yöntemlerden biri de K^2RED algoritmasıdır. Diğer modüler indirgeme algoritma çalışmaları incelenip bakıldığında çeşitli devre ihtiyaçlarına göre farklı devre tasarımları K^2RED algoritması elde edilmiştir. Örneğin devrenin maksimum saat frekansının çok önemli olduğu uygulamalar için farklı bir devre tasarımı yapılırken alan kullanımının önemli olduğu bir başka uygulama için ise farklı bir devre kullanılabileceği gözlenmiştir. Son kısımda ise literatürde bulunan bir NTT çekirdeği kullanarak K^2RED algoritmasının değerleri bu tez kapsamında tasarlanan en optimum tasarım ile adapte edilerek test edilmiştir. Elde edilen sonuçlar tez içeriğinde verilmiştir. Bu araştırma, modüler aritmetik algoritmalarındaki mevcut yöntemlerin FPGA üzerinde uygulanmasıyla karşılaştırmalı bir analiz yapar. Aynı zamanda bu modüler indirgeme yöntemiyle literatürde bulunan farklı bir modüler indirgemeyle elde edilen sonuçları karşılaştırır ve hız, alan ve gecikme gibi parametrelere göre farklı ihityaçları karşılayan devre çözümleri sunmaktadır. Literatürde sunulan bir indirgeme yöntemi olan K^2RED algoritması DSP blokları kullanılarak çarpma işlemine dönüştürülüp CRYSTAL-Dilithium ve Homomorfik şifreleme işlemi için de kullanılarak özgün bir çalışma yapılarak bu tez kapsamında sunulmuştur. Bu sonuçlardan elde edilen geliştirmelerden sonra NTT işleminde bu indirgeme yöntemi kullanılarak farklı bir modüler indirgeme yöntemiyle karşılaştırılmıştır. Sonuçlara göre yapılan çalışmayla birlikte alan kullanımına göre performans sonucunun daha iyi olduğu görülmüştür ve sonuç olarak elde edilen algoritma karşılaştırması, şifreleme algoritmalarının sonraki uygulamalarına rehberlik etmek amacıyla, veri gizliliğini ve güvenliği çeşitli cihazlar üzerinde kullanımı artırmayı hedefler.
Özet (Çeviri)
In light of the rapid advancements in quantum computing, security researchers delve into the field of post-quantum cryptography, aiming to address the imminent threat posed to conventional cryptographic systems. As quantum machines approach practical realization, the security underpinnings of current cryptographic protocols are at risk of compromise. By evaluating the strengths and weaknesses of these emerging cryptographic techniques, the goal is to contribute to the development of robust, quantum-resistant cryptographic hardware systems that ensure the ongoing security and privacy of digital communications in the post-quantum era. Hence, the National Institute of Standards and Technology (NIST) has undertaken the Post-Quantum Cryptography Standardization Process with the objective of devising algorithms resilient to quantum attacks. Currently, this process has progressed to its concluding stage, featuring four key encapsulation mechanisms and three digital signature methods. If we were to discuss the motivation for starting the study; it is aimed at implementing cryptographic algorithms proposed to prevent security vulnerabilities arising from the high processing capacity of quantum computers, which are expected to be increasingly used in the future and in the digital realm, on current hardware to ensure digital security. In line with this objective, work has begun to implement the algorithms identified as a result of the call opened by NIST on Field Programmable Gate Array (FPGA) hardware, and subsequently, it focuses on ensuring the seamless integration of selected post-quantum encryption algorithms into modern devices by recognizing the increasing efficiency needs in modular arithmetic operations in PQC and Homomorphic Encryption algorithms. The prevailing techniques in modular arithmetic predominantly rely on Barrett's and Montgomery's reduction methods, complemented by a few proposed alternatives aiming to supplant conventional reduction approaches. These modular arithmetic algorithms find application in cryptographic protocols like Rivest-Shamir-Adleman (RSA), Elliptic Curve Cryptography (ECC), among others. However, the advent of Quantum Computing techniques has instilled concern among researchers regarding data privacy. Given the escalating data privacy challenges, especially with the proliferation of network-connected devices, the imperative is to integrate post-quantum cryptography into every available device. The modular reduction modules (Barrett, Montgomery, Plantard, K^2RED) employed in PQC are also required to utilize hardware resources with optimal efficiency. In the studies carried out in the thesis, a literature research was conducted on the algorithms determined in the field of PQC. During these researches, algorithms based on the lattice-based cryptography method were implemented. These algorithms must be implemented on hardware according to security needs. It was considered to be done on FPGA because of its ability to perform parallel processing, and the design processes are software-based. At the same time, literature studies suggest that it is more suitable to implement lattice-based algorithms on FPGA. The implementation of the lattice-based algorithms selected by NIST and also the lattice-based encryption method used in Homomorphic encryption has begun. At this stage, a common step was encountered while following the steps of the algorithms. This step is the Number Theoretic Theorem (NTT) step, a type of Fast Fourier Transform made in Galois Field, and they share commonalities in terms of mathematical definition. Since the NTT process has the highest processing load among these algorithms, optimizations in this step (such as acceleration, area reduction) play a key role in increasing the overall performance of the system. When we look at the basis of this process, it is seen that there are basic mathematical operations such as multiplication, addition, subtraction, and modular reduction. Studies on this type of processes reveal that the modular reduction methods used today and innovative studies have been carried out. One of these methods is the K^2RED algorithm. When other modular reduction algorithm studies are examined, different circuit designs for the K^2RED algorithm have been obtained according to various circuit needs. For example, it has been observed that a different circuit can be designed for applications where the maximum clock frequency of the circuit is crucial, while a different circuit can be used for another application where space utilization is important. In the last part, the values of the K^2RED algorithm were tested by adapting it to the most optimal design within the scope of this thesis, using an NTT kernel found in the literature. The results obtained are presented in the thesis content. This research conducts a comparative analysis by implementing existing methods of modular arithmetic algorithms on FPGA. Simultaneously, it compares the results obtained with a different modular reduction found in the literature through this modular reduction method, and it provides circuit solutions that meet different requirements based on parameters such as speed, area, and delay. The K^2RED algorithm, a reduction method presented in the literature, is transformed into multiplication operations using DSP blocks and is utilized for CRYSTAL-Dilithium and Homomorphic encryption processes, presenting an original study within the scope of this thesis. Following the improvements obtained from these results, this reduction method is compared with a different modular reduction method in NTT operation. According to the results of the study, it is observed that the performance result is better in terms of area usage, and as a result, the algorithm comparison obtained aims to guide future applications of encryption algorithms to increase data privacy and security across various devices.
Benzer Tezler
- Pasif akustik konum belirleyici donanımı tasarımı
Hardware design of passive acoustic source localization system
ÇAĞIN TÜRKOĞLU
Yüksek Lisans
Türkçe
2014
Elektrik ve Elektronik MühendisliğiKocaeli ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ANIL ÇELEBİ
- İnternet üzerinden haberleşen güç kalitesi monitör cihazı donanım tasarımı
Hardware design of power quality monitor communicating via internet
TEVHİD ATALIK
Yüksek Lisans
Türkçe
2007
Elektrik ve Elektronik MühendisliğiHacettepe ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF.DR. IŞIK ÇADIRCI
- Akıllı fabrikalara yönelik gerçek zamanlı konumlama sistemi destekli IoT ağ geçidinin donanım tasarımı
Hardware design of real time positioning system supported IoT gateway for smart factories
HÜSEYİN ÖZDİL
Yüksek Lisans
Türkçe
2023
Elektrik ve Elektronik Mühendisliğiİzmir Katip Çelebi ÜniversitesiElektrik ve Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. ADNAN KAYA
- Mikroişlemcilerde üretilen değerlerin genişliklerini tahmin etmek için donanım tasarımı
Hardware design for predicting widths of values produced in microprocessors
HATİCE ŞEYMA ÜLKER
Yüksek Lisans
Türkçe
2007
Mühendislik BilimleriTOBB Ekonomi ve Teknoloji ÜniversitesiMühendislik Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. OĞUZ ERGİN
- Genel amaçlı bir yapay sinir ağının karma bir donanımla gerçeklenmesi
Mixed mode hardware design of a general purposed artificial neural network
BURCU ERKMEN
Doktora
Türkçe
2007
Elektrik ve Elektronik MühendisliğiYıldız Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF.DR. TÜLAY YILDIRIM