Skal krypteringsfolk frygte kvantecomputere?

Illustration: Golden Sikorka/Bigstock
Eksisterende krypteringsteknologi kan være nem at bryde, når kvantecomputerne er klar. Men hvornår er det?

Vil eksisterende krypteringsløsninger kunne overleve kvantecomputere? Det blev drøftet under flere paneldiskussioner, foredrag og præsentationer på Infosecurity-konferencen, som Version2 afholdt i sidste uge.

Bryd kryptering på 1 milliard år eller 100 sekunder

Kvantefysikeren Peter Krogstrup holdt en keynote om kvantecomputere, hvor han blandt andet kom ind på, hvorfor kvantecomputere er så interessante i krypteringsmæssig sammenhæng.

Såkaldte semiprimes, tal med præcis 2 primtalsfaktorer, er meget vigtige indenfor RSA-kryptering.

Med klassiske computere vil det eksempelvis tage en millard år at opløse RSA-2048, et tal med 617 cifre, i to primtals-faktorer og dermed bryde krypteringen.

Hvis man har en kvantecomputer med 4000 qubits, vil det tage 100 sekunder.

Med andre ord kan kvantecomputere underminere en vigtig del af den eksisterende kryptering.

Hvis man altså har en velfungerende kvantecomputer.

Hvilket ikke er tilfældet i dag.

Der findes kvantecomputere i dag, men levetiden for de såkaldte qubits, der kan antage værdierne 0 og 1 på samme tid og dermed er grundlaget for den eksponentielle forøgelse af regnekraften i kvanrecomputere, har meget kort levetid.

Omkring 500 mikrosekunder for de bedste.

Peter Krogstrup og hans team i Lyngby arbejder derfor på at udvikle materiale, der kan gøre qubits mere stabile, end de er i dag, men han turde dog ikke give et bud på, hvornår de mere stabile qubits fra Lyngby-laboratoriet er klar.

»Det er grundforskning vi laver, så det er svært at sætte tid på.«

Kryptologi-passiar

I en passiar om kryptologi mellem Version2-bloggeren Poul-Henning Kamp og Danmarks grand old man indenfor kryptering, Peter Landrock, stifter af Cryptomatic, kom spørgsmålet om kvantecomputere i relation til kryptering også op.

»De sidste 5 år har jeg hørt, at kvantecomputere bliver klar om 10-15 år. Så længe det fortsætter med at være om 10-15 år, så er jeg godt tilfreds,« sagde Peter Landrock, der dog også kunne fortælle, at han og hans kollegaer følger udviklingen nøje.

»Det gælder om ikke at blive taget med bukserne nede, hvis de bliver bygget. De public key-krypteringsteknikker, vi bruger i dag, som RSA og Diffe-Hellman til nøgleudveksling, de vil kunne brydes,« lød det fra Peter Landrock.

Post-kvantekryptering

Det samme gør sig gældende ved Triple DES og AES med 128-bit kryptering, der anses som stærk kryptering i dag, men som vil kunne brydes af kvantecomputere.

Dog anses AES med 256 bits for at være kvantecomputer-resistent.

Der bliver da også forsket i andre krypteringsalgoritmer, der kan modstå kvantecomputernes forventede regnekraft; såkaldte post-kvantekrypteringsalgoritmer.

Peter Landrock er eksempelvis tilknyttet Newton Instituttet på Cambridge Universitet, hvor der forskes i og udvikles den slags algoritmer. Peter Landrock advarer dog mod at tro, at det vil være enkelt at erstatte eksisterende krypteringsalgoritmer med nye:

»Vi skal huske, at de krypteringsalgoritmer, vi bruger i dag, har været anvendt i mange år, og der ligger 20-30 års forskning og test bag. De nye forslag til public key-krypteringsteknikker, der er post-kvantekryptering er ikke testet på samme måde, og der kan vi godt risikere, at en eller anden genial kryptolog finder en måde at bryde dem på.«

Qubit ja/nej

Det er en gylden regel i journalistik, at en overskrift med et spørgsmålstegn altid kan besvares med et 'nej'. I tilfældet med kryptering og kvantecomputere viser det sig at være lidt mere kompliceret.

Svaret er 'ja, men ikke endnu' – hvilket selvfølgelig kan tolkes som et nej, men ikke et kategorisk nej. Eller måske et qubit ja/nej?

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Følg forløbet
Kommentarer (22)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Bjarne Nielsen

Jeg tror det var Bo Bjørnvig, som sagde om scifi og tendensen til dystropier, at scifi-fans ikke er bange for fremtiden; de glæder sig, og er bare i gang med at forberede sig!

De 'krypteringsfolk', som jeg snakker med, virker til at have det på samme måde med fremtiden.

  • 0
  • 0
Niels Dybdahl

hvornår ved man at man har brudt koden?

Jeg har læst andetsteds at det drejer sig om asymmetrisk kryptering hvor den offentlige nøgle er et tal som er produktet af to store primtal. Den private nøgle formoder jeg er så de to primtal.
Så opgaven består i at finde et tal som går op i tallet fra den offentlige nøgle.
Men hvordan man får en kvantecomputer til at regne det ud, kunne jeg godt tænke mig at se et simpelt eksempel på.

  • 0
  • 0
Jens Madsen

Jeg har længe undret mig over, at man kan dekryptere en vilkårlig “tekst”. Nok kan computerne arbejde hurtigt, men hvornår ved man at man har brudt koden? Det skal der vel et menneske til at afgøre?


Det afhænger af krypteringen. Nogle krypteringer kan brydes ved at løse et matematisk problem, f.eks. RSA.

Krypteringer, som giver et svar uanset koden, og hvor du skal kunne vurdere om svaret er korrekt, er langt mere sikre for kvantecomputere end RSA. I nogle tilfælde, er det nemt at se om den dekrypterede besked indeholder kendte ord eller sætninger. Er du ikke i stand til, at kunne dekode om svaret er korrekt, f.eks. ved at have delvis kendskab til svaret, så er det ofte umuligt.

Du kan lave krypteringer af tekst der indeholder mange svar, og hvor at svaret vælges med kodeordet. Det betyder, at man også kan have et stort antal hemmelige kodeord som er nemme at huske, og som man giver en eventuel fjende, og så vil de kunne se det svar man ønsker at give dem.

  • 0
  • 0
Jens Madsen

Jeg husker en gang en film, hvor hemmelige efterretninger blev omskrevet til indkøbslister.

Det er også et eksempel på flertydig kodning, og har den fordel, at den er robust overfor skjulte mikrofoner anbragt i udstyret.

Alt i alt, så er kvantecomputere næppe et problem. Men, de kan være et problem for de krypteringer vi anvender i dag. RSA er meget anvendt i dag, og kan sandsynligvis brydes med kvantecomputere teoretisk.

  • 0
  • 0
Jens Jensen

Et eller andet sted er det nu interessant at lige meget hvor lang tid der går inden kvantecomputeren kommer, så virker det til, at en sådan vil være en "gigantisk teknisk himstragims". Ala hvordan en computer så ud i 1940'erne.

Dvs. at man i en årrække vil være i en situation hvor man, hvis man er teknologisk stærk nok, og har midlerne, vil have et forspring over for "pøblen", som endnu ikke har teknologien tilgængelig i deres hjem/smartphones.

  • 0
  • 0
Ditlev Petersen

Krypteringer, som giver et svar uanset koden, og hvor du skal kunne vurdere om svaret er korrekt, er langt mere sikre for kvantecomputere end RSA. I nogle tilfælde, er det nemt at se om den dekrypterede besked indeholder kendte ord eller sætninger. Er du ikke i stand til, at kunne dekode om svaret er korrekt, f.eks. ved at have delvis kendskab til svaret, så er det ofte umuligt.


Og så er der variationer over engangs-kryptering med meget lang nøgle (one-time cypher pad). Her kan man i princippet løbe samtlige nøgler igennem (ingen hjælp fra kvantecomputere), men det vil tage evighedernes evighed. Til gengæld vil man jo få svaret på et eller andet tidspunkt. Men også hver evige eneste mulige tekst med samme længde. Så man er ikke spor klogere, for mange af dem vil lyde plausible.
Ellers vil man f.eks. se på bogstavhyppigheden i en mulig dekryptering - jo mere ujævn den er, desto mere sandsynligt er det, at man har en valid nøgle. Man behøver ikke lede efter kendte ord (sproget kan jo være swahili eller koptisk).

  • 0
  • 0
Per Larsen

Som det tydeligt er refereret er det grundforskning.
I medierne fremstår det som der findes brugbare kvantecomputere.
Det gør der så ikke.
Det er sådan set 1st. gang jeg ser at de "CPU'er" eller QBits, som anvendes kun holder i 0,5 sek. Det kan så være, at man kun behøver at ha' den tændt i 5 sekunder for at få sin beregning? Men der er langt igen.
Da det stadig af indforståede betegnes som grundforskning, vil det i mine øjne vare mere end 10 - 15 år, at få noget der fungerer i en operation. Angiveligt mindst det dobbelte.
Når man nu er nede og lege med kvante fysiken og de mindst elementer vi har her i universet, er der givet udefra kommende interferens, som kan påvirke et sådant system, og som man angiveligt ikke kender til. Det vil man vel først erkende, når der findes QBits, som kan holde sig "vågne" i mere end 0,5 sek?

Mvh.

  • 0
  • 1
Torben Mogensen Blogger

hvornår ved man at man har brudt koden?

Der er to slags kryptering: Offentlig nøgle kryptering, og hemmelig nøgle kryptering.

Som andre svar allerede har nævnt, så kan man med offentlige nøgler se, om man har fundet den private nøgle ved at lave en matematisk beregning på den offentlige og den private nøgle -- helt uden at have data.

Med hemmelige nøgler bruges samme nøgle til indkodning og til afkoding, så man har ikke en offentlig nøgle, man kan bruge til at se, om man har gættet den rigtige hemmelige nøgle. Til brydning af kryptering med hemmelige nøgler har man altså brug for data.

I bedste fald har man et eller flere eksempler på tekst før og efter kryptering. Så kan man kontrollere om et gæt på en nøgle er rigtigt, om man kan analysere sammenhængen mellem klartekst og krypteret data til at indsnævre søgningen efter nøgler.

Hvis man kun har en krypteret tekst, kan man prøve at afkode den med et gæt på en nøgle og se, om det "ligner" en rigtig tekst. Det kan man gøre med statistiske metoder (f.eks. fordelingen af bogstaver og andre tegn i teksten). Da man ikke har en præcis facitliste (som f.eks. en specifik klartekst), er det vanskeligere at indskrænke søgerummet.

Jeg tror ikke, at kvantecomputere hjælper i det sidste tilfælde, men de kan hjælpe i de tilfælde, hvor man har en præcis facitliste. Men det kræver som sagt mange qubits og mange operationer, før de klapper sammen til klassiske bits. Om man nogensinde når så langt er tvivlsomt, men ikke umuligt. Men selv om det er muligt, så kan man i de fleste tilfælde omgå problemet ved at bruge mange flere bits i sine krypteringsnøgler. Det giver så langsommere kryptering, men det må man leve med.

  • 2
  • 0
Michael Aggerholm

Kan anbefale følgende videoer om emnet:

The mechanics of quantum computers
https://www.youtube.com/watch?v=IrbJYsep45E

Why Quantum Computing Requires Quantum Cryptography
https://www.youtube.com/watch?v=pi7YwxxZQ5A

How Quantum Computers Break Encryption | Shor's Algorithm
https://www.youtube.com/watch?v=lvTqbM5Dq4Q

Både PBS Space Time og PBS Infinite Series er forøvrigt rigtig gode kanaler for de videnbegærlige .. :-)

  • 0
  • 0
Jens Madsen

Indtil nu, har vi ikke set overbevisende eksempler på, at kvantecomputere er muligt. Vi ved f.eks. ikke, om naturens love giver en ukendt grænse for antallet af q-bits, måske relateret til energiforbrug. I de første mange år, tror jeg at forskningen i kvantecomputere vil blive ren grundforskning. Det udelukker ikke, at det kan bruges til noget, men sikkert ikke til noget væsentligt, som ikke kunne løses på anden måde. Viden om kvantemekanik - herunder også forskningen i kvantecomputere - kan dog sikkert give os noget. Måske indenfor måling. Indenfor forståelse af støj. Og måske indenfor meget, vi endnu ikke ved.

Kvantecomputere tror jeg derimod ikke vi skal forvente os noget af i de første mange år.

  • 0
  • 0
Jens Madsen

fremtiden er nærmere end det:) Du får ikke hele computere endnu men IBM lader dig køre algoritmer på deres HW:
https://www.research.ibm.com/ibm-q/technology/devices/


Når jeg ser på listen, er vi langt fra at kvantecomputere kan udregne noget, som normale computere ikke kan.

Det som jeg frygter, at at der er en ukendt sammenhæng mellem energi, støj, tid, og q-bits, som sætter en grænse for, hvad der kan opnås, og at kvantecomputere derfor ikke kan løse opgaver, som ikke kan løses på anden måde.

Vi skal op i langt større antal Q-bits, og langt længere ned i fejlrate, før vi ved om der er nogle fysiske fundementale problemer, der umuliggør at kvantecomputere kan blive bedre end normale computere. Så længe, at vi kan simulere en kvantecomputer på en kraftig computer, eller på almindeligt hardware lavet til det, så er vi ikke i nærheden af eventuelle problemer.

Det er sjovt, at man kan få lov at låne en af IBM's kvantecomputere. Men, jeg tror ikke, at vi kan bruge dem til at løse problemer, som ikke kunne løses på anden måde.

  • 0
  • 0
Poul-Henning Kamp Blogger

Jeg husker en gang en film, hvor hemmelige efterretninger blev omskrevet til indkøbslister.

Det er ikke flertydig kodning, det er "Pre-Shared-Key".

Hvis ikke man på forhånd har aftalt hvad "agurk" betyder, er den "rigtige" modtager af beskeden lige så meget på herrens mark som alle andre.

I fiktion har man nogen gange brugt den ide at en besked kunne være så meget "out of character" af modtageren med det samme kunne gennemskue hvad den virkelige besked var.

I virkelighedens verden har det trick vist været begrænset til opdage at "Der er noget der slet ikke stemmer her."

  • 4
  • 0
Poul-Henning Kamp Blogger

Det vil man vel først erkende, når der findes QBits, som kan holde sig "vågne" i mere end 0,5 sek?

Det er faktisk det mindste problem: Kvantecomputere, eller mere specifikt qbits, kører som udgangspunkt lige godt i begge retninger, de fundamentale operationer er alle reversible.

Det er en ret spindsfindig detalje som ikke har den helt store betydning så længe man bakser med en håndfuld qbits som dårligt nok virker.

Men som antallet af qbits vokser vil sandsynligheden for at de alle vælger at arbejde i samme retning falde dramatisk. Ikke helt 1/N² men kraftigt i den retning.

Løsningen er naturligvis at man så at sige skal lade dem arbejde på et "skråplan" så de har nemmere ved at køre den ene vej end den anden.

Mig bekendt er der ingen der har så meget som en ide til hvordan man i givet fald skulle bære sig ad med det...

  • 1
  • 0
Torben Mogensen Blogger

Det kaldes vist også "åbne koder". Kendt fra BBCs udsendelser under krigen. Totalt nonsens - undtagen for de indviede.

Jeg har læst en historie, hvor en besked var indkodet i en krydsordsopgave. Beskeden var rettet mod en person, der var kendt for altid at løse dagens krydsordsopgave, hvorimod de, der ikke skulle modtage beskeden, regnedes med ikke at gøre dette. Der var tale om den engelske type "cryptic crossword", som er mere udfordrende end en almindelig dansk krydsordsopgave.

  • 0
  • 0
Torben Mogensen Blogger

Kvantecomputere, eller mere specifikt qbits, kører som udgangspunkt lige godt i begge retninger, de fundamentale operationer er alle reversible.

Det er en ret spindsfindig detalje som ikke har den helt store betydning så længe man bakser med en håndfuld qbits som dårligt nok virker.

Men som antallet af qbits vokser vil sandsynligheden for at de alle vælger at arbejde i samme retning falde dramatisk. Ikke helt 1/N² men kraftigt i den retning.

Det er nu ikke det helt store problem. De fleste enkelte kvantegates (C-not gates, Toffoli gates, Hadamard gates, osv) er selvinverse, så det er ligegyldigt om de hver for sig udføres forlæns eller baglæns. Og selv om man i reglen beskriver et kvantekredsløb som et antal ledninger forbundet med kvantegates, uden at der er retning på ledningerne, så er kvantecomputere (endnu) ikke bygget på den måde: qubits ligger ikke i ledninger, men i beholdere. Når man skal udføre en kvanteoperation, forbindes de relevante beholdere med en gate, hvorved operationen udføres. Når operationen er færdig, fjernes denne gate, og en ny sættes på. Det er en lidt grov simplificering, men det faktum, at der er en klar temporal sekvens i anvendelsen af gates, betyder, at kvantecomputeren ikke lige pludselig af sig selv begynder at køre baglæns på nogle qubits.

Det er et langt større problem, at, når man anvender en gate på nogle qubits, så klapper de sammen til en klassisk tilstand. De nuværende kvantecomputere kan lave et par hundrede etbitsoperationer og en snes tobitsoperationer, før dette sker -- og tobitsoperationerne skal ske på naboqubits.

  • 0
  • 0
Palle Due Larsen
  • 0
  • 0
Log ind eller Opret konto for at kommentere