RSA-enkripcije. Opis i implementacija RSA algoritma

RSA-enkripcija je jedan od prvih praktičnih javnog ključa kriptosistemi koji se široko koristi za siguran prenos podataka. Njegova glavna razlika od sličnih usluga je da je ključ za šifriranje je otvoren i razlikuje od ključnih dešifriranje, koji se drži u tajnosti. RSA tehnologija , ova asimetrija se temelji na praktičnom poteškoća faktoring reprodukciju dva velika prosta broja (problem faktoring).

Povijest stvaranja

RSA Ime se sastoji od početnih slova prezimena Rivest, Shamir i Adleman - naučnici koji je prvi javno opisao ovih algoritama enkripcije u 1977. Klifford Koks, engleski matematičar, koji je radio za britanske obavještajne službe, prvi razvio ekvivalentan sistem 1973. godine, ali nije skinuta oznaka tajnosti sve do 1997. godine

RSA korisnik kreira, a zatim objavljuje javni ključ na osnovu dva velika prosta broja, zajedno sa dodatnom vrijednosti. Prostih brojeva treba držati u tajnosti. Svako može koristiti javni ključ za šifriranje poruku, ali ako je dovoljno velika, onda samo neko sa znanjem prostih brojeva može dekodirati poruku. RSA otkrivanje enkripcija je danas poznat kao glavni problem je otvorena rasprava o tome kako pouzdan mehanizam.

RSA algoritam je relativno sporo, zbog čega se ne kao široko se koristi za direktno šifriranje korisnika. U većini slučajeva, ova metoda se koristi za prijenos u Zajednički ključ šifrovane za simetrični ključ za enkripciju, što zauzvrat može obavljati operacije bulk šifriranje i dešifriranje na mnogo veće brzine.

Kada je došlo do kriptosistem u svom sadašnjem obliku?

Ideja asimetričnih kriptografski ključ pripisati Diffie i Hellman, koji je objavio koncept 1976. godine, uvođenjem digitalne potpise, i pokušava da primjenjuju teoriju brojeva. Njihova formulacija koristi zajednički tajni ključ generira iz određenog broja stepenovanje modulu odličnoj broj. Međutim, oni su otišli otvaraju pitanje realizacije ove funkcije, jer principi faktoring nije dobro razumio u to vrijeme.

Rivest, Adi Shamir i Adleman na MIT-u su napravili nekoliko pokušaja tokom godina da stvori jednu funkciju-način na koji je teško dekodirati. Rivest i Shamir (kao kompjuterski stručnjaci) predložili su mnoge potencijalne funkcije, dok Adleman (kao što je matematika) za traženje "slabe tačke" algoritma. Koristili su mnogo pristupa i na kraju razviti konačnu sistema, sada poznat kao RSA u travnju 1977.

Elektronski potpis i javni ključ

Digitalnog potpisa ili elektronski potpis, je sastavni dio vrsta elektronskog dokumenta. Ona se formira u određenom kriptografski promjene podataka. Uz ovaj atribut moguće provjeriti integritet dokumenta, njegova tajnost, kao i da se utvrdi ko je vlasnik. U stvari, alternativa običnim standard potpis.

Ovo kriptosistem (RSA šifrirani) nudi javni ključ, za razliku od simetrične. Princip rada je da se dva različita tasteri se koriste - zatvoren (encrypted) i na otvorenom. Prvi se koristi za generiranje digitalnog potpisa, a zatim biti u mogućnosti da dešifruje teksta. Drugi - za stvarne enkripciju i elektronski potpis.

Upotreba potpisa da bolje razumiju enkripciju RSA, primjer koji se može smanjiti kao normalan tajna "zatvoren od znatiželjnih očiju", u dokumentu.

Što je algoritam?

RSA algoritam se sastoji od četiri koraka: ključna proizvodnju, distribuciju, šifriranje i dešifriranje. Kao što je već spomenuto, RSA-šifriranje sadrži javni ključ i privatni ključ. Vanjski može biti poznat svima i koristi se za šifriranje poruka. Njegova suština je u tome da poruke šifrovanu sa javnim ključem može se dešifrovani samo u određenom vremenskom periodu koristi tajni ključ.

Iz sigurnosnih razloga, cijeli brojevi koji se nasumice birani i biti identični u veličini, ali se razlikuju u dužini od nekoliko brojeva da faktoring teže. Isto isti broj mogu efikasno pronašao test u jednostavnosti, tako enkripciju informacija mora nužno biti komplikovano.

Javni ključ se sastoji od modula i javnih eksponent. Unutarnja jedinica i sastoji se od privatnih figura, koja bi trebala biti tajna.

RSA enkripciju datoteka i slabosti

Međutim, postoji niz jednostavnih sjeckanje mehanizama RSA. Kada kriptiranje sa niskim i male vrijednosti šifre se lako može otvoriti, ako je pick korijen šifrata preko cijele brojeve.

S obzirom da je RSA-enkripcija je deterministički algoritam (tj nema slučajne komponente), napadač može uspješno pokrenuti odabrani tekst otvorenog napada na kriptosistem šifrovanjem vjerovatno otvorena komunikacija pa pod javni ključ i provjere da li su jednaki šifrata. Semantički siguran kriptosistem se zove u slučaju da napadač ne može napraviti razliku između dva enkripciju jedni od drugih, čak i ako on zna relevantne tekstove u proširenom obliku. Kao što je opisano gore, RSA ostale usluge bez padding nije semantički siguran.

Dodatni algoritmi za šifriranje i zaštitu

Da bi se izbjegla navedenih problema, u praktičnoj implementaciji RSA obično umetnuta u neki oblik strukturirane, randomiziranih punjenje prije enkripcije. Time se osigurava da se sadržaj ne spada u rasponu od nesigurne otvorena komunikacija i da ova poruka ne može riješiti slučajnim odabirom.

Sigurnost RSA kriptosistem i enkripciju na osnovu dva matematičkih problema: problem faktoring velikom broju i stvarni RSA problem. Cijeli otkrivanje šifrata i potpis u RSA smatra neprihvatljivim na pretpostavci da su oba problemi ne mogu riješiti zajedno.

Međutim, uz mogućnost da se oporavi prostih faktora, napadač može izračunati tajni eksponent javnog ključa, a zatim dešifriranje teksta pomoću standardne procedure. Uprkos činjenici da danas ni jedna postojeća metoda za faktoring velikih cijelih brojeva na klasičnu kompjuter ne može naći, to nije dokazano da on ne postoji.

automatizacija

Alata, pod nazivom Yafu, može se koristiti za optimizaciju procesa. Automatizacija u YAFU je napredna funkcija koja kombinira factorization algoritmi u intelektualnom i adaptivnom metodologija koja smanjuje vrijeme za pronalaženje faktora proizvoljnog unos brojeva. Većina implementacija multithreaded algoritam omogućava Yafu potpunosti iskoristiti multi ili više multi-core procesore (uključujući SNFS, SIQS i ECM). Prije svega, to je pod kontrolom komandne linije alat. Vrijeme provedeno u potrazi za faktor enkripciju Yafu koristeći konvencionalne računar, može se smanjiti na sekundi 103,1746. Alata obrađuje binarni kapaciteta 320 bita ili više. To je vrlo složen softver koji zahtijeva određenu količinu tehničkih vještina za instalaciju i konfiguraciju. Dakle, RSA-šifriranje može biti ranjiv C.

Pokušaja provaljivanja u posljednje vrijeme

U 2009. godini, Bendzhamin Mudi koristeći RSA-512 bitnim ključem radi na odgonetanje kriptoteksta za 73 dana, koristeći samo poznati softver (GGNFS) i prosječne desktop (dual-core Athlon64 na 1900 MHz). Kao što pokazuje iskustvo, potrebna nešto manje od 5 GB diska i oko 2,5 gigabajta memorije za proces "prosijavanje".

Od 2010. godine, najveći broj je faktor RSA 768 bita dug (232 decimala, ili RSA-768). Njegovo objavljivanje je trajalo dvije godine, na nekoliko stotina računala odjednom.

U praksi, RSA ključeva su dugi - tipično 1024-4096 bita. Neki stručnjaci vjeruju da 1024-bitne ključeve i može postati nepouzdan u bliskoj budućnosti ili čak i duže mogu biti napukla napadači vrlo dobro finansirani. Međutim, malo bi se tvrditi da 4096-bitne ključeve može biti otkrivene u bliskoj budućnosti.

perspektive

Stoga, po pravilu, pretpostavlja se da je RSA siguran ako su brojevi su dovoljno veliki. Ako je broj baze 300 bita ili kraće, a šifrata digitalnog potpisa može se rastaviti u roku od nekoliko sati na računaru koristeći softver dostupan već u javnosti. Ključni dužine 512 bita, kao što je prikazano, može biti otvoren već 1999. godine, uz upotrebu nekoliko stotina računala. Danas je moguće u nekoliko tjedana koristeći javno dostupne hardvera. Dakle, moguće je da je u buduschembudet lako otkrivene RSA šifrirani na prstima, a sistem će postati beznadežno zastarjeli.

Zvanično 2003., bio je doveden u pitanje sigurnost 1024-bitne ključeve u. Trenutno, preporučuje se da imaju minimalne dužine 2048 bita.