RSA-encryption. Deskrizzjoni u implimentazzjoni tal-algoritmu RSA

RSA-encryption huwa wieħed mill-ewwel cryptosystems prattiċi pubbliċi-ewlenin li tintuża ħafna għal trasmissjoni tad-data sigura. differenza prinċipali tagħha minn servizzi simili hija li l-encryption ewlenin huwa miftuħ u differenti mill-ċavetta decryption, li tinżamm sigrieta. It-teknoloġija RSA , din l-assimetrija hija bbażata fuq id-diffikultà prattika ta 'factoring l-qari ta' żewġ numri prime kbar (il-problema ta 'factoring).

Storja tal-ħolqien

RSA L-isem jikkonsisti fl-ittri inizjali tal-kunjomijiet Rivest, Shamir u Adleman --xjenzati li l-ewwel deskritti pubblikament dawn algoritmi encryption fl-1977. Klifford KOKS, matematiku Ingliż, li ħadem għal servizzi ta 'intelliġenza Brittaniċi, l-ewwel tiġi żviluppata sistema ekwivalenti fl-1973, iżda ma kienx deklassifikat biss fl-1997

utent RSA toħloq u mbagħad tippubblika l-ċavetta pubblika bbażat fuq żewġ numri kbar prime flimkien mal-valur awżiljarju. numri primi għandhom jinżammu sigriet. Kulħadd jista 'juża ċ-ċavetta pubblika għall-kriptaġġ messaġġ, imma jekk huwa kbir biżżejjed, allura biss xi ħadd bl-għarfien tan-numri primi jistgħu jiddekowdja-messaġġ. RSA iżvelar encryption huwa magħruf bħala l-problema ewlenija llum hija diskussjoni miftuħa dwar kif mekkaniżmu affidabbli.

RSA algoritmu huwa relattivament bil-mod, għal liema raġuni ma tintużax mod wiesa direttament kriptaġġ l-utent. F'ħafna każijiet, dan il-metodu tkun użata għal trasmissjoni fl-iskema maqsuma encrypted għal ċavetta kriptaġġ simmetriku, li mbagħad jistgħu jwettqu operazzjonijiet encryption ingrossa u deċifrar b'veloċità ħafna ogħla.

Meta kien hemm cryptosystem fil-forma preżenti tagħha?

L-idea ta muftieħ kriptografika asimmetrika attribwiti lill Diffie u Hellman, li ppubblika l-kunċett fl-1976, li tintroduċi firem diġitali, u jippruvaw japplikaw l-teorija tan-numri. formulazzjoni tagħhom juża sigrieti ewlenin maqsuma iġġenerat minn ċertu numru ta 'exponentiation modulo numru prime. Madankollu, ikunu telqu tiftaħ il-kwistjoni ta 'realizzazzjoni ta' din il-funzjoni, peress li l-prinċipji ta 'fatturar ma kienx mifhum sew fiż-żmien.

Rivest, Adi Shamir, u Adleman fil-MIT għamlu diversi tentattivi matul is-snin biex jinħoloq funzjoni one-way li huwa diffiċli li jiddekowdja. Rivest u Shamir (kif xjenzjati tal-kompjuter) ipproponew funzjonijiet potenzjali ħafna, filwaqt li Adleman (bħal matematika) ta 'tiftix għal "punti dgħajfa" ta' l-algoritmu. Huma użati ħafna ta 'approċċi u eventwalment tiżviluppa sistema finali, issa magħrufa bħala RSA fil April 1977.

firma elettronika u l-muftieħ pubbliku

firma diġitali jew firma elettronika, hija parti integrali mill-tipi ta 'dokumenti elettroniċi. Huwa ffurmat fil ċerti tibdiliet data kriptografiċi. Ma 'dan l-attribut possibbli li tkun verifikata l-integrità tad-dokument, il-kunfidenzjalità tagħha, kif ukoll li jiġi ddeterminat min hija tippossjedi. Fil-fatt, alternattiva għall firma istandard ordinarja.

Dan cryptosystem (RSA encrypted) joffri l-ċavetta pubblika, b'differenza simetriċi. prinċipju tagħha ta 'operazzjoni hija li ż-żewġ ċwievet differenti huma użati - magħluqa (encrypted) u barra. L-ewwel hija użata biex tiġġenera l-firma diġitali u mbagħad tkun tista 'decrypt-test. It-tieni - għall-kriptaġġ attwali u l-firma elettronika.

Bl-użu firem biex jifhmu aħjar l-encryption RSA, li eżempju tiegħu jista 'jitnaqqas bħala sigriet normali "magħluqa mill prying għajnejn,"-dokument.

X'inhu l-algoritmu?

RSA algoritmu jikkonsisti f'erba 'passi: ġenerazzjoni ewlenin, id-distribuzzjoni, encryption u deċifrar. Kif diġà ssemma, RSA-encryption tinkludi ċavetta pubblika u ċavetta privata. Outdoor jistgħu jiġu magħrufa għal kulħadd u huwa użat għall-kriptaġġ messaġġi. Essenza tiegħu tinsab fil-fatt li l-messaġġi encrypted b'ċavetta pubblika tista 'tiġi decrypted biss fil-perjodu partikolari ta' żmien permezz ta 'ċavetta sigriet.

Għal raġunijiet ta 'sigurtà, l-interi li jintgħażel saltwarjament u jkunu identiċi fid-daqs, iżda jvarjaw fit-tul permezz ta' numri ftit biex tagħmel factoring aktar diffiċli. istess numru istess jista 'jinstab b'mod effettiv permezz ta' test fil-sempliċità tagħhom, sabiex l-encryption ta 'informazzjoni għandha neċessarjament tkun ikkumplikata.

Iċ-ċavetta pubblika tikkonsisti fil-modulu u esponent pubbliku. unità ta 'ġewwa u tikkonsisti minn figura privata, li għandhom jinżammu sigriet.

RSA kodifikazzjoni ta 'fajls u nuqqasijiet

Madankollu, hemm numru ta 'mekkaniżmi sempliċi RSA hacking. Meta encrypting b'valuri baxxi u żgħar ta 'numri ta' kodiċi jista 'jiġi faċilment jinfetaħ, jekk il ciphertext pick għerq matul is-interi.

Peress li l-RSA-encryption huwa algoritmu deterministiku (jiġifieri, m'għandha l-ebda komponent każwali), attakkant jista 'jniedi b'suċċess it-test attakk miftuħ magħżul kontra l cryptosystem mill encrypting plaintexts probabbli taħt il-ċavetta pubblika u l-kontrolli fuq jekk humiex ciphertext ugwali. Semantikament cryptosystem sigura hija msejħa fil-każ li attakkant ma jistgħux jiddistingwu bejn it-tnejn encryption minn xulxin, minkejja li jkun jaf it-testi relevanti fil-forma estiża. Kif deskritt hawn fuq, RSA servizzi oħrajn mingħajr ikkuttunar mhuwiex semantikament sigura.

algoritmi addizzjonali għall encryption u l-protezzjoni

Biex tevita l-problemi msemmija hawn fuq, fl-implimentazzjoni prattika ta 'RSA huma normalment mdaħħla fis xi forma ta strutturat, mili randomised qabel encryption. Dan jiżgura li l-kontenut ma taqax fi ħdan il-firxa ta 'plaintexts prekarji, u li dan il-messaġġ ma jistgħux jiġu solvuti permezz ta' għażla każwali.

Sigurtà cryptosystem RSA u l-encryption bbażata fuq żewġ problemi matematiċi:-problema ta 'factoring numri kbar u l-problema RSA attwali. iżvelar sħiħ tal-ciphertext u firma fil-RSA hija kkunsidrata inammissibbli fuq is-suppożizzjoni li dawn iż-żewġ problemi ma jistgħux jiġu solvuti kollettivament.

Madankollu, bil-kapaċità li jirkupraw fatturi ewlenija, attakkant jistgħu jikkalkolaw l-esponent sigriet taċ-ċavetta pubblika u mbagħad jiddekripta test permezz tal-proċedura standard. Minkejja l-fatt li llum l-ebda metodu eżistenti għall factoring interi kbar fuq kompjuter klassiku ma jistax jinstab, ma ġiex ippruvat li hu ma teżistix.

awtomazzjoni

L-għodda, imsejħa Yafu, jistgħu jintużaw biex jottimizzaw il-proċess. Awtomazzjoni fi YAFU hija karatteristika avvanzati li tgħaqqad algoritmi factorization fil-metodoloġija intellettwali u adattabbli li jimminimizza l-ħin biex isibu l-fatturi ta 'numri input arbitrarji. Ħafna implimentazzjonijiet multithreaded algoritmu li jippermetti Yafu użu sħiħ tal multi- jew bosta proċessuri multi-core (inklużi SNFS, SIQS u ECM). L-ewwelnett, huwa kkontrollat minn għodda kmand tal-linja. Il-ħin mgħoddi tiftix għal fattur Yafu encryption użu ta 'kompjuter konvenzjonali, jista' jitnaqqas għal sekondi 103.1746. L-għodda proċessi l- binarju kapaċità ta '320 bit jew aktar. Dan huwa softwer kumpless ħafna li teħtieġ ċertu ammont ta 'ħiliet tekniċi biex tinstalla u kkonfigurat. Għalhekk, RSA-encryption jista 'jkun vulnerabbli C.

Hacking tentattivi fl-aħħar żminijiet

Fl-2009, Bendzhamin Mudi jużaw RSA-512 bit ċavetta kien qed jaħdem fuq deciphering kriptoteksta għal 73 jiem, permezz ta 'softwer biss magħrufa (GGNFS) u l-desktop medja (dual-qalba Athlon64 fil 1900 MHz). Kif muri mill-esperjenza, meħtieġa ftit inqas minn 5 GB ta 'disk u madwar 2.5 gigabytes ta' memorja għall-proċess ta ' "tgħarbil."

Mill-2010, l-akbar numru kien fatturati RSA 768 bits tul (232 ċifri deċimali, jew RSA-768). iżvelar tiegħu dam sentejn dwar diversi mijiet kompjuters f'daqqa.

Fil-prattika, il-ċwievet RSA huma twal - tipikament minn 1024 sa 4096 bits. Xi esperti jemmnu li l-mezzi 1024-bit jistgħu jsiru affidabbli fil-futur qarib jew saħansitra itwal jista 'jiġi maqsum attakkanti ħafna ffinanzjati tajjeb. Madankollu, ftit kien jargumentaw li ċwievet 4096-bit jista 'jintwera wkoll fil-futur qarib.

prospetti

Għalhekk, bħala regola, huwa preżunt li l RSA huwa sikur jekk in-numri huma kbar biżżejjed. Jekk in-numru bażi ta '300 bit jew iqsar, u l-firma diġitali ciphertext jistgħu jiġu dekompost fi żmien ftit sigħat fuq kompjuter personali jużaw software disponibbli diġà fid-dominju pubbliku. A tul 512-il bit ewlenin, kif muri, jistgħu jinfetħu kmieni kemm-1999, bl-użu ta 'ftit mijiet kompjuters. Illum huwa possibbli ftit ġimgħat li jużaw hardware disponibbli pubblikament. Għalhekk, huwa possibbli li fil buduschembudet faċilment żvelat RSA encrypted fuq il-swaba, u s-sistema se jsiru hopelessly antikwati.

Uffiċjalment fl-2003, ġiet f'dubju s-sigurtà tal-keys 1024-bit. Bħalissa, huwa rakkomandat li jkollhom tul minimu ta '2048 bits.