RSA šifrēšana. RSA algoritma apraksts un ieviešana

RSA šifrēšana ir viena no pirmajāmpraktiskas kriptosistēmas ar publisku atslēgu, ko plaši izmanto drošai datu pārraidei. Tās galvenā atšķirība no līdzīgiem pakalpojumiem ir tāda, ka šifrēšanas atslēga ir atvērta un atšķirīga no atšifrēšanas atslēgas, kas tiek glabāta slepenībā. RSA tehnoloģijās šī asimetrija balstās uz divu lielu galveno skaitļu (faktoringa problēma) faktoringa reprodukcijas praktisko sarežģītību.

Radīšanas vēsture

Nosaukums RSA sastāv no uzvārdu sākuma burtiemRivest, Shamir un Adleman - zinātnieki, kas pirmo reizi publiski aprakstītas šīs šifrēšanas algoritmus 1977.. Clifford Cox, 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 pēc tam publicēpubliskā atslēga, kuras pamatā ir divi lieli galvenie numuri kopā ar papildu vērtību. Vienkārši numuri jāsaglabā slepenībā. Ikviens var izmantot publisko atslēgu, lai šifrētu ziņu, bet, ja tas ir pietiekami liels, ziņu var atšifrēt tikai kāds, kurš zina galvenos numurus. RSA šifrēšanas atklāšana ir pazīstama kā galvenā problēma: šodien joprojām pastāv atklāta diskusija par to, cik šis mehānisms ir ticams.

RSA ir salīdzinoši lēns algoritms,tādēļ tas netiek plaši izmantots, lai tieši šifrētu lietotāja datus. Visbiežāk šī metode tiek izmantota, lai nosūtītu šifrētus koplietojamos atslēgas simetriskai šifrēšanas atslēgu, kas savukārt var veikt lielāko šifrēšanas un atšifrēšanas operāciju ar daudz lielāku ātrumu.

Kad kritipsistēma parādījās modernajā formā?

Ideja par asimetrisku kriptosistēmas atslēguDiffie un Hellman, kurš publicēja koncepciju 1976. gadā, iepazīstināja ar digitālajiem parakstiem un mēģināja piemērot skaitļu teoriju. Viņu formulējumā ir izmantota kopēja slepenā atslēga, kas izveidota no vairāku moduļu lieluma palielinājuma. Tomēr viņi atstāja atklātu šīs funkcijas ieviešanas problēmu, jo faktoringa principi tajā laikā nebija labi izprotami.

Rivest, Adi Shamir un Adleman MasačūsetsāTehnoloģijas institūts gada laikā veica vairākus mēģinājumus, lai izveidotu vienvirziena funkciju, kuru ir grūti atšifrēt. Rivest un Shamir (kā datorzinātnieki) piedāvāja daudzas potenciālās funkcijas, bet Adleman (kā matemātiķis) meklēja algoritma "vājās puses". Viņi izmantoja daudzas pieejas, un galu galā 1977. gada aprīlī tika izveidota sistēma, kas beidzot tika zināma šodien kā RSA.

EDS un publiskā atslēga

Elektroniskais ciparsignāls vai EDSir neatņemama elektroniskā tipa dokumentu daļa. Tas ir izveidots ar zināmu datu kriptogrāfisku izmaiņu. Izmantojot šo atribūtu, ir iespējams pārbaudīt dokumenta integritāti, tās konfidencialitāti un arī noteikt, kam tas pieder. Faktiski tā ir alternatīva parastajam standarta parakstam.

Šī kriptosistēma (RSA šifrēšana) piedāvāpubliskā atslēga atšķiras no simetriskās. Tās darbības princips ir tāds, ka tiek izmantotas divas dažādas atslēgas - slēgtas (šifrētas), un arī tās ir atvērtas. Pirmais tiek izmantots EDS ģenerēšanai un pēc tam iespējai atšifrēt tekstu. Otrais - par pareizu EDS šifrēšanu un pārbaudi.

Paraksta izmantošana ļauj labāk izprast RSA šifrēšanu, kuras piemēru var minēt kā parasto slepeno dokumentu, kas slēgts no nevēlamiem skatiem.

Kāda ir algoritma būtība?

RSA algoritms sastāv no četriem posmiem: atslēgu ģenerēšana, to izplatīšana, šifrēšana un atšifrēšana. Kā jau minēts, RSA šifrēšana ietver publisko atslēgu un privāto atslēgu. Atvērt var būt zināms visiem un tiek izmantots, lai šifrētu ziņas. 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ēļ ir jābūt veseliem skaitļiemir izvēlēti pēc nejaušības principa un ir vienādi vērtības ziņā, bet tie atšķiras ar gariem dažiem cipariem, lai padarītu faktoringa grūtāku. Tos pašus skaitļus var efektīvi atrast, izmantojot vienkāršības testu, tāpēc informācijas šifrēšana obligāti kļūst sarežģītāka.

Publiskā atslēga sastāv no moduļa un publiskā eksponāta. Slēgtais sastāv no moduļa un privāta rādītāja, kas jāuzglabā slepenībā.

RSA failu šifrēšana un vājās vietas

Tomēr ir vairāki hakeru mehānismivienkāršs RSA Šifrējot ar zemiem rādītājiem un nelielām skaitļu vērtībām, ciparu var viegli atvērt, izvēloties ciproteksta sakni, izmantojot veselus skaitļus.

Tā kā RSA šifrēšana ir(ti, tam nav izlases komponentes), uzbrucējs var veiksmīgi vadīt atlasīto atklāto uzbrukuma tekstu pret kripto sistēmu, šifrējot iespējamos atklātos tekstus ar publisko atslēgu un pārbaudot, vai tie ir līdzvērtīgi ciphertext. Kriptozīme tiek uzskatīta par semantisku drošību gadījumā, ja uzbrucējs nevar nošķirt divus kodējumus no cita, pat ja viņš pazīst atbilstošos tekstus paplašinātā formā. Kā aprakstīts iepriekš, RSA, neskaitot citus pakalpojumus, nav semantiski droša.

Papildu algoritmi šifrēšanai un aizsardzībai

Lai novērstu iepriekš minētās problēmas, arPraktiskā RSA ieviešana parasti ietver noteiktas formas strukturētu, randomizētu aizpildīšanu pirms šifrēšanas. Tas nodrošina, ka saturs neatrodas nedrošu vienkāršo tekstu klāstā un ka šo ziņojumu nevar atklāt, izvēloties nejauši.

RSA kriptogrāfijas drošība un šifrēšanainformācija balstās uz divām matemātiskām problēmām: lielu faktoringa faktoru problēmu un RSA faktiskajām problēmām. Pilnīga informācija par ciphertext un EDS in RSA tiek uzskatīta par nepieņemamu, pieņemot, ka abas šīs problēmas nevar atrisināt kopumā.

Tomēr sakarā ar atjaunošanas iespējuvienkāršs reizinātājs, uzbrucējs var aprēķināt slepeno atslēgu no publiskās atslēgas un pēc tam atšifrēt tekstu, izmantojot standarta procedūru. Neskatoties uz faktu, ka šodien nav atrasta neviena pašreizējā metode lielu skaitļu faktorēšanai klasiskajā datorā, nav pierādīts, ka tā neeksistē.

Automatizācija

Var būt instruments, ko sauc par Yafuizmantots, lai optimizētu šo procesu. Automatizācija YAFU ir moderna funkcija, kas apvieno inženierijas un adaptīvās metodoloģijas faktorizācijas algoritmus, kas samazina laiku, lai atrastu patvaļīgu ieejas skaitļu faktorus. Lielākā daļa algoritma ieviešanas ir vairāku vītņu, kas ļauj Yafu pilnībā izmantot daudzu vai daudzcentru procesorus (ieskaitot SNFS, SIQS un ECM). Pirmkārt, tas ir komandrindas rīks. Laiks, kas pavadīts, meklējot šifrēšanas faktoru, izmantojot Yafu parastā datorā, var samazināt līdz 103,1746 sekundēm. Rīks veic bināro failu apstrādi ar jaudu 320 bitu vai vairāk. Šī ir ļoti sarežģīta programmatūra, kas prasa noteiktu tehnisko prasmju daudzumu instalēšanai un konfigurēšanai. Tādējādi RSA C šifrēšana var būt neaizsargāta.

Mēģinājumi ielauzties mūsdienās

2009.gadā Benjamin Moody ar nelielu palīdzībuRSA-512 atslēga 73 dienas apstrādāja kodēšanas funkciju, izmantojot tikai plaši pazīstamo programmatūru (GGNFS) un vidējo galda datoru (dual-core Athlon64 1900 MHz). Kā liecina šī pieredze, sijāšanas procesam bija nepieciešams nedaudz mazāk par 5 gigabaitiem diska un aptuveni 2,5 gigabaitu RAM.

Sākot ar 2010. gadu, lielākais faktorizētais RSA skaits bija 768 biti garš (232 zīmes aiz komata vai RSA-768). Viņa atklāšana ilga divus gadus vairākos simtos datoru vienlaicīgi.

Tomēr praksē RSA atslēgas ir garas -parasti no 1024 līdz 4096 bitiem. Daži eksperti uzskata, ka 1024 bitu atslēgas tuvākajā nākotnē var kļūt nedrošas vai arī jau labi var finansēt uzbrucēju. Tomēr daži apgalvo, ka 4096 bitu atslēgas var arī atklāt tuvākajā nākotnē.

Perspektīvas

Tāpēc, kā likums, tiek pieņemts, ka RSAir drošs, ja numuri ir pietiekami lieli. Ja galvenais numurs ir 300 bitu vai īsāks, ciphertext un ciparparakstu var sadalīt vairākas stundas personālajā datorā, izmantojot programmatūru, kas jau ir pieejama publiskajā domēnā. Atslēgas ar garumu 512 biti, kā tas tika pierādīts, varētu atvērt 1999.gadā, izmantojot vairākus simtus datorus. Mūsdienās tas ir iespējams dažu nedēļu laikā, izmantojot publisko aparatūru. Tādējādi ir iespējams, ka RSA šifrēšana pirkstos būs viegli atklājama nākotnē, un sistēma kļūs bezcerīgi novecojusi.

Oficiāli 2003. gadā tika apšaubīta 1024 bitu atslēgu drošība. Pašlaik ieteicams būt vismaz 2048 bitiem garumā.