Kvantu datori: kriptogrāfijas beigas?

Reklāma

Kvantu skaitļošana ir viena no tām tehnoloģijām, kas ir tik izcila, ka TV varoņu vārdi to nomāc, kad viņi vēlas izklausīties gudri.

Kvantu skaitļošana kā ideja pastāv jau kādu laiku - teorētisko iespēju sākotnēji ieviesa Jurijs Manins un Ričards Feinmans 1982. gadā. Tomēr dažu pēdējo gadu laikā šī joma ir satraucoši tuvinājusies praktiskumam.

Uzņēmumi, piemēram, Google un Microsoft, kā arī valdības aģentūras, piemēram, NSA, jau gadiem ilgi drudžaini rīkojas ar kvantu datoriem. Uzņēmums ar nosaukumu D-Wave ir ražojis un pārdod ierīces, kas (kamēr tie nav piemēroti datori, to var) veic tikai dažus algoritmus) izmanto kvantu īpašības un ir vēl viens solis ceļā uz a pilnībā Pilnībā pabeigta Kas ir Tjūringa tests un vai tas kādreiz tiks pārspēts?Tjūringa tests ir paredzēts, lai noteiktu, vai mašīnas domā. Vai Jevgeņija Goostmana programma patiešām izturēja Tjūringa testu, vai arī veidotāji vienkārši apkrāpa? Lasīt vairāk kvantu mašīna.

Nešķiet nepamatoti teikt, ka varētu notikt izrāvieni, kas desmit gadu laikā ļaus uzbūvēt pirmo liela mēroga kvantu datoru.

Tad kāpēc visa interese? Kāpēc jums vajadzētu rūpēties? Datori visu laiku kļūst ātrāki Kas ir Mūra likums, un kā tam ir sakara ar jums? [MakeUseOf skaidrojumi]Neveiksmīgajai veiksmei nav nekā kopīga ar Mūra likumu. Ja tā ir asociācija, kas jums bija, jūs to sajaucat ar Mērfija likumu. Tomēr jūs nebijāt tālu, jo Mūra likums un Mērfija likums ... Lasīt vairāk - kas ir tik īpašs kvantu datoros?

Lai izskaidrotu, kāpēc šīs mašīnas ir tik svarīgas, mums būs jāveic solis atpakaļ un precīzi jāizpēta, kas ir kvantu datori un kāpēc tie darbojas. Sākumā runāsim par jēdzienu “izpildlaika sarežģītība”.

Kas ir izpildlaika sarežģītība?

Viens no lielākajiem pārsteigumiem pirmajās datorzinātnes dienās bija atklājums, ka, ja jums ir dators, kas atrisina noteikts lielums noteiktā laika posmā, datora ātruma divkāršošana ne vienmēr ļauj to divreiz risināt liels.

Daži algoritmi kopējā izpildes laikā palielinās ļoti, ļoti ātri, pieaugot problēmas apjomam - dažus algoritmus var ātri pabeigt ņemot vērā 100 datu punktus, bet, lai pabeigtu algoritmu, kurā bija doti 1000 datu punkti, būs nepieciešams dators, kura Zemes izmērs darbosies miljardam gados. Runtime sarežģītība ir šīs idejas formalizēšana: tiek apskatīta līkne, cik ātri palielinās problēmas sarežģītība, un algoritma klasificēšanai izmanto šīs līknes formu.

Parasti šīs grūtības klases izsaka kā funkcijas. Algoritms, kas kļūst proporcionāli grūtāks, kad palielinās datu kopas darbība (piemēram, vienkārša skaitīšanas funkcija), tiek uzskatīts par funkciju ar izpildlaika sarežģītību “n ” (tāpat kā tas notiek) n apstrādājamās laika vienības n datu punkti).

Pārmaiņus to var saukt par “lineāru”, jo, to grafizējot, tiek iegūta taisna līnija. Citas funkcijas varētu būt n ^ 2 vai 2 ^ n vai n! (n faktoriālais). Tie ir polinoma un eksponenciāli. Pēdējos divos gadījumos eksponenciālie aug tik ātri, ka gandrīz visos gadījumos tos nevar atrisināt neko, izņemot ļoti triviālus piemērus.

Runtime Complexity and Cryptography

Ja jūs dzirdat šo saturu pirmo reizi un tas izklausās bezjēdzīgs un liekulīgs, mēģināsim pamatot šo diskusiju. Kriptogrāfijai ir ļoti būtiska izpildlaika sarežģītība, kuras pamatā ir atšifrēšanas atvieglošana cilvēkiem, kuri zina slepeno atslēgu, nekā tiem, kuri to nedara. Ideālā kriptogrāfijas shēmā atšifrēšanai vajadzētu būt lineārai, ja jums ir atslēga, un 2 ^ k (kur k ir atslēgas bitu skaits), ja tā nav.

Citiem vārdiem sakot, vislabākajam ziņojuma atšifrēšanas bez atslēgas algoritmam vajadzētu būt vienkārši iespējamo atslēgu uzminēšanai, kas ir nepielūdzami taustiņiem, kas ir tikai dažus simtus bitu gari.

Simetriskas atslēgas kriptogrāfijas gadījumā (kurā abām pusēm ir iespēja droši apmainīties ar noslēpumu pirms komunikācijas uzsākšanas) tas ir diezgan viegli. Asimetriskai kriptogrāfijai tas ir grūtāk.

Asimetriskā kriptogrāfija, kurā šifrēšanas un atšifrēšanas atslēgas ir atšķirīgas un kuras nevar viegli aprēķināt viena no otras, ir daudz grūtāk matemātiska īstenojama struktūra nekā simetriska kriptogrāfija, taču tā ir arī daudz jaudīgāka: asimetriskā kriptogrāfija ļauj privāti sarunāties pat pat pieskaroties līnijas! Tas arī ļauj jums izveidot “ciparparakstus”, lai jūs varētu pārbaudīt, kurš ziņojums nāk no tā, vai tas nav ticis mainīts.

Šie ir jaudīgi rīki un veido mūsdienu privātuma pamatus: bez asimetriskas kriptogrāfijas elektronisko ierīču lietotājiem nebūtu drošas aizsardzības pret ziņkārīgo acīm.

Tā kā asimetrisko kriptogrāfiju ir grūtāk izveidot nekā simetrisku, šodien izmantotās standarta šifrēšanas shēmas nav tik spēcīgas kādi tie varētu būt: visizplatītākais šifrēšanas standarts RSA var tikt uzlauzts, ja jūs varat efektīvi atrast ļoti liela pamata faktorus numuru. Labās ziņas ir tā, ka tā ir ļoti smaga problēma.

Pazīstamāko algoritmu lielu skaitļu ieskaitīšanai to komponentu primos sauc par vispārīgo skaitļu lauka sietu, un tā izpildlaika sarežģītība aug nedaudz lēnāk nekā 2 ^ n. Rezultātā taustiņiem jābūt apmēram desmit reizes garākiem, lai nodrošinātu līdzīgu drošību, ko cilvēki parasti pacieš kā uzņēmējdarbības izmaksas. Sliktā ziņa ir tā, ka viss spēles laukums mainās, kad kvantu datori nonāk metienā.

Kvantu datori: kripto spēles mainīšana

Kvantu datori darbojas tāpēc, ka tiem var būt vairāki iekšējie stāvokļi vienlaikus ar kvantu parādību, ko sauc par “superpozīciju”. Tas nozīmē, ka viņi var vienlaikus uzbrukt dažādām problēmas daļām, sadalot iespējamās Visuma versijas. Tos var arī konfigurēt tā, lai filiāles, kas atrisina problēmu, būtu vijas ar vislielāko amplitūdu, tā ka, atverot lodziņu Šrodingera kaķis, tā iekšējā stāvokļa versija, kas jums, visticamāk, tiks parādīta, ir smuki izskata kaķis, kuram ir atšifrēts ziņa.

Lai iegūtu papildinformāciju par kvantu datoriem, pārbaudiet mūsu nesenais raksts par šo tēmu Kā darbojas optiskie un kvantu datori?Tuvojas Exascale laikmets. Vai jūs zināt, kā darbojas optiskie un kvantu datori, un vai šīs jaunās tehnoloģijas kļūs par mūsu nākotni? Lasīt vairāk !

Rezultāts ir tāds, ka kvantu datori nav tikai lineāri ātrāki, tāpat kā parasti datori: iegūstot divus, desmit vai simtu reizes ātrāk nepalīdz, ja runājam par parasto kriptogrāfiju, kuras apstrāde ir simtiem miljardu reižu pārāk lēna. Kvantu datori atbalsta algoritmus, kuriem ir mazāka pieaugošā izpildes laika sarežģītība, nekā tas ir iespējams citādi. Tas ir tas, kas padara kvantu datorus principiāli atšķirīgus no citām nākotnes skaitļošanas tehnoloģijām, piemēram grafēna un memtera skaitīšana Jaunākās datortehnoloģijas, kas jums jāredz, lai ticētuIepazīstieties ar dažām jaunākajām datortehnoloģijām, kas nākamo gadu laikā ir pārveidotas elektronikas un personālo datoru pasaulē. Lasīt vairāk .

Konkrēts piemērs ir Šora algoritms, kuru var izpildīt tikai ar kvantu datoru, un žurnāls (n) ^ 3 laiks, kas ir krasi labāks par labāko klasisko uzbrukumu. Vispārējā skaitļa lauka sieta izmantošana skaitļa ar 2048 bitiem koeficientam prasa apmēram 10 ^ 41 laika vienības, kas pārsniedz vairāk nekā triljonus triljonus triljonu. Izmantojot Šora algoritmu, tā pati problēma prasa tikai apmēram 1000 laika vienības.

Efekts kļūst izteiktāks, jo ilgāk ir taustiņi. Tas ir kvantu datoru spēks.

Nekļūdieties man nepareizi - kvantu datoriem ir daudz potenciālu ļaunuma lietojumu. Kvantu datori var efektīvi atrisināt ceļojošo pārdevēju problēmu, ļaujot pētniekiem izveidot efektīvākus pārvadājumu tīklus un projektēt labākas shēmas. Kvantu datoriem mākslīgais intelekts jau ir plaši izmantots.

Tomēr to loma kriptogrāfijā būs katastrofāla. Šifrēšanas tehnoloģijas, kas ļauj mūsu pasaulei turpināt darboties, ir atkarīgas no tā, vai grūti atrisināt skaitļu faktorizācijas problēmu. RSA un saistītās šifrēšanas shēmas ļauj uzticēties, ka atrodaties pareizajā vietnē, proti, failos lejupielāde nav apgrūtināta ar ļaunprātīgu programmatūru, kā arī tas, ka cilvēki nav izspiegojuši jūsu pārlūkošanu internetā (ja izmantojat Tor).

Kriptogrāfija nodrošina jūsu bankas konta drošību un pasaules kodolenerģijas infrastruktūras drošību. Kad kvantu datori kļūst praktiski, visa šī tehnoloģija pārstāj darboties. Pirmā organizācija, kas izstrādās kvantu datoru, ja pasaule joprojām darbojas uz tehnoloģijām, kuras mēs šodien izmantojam, būs biedējoši spēcīgā stāvoklī.

Tātad, vai kvantu apokalipse ir neizbēgama? Vai mēs kaut ko varam darīt? Kā izrādās… jā.

Pēckvantu kriptogrāfija

Ir vairākas šifrēšanas algoritmu klases, kuras, cik mēs zinām, nav ievērojami ātrāk atrisināt kvantu datorā. Tos kopīgi sauc par postkvantu kriptogrāfiju, un tie sniedz nelielu cerību, ka pasaule var pāriet uz kriptosistēmām, kuras kvantu šifrēšanas pasaulē arī turpmāk būs drošas.

Daudzsološajos kandidātos ietilpst uz režģiem balstīta šifrēšana, piemēram, gredzenu apgūšana ar kļūdu, kuras drošību nodrošina demonstrējami sarežģīts mašīnmācīšanās problēma un daudzfaktoru kriptogrāfija, kuras drošība izriet no grūtībām atrisināt ļoti lielas vienkāršu sistēmu vienādojumi. Plašāku informāciju par šo tēmu varat lasīt vietnē Wikipedia raksts. Uzmanieties: liela daļa šo lietu ir sarežģīta, un, iespējams, var secināt, ka matemātikas fons ir ievērojami jāpaaugstina, lai varētu reāli iedziļināties detaļās.

Daudz kas no tā ir tas, ka pēckvantu kriptogrammas ir ļoti foršas, bet arī ļoti jaunas. Viņiem ir jāpieliek vairāk darba, lai tie būtu efektīvi un praktiski, kā arī lai parādītu, ka viņi ir droši. Iemesls, kāpēc mēs varam uzticēties kriptosistēmām, ir tas, ka mēs pietiekami ilgi esam uz viņiem iemetuši klīniski paranojas ģēnijus ka tagad būtu atklāti visi acīmredzamie trūkumi, un pētnieki ir pierādījuši dažādas īpašības, kas tos padara stipra.

Mūsdienu kriptogrāfija ir atkarīga no gaismas kā dezinfekcijas līdzekļa, un vairums postkvantu kriptogrāfijas shēmu ir vienkārši pārāk jaunas, lai uzticētos pasaules drošībai. Viņi tomēr dodas uz turieni, un ar nelielu veiksmi un nelielu sagatavošanos drošības eksperti var pabeigt pārslēgšanu, pirms pirmais kvantu dators ienāk tiešsaistē.

Ja tie tomēr neizdodas, sekas var būt drausmīgas. Doma par ikvienu, kam ir šāda veida vara, ir satraucoša, pat ja jūs optimistiski domājat par viņu nodomiem. Jautājums par to, kurš pirmais izstrādā strādājošu kvantu datoru, ir tāds, kuru ikvienam vajadzētu ļoti uzmanīgi skatīties, pārejot uz nākamo desmitgadi.

Vai jūs uztrauc kriptogrāfijas nedrošība attiecībā uz kvantu datoriem? Kādas ir jūsu iespējas? Dalieties savās domās komentāros zemāk!

Attēlu kredīti: Binārā orb Caur Shutterstock