Kvantarvutid: krüptograafia lõpp?

Reklaam

Kvantarvutamine on üks neist tehnoloogiatest, mis on nii aromaatne, et telekangelased panevad selle nutika kõlamise korral selle maha.

Kvantarvutamine kui idee on olnud juba mõnda aega olemas - teoreetilise võimaluse tutvustasid algselt Juri Manin ja Richard Feynman 1982. aastal. Viimase paari aasta jooksul on valdkond siiski murettekitavalt lähenenud praktilisusele.

Ettevõtted nagu Google ja Microsoft, aga ka valitsusasutused nagu NSA, on kõik nüüd palavikuliselt kvantarvuteid jälitanud. Firma nimega D-Wave on tootnud ja müüb seadmeid, mis (kuigi nad pole korralikud arvutid, aga saavad) kasutage ainult mõnda algoritmi) kvantomaduste ärakasutamine ja see on veel üks järkjärguline samm teel a-le täielikult Turing-täielik Mis on Turingi test ja kas seda kunagi võidetakse?Turingi testi eesmärk on teha kindlaks, kas masinad mõtlevad. Kas Eugene Goostmani programm läbis Turingi testi tõesti või tegid loojad lihtsalt petmise? Loe rohkem kvantmasin.

Ei tundu mõistlik öelda, et võib toimuda läbimurre, mis võimaldab esimese suuremahulise kvantarvuti ehitada kümne aasta jooksul.

Miks siis kogu huvi? Miks sa peaksid hoolima? Arvutid muutuvad kogu aeg kiiremaks Mis on Moore'i seadus ja mis sellel on teiega pistmist? [MakeUseOf selgitab]Halval õnnel pole Moore'i seadusega mingit pistmist. Kui see on ühendus, mis teil oli, ajate selle segamini Murphy seadusega. Kuid te ei olnud kaugel, sest Moore'i seadus ja Murphy seadus ... Loe rohkem - Mis on kvantarvutites nii erilist?

Selgitamaks, miks need masinad on nii olulised, peame astuma sammu tagasi ja uurima, mis täpselt on kvantarvutid ja miks need töötavad. Alustuseks räägime kontseptsioonist, mille nimi on käitusaja keerukus.

Mis on Runtime keerukus?

Arvutiteaduse esimestel päevadel oli üheks suureks üllatuseks avastus, et kui teil on arvuti, mis lahendab teatud suurusega teatud aja jooksul, ei võimalda arvuti kiiruse kahekordistamine tingimata kaks korda probleeme lahendada suur.

Mõni algoritm suureneb kogu täitmisaja jooksul väga kiiresti, probleemi suuruse kasvades - mõnda algoritmi saab kiiresti täita 100 andmepunkti, kuid 1000 andmepunktiga algoritmi täitmiseks oleks vaja arvutit, mille suurus Maa töötab miljardi aastatel. Tööaja keerukus on selle idee vormistamine: see vaatab kõveralt, kui kiiresti probleem keerukus kasvab, ja kasutab algoritmi klassifitseerimiseks selle kõvera kuju.

Üldiselt väljendatakse neid raskusklasse funktsioonidena. Algoritmi, mis muutub proportsionaalselt raskemaks, kui andmekogum töötab edasi (nagu lihtne loendusfunktsioon), öeldakse olevat funktsiooni, mille käitusaeg on keerukas „n ” (nagu ka, see võtab n töötlemise ajaühikud n andmepunktid).

Teise võimalusena võib seda nimetada “lineaarseks”, sest graafiku koostamisel saate sirge. Muud funktsioonid võivad olla n ^ 2 või 2 ^ n või n! (n faktoriaal). Need on polünoomsed ja eksponentsiaalsed. Kahel viimasel juhul kasvavad eksponentsiaalsed nii kiiresti, et peaaegu kõigil juhtudel pole neid võimalik lahendada, välja arvatud väga triviaalsed näited.

Kestus keerukus ja krüptograafia

Kui kuulete seda kraami esimest korda ja see kõlab mõttetu ja arukaks, proovime seda arutelu maandada. Tööaja keerukus on krüptograafia jaoks kriitilise tähtsusega, mis põhineb salajase võtme tundvate inimeste dekrüptimise lihtsustamisel palju hõlpsamaks kui nende jaoks, kes seda ei tee. Ideaalses krüptograafilises skeemis peaks dekrüptimine olema lineaarne, kui teil on võti, ja 2 ^ k (kus k on võtmes bittide arv), kui te seda ei tee.

Teisisõnu, parimaks algoritmiks sõnumi dekrüpteerimiseks ilma võtmeta peaks olema lihtsalt võimalike võtmete äraarvamine, mis on vaid paarsada bitti pikkuste võtmete jaoks vaevamatu.

Sümmeetrilise võtme krüptograafia jaoks (milles kahel osapoolel on võimalus enne suhtluse alustamist turvaliselt saladust vahetada) on see üsna lihtne. Asümmeetrilise krüptograafia jaoks on see raskem.

Asümmeetriline krüptograafia, milles krüpteerimis- ja dekrüpteerimisvõtmed on erinevad ja mida ei saa üksteisest hõlpsasti arvutada, on palju raskem matemaatiline rakendatav struktuur kui sümmeetriline krüptograafia, kuid see on ka palju võimsam: asümmeetriline krüpto võimaldab privaatseid vestlusi pidada isegi üle koputades read! See võimaldab teil luua ka „digitaalallkirju”, mis võimaldavad teil kontrollida, kelle sõnum tuli ja kas seda ei ole rikutud.

Need on võimsad tööriistad ja moodustavad tänapäevase privaatsuse aluse: ilma asümmeetrilise krüptograafiata poleks elektrooniliste seadmete kasutajatel usaldusväärset kaitset uteliaalsete silmade eest.

Kuna asümmeetrilist krüptograafiat on raskem üles ehitada kui sümmeetrilist, pole tänapäeval kasutatavad standardsed krüptimisskeemid nii tugevad nagu need võiksid olla: kõige tavalisemat krüptimisstandardit RSA saab hävitada, kui suudate tõhusalt leida väga suure algteguri number. Hea uudis on see, et see on väga raske probleem.

Tuntuimat algoritmi suurte arvude faktoriseerimiseks nende komponendi alusteks nimetatakse üldiseks numbrivälja sõelaks ja selle käitusaja keerukus kasvab pisut aeglasemalt kui 2 ^ n. Selle tagajärjel peavad võtmed olema umbes kümme korda pikemad, et pakkuda sarnast turvalisust, mida inimesed tavaliselt ettevõtluse kuludena taluvad. Halb uudis on see, et kui kvantarvutid segamini visatakse, muutub kogu mänguväli.

Kvantarvutid: krüptomängu muutmine

Kvantarvutid töötavad sellepärast, et neil võib olla samaaegselt mitu sisemist olekut kvantnähtuse kaudu, mida nimetatakse „superpositsiooniks”. See tähendab, et nad saavad üheaegselt rünnata probleemi erinevaid osi, jaotades need universumi võimalike versioonide vahel. Neid saab konfigureerida ka nii, et harusid, mis probleemi lahendavad, keerleks kõige suurema amplituudiga, nii et kui avate kasti Schrodingeri kass, see sisemise oleku versioon, mis teile kõige tõenäolisemalt esitatakse, on suitsetamise välimusega kass, kellel on dekrüpteeritud sõnum.

Kvantarvutite kohta lisateabe saamiseks vaadake meie hiljutine artikkel sellel teemal Kuidas optilised ja kvantarvutid töötavad?Exascale ajastu on tulemas. Kas teate, kuidas optilised ja kvantarvutid töötavad, ja kas neist uutest tehnoloogiatest saab meie tulevik? Loe rohkem !

Selle tulemus on see, et kvantarvutid pole lihtsalt lineaarselt kiiremad - tavaliste arvutite moodi: saab kaks või kümme või sada korda kiirem ei aita palju tavapärasest krüptograafiast, mille töötlemine on sadu miljardeid kordi liiga aeglane. Kvantarvutid toetavad algoritme, mille käitusaja keerukus on väiksema kasvuga kui muidu võimalik. See teebki kvantarvutitest fundamentaalse erinevuse teistest tulevastest arvutustehnoloogiatest, näiteks grafeeni ja memristide arvutamine Viimane arvutitehnoloogia, mida peate uskumaVaadake mõnda uusimat arvutitehnoloogiat, mis on lähiaastatel muudetud elektroonika ja personaalarvutite maailma muutmiseks. Loe rohkem .

Konkreetse näitena võib Shori algoritm, mida saab täita ainult kvantarvutis, arvestada log (n) ^ 3 aeg, mis on drastiliselt parem kui parim klassikaline rünnak. Üldise numbrivälja sõela kasutamine 2048-bitise arvu arvutamiseks võtab umbes 10 ^ 41 ajaühikut, mis moodustab enam kui triljon triljonit triljonit. Shori algoritmi kasutades võtab sama probleem ainult umbes 1000 ajaühikut.

Efekt muutub selgemaks, mida kauem klahvid on. See on kvantarvutite jõud.

Ärge saage minust valesti aru - kvantarvutitel on palju potentsiaalset mitte-kurja kasutamist. Kvantarvutid saavad rändmüüjate probleemi tõhusalt lahendada, võimaldades teadlastel luua tõhusamaid saatmisvõrgustikke ja kujundada paremaid vooluringid. Kvantarvutitel on tehisintellektil juba võimsaid kasutusvõimalusi.

Sellegipoolest saab nende roll krüptograafias katastroofiliseks. Krüpteerimistehnoloogiad, mis võimaldavad meie maailmas toimimist säilitada, sõltuvad sellest, kas täisarvu faktoriseerimise probleemi on raske lahendada. RSA ja sellega seotud krüptimisskeemid võimaldavad teil uskuda, et olete õigel veebisaidil, st teie failides allalaadimine pole pahavaraga seotud ja inimesed ei luura teie Interneti-sirvimist (kui kasutate Tor).

Krüptograafia hoiab teie pangakontot turvalisena ja kaitseb maailma tuumainfrastruktuuri. Kui kvantarvutid muutuvad praktilisteks, lakkab kogu see tehnoloogia töötamast. Esimene organisatsioon, mis arendab kvantarvutit, kui maailm töötab endiselt nende tehnoloogiate järgi, mida me täna kasutame, on kohutavalt võimsas positsioonis.

Niisiis, kas kvant-apokalüpsis on vältimatu? Kas saame selles midagi teha? Nagu selgub… jah.

Kvantjärgne krüptograafia

Krüpteerimisalgoritme on mitu klassi, mida teadaolevalt pole kvantarvutis oluliselt kiiremini lahendada. Neid nimetatakse ühiselt kvantijärgseks krüptograafiaks ja need annavad lootust, et maailm saab üle minna krüptosüsteemidele, mis jäävad kvantkrüptimise maailmas turvaliseks.

Paljutõotavad kandidaadid hõlmavad võrepõhist krüpteerimist, näiteks veaga ringõppimine, mis tuleneb selle turvalisusest demonstreeritavalt keerulisest masinõppe probleem ja mitme muutujaga krüptograafia, mis tuleneb selle turvalisusest raskustest lahendada väga suuri lihtsate süsteemide süsteeme võrrandid. Selle teema kohta saate lisateavet lugeda Vikipeedia artikkel. Ettevaatust: suur osa sellest kraamist on keeruline ja võite enne matemaatika tausta põhjalikult uurida, et peate oma matemaatika tausta märkimisväärselt täiendama.

Suur osa sellest on see, et kvantijärgsed krüptoskeemid on väga lahedad, aga ka väga noored. Nad vajavad rohkem tööd, et olla tõhusad ja praktilised ning ühtlasi näidata, et nad on turvalised. Põhjuseks, et võime krüptosüsteeme usaldada, on see, et oleme neile piisavalt kaua visanud kliiniliselt paranoilisi geeniusi et kõik ilmsed puudused oleks praeguseks avastatud ja teadlased on tõestanud erinevaid omadusi, mis neid teevad tugev.

Kaasaegne krüptograafia sõltub valgust kui desinfitseerivat ainet ja enamik kvantijärgseid krüptograafilisi skeeme on lihtsalt liiga uued, et usaldada maailma julgeolekut. Nad jõuavad sinna siiski ning vähese õnne ja mõningase ettevalmistusega saavad turbeeksperdid lüliti lõpule viia enne, kui esimene kvantarvuti kunagi võrku tuleb.

Kui need siiski läbi kukuvad, võivad tagajärjed olla rängad. Mõte kõigist, kellel on selline võim, on segane, isegi kui olete nende kavatsuste suhtes optimistlik. Küsimus, kes kõigepealt töötab välja töötava kvantarvuti, on selline, mida kõik peaksid järgmise kümnendi liikumisel väga hoolikalt jälgima.

Kas tunnete muret kvantarvutite krüptograafia ebakindluse pärast? Mis sa võtad? Jagage oma mõtteid allpool olevates kommentaarides!

Pildikrediidid: Binaarne orb Shutterstocki kaudu