Algoritmas, naudojamas kaip kriptografijos standartas kvantinių skaičiavimų eroje


algoritmo matematika

Kreditas: Unsplash/CC0 viešasis domenas

Matematikai dažnai triūsia nežinomybėje, ir tai greičiausiai todėl, kad tik nedaugelis žmonių, išskyrus kolegas matematikus, kurie dalijasi ta pačia subspecialybe, supranta, ką daro. Net kai algoritmai turi praktinių pritaikymų, pvz., padeda vairuotojams pamatyti artėjančius automobilius, kurių akis negali įžvelgti, nuopelnas tenka automobilių gamintojui (arba jo programinės įrangos kūrėjui).

Tai ypač pasakytina apie kriptografus – neapdainuotus herojus, kurių algoritmai apsaugo žmonių ryšius ir duomenis, kai jie naudojasi internetu – technologija, žinoma kaip viešojo rakto kriptografija.

Tačiau kartais gryna matematika paveikia realų pasaulį. Tai atsitiko šią vasarą, kai atrinko Nacionalinis standartų ir technologijų institutas keturi kriptografijos algoritmai bus naudojami kaip viešojo rakto saugumo standartai artėjančioje kvantinių kompiuterių eroje, dėl kurios dabartinės šifravimo sistemos greitai pasens.

Trys iš keturių pasirinktų algoritmų remiasi darbu, kuriam vadovauja Browno matematikų komanda: profesoriai Jeffrey Hoffstein, Joseph Silverman ir Jill Pipher (kuri taip pat yra Browno viceprezidentė tyrimams).

NIST patvirtinta istorija Falcon algoritmasir NTRU, viešojo rakto kriptosistema, kuria remiasi Falcon, prasidėjo 90-ųjų viduryje, kai kvantinis skaičiavimas vis dar buvo mokslinės fantastikos sferoje. Tuo metu Hoffsteino tikslas buvo sukurti algoritmą, kuris supaprastintų ir paspartintų įprastinių kriptografinių algoritmų veikimą; 1996 m. jis kartu su Silvermanu ir Pipheriu (kuris taip pat yra vedęs Hoffsteiną) įkūrė NTRU Cryptosystems Inc., siekdamas pateikti ją rinkai. Hoffsteinas teigė, kad NTRU istorija yra „kraują stingdanti saga“, tačiau galiausiai įmonei pasisekė – „Qualcomm“ rado tinkamą pirkėją. „Falcon“, kurį Hoffsteinas sukūrė kartu su devyniais kitais kriptografais, ir du iš trijų kitų pasirinktų NIST algoritmų yra sukurti remiantis originalia NTRU sistema.

Nuo pat doktorantūros studijų MIT iki visų pareigų Kembridžo universiteto Pažangiųjų studijų institute, Ročesterio ir Brauno universitete Hoffsteinas buvo „skaičių vaikinas“: „Man tai niekada neatėjo į galvą. nebūti matematiku“, – sakė jis. “Pažadėjau sau, kad ir toliau užsiimsiu matematika, kol nebebus smagu. Deja, vis tiek smagu!”

Remdamasis NIST atranka, Hoffsteinas aprašė savo transformaciją iš skaičių teoretiko į taikomąjį matematiką, išsprendęs artėjančią pasaulinę itin svarbią problemą.

Kl.: Kas yra viešojo rakto kriptografija?

Kai prisijungiate prie „Amazon“, kad apsipirktumėte, kaip žinoti, kad tikrai esate prisijungę prie „Amazon“, o ne su netikra svetaine, sukurta taip, kad atrodytų tiksliai kaip „Amazon“? Tada, kai siunčiate savo kredito kortelės informaciją, kaip ją išsiųsti nebijodami, kad ji bus perimta ir pavogta? Pirmasis klausimas išspręstas vadinamuoju skaitmeniniu parašu; antrasis sprendžiamas viešo rakto šifravimu. Iš NIST standartizuotų algoritmų vienas yra skirtas viešojo rakto šifravimui, o kiti trys, įskaitant Falcon, yra skirti skaitmeniniams parašams.

Jų esmė yra labai ypatingo tipo grynosios matematikos problemos. Jas sunku išspręsti (pagalvokite: laikas iki visatos pabaigos), jei turite vieną informaciją, ir nesunku (užtrunka mikrosekundes), jei turite papildomą slaptos informacijos dalį. Nuostabu yra tai, kad tik viena iš bendraujančių šalių – šiuo atveju „Amazon“ – turi turėti slaptą informaciją.

K: Koks yra kvantinių kompiuterių saugumo iššūkis?

Be pakankamai stipraus kvantinio kompiuterio, laikas išspręsti šifravimo problemą trunka eonus. Turint stiprų kvantinį kompiuterį, laikas problemai išspręsti sutrumpėja iki valandų ar mažiau. Jei kas nors turėtų stiprų kvantinį kompiuterį, visas interneto saugumas visiškai sugestų. O Nacionalinio saugumo agentūra ir didžiosios korporacijos lažinasi, kad per penkerius metus yra didelė tikimybė, kad bus sukurtas kvantinis kompiuteris, pakankamai stiprus, kad nutrauktų internetą.

Klausimas: Jūs sugalvojote NTRU sprendimą 90-ųjų pradžioje ar viduryje, gerokai anksčiau, nei visi galvoja apie potencialių kvantinių kompiuterių kriptografijos poreikius. Ką tuo metu galvojote?

Man atrodė, kad trys pagrindiniai viešojo rakto kriptografijos būdai yra labai nepatogūs ir neestetiški. Kaip vienas pavyzdys, labiausiai žinomas metodas, RSA, apima šimtų skaitmenų ilgio skaičius, tada jų padidinimą iki šimtų skaitmenų laipsnių, padalijus iš dar kito skaičiaus, kuris yra šimtų skaitmenų, ir pagaliau pasiima likusią dalį. Šį skaičiavimą nesunku atlikti kompiuteryje, tačiau jis nėra labai praktiškas, jei turite mažą, lengvą procesorių, pavyzdžiui, 1996 m. mobilųjį telefoną. RSA taip pat yra labai lėta – gerai, milisekundės, bet tai vis tiek laikoma lėta.

Mūsų svajonė buvo rasti viešojo rakto kriptografijos metodą, kuris būtų daug greičiau nei RSA ir galėtų veikti mažai galios įrenginiuose. Ir mes tai padarėme! Jį įdiegę žmonės galėjo jį paleisti 200–300 kartų didesniu greičiu nei RSA. Aš to dariau ne vienas – įkyriai galvojau apie problemą pusantrų metų, bet ji nesusiliejo į sprendimą, kol nesusidėjau su Joe Silvermanu ir Jill Pipher, mano Browno kolegomis ir NTRU įkūrėjais. .

K: Ką reiškia NTRU?

Niekada nesakėme – žmonės tiesiog manė, kad turime omenyje kažką techninio, ir pasitelkė savo vaizduotę! Bet tai reiškia „Skaičių teoretikai R Us“. Tai suerzino Džilę, nes ji yra harmonikų analitikė, o ne skaičių teoretikė, bet galiausiai ji man atleido.

Kl.: Apibūdinote savo startuolį NTRU Cryptosystems kaip turintį maždaug penkias „beveik mirties“ patirtis. Su kokiais iššūkiais susidūrėte?

Šios srities vartų sargai dažniausiai yra kriptografai, dirbantys įmonėse ir kompiuterių mokslo skyriuose. Neįtikėtinai sunku priversti bet kokį naują algoritmą priimti rimtai, o ypač sunku, jei nesate kriptografijos klube. Mūsų atveju pavojaus varpais skambėjome dėl dviejų priežasčių. Pavyzdžiui, mes buvome pašaliniai ir, norėdami padaryti viską efektyvesnį, pridėjome papildomą struktūrą nuo algebrinių skaičių teorijos iki gardelių.

Kai tai padarysite, kyla rimta rizika, kad netyčia įvedėte trūkumų. Taip, nuostabu ką nors padaryti efektyviau. Bet ar praradote kai kuriuos gyvybiškai svarbius saugumo elementus? Visiškai suprantama, kad žmonės labai įtariai žiūrėjo į šią papildomą struktūrą, kuri suteikė galimybę daugintis ir pridėti. Prireikė 10 metų intensyvaus tikrinimo, kol žmonės pradėjo pripažinti, kad nebuvo pridėta jokių trūkumų.

Klausimas: Tai nebuvo tik akademinis užsiėmimas. NTRU buvo įmonė, kuri turėjo dirbti su investuotojais ir potencialiais klientais. Anksti NTRU buvo neteisingai užpultas dokumente, parašytame kai kuriais buitiniais vardais kriptografijoje (kurie vėliau pripažino savo klaidą). Kaip NTRU tai išgyveno?

Paaiškėjo, kad jų dokumentas buvo iš esmės ignoruojamas, bet mūsų straipsnis buvo pakankamai įdomus, kad visi į jį įsitraukė. Jie bandė jį pulti ir sunaikinti, ir tai sulaukė didžiulio dėmesio. Kiekvienas paviršius, kurį galite įsivaizduoti, buvo apimtas mušančių avinų. Kriptografijos bendruomenė buvo tokia atspari matematikų įsiveržimui į jų velėną. Jei nebūtume buvę žinomi Browno matematikai, nebūtume išgyvenę ginčo. Galų gale tas dėmesys tikriausiai mums padėjo.

Kl.: Ar buvo kokių nors būdų, kaip būti matematiku – autsaideriais, šiame pasaulyje – buvo pranašumas?

Dalykas, kuriuo aš didžiuojuosi, nebūtinai yra tai, kad konkretus algoritmas atsidūrė paskutiniuose keturiuose NIST pasirinkimuose, nors kiekvienas iš trijų gardelės algoritmų naudoja mūsų žiedo struktūrą (daugybos funkciją). Jie visi naudoja matematiką, kurią mes įvedėme, nes po daugiau nei 25 metų tikrinimo nebuvo pastebėta nė vienos silpnybės dėl šios struktūros pridėjimo. Ta matematika, kilusi iš algebrinės skaičių teorijos, anksčiau nebuvo kriptografijos dalis. Tai yra dalis to, ką darau dėl savo kito gyvenimo, ir man ypač malonu, kad mums pavyko pasinaudoti šiuo visiškai abstrakčiu teoriniu dalyku, kuris, matyt, visiškai nenaudingas, ir rasti praktinį pritaikymą. Todėl dabartinė kriptografų karta turi išmanyti algebrinę teoriją, o tai savotiškai smagu.

Kl.: Ką reiškia būti susituokusiam su kitu matematiku?

Palaimingiausias dalykas visatoje yra susituokus su žmogumi, kuris supranta, ką reiškia būti matematiku. Matematikos srityje 99,9 % laiko praleidžiate valandas, savaites, mėnesius ir metus galvodami apie tai, kas neįvyksta. Daug kartų manote, kad turite fantastišką idėją, bet ji niekur nedingsta. Nuostabu būti vedusiam su žmogumi, kuris supranta tą jausmą, net jei ne visada suprantame smulkmenas, ką kitas dirba.

Kl.: Ji supranta, kada esi pasiklydęs mintyse?

Taip, ir ji tikriausiai taip pat.


NIST paskelbė pirmuosius keturis kvantiniams atsparius kriptografinius algoritmus


Citata: Klausimai ir atsakymai: Algoritmas, naudojamas kaip kriptografijos standartas kvantinio skaičiavimo eroje (2022 m. rugsėjo 22 d.), gautas 2022 m. rugsėjo 23 d. iš https://phys.org/news/2022-09-qa-algorithm-cryptography-standard-quantum.html

Šis dokumentas yra saugomas autorių teisių. Išskyrus bet kokius sąžiningus sandorius privačių studijų ar mokslinių tyrimų tikslais, jokia dalis negali būti atkuriama be raštiško leidimo. Turinys pateikiamas tik informaciniais tikslais.