RSA šifriranje. Opis in izvajanje RSA algoritma

RSA šifriranje 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 reproduciranja faktoringa dveh velikih primehtnih števil (problem faktoringa).

Zgodovina ustvarjanja

Ime RSA sestavljajo začetni črki priimkov Rivest, Shamir in Adleman, znanstveniki, ki so prvič javno opisali podobne algoritmi za šifriranje v letu 1977. 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. Prime številke naj ostanejo tajni. Vsakdo lahko uporabi javni ključ za šifriranje sporočila, če pa je dovolj velik, lahko le nekdo, ki ima znanje prvotnih števil, dekodira sporočilo. Razkritje šifriranja RSA je znano kot glavni problem: danes ostaja odprta razprava o tem, kako zanesljiv je ta mehanizem.

RSA je sorazmerno počasen algoritem, zaradi česar ga ne uporabljamo široko za neposredno šifriranje podatkov uporabnik. V večini primerov se ta metoda uporablja za prenos v skupni ključem šifrirani za simetrično šifriranje ključa, kar lahko izvajajo operacije v razsutem stanju šifriranje in dešifriranje na veliko večjo hitrostjo.

Kdaj se je kriptosistem pojavil v sodobni obliki?

Idejo asimetričnega ključa kriptosistema pripisujejo Diffieju in Hellmanu, ki je leta 1976 objavil koncept, predstavil digitalne podpise in poskušal uporabiti teorijo številk. Njihova formulacija uporablja skupni tajni ključ, ki je nastal iz eksponentiacije števila modulo glavnega števila. Kljub temu so pustili odprt problem pri izvajanju te funkcije, saj načela faktoringja v tistem času niso bila dobro razumljena.

Rivest, Adi Shamir in Adleman na Tehnološkem inštitutu Massachusetts 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 tudi 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 uporabljata dva različna ključa - zaprta (šifrirana) in tudi odprta. Prva se uporablja za ustvarjanje EDS in nato dobi priložnost za dešifriranje besedila. Drugi - za pravilno šifriranje in preverjanje EDS.

Uporaba podpisa omogoča boljše razumevanje šifriranja RSA, primer tega pa je mogoče navajati kot navaden tajni dokument, zaprt z nadleženimi očmi.

Kaj je bistvo algoritma?

Algoritem RSA sestavljajo štirje koraki: generiranje ključev, njihova porazdelitev, šifriranje in dešifriranje. Kot smo že omenili, šifriranje RSA vključuje javni ključ in zasebni ključ. Odprto lahko vsakdo pozna in šifrira sporočila. 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.

Iz varnostnih razlogov bi morali biti celo število naključno izbrana in enaka velikosti, vendar se razlikuje po dolžini za nekaj številk, da bi otežili faktoring. Iste številke je mogoče učinkovito najti z uporabo 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 kazalnika, ki mora ostati skrivnost.

Šifriranje datotek RSA in šibkih točk

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

Ker je RSA-šifriranje je determinističen algoritem (tj, ni naključno komponento), napadalec lahko uspešno zaženete izbrano besedilo odprt napad na kriptosistem s šifriranjem verjetne plaintexts pod javnim ključem in preverjanja, ali so enaki šifropisom. Pomensko je varen kripto imenuje v primeru, da napadalec ni mogoče razlikovati med dvema šifriranje drug od drugega, čeprav ve ustreznih besedil 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 oblika strukturiranega, randomiziranega polnjenja običajno zgrajena pred šifriranjem. 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: problemu faktoringa velikih števil in dejanskih problemih RSA. Popolno razkritje šifriranja in EDS v RSA se šteje za nesprejemljivo ob predpostavki, da obeh teh problemov ni mogoče razrešiti v skupnem znesku.

Zaradi zmožnosti obnovitve preprostih množiteljev lahko napadalec iz javnega ključa izračuna tajni ključ in nato dešifrira besedilo s standardnim postopkom. Kljub dejstvu, da danes ni bilo ugotovljeno nobene obstoječe metode za faktoring velikih števil na klasičnem računalniku, ni bilo dokazano, da ne obstaja.

Avtomatizacija

Za optimizacijo tega procesa lahko uporabite orodje z imenom Yafu. Avtomatizacija v YAFU je napredna funkcija, ki združuje razcepa algoritme v intelektualni in prilagodljivo metodologijo, ki bo čim manj časa, da najdejo dejavnikov poljubnih vhodnih številk. Večina implementacij algoritma je večnitna, kar omogoča Yafu, da v celoti izkoristi multi- večjezični procesorji (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 procesira 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 zloma v sodobnem času

Leta 2009 je Benjamin Moody uporabo RSA-512 bitni ključ je delal na dešifriranja kriptoteksta za 73 dni, z uporabo le dobro znane programske opreme (GGNFS) in povprečno namizje (dual-core Athlon64 na 1900 MHz). Kot je pokazala ta izkušnja, je potrebovala nekaj manj kot 5 gigabajtov diska in približno 2,5 gigabajta RAM-a za proces "presejanja".

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

V praksi pa so ključi RSA dolgi - 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 v bližnji prihodnosti razkrije tudi 4096-bitne ključe.

Možnosti

Zato se na splošno domneva, da je RSA varna, če so številke dovolj velike. Če se osnova število 300 bitov ali krajše, in šifriranim digitalnega podpisa lahko razgradi v nekaj urah na osebnem računalniku s pomočjo programske opreme, ki je na voljo že 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. Danes je to mogoče v nekaj tednih z uporabo javne strojne opreme. Tako je mogoče, 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.