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

reklama

Kvantová výpočetní technika je jednou z těch technologií, které jsou tak tajemné, že název televizních znaků je vypouští, když chtějí znít chytře.

Kvantová výpočetní technika jako nápad již nějakou dobu existuje - teoretickou možnost původně představili Yuri Manin a Richard Feynman v roce 1982. V posledních několika letech se však pole ohromně přibližovalo praktičnosti.

Společnosti jako Google a Microsoft, stejně jako vládní agentury, jako je NSA, už mnoho let horečně sledují kvantové počítače. Společnost s názvem D-Wave vyrobila a prodává zařízení, která (zatímco oni nejsou správné počítače, a mohou) provádějte pouze několik algoritmů) využívejte kvantové vlastnosti a jsou dalším krokovým krokem na cestě k a plně Turing-kompletní Co je Turingův test a bude to někdy porazeno?Turingův test má zjistit, zda si stroje myslí. Prošel program Eugene Goostman opravdu Turingovým testem, nebo ho tvůrci prostě podváděli? Přečtěte si více kvantový stroj.

Nezdá se být nepřiměřené říkat, že by mohlo dojít k průlomům, které by umožnily postavit první kvantový počítač ve velkém měřítku za deset let.

Tak proč všichni zájem? Proč by vás to mělo zajímat? Počítače jsou stále rychlejší Co je Mooreův zákon a co to má s vámi společného? [MakeUseOf vysvětluje]Smůla nemá nic společného s Mooreovým zákonem. Pokud je to asociace, kterou jste měli, plete ji s Murphyho zákonem. Nebyli jste však daleko, protože Mooreův zákon a Murphyho zákon ... Přečtěte si více - co je tak zvláštního na kvantových počítačích?

Abychom vysvětlili, proč jsou tyto stroje tak důležité, musíme udělat krok zpět a prozkoumat přesně, jaké kvantové počítače jsou a proč fungují. Začněme mluvit o konceptu zvaném „runtime complexity“.

Co je složitost běhu?

Jedním z největších překvapení v počátcích počítačové vědy byl objev, že pokud máte počítač, který řeší problém určitá velikost v určitém čase, zdvojnásobení rychlosti počítače nemusí nutně umožnit, aby řešila problémy dvakrát tak rychle velký.

Některé algoritmy zvyšují celkovou dobu provádění velmi, velmi rychle s rostoucím problémem - některé algoritmy lze rychle dokončit vzhledem k 100 datovým bodům, ale dokončení algoritmu s 1000 datovými body by vyžadovalo, aby počítač o velikosti Země běžel za miliardu let. Runtime složitost je formalizace této myšlenky: to dívá se na křivku jak rychle složitost problému roste, a používá tvar této křivky klasifikovat algoritmus.

Obecně jsou tyto třídy obtížnosti vyjádřeny jako funkce. Algoritmus, který se úměrně ztíží, když se datová sada pracuje na zvýšení (jako jednoduchá funkce počítání), se říká, že je funkcí s runtime složitostí „n “ (jako v, to trvá n jednotky času na zpracování n datové body).

Alternativně by to mohlo být nazýváno „lineární“, protože při jeho grafu získáte přímku. Mohou být jiné funkce n ^ 2 nebo 2 ^ n nebo n! (n faktoriál). Jsou to polynomiální a exponenciální. V posledních dvou případech exponenciální rostou tak rychle, že téměř ve všech případech nemohou být vyřešeny pro nic jiného než velmi triviální příklady.

Runtime složitost a kryptografie

Pokud to slyšíte poprvé a zní to nesmyslně a tajemně, pokusme se tuto diskusi zakotvit. Složitost runtime je pro kryptografii rozhodující, protože spoléhá na to, že dešifrování bude mnohem snazší pro lidi, kteří znají tajný klíč, než pro ty, kteří to neví. V ideálním kryptografickém schématu by mělo být dešifrování lineární, pokud máte klíč, a 2 ^ k (kde k je počet bitů v klíči), pokud nemáte.

Jinými slovy, nejlepším algoritmem pro dešifrování zprávy bez klíče by mělo být pouhé uhodnutí možných klíčů, což je neřešitelné pro klíče dlouhé jen několik set bitů.

Pro symetrickou kryptografii klíčů (ve které obě strany mají šanci bezpečně si vyměnit tajemství před zahájením komunikace) je to docela snadné. Pro asymetrickou kryptografii je to těžší.

Asymetrická kryptografie, ve které jsou šifrovací a dešifrovací klíče odlišné a nelze je snadno vypočítat jeden od druhého, je mnohem těžší matematická strukturu implementovat než symetrickou kryptografii, ale je také mnohem silnější: asymetrická krypta umožňuje soukromé konverzace, dokonce i přes poklepané linky! Také vám umožňuje vytvářet „digitální podpisy“, které vám umožní ověřit, od koho zpráva přišla a zda s ní nebylo manipulováno.

Jsou to výkonné nástroje a tvoří základ moderního soukromí: bez asymetrické kryptografie by uživatelé elektronických zařízení neměli spolehlivou ochranu před zvědavými očima.

Protože asymetrická kryptografie je obtížnější stavět než symetrická, standardní šifrovací schémata, která se dnes používají, nejsou tak silná jak by to mohlo být: nejběžnější šifrovací standard, RSA, lze popraskat, pokud můžete efektivně najít hlavní faktory velmi velké číslo. Dobrou zprávou je, že je to velmi těžký problém.

Nejznámější algoritmus pro rozdělování velkých čísel do jejich prvočísel se nazývá sítko obecného číselného pole a jeho runtime složitost roste o něco pomaleji než 2 ^ n. V důsledku toho musí být klíče asi desetkrát delší, aby poskytovaly podobné zabezpečení, což je něco, co lidé obvykle tolerují jako náklady na podnikání. Špatnou zprávou je, že když se kvantové počítače hodí do mixu, změní se celé hřiště.

Kvantové počítače: Změna hry Crypto

Kvantové počítače pracují, protože mohou mít více vnitřních stavů najednou, skrze kvantový jev zvaný „superpozice“. To znamená, že mohou zaútočit na různé části problému současně a rozdělit je na možné verze vesmíru. Lze je také nakonfigurovat tak, aby se větve, které řeší problém, navíjely s největší amplitudou, takže když otevřete krabici na Schrodingerova kočka, verze vnitřního stavu, s níž budete nejpravděpodobněji seznámeni, je samolibá kočka s dešifrovanou zpráva.

Další informace o kvantových počítačích naleznete v sekci náš nedávný článek na toto téma Jak fungují optické a kvantové počítače?Věk Exascale se blíží. Víte, jak optické a kvantové počítače fungují, a stanou se tyto nové technologie naší budoucností? Přečtěte si více !

Výsledkem toho je, že kvantové počítače nejsou jen lineárně rychlejší, tak, jak jsou běžné počítače: získání dvou, deseti či stovek krát rychleji moc nepomáhá, pokud jde o konvenční kryptografii, že jste stovky miliardkrát příliš pomalí na zpracování. Kvantové počítače podporují algoritmy, které mají menší rostoucí doby běhu, než je jinak možné. To je důvod, proč se kvantové počítače zásadně liší od jiných budoucích výpočetních technologií, jako jsou výpočet grafenu a memristeru Nejnovější počítačové technologie, které musíte vidět, abyste uvěřiliPodívejte se na některé z nejnovějších počítačových technologií, které jsou připraveny transformovat svět elektroniky a počítačů v příštích několika letech. Přečtěte si více .

Pro konkrétní příklad, Shorův algoritmus, který lze provést pouze na kvantovém počítači, může faktorovat velká čísla v log (n) ^ 3 čas, který je drasticky lepší než nejlepší klasický útok. Použití sítka obecného číselného pole k faktoru číslo s 2048 bity zabere asi 10 ^ 41 jednotek času, což se projeví na více než bilionu trilionů trilionů. Při použití Shorovho algoritmu trvá stejný problém jen asi 1000 jednotek času.

Efekt bude výraznější, čím déle budou klávesy. To je síla kvantových počítačů.

Nechápejte mě špatně - kvantové počítače mají mnoho potenciálních použití, která nejsou zlá. Kvantové počítače mohou efektivně vyřešit problém obchodního cestujícího, což vědcům umožňuje vytvářet efektivnější přepravní sítě a navrhovat lepší obvody. Kvantové počítače již mají silné využití v umělé inteligenci.

Jejich role v kryptografii však bude katastrofická. Technologie šifrování, které umožňují fungování našeho světa, závisí na obtížném řešení celého faktorizačního problému. RSA a související šifrovací schémata vám umožňují věřit, že jste na správném webu, že vám soubory stahování není propláchnuto malwarem a že lidé na vašem internetovém prohlížení nešpionují (pokud používáte Tor).

Kryptografie udržuje váš bankovní účet v bezpečí a zajišťuje světovou jadernou infrastrukturu. Když se kvantové počítače stanou praktickými, přestane tato technologie fungovat. První organizace, která vyvinula kvantový počítač, pokud svět stále pracuje na technologiích, které dnes používáme, bude v děsivě silné pozici.

Je tedy kvantová apokalypsa nevyhnutelná? Můžeme s tím něco udělat? Jak se ukazuje... ano.

Post-kvantová kryptografie

Existuje několik tříd šifrovacích algoritmů, které, pokud víme, nejsou podstatně rychlejší k vyřešení na kvantovém počítači. Tito jsou známí společně jako post-kvantová kryptografie a poskytují určitou naději, že svět může přejít na kryptosystémy, které zůstanou v bezpečí ve světě kvantového šifrování.

Mezi slibné kandidáty patří šifrování založené na mřížce, jako je Ring-Learning With Error, které odvozuje její zabezpečení z prokazatelně komplexního problém strojového učení a vícerozměrná kryptografie, která odvozuje její zabezpečení od obtížnosti řešení velmi velkých systémů jednoduchých rovnice. Více o tomto tématu si můžete přečíst na Článek na Wikipedii. Pozor: spousta těchto věcí je složitá a možná zjistíte, že vaše matematické pozadí je třeba značně posílit, než se budete moci opravdu kopat do detailů.

Z mnoha z toho plyne, že post-kvantové kryptoschémy jsou velmi cool, ale také velmi mladé. Potřebují více práce, aby byli efektivní a praktičtí, a také aby prokázali, že jsou v bezpečí. Důvod, proč jsme schopni důvěřovat kryptosystémům, je ten, že jsme na ně dostatečně dlouho házeli klinicky paranoidní géniové že všechny zjevné nedostatky by byly objeveny již nyní a vědci prokázali různé vlastnosti, které je činí silný.

Moderní kryptografie závisí na světle jako dezinfekčním prostředku a většina post-kvantových kryptografických schémat je prostě příliš nová, než aby věřila světové bezpečnosti. Dostanou se tam, ale s trochou štěstí a přípravou mohou odborníci na bezpečnost dokončit přepínač dříve, než se první kvantový počítač kdy uvede do provozu.

Pokud však neuspějí, mohou být důsledky strašné. Myšlenka na kohokoli, kdo má takovou moc, je znepokojující, i když jste optimističtí ohledně svých záměrů. Otázka, kdo nejprve vyvinul funkční kvantový počítač, je otázka, kterou by si měli všichni pečlivě sledovat, když se přesuneme do příštího desetiletí.

Znepokojuje vás nejistota kryptografie pro kvantové počítače? Jaký je váš názor? Podělte se o své myšlenky v komentářích níže!

Obrazové kredity: Binární koule Přes Shutterstock