RSA šifriranje. Opis i implementacija RSA algoritma

RSA enkripcija je jedan od prvih praktičnih kriptosustava s javnim ključem koji se široko koristi za siguran prijenos podataka. Njegova glavna razlika od sličnih usluga jest taj da je ključ za šifriranje otvoren i razlikuje se od ključa za dešifriranje, koji se čuva u tajnosti. U RSA tehnologiji ova asimetrija Temelji se na praktičnoj složenosti faktoring reprodukcije dvaju velikih premijera (faktoring problem).

Povijest stvaranja

Naziv RSA sastoji se od početnih slova prezimena Rivest, Shamir i Adleman, znanstvenici koji su prvi javno opisivali slično enkripcijski algoritmi u godini 1977. Clifford Cox, engleski matematičar koji je radio za britanske tajne službe, prvi je put razvio ekvivalentni sustav 1973. godine, ali nije bio odbačen do 1997. godine.

RSA korisnik stvara i zatim objavljuje javni ključ koji se temelji na dva velika premijera zajedno s pomoćnom vrijednošću. Premijerni brojevi treba čuvati tajnu. Svatko može koristiti javni ključ za šifriranje poruke, ali ako je dovoljno velik, samo netko tko zna znanje primarnih brojeva može dekodirati poruku. Otkrivanje RSA enkripcije poznato je kao glavni problem: danas ostaje otvorena rasprava o tome koliko je pouzdan ovaj mehanizam.

RSA je relativno spori algoritam, zbog čega nije široko korišten za izravno šifriranje podataka korisnika. U većini slučajeva, ova metoda se koristi za prijenos u dijeljenom ključu šifrirani za simetrični ključ šifriranja, što zauzvrat može izvesti operacije bulk šifriranje i dešifriranje na mnogo višoj brzini.

Kada se kriptosustav pojavio u modernom obliku?

Ideja asimetričnog kriptosustavnog ključa pripisuje se Diffie i Hellman, koji je 1976. objavio koncept, predstavivši digitalne potpise i pokušavajući primijeniti teoriju brojeva. Njihova formulacija koristi zajednički tajni ključ, stvoren iz eksponencijanja brojnog modula premijera. Ipak, ostavili su otvoreni problem provođenja ove funkcije, budući da principi faktoringa nisu dobro razumjeli u to vrijeme.

Rivest, Adi Shamir i Adleman na Tehnološkom institutu u Massachusettsu napravili su nekoliko pokušaja tijekom cijele godine kako bi stvorili jednosmjernu funkciju koja je teško dekodirati. Rivest i Shamir (kao računalni znanstvenici) ponudili su mnoge potencijalne funkcije, dok je Adleman (kao matematičar) tražio "slabosti" algoritma. Koristili su mnoge pristupe i na kraju su u travnju 1977. razvili sustav koji je danas poznat kao RSA.

EDS i javni ključ

Elektronički digitalni potpis, ili EDS, sastavni je dio elektroničkih tipova dokumenata. Formirana je s određenom kriptografskom promjenom podataka. Uz pomoć ovog atributa moguće je provjeriti integritet dokumenta, njegovu tajnost i odrediti tko je to vlasnik. Zapravo, ovo je alternativa običnom standardnom potpisu.

Taj kriptosustav (RSA-enkripcija) nudi javni ključ, nego se razlikuje od simetričnih. Načelo njegovog funkcioniranja je korištenje dva različita ključa - zatvorena (šifrirana) i otvorena. Prva se koristi za generiranje EDS-a i zatim dobiva priliku za dešifriranje teksta. Drugi - za pravilno šifriranje i provjeru EDS-a.

Korištenje potpisa omogućuje bolje razumijevanje RSA enkripcije, čiji se primjer može citirati kao obični tajni dokument zatvoren od znatiželjnih očiju.

Koja je bit algoritma?

RSA algoritam se sastoji od četiri koraka: stvaranje ključeva, njihova distribucija, šifriranje i dešifriranje. Kao što je već spomenuto, RSA šifriranje uključuje javni ključ i privatni ključ. Otvoren je svima poznat i koristi se za šifriranje poruka. Bit je da se poruke šifrirane javnim ključem mogu dešifrirati samo u određenom vremenu pomoću privatnog ključa.

Iz sigurnosnih razloga, cijeli brojevi bi trebali biti nasumično odabrani i jednaki u veličini, ali se razlikuju u duljini od nekoliko znamenki kako bi faktoriranje bilo teže. Isti brojevi mogu se učinkovito pronaći pomoću testova za njihovu jednostavnost, tako da šifriranje informacija mora nužno postati složenije.

Javni ključ sastoji se od modula i javnog eksponenta. Zatvoreni se sastoji od modula i privatnog pokazatelja, koji se mora čuvati tajnim.

Šifriranje RSA datoteka i slabih točaka

Međutim, postoji niz mehanizama za sjeckanje jednostavnog RSA. Kod šifriranja s niskim rezultatima i malim brojevima brojeva, šifra se može lako otvoriti ako odaberete korijen šifriranog teksta u odnosu na cijele brojeve.

Budući da je RSA enkripcija je deterministički algoritam (tj nema slučajan komponentu), napadač može uspješno pokretanje odabranog teksta otvoreni napad na kriptosustava šifriranjem vjerojatno plaintexts pod javni ključ i provjerava na to jesu li jednaki šifrirana. Semantički sigurna kripto zove u slučaju da napadač ne može razlikovati između dva šifriranje jedni od drugih, pa ako zna relevantne tekstove u proširenom obliku. Kao što je gore opisano, RSA drugih usluga bez padding nije semantički sigurna.

Dodatni algoritmi za šifriranje i zaštitu

Kako bi se izbjegli gore navedeni problemi, u praktičnoj implementaciji RSA, obično se ugrađuje oblik strukturiranog, randomiziranog punjenja prije enkripcije. To osigurava da sadržaj ne padne u raspon nesigurnih tekstualnih tekstova i da se ova poruka ne može otkriti slučajnim odabirom.

Sigurnost RSA kriptosustava i šifriranje informacija temelje se na dva matematička problema: problemu faktorizacije velikih brojeva i stvarnih problema RSA. Puna otkrića šifriranog teksta i EDS-a u RSA smatra se neprihvatljivom na pretpostavku da se oba ova problema ne mogu riješiti u skupini.

Međutim, zbog mogućnosti obnavljanja jednostavnih množitelja, napadač može izračunati tajni ključ iz javnog ključa, a zatim dekriptirati tekst standardnim postupkom. Unatoč činjenici da danas nije pronađena postojeća metoda za faktoring velikih brojeva na klasičnom računalu, nije dokazano da ona ne postoji.

automatizacija

Alat koji se zove Yafu može se koristiti za optimizaciju ovog procesa. Automatizacija u YAFU je moderna funkcija koja kombinira algoritme faktorizacije u intelektualnoj i adaptivnoj metodologiji, što smanjuje vrijeme za pronalaženje čimbenika proizvoljnih ulaznih brojeva. Većina implementacija algoritma je multithreaded, što Yafu omogućuje da u potpunosti iskoriste multi- ili multi- višejezgrenih procesora (uključujući SNFS, SIQS i ECM). Prije svega, to je alat naredbenog retka. Vrijeme provedeno u potrazi za faktorom šifriranja pomoću Yafua na konvencionalnom računalu može se smanjiti na 103,1746 sekundi. Alat procesa binarne datoteke s kapacitetom od 320 bita ili više. Ovo je vrlo složen softver koji zahtijeva određenu količinu tehničkih vještina za instaliranje i konfiguriranje. Stoga, RSA enkripcija C može biti ranjiva.

Pokušaji razbijanja u suvremenim vremenima

U 2009, Benjamin Moody koristeći RSA-512 bitni ključ radi na dešifriranju kriptoteksta za 73 dana, koristeći samo poznati softver (GGNFS) i prosječnu radnu površinu (dvojezgreni Athlon64 na 1900 MHz). Kao što je prikazano iskustvo, potrebno je nešto manje od 5 GB diska i oko 2,5 gigabajta memorije za proces „sijanje”.

Od 2010. godine najveći faktorizirani RSA broj bio je 768 bita (232 decimalna znamenka ili RSA-768). Njegovo otkrivanje trajalo je dvije godine na nekoliko stotina računala u isto vrijeme.

U praksi, međutim, RSA ključevi imaju dugu dužinu - obično od 1024 do 4096 bita. Neki stručnjaci vjeruju da 1024-bitni ključevi mogu postati nepouzdani u skoroj budućnosti ili ih već može napuknuti dobro financiranim napadačem. Međutim, malo će se tvrditi da 4096-bitne tipke također mogu biti otkrivene u doglednoj budućnosti.

planovi

Stoga se općenito pretpostavlja da je RSA siguran ako su brojevi dovoljno velik. Ako je glavni broj 300 bita ili kraći, šifrirani i digitalni potpis može se raspasti nekoliko sati na osobnom računalu pomoću softvera koji je već dostupan u javnoj domeni. Tipke s duljinom od 512 bita, kao što je dokazano, mogu se otvoriti 1999. godine koristeći nekoliko stotina računala. Danas je to moguće u roku od nekoliko tjedana uz korištenje javnog hardvera. Dakle, moguće je da će RSA enkripcija na prstima lako biti otkrivena u budućnosti, a sustav će postati beznadno zastarjel.

Službeno je 2003. godine ispitana sigurnost 1024-bitnih ključeva. Trenutačno se preporučuje duljina od najmanje 2048 bita.