Kā kvantu dators varētu izjaukt 2048 bitu RSA šifrēšanu 8 stundās

D-Wave Vesuvius mikroshēmas tuvplāns Stīvs Jurvetsons | Flickr

Daudzi cilvēki uztraucas, ka kvantu datori varēs uzlauzt noteiktus kodus, ko izmanto drošu ziņojumu sūtīšanai. Attiecīgie kodi šifrē datus, izmantojot slazddurvju matemātiskās funkcijas, kas viegli darbojas vienā virzienā, bet ne otrā virzienā. Tas padara datu šifrēšanu vienkāršu, bet ļoti sarežģītu to dekodēšanu bez īpašas atslēgas palīdzības.

Šīs šifrēšanas sistēmas nekad nav bijušas nepārspējamas. Tā vietā viņu drošība ir balstīta uz milzīgo laiku, kas būtu nepieciešams klasiskajam datoram, lai veiktu šo darbu. Mūsdienu šifrēšanas metodes ir īpaši izstrādātas tā, lai to atkodēšana aizņemtu tik ilgu laiku, ka tās ir praktiski nesalaužamas.

Taču kvantu datori maina šo domāšanu. Šīs mašīnas ir daudz jaudīgākas par klasiskajiem datoriem, un tām vajadzētu viegli lauzt šos kodus.

Tas rada svarīgu jautājumu — kad kvantu datori būs pietiekami jaudīgi, lai to izdarītu? Pēc šī datuma visa ar šo šifrēšanas veidu aizsargātā informācija kļūst nedroša.

Tāpēc datorzinātnieki ir mēģinājuši aprēķināt resursus, kas varētu būt nepieciešami šādam kvantu datoram, un pēc tam noskaidrot, cik ilgs laiks būs nepieciešams, līdz šādu mašīnu varēs uzbūvēt. Un atbilde vienmēr ir bijusi gadu desmitiem.

Šodien šī domāšana ir jāpārskata, pateicoties Kreiga Gidnija darbam Google Santabarbarā un Martina Ekero darbam KTH Karaliskajā tehnoloģiju institūtā Stokholmā, Zviedrijā. Šie puiši ir atraduši efektīvāku veidu, kā kvantu datori veikt kodu sadalīšanas aprēķinus, samazinot tiem nepieciešamos resursus par lielumu kārtām.

Līdz ar to šīs mašīnas ir ievērojami tuvāk realitātei, nekā kāds tur aizdomās. Rezultāts valdībām, militārajām un drošības organizācijām, bankām un ikvienam citam, kam nepieciešams nodrošināt datu drošību 25 gadus vai ilgāk, būs neērti lasīt.

Vispirms nedaudz fona. Tālajā 1994. gadā amerikāņu matemātiķis Pīters Šors atklāja kvantu algoritmu, kas pārspēja klasisko ekvivalentu. Šora algoritms ņem vērā lielus skaitļus, un tas ir būtisks elements uz slazdām balstītu kodu uzlaušanas procesā.

Slazddurvju funkcijas ir balstītas uz reizināšanas procesu, ko ir viegli veikt vienā virzienā, bet daudz grūtāk veikt pretējā virzienā. Piemēram, ir triviāli reizināt divus skaitļus kopā: 593 reiz 829 ir 491 597. Bet ir grūti sākt ar skaitli 491 597 un izdomāt, kuri divi pirmskaitļi ir jāreizina, lai to iegūtu.

Un tas kļūst arvien grūtāk, jo skaitļi kļūst lielāki. Patiešām, datorzinātnieki uzskata, ka klasiskajam datoram ir praktiski neiespējami faktorēt skaitļus, kas ir garāki par 2048 bitiem, kas ir visbiežāk izmantotā RSA šifrēšanas veida pamatā.

Šors parādīja, ka pietiekami jaudīgs kvantu dators to var viegli izdarīt, un tas izraisīja trieciena viļņus cauri drošības nozarei.

Kopš tā laika kvantu datoru jauda ir palielinājusies. 2012. gadā fiziķi izmantoja četru kubitu kvantu datoru, lai aprēķinātu koeficientu 143. Pēc tam 2014. gadā viņi izmantoja līdzīgu ierīci, lai aprēķinātu koeficientu 56 153.

Ir viegli iedomāties, ka ar šādu progresa ātrumu kvantu datoriem drīz vajadzētu spēt pārspēt labākos klasiskos datorus.

Ne tā. Izrādās, ka kvantu faktorings praksē ir daudz grūtāks, nekā citādi varētu gaidīt. Iemesls ir tāds, ka troksnis kļūst par būtisku problēmu lieliem kvantu datoriem. Un pašlaik labākais veids, kā novērst troksni, ir izmantot kļūdu labošanas kodus, kuriem pašiem ir nepieciešami ievērojami papildu kubiti.

Ņemot to vērā, ievērojami palielinās resursi, kas nepieciešami 2048 bitu skaitļu faktorēšanai. 2015. gadā pētnieki aprēķināja, ka kvantu datoram būtu nepieciešams miljards kubitu, lai uzticami veiktu darbu. Tas ir ievērojami vairāk nekā 70 kubiti mūsdienu modernajos kvantu datoros.

Pamatojoties uz to, drošības eksperti, iespējams, varēja pamatot domu, ka paies gadu desmitiem, pirms kvantu dators varētu izjaukt ziņojumus ar 2048 bitu RSA šifrēšanu.

Tagad Gidnijs un Ekero ir parādījuši, kā kvantu dators var veikt aprēķinus tikai ar 20 miljoniem kubitu. Tie patiešām parāda, ka šādai ierīcei būtu nepieciešamas tikai astoņas stundas, lai pabeigtu aprēķinu. [Tā rezultātā] sliktākā gadījuma aprēķins par to, cik kubitu būs nepieciešams, lai faktorētu 2048 bitu RSA veselus skaitļus, ir samazinājies gandrīz par divām kārtām.

Viņu metode ir vērsta uz efektīvāku veidu, kā veikt matemātisko procesu, ko sauc par modulāro eksponenci. Šis ir atlikuma atrašanas process, kad skaitlis tiek palielināts līdz noteiktai pakāpei un pēc tam dalīts ar citu skaitli.

Šis process ir skaitļošanas ziņā dārgākā darbība Šora algoritmā. Taču Gidnijs un Ekero ir atraduši dažādus veidus, kā to optimizēt, būtiski samazinot algoritma darbināšanai nepieciešamos resursus.

Tas ir interesants darbs, kam vajadzētu būt nozīmīgam ikvienam, kas glabā informāciju nākotnei. 20 miljonu kubitu kvantu dators šodien noteikti šķiet tāls sapnis. Taču jautājums, kas šiem ekspertiem būtu jāuzdod sev, ir tas, vai šāda ierīce varētu būt iespējama 25 gadu laikā, kad viņi vēlas nodrošināt informāciju. Ja viņi tā domā, viņiem ir nepieciešams jauns šifrēšanas veids.

Patiešām, drošības eksperti ir izstrādājuši pēckvantu kodus, kurus pat kvantu dators nespēs uzlauzt. Tātad jau šodien ir iespējams aizsargāt datus pret kvantu datoru uzbrukumiem nākotnē. Taču šie kodi vēl netiek izmantoti kā standarta.

Parastajiem cilvēkiem risks ir mazs. Lielākā daļa cilvēku izmanto 2048 bitu šifrēšanu vai kaut ko līdzīgu, lai veiktu tādus uzdevumus kā kredītkartes informācijas nosūtīšana internetā. Ja šos darījumus reģistrēs šodien un izjauks pēc 25 gadiem, maz kas tiks zaudēts.

Taču valdībām ir daudz vairāk. Ziņojumi, ko viņi sūta šodien, piemēram, starp vēstniecībām vai militārpersonām, var būt nozīmīgi pēc 20 gadiem, un tāpēc tos ir vērts paturēt noslēpumā. Ja šādi ziņojumi joprojām tiek sūtīti, izmantojot 2048 bitu RSA šifrēšanu vai ko līdzīgu, šīm organizācijām vajadzētu ātri uztraukties.

Atsauce: arxiv.org/abs/1905.09749 : 2048 bitu RSA veselo skaitļu koeficientu noteikšana 8 stundās, izmantojot 20 miljonus trokšņainu kubitu

paslēpties