Sissejuhatus
1994. aastal arvutiteadlane Peter Shor avastasin et kui kvantarvutid kunagi leiutataks, hävitaksid need suure osa võrgus jagatava teabe kaitsmiseks kasutatavast infrastruktuurist. See hirmutav võimalus on pannud teadlasi otsima uusi "kvantjärgseid" krüpteerimisskeeme, et säästa kvanthäkkerite kätte sattumise eest nii palju teavet kui võimalik.
Selle aasta alguses riikliku standardi- ja tehnoloogiainstituut selgus neli finalisti postkvant-krüptograafia standardi otsingul. Kolm neist kasutavad võre krüptograafiat - võretest inspireeritud skeemi, punktide korrapärast paigutust ruumis.
Võre krüptograafia ja muud kvantijärgsed võimalused erinevad praegustest standarditest olulisel määral. Kuid nad kõik tuginevad matemaatilisele asümmeetriale. Paljude praeguste krüptograafiasüsteemide turvalisus põhineb korrutamisel ja faktoringul: iga arvuti suudab kiiresti korrutada kaks arvu, kuid krüptograafiliselt suure arvu arvestamine oma põhikomponentidesse võib võtta sajandeid. See asümmeetria muudab saladusi kergesti kodeeritavaks, kuid raskesti dekodeeritavaks.
Shor avastas oma 1994. aasta algoritmis, et faktooringu veidrus muudab selle haavatavaks kvantarvutite rünnakute suhtes. "See on väga spetsiifiline ja eriline asi, mida kvantarvuti suudab teha," ütles Katherine Stange, matemaatik Colorado ülikoolist Boulderis. Nii et pärast Shori oli krüptograafidel uus töö: leidke uudne matemaatiliste toimingute komplekt, mida on lihtne teha, kuid peaaegu võimatu tagasi võtta.
Võre krüptograafia on seni üks edukamaid katseid. Algselt 1990ndatel välja töötatud see tugineb punktide summade pöördprojekteerimise raskustele.
Siin on üks viis võre krüptograafia kirjeldamiseks. Kujutage ette, et teie sõbral on võre, mis on vaid hunnik punkte korrapärases, kogu tasapinnas korduvas mustris. Teie sõber soovib, et nimetaksite neist 10 punktist. Kuid tal on raske ja ta ei tõmba tervet võre välja. Selle asemel loetleb ta vaid kaks punkti - esimene on an x-väärtus 101 ja a y-väärtus 19, teine koordinaatidega [235, 44].
Õnneks on võre uute punktide leidmine lihtne, sest kui liidate ja lahutate võre suvalised kaks punkti, saate samasse võresse kolmanda punkti. Nii et kõik, mida pead tegema, on liita sõbra antud punktid või korrutada need täisarvudega ja seejärel liita või nende kahe kombinatsiooniga. Tehke seda kaheksal erineval viisil ja saate vastata oma sõbra küsimusele.
Kuid teie sõber pole ikka veel rahul. Ta annab teile kaks sama lähtepunkti ja küsib seejärel, kas punkt [2, 1] asub samal võrel. Sellele küsimusele õigesti vastamiseks peate leidma kombinatsiooni [101, 19] ja [235, 44], mis annab [2, 1]. See probleem on palju raskem kui esimene ja tõenäoliselt jääte vastuse saamiseks lihtsalt oletama ja kontrollima.* See asümmeetria on võre krüptograafia aluseks.
Kui soovite teabe jagamiseks kasutada võre krüptograafiat, toimige järgmiselt. Kujutage ette, et sõber (sobivam!) soovib teile turvalise sõnumi saata. Alustate numbrite ruudustikuga. Oletame, et sellel on kaks rida ja kaks veergu ning see näeb välja järgmine:
Nüüd leiate privaatse "võtme", mida teate ainult teie. Selles näites oletame, et teie privaatvõti on vaid kaks salanumbrit: 3 ja −2. Korrutate esimeses veerus olevad arvud 3-ga ja teise veeru numbrid -2-ga. Lisage iga rea tulemused, et saada kolmas kahe kirjega veerg.
Kleepige uus veerg ruudustiku lõppu. See uus kolmeveeruline ruudustik on teie avalik võti. Jaga seda vabalt!
(Tegelik stsenaarium on veidi keerulisem. Et häkkerid teie privaatvõtit ei dekodeeriks, peate oma viimasesse veergu lisama natuke juhuslikku müra. Kuid siin me jätame selle sammu lihtsuse huvides tähelepanuta. )
Nüüd kasutab teie sõber teile sõnumi saatmiseks avalikku võtit. Ta mõtleb välja kaks enda salanumbrit: 2 ja 0. Ta korrutab esimeses reas olevad numbrid 2-ga ja teise rea numbrid 0-ga. Seejärel liidab ta igas veerus saadud tulemused, et saada kolmas rida.
Nüüd kinnitab ta uue rea ruudustiku põhja ja saadab selle teile tagasi. (Jällegi, reaalses süsteemis peaks ta oma rida müra lisama.)
Nüüd loete sõnumit. Selleks kontrollid, kas sõbra viimane rida on õige. Rakendage oma privaatvõtit tema rea kahele esimesele kirjele. Tulemus peaks vastama viimasele kirjele.
Teie sõber võib ka saata teile rea, mille viimases veerus on vale number. Ta teab, et see arv ei vasta teie arvutustele.
Kui teie sõber saadab rea, kus viimane number on õige, tõlgendate seda kui 0. Kui ta saadab rea, kus number on vale, tõlgendate seda kui 1. Seetõttu kodeerib see rida üksikut bitt: kas 0 või 1.
Pange tähele, et välisel ründajal pole juurdepääsu ei teie ega teie sõbra privaatsele võtmele. Ilma nendeta pole ründajal aimugi, kas lõplik arv on õige või mitte.
Praktikas soovite saata sõnumeid, mis on pikemad kui üks bit. Nii et inimesed, kes soovivad saada näiteks 100-bitist sõnumit, loovad ühe veeru asemel 100 uut veergu. Seejärel loob sõnumi saatja ühe uue rea, muutes viimased 100 kirjet, et kodeerida iga kirje jaoks kas 0 või 1.
Kui võre krüptograafiat tegelikult rakendatakse, on sellel lugematu arv nüansse, mida see stsenaarium ei hõlma. Näiteks kui soovite, et sõnum oleks võõraste pilkude eest tõeliselt kaitstud, peab maatriksis olema mõeldamatu arv kirjeid, mis muudab kogu asja nii kohmakaks, et seda ei tasu kasutada. Sellest möödasaamiseks kasutavad teadlased kasuliku sümmeetriaga maatrikseid, mis võivad parameetrite arvu vähendada. Lisaks sellele on olemas terve komplekt näpunäiteid, mida saab rakendada probleemi enda, vigade lisamise ja muu jaoks.
Muidugi on alati võimalik, et keegi leiab võre krüptograafias saatusliku vea, täpselt nagu Shor tegi faktooringu puhul. Pole mingit kindlust, et konkreetne krüptograafiline skeem töötab igasuguse võimaliku rünnaku korral. Krüptograafia töötab seni, kuni see puruneb. Tõepoolest, selle suve alguses purustati üks paljutõotav postkvant-krüptograafia skeem kasutades mitte kvantarvutit, vaid tavalist sülearvutit. Stange'i jaoks tekitab kogu projekt ebamugava paradoksi: "Minu arvates on krüptograafias nii hämmastav see, et oleme inimrassi jaoks selle infrastruktuuri loonud kindlale veendumusele, et meie võimed inimestena on piiratud," ütles ta. "See on nii tagurlik."
*: vastus, kui olete uudishimulik, on 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [tagasi artikli juurde]
