Geri Dön

Kuantum sonrası kriptografi

Post quantum cryptography

PDF İndir

  1. Tez No: 783401
  2. Yazar: VEYSEL GÜLTEKİN
  3. Danışmanlar: PROF. DR. ENVER ÖZDEMİR
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilim ve Teknoloji, Science and Technology
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: Türkçe
  9. Üniversite: İstanbul Teknik Üniversitesi
  10. Enstitü: Lisansüstü Eğitim Enstitüsü
  11. Ana Bilim Dalı: Bilişim Uygulamaları Ana Bilim Dalı
  12. Bilim Dalı: Bilgi Güvenliği Mühendisliği ve Kriptografi Bilim Dalı
  13. Sayfa Sayısı: 105

Özet

Kuantum bilgisayarların keşfi ile klasik kriptografi olarak adlandırdığımız ve günümüzde tüm kriptografik cihazlarda kullanılan kriptosistemlerin güvenliği tartışılır hale gelmiştir. Kuantum bilgisayarlardaki hızlı gelişme sonucunda kriptografideki çalışma alanı kuantum bilgisayarlara karşı güvenli sistemlerin tasarlanması ve analiz edilmesi yönünde değişmiştir. Shor Algoritması ile çarpanlara ayırma probleminin çözümünün üstel zamandan polinom zamana indirilmesiyle özellikle asimetrik kriptosistemler tehdit altına girmiştir. Günümüzde verilerin büyük çoğunluğu klasik kriptografide kullanılan anahtar anlaşma algoritmaları ile paylaşılan anahtar kullanılarak simetrik şifreleme algoritmaları ile şifreli olarak saklanmaktadır. Kuantum kriptografinin esas etkisi asimetrik kriptografiye olmasına rağmen simetrik şifreleme algoritmalarının anahtarları asimetrik kriptografi ile paylaşıldığı için tüm veriler kuantum tehtidinden etkilenmektedir. Özellikle şifrelenen verilerin geriye dönük olarak tutulabileceği göz önünde bulundurulursa ve yakın zamanda kuantum bilgisayların çarpanlara ayırma problemini etkili bir şekilde çözecek seviyeye gelmesi durumunda şu andan itibaren simetrik şifreleme algoritmaları ile şifrelenen veriler de ileride çözülebilecektir. İmza algoritmalarının etkilenmesi ise imzanın kimlik doğrulama mekanizmaları veya mesajın kaynağını doğrulamak gibi o ana ait bir kriptografik hizmeti sağladığı için daha kısıtlı olacaktır. Bu yüzden kuantum tehtidi için anahtar paylaşma probleminin çözümü imza probleminin çözümüne nazaran daha acil bir ihtiyaç olarak görülmektedir. Bu sebeplerle bu çalışmada kuantum sonrası kriptografinin anahtar paylaşma problemine getirdiği çözümler üzerinde durulacaktır. Burada bahsedilen her iki problem için de daha önceden AES'i blok şifreleme algoritması olarak bir yarışma aracılığıyla standartlaştıran NIST (Ulusal Standartlar ve Teknoloji Enstitüsü), standart bir algoritma seçmek için 2016 yılında bir yarışma başlatarak standart bir kuantum sonrası anahtar değişim algoritması ve imza algoritması seçme kararı almıştır. Bu süreçten sonra algoritma tasarımı ve analizi üzerine çalışmalar hızlanmıştır. Yarışmaya katılan algoritmalar dayandıkları zorluklara göre farklı gruplara ayrılabilir. Bunlar kafes tabanlı kriptosistemler, kod tabanlı kriptosistemler, isojeni tabanlı kriptosistemler, özet tabanlı kriptosistemler ve çok değişkenli polinom tabanlı kriptosistemlerdir. Bunların içinden en çok dikkat çeken ve üzerine çalışan homomorfik şifreleme gibi yapılarda da kullanılabilmesi itibariyle kafes tabanlı kriptosistemlerdir. Ayrıca yarışma neticesinde standart olarak seçilen Kyber Algoritması da kafes tabanlı bir anahtar değişim algoritmasıdır. Kod tabanlı kriptosistemler McEliece tarafından ortaya atılılmıştır ve asimetrik kriptografinin en eski problemlerinden biri olan kod çözme problemine dayanmaktadır. Anahtar boyutlarının büyük olması dezavantajından dolayı, kuantum tehditi ortaya çıkana kadar, görece az çalışılan bir alan olarak kalmıştır. Niederreiter kriptosisteminin ortaya çıkması ve anahtar boyutlarında iyileştirmeler yapılması ile kuantum sonrası anahtar değiştirme algoritmaları için önemli bir aday durumuna gelmişlerdir. Izojeni tabanlı algoritmalar klasik bilgisayarlarla kırılabilen bir saldırının ortaya çıkmasıyla riskli duruma düşmüştür. Her ne kadar NIST SIKE anahtar anlaşma algoritmasını alternatif algoritma adaylarına alsa da saldırı bu tarihten sonra ortaya çıktığı için kullanılması önerilmez ibaresi eklemiştir. Ayrıca bazı kriptosistemlerin analizi için üzerine yeterince çalışılmadığı düşünüldüğü için kuantum sonrası anahtar anlaşma algoritmalarının tek başına kullanılmasına şüpheyle bakılmaya başlanmıştır. Bu sebeple anahtar paylaşım problemini çözmek için kuantum sonrası algoritmalar, asimetrik kriptografi ve daha önce paylaşılmış ortak simetrik anahtarlardan en az iki tanesini kullanan hibrit anahtar paylaşım protokolleri de önerilmiştir. Bu çalışma kapsamında anahtar anlaşma problemini çözmek için geliştirilen önerilerden kabaca bahsedilecektir. Kafes tabanlı kriptosistemler ile Kod tabanlı kriptosistemlerin dayandıkları problemler ve bu problemler üzerine anahtar değişim mekanizmalarının nasıl kurulduğu anlatılacaktır. Ayrıca bazı analiz metotları anlatılarak standartta bulunan bazı algoritmaların güvenlik seviyeleri ve analizi hakkında bilgi verilecektir.

Özet (Çeviri)

With the discovery of quantum computers, the security of cryptosystems, which we call classical cryptography and used in all cryptographic devices, has become controversial. As a result of the rapid development in quantum computers, the field of study in cryptography has changed to design and analyze systems that are secure against quantum computers. Asymmetric cryptosystems are especially threatened by reducing the factorization problem from exponential time to polynomial time with Shor's Algorithm. Nowadays, most of the data is stored encrypted with symmetric encryption algorithms using the shared key with the key agreement algorithms used in classical cryptography. Although the main effect of quantum cryptography is asymmetric cryptography, all data is affected by the quantum threat since the keys of symmetric encryption algorithms are shared with asymmetric cryptography. Especially considering that the encrypted data can be kept retrospectively, and in the near future, if quantum computers come to a level that can effectively solve the factorization problem, the data encrypted with the AES algorithm from now on will also be able to be decrypted in the future. If signature algorithms are affected, the retrospective effect will be more limited as the signature provides a current cryptographic service, such as authentication mechanisms or verifying the origin of the message. Therefore, the solution of the key sharing problem for the quantum threat is seen as a more urgent need than the solution of the signature problem. For these reasons, this study will focus on the solutions brought by post-quantum cryptography to the key sharing problem. For both problems mentioned here, NIST (National Institute of Standards and Technology), which previously standardized AES as a block cipher algorithm through a competition, started a competition in 2016 to choose a post-quantum key exchange algorithm and a signature algorithm to choose a standard algorithm. After this process, studies on algorithm design and analysis accelerated. Algorithms participating in the competition can be divided into different groups according to the difficulties they rely on. These are lattice-based cryptosystems, code-based cryptosystems, isogeny-based cryptosystems, hash-based cryptosystems, and multivariate polynomial-based cryptosystems. Lattice-based cryptosystems are the most remarkable and can be used in structures such as homomorphic encryption that works on them. In addition, the Kyber Algorithm, which was chosen as a standard as a result of the competition, is a lattice-based key exchange algorithm. Isogeny-based algorithms have become risky with the emergence of an attack that can be cracked by classical computers. Although NIST has taken the SIKE key agreement algorithm to alternative algorithm candidates, it is not recommended to use since the attack occurred after this date. In addition, since it is thought that some cryptosystems have not been studied enough for the analysis, the use of post-quantum key agreement algorithms alone has begun to be viewed with suspicion. For this reason, hybrid key sharing protocols, which include at least two of the options of post-quantum algorithms, asymmetric cryptography and previously shared common symmetric key, have also been proposed to solve the key sharing problem. Within the scope of this study, the suggestions developed to solve the key agreement problem will be mentioned roughly. The problems of lattice-based cryptosystems and code-based cryptosystems and how key exchange mechanisms are built on these problems will be explained. In addition, some analysis methods will be explained and information will be given about the security levels and analysis of some algorithms in the standard. The use of lattice structures in cryptosystems first started with the study of Ajtai. In this study, Ajtai showed the worst-to-average-case reductions for lattice problems and paved the way for the use of these problems in cryptosystems. Following this development, the first lattice-based public-key encryption algorithm emerged by Ajtai and Dwork. With the study of Aharonov and Regev, the average-case learning with error problem and a public-key cryptosystem based on this problem have been proposed. In this cryptosystem, a structure in which 1-bit data is encrypted is shown. With the study of Lyubashevsky, the problem of learning with errors on the rings, which increases the amount of encrypted data, is introduced. With this structure, a mathematical structure was added to the problem of learning with errors. With the study of Langlois and Stehle, a module learning with error structure was introduced, which complicates this mathematical structure. During this study, learning with errors, ring learning with errors and module learning with errors will be defined. When transforming lattice structures into cryptosystems, problems such as learning with errors and shortest integer solution are used. The solution of these problems is based on the difficulty of solving basic lattice structure problems such as the shortest vector problem and the closest vector problem. In this study, the difficulty of learning with errors for lattice-based cryptosystems will be emphasized. It will be shown how the learning with errors problem is reduced to the shortest vector problem. LLL and BKZ algorithms are used to solve the shortest vector problem in lattice structures. The security of the algorithm is defined over the complexity of these algorithms. For these reasons, we will focus on how these algorithms work. The Kyber Algorithm is a lattice-based key encapsulation algorithm that uses the module learning with errors problem and is accepted as a standard by NIST. The Kyber Algorithm is explained in this study to be an example of lattice-based cryptosystems and to understand how the key encapsulation mechanism works. Code-based cryptosystems were introduced by McEliece. It is based on the decoding problem, which is one of the oldest problems of asymmetric cryptography. Due to the disadvantage of large key sizes, it remained a relatively understudied area until the quantum threat emerged. With the emergence of the Niederreiter cryptosystem and improvements in key sizes, it has become an important candidate for post-quantum key exchange algorithms. It started with information set decoding attacks with Prange Algorithm at 1962, which is the first type of attack described in code-based cryptosystems, and many algorithms have been developed using this technique. However, the attack complexity could not be significantly reduced. Therefore, the security of code-based cryptosystems has been studied more than other cryptosystems and is considered to be safe. In this study, in order to better understand code-based cryptosystems, the problems on which code-based cryptosystems are built are explained by giving information with basic level error correction codes. McEliece and Niederreiter cryptosystem is introduced. Besides McEliece algorithm, which is selected as an alternative by NIST from code-based key encapsulation algorithms, is shown as an example in this study. By giving the definition of the algorithm, the key encapsulation process is explained through the algorithm.

Benzer Tezler

  1. Tez No

    846982

    Developments in post-quantum cryptography

    Kuantum sonrası kriptografideki gelişmeler

    HASAN SARIŞIN

    Yüksek Lisans

    İngilizce

    İngilizce

    2024

    MatematikAnkara Yıldırım Beyazıt Üniversitesi

    Matematik Ana Bilim Dalı

    PROF. DR. FATİH KOYUNCU

  2. Tez No

    708796

    New efficient characteristic three polynomial multiplication algorithms and their applications to NTRU prime

    Yeni verimli karakteristik üç polinom çarpımı algoritmaları ve NTRU prime'a uygulamaları

    ESRA YENİARAS

    Doktora

    İngilizce

    İngilizce

    2022

    MatematikOrta Doğu Teknik Üniversitesi

    Kriptografi Ana Bilim Dalı

    DOÇ. DR. MURAT CENK

  3. Tez No

    468178

    İkinci dereceden çok değişkenli polinom sistemlerine dayanan imzalama algoritmalarının bileşenlerinin analizi ve açık kaynak kodlu uygulamaları

    Efficiency analysis of signature schemes based on multivariate quadratic polynamials and open source implementation

    EMRE ENGİN

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOndokuz Mayıs Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. SEDAT AKLEYLEK

  4. Tez No

    750001

    New TMVP-based multiplication algorithms for polynomial quotient rings and application to post-quantum cryptography

    Polinom halkaları için yeni TMVP-tabanlı çarpım algoritmaları ve quantum-sonrası kriptografiye uygulamaları

    İREM KESKİNKURT PAKSOY

    Doktora

    İngilizce

    İngilizce

    2022

    MatematikOrta Doğu Teknik Üniversitesi

    Kriptografi Ana Bilim Dalı

    PROF. DR. MURAT CENK

  5. Tez No

    731342

    Post-quantum cryptographic protocols based on isogenies of elliptic curves

    Eliptik eğrilerin izojenileri tabanlı kuantum sonrası kriptografik protokoller

    MEHMET EMİN GÖNEN

    Doktora

    İngilizce

    İngilizce

    2022

    MatematikGebze Teknik Üniversitesi

    Matematik Ana Bilim Dalı

    DOÇ. DR. SEHER TUTDERE KAVUT

    PROF. DR. OSMANBEY UZUNKOL

Geri Dön