Dagens tekst er hentet fra kapittel 9 i Cryptography and Network Security, og handler om offentlig-nøkkel-kryptografi generelt og RSA-algoritmen spesielt.

Tradisjonell kryptografi med en privat/hemmelig/enkel nøkkel bruker en enkelt nøkkel som er delt mellom sender og mottaker. Hvis denne røpes til en tredjepart, vil kommunikasjonen være kompromittert. Tradisjonell kryptografi er også symmetrisk; partene er likeverdige, og ingenting hindrer en mottaker fra å forfalske en melding og hevde at den er sendt av den andre parten.

Offentlige nøkler

Offentlig-nøkkel-kryptering er sannsynligvis det viktigste framskrittet i kryptografiens 3000 år gamle historie. Vi bruker to nøkler – en offentlig, og en privat, og metoden er altså asymmetrisk, partene er ikke likeverdige. Forutsetningen for at det skal fungere er en ganske snedig bruk av tallteori. Det er imidlertid viktig å påpeke at offentlig-nøkkel-kryptering komplementerer snarere enn å erstatte konvensjonell symmetrisk kryptering.

Terminologi

Asymmetriske nøkler

To nøkler som hører sammen, en offentlig nøkkel og en privat nøkkel som brukes til å utføre komplementære operasjoner, som kryptering og dekryptering, eller signaturgenerering og signaturverifisering.

Offentlig-nøkkel-sertifikat

Et digitalt dokument utstedt av og signert med den private nøkkelen til en Sertifikatmyndighet som knytter navnet til en Abonnent til en offentlig nøkkel. Sertifikatet indikerer at Abonnenten identifisert i sertifikatet har full kontroll på og aksess til den korresponderende private nøkkelen.

Offentlig-nøkkel (Asymmetrisk) Kryptografisk algoritme

En kryptografisk algoritme som bruker to nøkler som hører sammen, en offentlig nøkkel og en privat nøkkel. De to nøklene har egenskapen at det er beregningsmessig ugjennomførbart å utlede den private nøkkelen fra den offentlige.

**Offentlig-nøkkel-infrastruktur (Public Key Infrastructure – PKI)**

Et sett av retningslinjer, prosesser, tjenerplattformer, programvare og arbeidsstasjoner som brukes med formålet å administrere sertifikater og offentlig-privat nøkkelpar, inkludert muligheten til å utstede, vedlikeholde og tilbakekalle offentlig-nøkkel-sertifikater.

Prinsipper for offentlig-nøkkel-kryptosystemer

Konseptet offentlig-nøkkel-kryptering oppstod fra et forsøk på å angripe to av de vanskeligste problemene ved symmetrisk kryptering: Nøkkeldistribusjon og digitale signaturer. Utfordringen med nøkkeldistribusjon dreier seg om hvordan man kan oppnå sikker kommunikasjon uten å måtte stole på et nøkkeldistribusjonssenter som har din krypteringsnøkkel. Målet med digitale signaturer er å kunne verifisere at en melding kommer uforandret fra den avsenderen som den påstår.

Whitfield Diffie og Martin Hellman fra Stanford University fikk et gjennombrudd i 1976 ved å finne på en metode som addresserte begge problemene; denne metoden varradikalt forskjellig fra alle tidligeretilnærminger til kryptering.

Det ble senere kjent at britiske James H. Ellis publiserte en gradert rapport i 1970 som skisserte tilsvarende ideer som Diffie og Hellman kom med seks år senere. Denne rapporten ble imidlertid ikke avgradert før i 1997.

Vrangforestillinger rundt offentlig-nøkkel-kryptering

Ikke alt det som mange mennesker tror om asymmetrisk kryptering er riktig:

Offentlig-nøkkel-kryptering er sikrere mot kryptoanalyse enn symmetrisk kryptering (det er den ikke)
Offentlig-nøkkel kryptering er en generell teknikk som har gjort symetrisk kryptering overflødig (vi trenger fortsatt symmetrisk kryptering)
Nøkkeldistribusjon er blitt trivielt med offentlig-nøkkel (vi må fortsatt ha tunga rett i munnen)

Offentlig-nøkkel-kryptosystemer

Den offentlige nøkkelen kan være kjent for hvem som helst, og brukes til å kryptere meldinger TIL eieren, eller verifisere signaturer FRA eieren. Den tilhørende private nøkkelen må kunne være kjent for eieren, og kan brukes til å dekryptere meldinger sendt TIL eieren, eller signere meldinger som sendes FRA eieren. Vi kaller denne mekanismen asymmetrisk fordi nøklene som brukes til å kryptere meldinger ikke kan dekryptere meldinger, og de som brukes til å verifisere signaturer kan ikke brukes til å opprette signaturer.

Et offentlig-nøkkel-kryptosystem har seks ingredienser:

Klarteksten – den lesbare meldingen (eller andre data) som mates inn i algortimen
Krypteringsalgoritmen – foretar forskjellige transformasjoner på klarteksten
Offentlig nøkkel (K_PU) – brukes for kryptering (eller verifisering av signatur)
Privat nøkkel (K_PR) – brukes for dekryptering (eller signering)
Chiffertekst – den krypterte meldingen som genereres av krypteringsalgoritmen
Dekrypteringsalgoritmen – tar i mot chifferteksten og den tilhørende meldingen og genererer den opprinnelige klarteksten

Karakteristikker ved offentlige nøkler

Offentlig-nøkkel-algoritmer baserer seg på to nøkler, hvor det ikke lar seg gjøre å finne dekrypteringsnøkkelen hvis man bare vet algoritmen og krypteringsnøkkelen, men det er enkelt å kryptere/dekryptere meldinger når den relevante nøkkelen er kjent. For mange algoritmer er det sånn at man når man genererer et nøkkelpar, er det likegyldig hvem av dem man velger til privat eller offentlig nøkkel.

Krav

En algoritme må tilfredsstille følgende krav:

Det er beregningsmessig enkelt for Bob å generere et nøkkelpar (offentlig nøkkel PU_b, privat nøkkel PR_b)
Det er beregningsmessig enkelt for en avsender Alice, som kjenner Bobs offentlige nøkkel og meldingen som skal krypteres, å generere den korresponderende chifferteksten.
Det er beregningsmessig enkelt for mottakeren Bob å dekryptere chifferteksten med sin private nøkkel for å gjenvinne den opprinnelige meldingen
Det er beregningsmessig ugjennomførbart (“umulig”) for en motpart som kjenner den offentlige nøkkelen å utlede den private nøkkelen
Det er beregningsmessig ugjennomførbart for en motpart som kjenner den offentlige nøkkelen ogchifferteksten å gjenvinne den opprinnelige meldingen
I mange systemer kan de to nøklene anvendes i vilkårlig rekkefølge

Vi trenger en “fall-lem” enveisfunksjon. En enveisfunksjon er en funksjon som avbilder et domene inn i et intervall slik at enhver funksjonsverdi har en unik invers, med betingelsen at kalkuleringen av funksjonen er enkel, men kalkuleringen av den inverse er ugjennomførbar.

Y = f(X) lett
X = f^–1(Y) ugjennomførbart

En fall-lem enveisfunksjon er en familie av invertible funksjoner f_k, slik at

Y = f_k(X) lett, hvis k og X er kjent
X = f_k^–1(Y) lett, hvis k og Y er kjent
X = f_k^–1(Y) ugjennomførbart, hvis Y kjent men k ikke kjent

NB: Det er ikke samme k i funksjonen og den inverse funksjonen!

Et praktisk offentlig-nøkkel-system avhenger av en passende fall-lem enveisfunksjon.

Kryptoanalyse med offentlige nøkler

Et offentlig-nøkkel-krypteringssystem er sårbart for et angrep med uttømmende søk. Det åpenbare mottiltaket er å bruke større (lengre) nøkler, men nøkkelstørrelsen må være liten nok for praktisk kryptering og dekryptering. De nøkkelstørrelsene som typisk oppfattes som sikre nok fører til krypterings-/dekrypteringshastighet som er for langsom for generelt bruk, dette betyr at asymmetrisk kryptering generelt begrenses til nøkkelhåndtering og digitale signaturer. En annen type angrep ville være å finne en måte å beregne den private nøkkelen basert på den offentlige nøkkelen. P.t. har det ikke blitt bevist matematisk at et slik angrep vil være ugjennomførbart for en gitt offentlig-nøkkel-algoritme. Til slutt har en det såkalte “sannsynlig melding”-angrepet, som kan motvirkes ved å legge til noen tilfeldige bits til enkle meldinger.

Anvendelser for offentlig-nøkkel-kryptosystemer

Offentlig-nøkkel-kryptosystemer kan klassifiseres i tre kategorier:

Kryptering/dekryptering: Avsenderen kryptere en melding med mottakerens offentlige nøkkel
Digital signatur: Avsenderen “signerer” en melding med sin private nøkkel
Nøkkelutveksling: To parter samarbeider for å utveksle en sesjonsnøkkel

Enkelte algoritmer kan brukes for alle tre anvendelsesområder,men andre kan kun brukes for en eller to.

RSA

RSA-algoritmen ble utviklet ved MIT i 1977 av Ron Rivest, Adi Shamir & Len Adleman. Det virker som om en tilsvarende algoritme ble utviklet av Clifford Cocks ved CESG allerede i 1973, men dette arbeidet var gradert og ikke allment kjent før utpå 90-tallet.

RSA er kanskje den mest brukte generelle tilnærmingen til offentlig-nøkkel-kryptering. I RSA er klarteksten og chifferteksten et heltall mellom n – 1 for en eller annen n. En typisk størrelse for n var 1024 bits, eller 309 desimale siffer. RSA bruker et utrykk med eksponenter. Klartekst krypteres i blokker, hvor hver blokk har en (binær) verdi mindre enn et tall n. Kryptering og dekryptering er på følgende form, for en klartekst blokk M og en chiffertekst blokk C:

C = M^e mod n

M = C^d mod n = (M^e)^d mod n = M^ed mod n

Både sender og mottaker må kjenne til verdien n. Avsenderen kjenner til verdien til e, og bare mottakeren kjenner til verdien av d. Dette er en offentlig-nøkkel-krypteringsalgoritme med en offentlig nøkkel PU={e,n} og en privat nøkkel PR={d,n}.

Krav til algoritmen

For at denne algoritmen skal være tilfredsstillende for offentlig-nøkkel-kryptering, må følgende krav være oppfylt:

Det er mulig å finne verdier for e, d, n slik at M^ed mod n = M for alle M < n
Det er relativ enkelt å beregne M^e mod n and C^d mod n for alle verdier av M < n
Det er ugjennomførbart å utlede d gitt e og n

RSA kryptering/dekryptering

For å kryptere en melding M må avsenderen få tak i den offentlige nøkkelen til mottakeren PU={e,n}, og beregne C = M^e mod n, hvor 0≤M<n. For å dekryptere chifferteksten C må eieren bruke sin private nøkkel PR={d,n} og beregne M = C^d mod n. Meldingen M må være mindre enn modulusen n, hvis den er større må den deles opp i blokker.

RSA nøkkelkonfigurering

Hver bruker genererer et offentlig/privat nøkkelpar ved å velge to tilfeldige store primtall p, q. Modulusen blir da n=p∙q. Legg merke til at φ(n)= (p-1)(q-1). Vi velger så en tilfeldig krypteringsnøkkel e, hvor 1<e<φ(n), gcd(e, φ(n))=1. Løser deretter følgende likning for å finne dekrypteringsnøkkelen d: e∙d=1 mod φ(n) og 0≤d≤n. Til slutt offentliggjør brukeren sin offentlige krypteringsnøkkel PU={e,n}, og holder den private dekrypteringsnøkkelen hemmelig: PR={d,n}.

Hvorfor RSA fungerer

RSA fungerer på grunn av Eulers Teorem: a^φ(n)mod n = 1 hvor gcd(a,n)=1. I RSA har vi:
n=p∙q, φ(n)= (p-1)(q-1).
Velger med omhu e & d til å være inverser mod φ(n). Dermed har vi at e∙d=1+k∙φ(n) for en eller annen k. Dermed får vi
C^d = M^e∙d= M^1+k∙^φ(n) = M¹∙ (M^φ(n))^k = M¹∙(1)^k = M¹ = M mod n

RSA eksempel

Vi velger primtall p=17 & q=11, så beregner vi n = pq =17 x 11=187. Vi beregner
φ(n)=(p–1)(q-1)=16×10=160, og velger så en e som ikke har felles faktorer med 160; velger e=7. Bestemmer d: de=1 mod 160 og d < 160. Verdien er d=23 siden 23×7=161= 10×160+1. Den offentlige nøkkelen PU={7,187}, den private nøkkelen PR={23,187}.

Eksempelkryptering: Gitt melding M = 88 (NB: 88<187). Kryptering C = 88⁷ mod 187 = 11. Dekryptering M = 11²³ mod 187 = 88.

Eksponenter i modulær aritmetikk

Både kryptering og dekryptering i RSA involverer å opphøye et helltall i en heltallspotens, mod n. Med RSA driver du med potensielt veldig store eksponenter, så effektivitet i eksponentieringen må tas hensyn til. Her kan vi gjøre bruk av en egenskap til modulær aritmetikk:
[(a mod n) x (b mod n)] mod n =(a x b) mod n. Vi kan bruke “kvadrer og multipliser”-algoritmen, som er en rask, effektiv algoritme for eksponensiering. Konseptet er basert på å kvadrere basen gjentatte ganger, og multiplisere inn det som mangler for å beregne resultatet. Grunnen til at dette blir enklere, er at man hele tiden gjør kvadrering modulo n, slik at hvert delresultat alltid er mindre enn n.

Se på binær representasjon av eksponenten, trenger bare O(log₂ n) multipler for tallet n

eks. 7⁵ = 7⁴∙7¹ = 3∙7 = 10 mod 11
eks. 3¹²⁹ = 3¹²⁸∙3¹ = 5∙3 = 4 mod 11

Algoritme for å beregne eksponenter

Vi skal beregne a^m for de positive heltallene a og m. Vi utrykker m som et binært tall b_kb_k-1…b₀

Effektiv operasjon med den offentlige nøkkelen

For å gjøre operasjonen av RSA-algoritmen med den offentlige nøkkelen raskere, gjøres vanligvis et spesifikt valg av e. Det mest vanlige valget er 65537 (2¹⁶ + 1), som bare har to 1-bit – antallet multiplikasjoner for å gjøre eksponensieringen er dermed minimalisert. Andre populære valg var tidligere e=3 og e=17, men med en veldig liten offentlig nøkkel har det vist seg at RSA er sårbar for et enkelt angrep (vi går ikke inn på detaljene her, men interesserte finner mer informasjon med Google).

Effektiv operasjon med den private nøkkelen

Dekryptering bruker eksponensiering med potensen d. En liten verdi for d er sårbar for et uttømmende søk og andre former for kryptoanalyse. Vi må derfor bruke større verdier for d, men kan bruke det kinesiske rest-teoremet for å gjøre beregningen raskere. Størrelsene d mod (p – 1) og d mod (q – 1) kan regnes ut på forhånd. Sluttresultatet er at beregningen er omtrent fire ganger raskere enn å beregne M = C^d mod n direkte.

Mer nøkkelgenerering

Før vi kan ta i bruk offentlig-nøkkel-kryptosystemet må hver deltaker generere et nøkkelpar. Først må de to primtallene p og q velges, og deretter må man velge enten e eller d og beregne den andre. Ettersom verdien av n = pq vil være kjent for en potensiell angriper må primtallene velges fra en tilstrekkelig stor mengde, og metoden for å finne store primtall må være høvelig effektiv.

Prosedyre for å velge et primtall

Man velger et tilfeldig odde heltall, og et annet tilfeldig heltall a < n. Vi utfører deretter den probabilistiske primtallstesten med a som parameter. Hvis n stryker på testen, forkaster vi verdien for n og starter helt fra begynnelsen igjen. Hvis n har bestått et tilstrekkelig antall tester, aksepter n; ellers, velg en ny a og fortsett primtallstestingen.

Sikkerhet til RSA

Det er fem mulige angrepsmåter mot RSA:

Uttømmende søk – prøve alle mulige private nøkler
Matematiske angrep – det finnes flere teoretiske forslag, men alle innebærer tilsvarende innsats som for å faktorisere produktet av to store primtall
Tidtakingsangrep – avhenger av å ta tiden på dekrypteringsalgoritmen
Maskinvarefeil-baserte angrep – innebærer å provosere fram maskinvare-feil i prosessoren som genererer digitale signaturer
Valgt-chiffertekst-angrep – denne typen angrep utnytteriboende egenskaper til RSA-algoritmen.

Faktoriseringsproblemet

Vi kan identifisere tre tilnærminger til matematiske angrep på RSA:

Faktorisering av n I sine to primtallsfaktorer. Dette ville gjøre det mulig å beregne
j(n)=(p–1)(q-1), som så gjøre det mulig å bestemme d = e^-1 (mod j(n)).
Bestemme j(n) direkte uten å først bestemme p and Dette vil igjen gjøre det mulig å bestemme d = e^-1 (mod j(n)).
Bestemme d direkte uten å først bestemme j(n).

Tidtakingsangrep

Kryptokonsulenten Paul Kocher demonstrerte at en avlytter kan bestemme en privat nøkkel ved å måle hvor lang tid en datamaskin tar på å dekryptere en melding. Denne metoden er også anvendbar på andre offentlig-nøkkel-krypteringssystemer, ikke bare RSA. Dette er bekymringsfullt av to årsaker; det kommer fra en fullstendig uventet kant, og er et kun-chiffertekst-angrep.

Mottiltak

Vi kan nevne tre mottiltak mot tidtakingsangrep:

Konstant eksponentieringstid – vi kan sørge for at alle eksponensieringer tar samme tid før vi returnerer et resultat; dette er en enkel fiks, men gir dårligere ytelse
Tilfeldig forsinkelse – vi kan få noe bedre ytelse ved å legge til en tilfeldig forsinkelse for å forvirre fienden med stoppeklokka
Blinding – multipliser chifferteksten med et tilfeldig tall før eksponensieringen utføres; denne prosessen forhindrer angriperen fra å vite hvilke chiffertekst-bit som prosesseres inne i datamaskinen, og forhindrer følgelig bit-for-bit analysen som er essesiell for tidtakingsangrepet.

Blinding i RSA

På mottakersiden i RSA implementeres M = C^d mod n som:

Generer en hemmelig tilfeldig r, 0 ≤ r ≤ n – 1
C’ = C ( r^e) mod n
M’ = ( C’ )^d mod n
M = M’ r^-1 mod n
= (C ( r^e) )^d r^-1 mod n
= C^dr^edr^-1mod n
= M r r^-1mod n
= M 1 = M

Maskinvarefeil-basert angrep

Dette er et angrep på en prosessor som genererer RSA digitale signaturer. Feil i signaturberegningen kan provoseres fram ved å redusere spenningen til prosessoren, feilene forårsaker at programvaren genererer ugyldige signaturer som så kan analyseres for å gjenvinne den private nøkkelen. Angrepsalgoritmen involverer å fremprovosere enkelt-bit-feil og så observere resultatene. Selv om dette angrepet er verdt å diskutere, later det ikke til å være noen alvorlig trussel mot RSA; det krever at angriperen har fysisk tilgang til målmaskinen, og at hun er i stand til å direkte kontrollere strømtilførselen til prosessoren.

Valgt-chiffertekst-angrep (Chosen Ciphertext Attack – CCA)

Vi antar at angriperen kan velge et antall chiffertekster og få de korresponderende klartekstene, dekryptert med målets private nøkkel. Dette er ikke så urealistisk som man skulle tro, ettersom dekryptering med den private nøkkelen i RSA er det samme som signering med den private nøkkelen. Siden RSA er asymmetrisk, kan angriperen velge en klartekst, kryptere den med offerets offentlige nøkkel, og så få klarteksten tilbake, men dette er jo ganske meningsløst, ettersom dette ikke gir angriperen noen ny informasjon. Imidlertid kan angriperen utnytte følgende egenskap til RSA for å finne informasjon om en annen chiffertekst som hun i utgangspunktet ikke har klarteksten til:

E(PU,M₁) x E(PU,M₂) = E(PU,[M₁xM₂])

Vi kan dekryptere C = M^e mod n vha. CCA som følger:

Beregn X = (C x 2^e) mod n
Send X som den valgte chifferteksten, og få tilbake Y = X^d mod n
Legg nå merke til at X = (C mod n) x (2^e mod n)
                                        = (M^e mod n) x (2^e mod n)
                                        = (M^e x 2^e) mod n
                                        = (2M)^e mod n
Derfor er Y = 2M mod n

For å motvirke slike angrep anbefaler RSA Security Inc. å modifisere klarteksten vha. en prosedyre kalt optimal asymmetric encryption padding (OAEP) – men denne går vi ikke videre inn på her. Dette er også en god grunn til at man aldri skal bruke samme nøkkelpar både til kryptering og signering!

Kvantedatamaskinens påvirkning på klassisk kryptografi

For symmetriske algoritmer kan vi for alle praktiske formål si at hvis algoritmen ellers er teknisk tilfredsstillende, må man doble nøkkellengden hvis man skal ta hensyn til fremtidig eksistens av en kvantedatamaskin. Dette betyr at man må gå fra AES-128 til AES-256.

For populære asymmetriske algoritmer må vi dessverre konstatere at en kvantedatamaskin ødelegger moroa – man må gå over til helt andre asymmetriske algoritmer (men detaljer går vi ikke inn på her). Se “Quantum safe cryptography and security, ETSI White paper no.8” for mer detaljer.

Photo by PhotoMIX Ltd. from Pexels

Kryptografi og nettverkssikkerhet (Kapittel 9: Offentlige nøkler og RSA)