Kvantecomputere: slutningen af ​​kryptografi?

Reklame

Kvanteberegning er en af ​​disse teknologier, der er så arkane, at TV-tegnens navn slipper det, når de vil lyde smart.

Kvanteberegning som en idé har eksisteret i et stykke tid - den teoretiske mulighed blev oprindeligt introduceret af Yuri Manin og Richard Feynman i 1982. I løbet af de sidste par år er feltet imidlertid foruroligende tættere på det praktiske.

Virksomheder som Google og Microsoft såvel som regeringsagenturer som NSA har alle forfulgt kvantecomputere i mange år nu. Et firma kaldet D-Wave har produceret og sælger enheder, der (mens de ikke er rigtige computere, og kan kun udføre et par algoritmer) udnytte kvanteegenskaber og er et andet trin på vejen mod en fuldt ud Turing-komplet Hvad er Turing-testen, og vil den nogensinde blive slået?Turing-testen er beregnet til at bestemme, om maskiner tænker. Gik Eugene Goostman-programmet virkelig Turing-testen, eller snydt skaberne simpelthen? Læs mere kvantemaskine.

Det ser ikke ud til at være urimeligt at sige, at der kan forekomme gennembrud, der tillader den første store kvantecomputer at blive bygget inden for et årti.

Så hvorfor al interessen? Hvorfor skal du passe på? Computere bliver hurtigere hele tiden Hvad er Moore's lov, og hvad har det at gøre med dig? [MakeUseOf Explains]Ulykke har intet at gøre med Moore's Law. Hvis det er den forening, du havde, forvirrer du det med Murphys lov. Du var dog ikke langt væk, fordi Moore's Law og Murphy's Law ... Læs mere - hvad er så specielt ved kvantecomputere?

For at forklare, hvorfor disse maskiner er så vigtige, bliver vi nødt til at tage et skridt tilbage og undersøge nøjagtigt, hvad kvantecomputere er, og hvorfor de fungerer. Lad os tale om et koncept kaldet "runtime complexity."

Hvad er Kørselskompleksitet?

En af de store overraskelser i de tidlige dage af datalogi var opdagelsen af, at hvis du har en computer, der løser et problem med en bestemt størrelse på en bestemt tid, ved at fordoble computerens hastighed ikke nødvendigvis lade den tackle problemer dobbelt så meget stor.

Nogle algoritmer øges i den samlede eksekveringstid meget, meget hurtigt, når problemets størrelse vokser - nogle algoritmer kan hurtigt udføres givet 100 datapunkter, men at udfylde algoritmen, der er givet 1000 datapunkter, ville kræve en computer på størrelse med Jorden, der kører for en milliard flere år. Kørselskompleksitet er en formalisering af denne idé: den ser på kurven for, hvor hurtigt kompleksiteten af ​​et problem vokser, og bruger formen på denne kurve til at klassificere algoritmen.

Generelt udtrykkes disse vanskelighedsklasser som funktioner. En algoritme, der bliver forholdsmæssigt sværere, når datasættet, der arbejder på, øges (som en simpel tællefunktion) siges at være en funktion med en runtime-kompleksitet på "n” (som i det tager det n tidsenheder til behandling n datapunkter).

Alternativt kaldes det muligvis "lineær", for når du tegner det, får du en lige linje. Andre funktioner kan være n ^ 2 eller 2 ^ n eller n! (n factorial). Disse er polynomiale og eksponentielle. I de to sidstnævnte tilfælde vokser de eksponentielle så hurtigt, at de i næsten alle tilfælde ikke kan løses til noget undtagen meget trivielle eksempler.

Kørselskompleksitet og kryptografi

Hvis du hører det her for første gang, og det lyder meningsløst og arket, lad os prøve at forankre denne diskussion. Runtime-kompleksitet er kritisk for kryptografi, der er afhængig af at gøre dekryptering meget lettere for folk, der kender en hemmelig nøgle end for dem, der ikke gør det. I et ideelt kryptografisk skema skal dekryptering være lineær, hvis du har nøglen, og 2 ^ k (hvor k er antallet af bit i nøglen), hvis du ikke gør det.

Med andre ord, den bedste algoritme til dekryptering af meddelelsen uden nøglen burde simpelthen være at gætte mulige taster, hvilket er ufravigeligt for nøgler, der kun er et par hundrede bits lange.

For symmetrisk nøglekryptografi (hvor de to parter har chancen for at udveksle en hemmelighed sikkert, inden de begynder at kommunikere) er dette temmelig let. For asymmetrisk kryptografi er det sværere.

Asymmetrisk kryptografi, hvor krypterings- og dekrypteringsnøglerne er forskellige og ikke let kan beregnes fra hinanden, er en meget sværere matematisk struktur til implementering end symmetrisk kryptografi, men det er også meget mere kraftfuldt: asymmetrisk krypto giver dig mulighed for at have private samtaler, endda overappede linjer! Det giver dig også mulighed for at oprette "digitale signaturer", så du kan bekræfte, hvem en meddelelse kom fra, og at den ikke er blevet manipuleret.

Dette er kraftfulde værktøjer og udgør fundamentet for moderne privatliv: uden asymmetrisk kryptografi ville brugere af elektroniske enheder ikke have nogen pålidelig beskyttelse mod nysgerrige øjne.

Da asymmetrisk kryptografi er sværere at opbygge end symmetrisk, er de standardkrypteringsordninger, der er i brug i dag, ikke så stærke som de kunne være: den mest almindelige krypteringsstandard, RSA, kan knækkes, hvis du effektivt kan finde de primære faktorer for en meget stor nummer. Den gode nyhed er, at det er et meget hårdt problem.

Den bedst kendte algoritme til at indregne stort antal i deres komponentprimes kaldes det generelle talfeltesigt og har en runtime-kompleksitet, der vokser lidt langsommere end 2 ^ n. Som en konsekvens heraf skal nøgler være cirka ti gange længere for at give lignende sikkerhed, hvilket er noget, som folk normalt tolererer som en omkostning for at drive forretning. Den dårlige nyhed er, at hele spillefeltet ændres, når kvantecomputere kastes i blandingen.

Kvantecomputere: Ændring af kryptospil

Kvantecomputere fungerer, fordi de kan have flere interne tilstande på samme tid gennem et kvantefænomen kaldet “superposition”. Det betyder, at de kan angribe forskellige dele af et problem samtidig, fordelt på mulige versioner af universet. De kan også konfigureres således, at de grene, der løser problemet, vinder op med mest amplitude, så når du åbner kassen på Schrodingers kat, den version af den interne tilstand, som du mest sandsynligt vil blive præsenteret for, er en selvmuglerkat, der holder en dekrypteret besked.

For mere information om kvantecomputere, tjek vores nylige artikel om emnet Hvordan fungerer optiske og kvante computere?Exascale-alderen kommer. Ved du, hvordan optiske og kvante computere fungerer, og vil disse nye teknologier blive vores fremtid? Læs mere !

Resultatet af dette er, at kvantecomputere ikke bare er lineært hurtigere, som normale computere er: at få to eller ti eller hundrede gange hurtigere hjælper ikke meget, når det kommer til konventionel kryptografi, som du er hundreder af milliarder gange for langsom til at behandle. Kvantecomputere understøtter algoritmer, der har mindre voksende løbetidskompleksiteter end ellers er muligt. Det er dette, der gør kvantecomputere grundlæggende forskellig fra andre fremtidige computerteknologier, f.eks grafen og memrister beregning Den seneste computerteknologi, du skal se for at troSe nogle af de nyeste computerteknologier, der er indstillet til at transformere verdenen inden for elektronik og pc'er i de næste par år. Læs mere .

For et konkret eksempel kan Shor's algoritme, der kun kan udføres på en kvantecomputer, faktorere stort antal i log (n) ^ 3 tid, hvilket er drastisk bedre end det bedste klassiske angreb. Brug af det generelle talfilt til at faktorere et tal med 2048 bit tager ca. 10 ^ 41 tidsenheder, hvilket fungerer til mere end en billion billioner billion. Ved hjælp af Shors algoritme tager det samme problem kun ca. 1000 enheder tid.

Effekten bliver mere markant, jo længere tasterne er. Det er magtcomputers magt.

Misforstå mig ikke - kvantecomputere har en masse potentielle ikke-onde anvendelser. Kvantecomputere kan effektivt løse det rejsende sælgerproblem, så forskere kan opbygge mere effektive forsendelsesnetværk og designe bedre kredsløb. Kvantecomputere har allerede kraftige anvendelser inden for kunstig intelligens.

Når det er sagt, vil deres rolle i kryptografi være katastrofal. De krypteringsteknologier, der tillader vores verden at fortsætte med at fungere, afhænger af, at det helhedsfaktoriseringsproblem er svært at løse. RSA og relaterede krypteringsordninger er det, der lader dig stole på, at du er på det rigtige websted, at filerne du har download er ikke fyldt med malware, og at folk ikke spionerer på din internet-browsing (hvis du bruger Tor).

Kryptografi holder din bankkonto sikker og sikrer verdens nukleare infrastruktur. Når kvantecomputere bliver praktiske, stopper al denne teknologi med at fungere. Den første organisation, der udvikler en kvantecomputer, hvis verden stadig arbejder med de teknologier, vi bruger i dag, vil være i en skræmmende magtfuld position.

Så er kvanteapokalypsen uundgåelig? Er der noget, vi kan gøre ved det? Som det viser sig... ja.

Kryptering efter kvantitet

Der er flere klasser af krypteringsalgoritmer, som vi, så vidt vi ved, ikke er betydeligt hurtigere at løse på en kvantecomputer. Disse er samlet kendt som post-kvante kryptografi og giver et håb om, at verden kan overgå til kryptosystemer, der forbliver sikre i en verden af ​​kvantekryptering.

Lovende kandidater inkluderer gitterbaseret kryptering som Ring-Learning With Error, som henter dens sikkerhed fra et påviseligt kompleks maskinindlæringsproblem og multivariat kryptografi, som henter dens sikkerhed fra vanskeligheden med at løse meget store systemer af enkle ligninger. Du kan læse mere om dette emne på Wikipedia-artikel. Pas på: meget af dette er kompliceret, og du kan opleve, at din matematikbaggrund skal øges betydeligt, før du virkelig kan grave i detaljerne.

Takeaway fra meget af dette er, at kryptoskemi efter kvantet er meget cool, men også meget ung. De har brug for mere arbejde for at være effektive og praktiske og også for at demonstrere, at de er sikre. Årsagen til, at vi er i stand til at stole på kryptosystemer, er fordi vi har kastet nok klinisk paranoide genier på dem længe nok at eventuelle åbenlyse mangler ville være blevet opdaget nu, og forskere har bevist forskellige egenskaber, der gør dem stærk.

Moderne kryptografi afhænger af lys som desinfektionsmiddel, og de fleste af de kryptografiske ordninger efter kvantum er simpelthen for nye til at stole på verdenssikkerheden til. De kommer derimod, og med lidt held og lidt forberedelse kan sikkerhedseksperter gennemføre kontakten, før den første kvantecomputer nogensinde kommer på nettet.

Hvis de mislykkes, kan konsekvenserne dog være alvorlige. Tanken på alle, der har den slags magt, er foruroligende, selvom du er optimistisk med hensyn til deres intentioner. Spørgsmålet om, hvem der først udvikler en fungerende kvantecomputer er et, som alle skal se meget nøje, når vi går ind i det næste årti.

Er du bekymret for usikkerheden ved kryptografi til kvantecomputere? Hvad tager du? Del dine tanker i kommentarerne herunder!

Billedkreditter: Binær orb Via Shutterstock