Få bedre it-sikkerhed med elliptiske kurver

Illustration: arkivfoto

Primtal, diskrete logaritmer og elliptiske kurver – som vel at mærke ikke har noget med ellipser at gøre – er nøglen til sikker kommunikation.

Hvis metoderne anvendes korrekt, må selv det amerikanske National Security Agency (NSA) give op.

‘Stol på matematikken, kryptering er din ven,’ som amerikaneren Bruce Schneier skrev for nylig i The Guardian om afsløringerne af NSA’s omfattende overvågningsprogram.

Bruce Schneier er en af verdens førende eksperter i kryptering og it-sikkerhed, og hans synspunkt deles af professor Ivan Damgård fra Aarhus Universitet:

‘Skellet går mellem algoritmer, der har en troværdig ‘stamtavle’, og dem, der ikke har,’ skrev han i en kommentar på ing.dk med henvisning til, at NSA formodes at have samarbejdet med visse leverandører om at installere bagdøre i krypteringssystemer.

Men hvorfor er det stadig tilforladeligt at stole på matematikken?

Størst udbredelse til sikker kommunikation har asymmetriske algoritmer med to forskellige nøgler til kryptering og dekryptering. Skal Alice sende en besked til Bob, benytter hun Bobs offentlige nøgle til at kryptere sin besked. Kun Bob, som er i besiddelse af sin egen private nøgle, kan dekryptere beskeden.

Nøglerne genereres med hjælp af matematiske principper, hvorefter det er simpelt at foretage en regneoperation, mens det er vanskeligt – i praksis umuligt – at foretage den modsatte regneoperation.

De mest almindelige metoder er RSA og Diffie-Hellman.

RSA-kryptering, opkaldt efter Ron Rivest, Adi Shamir og Leonard Adleman, udnytter, at det er meget let at gange to store, mangecifrede primtal med hinanden, men vanskeligt at bestemme, hvilke to primtalsfaktorer der indgår i et sammensat tal med eksempelvis flere hundrede cifre.

Alternativet er en metode udviklet af Whitfield Diffie og Martin Hellman, som er 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 = g^x modulus p, dvs. den rest man får for g^x efter division med p.

Det er derimod meget vanskeligt at finde x, hvis man kender y, g og p.

Illustration: Ingeniøren

Elliptisk kurve-kryptografi er beslægtet med Diffie-Hellman, men benytter egenskaber ved elliptiske kurver af formen y^2 = x^3 + ax + b.

Princippet blev opdaget i 1985 af Victor S. Miller, der dengang var ansat ved IBM iUSA, og – uafhængigt heraf – af Neal Koblitz fra University of Washington i Seattle, USA.

For elliptiske kurver kan man definere regler for, hvordan man adderer to punkter, og hvordan man fordobler et punkt (se illustrationen).

På den måde kan man på simpel måde 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.

Principperne for addition og fordobling virker for alle punkter, hvis koordinater er beskrevet ved reelle tal. Til kryptografi anvendes dog en variant, hvor den glatte kurve erstattes med en sky af punkter, som er defineret op til en endelig feltstørrelse, på samme måde som der i Diffie-Helman sker en udregning modulus p. De samme regler for addition og fordobling gælder stadig.

NIST P192-kurven er eksempelvis defineret over et endeligt felt givet ved et primtal med 192 cifre. På denne kurve kan man beregne Q = kP med noget, der svarer til 38 additioner og 192 fordoblinger.

Med en ren brute force-metode skal man til gengæld foretage en fordobling og mere end 10^57 additioner for at finde k ud fra Q og P. Det er en umulig opgave i praksis.

Der findes metoder, der er bedre end brute force, men humlen er, at de bedste angrebsmetoder over for elliptisk kurve-kryptografi er mere beregningstunge end angrebsmetoder over for RSA og Diffie-Hellman.

Derfor er elliptiske kurver bedst til at holde på hemmelighederne.

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

Lidt underligt, at Ingeniøren laver en artikel om, at lige præcis elliptiske kurver skulle være sikkerhedsmæssigt "bedre" i en post-Snowden verden og underbygger dette med en artikel skrevet af Bruce Schneier i The Guardian når Schneier netop under punkt 5 i samme artikel skriver:

Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can.

Jeg gætter på, at Schneier henviser til samme forhold Bent Andersen også henviser til i første kommentar. Matematikken bag elliptiske kurver er muligvis god nok, men hvis der er svagheder (specielt for visse valg af konstanter) så er NSA nok bekendt med dem og kan reelt set kun forventes at have udnyttet det til "egen fordel".

  • 2
  • 0

Dual EC DRBG er en algoritme til at konstruere tilfældige tal med. Den benytter sig ganske vist af Elliptiske Kurver, men det er ikke dette som er ankepunktet. Problemet er at visse input til algoritmen er valgt af NIST og der i 2007 blev vist at hvis der var en forhold mellem disse input, så ville sikkerheden og tilfældigheden falde sammen.

Hvad værre er at det er standard-generatoren i RSA labs kode. Det lugter langt væk fordi denne generator er over 3 gange så langsom de alternative generatorer og fordi det må formodes at RSA labs har nok kryptofolk til at have hørt 2007 udmeldingen. Det er dette punkt Wired skriver om.

Elliptiske kurver har det problem at du, som i artiklen skrevet, udvælger en punktsky som du arbejder i. Standardkurverne er udarbejdet af NIST. Med de afsløringer som kommer frem lige nu har folk meget svært ved at stole på disse standardkurver fordi de er bange for at der er et bestemt forhold der gør sig gældende for dem på samme måde som Dual EC DRBG. Gennem de år der er gået siden Kurverne blev defineret så er man blevet klogere og man har flere kriterier for at udvælge kurverne og punktskyerne.

Jeg formoder det er derfor Bruce Schneier har bekymringer omkring brugen af Elliptiske Kurver.

  • 0
  • 0
Bidrag med din viden – log ind og deltag i debatten