SIKE
Općenito
SIKE je algoritam za enkapsulaciju ključeva zasnovan 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 2011. godine predložili Luca de Feo, David Jao i Jerome Plut.
Inačica SIKE (Supersingular Isogeny Key Encapsulation) se nalazi među alternativnim kandidatima u trećoj rundi NIST-ovog natječaja za izbor novih asimetričnih algoritama za uspostavu tajnog ključa otpornih na napade kvantnim računalom.
Tim koji je razvio SIKE čine: David Jao, Reza Azarderakhsh, Matthew Campagna, Craig Costello, Luca De Feo, Basil Hess, Aaron Hutchinson, Amir Jalali, Koray Karabina, Brian Koziel, Brian LaMacchia, Patrick Longa, Michael Naehrig, Geovandro Pereira, Joost Renes, Vladimir Soukharev i David Urbanik.
SIKE sadrži dva algoritma: CPA-zaštićeni algoritam šifriranja javnim ključem SIKE.PKE i CCA-siguran mehanizam za enkapsulaciju ključevima SIKE.KEM, svaki instanciran s četiri skupa parametara: SIKEp434, SIKEp503, SIKEp610 i SIKEp751.
Parametri
Javni parametri u SIKE-u su: dvije pozitivne cijele vrijednosti e2 i e3 koje definiraju konačno polje Fp2 gdje je p = 2e23e3 - 1, početna supersingularna eliptička krivulja E0 = Fp2, skup od tri x koordinate koje odgovaraju točkama u E0 [2e2] te skup od tri x koordinate koje odgovaraju točkama u E0 [3e3].
Tajni ključ
Algoritmi PKE i KEM zahtijevaju dva tajna ključa, sk2 i sk3, koji se koriste za izračunavanje 2e2-izogenije i 3e3-izogenije.
Supersingualni izogenijski par ključeva sastoji se od tajnog ključa skl>, koji je cijeli broj i skupa od tri x koordinate pkl = (xP, xQ, xR).
Šifriranje javnim ključem
Algoritam 1 definira shemu šifriranja javnim ključem PKE = (Gen, Enc, Dec). Veličina prostora za poruke M = {0, 1}n i funkcija F koja preslikava zajedničku tajnu j u nizove bitova ostaju neodređeni, a konkretni izbori odgovaraju implementaciji. Funkcija Enc generira slučajne vrijednosti u sk2. U slučaju mehanizma enkapsulacije ključa želimo te slučajne vrijednosti proslijediti kao ulaz pa se tada koristi write (c0, c1) ← Enc (pk3, m, sk2).
Enkapsulacija ključa
Algoritam 2 definira ključni mehanizam enkapsulacije KEM = (KeyGen, Encaps, Decaps) primjenom transformacija Hofheinza, Hövelmannsa i Kiltza u PKE. Ova transformacija je modificirana uključivanjem pk3 u ulaz u funkciju G i pojednostavljivanjem "ponovnog šifriranja". Veličina M = {0, 1}ni funkcije G i H ostaju neodređene, a konkretni izbori odgovaraju implementaciji.
Veličina parametara
Osam skupova parametara su SIKEp434, SIKEp434_compressed, SIKEp503, SIKEp503_compressed, SIKEp610, SIKEp610_compressed, SIKEp751 i SIKEp751_compressed, nazvani tako zbog duljina bitova osnovnog polja.
Očekivana razina sigurnosti
Pod pretpostavkom da dostupna memorija dopušta pohranu 280 jedinica, može se zaključiti da SIKEp434 i SIKEp610 udovoljavaju odgovarajućim sigurnosnim zahtjevima NIST-ovih kategorija 2 i 4. Nedavni članak Costella, Longe, Naehriga, Renesa i Virdije tvrdi da SIKEp751, za koji je isprva predloženo da zadovoljava razinu 3, zapravo ispunjava zahtjeve NIST-ove kategorije 5.
Početni prijedlog SIKE koristio je asimptotsku složenost Tanijevog kvantnog algoritma zajedno sa čvrstim donjim granicama broja kvantnih vrata korištenih u Fp-množenju i broju takvih množenja u tipičnom izračunu izogenije. Nedavno istraživanje Jaquesa i Schancka provodi mnogo detaljniju analizu najpoznatijih kvantnih algoritama za računsko rješavanje supersingualnog problema izogenije. Jaques i Schanck predlažu model kvantnog računanja koji dopušta izravnu usporedbu između kvantnih i klasičnih algoritama. Relevantno ograničenje za podudaranje sigurnosnih kategorija NIST nameće ograničenje dubine kvantnih krugova između 264 i 296. Dopuštajući dubine 296, Jaques i Schanck zaključuju da niti jedan poznati kvantni algoritam ne može slomiti SIKE u njihovom modelu proračuna s manje od 2143 klasičnih vrata i 2207 klasičnih vrata za SIKEp434 i SIKEp610. Stoga su ova dva skupa parametara prikladna za NIST kategorije 1 i 3. Skripte za izradu istih tablica za SIKEp503 i SIKEp751 sugeriraju da kvantni algoritam ne može slomiti one s manje od 2146, odnosno 2272 klasičnih vrata, što potvrđuje da su ovi skupovi parametara prikladni za NIST kategorije 2 i 5.
Analiza bočnih kanala napada cilja razne fizičke pojave koje emitira kriptografska implementacija kako bi se otkrile kritične interne informacije o uređaju. Informacije o potrošnji energije, informacije o vremenu i elektromagnetsko zračenje se emitiraju dok se izvode kriptografski algoritmi. Općenito, kriptografija zasnovana na izogeniji svodi se na dva izračuna: generiranje tajne jezgre i izračunavanje izogenije velikog stupnja nad tom jezgrom. U shemama poput SIKE pronađena je tajna jezgra izračunavanjem množenja dvostrukih točaka preko torzijske osnove. Dakle, postoje 2 opća pristupa koje napadač može iskoristiti za napad na sigurnost kriptosustava analizom bočnog kanala: otkrivanje dijelova skrivene točke jezgre i otkrivanje tajnih izogenih šetnji tijekom izračuna izogenije. Ciljajući ove dijelove SIKE kriptosustava, napadač bez sumnje ima pristup širokom spektru snaga, vremenu, kvaru i raznim drugim bočnim kanalima. Konstantne implementacije pomoću konstantnog skupa pokazale su se dobrom protumjerom protiv SPA i vremenskih napada. Međutim, napade diferencijalne analize snage i napade ubrizgavanja kvara puno je teže obraniti.