3.5. Post-kvantna kriptografija

Od poznatih algoritama za kvantna računala, dva su vrlo relevantna za kriptoanalizu: Groverov i Shorov. Groverov algoritam ubrzava pretraživanja nesortiranih datoteka, te pomoću njega napadi "grubom silom" postaju puno učinkovitiji (kod simetričnih kriptosustava to bi značilo da će biti potreban otprilike dvostruko duži ključ da se zadrži sadašnja razina sigurnosti). Shorov algoritam koristi činjenicu da kvantne metode omogućavaju vrlo brzo računanje perioda periodičnih funkcija. To daje polinomijalne kvantne algoritme za probleme faktorizacije i diskretnog algoritma. To znači da bi efektivna konstrukcija dovoljno snažnih kvantnih računala učinila neupotrebljivim kriptosustave javnog ključa zasnovane na faktorizaciji (RSA, Rabin) i problemu diskretnog logaritma (ElGamal, ECC).

Grana kriptografije koja se bavi dizajniranjem i analizom kriptosustava koji bi bili otporni i na napade koje bi realizirala kvantna računala naziva se post-kvantna kriptografija. Post-kvantna kriptografija je poseban zamah dobila raspisivanjem natječaja za post-kvantne kriptografske standarde, koji je NIST raspisao 2017. godine. Na natječaj se javilo 59 prijedloga za kriptosustave s javnim ključem i protokole za razmjenu ključeva, te 23 algoritma za digitalne potpise. Godine 2019. je izabrano ukupno 26 prijedloga koji su prošli u drugu rundu natječaja. U srpnju 2020. lista je dodatno reducirana te je objavljeno 7 finalista treće runde natječaja, uz još 8 alternativnih kandidata. Konačan izbor standarda se očekuje do 2024. godine.

Opisat ćemo dva kriptosustava za koja se smatra da bi mogli biti sigurni i u eri kvantnih računala. Oni su nastali dosta prije NIST-ovog natječaja, ali se njihove inačice nalaze među kandidatima koji su se javili na natječaj i prošli u drugu i treću rundu. To su McElieceov kriptosustav i NTRU kriptosustav.

U McElieceovom kriptosustavu (Robert McEliece, 1978) koristi se ideja slična ideja onoj koju smo vidjeli kod Merkle-Hellmanovog kriptosustava. Ovdje je pripadni NP-potpuni problem dekodiranje općih linearnih kodova za ispravljanje grešaka. Kao osnova u ovom kriptosustavu koristi se specijalna klasa Goppinih kodova za koje postoji polinomijalni algoritam za dekodiranje.

Neka su k i n prirodni brojevi, k ≤ n. Binarni linearni [n,k]-kod C je k-dimenzionalni potprostor vektorskog prostora (Z₂)ⁿ. Generirajuća matrica za linearni kod C je k × n matrica G čiji redci tvore bazu za C.

Za x = (x₁, ..., x_n), y = (y₁, ..., y_n) ∈ (Z₂)ⁿ, definiramo Hammingovu udaljenost s

d(x,y) = |{i : 1 ≤ i ≤ n, x_i ≠ y_i}|,

d = d(C) = min {d(x,y) : x, y ∈ C, x ≠ y}.

Primjer jednog [7,4,3]-koda dan je sljedećom generirajućom matricom:

G =	1 0 0 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 1 1 1 1

Svrha kodova za ispravljanje grešaka jest da isprave slučajne greške koje mogu nastati prilikom prenošenja binarnih podataka preko kanala sa "šumom" (engl. chanell with noise). Neka je G generirajuća matrica za [n,k,d]-kod C. Pretpostavimo da je x binarna k-torka koju Alice želi prenijeti Bobu preko kanala sa šumom. Tada Alice kodira x kao n-torku y = xG, te pošalje y preko kanala. Bob primi n-torku r koja se, budući da kanal ima šum, ne mora podudarati s y. Da bi dekodirao r, Bob traži element ("kodnu riječ") y' ∈ C koja ima najmanju Hammingovu udaljenost od r, te potom izračuna k-torku x' takvu da je y' = x'G. Tada Bob može očekivati da je y' = y, pa onda i x' = x, tj. da je uspio ispraviti sve greške nastale prilikom prijenosa. Nije teško vidjeti da ukoliko broj grešaka nije veći od (d-1)/2, onda se na ovaj način mogu "ispraviti sve greške", tj. može se jednoznačno rekonstruirati poslana poruka. Primijetimo analogiju, ali i razliku između pojmova šifriranje-dešifriranje i kodiranje-dekodiranje.

Pokazuje se da je problem nalaženja najbliže kodne riječi vrlo težak problem za opće linearne kodove. No, postoje kodovi za koje postoje efikasni algoritmi za dekodiranje. McEliece je 1978. godine predložio da se jedna klasa takvih kodova, tzv. Goppini kodovi, iskoristi u konstrukciji kriptosustava s javnim ključem. Parametri Goppinih kodova imaju oblik n = 2^m,   d = 2t + 1,   k = n - mt.

Slijedi definicija McElieceovog kriptosustava.

Neka je G generirajuća matrica za [n,k,d]-kod C. Neka je S invertibilna k × k matrica nad Z2, te P n × n permutacijska matrica (u svakom retku i svakom stupcu ima točno jednu jedinicu, a svi ostali elementi su nule). Stavimo G'= SGP. Sada definiramo P = (Z2)k, C = (Z2)n, K = { (G,S,P,G') }, gdje su G, S, P, G' konstruirani na prije opisani način. Ovdje je G' javni, a G,S,P tajni ključ. Za K = (G,S,P,G') ∈ K, definiramo eK(x,e) = xG' + e, gdje je e ∈ (Z2)n slučajno generirani vektor težine t = (d-1)/2 (ima t jedinica, a ostalo su nule). Šifrat y ∈ (Z2)n se dešifrira na sljedeći način. Najprije se izračuna y1 = yP-1. Potom se dekodira y1, i tako se dobije kodna riječ x1 ∈ C koja je najbliža y1 (budući da je P permutacijska matrica, imamo da je y1 = xSG + e1, gdje je e1 = eP-1 binarni niz težine t = (d-1)/2, pa znamo da mora vrijediti da je x1 = xSG). Izračuna se x0 ∈ (Z2)k, takav da je x0G = x1. Konačno se izračuna x = x0S-1.

Uočimo da y₁ možemo dekodirati jer je kodiran Goppinim kodom G, a y ne možemo jer je kodiran s G' za koji nemamo efikasan algoritam za dekodiranje. McEliece je predložio korištenje Goppinog koda s parametrima [1024, 524, 101]. Otvoreni tekst je binarna 524-torka, a odgovarajući šifrat je binarna 1024-torka. Javni ključ je 524 × 1024 binarna matrica. Do danas nije poznat niti jedan efikasan napad na McElieceov kriptosustav. Važan nedostatak mu je ogromna veličina javnog ključa. Jedna njegova inačica je jedan od finalista u trećoj rundi NIST-ovog natječaja za post-kvantne kriptografske standarde.

Primjer 3.6: Ilustrirat ćemo šifriranje i dešifriranje pomoću McElieceovog kriptosustava sa sasvim malim parametrima. Za G ćemo uzeti prethodno navedenu generirajuću matricu za [7,4,3]-kod. Za matrice S i P uzmimo:

S =	1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1

P =	0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0

Sada je Bobov javni ključ

G' =	0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1 0 0

Pretpostavimo da Alice želi poslati Bobu poruku x = (1,0,1,1), te da je izabrala slučajni vektor e = (0,1,0,0,0,0,0) (s jednom jedinicom). Tada Alice pošalje Bobu šifrat y = (0,0,0,1,1,0,0).

Bob računa y₁ = yP^-1 = (0,0,1,0,0,0,1). Sada Bob treba dekodirati y₁. Jedna metoda koja je praktična za ovako male dimenzije je korištenje tzv. sindroma. Kodu G pridružimo njegovu matricu provjere parnosti H, što je (n-k) × n matrica čiji redci tvore bazu za ortogonalni komplement od C (koji se naziva dualni kod od C i označava C^⊥). Za našu matricu G je

H =	1 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 1 1 0 0 1

Sindrom od r ∈ (Z₂)ⁿ je s = Hr^T. Ako se vektor s sastoji od samih nula, onda r dekodiramo kao r. U protivnom, generiramo sve moguće e₁ vektore s težinom 1, te računamo He₁^T. Ako za neki od tih vektora e₁ vrijedi He₁^Ts, onda r dekodiramo kao r - e₁. Postupak nastavljamo s vektorima težine 2, 3, ..., ⌊(d-1)/2⌋. U našem slučaju, računamo sindrom od y₁ i dobivamo Hy₁^T = (0,1,0)^T. Sada tražimo vektor e₁ težine 1 sa svojstvom He₁^T = (0,1,0)^T. Nalazimo da je e₁ = (0,0,0,0,0,1,0), pa y₁ dekodiramo kao x₁ = (0,0,1,0,0,1,1). Sada treba naći x₀ takav da je x₀G = x₁. No, zbog specijalnog oblika od G, x₀ čine upravo prve četiri komponente od x₁, tj. x₀ = (0,0,1,0). Konačno, otvoreni tekst x dobivamo računajući x = x₀S^-1 = (1,0,1,1).

Jedan od najzanimljivijih novijih kriptosustava, koji je još uvijek predmet intenzivnog proučavanja, je NTRU kriptosustav (od "Nth degree TRUncated polynomials"), koji su 1997. godine predložili Jeffrey Hoffstein, Jill Pipher i Joseph Silverman. U ovom se kriptosustavu kod šifriranja koriste polinomi. Preciznije, koristi se prsten R = Z[X]/(X^N -1). Na elementima od R definira se operacija cikličke konvolucije, tj. za F = Σ_i=0^N-1 F_i xⁱ, G = Σ_i=0^N-1 G_i xⁱ, definira se H = F ⊛ G = Σ_k=0^N-1 H_k x^k ∈ R s

H_k = Σ_{i+j≡k (mod N)} F_i G_j.

Da bi kreirao svoje NTRU ključeve, Bob na slučajan način izabire dva polinoma f, g ∈ R. Polinom f mora zadovoljavati uvjet da ima inverze modulo p i modulo q. Ako je p prost, onda se inverz od f računa primjenom proširenog Euklidovog algoritma na polinome f i x^N-1 u prstenu polinoma Z_p[x], a ako je p složen, onda se, slično kao kod rješavanja kongruencija, inverz po prostom modulo "podigne" do inverza po potenciji prostog broja, a inverzi koji odgovaraju različitim prostim brojevima "kombiniraju" primjenom Kineskog teorem o ostatcima.

Označimo te inverze s F_p i F_q, tj.

F_p ⊛ f ≡ 1 (mod p),     F_q ⊛ f ≡ 1 (mod q).

h ≡ F_q ⊛ g (mod q).

Pretpostavimo da Alice želi poslati Bobu poruku m, za koju ćemo pretpostaviti da je također element skupa R (obično se uzima da su koeficijenti tog polinoma iz segmenta [-p/2, p/2]). Ona izabire slučajan polinom r ∈ R i koristi Bobov javni ključ da izračuna

e ≡ p ^. r ⊛ h + m (mod q).

Kad Bob primi šifrat e, najprije pomoću svog tajnog ključa f izračuna

a ≡ f ⊛ e (mod q),

m ≡ F_p ⊛ a (mod p).

Provjerimo hoće li Bob na ovaj način zaista dešifrirati šifrat. Imamo:

a ≡ f ⊛ e ≡ f ⊛ (p ^. r) ⊛ h + f ⊛ m ≡ f ⊛ (p ^. r) ⊛ F_q ⊛ g + f ⊛ m
≡ p ^. r ⊛ g + f ⊛ m (mod q).

a = p ^. r ⊛ g + f ⊛ m     (u R).

F_p ⊛ a ≡ F_p ⊛ f ⊛ m ≡ m (mod p).

Bob izabire polinome

f(x) = x⁶ - x⁴ + x³ + x² - 1,   g(x) = x⁶ + x⁴ - x² - x,

F_p = f(x)^-1 mod p = x⁶ + 2x⁵ + x³ + x² + x + 1,   F_q = f(x)^-1 mod q = 8x⁶ + 26x⁵ + 31x⁴ + 21x³ + 40x² + 2x + 37

h(x) = F_q ⊛ g = 20x⁶ + 40x⁵ + 2x⁴ + 38x³ + 8x² + 26x + 30.

m(x) = -x⁵ + x³ + x² - x + 1

r(x) = x⁶ - x⁵ + x - 1.

e(x) ≡ p r(x) ⊛ h(x) + m(x) ≡ 31x⁶ + 19x⁵ + 4x⁴ + 2x³ + 40x² + 3x + 25 (mod q).

f(x) ⊛ e(x) ≡ x⁶ + 10x⁵ - 8x⁴ - x³ - x² + x - 1 (mod q),

F_p ⊛ a ≡ -x⁵ + x³ + x² - x + 1 (mod p),

Šifriranje i dešifriranje kod NTRU kriptosustava je usporedive brzine kao kod RSA kriptosustava. No, poznato je nekoliko mogućih napada na NTRU koji koriste LLL-algoritam za nalaženje najkraćeg elementa u rešetki. Također, postoje i napadi koji koristi činjenicu da u NTRU-u postoje šifrati koje je nemoguće dešifrirati (postoji vrlo mala vjerojatnost da će neki koeficijent polinoma p ^. r ⊛ g + f ⊛ m biti izvan segmenta [-q/2, q/2]). Zasad nije sasvim jasno koliko su ti napadi ozbiljna prijetnja za sigurnost ovog kriptosustava. Dvije inačice NTRU kriptosustava, jedna nastala spajanjem kandidata iz prve runde NTRUEncrypt i NTRU-HRSS-KEM te druga NTRU Prime, bile su među finalistima druge runde NIST-ovog natječaja za post-kvantne kriptografske standarde, te je prva inačica prošla i u treću rundu, dok se druga inačica nalazi među alternativnim kandidatima.

Većina predloženih post-kvantnih kriptografskih algoritama su povezani ili s kodovima (poput McElieceovog) ili s rešetkama (poput NTRU). Spomenimo da postoje i post-kvantni algoritmi zasnovani na svojstvima izogenija supersingularnih eliptičkih krivulja, od kojih je najpoznatiji protokol za razmjenu ključeva SIDH (supersingular isogeny Diffie-Hellman key exchange), kojeg su predložili Luca de Feo, David Jao i Jerome Plut 2011. godine. Inačica SIKE (Supersingular Isogeny Key Encapsulation) se nalazi među alternativnim kandidatima u trećoj rundi NIST-ovog natječaja.