Kvantové počítače: koniec kryptografie?

Reklama

Kvantová práca s počítačom je jednou z technológií, ktoré sú také tajomné, že názov televíznych znakov ich zruší, keď chcú znieť inteligentne.

Kvantové výpočty ako myšlienka už nejakú dobu existujú - teoretickú možnosť pôvodne predstavili Yuri Manin a Richard Feynman v roku 1982. V posledných rokoch sa však toto pole znepokojivo priblížilo praktickosti.

Spoločnosti ako Google a Microsoft, ako aj vládne agentúry ako NSA už roky horlivo sledujú kvantové počítače. Spoločnosť s názvom D-Wave vyrába a predáva zariadenia, ktoré (hoci nie sú správne počítače a dokážu ich) vykonávajú len niekoľko algoritmov) využívajú kvantové vlastnosti a sú ďalším krokom na ceste smerom k a plne Turing-kompletný Čo je Turingov test a bude ho niekedy poraziť?Turingov test je určený na určenie, či si stroje myslia. Prešiel program Eugene Goostman skutočne Turingovým testom, alebo ho tvorcovia jednoducho podviedli? Čítaj viac kvantový stroj.

Nezdá sa byť neprimerané tvrdiť, že by mohlo dôjsť k prielomom, ktoré umožnia, aby sa prvý veľký kvantový počítač vybudoval v priebehu desiatich rokov.

Tak prečo všetok záujem? Prečo by ste sa mali starať? Počítače sú stále rýchlejšie Čo je Mooreov zákon a čo to má s tebou spoločné? [MakeUseOf vysvetľuje]Smola nemá nič spoločné s Mooreovým zákonom. Ak je toto združenie, ktoré ste mali, zamieňate ho s Murphyho zákonom. Neboli ste však ďaleko, pretože Mooreov zákon a Murphyho zákon ... Čítaj viac - Čo je také zvláštne na kvantových počítačoch?

Aby sme vysvetlili, prečo sú tieto stroje také dôležité, musíme urobiť krok späť a preskúmať, čo presne sú kvantové počítače a prečo fungujú. Na začiatok sa porozprávame o koncepte s názvom „runtime complexity“.

Čo je to runtime zložitosť?

Jedným z veľkých prekvapení v počiatkoch počítačovej vedy bolo zistenie, že ak máte počítač, ktorý rieši problém určitá veľkosť v určitom čase, zdvojnásobenie rýchlosti počítača nemusí nevyhnutne umožniť vyriešiť problémy dvakrát veľký.

Niektoré algoritmy zvyšujú celkový čas vykonávania veľmi, veľmi rýchlo s rastúcou veľkosťou problému - niektoré algoritmy je možné rýchlo dokončiť vzhľadom na 100 údajových bodov, ale na dokončenie algoritmu na 1 000 údajových bodov by bolo potrebné, aby počítač s veľkosťou Zeme bežal za miliardu rokov. Runtime zložitosť je formalizáciou tejto myšlienky: pozerá sa na krivku toho, ako rýchlo zložitosť problému rastie, a používa tvar tejto krivky na klasifikáciu algoritmu.

Všeobecne sa tieto triedy ťažkostí vyjadrujú ako funkcie. Algoritmus, ktorý je úmerne ťažší, keď sa množina údajov, na ktorých pracuje, zvyšuje (ako napríklad jednoduchá funkcia počítania), sa považuje za funkciu s runtime zložitosťou „n " (rovnako ako v prípade, n jednotky času na spracovanie n dátové body).

Alternatívne by sa to mohlo nazývať „lineárne“, pretože keď ho vytvoríte grafom, získate priamku. Ostatné funkcie môžu byť n ^ 2 alebo 2 ^ n alebo n! (n faktoriál). Sú to polynóm a exponenciál. V posledných dvoch prípadoch exponenciálne rastú tak rýchlo, že takmer vo všetkých prípadoch ich nemožno vyriešiť pre nič iné, iba pre veľmi triviálne príklady.

Runtime Complexity and Cryptography

Ak počúvate tieto veci prvýkrát a znie to nezmyselne a tajomne, skúste túto diskusiu rozložiť. Zložitosť runtime je kľúčová pre kryptografiu, ktorá sa spolieha na to, že dešifrovanie bude oveľa jednoduchšie pre ľudí, ktorí poznajú tajný kľúč, ako pre tých, ktorí ho nemajú. V ideálnej kryptografickej schéme by malo byť dešifrovanie lineárne, ak máte kľúč, a 2 ^ k (kde k je počet bitov v kľúči), ak tak neurobíte.

Inými slovami, najlepším algoritmom na dešifrovanie správy bez kľúča by malo byť jednoducho uhádnutie možných kľúčov, čo je nevyčísliteľné pre kľúče dlhé iba niekoľko stoviek bitov.

Pre symetrickú kryptografiu kľúčov (v ktorej majú obe strany šancu vymeniť si tajne pred začatím komunikácie) je to celkom ľahké. Pre asymetrickú kryptografiu je to ťažšie.

Asymetrická kryptografia, v ktorej sú šifrovacie a dešifrovacie kľúče odlišné a nedajú sa ľahko vypočítať jeden od druhého, je oveľa ťažšou matematickou metódou. implementácia štruktúry ako symetrická kryptografia, ale je tiež omnoho výkonnejšia: asymetrická kryptografia vám umožňuje viesť súkromné ​​konverzácie, dokonca aj pri poklepaní linky! Umožňuje vám tiež vytvárať „digitálne podpisy“, ktoré vám umožnia overiť, od koho správa prišla a či s ňou nebolo manipulované.

Sú to výkonné nástroje a tvoria základ moderného súkromia: bez asymetrickej kryptografie by používatelia elektronických zariadení nemali spoľahlivú ochranu pred zvedavými očami.

Pretože asymetrická kryptografia sa dá ťažšie zostaviť ako symetrická, nie sú štandardné šifrovacie schémy, ktoré sa dnes používajú, také silné ako by mohli byť: najbežnejší šifrovací štandard, RSA, môže byť popraskaný, ak dokážete efektívne nájsť hlavné faktory veľmi veľkého číslo. Dobrou správou je, že je to veľmi ťažký problém.

Najznámejší algoritmus na rozdeľovanie veľkých čísel do prvočísel komponentov sa nazýva sito všeobecného číselného poľa a jeho runtime zložitosť rastie o niečo pomalšie ako 2 ^ n. V dôsledku toho musia byť kľúče asi desaťkrát dlhšie, aby poskytovali podobnú bezpečnosť, čo ľudia bežne tolerujú ako náklady na podnikanie. Zlá správa je, že keď sa kvantové počítače hodia do mixu, zmení sa celé ihrisko.

Kvantové počítače: Zmena hry Crypto

Kvantové počítače pracujú, pretože môžu mať viac vnútorných stavov súčasne, a to prostredníctvom kvantového javu nazývaného „superpozícia“. To znamená, že môžu súčasne útočiť na rôzne časti problému a rozdeliť ho na možné verzie vesmíru. Môžu byť tiež nakonfigurované tak, aby sa vetvy, ktoré riešia problém, navíjali s najväčšou amplitúdou, takže keď otvoríte krabicu Schrodingerova mačka, verzia vnútorného stavu, s ktorou sa pravdepodobne stretnete, je samolibá mačka, ktorá drží dešifrovanú správa.

Viac informácií o kvantových počítačoch nájdete na stránke náš nedávny článok na túto tému Ako fungujú optické a kvantové počítače?Vek Exascale sa blíži. Viete, ako optické a kvantové počítače fungujú, a stanú sa tieto nové technológie našou budúcnosťou? Čítaj viac !

Výsledkom je, že kvantové počítače nie sú len lineárne rýchlejšie, ako sú bežné počítače: získanie dvoch, desiatich alebo stoviek krát rýchlejšie nepomáha, pokiaľ ide o konvenčnú kryptografiu, ktorú spracovávate stovky miliárd krát. Kvantové počítače podporujú algoritmy, ktoré majú menšiu rastúcu dobu spracovania, ako je inak možné. To je dôvod, prečo sa kvantové počítače zásadne líšia od iných budúcich výpočtových technológií výpočet grafénu a memristera Najnovšia počítačová technológia, ktorú musíte vidieť, aby ste uveriliVyskúšajte niektoré z najnovších počítačových technológií, ktoré sú pripravené v nasledujúcich rokoch transformovať svet elektroniky a počítačov. Čítaj viac .

Konkrétnym príkladom je Shorov algoritmus, ktorý je možné spustiť iba na kvantovom počítači, a môže v ňom zahrnúť veľké čísla log (n) ^ 3 čas, ktorý je drasticky lepší ako najlepší klasický útok. Použitie sita všeobecného poľa s číslami na vynásobenie čísla s 2048 bitmi trvá asi 10 ^ 41 jednotiek času, čo sa prejaví na viac ako trilióne biliónov biliónov. Pri použití Shorovho algoritmu trvá rovnaký problém iba asi 1 000 jednotiek času.

Efekt bude výraznejší, čím dlhšie budú klávesy. To je sila kvantových počítačov.

Nechápte ma zle - kvantové počítače majú veľa potenciálnych nezlých použití. Kvantové počítače dokážu efektívne vyriešiť problém obchodného cestujúceho, čo výskumníkom umožňuje vytvárať efektívnejšie dopravné siete a navrhovať lepšie obvody. Kvantové počítače už majú silné využitie v umelej inteligencii.

Ich úloha v kryptografii bude katastrofická. Technológie šifrovania, ktoré umožňujú nášmu svetu udržať fungovanie, závisia od ťažko riešiteľného problému celočíselnej faktorizácie. RSA a súvisiace šifrovacie schémy vám umožňujú veriť, že sa nachádzate na správnom webe, že vaše súbory Sťahovanie nie je preplnené škodlivým softvérom a že ľudia pri vašom prehliadaní Internetu neprezerajú (ak používate Tor).

Kryptografia udržuje váš bankový účet v bezpečí a zabezpečuje svetovú jadrovú infraštruktúru. Keď sa kvantové počítače stanú praktickými, všetka táto technológia prestane fungovať. Prvá organizácia, ktorá vyvinie kvantový počítač, ak svet stále pracuje na technológiách, ktoré dnes používame, bude mať strašidelne silné postavenie.

Je teda nevyhnutná kvantová apokalypsa? Môžeme s tým niečo urobiť? Ako sa ukazuje... áno.

Postkvantová kryptografia

Existuje niekoľko tried šifrovacích algoritmov, ktoré, pokiaľ vieme, nie sú podstatne rýchlejšie vyriešiteľné na kvantovom počítači. Sú známe ako post-kvantová kryptografia a poskytujú nádej, že svet môže prejsť na kryptosystémy, ktoré zostanú v bezpečí vo svete kvantového šifrovania.

Medzi sľubných kandidátov patrí šifrovanie založené na mriežke, napríklad Ring-Learning With Error, ktoré odvodzuje svoju bezpečnosť od preukázateľne zložitého strojové učenie a viacrozmerná kryptografia, ktorá odvodzuje svoju bezpečnosť od problémov pri riešení veľmi veľkých systémov jednoduchých rovnice. Viac informácií o tejto téme nájdete na Článok Wikipedia. Dajte si pozor: veľa z týchto vecí je zložitých a možno zistíte, že vaše matematické zázemie je potrebné výrazne zvýšiť, aby ste sa mohli skutočne venovať podrobnostiam.

Z mnohých z toho vyplýva, že post-kvantové kryptoschémy sú veľmi cool, ale tiež veľmi mladé. Potrebujú viac práce, aby boli efektívne a praktické, a tiež aby preukázali, že sú bezpečné. Dôvod, prečo sme schopní dôverovať kryptosystémom, je ten, že na ne dosť dlho hodíme klinicky paranoidných géniov. že akékoľvek zjavné nedostatky by sa teraz objavili a vedci preukázali rôzne vlastnosti, ktoré ich robia silný.

Moderná kryptografia závisí od svetla ako dezinfekčného prostriedku a väčšina postkvantových kryptografických schém je jednoducho príliš nová na to, aby dôverovala svetovej bezpečnosti. Dostávajú sa tam, avšak s trochou šťastia a prípravy sa odborníci na bezpečnosť môžu prepnúť pred tým, ako sa prvý kvantový počítač niekedy uvedie do prevádzky.

Ak však zlyhajú, môžu byť následky zlé. Myšlienka každého, kto má takúto moc, je znepokojujúca, aj keď ste optimistickí, pokiaľ ide o ich úmysly. Otázka, kto ako prvý vyvinie funkčný kvantový počítač, je otázkou, ktorú by mal každý pozorne sledovať, keď sa presťahujeme do nasledujúceho desaťročia.

Znepokojuje vás neistota kryptografie pre kvantové počítače? Čo si berieš? Podeľte sa o svoje myšlienky v komentároch nižšie!

Kredity obrázkov: Binárne gule Cez Shutterstock