O projektu Detalji
Classic McEliece CRYSTALS-KYBER NTRU SABER BIKE FrodoKEM HQC NTRU Prime SIKE
Preuzimanja Reference
Classic McEliece CRYSTALS-KYBER NTRU SABER BIKE FrodoKEM HQC NTRU Prime SIKE

Classic McEliece

Općenito o algoritmu

Classic McEliece je familija kandidata asimetričnih kriptografskih algoritama. Ideju samog algoritma osmislio je Robert McEliece 1978. godine, no tada nije ozbiljno razmotren njegov rad sve do danas kada nam se postepeno približava doba kvantnih računala. Unatoč njegovoj starosti, ovaj algoritam je nadmašio više od 40 godina napredaka u matematici i brojne pokušaje kriptoanalize.


Parametri

lgoritam je baziran na Goppinom kodiranju. To je vrsta zaštitnog kodiranja koju je definirao sovjetski matematičar Valerii Denisovich Goppa. Radi se o cikličkom kodiranju baziranom na (nadopuni) (dakle, generirajuća matrica se dobiva rotacijom bitova posebnog polinoma g(x)). Goppin kod je definiran s dva elementa:

  1. Polinomom stupnja t nad Galoisovim poljem GP (2m) bez višestrukih nultočaka
  2. Nizom L od n jedinstvenih elemenata iz tog Galoisovog polja koji nisu korijeni izabranog polinoma.

Komunikacijski kanal možemo vizualizirati sljedećom slikom:

komunikacijski kanal

Tako definirani kod ima distancu 2t + 1 te može ispraviti ((2t + 1) - 1)/2 pogrešaka u kodnim riječima duljine n - mt te se zbog mogućnosti ispravljanja velikog broja pogrešaka koristi u McEliece kriptosustavu. Ovo je primjer parametara koje koristi prvi od algoritama iz McEliece kriptosustava:

inačica m n t f F
mceliece348864 12 3488 64 z12+z3>+1 y64>+y3>+y+z

Zanimljivo svojstvo McEliece kriptosustava jest mogućnost da dekriptira bilo koji kriptirani tekst sa privatnim ključem neovisno o tome je li on stvarno nastao kriptiranjem odgovarajućim javnim ključem. Upravo se to svojstvo koristi za digitalno potpisivanje u Niederreiter-ovoj varijaciji McElieve kriptosustava.

Također, razina sigurnosti koju nudi je IND-CCA2 što znači da je otporan na sposobnost dedukcije privatnog ključa iz teoretski kooperativnog vlasnika koji za njega dekriptira arbitrarne kriptate (koje napadač može adaptirati prema prethodno poslanim kriptatima po svojoj želji).


Svojstva

Jedno od negativnih svojstava svih post-kvantnih kriptografskih algoritama koje ovdje obrađujemo jest veličina javnog ključa. Doduše, McEliece javni ključevi se kreću u veličinama od 26 KB do 1.35 MB ovisno o odabranim prethodno navedenim parametrima. Točne veličine su vidljive u sljedećoj tablici (vrijednosti veličina su u oktetima):

Inačica Javni ključ Privatnog ključ Kriptat Ključ sjednice
mceliece348864 261120 6492 128 32
mceliece348864f 261120 6492 128 32
mceliece460896 524160 13608 188 32
mceliece460896f 524160 13608 188 32
mceliece6688128 1044992 13932 240 32
mceliece6688128f 1044992 13932 240 32
mceliece6960119 1047319 13948 226 32
mceliece6960119f 1047319 13948 226 32
mceliece8192128 1357824 14120 240 32
mceliece8192128f 1357824 14120 240 32

Ove veličine ne čine ovaj kriptosustav pogodnim za ugrađene memorijski ograničene uređaje koji žele postići otpornost na napade kvantnih računala. Istovremeno, nije pogodan niti za blockchain tehnologiju gdje je mala veličina ključa od velike važnosti.


Stabilnost

Slabosti ovog kriptosustava obrađene su u brojnim analizama ( https://classic.mceliece.org/papers.html). Pronađene su ranjivosti u generaliziranim Reed-Solomon kodnim sustavima, no još do danas nisu pronađene iste za poseban podskup već spomenutih Goppa kodova sa opisanim svojstvima. Kada se koristi kod jačine k = (0.8 + o(1)) * n kada n -> ∞, čak i Prange-ov napad (1962., dekodiranje skupa informacija), koji jest prijetnja za sve sustave bazirane na kodovima, ima eksponencijalnu složenost (5+o(1))t (u najgorem slučaju, dakle je poznato da je njegovo rješavanje NP-težak problem). ‘t’ = (0.2 + O(1)) * n / log2(n) je jednak broju pogrešaka korištenih u sustavu. To je najbolji poznati napad kada struktura kodirajuće matrice nije dobro dizajnirana te su, naravno, uzimajući to u obzir, odabrani McEliece službeni polinomi čiji su nazivi navedeni u tablici iznad. Što se tiče kvantnih računala, ona kao i u drugim shemama reduciraju taj eksponencijalni faktor na pola (5+o(1))t/2 no to i dalje ostaje u domeni eksponencijalno složenih problema ako se ne pronađe efikasniji algoritam. Možemo zaključiti da je McEliece baziran na vrlo čvrstim temeljima, odnosno po svojoj prirodi teškom problemu ukoliko se ne pokaže da je milenijski problem P = NP istinit.


Reference