Predstavitev
Leta 1994 računalničar Peter Šor odkril da če bi bili kdaj izumljeni kvantni računalniki, bi zdesetkali velik del infrastrukture, ki se uporablja za zaščito informacij, ki se delijo na spletu. Zaradi te zastrašujoče možnosti so se raziskovalci trudili izdelati nove, "postkvantne" šifrirne sheme, da bi čim več informacij rešili pred tem, da bi padle v roke kvantnih hekerjev.
V začetku tega leta je Nacionalni inštitut za standarde in tehnologijo je pokazala, štirje finalisti pri iskanju standarda postkvantne kriptografije. Trije od njih uporabljajo "mrežasto kriptografijo" - shemo, ki jo navdihujejo mreže, pravilne razporeditve pik v prostoru.
Mrežasta kriptografija in druge postkvantne možnosti se bistveno razlikujejo od trenutnih standardov. Toda vsi se zanašajo na matematično asimetrijo. Varnost mnogih trenutnih kriptografskih sistemov temelji na množenju in faktoriziranju: vsak računalnik lahko hitro pomnoži dve števili, vendar lahko traja stoletja, da faktorizira kriptografsko veliko število v njegove glavne sestavine. Zaradi te asimetrije je skrivnosti enostavno kodirati, vendar težko dekodirati.
Kar je Shor razkril v svojem algoritmu iz leta 1994, je bilo, da je faktoring ranljiv za napade kvantnih računalnikov. "To je zelo specifična, posebna stvar, ki jo lahko naredi kvantni računalnik," je dejal Katherine Stange, matematik na univerzi Colorado, Boulder. Tako so imeli po Shoru kriptografi novo nalogo: poiskati nov nabor matematičnih operacij, ki jih je enostavno izvesti, vendar jih je skoraj nemogoče razveljaviti.
Rešetkasta kriptografija je eden najuspešnejših poskusov doslej. Prvotno je bil razvit v devetdesetih letih 1990. stoletja in temelji na težavah povratnega inženiringa vsot točk.
Tukaj je en način za opis mrežne kriptografije: Predstavljajte si, da ima vaš prijatelj mrežo, ki je le kup točk v pravilnem, ponavljajočem se vzorcu po vsej ravnini. Vaš prijatelj želi, da navedete 10 od teh točk. Vendar je težaven in ne bo narisal celotne mreže. Namesto tega navaja samo dve točki - prvo z an x-vrednost 101 in a y-vrednost 19, drugo s koordinatami [235, 44].
Na srečo je enostavno najti nove točke na mreži, ker ko dodate in odštejete kateri koli dve točki na mreži, dobite tretjo točko v isti mreži. Torej vse, kar morate storiti, je, da seštejete točke, ki vam jih je dal prijatelj, ali jih pomnožite s celimi števili in jih nato seštejete ali uporabite kombinacijo obojega. Naredite to na osem različnih načinov in lahko boste odgovorili na prijateljevo vprašanje.
Toda vaš prijatelj še vedno ni zadovoljen. Dal vam je isti dve začetni točki, nato pa vas vpraša, ali je točka [2, 1] na isti mreži. Če želite pravilno odgovoriti na to vprašanje, morate najti kombinacijo [101, 19] in [235, 44], ki daje [2, 1]. Ta težava je veliko težja od prve in verjetno boste na koncu samo ugibali in preverjali, da bi dobili odgovor.* Ta asimetrija je tisto, kar je osnova mrežne kriptografije.
Če dejansko želite uporabiti mrežno kriptografijo za izmenjavo informacij, bi storili naslednje. Predstavljajte si, da vam prijatelj (prijaznejši!) želi poslati varno sporočilo. Začnete s kvadratno mrežo številk. Recimo, da ima dve vrstici in dva stolpca in je videti takole:
Zdaj dobite zasebni "ključ", ki ga poznate samo vi. V tem primeru recimo, da sta vaš zasebni ključ samo dve tajni številki: 3 in −2. Števila v prvem stolpcu pomnožiš s 3, tista v drugem stolpcu pa z −2. Seštejte rezultate v vsaki vrstici, da dobite tretji stolpec z dvema vnosoma.
Prilepite nov stolpec na konec mreže. Ta nova mreža s tremi stolpci je vaš javni ključ. Prosto delite!
(Scenarij iz resničnega sveta bo nekoliko bolj zapleten. Če želite hekerjem preprečiti dekodiranje vašega zasebnega ključa, morate v zadnji stolpec dodati malo naključnega hrupa. Vendar bomo zaradi poenostavitve ta korak prezrli. )
Zdaj bo vaš prijatelj uporabil javni ključ, da vam pošlje sporočilo. Zamisli si dve svoji skrivni števili: 2 in 0. Števili v prvi vrstici pomnoži z 2, tista v drugi vrstici pa z 0. Nato rezultate v vsakem stolpcu sešteje, da dobi tretjo vrstico.
Zdaj pritrdi novo vrstico na dno mreže in vam jo pošlje nazaj. (Spet v resničnem sistemu bi morala svoji vrsti dodati nekaj hrupa.)
Zdaj boste prebrali sporočilo. Če želite to narediti, preverite, ali je zadnja vrstica vašega prijatelja pravilna. Na prva dva vnosa v njeni vrstici uporabite svoj zasebni ključ. Rezultat se mora ujemati z zadnjim vnosom.
Vaš prijatelj se lahko tudi odloči, da vam pošlje vrstico z napačno številko v zadnjem stolpcu. Ve, da se ta številka ne bo ujemala z vašimi izračuni.
Če vaša prijateljica pošlje vrstico, v kateri je zadnja številka pravilna, boste to razumeli kot 0. Če pošlje vrstico, v kateri je številka napačna, jo boste razumeli kot 1. Vrstica torej kodira eno bit: 0 ali 1.
Upoštevajte, da zunanji napadalec ne bo imel dostopa niti do vašega zasebnega ključa niti do ključa vašega prijatelja. Brez tega napadalec ne bo vedel, ali je končna številka pravilna ali ne.
V praksi bi želeli poslati sporočila, ki so daljša od enega bita. Torej bodo ljudje, ki želijo prejeti, recimo, 100-bitno sporočilo, ustvarili 100 novih stolpcev namesto enega. Nato bo pošiljatelj sporočila ustvaril eno samo novo vrstico in spremenil zadnjih 100 vnosov tako, da bodo kodirali 0 ali 1 za vsak vnos.
Če se mrežasta kriptografija dejansko izvaja, bo imela nešteto odtenkov, ki v tem scenariju niso zajeti. Na primer, če želite, da je sporočilo resnično varno pred radovednimi očmi, mora imeti matrika nepredstavljivo veliko vnosov, zaradi česar je vse skupaj tako okorno, da se ga ne splača uporabljati. Da bi se temu izognili, raziskovalci uporabljajo matrike z uporabnimi simetrijami, ki lahko zmanjšajo število parametrov. Poleg tega obstaja cela zbirka popravkov, ki jih je mogoče uporabiti za samo težavo, za način vključitve napak in drugo.
Seveda je vedno mogoče, da bo nekdo našel usodno napako v mrežni kriptografiji, tako kot je Shor storil za faktoring. Nobenega zagotovila ni, da bo določena kriptografska shema delovala ob morebitnem napadu. Kriptografija deluje, dokler je ne razbijete. Res, v začetku tega poletja ena obetavna postkvantna kriptografska shema je bila vlomljena z uporabo ne kvantnega računalnika, ampak navadnega prenosnika. Za Stangeja celoten projekt ustvari neprijeten paradoks: "Kar se mi zdi tako neverjetno pri kriptografiji, je to, da smo to infrastrukturo za človeško raso zgradili na podlagi trdnega prepričanja, da so naše sposobnosti kot ljudi omejene," je dejala. "Tako zaostalo je."
*: Odgovor, če ste radovedni, je 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [nazaj k članku]
