Kvantecomputere risikerer at tabe kryptokapløbet
more_vert
close

Få de daglige nyheder fra Version2 og Ingeniøren. Læs mere om nyhedsbrevene her.

close
Ved at tilmelde dig accepterer du vores Brugerbetingelser, og at Teknologiens Mediehus og IDA-gruppen lejlighedsvis kan kontakte dig om arrangementer, analyser, nyheder, tilbud mm via telefon, SMS og email. I nyhedsbreve og mails fra Teknologiens Mediehus kan findes markedsføring fra samarbejdspartnere.

Kvantecomputere risikerer at tabe kryptokapløbet

»Er det virkelig sandt, at kvantecomputere vil dræbe RSA?«

Det spørgsmål stiller Daniel Bernstein fra University of Illinois, Chicago sammen med tre kollegaer fra University of Pennsylvania i en artikel, der præsenteres på konferencen PQCrypto 2017 i næste måned.

RSA-kryptering er baseret på, at det er let at gange to store primtal sammen, men det er uhyre svært med almindelige computere at finde de to primtalsfaktorer af et sammensat tal, hvis primtalsfaktorerne består af nogle hundrede eller tusinde bit.

Har man derimod en kvantecomputer med nogle hundrede kvantebit til rådighed, så kan man legende let og lynhurtigt finde svaret med brug af Shors algoritme - og så ryger al sikkerhed ved de nuværende systemer, har vi beskrevet ved flere lejligheder.

Læs også: Kvanteskolen del 4: Kvantebit og kvantealgoritmer

Men nu viser de amerikanske forskere, at denne ‘sandhed’ måske ikke står helt til troende.

Shors algoritme og andre algoritmer, der kan knække RSA-kryptering, er godt nok uhyre effektive i forhold til de algoritmer, der kan køre på klassiske computere, men de er ikke helt simple at bruge i praksis.

Derfor er man med de små kvantecomputer med kun en håndfuld kvantebit eller qubit, man endnu har til rådighed, kun i stand til at vise, at 15 består af de to primtalsfaktorer 3 og 5, men må give op for meget større sammensatte tal.

Læs også: Kvantecomputer haves (næsten) – software ønskes

Øger man antallet af bit i krypteringsnøglen, gør man det både mere besværligt at fremstille krypteringsnøglen, men man gør det også mere besværligt at bruge Shors algoritme eller for den sags skyld en anden effektiv kvantealgoritme, som Bernstein og Co. har udviklet, der i visse tilfælde er hurtigere end Shors algoritme.

Det afgørende er, at besværet med at knække krypteringsnøglen vokser meget hurtigere med nøglens størrelse end besværet med at lave krypteringsnøglen.

Men det bliver dyrt

Nøjes man ikke med krypteringsnøgler på nogle få tusinde bits, men tager springet til flere terabit (tusinder milliarder bit), så bliver det i praksis umuligt for selv en kvantecomputer at knække krypteringsnøglen, viser forskerne i deres artikel.

Det vil være problem i sig selv at lave så store krypteringsnøgler, men forskerne fremhæver som et af deres vigtigste nye resultater, at de har fundet en metode, der kan generere en nøgle på en terabyte (2^43) med udgangspunkt i, at man først finder 2^31 primtal med 4096 bit.

Det sidste er langsommelig opgave, og post-quantum RSA er i det hele taget ikke letvægtskryptografi, skriver forskerne i deres artikel.

Ud over det enorme besvær med at lave krypteringsnøglen vil hver eneste kryptering og dekryptering koste omkring en dollar i computertid. Det er mange størrelsesordener over det, som er gældende i nuværende pre-quantum RSA, og mange vil sikkert finde, at det er helt prohibitivt.

»Men hvis det nu alligevel er den billigste metode til beskyttelse af af meget følsomme data, så vil det måske alligevel være af interesse for nogle,« fremhæver forskerne.

Alternativet til beskyttelse i en verden, hvor kvantecomputere er almindelige, er at benytte metoder, som selv kvantecomputere ikke kan knække.

Alt tyder på, at kryptokapløbet uden tvivl vil fortsætte, men den nye artikel fra amerikanerne gør det ikke lettere at udpege den endelige vinder.

sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Vi er lige her og nu i en enestående situation. Et enkelt SD kort kan indeholde 128 Gb data og youtube indeholder Pb af unik information, så hvorfor i alverden bekymre sig om noget så old-school som nøgler?

RSA kryptering var da meget fedt dengang man skulle spare på data, men nu???? det giver ikke mening.

Hvad der er brug for er, at man aftaler en fælles nøgle et eller andet sted ude på U-røret, f.eks. en bestemt video om ufo konspirationer og så aftaler at nøgle seed er f.eks. datastrøm fra 1248 ms og så frem til 13673 ms inde i videoen.

Så er den ged barberet, fuldkommen ubrydelig kryptering lige ved hånden.

For om man kan lide det eller ej: En kodning der er baseret på faktorisering af primtal vil kunne brydes - altid, det er bare et spgsm om regnekraft.

Og....... skal det være fuldkommen ubrydeligt, så kan man vel udveksle et SD kort fyldt med den reneste hvide støj. info+støj = støj der per definition ikke kan dekrypteres. 128 Gb engangskode er noget man kun kunne dømme om i enigmadagene, men nu er det jo nemt at bære rundt på et helt livs kommunikation i en hul tand.

Skal man være konspiratorisk: Er der i virkelighed "nogle" der er interesserede i at opretholde anvendelsen af koder baseret på primtalsfaktorisering fordi der allerede er fundet en matematisk bagindgang?

Hvis jeg tager fejl i ovenstående vil jeg meget gerne rettes/belæres - det er jo det man har debatsider til :)

PS: Jeg er klar over RSA kodningens fordele mht. genrering af fælles nøgler, men dem der er RIGTIGT onde - tror I ikke at de er ligeglade med at de skal udveksle f.eks. et SD kort en gang imellem?

  • 5
  • 4

Det vigtige, hvis du skal lave en helt sikker krypteringsmetode, er ikke kun antallet af bits, men også at du ikke kan vide, om den dekrypterede information er sand. Hvis dekrypteringen resultere i både løgn og latin, og der ikke findes nogen automatisk metode, til at verificere sandheden, så får du nemt en stor mængde information ud, der er mere vildledning end sandt.

  • 0
  • 0

Det vigtige, hvis du skal lave en helt sikker krypteringsmetode, er ikke kun antallet af bits, men også at du ikke kan vide, om den dekrypterede information er sand. Hvis dekrypteringen resultere i både løgn og latin, og der ikke findes nogen automatisk metode, til at verificere sandheden

Det forstår jeg godt, men jeg har svært ved at se at dette ikke kunne implementeres i en metode der baserer sig på et symmetrisk nøglepar der f.eks. er høstet på youtube, f.eks ved at skrive en checksum ind i meddelelsen før kodning.

  • 1
  • 0

Ideen med at bruge en bestemt sekvens af en mere eller mindre tilfældig Youtube video som krypteringsnøgle er et udemærket bud men desværre ikke nogen ny ide og langtfra 'ubrydelig'. Det er blot en variant af begrebet 'running key cipher', som er lidt i familie med metoder som concealment ciphers, steganografi og den slags. Det kan diskuteres om det falder under begrebet egentlig kryptografi. Men en af de helt store udfordringer indenfor kryptogafien frem til 1980'erne har været at finde på en sikker udveksling af krypteringsnøglen (der er også andre problemer - f.eks at antallet vokser med N(N-1)/2 for symmetriske nøgler).

Hvis nøglen er aftalt på forhånd er der tale om symmetrisk kryptering, i modsætning til RSA hvor Alice og Bob i princippet kun udveksler hver sin public key, også kaldet assymetrisk kryptering (antallet af nøgler vokser kun med 2N). RSA er meget mere end dette, men det er uvæsentligt i denne sammenhæng. Pointen er at alle varianter af running key cipher har samme udfordringer som de klassiske symmetriske metoder som DES, Tripple DES, AES mf. De kan være nok så svære at bryde, men udvekslingen af nøglen er stadig en sikkerhedsmæssig udfordring. Iøvrigt er - så vidt jeg er orienteret - den eneste fuldstændig sikre krypteringsmetode den såkaldte one time pad, en slags stream cipher metode, hvor nøglen er ligeså lang som beskeden der skal krypteres og den bruges kun en gang, deraf navnet. Det er næsten indlysende hvilken udfordring der er med one time pads

  • 2
  • 0

"Glemmer du ikke hele konceptet omkring digital signatur?"

Hvad mener du?

Digital signatur kan ikke implementeres med symmetrisk kryptering.

Symmetrisk kryptering med en engangsnøgle der er mindst ligeså stor som det der skal krypteres er ubrydelig. Du behøver end ikke nogen fancy algoritme: du kan bare køre XOR mellem nøgle og tekst.

Derudover er der ikke nogen kendt kvantealgoritme der angriber AES eller nogen anden udbredt symmetrisk algoritme.

Men symmetrisk kryptering er kun en lille del af det vi bruger kryptering til. De symmetriske nøgler bliver oftest udvekslet ved brug af asymmetrisk kryptering. Digital signatur er baseret på asymmetrisk kryptering. SSL certifikater er en variant af digital signatur. SSH bruger asymmetrisk kryptering til at udveksle nøgler og verificere identiteten af modparten. Etc

  • 2
  • 0

De kan være nok så svære at bryde, men udvekslingen af nøglen er stadig en sikkerhedsmæssig udfordring. Iøvrigt er - så vidt jeg er orienteret - den eneste fuldstændig sikre krypteringsmetode den såkaldte one time pad, en slags stream cipher metode, hvor nøglen er ligeså lang som beskeden der skal krypteres

Tak for et rigtigt godt svar. Såhhhh, hvis man er resourcefuld og har onde hensigter, kan man i sin organisation uddele onetime pads i form ad SD kort med støj.

Det giver et interessant paradoks: Alle dem man ønsker at fange og som ønsker at skjule sig kan (i princippet) benytte sig af ubrydelig kode, medens vi andre tosser der ikke har noget at skjule (eller ikke har tilstrækkelig med resourcer/fantasi) er henvist til at bruge kode der kan knækkes.

Hrmmmm, det er interessant. Det gør jo nærmest masseovervågning til en Darwinistisk udvælgelses metode der hjælper med at fange de dumme kriminelle, men lader de smarte slippe igennem nettet......

  • 2
  • 0

One time pads på SD kort ....tjaaa, hmmm. Det bliver noget af en bunke SD kort der skal i anvendelse. Lad os blot antage for underholdningens skyld at FE og PET skulle benytte denne metode. Nu véd jeg jo intet om hvor mange der arbejder i efterretningstjenesterne men 1000 tilsammen er jo et dejligt rundt tal ,så det gæt er ligeså godt som alle andres. Lad os sige at de 1000 medarbejdere skal sende een besked hver på daglig basis til hinanden....så dør de næppe af stress - jeg sender selv ca 50 mails/dag. Vi tager fat i vores formel for antallet af nødvendige SD kort. N(N-1)/2 =10E6*(10E6-1)/2 = 500E11 SD kort/ dag. De vejer ca 2 gram men det løber alligevel op i 1 mio tons SD kort - husk en god bunke kortlæsere , en masse paller og gaffeltrucks. Sammenlign venligst med en asymmetrisk udveksling af....1000 nøglepar. Det var bare én grund til at vi er glade for Deffie Hellman fik den strålende ide at man kunne benytte sig af indbyrdes afhængige nøglepar. Der er masser af andre grunde. En anden læser har nævnt digitale signature, foruden al internet handel ville være en noget usikker affære.

  • 0
  • 0

Jeg må hellere sætte antallet af medarbejder til 1 million og antallet af mails til 1000/dag (nu bliver de nok stresset alligevel...), ellers passer mit regnestykke ikke, men worldwide kan MI6, NSA, FBI og alle de andre sikker godt mønstre dette antal. Absurditeten i eksemplet fra en verden for alt skal foregå uden assymetrisk kryptering er nok stadigvæk indlysende ;-)

  • 0
  • 0

Jeg må hellere sætte antallet af medarbejder til 1 million og antallet af mails til 1000/dag (nu bliver de nok stresset alligevel...)

Point taken - hvis man koder alt. Men det er jo ikke sådan verdenen hænger sammen. Koder man kun meddelelser over en hvis følsomhed falder behovet dramatisk.

Uden at vide en bjælle om det, så kan jeg ikke forestille mig at der blev udvekslet mere end måske 1Gb super hemmelig information under hele WW2.

I min egen verden koder jeg kun vigtig information der ryger ud af huset, til f.eks. vores patentagent. Havde jeg udvekslet et 128 Gb kort med dem for 5 år siden, så ville jeg stadig have 123 Gb tilbage :) og af denne datamængde er grafisk information der principielt kunne undværes langt overvejende mængde.

Anyway - min pointe er, at hvis det er liv og død det gælder, så KAN man kode ubrydeligt, hvilket på et eller andet niveau gør supercomputerne i Fort Meade en smule overflødige.

  • 1
  • 0

Glemmer du ikke hele konceptet omkring digital signatur?


Det er netop der, de lange nøgler kan være interessante.

Det var så også derfor jeg spurgte, hvor langt nøglerne aktuelt skulle være.

Et paradoks er så at et dokument du gemmer i dag krypteret, vil sandsynligvis en gang i fremtiden kunne dekrypteres. Og så samme måde vil en digital signatur kunne spoofes i fremtiden, så fortiden kan ændres. I længden kan digital signatur altså ikke stå alene.

Et sjovt eksempel jeg hørte for nyligt, var at Dronningen stadigt underskriver love i hånden, hvorfor gør hun ikke det digitalt? Tænker man nærmere over det, så viser netop det eksempel svagheden ved digital signatur. Groft sagt så bygger vores nuværende digitale signaturs gyldighed sig på Dronningens underskrift.
Uden andre indikationer og registreringer, kan man altså ikke om bare 10 år stole på en digital signaturs gyldighed.

Derudover er der ikke nogen kendt kvantealgoritme der angriber AES eller nogen anden udbredt symmetrisk algoritme.


Så hvorfor sidder vi så egentligt og diskuterer det her?
Fordi AES som det bruges i dag, også på et tidspunkt må bukke under for en supercomputer?

  • 0
  • 0

Personligt tror jeg ikke, at man man nogensinde får bygget en kvantecomputer, der kan faktorisere primtalsprodukter hurtigere end en supercomputer med klassisk logik. Der er en del, der tyder på, at det at undgå, at en kvantetilstand henfalder til en klassisk tilstand stiger voldsomt med antallet af sammenfiltrede kvantebit og antallet af operationer, der laves på disse. Hvor voldsomt vides ikke, men det ville ikke undre mig, hvis det var eksponentielt.

Derudover er der faktisk ret få algoritmer, som man p.t. ved kan køre eksponentielt hurtigere på en kvantecomputer end den bedst kendte klassiske algoritme. Det er en misforståelse, at N kvantebits tillader næsten vilkårlige beregninger p 2^N kombinationer på en gang -- det, man kan, er at "skubbe" en kvantetilstand hen imod en løsning ved at lade de komponenter af kvantetilstanden, man ikke ønsker, interferere negativt, sådan at sandsynligheden for at man, når man til sidst aflæser resultatet (som dermed kollapser til en klassisk tilstand), rammer et brugbart resultat, øges. Så generelt skal en kvanteberegning gentages nogle gange, indtil man tilfældigvis rammer et brugbart resultat. Algoritmens formål er således at maksimere denne sandsynlighed, og det er alt andet end trivielt.

Schors algoritme er en af de få, der rent faktisk giver et stort teoretisk speedup over klassiske computere. Så moralen er nok, at man skal bruge noget andet end primtal eller elliptiske kurser til sin kryptering, hvis man vil være sikret mod kvantecomputer. Problemet er, at det er svært at vide, om der en gang i fremtiden findes en kvantealgoritme til den valgte metode. Men det samme gælder også klassiske computere: Det er muligt, at man en gang i fremtiden finder en polynomiel algoritme til faktorisering af primtalsprodukter eller finde diskrete logaritmer i elliptiske kurver.

  • 2
  • 0

Fordi AES som det bruges i dag, også på et tidspunkt må bukke under for en supercomputer?

Det er muligt at det sker men det er ikke emnet. I forhold til kvantecomputere er AES sikker i forhold til de algoritmer vi kender idag. Konsekvensen af det er at hvis du krypterer din harddisk med AES med en nøgle baseret på et helt almindeligt kodeord, så er der ikke nogen kendt kvantealgoritme der truer sikkerheden af det.

Det der er truet er mange former for digital signatur og nøgleudveksling. Herunder eksempelvis SSL som der bruges på https://ing.dk. Selve trafikken er krypteret med AES som ikke kan brydes, men hvis du kan opsnappe nøglen, så er det ligemeget at AES i sig selv er sikker. SSL fungerer groft sagt ved at server og klient opfinder en ny tilfældig nøgle med jævne mellemrum og udveksler så nøglen ved hjælp af asymmetrisk kryptering. De onde lytter med på denne nøgleudveksling og kan herefter dekryptere AES trafikken, da de har nøglen.

  • 0
  • 0

Man kan vel ikke tabe noget man ikke har vundet, medmindre konkurrencen stadig er i gang.
Problemet er vel bare at det kun er teoretisk kvantekomputeren kan vinde, den har jo ikke bit nok endnu om den overhovedet findes.

  • 0
  • 1