RSA krüptimine. RSA algoritmi kirjeldus ja rakendamine

RSA-krüpteerimine on üks esimesi praktilist krüpto-süsteeme, millel on avalik võti, mida laialdaselt kasutatakse turvaliseks andmeedastuseks. Selle peamine erinevus sarnaste teenuste vahel on see, et krüpteerimisvõti on avatud ja erineb dekodeerimisvõtmest, mis on salajane. RSA-tehnoloogia puhul põhineb see asümmeetria kahe suure peamise numbri faktooringu taasesitamise praktilise keerukusega (faktorite probleem).

Looja ajalugu

Nimi RSA koosneb perekonnanimede Rivest, Shamir ja Adleman algkirjutustest, kes 1977. aastal avalikult kirjeldasid sarnaseid krüpteerimisalgoritme . Suurbritannia salateenistuste eest töötanud inglise matemaatik Clifford Cox lõi esmakordselt samaväärse süsteemi 1973. aastal, kuid seda ei kustutatud enne 1997. aastat.

RSA kasutaja loob ja seejärel avaldab avaliku võtme, mis põhineb kahel suurel primearvul koos lisaväärtusega. Lihtsaid numbreid tuleb hoida salajas. Igaüks saab sõnumit krüptida kasutada avaliku võtmega, kuid kui see on piisavalt suur, siis saab sõnumit dekodeerida ainult üks peamine numbrite kohta. Peamine probleem on RSA krüpteerimise avalikustamine: täna on avatud arutlus selle üle, kui usaldusväärne on see mehhanism.

RSA on suhteliselt aeglane algoritm, mistõttu seda ei kasutata laialdaselt kasutajaandmete otsesel krüptimiseks . Enamasti kasutatakse seda meetodit krüpteeritud jagatud võtmete saatmiseks sümmeetrilise krüpteerimisvõtme jaoks, mis omakorda suudab suurema kiirusega massi krüpteerimist ja dekrüpteerimist teha.

Millal praegusel kujul ilmnes krüptoosüsteem?

Asümmeetrilise krüpto-süsteemivõtme idee on omistatud Diffie ja Hellmanile, kes avaldas kontseptsiooni 1976. aastal, esitades digitaalallkirju ja üritades arvude teooriat rakendada. Nende koostises kasutatakse ühist salajast võtit, mis on loodud numbri modulo suurimast numbrist. Siiski jätsid nad selle ülesande täitmise probleemi lahti, sest faktooringu põhimõtted sel ajal ei arusaadavalt.

Rivest, Adi Shamir ja Adleman Massachusettsi Tehnoloogiainstituudis on aasta jooksul teinud mitmeid katseid, et luua ühesuunaline funktsioon, mida on keeruline dekodeerida. Rivest ja Shamir (arvutiteadlased) pakkusid palju potentsiaalseid funktsioone, samas kui Adleman (matemaatik) otsis algoritmi "nõrkusi". Nad kasutasid palju lähenemisviise ja lõpuks aprillis 1977 arenenud süsteem lõpuks tuntud täna kui RSA.

EDS ja avalik võti

Elektrooniline digitaalallkiri või EDS on elektrooniliste dokumentide lahutamatu osa. See on moodustatud andmete teatud krüptograafilise muutusega. Selle atribuudi abil on võimalik kontrollida dokumendi terviklikkust, selle konfidentsiaalsust ja määrata, kellele see kuulub. Tegelikult on see tavalise tavapärase allkirja alternatiiv.

See krüptosüsteem (RSA-krüpteerimine) pakub avalikku võtit kui erineb sümmeetrilisest. Selle toimimise põhimõte on see, et kasutatakse kahte erinevat võtme - suletud (krüptitud) ja ka avatud. Esimest kasutatakse EDS genereerimiseks ja seejärel saab teksti dekodeerimise võimalust. Teine on EDSi tegelik krüpteerimine ja kontrollimine.

Allkirja kasutamine võimaldab paremini mõista RSA-krüpteerimist, mille eeskuju võib tsiteerida tavapärase salajase dokumendina "suletud peetavate silmade" all.

Mis on algoritmi olemus?

RSA algoritm koosneb neljast etapist: võtmete genereerimine, nende levitamine, krüptimine ja dekrüptimine. Nagu juba mainitud, hõlmab RSA krüptimine avalikku võtit ja privaatvõtit. Avatud saab teada kõigile ja seda kasutatakse sõnumite krüptimiseks. Selle sisuks on see, et avaliku võtmega krüptitud kirju saab dekrüpteerida ainult teatud aja jooksul privaatvõtme abil.

Turvalisuse huvides peaks täisarvud olema juhuslikult valitud ja sama suurusega, kuid erinevad pikkusega mõne numbriga, et muuta faktoring veelgi raskemaks. Neid samu numbreid saab efektiivselt leida nende lihtsuse testiga, seega tuleb teabe krüpteerimine tingimata muutuda keerulisemaks.

Avalik võtmeks on moodul ja avalik eksponent. Suletud moodustab mooduli ja erasektori näitaja, mida tuleb hoida salajas.

RSA-failide ja nõrkade kohtade krüptimine

Siiski on olemas mitmeid mehhanisme lihtsa RSA häkkimise jaoks. Kui krüpteeritakse väikeste punktidega ja väikeste väärtustega, saab šifri kergesti avada, kui valite täisarvude abil šifterteksti root.

Kuna RSA-krüpteerimine on deterministlik algoritm (see tähendab, et tal pole juhuslikku komponenti), saab ründaja edukalt käivitada valitud avatud rünnakute teksti krüptoosüsteemi vastu, krüpteerides tõenäolisi avatud tekste avaliku võtme abil ja kontrollides, kas need on võrdsed ciphertext'iga. Krüptosüsteem on semantiliselt turvaline juhul, kui ründaja ei saa üksteisest eristada kahte kodeeringut, isegi kui ta teab vastavaid tekste laiendatud kujul. Nagu eespool kirjeldatud, pole RSA ilma muude teenuste lisamiseta semantiliselt turvaline.

Krüptimise ja kaitse täiendavad algoritmid

Eespool nimetatud probleemide vältimiseks on RSA praktilise rakendamise käigus enne krüpteerimist ehitatud mõni struktureeritud, randomiseeritud täidis. See tagab, et sisu ei kuulu ohtlike lihtsate tekstide hulgast ja et seda teadet ei saa juhusliku valiku abil avastada.

RSA krüptosüsteemi turvalisus ja teabe krüptimine põhinevad kahel matemaatilisel probleemil: suure hulga faktooringu probleemid ja RSA tegelikud probleemid. RSA-s olev tsifterteksti ja digitaalallkirja täielik avalikustamine loetakse vastuvõetamatuks eeldusel, et mõlemad probleemid ei saa koondandmetes lahendada.

Kuid lihtsate multiplikaatorite taastamise võime tõttu võib ründaja avaliku võtme abil arvutada salajase võtme ja seejärel lahti krüptida tavalise protseduuri kasutades. Hoolimata asjaolust, et tänapäeval pole leitud ühtegi olemasolevat meetodit arvukate arvukate tegelike klassikalise arvuti jaoks, ei ole tõestatud, et seda ei eksisteeri.

Automatiseerimine

Selle protsessi optimeerimiseks saab kasutada Yafu tööriista. Automatiseerimine YAFUs on tänapäevane funktsioon, mis ühendab algoritmid faktoriseerimiseks intelligentses ja adaptiivses metoodikas, mis minimeerib aega mehaaniliste sisendnumbrite tegurite leidmiseks. Enamik algoritmi rakendusi on mitme keermestusega, mis võimaldab Yafu'il kasutada täielikult mitme- või mitme tuumaga protsesse (sh SNFS, SIQS ja ECM). Esiteks on see käsurea tööriist. Krüptefaktori otsimisel tavapärasel arvutis kasutatavat Yafu'it saab vähendada 103.1746 sekundiks. Tööriist töötleb binaarfailide mahtu 320 biti või rohkem. See on väga keeruline tarkvara, mis nõuab teatud tehniliste oskuste installimist ja seadistamist. Seega on RSA krüpteerimine C haavatav.

Püüded murda kaasaegsetel aegadel

2009. aastal töötas Benjamin Moody kasutades RSA-512 bitivõtmega krüptograafiat dekrüpteerimisega 73 päeva, kasutades ainult tuntud tarkvara (GGNFS) ja keskmist lauaarvuti (kahetuumaline Athlon64 1900 MHz). Nagu näitas see kogemus, kulus veidi vähem kui 5 gigabaiti kettale ja ligikaudu 2,5 gigabaiti RAM-i jaoks "sõelumiseks".

Alates 2010. aastast oli RSA suurim faktoriseeritud 768 bitti pikk (232 numbrit või RSA-768). Tema avaldamine kestis kaks aastat korraga mitusada arvutit.

Praktikas aga on RSA võtmed pikad - tavaliselt 1024 kuni 4096 bitti. Mõned eksperdid usuvad, et 1024-bitine võtmed võivad lähitulevikus osutuda ebausaldusväärseks või isegi hästi rahastatud ründaja poolt juba purunenud. Kuid vähesed väidavad, et 4096-bitiseid võtmeid saab ka lähitulevikus avalikustada.

Väljavaated

Seetõttu eeldatakse üldiselt, et RSA on ohutu, kui need on piisavalt suured. Kui baasnumber on 300 bitti või lühem, saab selle tsirktteksti ja digitaalallkirjaga jagada mõne tunni jooksul arvutisse, kasutades juba avalikkusele kättesaadavaks olevat tarkvara. Võimalikud 512-bitised klahvid, nagu see oli tõendatud, võib avada 1999. aastal, kasutades mitut sada arvutit. Nendel päevadel on avaliku riistvara kasutamine mitu nädalat võimalik. Seega on täiesti võimalik, et RSA krüpteerimine sõrmedel avaneb tulevikus kergesti ja süsteem muutub lootusetult vananenudks.

Ametlikult 2003. aastal küsitati 1024-bitise võtme turvalisust. Praegu soovitatakse pikkus vähemalt 2048 bitti.