Dagens tekst er hentet fra kapittel 10 i Cryptography and Network Security, og handler om andre algoritmer for offentlig-nøkkel-kryptografi, som Diffie-Hellman og elliptiske kurver.

Diffie-Hellman Nøkkelutveksling

Diffie-Hellman er kjent som den første publiserte algoritmen for offentlig-nøkkel-kryptografi. Det finnes flere kommersielle produkter som i dag bruker denne teknikken for å etablere delte symmetriske nøkler mellom to parter. Selv om man sier “nøkkelutveksling”, er det ikke snakk om å utveksle en nøkkel, men de to partene blir vha. algoritmen enige om en felles nøkkel. Algoritmen er begrenset til dette formålet; den kan ikke brukes til å kryptere vilkårlige meldinger, og sikkerheten er basert på vanskeligheten av å beregne diskrete logaritmer.

Verdien av den etablerte nøkkelen avhenger av de to partene og deres offentlige og private nøkkelinformasjon. D-H er basert på eksponensiering i en endelig (Galios) kropp (modulo et primtall eller polynom), noe som er enkelt. Beregning av diskrete logaritmer er typisk like vanskelig som å faktorisere store tall.

Diffie-Hellman oppsett

Alle brukerne blir enige om noen globale parametre: Et stort primtall (eller polynom) q, og et heltall a som er en primitiv rot mod q (a genererer alle heltall 0 .. q-1). Hver bruker (f.eks. A) genererer sitt nøkkelpar ved å velge en hemmelig nøkkel (heltall): x_A < q, og beregne den offentlige nøkkelen: y_A = a^xA mod q. Brukerne gjør så den offentlige nøkkelen y_A kjent for den som vil ha den.

Diffie-Hellman nøkkeletablering

A sender sin offentlige nøkkel y_A til B, som sender sin offentlige nøkkel y_B til A. B beregner så y_A^xB mod q = a^xAxB mod q. A beregner likeledes y_B^xA mod q = a^xBxA mod q = a^xAxB mod q. A(lice) og B(ob) har dermed beregnet samme nøkkel K_AB = a^xAxB mod q, som så kan brukes for symmetrisk kryptering mellom partene. Hvis Alice og Bob skal kommunisere senere en gang, vil de få samme symmetriske nøkkel med mindre de velger nye offentlige nøkler. Vi antar at en angriper vil ha tilgang til begge de offentlige nøklene, men vil ikke kunne beregne den felles nøkkelen hvis hun ikke har en av X-verdiene; for å finne det måtte hun kunne beregne den diskrete logaritmen, som er vanskelig (“umulig”).

Diffie-Hellman eksempel

Alice og Bob som ønsker å kommunisere sikkert blir enige om et primtall q=353 og a=3. De velger så tilfeldige hemmelige nøkler, Alice velger x_A=97, Bob velger x_B=233. De beregner så de respektive offentlige nøklene: y_A=3⁹⁷ mod 353 = 40 (Alice), y_B=3²³³ mod 353 = 248 (Bob), og sender disse til hverandre. De beregner så den delte sesjonsnøkkelen: K_AB= y_B^xA mod 353 = 248⁹⁷ = 160 (Alice) og K_AB= y_A^xB mod 353 = 40²³³ = 160 (Bob).

Nøkkelutvekslingsprotokoller

Brukere kunne opprette tilfeldige private/offentlige D-H-nøkler hver gang de kommuniserer, eller de kunne lage et fast nøkkelpar, og publisere den offentlige nøkkelen i en offentlig katalog som alle kan slå opp i når de ønsker å kommunisere sikkert, men begge disse variantene er sårbare for et “mann-i-midten-angrep”. Det er derfor nødvendig å autentisere nøklene.

Lille-Per i midten (Man-in-the-Middle Attack)

Darth forbereder seg ved å lage to privat/offentlig nøkkelpar. Alice sender sin offentlige nøkkel til Bob, men Darth snapper den opp, og sender i stedet sin første offentlige nøkkel til Bob mens han later som at han er Alice. Darth bruker Alices virkelige offentlige nøkkel og sin andre private nøkkel til å beregne en delt nøkkel med Alice. Bob mottar det han tror er Alice sin offentlige nøkkel, og genererer en symmetrisk nøkkel som han tror er delt med Alice (men faktisk delt med Darth). Bob sender sin offentlige nøkkel til Alice, men Darth snapper den opp og sender i stedet sin andre offentlige nøkkel til Alice. Darth bruker Bobs virkelige offentlige nøkkel til å beregne en delt nøkkel med Bob. Alice mottar det hun tror er Bobs offentlige nøkkel, og beregner en delt nøkkel (med Darth, selv om hun tror det er med Bob). Darth har dermed to delte nøkler med hhv. Alice og Bob, og kan snappe opp, dekryptere, re-kryptere og videresende alle meldinger mellom Alice og Bob.

ElGamal

I 1984 publiserte T. ElGamal en ny krypteringsalgoritme basert på diskrete logaritmer, nært beslektet med Diffie-Hellman-teknikken. Den brukes bl.a. i Digital Signature Standard (DSS) og S/MIME e-post-standarden.

De globale elementene er et primtall q og et heltall a som er en primitiv rot av q. Som den observante leser har fått med seg, skal vi nok en gang gi oss fatt med eksponensiering i en endelig (Galois) kropp. Hver bruker (f.eks. Alice) genererer sine nøkkelpar ved først å velge sin hemmelige nøkkel: 1 < x_A < q-1, og så beregne sin offentlige nøkkel: y_A = a^xA mod q.

ElGamal Meldingsutveksling

For å sende en melding til Alice, må Bob først representere meldingen som et heltall M slik at 0 <= M <= q-1 (Hvis meldingen er for stor for dette, må den deles inn i blokker). Bob velger så et tilfeldig heltall k slik at 1 <= k <= q-1, og beregner en engangsnøkkel K = y_A^k mod q. M krypteres som et par heltall (C₁,C₂) hvor C₁= a^k mod q og C₂ = KM mod q.

Alice kan dekryptere meldingen ved å gjenvinne nøkkelen K, ettersom K = C₁^xAmod q, og beregne M = C₂ K^-1 mod q. En unik k må brukes hver gang, ettersom man i motsatt fall vil kunne angripe algoritmen.

ElGamal Eksempel

Vi bruker kroppen GF(19); q=19 og a=10. Alice lager sitt nøkkelpar ved å velge x_A=5 og beregne y_A=10⁵mod 19 = 3. Bob sender meldingen m=17 som (11,5) ved å velge tilfeldig k=6, beregne K = y_A^k mod q = 3⁶ mod 19 = 7, beregne C₁= a^k mod q = 10⁶ mod 19 = 11, og beregne C₂ = KM mod q = 7∙17 mod 19 = 5.

Alice gjenvinner den opprinnelige meldingen ved å først beregne K = C₁^xA mod q = 11⁵mod 19 = 7, og finner deretter inversen K^-1 = 7^-1 = 11 (mod 19) (fordi 19∙4 =76, 7∙11=77 ≡ 1 mod 19). Kan dermed beregne M = C₂ K^-1 mod q = 5∙11 mod 19 = 17.

Aritmetikk med elliptiske kurver

De fleste produkter og standarder som bruker offentlig-nøkkel-kryptografi for kryptering og digitale signaturer har brukt RSA. Nøkkellengden som er nødvendig for sikker bruk av RSA har imidlertid økt i senere år, og dette har medført høyere prosesseringsbelastning på applikasjoner som bruker RSA. Elliptic curve cryptography (ECC) har begynt å vises i standardiseringsarbeid, inkludert IEEE P1363 Standard for offentlig-nøkkel-kryptografi. Hovedattraksjonen ved ECC er at den later til å tilby samme sikkerhet som RSA, men med mye kortere nøkler.

Abelske Grupper

Vi repeterer her egenskapene til Abelske grupper:

Et sett av elementer med en binær operator ● som assosierer et element (a●b) med hvert ordnede par (a,b) av elementer i G, slik at de følgende aksiomene oppfylles:

(A1) Lukkethet: Hvis a og b hører til G, så er (a●b) også i G
(A2) Assosiativitet: a●(b●c) = (a●b)●c for alle a, b, c i G
(A3)Identitetselement: Det finnes et element e i G slik at a●e = e●a = a for alle a i G
(A4) Invers: For hver a i G, finnes det et element a’ i G slik at a●a’ = a’●a = e
(A5) Kommutativitet: a●b = b●a for alle a, b i G

Reelle elliptiske kurver

En elliptisk kurve er definert av en likning med to variable x & y, med koeffisienter. Ta en kubisk elliptisk kurve av formen y² = x³ + ax + b hvor x,y,a,b alle er reelle tall, og definer et nullpunkt O. Notasjonen E(a,b) brukes for å angi mengden av alle punkter (x,y) som tilfredsstiller likningen.

Vi har en addisjonsoperasjon for elliptiske kurver, geometrisk sier vi at addisjon av punktene P og Q: P+Q er krysningspunktet R (det neste stedet linjen mellom P og Q krysser grafen) speilet om X-aksen.

Geometrisk beskrivelse av addisjon

Vi har den additive identiteten O (nullpunktet): P + O = P. Det negative av punktet P: P + (-P) = P – P = O, ergo punktet med samme x-koordinat, men med den negative verdien av y-koordinaten. Addisjon av to punkter P og Q med forskjellige x-koordinater: Tegn en rett linje mellom dem, og finn det tredje punktet på grafen hvor linjen krysser; vi kaller dette punktet R. Hvis vi nå reflekterer R om X-aksen, får vi -R, og vi definerer P + Q = -R. For å doble et punkt P, tegn tangenten og finn det andre punktet S hvor tangenten krysser grafen: P + P = 2P = -S

Elliptiske kurver over Z_p

ECC bruker kurver hvis variabler og koeffisienter er endelige. Det er to familier av elliptiske kurver som brukes i kryptografiske applikasjoner: Primtallskurver over Z_p, og binære kurver over GF(2^m).

Primtallskurver over Z_p bruker en kubisk likning hvor variablene og koeffisientene alle har verdier i mengden heltall fr 0 til p-1, og hvor alle beregninger utføres modulo p. Denne varianten er best for programvareapplikasjoner.

Elliptiske kurver over GF(2^m)

Binære kurver over GF(2^m) har variable og koeffisienter som alle har verdier i GF(2^m), og alle beregninger utføres over GF(2^m). Denne varianten er best for maskinvareapplikasjoner.

Vi bruker en kubisk likning hvor variable og koeffisienter alle antar verdier i GF(2^m) for et eller annet tall m. Beregninger utføres etter reglene for aritmetikk i GF(2^m). Formen av kubiske likninger som egner seg for kryptografiske applikasjoner for elliptiske kurver er noe annerledes for GF(2^m) enn for Z_p. Det er underforstått at variablene x og y og koeffisientene a og b er elementer i GF(2^m) og at beregninger utføres i GF(2^m).

Elliptic Curve Cryptography (ECC)

Addisjonsoperasjonen i ECC er motstykket til modulær multiplikasjon i RSA. Multippel addisjon er motstykket til modulær eksponensiering. For å lage et kryptografisk system ved hjel av elliptiske kurver, trenger vi et “vanskelig” problem tilsvarende å faktorisere et produkt av to store primtall eller å beregne den diskrete logaritmen.

Hvis vi sier at Q=kP, hvor Q, P er punkter på en primtallskurve, så er det “enkelt” å beregne Q gitt k og P, men “vanskelig” å finne k gitt Q og P. Dette er kjent som elliptisk kurve logaritmeproblemet (eller det diskrete logaritmeproblemet for en elliptisk kurve).

ECC Diffie-Hellman

Vi kan nå foreta nøkkeletablering analogt til D-H. Brukere velger en passende kurve E_q(a,b) og et basispunkt G=(x₁,y₁) som har stor orden n slik at nG=O. A & B velger private nøkler n_A<n, n_B<n, og beregner offentlige nøkler: P_A=n_AG, P_B=n_BG. Etter å ha utvekslet offentlige nøkler kan A og B så beregne den delte nøkkelen: K=n_AP_B, K=n_BP_A; disse er samme nøkkel ettersom K=n_An_BG. Angriperen måtte kunne finne K, som er vanskelig.

ECC kryptering/dekryptering

Det finnes flere tilnærminger til bruk av elliptiske kurver for kryptering. Må først velge en passende kurve, og så kode en melding m som et punkt på den elliptiske kurven P_m, velger så punkt G som i Diffie-Hellman. Hver bruker velger en privat nøkkel n_Aog generer en offntlig nøkkel P_A=n_A * G. For å kryptere og sende meldingen P_m til B, velger A et tilfeldig positivt heltall k og lager chifferteksten C_m som består av følgende to punkter: C_m= {kG, P_m+kP_B}. For å dekryptere chifferteksten må B først multiplisere det første punktet av paret med sin private nøkkel, og trekker resultatet fra det andre punktet: P_m+kP_B–n_B(kG) = P_m+k(n_BG)–n_B(kG) = P_m

Sikkerheten til Elliptic Curve Cryptography

ECC avhenger av vanskeligheten til det diskrete logaritmeproblemet for en elliptisk kurve. Den raskeste metoden kjent så langt er “Pollard-rho-metoden”. Sammenlignet med faktorisering kan vi bruke langt kortere nøkler enn RSA. For ekvivalente nøkkellengder er beregningstiden omtrent det samme, ergo vil ECC tilby signifikante beregningsmessige fordeler over RSA.

Photo by rawpixel.com from Pexels

Kryptografi og nettverkssikkerhet (Kapittel 10: Andre offentlige nøkler)