RSA šifriranje. Opis in izvajanje RSA algoritma

Enkripcija RSA je eden prvih praktičnih kriptosistemov z javnim ključem, ki se pogosto uporablja za varen prenos podatkov. Glavna razlika med podobnimi storitvami je, da je šifrirni ključ odprt in se razlikuje od ključa za dešifriranje, ki je v skrivnosti. V tehnologiji RSA ta asimetrija temelji na praktični zapletenosti predvajanja faktorjev dveh velikih primehtnih števil (problem faktoringa).

Zgodovina ustvarjanja

Ime RSA sestavljajo začetni črki priimkov Rivest, Shamir in Adleman, znanstveniki, ki so leta 1977 javno opisali podobne algoritme šifriranja . Clifford Cox, angleški matematik, ki je delal za britanske tajne službe, je leta 1973 razvil enakovreden sistem, vendar do leta 1997 ni bil preklican.

Uporabnik RSA ustvari in nato objavi javni ključ, ki temelji na dveh velikih prime številkah skupaj s pomožno vrednostjo. Preproste številke bi morale biti skrivne. Vsakdo lahko uporablja javni ključ za šifriranje sporočila, če pa je dovolj velik, potem lahko le nekdo, ki ima znanje prvotnih številk, dekodira sporočilo. Razkritje RSA šifriranja je znano kot glavni problem: danes ostaja odprta razprava o tem, kako zanesljiv je ta mehanizem.

RSA je sorazmerno počasen algoritem, zato se ne uporablja za neposredno šifriranje uporabniških podatkov . Najpogosteje se ta metoda uporablja za pošiljanje šifriranih ključev v skupni rabi za simetrični šifrirni ključ, ki pa lahko izvaja veliko množično kodiranje in dešifriranje pri veliko večji hitrosti.

Kdaj se je kriptosistem pojavil v sodobni obliki?

Idejo o asimetričnem ključu kriptosistema pripisujejo Diffie in Hellman, ki je leta 1976 objavil koncept, ki predstavlja digitalne podpise in poskuša uporabiti teorijo številk. Njihova formulacija uporablja skupni tajni ključ, ustvarjen iz eksponentiacije števila, ki je modulo glavnega števila. Vendar pa so odpustili problem izvajanja te funkcije, saj načela faktoringa v tistem času niso bila dobro razumljena.

Rivest, Adi Shamir in Adleman na Tehničnem inštitutu v Massachusettsu so več let poskušali ustvariti enosmerno funkcijo, ki jo je težko dekodirati. Rivest in Shamir (kot računalniški znanstveniki) so ponujali številne potencialne funkcije, medtem ko je Adleman (kot matematik) iskal »slabosti« algoritma. Uporabili so številne pristope in sčasoma aprila 1977 razvili sistem, ki je bil danes znan kot RSA.

EDS in javni ključ

Elektronski digitalni podpis ali EDS je sestavni del dokumentov elektronskega tipa. Nastane z določeno kriptografsko spremembo podatkov. S pomočjo tega atributa je mogoče preveriti celovitost dokumenta, njegovo zaupnost in ugotoviti, kdo je lastnik. Dejansko je to alternativa običajnemu standardnemu podpisu.

Ta kriptosistem (RSA-šifriranje) ponuja javni ključ, ki se razlikuje od simetričnih. Načelo njegovega delovanja je, da se uporabita dva različna ključa - zaprta (šifrirana) in tudi odprta. Prva se uporablja za ustvarjanje EDS in nato možnost, da dekodira besedilo. Druga je dejansko šifriranje in preverjanje EDS.

Uporaba podpisa omogoča boljše razumevanje šifriranja RSA, primer tega pa je mogoče navajati kot navaden klasificiran dokument »zaprto iz radovednih oči«.

Kaj je bistvo algoritma?

RSA algoritem sestavljajo štiri stopnje: generiranje ključev, njihova porazdelitev, šifriranje in dešifriranje. Kot smo že omenili, šifriranje RSA vključuje javni ključ in zasebni ključ. Odprto je lahko vsakomur znano in se uporablja za šifriranje sporočil. Bistvo je, da so lahko sporočila, ki so šifrirana z javnim ključem, dešifrirana le v določenem časovnem obdobju z uporabo zasebnega ključa.

Zaradi varnostnih razlogov je treba celo število naključno izbirati in biti enaka velikosti, vendar se razlikuje po dolžini za nekaj številk, da otežuje faktoring. Enake številke je mogoče učinkovito najti na podlagi preizkusa za njihovo preprostost, zato mora biti šifriranje informacij nujno zapleteno.

Javni ključ sestoji iz modula in javnega eksponenta. Zaprta je sestavljena iz modula in zasebnega indikatorja, ki mora ostati tajen.

Šifriranje RSA datotek in šibke točke

Vendar pa obstajajo številni mehanizmi za hacking preprost RSA. Ko šifrirate z nizkimi rezultati in majhnimi vrednostmi številk, lahko šifro enostavno odprete, če izberete koren šifriranja čez cela števila.

Ker RSA šifriranje je deterministični algoritem (torej nima naključne komponente), lahko napadalec uspešno izbere izbrano besedilo odprtega napada proti kriptosistemu s šifriranjem verjetnih odprtih besedil pod javnim ključem in preverjanjem, ali so enaki šifriranju. Za kriptosistem velja, da je semantično varen, če napadalec ne more razlikovati dveh kodiranj drug od drugega, četudi pozna ustrezna besedila v razširjeni obliki. Kot je opisano zgoraj, RSA brez dodajanja drugih storitev ni semantično varna.

Dodatni algoritmi za šifriranje in zaščito

Da bi se izognili zgornjim težavam, pri praktičnem izvajanju RSA je nekakšna oblika strukturiranega, randomiziranega polnjenja običajno vgrajena pred šifriranje. To zagotavlja, da vsebina ne spada v obseg nevarnih besedilnih besedil in da tega sporočila ni mogoče odkriti z naključnim izbiranjem.

Varnost RSA kriptosistema in šifriranje informacij temeljita na dveh matematičnih problemih: problemih faktoringa velikih števil in dejanskih problemih RSA. Popolno razkritje šifrirnega in digitalnega podpisa v RSA se šteje za nedopustno ob predpostavki, da obeh teh težav ni mogoče razrešiti v skupnem znesku.

Zaradi zmožnosti za obnovitev preprostih množiteljev lahko napadalec iz javnega ključa izračuna tajni ključ in nato z uporabo standardnega postopka dešifrira besedilo. Kljub temu, da danes ni bilo mogoče najti nobene obstoječe metode za faktoring velikih številk na klasičnem računalniku, ni bilo dokazano, da to ne obstaja.

Avtomatizacija

Za optimizacijo tega procesa lahko uporabimo orodje z imenom Yafu. Avtomatizacija v YAFU je sodobna funkcija, ki združuje algoritme faktorizacije v inteligentni in prilagoditveni metodologiji, kar zmanjšuje čas, da bi našli dejavnike poljubnih vhodnih številk. Večina implementacij algoritma je večnitna, kar omogoča Yafu, da v celoti uporablja več-ali večjedrne procesorje (vključno z SNFS, SIQS in ECM). Najprej je orodje za ukazno vrstico. Čas, porabljen za iskanje faktorja šifriranja z uporabo Yafuja na običajnem računalniku, se lahko zmanjša na 103,1746 sekund. Orodje obdeluje binarne datoteke z zmogljivostjo 320 bitov ali več. To je zelo zapletena programska oprema, ki zahteva namestitev in konfiguracijo določene tehnične usposobljenosti. Tako je RSA šifriranje C lahko ranljivo.

Poskusi prebiti v sodobne čase

Leta 2009 je Benjamin Moody, ki uporablja ključ RSA-512, delal na dešifriranju kriptografije za 73 dni z uporabo samo dobro znane programske opreme (GGNFS) in povprečnega namiznega računalnika (dual-core Athlon64 pri 1900 MHz). Kot je pokazala ta izkušnja, je za postopek "presejanja" potreboval nekaj manj kot 5 gigabajtov diska in okoli 2,5 gigabajtov RAM-a.

Od leta 2010 je bila največja faktorizirana številka RSA 768 bitov (232 decimalna števila ali RSA-768). Njegovo razkritje je trajalo dve leti na več sto računalnikov hkrati.

V praksi pa imajo ključi RSA dolgo dolžino - običajno od 1024 do 4096 bitov. Nekateri strokovnjaki verjamejo, da lahko 1024-bitni ključi v bližnji prihodnosti postanejo nezanesljivi ali jih lahko že dobro počutijo dobro financirani napadalci. Vendar pa bodo le redki trdili, da se lahko 4096-bitne ključe razkrije tudi v bližnji prihodnosti.

Obeti

Zato se na splošno domneva, da je RSA varna, če so številke dovolj velike. Če je osnovna številka 300 bitov ali krajša, se lahko šifrirni in digitalni podpis v nekaj urah razkrojijo na osebnem računalniku z uporabo programske opreme, ki je že na voljo v javni domeni. Ključi z dolžino 512 bitov, kot je bilo dokazano, bi se lahko odprli leta 1999 z uporabo več sto računalnikov. Te dni je mogoče več tednov z uporabo javne strojne opreme. Tako je možno, da se RSA šifriranje na prstih zlahka razkrije v prihodnosti, sistem pa bo postal brezupno zastarel.

Uradno v letu 2003 je bila vprašljiva varnost 1024-bitnih ključev. Trenutno je priporočljivo imeti dolžino najmanj 2048 bitov.