RSA šifravimas. RSA algoritmo aprašymas ir įgyvendinimas

RSA šifravimas yra viena iš pirmųjų praktinių kriptografinių sistemų su viešuoju raktu, kuris plačiai naudojamas saugiam duomenų perdavimui. Pagrindinis skirtumas nuo panašių paslaugų yra tas, kad šifravimo raktas yra atviras ir skiriasi nuo dekritavimo raktas, kuris yra slaptas. RSA technologijose ši asimetrija yra pagrįsta praktiniu sunkumu faktoringo atkūrimo dviejų didžiųjų skaičių (faktoringo problema).

Kūrimo istorija

Vardas RSA susideda iš pradinių raidžių pavardžių Rivest, Shamir ir Adleman, mokslininkų, kurie pirmą kartą viešai apibūdino panašius šifravimo algoritmus 1977 metais. Anglų matematikas Clifford Cox, dirbantis britų slaptųjų tarnybų, pirmą kartą sukūrė lygiavertę sistemą 1973 m., Tačiau iki 1997 m. Ji nebuvo išslaptinta.

RSA naudotojas sukuria ir tada paskelbia viešąjį raktą, pagrįstą dviem dideliais paprastais skaičiais kartu su papildoma verte. Paprasti numeriai turėtų būti laikomi slaptai. Kiekvienas gali šifruoti pranešimą naudodamas viešąjį raktą, bet jei jis yra pakankamai didelis, tada tik tas, kuris žino pirminius skaičius, gali dekoduoti pranešimą. Pagrindinė problema yra RSA šifravimo atskleidimas: šiandien lieka atvira diskusija apie tai, kaip patikimas šis mechanizmas.

RSA yra palyginti lėtas algoritmas, todėl jis nėra plačiai naudojamas tiesiogiai užšifruoti vartotojo duomenis . Dažniausiai šis metodas naudojamas šifruotų bendrų raktų siuntimui simetriškam šifravimo raktui, kuris savo ruožtu gali atlikti masinio šifravimo ir iššifravimo operacijas daug didesniu greičiu.

Kada kripto sistema atsirado šiuolaikine forma?

Asimetriškos kripto-sisteminės raktos idėja priskiriama Diffie ir Hellmanui, kuris 1976 m. Paskelbė koncepciją, pateikdamas skaitmeninius parašus ir bandydamas taikyti skaičių teoriją. Jų formuluotėje naudojamas bendras slaptasis raktas, sukurtas skaičiuojant skaičių moduliu pagrindiniu skaičiumi. Tačiau jie paliko atvirą šios funkcijos įgyvendinimo problemą, nes faktoringo principai tuo metu nebuvo gerai suprasti.

Rivest, Adi Shamir ir Adleman Masačusetso technologijos institute per kelerius metus bandė kurti vienkryptę funkciją, kurią sunku iššifruoti. Rivestas ir Shamiras (kaip kompiuterių mokslininkai) pasiūlė daugybę galimų funkcijų, o Adlemanas (kaip matematikas) ieškojo algoritmo "silpnybių". Jie naudojosi daugeliu požiūrių ir galiausiai 1977 m. Balandžio mėn. Sukūrė sistemą, kurią pagaliau žinoma kaip RSA.

EDS ir viešasis raktas

Elektroninis skaitmeninis parašas arba EDS yra neatskiriama elektroninio tipo dokumentų dalis. Jis susidaro su tam tikru kriptografiniu duomenų pokyčiu. Naudodamas šį požymį, galima patikrinti dokumento vientisumą, jo konfidencialumą ir nustatyti, kam jis priklauso. Tiesą sakant, tai alternatyva įprastam įprastam parašui.

Ši kripto sistema (RSA-šifravimas) siūlo viešąjį raktą, nei skiriasi nuo simetrinių. Jos veikimo principas yra tai, kad naudojami du skirtingi raktiniai žodžiai: uždaras (užšifruotas), taip pat atidarytas. Pirmasis naudojamas EDS generavimui, o vėliau - teksto dekodavimo galimybė. Antrasis skirtas faktiniam EDS šifravimui ir patikrinimui.

Parašo naudojimas leidžia geriau suprasti RSA šifravimą, kurio pavyzdį galima paminėti kaip įprastą "uždarytą iš smalsių akių" dokumentą.

Kokia yra algoritmo esmė?

RSA algoritmas susideda iš keturių etapų: raktų generavimas, jų platinimas, šifravimas ir iššifravimas. Kaip jau minėta, RSA šifravimas apima viešąjį raktą ir privataus raktą. Atidaryti galima žinoti visiems ir naudoti šifruojant pranešimus. Esmė ta, kad pranešimai, užšifruojami naudojant viešąjį raktą, gali būti iššifruoti tik per tam tikrą laiką naudodami uždarą raktą.

Saugumo sumetimais sveikieji skaičiai turėtų būti atsitiktinai parinkti ir būti vienodi dydžio, tačiau ilgio dydis skiriasi keliais skaitmenimis, kad faktoringas būtų sunkesnis. Tie patys numeriai gali būti efektyviai nustatyti naudojant jų paprastumo testą, todėl informacijos šifravimas būtinai turi tapti sudėtingesnis.

Viešasis raktas susideda iš modulio ir viešosios ekspozicijos. Uždarą sudaro modulis ir privatus rodiklis, kuris turi būti slaptas.

RSA failų šifravimas ir silpnosios vietos

Tačiau yra keletas būdų, kaip įsilaužti paprastą RSA. Kai šifruojatės su mažais balais ir mažomis skaitinių verčių skaičiumi, šifrą galima lengvai atidaryti, jei pasirinksite šifro kodo šaknį per sveikasis skaičius.

Kadangi RSA šifravimas yra deterministinis algoritmas (ty jis neturi atsitiktinio komponento), užpuolikas gali sėkmingai paleisti pasirinktą atvirą atakos tekstą prieš kriptografinę sistemą, šifruodamas tikėtinus atvirus tekstus pagal viešąjį raktą ir tikrinant, ar jie yra lygūs užšifruotam tekstui. Kripto sistema yra semantiniu požiūriu saugi tuo atveju, jei užpuolikas negali atskirti dviejų koduotų vienas nuo kito, net jei jis žino atitinkamus tekstus išplėstine forma. Kaip aprašyta aukščiau, RSA be kitų paslaugų pridėjimo nėra semantiškai saugus.

Papildomi algoritmai šifravimo ir apsaugos

Siekiant išvengti pirmiau minėtų problemų, praktiniame RSA įgyvendinime prieš šifravimą įprastai statoma kokia nors struktūruota, atsitiktinės atrankos užpildyta forma. Tai užtikrina, kad turinys nepatenka į nesaugių paprastų tekstų asortimentą ir kad šis pranešimas negali būti atskleistas atsitiktine parinktimi.

RSA kripto sistemos saugumas ir informacijos šifravimas pagrįstas dviem matematinėmis problemomis: didelių skaičiavimų faktoringo problemomis ir realiomis RSA problemomis. Visiškas RSA šifravimo ir skaitmeninio parašo atskleidimas laikomas nepriimtinu, darant prielaidą, kad abiejų šių problemų negalima išspręsti bendrai.

Tačiau dėl galimybės atkurti paprastus daugintojus užpuolikas gali apskaičiuoti slaptą raktą iš viešojo rakto ir tada iššifruoti tekstą naudodamas standartinę procedūrą. Nepaisant to, kad šiandien nebuvo nustatytas esamas metodas daugybei faktoringo panaudojimo klasikiniame kompiuteryje, nebuvo įrodyta, kad jo nėra.

Automatika

Šiam procesui optimizuoti galima naudoti įrankį "Yafu". Automatika YAFU yra moderni funkcija, jungianti algoritmus faktorizavimo pažangios ir adaptyvi metodika, kuri sutrumpina laiką, norint rasti savavališko įvesties skaičių veiksnius. Dauguma algoritmo įdiegimų yra daugiasluoksniai, todėl "Yafu" visapusiškai gali naudoti daugiaformačius arba daugiakrypčius procesorius (įskaitant SNFS, SIQS ir ECM). Visų pirma, tai yra komandinės eilutės įrankis. Laikas, kuriuo ieškoma šifravimo faktoriaus naudojant "Yafu" įprastu kompiuteriu, gali būti sumažintas iki 103,1746 sekundžių. Įrankis apdoroja dvejetainius failus , kurių talpa yra 320 bitų ar daugiau. Tai labai sudėtinga programinė įranga, kuri reikalauja tam tikrų techninių įgūdžių įdiegti ir konfigūruoti. Taigi RSA šifravimas C gali būti pažeidžiamas.

Bandymai įsilaužti į šiuolaikinius laikus

2009 m. Benjamin Moody, naudodamas RSA-512 bitų raktą, 73 dienas iššifravo kriptografinį įrenginį naudodamas tik gerai žinomą programinę įrangą (GGNFS) ir vidutinį stalinį kompiuterį (dual core Athlon64 1900 MHz). Kaip parodė ši patirtis, "šifravimo" procesui užtruko šiek tiek mažiau nei 5 gigabaito disko ir apie 2,5 gigabaitų RAM.

Nuo 2010 m. Didžiausias factorizuotas RSA skaičius buvo 768 bitų ilgio (232 dešimtainiai skaitmenys arba RSA-768). Jo atskleidimas truko dvejus metus kelis šimtus kompiuterių vienu metu.

Tačiau praktikoje RSA raktų ilgis - paprastai nuo 1024 iki 4096 bitų. Kai kurie ekspertai mano, kad artimiausioje ateityje 1024 bitų raktai gali tapti nepatikimi arba netgi gali būti sugadinti gerai finansuojamas užpuolikas. Tačiau nedaugelis tvirtino, kad artimiausioje ateityje gali būti atskleisti ir 4096 bitų raktus.

Perspektyvos

Todėl paprastai manoma, kad RSA yra saugus, jei skaičiai yra pakankamai dideli. Jei bazinis numeris yra 300 bitų ar trumpesnis, per keletą valandų į kompiuterį, naudojant programinę įrangą, kuri jau yra viešai prieinama, ciphertext ir skaitmeninis parašas gali būti suskaidyti per kelias valandas. Raktai, kurių ilgis 512 bitų, kaip buvo įrodyta, gali būti atidarytas 1999 m., Naudojant kelis šimtus kompiuterių. Šiomis dienomis keletą savaičių galima naudoti viešąją techninę įrangą. Taigi visiškai įmanoma, kad RSA šifravimas pirštais bus lengvai atskleistas ateityje, ir sistema taps beviltiškai pasenusi.

Oficialiai 2003 m. Buvo užginčytas 1024 bitų raktų saugumas. Šiuo metu rekomenduojama turėti mažiausiai 2048 bitų ilgį.