Kryptering kan vinde over kvante-computere
I en verden, hvor digital kommunikation opsamles og analyseres i stor stil, må vi ty til kryptering for at opretholde forretningshemmeligheder og værne om privatlivets fred.
De mest populære metoder til kryptering giver dog ingen sikkerhed over for en fjende med adgang til en passende stor kvantecomputer.
Men sådan én er der ingen, der har – og så er der vel ingen grund til bekymring? Jo, for det kunne jo tænkes, at nogen allerede i dag opsnapper krypterede meddelelser og gemmer dem, til de en dag står med den kvantecomputer, som kan låse op for alle hemmelighederne.
På den baggrund har National Security Agency (NSA) i USA meddelt, at de vil igangsætte et program for overgang til krypteringsalgoritmer, der er sikre over for en kvantecomputer.
Den amerikanske it-sikkerhedsekspert Bruce Schneier skriver på sin blog, at vi alle bør følge NSA og senest inden for en periode på 10 år skifte til kvantemodstandsdygtige algoritmer – og sandsynligvis bør vi handle hurtigere end det.
Et europæisk forskningsprojekt under EU kaldet PQCRYPTO, hvor bl.a. DTU indgår, har i denne måned udsendt en kort rapport med anbefalinger til, hvilken teknologi der bør benyttes i langtidssikre såkaldte post-kvantesystemer.
Projektets leder, professor Tanja Lange fra Technische Universiteit Eindhoven i Holland, anbefaler, at man allerede nu tager post-kvante- kryptering i brug, når det gælder sundhedsoplysninger og tophemmelige dokumenter med en tids¬horisont på mere end 10 år.
Fra professor Lars Ramkilde Knudsen fra DTU, der leder det danske bidrag til PQCRYPTO, lyder det lidt mere forsigtigt:
»Der er ingen grund til panik, men der er et reelt problem.«
Artiklen fortsætter under illustrationen
Klassiske metoder
Kryptering med brug af offentlige og private nøgler er baseret på, at visse matematiske operationer er lette at udføre den ene vej, men meget svære (i praksis umulige) den anden vej.
Det er eksempelvis let at gange to store primtal med flere hundrede cifre. Har man derimod et tal, som man ved er produktet af to sådanne store primtal, så er det umuligt at finde de to primtalsfaktorer.
Dette er princippet bag RSA-krypteringen, der er opkaldt efter Ron Rivest, Adi Shamir og Leonard Adleman og udviklet i 1977.
Et alternativ er Diffie-Hellman- metoden fra 1976 udviklet af Whitfield Diffie og Martin Hellman og baseret på det såkaldte diskrete logaritme-problem.
Vælger man to tal g og x og et stort primtal p, så er det let at udregne y = gx modulo p, dvs. den rest man får for gx efter division med p.
Det er derimod meget vanskeligt at finde x, hvis man kender y, g og p.
En tredje metode, elliptisk kurve- kryptografi, er beslægtet med Diffie-Hellman, men benytter egenskaber ved elliptiske kurver af formen y2 = x3 + ax + b.
For sådanne kurver kan man definere regler for, hvordan man adderer to punkter, og hvordan man fordobler et punkt. På den måde kan man let beregne et punkt Q med udgangspunkt i et punkt P, så Q = kP, hvor k er et heltal.
Til gengæld er det vanskeligt at finde k, hvis man kender P og Q – medmindre nogen har installeret en form for bagdør i algoritmen; en risiko, som er blevet intenst diskuteret efter Edward Snowdens afsløringer af NSA’s omfattende overvågningsprogram.
21 = 3 x 7
Hvad der er umuligt på en klassisk computer, kan dog blive muligt med en kvantecomputer.
Den amerikanske matematiker Peter Shor formulerede i 1994 en algoritme, som kan knække RSA, Diffie-Hellman og elliptisk kurve-kryptering. Algoritmen blev første gang implementeret i 2001 på en lille kvantecomputer med syv kvantebits.
Beregningen på computeren kunne vise, at primtalsfaktorerne i 15 var 3 og 5. I 2012 lykkedes det med algoritmen at vise, at primtalsfaktorerne i 21 er 3 og 7.
Disse beregninger ryster ikke mange. Men den dag, man får en kvantecomputer med 100 kvantebit eller noget lignende, så giver RSA og lignende metoder ikke længere garanti for noget som helst.
Hvornår en sådan computer bliver fremstillet, hersker der stor usikkerhed om. Nogle taler om en horisont på 10 år, andre om 50 år.
»Jeg ved ikke, hvornår vi får en kvantecomputer, men det skal nok ske en dag,« siger Lars Ramkilde Knudsen.
Selv kvantecomputere har dog deres begrænsninger.
Der kendes flere krypterings¬metoder, som ikke kan knækkes af en kvantecomputer – fordi der ingen kvantealgoritmer findes.
Blandt de mest interessante er et princip udviklet af amerikaneren Robert McEliece i 1970’erne – på samme tid som RSA- og Diffie-Hell¬man-metoderne så dagens lys – og et nyere princip udviklet af den israelske matematiker Oded Regev for 10 år siden.
PQCRYPTO anbefaler McEliece- princippet, der gennem mere end 35 år har modstået alle forsøg på at blive brudt.
McEliece har forbindelse til princippet om fejlkorrigerende koder, som anvendes inden for tele- og datakommunikation:
Ved eksempelvis at omsætte information bestående af fire bit til en besked på syv bit kan en modtager finde og rette fejl i det modtagne signal sendt over en støjfyldt kanal og derved bestemme informationen i de fire oprindelige bit.
McEliece benytter et mere avanceret system kaldet Goppa-koder, hvor man omsætter k bit til n bit (n > k), og hvor koden kan rette op til t fejl.
Ved McElice-kryptering omdannes det Goppa-kodede signal med en offentlig nøgle til en besked, som kun en person med den tilhørende private nøgle kan transformere til noget, som kan afkodes med en algoritme udviklet af den irske matematiker Nicholas J. Patterson
Krypteringseksperten professor Ivan Damgård fra Aarhus Universitet hælder dog mere til såkaldt lattice-baseret kryptografi og en metode, som kaldes ‘learning with errors’ (LWE). Princippet i LWE kan kort illustreres på følgende vis:
Det er let at løse fire ligninger med fire ubekendte. Handler det i stedet om syv ligninger – igen med fire ubekendte – og er hver ligning kun tilnærmelsesvis korrekt inden for en given fejlmargen, så kan det være ganske kompliceret at finde de fire ubekendte, så alle ligninger er opfyldt inden for den givne fejlmargen.
Gitre (lattices) er inden for matematikken en regelmæssigt placeret punktmængde, f.eks. alle heltallige koordinater i et koordinatsystem.
Med brug af en offentlig nøgle gemmer man så at sige informationen et sted, som ligger i en vis afstand fra et punkt i gitteret, som ikke kun har to dimensioner, men rigtig mange. Der findes ingen algoritme på en klassisk computer eller en kvantecomputer, der kan løse dette LWE-problem – men den, der besidder en privat nøgle svarende til den offentlige nøgle, kan forholdsvis enkelt gøre det.
Selv om Ivan Damgård ikke giver nogen garanti for, at en kvantealgoritme aldrig kan findes for LWE, har han svært ved at forestille sig det.
»Det vil være virkelig rystende, hvis man havde en algoritme, der kunne løse LWE. Det ville have store konsekvenser også uden for kryptoverdenen,« siger han.
Lars Ramkilde Knudsen udtrykker det på denne måde:
»Vi kan ikke gardere os mod, hvad der bliver muligt i fremtiden. Vi må basere os på erfaring om, hvad der er svært i dag.«
...men det er dyrt at lave god journalistik. Derfor beder vi dig overveje at tegne abonnement på Version2.
Digitaliseringen buldrer derudaf, og it-folkene tegner fremtidens Danmark. Derfor er det vigtigere end nogensinde med et kvalificeret bud på, hvordan it bedst kan være med til at udvikle det danske samfund og erhvervsliv.
Og der har aldrig været mere akut brug for en kritisk vagthund, der råber op, når der tages forkerte it-beslutninger.
Den rolle har Version2 indtaget siden 2006 - og det bliver vi ved med.
