RSA (kryptering)

RSA
Generell
Designere	Ronald Rivest , Adi Shamir , Leonard Adleman
Første utgivelse	1977
Detaljer
Nøkkelstørrelse	Vanligvis 1024 bits til 4096 bits (minst 2048 bits anbefales)
Bedre kryptoanalyse
Sil av feltene med generelle tall for klassisk datamaskin. Shor-faktoriseringsalgoritme for kvantedatamaskiner .

I kryptografi indikerer akronymet RSA en asymmetrisk krypteringsalgoritme , oppfunnet i 1977 av Ronald Rivest , Adi Shamir og Leonard Adleman , som kan brukes til å kryptere eller signere informasjon.

I 1976 var Whitfield Diffie og Martin Hellman , amerikanske kryptologer, de første som publiserte et system basert på opprettelsen av en "asymmetrisk" chiffer sammensatt av "offentlige nøkler"; selv om James H. Ellis , Clifford Cocks og Malcolm J. Williamson fra de britiske hemmelige tjenestene allerede hadde tenkt på det noen år tidligere, ble nyheten dekket av militær hemmelighold og ble først avslørt i 1997. [1]

Krypteringssystemet er basert på eksistensen av to forskjellige nøkler, som brukes til å kryptere og dekryptere. Hvis den første nøkkelen brukes til kryptering, må den andre nødvendigvis brukes til dekryptering og omvendt. Det grunnleggende spørsmålet er at selv om de to nøklene er avhengige av hverandre, er det ikke mulig å spore tilbake fra den ene til den andre, slik at selv om man er klar over en av de to nøklene, kan den ene ikke spore den andre, noe som garanterer dette sikrer integriteten til krypteringen.

For å oppnå god sikkerhet er det nødvendig å bruke binære nøkler på minst 2048 biter. De 512-biters kan fås på noen få timer. 1024-bits nøkler, fortsatt mye brukt i dag, anbefales ikke lenger. Faktoriseringen av store heltall har faktisk utviklet seg raskt gjennom bruk av sofistikert maskinvare, til det punktet at det kan være mulig å faktorisere et 1024-bits heltall i løpet av et enkelt år, til en kostnad av én million dollar (en bærekraftig kostnad) . per stor organisasjon, byrå eller etterretning). [2] [3]

( NO ) "Jeg håper RSA-applikasjoner ville ha gått bort fra 1024-bits sikkerhet for mange år siden, men for de som ikke har gjort det ennå: våkn opp."	( IT ) "Jeg håper RSA-applikasjoner har forlatt 1024-bits nøkler i årevis, men for de som ikke har gjort det, våkn opp!"
( Bruce Schneier , sbsuneebxu 21. mai 2007 )

Beskrivelse

For å ta et praktisk eksempel, hvis Alice ønsker å sende Bob en melding og ikke vil at noen andre enn Bob skal lese den, vil Alice se etter Bobs offentlige nøkkel på listen og med det kan hun kryptere meldingen. Siden Bob er den eneste som har den private nøkkelen (derfor kan dekryptere meldingen kryptert med den offentlige nøkkelen), vil han også være den eneste som kan dekryptere meldingen, som vil forbli så hemmelig for alle andre, inkludert Alice, som siden hun ikke har Bobs private nøkkel, vil hun ikke kunne dekryptere meldingen hun opprettet selv. Det er klart at suksessen til dette systemet er basert på det absolutte behovet for at Bob skal være den eneste som har sin egen private nøkkel. Ellers, med begge nøklene, kan hvem som helst enkelt dekryptere meldingen.

Med denne krypteringsmetoden er det også mulig å garantere opprinnelsen til en melding. La oss gå tilbake til forrige eksempel: Alice denne gangen, før hun krypterer meldingen ved hjelp av Bobs offentlige nøkkel, vil kryptere den med sin egen private nøkkel og først senere kryptere den på nytt med Bobs offentlige nøkkel. Når Bob mottar meldingen og dekrypterer den med sin omvendte nøkkel, vil han fortsatt få en kryptert melding. Den gitte meldingen vil da trenge at Alices offentlige nøkkel dekrypteres, og dermed sikre at meldingen kun ble sendt av Alice, den eneste som har den private nøkkelen som meldingen ble kryptert med.

Enklere, ved å bruke denne krypteringsmetoden, kan Alice sende meldinger til alle, og garantere opprinnelsen. Faktisk, ved å kryptere meldingen med sin private nøkkel, vil hvem som helst kunne lese meldingen, dekryptere den med sin offentlige nøkkel, og dermed sikre at avsenderen er Alice.

Implementering ved hjelp av RSA-algoritmen

Det var i 1978 at dette systemet fant sin virkelige anvendelse, da de tre MIT -forskerne Ronald Rivest , Adi Shamir og Leonard Adleman var i stand til å implementere denne logikken ved å bruke spesielle formelle egenskaper til primtall med noen få hundre sifre. Algoritmen de fant opp, kalt RSA fra initialene til etternavnene deres, er ikke sikker fra et teoretisk matematisk synspunkt, da det er mulighet for at gjennom kunnskapen om den offentlige nøkkelen kan en melding tydes; men den enorme mengden av beregninger og de enorme utgiftene i form av tid som kreves for å finne løsningen, gjør denne algoritmen til et system med nesten absolutt pålitelighet.

Ronald Rivest , Adi Shamir og Leonard Adleman patenterte i 1983 algoritmen i USA fra MIT (patent 4 405 829, utløp 21. september 2000 ); de opprettet også RSA Data Security- selskapet , og beskyttet dermed deres kommersielle interesser. Security Dynamics kjøpte senere selskapet og solgte bruken av algoritmene til selskaper som Netscape , Microsoft og andre. En variant av RSA-systemet brukes i Pretty Good Privacy (PGP) chiffersuite . RSA-algoritmen danner grunnlaget for de kryptografiske systemene som datasikkerhetssystemene som brukes på Internett for å autentisere brukere er basert på.

Clifford Cocks , en britisk matematiker som jobbet for en spionasjeavdeling, GCHQ , beskrev et tilsvarende system i et internt dokument i 1973 . Dokumentene ble holdt skjult, og gitt de relativt høye kostnadene for maskinene som var nødvendig for å implementere det på den tiden, var det ingen ytterligere undersøkelser eller praktiske tester, og dette ble sett på som en kuriositet så langt det er kjent. Cocks oppdagelse ble først offentliggjort i 1997 .

I 2005 var et forskerteam i stand til å dekomponere et 640 - bit (193 desimal) tall i to 320-biters primtall, ved å bruke en Opteron - klynge med 80 2,2 GHz-prosessorer i fem måneder, og potensielt dekryptere en RSA-kodet melding.

RSA er beregningsmessig krevende, spesielt med tanke på en eventuell maskinvareimplementering. Følgelig er en effektiv bruk å utnytte RSA til å kryptere en enkelt melding som inneholder en hemmelig nøkkel; denne nøkkelen vil deretter bli brukt til å utveksle meldinger gjennom en symmetrisk nøkkelalgoritme, for eksempel AES .

I dag, sammen med DSA , er RSA en av de mest brukte algoritmene for kryptering av digitale signaturer .

Operasjoner

RSA er basert på den høye beregningsmessige kompleksiteten til primfaktorisering . Dens grunnleggende operasjon er som følger:

to primtall velges tilfeldig, og store nok til å sikre sikkerheten til algoritmen (for eksempel bruker det største RSA-tallet, RSA-2048 , to primtall lengre enn 300 sifre) $s$ $q$
vi beregner produktet deres , kalt modulo (siden all den følgende aritmetikken er modulo n ), og produktet deres , hvor er tozient-funksjonen ${\ displaystyle n = pq}$ $\ varphi (n) = (p-1) (q-1)$ $\ varphi (n)$
vi anser at faktoriseringen av n er hemmelig og bare de som velger de to primtallene, p og q , vet det
vi velger så et tall (kalt offentlig eksponent ), vi dekker med og mindre enn $Og$ $\ varphi (n)$ $\ varphi (n)$
tallet (kalt privat eksponent ) beregnes slik at produktet med er kongruent med modulo eller at $d$ $Og$ $1$ $\ varphi (n)$ $og \ equiv 1 {\ pmod {\ varphi (n)}}$

Den offentlige nøkkelen er , mens den private nøkkelen er . [4] $(ingen)$ $(n, d)$

Styrken til algoritmen ligger i det faktum at å beregne fra (eller omvendt) er kunnskapen om ikke nok , men tallet er nødvendig , og at beregningen krever svært lang tid; faktisk, faktorisering i primtall (det vil si å bryte ned et tall i dets primtall) er en beregningsmessig kostbar operasjon. $d$ $Og$ $n$ $\ varphi (n) = (p-1) (q-1)$

En melding blir kryptert gjennom operasjonen ved å transformere den til den krypterte meldingen . Når den er overført, dekrypteres den med . Prosedyren fungerer bare hvis nøkkelen som brukes til å kryptere og nøkkelen som brukes til å dekryptere er koblet sammen av forholdet , så når en melding er kryptert med en av de to nøklene kan den bare dekrypteres med den andre. Algoritmen er basert på den aldri beviste antagelsen (kjent som RSA assumption , eller RSA assumption på engelsk) at problemet med å beregne , med et sammensatt tall hvis faktorer er ukjente, er beregningsmessig usporbart. $m$ $m ^ {e} {\ pmod {n}}$ $c$ $c$ ${\ displaystyle c ^ {d} {\ pmod {n}} = m}$ ${\ displaystyle m <n}$ $Og$ $d$ $og \ equiv 1 {\ pmod {\ varphi (n)}}$ ${\ sqrt [{e}] {c}} \ mod n$ $n$

Den digitale signaturen er ikke annet enn det motsatte: meldingen er kryptert med den private nøkkelen, slik at hvem som helst kan, ved å bruke den offentlige nøkkelen som er kjent for alle, dekryptere den og, i tillegg til å kunne lese den i klartekst, være sikker på at meldingen ble sendt av eieren av den private nøkkelen som tilsvarer den offentlige nøkkelen som ble brukt til å lese den.

Av hensyn til effektivitet og bekvemmelighet sendes meldingen normalt i klartekst med den digitale signaturen til en hash av meldingen vedlagt; på denne måten kan mottakeren direkte lese meldingen (som er i klartekst), bruke den offentlige nøkkelen til å trekke ut hashen fra signaturen og verifisere at denne er den samme som den som er beregnet lokalt på den mottatte meldingen. Hvis hashen som brukes er kryptografisk sikker , bekrefter korrespondansen mellom de to verdiene at meldingen som er mottatt er identisk med den som opprinnelig ble signert og overført.

Matematisk grunnlag

Dekrypteringen av meldingen er sikret takket være noen matematiske teoremer; faktisk fra beregningen vi får:

$c ^ {d} {\ pmod {n}} = (m ^ {e}) ^ {d} {\ pmod {n}} = m ^ {{ed}} {\ pmod {n}}$

Men vi vet det , derfor har vi det og det . $og \ equiv 1 {\ pmod {(p-1) (q-1)}}$ $og \ equiv 1 {\ pmod {p-1}}$ $og \ equiv 1 {\ pmod {q-1}}$

Så ved Fermats lille teorem :

$m ^ {{ed}} \ equiv m {\ pmod {p}}$ Og $m ^ {{ed}} \ equiv m {\ pmod {q}}$

Siden og er forskjellige og primtall, kan vi bruke den kinesiske restsetningen , og få det $s$ $q$

$m ^ {{ed}} \ equiv m {\ pmod {pq}}$

og derfor det

$c ^ {{d}} \ equiv m {\ pmod {n}}$

Eksempel

Her er et eksempel på RSA-kryptering og dekryptering. Tallene som er valgt er bevisst små primtall, men i virkeligheten brukes tall i størrelsesorden . $10 ^ {{100}}$

Nøkkelgenerering

$p = 3$ Og $q = 11$
$n = p * q = 3 * 11 = 33$ Og ${\ displaystyle \ varphi (n) = (p-1) (q-1) = 2 * 10 = 20}$
Jeg tar , siden og er coprimo med (det trenger ikke å være prime) $e = 7$ $og <20$ $Og$ $20$ $Og$
$d = 3$ ; faktisk siden med resten [5] $ed = 7 * 3 = 21 \ equiv 1 {\ pmod {20}}$ $21/20 = 1$ $1$

Så vi har den private nøkkelen og den offentlige nøkkelen (det faktum at det er lik er rent tilfeldig). $(33.3)$ $(33,7)$ $d$ $s$

Kryptering og dekryptering

La oss nå vurdere meldingen og kryptere den for å få den krypterte meldingen ; åpenbart kan vi bruke 33 og 7, men ikke 3 som er en del av den private nøkkelen. $m = 15$ $c$

$c = m ^ {e} {\ pmod {n}} = 15 ^ {{7}} {\ pmod {33}} = 27$

Og la oss nå tyde for å få ; her vil vi bruke 3, viktig komponent av den private nøkkelen. $c = 27$ $m$

$m = c ^ {d} {\ pmod {n}} = 27 ^ {{3}} {\ pmod {33}} = 15$

Så vi dechiffrerte endelig meldingen.

Blind signatur

Det finnes også et digitalt signaturformat basert på RSA, der innholdet i en melding skjules før den signeres, kalt blindsignatur .

Merknader

^ GCHQ-trioen anerkjent for nøkkelen til sikker netthandel , på bbc.com , BBC, 5. oktober 2010.
^ A. Shamir, E. Tromer, On the Cost of Factoring RSA-1024 , 2003.
^ Franke et al., SHARK: En realiserbar maskinvaresiktingsenhet for factoring 1024-bit , 2005.
^ Selv om fra et matematisk synspunkt bare kunnskap om er tilstrekkelig, er det av effektivitetshensyn mulig å eksplisitt bevare de to faktorene og , kunnskapen om hvilke gjør det mulig å bruke en raskere beregningsmetode for kryptering / dekryptering. ${\ displaystyle (n, d)}$ $s$ $q$
^ d kan beregnes ved å bruke Pericles Extended Algorithm .

Relaterte elementer

Eksterne lenker

Nettstedet til handelsselskapet RSA , på rsasecurity.com .