Kvantecomputere slutningen af ​​kryptografi?

Kvanteberegning er en af ​​disse teknologier, der er så arcane, 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 korrekte computere og kun kan udføre et par algoritmer) udnytter kvanteegenskaber, og er et andet trin på vejen mod en fuldstændig Turing-komplet Hvad er Turing-testen, og vil den nogensinde blive slået? 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? kvantemaskine.

Det forekommer ikke 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 går hurtigere hele tiden Hvad er Moore's lov, og hvad har det at gøre med dig? [MakeUseOf Explains] Hvad er Moore's lov, og hvad har det at gøre med dig? [MakeUseOf Explains] Uheld har ikke noget at gøre med Moore's Law. Hvis det er den forening, du havde, forvirrer du den med Murphys lov. Du var dog ikke langt væk, fordi Moore's Law og Murphy's Law ... - 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 starte med at tale om et kaldet koncept “løbetid kompleksitet.”

Hvad er Runtime Complexity?

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 af en bestemt størrelse på en bestemt tid, er det ikke nødvendigt at fordoble computerens hastighed til at tackle problemer dobbelt så stor.

Nogle algoritmer øges i den samlede eksekveringstid meget, meget hurtigt, når problemets størrelse vokser - nogle algoritmer kan hurtigt udfyldes med 100 datapunkter, men at udfylde den algoritme, der er givet 1000 datapunkter, ville kræve en computer på størrelse med jorden, der kører for en milliarder år. Runtime-kompleksitet er en formalisering af denne idé: den ser på kurven for, hvor hurtigt kompleksiteten af ​​et problem vokser, og bruger formen på den 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, der skal behandles n datapunkter).

Alternativt kaldes det muligvis “lineær”, fordi 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 disse ting for første gang, og det lyder meningsløst og arket, lad os prøve at grundlægge 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 taster, 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 at implementere end symmetrisk kryptografi, men det er også meget mere magtfuldt: asymmetrisk krypto giver dig mulighed for at have private samtaler , selv over tappede linjer! Det giver dig også mulighed for at oprette “digitale underskrifter” for at give dig mulighed for at 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.

Fordi asymmetrisk kryptografi er sværere at opbygge end symmetrisk, er standardkrypteringsskemaerne, 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 stort antal. 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 talfiltesigt 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 kvantefenomen, der kaldes “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, ender op med mest amplitude, så når du åbner boksen på Schrodingers kat, er versionen af ​​den interne tilstand, som du mest sandsynligt bliver præsenteret for, en selvtilfreds - ser kat ud med en dekrypteret besked.

For mere information om kvantecomputere, se vores nylige artikel om emnet Hvordan fungerer optiske og kvante computere? 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? !

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. Dette er hvad der gør kvantecomputere grundlæggende forskellig fra andre fremtidige computerteknologier, som grafen- og memrister-beregning. Den seneste computerteknologi, du er nødt til at se for at tro Den nyeste computerteknologi, du er nødt til at se for at tro. at transformere verdenen af ​​elektronik og pc'er i de næste par år. .

Som et konkret eksempel kan Shors 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 kraften i kvantecomputere.

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 de filer, du downloader, ikke er fyldt med malware, og at folk ikke spionerer på din internetbrowsing (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 fungerer 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, der så vidt vi ved ikke er væsentligt 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 vil forblive sikre i en verden af ​​kvantekryptering.

Lovende kandidater inkluderer gitterbaseret kryptering som Ring-Learning With Error, som henter sin sikkerhed fra et påviseligt komplekst maskinindlæringsproblem, og multivariat kryptografi, som henter sin sikkerhed fra vanskeligheden ved at løse meget store systemer med enkle ligninger. Du kan om dette emne på Wikipedia-artiklen. 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 til, at nogen åbenlyse mangler ville være blevet opdaget i øjeblikket, og forskere har bevist forskellige egenskaber, der gør dem stærke.

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. Men de kommer dertil, og med lidt held og forberedelse kan sikkerhedseksperter gennemføre skiftet, før den første kvantecomputer nogensinde kommer på nettet.

Hvis de mislykkes, kan konsekvenserne dog være alvorlige. Tanken på nogen, 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 overfor kvantecomputere? Hvad tager du? Del dine tanker i kommentarerne herunder!

Billedkreditter: Binær orb via Shutterstock