RSA-kryptering. Beskrivelse og implementering av RSA algoritmen

RSA kryptering er et av de første praktiske offentlig-nøkkel kryptosystemer som er mye brukt for sikker dataoverføring. Dens viktigste forskjellen fra lignende tjenester er at krypteringsnøkkelen er åpen og forskjellig fra dekrypteringsnøkkelen, som er holdt hemmelig. RSA teknologi , denne asymmetrien er basert på praktiske vanskeligheter av facto avspilling av to store primtall (problemet med factoring).

Historien om skapelsen

RSA Navnet består av de første bokstavene i etternavn Rivest, Shamir og Adleman - forskerne som først offentlig beskrevet disse krypteringsalgoritmer i 1977. Klifford Koks, en engelsk matematiker, som jobbet for britiske etterretningstjenesten, den første til å utvikle et tilsvarende system i 1973 men det ble ikke nedgraderes til 1997

RSA bruker oppretter og publiserer deretter den offentlige nøkkelen basert på to store primtall sammen med hjelpe verdi. Primtall bør holdes hemmelig. Hvem som helst kan bruke den offentlige nøkkelen til å kryptere en melding, men hvis det er stort nok, da bare noen med kunnskap om primtall kan dekode meldingen. RSA kryptering avsløring er kjent som hovedproblemet i dag er en åpen diskusjon om hvordan en pålitelig mekanisme.

RSA algoritmen er relativt treg, og av den grunn er det ikke så mye brukt til å direkte kryptere brukeren. I de fleste tilfeller er denne fremgangsmåte som brukes for overføring i den felles nøkkel kryptert for en symmetrisk krypteringsnøkkel, som i sin tur kan utføre operasjoner bulk kryptering og dekryptering ved en mye høyere hastighet.

Når det var en kryptosystem i sin nåværende form?

Ideen om asymmetrisk kryptografisk nøkkel tilskrives Diffie og Hellman, som publiserte konseptet i 1976, innføre digitale signaturer, og prøver å bruke teorien om tall. Deres formulering bruker en delt hemmelig nøkkel som genereres fra et visst antall eksponensieringen modulo et primtall. Men de forlot åpne spørsmålet om realisering av denne funksjonen, siden prinsippene for factoring ikke ble godt forstått på den tiden.

Rivest, Adi Shamir, og Adleman ved MIT har gjort flere forsøk gjennom årene for å skape en enveis funksjon som er vanskelig å dekode. Rivest og Shamir (som dataforskere) har foreslått mange potensielle funksjoner, mens Adleman (som matematikk) for å søke etter "svake punkter" i algoritmen. De brukte mye av tilnærminger og etter hvert utvikle en endelig system, nå kjent som RSA i april 1977.

Elektronisk signatur og den offentlige nøkkelen

Digital signatur eller elektronisk signatur, er en integrert del av de elektroniske dokumenttyper. Det er dannet ved en viss kryptografiske data endres. Med dette attributtet mulig å sjekke integriteten av dokumentet, til sin taushetsplikt, samt bestemme hvem som eier den. Faktisk et alternativ til vanlig standard signatur.

Dette kryptosystem (RSA-kryptert) tilbyr den offentlige nøkkelen, i motsetning til symmetrisk. Sitt prinsipp om operasjonen er at de to forskjellige tastene brukes - stengt (kryptert) og utendørs. Den første brukes til å generere den digitale signaturen og da kunne dekryptere teksten. Andre - for selve kryptering og elektronisk signatur.

Ved hjelp av underskrifter for å bedre forstå RSA kryptering, et eksempel på noe som kan bli redusert som en vanlig hemmelig "stengt fra nysgjerrige øyne," dokumentet.

Hva er algoritmen?

RSA-algoritmen består av fire trinn: nøkkelgenerering, distribusjon, kryptering og dekryptering. Som allerede nevnt, inneholder RSA-krypterings en offentlig nøkkel og en privat nøkkel. Utendørs kan være kjent for alle, og brukes til å kryptere meldinger. Sin essens ligger i det faktum at meldingene kryptert med den offentlige nøkkelen kan kun dekrypteres i en gitt tidsperiode ved hjelp av en hemmelig nøkkel.

Av sikkerhetsmessige årsaker heltallene å bli valgt tilfeldig og være identiske i størrelse, men varierer i lengde fra noen tall å gjøre facto vanskeligere. Samme samme antallet kan være effektivt funnet av en test i sin enkelhet, slik at kryptering av informasjon må nødvendigvis være komplisert.

Den offentlige nøkkelen består av modul og offentlig eksponent. Innendørsenheten og består av en privat figur, som bør holdes hemmelig.

RSA kryptering av filer og svakheter

Det finnes imidlertid en rekke enkle hacking RSA mekanismer. Når kryptering med lave og små verdier av kodenummer kan enkelt åpnes, hvis pick roten krypterte teksten over heltall.

Siden RSA-kryptering er en deterministisk algoritme (dvs. har ingen tilfeldig komponent), kan en angriper kunne lansere den markerte teksten åpne angrep mot kryptosystem ved å kryptere sannsynlig tekster under den offentlige nøkkelen og sjekker om de er like krypterte teksten. Semantisk sikker kryptosystem kalles i tilfelle at en angriper kan ikke skille mellom de to krypterings fra hverandre, selv om han vet de aktuelle tekstene i utvidet form. Som beskrevet ovenfor, RSA andre tjenester uten padding er ikke semantisk sikker.

Andre algoritmer for kryptering og beskyttelse

For å unngå de ovennevnte problemer i den praktiske gjennomføring av RSA blir vanligvis ført inn i en form for strukturert, randomisert fylling før kryptering. Dette sikrer at innholdet ikke faller innenfor området fra usikre rene tekster, og at denne meldingen ikke kan løses ved tilfeldig valg.

Sikkerhet RSA kryptosystem og kryptering basert på to matematiske problemer: problemet med facto store tall og selve RSA problem. Full avsløring av krypterte teksten og underskrift i RSA anses avvises på antagelsen om at begge disse problemene ikke kan løses kollektivt.

Men med muligheten til å gjenopprette primfaktorene, kan en angriper beregne hemmelig eksponent for den offentlige nøkkelen og deretter dekryptere tekst ved hjelp av standard prosedyre. Til tross for at det i dag ikke eksisterende metode for facto store heltall på en klassisk datamaskin ikke kan bli funnet, har det ikke blitt bevist at han ikke eksisterer.

automatisering

Verktøyet kalles Yafu, kan anvendes for å optimalisere prosessen. Automasjon i YAFU er en avansert funksjon som kombinerer faktorisering algoritmer i intellektuelle og adaptive metodikk som minimerer tid til å finne de faktorer av vilkårlige innspill tall. De fleste implementeringer flertråds-algoritme slik at Yafu full bruk av multi- eller flere flerkjerneprosessorer (inkludert SNFS, SIQS og ECM). Først av alt, det er kontrollert av kommandolinjeverktøyet. Tiden brukt på å lete etter kryptering Yafu faktor ved bruk av en vanlig datamaskin, kan det bli redusert til sekunder 103.1746. Verktøyet behandler binær kapasitet på 320 biter eller mer. Dette er en svært kompleks programvare som krever en viss mengde tekniske ferdigheter til å installere og konfigurere. Således kan RSA-krypterings være sårbar C.

Hacking i nyere tid

I 2009 ble Bendzhamin Mudi bruke RSA-512 biters nøkkel jobber med å tyde kriptoteksta for 73 dager, kun ved hjelp av velkjente programvare (GGNFS) og gjennomsnittlig desktop (dual-core Athlon64 på 1900 MHz). Som vist ved erfaring, kreves litt mindre enn 5 GB disk og omtrent 2,5 gigabyte minne for prosessen med "sikting."

Som i 2010, var det største antall faktorisert RSA 768 biter lang (232 desimalsifre, eller RSA-768). Hans avsløring varte i to år på flere hundre maskiner samtidig.

I praksis RSA-nøkler er lange - vanligvis fra 1024 til 4096 biter. Noen eksperter mener at 1024-biters nøkler kan bli ustabile i nær fremtid eller enda lenger kan være sprakk svært godt finansiert angripere. Men få vil hevde at 4096-biters nøkler kan også bli offentliggjort i nær fremtid.

prospekter

Derfor, som regel er det antatt at RSA er sikker hvis tallene er store nok. Hvis bunnen antallet 300 bits eller kortere, og den krypterte teksten digital signatur kan dekomponeres i løpet av noen timer på en PC ved hjelp av programvare som er tilgjengelig allerede i den offentlige sfæren. En nøkkel lengde 512 biter, som vist, kan bli åpnet så tidlig som i 1999, med bruk av et par hundre datamaskiner. I dag er det mulig i et par uker ved hjelp av en offentlig tilgjengelig maskinvare. Det er således mulig at i buduschembudet lett beskrevet RSA-kryptert på fingrene, og systemet vil bli håpløst utdatert.

Offisielt i 2003, ble kalt inn spørsmålet sikkerheten av 1024-bits nøkler. Foreløpig er det anbefalt å ha en minimumslengde på 2048 bits.