RSA šifrēšanas. Apraksts un īstenošana RSA algoritms

RSA-šifrēšana ir viens no pirmajiem praktiskajiem sabiedrības galvenajiem Kriptogrāfiska sistēma, kas tiek plaši izmantoti drošai datu pārraidei. Tās galvenā atšķirība no līdzīgiem pakalpojumiem, ir tas, ka šifrēšanas atslēga ir atvērts, un atšķiras no atšifrēšanas atslēgu, kas tiek turēta noslēpumā. DĀR tehnoloģija , šī asimetrija ir balstīta uz praktisko grūtībām faktoringa atskaņošanu divu lielu prime skaitu (problēmu faktoringa).

Vēsture radīšanas

RSA nosaukums sastāv no sākuma burti uzvārdu Rivest, Shamir un Adleman - zinātniekiem, kuri pirmo reizi publiski aprakstītas šīs šifrēšanas algoritmus 1977.. Klifford Koks, angļu matemātiķis, kurš strādāja britu izlūkdienestu, pirmais, lai attīstītu līdzvērtīgu sistēmu 1973. gadā, taču tas netika deklasificēta līdz 1997

RSA lietotājs izveido un tad publicē publisko atslēgu, pamatojoties uz diviem lieliem prime numuriem kopā ar papildu vērtību. Prime numuri jātur slepenībā. Ikviens var izmantot publisko atslēgu, lai šifrētu ziņu, bet, ja tas ir pietiekami liels, tad tikai kāds ar zināšanām prime skaitu var atšifrēt ziņu. RSA šifrēšanas izpaušana ir pazīstama kā galvenā problēma šodien ir atvērta diskusija par to, kā uzticamu mehānismu.

RSA algoritms ir salīdzinoši lēns, un šī iemesla dēļ tas nav tik plaši izmanto, lai tieši šifrētu lietotājam. Vairumā gadījumu, šī metode tiek izmantota pārraidei ar kopīgu atslēgu šifrētā par simetrisku šifrēšanas atslēgu, kas, savukārt, var veikt darbības, beztaras šifrēšana un ar daudz lielāku ātrumu.

Kad bija cryptosystem savā pašreizējā formā?

Ideja par asimetrisku kriptogrāfijas atslēgu piedēvēt Difī un Hellman, kurš publicēja koncepciju 1976. gadā, ieviešot digitālos parakstus, un cenšoties piemērot teoriju numurus. To sastāvs tiek izmantota koplietota slepena atslēga, ko ražo ar noteiktu skaitu kāpināšana moduļa galvenais numurs. Taču viņi atstāja atvērtu jautājumu par īstenotu šo funkciju, jo faktorings principi nebija labi saprotams tajā laikā.

Rivest, Adi Shamir, un Adleman MIT vairākkārt centies gadu gaitā, lai izveidotu vienvirziena funkciju, kas ir grūti atšifrēt. Rivest un Šamir (kā datoru zinātnieki) ir ierosinājušas daudzus potenciālos funkcijas, bet Adleman (piemēram, matemātika), lai meklētu "vājos punktus" no algoritmu. Viņi izmantoja daudz pieejas un beidzot izstrādāt galīgo sistēmu, kas tagad pazīstama kā RSA 1977. gada aprīlī.

Elektroniskais paraksts un publiskā atslēga

Digitālais paraksts vai elektroniskais paraksts, kas ir neatņemama daļa no elektronisko dokumentu veidiem. Tā ir veidota uz noteiktu datu kriptogrāfiskās izmaiņas. Ar iespējamu šo atribūtu, lai pārbaudītu integritāti dokumentu, tā konfidencialitāte, kā arī, lai noteiktu, kam pieder to. Faktiski, ir alternatīva parastajai standarta parakstu.

Tas cryptosystem (RSA šifrēti) piedāvā publisko atslēgu, atšķirībā simetrisks. Tās darbības princips ir tāds, ka tiek izmantoti divi dažādi taustiņi - slēgts (kodēti) un āra. Pirmais tiek izmantota, lai radītu digitālo parakstu, un tad varēs atšifrēt tekstu. Otrais - par faktisko šifrēšanas un elektronisko parakstu.

Izmantojot parakstus, lai labāk izprastu RSA šifrēšanu, piemērs, ko var samazināt par normālu noslēpumu "slēgta no ziņkārīgo acīm," dokumentā.

Kas ir algoritms?

RSA algoritms sastāv no četriem soļiem: atslēgu ražošanu, sadali, šifrēšanu un atšifrēšanu. Kā jau minēts, RSA šifrēšana ietver publisko atslēgu un privāto atslēgu. Āra var zināms visiem, un to izmanto, lai šifrētu ziņojumus. Tās būtība slēpjas faktā, ka ziņas šifrēti ar publisko atslēgu var atšifrēt tikai noteiktā laika posmā, izmantojot slepeno atslēgu.

Drošības apsvērumu dēļ, tad veseli skaitļi, kas izvēlēti pēc nejaušības principa un būs vienādi pēc lieluma, bet atšķiras garumā ar dažiem skaitļiem, lai padarītu faktoringa grūtāk. Same pašu numuru var efektīvi atrast, veicot testu savā vienkāršībā, tāpēc šifrēšanas informācijas obligāti būt sarežģīta.

Publiskā atslēga sastāv no moduļa un publisko eksponents. Iekštelpu vienība un sastāv no privātā skaitlis, kas būtu jātur slepenībā.

RSA šifrēšanas failu un vājās puses

Tomēr ir vairākas vienkāršas hakeru RSA mehānismiem. Kad šifrējot ar zemiem un mazām vērtībām koda numurus var viegli atvērt, ja pick sakne ciphertext pār veseliem skaitļiem.

Tā kā RSA šifrēšanas ir stingri noteikts algoritms (ti, nav izlases sastāvdaļa), uzbrucējs var veiksmīgi uzsāktu izvēlēto tekstu atklātu uzbrukumu cryptosystem šifrējot iespējamos plaintexts saskaņā ar publisko atslēgu un pārbaudes par to, vai tie ir vienādi ciphertext. Semantiski droša cryptosystem sauc gadījumā, ja uzbrucējs nevar atšķirt starp diviem šifrēšanu no otra, pat tad, ja viņš zina attiecīgos tekstus izvērstā formā. Kā aprakstīts iepriekš, RSA citi pakalpojumi bez polsterējuma nav semantiski droša.

Papildu algoritmi šifrēšanu un aizsardzību

Lai izvairītos no iepriekš minētās problēmas, jo praktiskajā īstenošanā RSA parasti ievieto kādā veidā strukturētu, randomizētā pildījumu pirms šifrēšanu. Tas nodrošina, ka saturs neatbilst diapazonā nedrošu plaintexts, un ka šis ziņojums nevar atrisināt, izlases kārtībā.

Drošība RSA cryptosystem un šifrēšanas, pamatojoties uz diviem matemātiskas problēmas: problēma faktoringa lielu skaitu un faktisko RSA problēmu. Pilna atklāšana ciphertext un paraksta RSA tiek uzskatīts par nepieņemamu uz pieņēmumu, ka abas šīs problēmas nevar atrisināt kolektīvi.

Tomēr ar iespēju atgūt reizinātājus, uzbrucējs var aprēķināt slepeno eksponents publisko atslēgu, un tad atšifrēt tekstu, izmantojot standarta procedūru. Neskatoties uz to, ka šodien neviens esošais metode faktoringa lielus veselus skaitļus par klasisko dators nevar atrast, tas nav pierādīts, ka viņš neeksistē.

automatizācija

Rīks Yafu, var izmantot, lai optimizētu procesu. Automatizācija YAFU ir papildu funkcija, kas apvieno factorization algoritmi intelektuālās un adaptīvās metodoloģiju, kas samazina laiku, lai atrastu faktorus patvaļīgu ieejas numurus. Vairums instrumentu multithreaded algoritms ļauj Yafu pilnībā izmantot daudz- vai daudzām daudzkodolu procesoriem (ieskaitot SNFS, SIQS un ECM). Pirmkārt, tas kontrolē komandrindas rīks. Kas pavadīts meklējot šifrēšanas Yafu faktoru izmantojot parasto datoru laiks, to var samazināt līdz sekundēm 103.1746. Šis rīks apstrādā bināro jauda 320 biti vai vairāk. Tas ir ļoti sarežģīts programmatūru, kas prasa noteiktu daudzumu tehnisko iemaņu, lai instalēt un konfigurēt. Tādējādi RSA šifrēšana var būt neaizsargāti C.

Datorurķēšana mēģinājumi pēdējā laikā

2009. Bendzhamin Mudi izmantojot RSA-512 bitu atslēgu strādā pie tā atšifrējums kriptoteksta uz 73 dienām, izmantojot tikai labi zināms programmatūru (GGNFS) un vidējo darbvirsmas (dual-core Athlon64 pie 1900 MHz). Kā liecina pieredze, nepieciešami nedaudz mazāk nekā 5 GB diska un aptuveni 2,5 gigabaitu atmiņu procesa nodrošināšanai "sijāšanas".

Kopš 2010. gada, kas ir lielākais skaits, tika ņemti RSA 768 bitus garas (232 decimālsk vai RSA-768). Viņa atklāšana ilga divus gadus uz vairākiem simtiem datoriem vienlaicīgi.

Praksē RSA atslēgās ir garš - parasti no 1024 līdz 4096 bitiem. Daži eksperti uzskata, ka 1024 bitu atslēgas var kļūt uzticami tuvākajā nākotnē vai pat ilgāk, var būt sašķelts ļoti labi finansētas uzbrucējiem. Tomēr daži varētu apgalvot, ka 4096-bit atslēgas var izpaust tuvākajā nākotnē.

perspektīvas

Tāpēc, kā likums, tiek pieņemts, ka RSA ir droša, ja skaits ir pietiekami liels. Ja bāze skaits 300 biti vai īsāks, un ciphertext digitālo parakstu var sadalīt dažu stundu laikā, izmantojot personālo datoru, izmantojot programmatūru, kas pieejami jau publiski. Atslēgas garumu 512 biti, kā redzams, var atvērt jau 1999. gadā, izmantojot dažus simtus datoriem. Mūsdienās tas ir iespējams, pēc pāris nedēļām, izmantojot publiski pieejamu aparatūru. Tādējādi ir iespējams, ka buduschembudet viegli atklāt RSA šifrēta uz pirkstiem, un sistēma kļūs bezcerīgi novecojusi.

Oficiāli 2003. gadā, tika apšaubīts uz 1024 bitu atslēgas drošību. Pašlaik tas ir ieteicams, lai būtu minimālais garums 2048 bitiem.