Kvantiniai kompiuteriai: Kriptografijos pabaiga?

Skelbimas

Kvantinis skaičiavimas yra viena iš tų technologijų, kurios yra tokios lanksčios, kad televizoriaus personažai, norėdami nuskambėti išmaniai, jį pameta.

Kvantinis skaičiavimas kaip idėja egzistavo kurį laiką - teorinę galimybę iš pradžių pristatė Jurijus Maninas ir Richardas Feynmanas 1982 m. Tačiau per pastaruosius kelerius metus ši sritis tapo nerimastinga ir artimesnė praktiškumui.

Tokios kompanijos kaip „Google“ ir „Microsoft“, taip pat vyriausybinės agentūros, tokios kaip NSA, jau daugelį metų karštligiškai vykdo kvantinius kompiuterius. Bendrovė, vadinama „D-Wave“, pagamino ir parduoda įrenginius, kurie (nors jie nėra tinkami kompiuteriai ir gali) atlikti tik keletą algoritmų) išnaudoti kvantines savybes ir yra dar vienas žingsnis kelyje link a visiškai Turing-complete Kas yra Turingo testas ir ar jis kada nors bus sumuštas?Turingo testas skirtas nustatyti, ar mašinos mąsto. Ar programa Eugene Goostman tikrai išlaikė Turingo testą, ar kūrėjai tiesiog apgavo? Skaityti daugiau kvantinis aparatas.

Neatrodo neprotinga sakyti, kad gali įvykti proveržis, kuris leis per dešimtmetį pastatyti pirmąjį didelio masto kvantinį kompiuterį.

Taigi kodėl visi susidomėjimai? Kodėl tau turėtų rūpėti? Kompiuteriai visą laiką spartėja Kas yra Moore'io dėsnis ir ką jis turi su jumis daryti? [„MakeUseOf“ paaiškina]Sėkmė neturi nieko bendra su Moore'io įstatymu. Jei tai yra asociacija, kurią turėjote, painiojate ją su Murphy įstatymu. Tačiau jūs nebuvote toli, nes Moore'io ir Murphy'io įstatymai ... Skaityti daugiau - kas gi ypatinga kvantiniuose kompiuteriuose?

Norėdami paaiškinti, kodėl šios mašinos yra tokios svarbios, turėsime atsitraukti ir tiksliai ištirti, kas yra kvantiniai kompiuteriai ir kodėl jie veikia. Norėdami pradėti, pakalbėkime apie sąvoką, vadinamą „runtime sudėtingumu“.

Kas yra „Runtime“ sudėtingumas?

Vienas didžiausių netikėtumų pirmosiomis informatikos dienomis buvo atradimas, kad jei turite kompiuterį, kuris išsprendžia tam tikras dydis per tam tikrą laiką, padvigubinęs kompiuterio greitį nebūtinai leidžia jį spręsti du kartus didelis.

Kai kurie algoritmai labai greitai ilgėja per visą vykdymo laiką, nes problemos mastas auga - kai kuriuos algoritmus galima greitai atlikti duotų 100 duomenų taškų, tačiau norint atlikti algoritmą, pateiktą 1000 duomenų taškų, reikės kompiuterio, kurio dydis yra Žemė, milijardas metų. Runtime sudėtingumas yra šios idėjos įforminimas: žiūrima, kaip greitai išauga problemos sudėtingumas, ir algoritmui klasifikuoti naudojama tos kreivės forma.

Paprastai šios sunkumų klasės yra išreikštos kaip funkcijos. Sakoma, kad algoritmas, kuris tampa proporcingai sunkesnis, kai padidėja duomenų rinkinio veikimas (kaip paprasta skaičiavimo funkcija), yra funkcija, kurios vykdymo laikas yra „n ” (kaip ir reikia n apdorojimo laiko vienetai n duomenų taškai).

Arba jis gali būti vadinamas „linijiniu“, nes jį nubraižydami gausite tiesę. Gali būti ir kitos funkcijos n ^ 2 arba 2 ^ n arba n! (n faktorinė). Tai yra polinomai ir eksponentai. Pastaruoju atveju du eksponentai auga taip greitai, kad beveik visais atvejais jų neįmanoma išspręsti niekuo, išskyrus labai nereikšmingus pavyzdžius.

Klaida ir kriptografija

Jei pirmą kartą girdite šią medžiagą ir ji skamba beprasmiškai ir keistai, pabandykime pagrįsti šią diskusiją. Kriptografija yra labai svarbi vykdymo laiko sudėtingumui, o tai palengvina iššifravimą žmonėms, kurie žino slaptą raktą, nei tiems, kurie to nedaro. Idealioje kriptografinėje schemoje iššifravimas turėtų būti tiesinis, jei turite raktą, ir 2 ^ k (kur k yra rakto bitų skaičius), jei to neturite.

Kitaip tariant, geriausias algoritmas, leidžiantis iššifruoti pranešimą be rakto, turėtų būti tiesiog atspėti galimus raktus, o tai neįmanoma padaryti klaviatūroje tik kelių šimtų bitų ilgio.

Simetrinei raktų kriptografijai (kurioje abi šalys turi galimybę saugiai pasikeisti paslaptimi prieš pradėdamos bendrauti) tai gana lengva. Asimetrinei kriptografijai tai sunkiau.

Asimetrinė kriptografija, kurioje šifravimo ir dešifravimo raktai skiriasi ir jų negalima lengvai apskaičiuoti vienas nuo kito, yra daug sunkiau matematinė. struktūra, kurią reikia įgyvendinti, nei simetrinė kriptografija, tačiau ji taip pat yra daug galingesnė: asimetrinė kriptograma leidžia jums užmegzti privačius pokalbius, net per bakstelėjus linijos! Tai taip pat leidžia jums sukurti „skaitmeninius parašus“, kad galėtumėte patikrinti, iš ko kilęs pranešimas, ir ar jis nebuvo suklastotas.

Tai yra galingos priemonės ir sudaro šiuolaikinio privatumo pagrindą: be asimetrinės kriptografijos elektroninių prietaisų vartotojai neturėtų patikimos apsaugos nuo smalsių akių.

Kadangi asimetrinę kriptografiją yra sunkiau sukurti nei simetrišką, šiandien naudojamos standartinės šifravimo schemos nėra tokios stiprios kokie jie gali būti: įprasčiausias šifravimo standartas RSA gali būti nulaužtas, jei efektyviai rasite pagrindinius labai didelio skaičius. Geros žinios yra tai, kad tai labai sunki problema.

Labiausiai žinomas algoritmas, leidžiantis įskaityti didelius skaičius į jų komponentus, yra vadinamas bendrojo skaičiaus lauko sietu, o jo vykdymo laikas yra sudėtingas ir auga šiek tiek lėčiau nei 2 ^ n. Dėl to raktai turi būti maždaug dešimt kartų ilgesni, kad būtų užtikrintas panašus saugumas - tai kažkas, ko žmonės paprastai toleruoja kaip verslo sąnaudas. Bloga žinia ta, kad kvantiniai kompiuteriai, įmesti į miksą, keičiasi visomis sąlygomis.

Kvantiniai kompiuteriai: kriptovaliutos keitimas

Kvantiniai kompiuteriai veikia todėl, kad jie gali turėti kelias vidines būsenas tuo pačiu metu per kvantinį reiškinį, vadinamą „superpozicija“. Tai reiškia, kad jie gali vienu metu užpulti skirtingas problemos dalis, išskaidydami galimas visatos versijas. Jie taip pat gali būti sukonfigūruoti taip, kad šakos, kurios išspręstų problemą, būtų suvytos su didžiausia amplitudė, kad atidarius langelį Schrodingerio katė, vidinės būsenos, kuri jums greičiausiai bus pristatyta, versija yra katės, turinčios smulkią išvaizdą, iššifruotos žinutė.

Norėdami gauti daugiau informacijos apie kvantinius kompiuterius, apsilankykite mūsų naujausias straipsnis šia tema Kaip veikia optiniai ir kvantiniai kompiuteriai?Artėja tremtinių amžius. Ar žinote, kaip veikia optiniai ir kvantiniai kompiuteriai, ir ar šios naujos technologijos taps mūsų ateitimi? Skaityti daugiau !

Rezultatas yra tai, kad kvantiniai kompiuteriai nėra tik tiesiškai greitesni, tokie, kokie yra normalių kompiuterių: gaunami du, dešimt ar šimtas kartų greitesnis sprendimas daug nepadeda, kai kalbama apie įprastą kriptografiją, kurios apdorojimas šimtai milijardų kartų yra per lėtas. Kvantiniai kompiuteriai palaiko algoritmus, kurių vykdymo laikas yra sudėtingesnis, nei įmanoma. Štai kodėl kvantiniai kompiuteriai iš esmės skiriasi nuo kitų būsimų skaičiavimo technologijų, pvz grafeno ir memristo skaičiavimas Naujausios kompiuterinės technologijos, kurias turite pamatyti, kad patikėtumėtePeržiūrėkite kai kurias naujausias kompiuterių technologijas, kurios per artimiausius kelerius metus pakeis elektronikos ir asmeninių kompiuterių pasaulį. Skaityti daugiau .

Konkrečiu pavyzdžiu, „Shor“ algoritmas, kuris gali būti vykdomas tik kvantiniame kompiuteryje, gali reikšti didelius skaičius žurnalas (n) ^ 3 laikas, kuris yra drastiškai geresnis už geriausią klasikinę ataką. Naudojant bendrojo skaičiaus lauko sietą skaičiui su 2048 bitų sudaryti reikia maždaug 10 ^ 41 laiko vienetų, o tai išeina daugiau nei trilijoną trilijonų trilijonų. Naudojant „Shor“ algoritmą, ta pati problema užtrunka tik apie 1000 laiko vienetų.

Efektas bus ryškesnis, kuo ilgesni klavišai. Tai yra kvantinių kompiuterių galia.

Nesupraskite manęs neteisingai - kvantiniai kompiuteriai naudoja daugybę galimų nenaudingų galimybių. Kvantiniai kompiuteriai gali efektyviai išspręsti keliaujančio pardavėjo problemą, leisdami tyrėjams sukurti efektyvesnius gabenimo tinklus ir suprojektuoti geresnes grandines. Kvantiniai kompiuteriai jau yra galingi dirbtinio intelekto naudojimo būdai.

Nepaisant to, jų vaidmuo kriptografijoje bus katastrofiškas. Šifravimo technologijos, leidžiančios mūsų pasauliui toliau funkcionuoti, priklauso nuo to, ar sunku išspręsti sveiko skaičiaus faktorizacijos problemą. RSA ir susijusios šifravimo schemos leidžia patikėti, kad esate tinkamoje svetainėje, ty kad failai atsisiuntimas nėra apkrautas kenkėjiška programine įranga ir kad žmonės nespėja naršyti internete (jei naudojate Tor).

Kriptografija saugo jūsų banko sąskaitą ir saugo pasaulio branduolinę infrastruktūrą. Kai kvantiniai kompiuteriai tampa praktiškais, visa ta technologija nustoja veikti. Pirmoji organizacija, sukūrusi kvantinį kompiuterį, jei pasaulis vis dar veikia tomis technologijomis, kurias naudojame šiandien, užims bauginančiai galingą padėtį.

Taigi, ar neišvengiama kvantinė apokalipsė? Ar galime ką nors padaryti? Kaip paaiškėja... taip.

Postkvantinė kriptografija

Yra kelios šifravimo algoritmų klasės, kurios, kiek mes žinome, nėra žymiai greitesnės nei kvantiniame kompiuteryje. Tai bendrai vadinama postkvantine kriptografija ir suteikia tam tikros vilties, kad pasaulis gali pereiti prie kriptosistemų, kurios išliks saugios kvantinio šifravimo pasaulyje.

Žadantys kandidatai apima grotelėmis pagrįstą šifravimą, pavyzdžiui, „Ring-Learning With Error“, kuris savo saugumą sukuria iš demonstruojamo sudėtingumo. mašininio mokymosi problema ir daugiamatė kriptografija, kurios saugumas kyla dėl to, kad sunku išspręsti labai dideles paprastų sistemų problemas. lygtys. Galite skaityti daugiau šia tema Vikipedijos straipsnis. Saugokitės: daug šios medžiagos yra sudėtinga, ir jūs galite pastebėti, kad jūsų matematikos pagrindus reikia gerokai padidinti, kad galėtumėte iš tikrųjų įsigilinti į detales.

Įsigiję daug ką, jūs pastebite, kad postkvantinės kriptoschemos yra labai šaunios, bet ir labai jaunos. Jiems reikia daugiau darbo, kad jie būtų veiksmingi ir praktiški, taip pat parodydami, kad yra saugūs. Priežastis, kad mes galime pasitikėti kriptosistemomis, yra tai, kad pakankamai ilgai išmetėme į juos kliniškai paranojiškus genijus kad bet kokie akivaizdūs trūkumai būtų buvę nustatyti jau dabar, o tyrėjai įrodė įvairias juos lemiančias savybes stiprus.

Šiuolaikinė kriptografija priklauso nuo šviesos, kaip dezinfekavimo priemonės, ir dauguma postkvantinių kriptografinių schemų yra tiesiog per daug naujos, kad pasitikėtų pasaulio saugumu. Vis dėlto jie ten nuvyksta ir, šiek tiek pasisekę bei šiek tiek pasiruošę, saugumo ekspertai gali užbaigti jungiklį, kol kada nors prisijungs pirmasis kvantinis kompiuteris.

Tačiau jei jų nepavyks padaryti, pasekmės gali būti skaudžios. Mintis apie tai, kas turi tokią galią, kelia nerimą, net jei optimistiškai vertinate jų ketinimus. Klausimas, kas pirmiausia sukuria veikiantį kvantinį kompiuterį, yra tas, kurį visi turėtų labai atidžiai stebėti, kai judame į kitą dešimtmetį.

Ar jums rūpi kriptografijos nesaugumas kvantiniuose kompiuteriuose? Ko tu imiesi? Pasidalykite savo mintimis komentaruose žemiau!

Vaizdo kreditai: Dvejetainė orb Per „Shutterstock“