RSA-encryption. Përshkrimi dhe zbatimi i algoritmit RSA

RSA-encryption është një nga e para praktike cryptosystems publik-kyçe që është përdorur gjerësisht për transmetimin e të dhënave të sigurt. Dallimi kryesor i saj nga shërbime të ngjashme është se çelësi encryption është e hapur dhe e ndryshme nga kyç decryption, e cila është mbajtur sekret. Teknologjia RSA , kjo asimetri është i bazuar në vështirësi praktike të factoring riprodhimin e dy numri të madh të kryeministrit (problemi i faktorizimit).

Historia e krijimit

RSA Emri përbëhet nga shkronja fillestare e mbiemrat Rivest, Shamir dhe Adleman - shkencëtarët të cilët për herë të parë publikisht përshkruara këto algoritme encryption në vitin 1977. Klifford Koks, një matematikan anglisht, i cili ka punuar për shërbimet e inteligjencës britanike, i pari për të zhvilluar një sistem ekuivalent në vitin 1973, por ajo nuk u deklasifikuar deri në vitin 1997

RSA përdoruesi krijon dhe pastaj publikon çelësi publik në bazë të dy një numër të madh të kryeministrit së bashku me vlerën ndihmëse. numrave të kryeministrit duhet të mbahen sekret. Çdokush mund të përdorni çelësin publik të encrypt një mesazh, por në qoftë se ajo është mjaft e madhe, atëherë vetëm dikush me njohuri të numrave të kryeministrit mund të deshifroj mesazhin. RSA zbulimi encryption është i njohur si problemi kryesor sot është një diskutim i hapur në lidhje me se si një mekanizëm të besueshëm.

RSA algoritmi është relativisht i ngadaltë, për të cilën arsye ajo nuk është përdorur si gjerësisht të drejtpërdrejtë encrypt përdoruesit. Në shumicën e rasteve, kjo metodë është përdorur për transmetim në kyç të përbashkët të koduar për një çelës simetrik encryption, e cila nga ana mund të kryejnë operacione encryption pjesa më e madhe dhe decryption me një shpejtësi shumë më të lartë.

Kur ka pasur një cryptosystem në formën e tanishme?

Ideja e çelësit asimetrik kriptografike atribuohet Diffie dhe Hellman, i cili botuar konceptin në vitin 1976, duke futur nënshkrime digjitale, dhe duke u përpjekur për të aplikuar teorinë e numrave. Formulimi i tyre përdor një çelës të përbashkët sekret të gjeneruara nga një numër i caktuar i exponentiation modulo një numër kryesor. Megjithatë, ata e lanë të hapur çështjen e realizimit të këtij funksioni, pasi që parimet e factoring nuk është kuptuar mirë në atë kohë.

Rivest, Adi Shamir, dhe Adleman në MIT kanë bërë disa përpjekje gjatë viteve për të krijuar një funksion një mënyrë që është e vështirë për të deshifroj. Rivest dhe Shamir (si shkencëtarët kompjuterike) kanë propozuar shumë funksione të mundshme, ndërsa Adleman (si matematika) për të kërkuar për "pikat e dobëta" të algoritmit. Ata kanë përdorur një shumë të qasjeve dhe përfundimisht të zhvillojë një sistem përfundimtar, i njohur tani si RSA në prill 1977.

Nënshkrimi elektronik dhe çelësi publik

nënshkrim dixhital ose nënshkrimi elektronik, është një pjesë integrale e llojeve të dokumenteve elektronike. Ajo është formuar në një disa ndryshime kriptografike të dhënave. Me këtë atribut të jetë e mundur për të kontrolluar integritetin e dokumentit, konfidencialiteti i saj, si dhe për të përcaktuar se kush zotëron atë. Në fakt, një alternativë për nënshkrim të zakonshëm standarde.

Kjo cryptosystem (RSA-Encrypted) ofron çelësin publik, ndryshe nga simetrik. Parimi i saj i operacionit është që të dy çelësat e ndryshme janë përdorur - të mbyllura (koduar) dhe në natyrë. E para është përdorur për të gjeneruar nënshkrimin dixhital dhe pastaj të jenë në gjendje të decrypt tekstin. Së dyti - për encryption duhur dhe nënshkrimin elektronik.

Përdorimi i nënshkrimeve për të kuptuar më mirë encryption RSA, një shembull i cili mund të reduktohet si një sekret normale "mbyllur nga sytë prying," dokumenti.

Çfarë është algoritmi?

RSA algoritmi përbëhet nga katër hapa: gjenerimit kryesor, shpërndarjen, encryption dhe decryption. Siç është përmendur tashmë, RSA-encryption përfshin një çelës publik dhe një çelës privat. Outdoor mund të jetë i njohur për të gjithë dhe është përdorur për të encrypt mesazhe. Thelbin e saj qëndron në faktin se mesazhe të koduara me çelësin publik mund të decrypted vetëm në një periudhë të caktuar kohe duke përdorur një çelës sekret.

Për arsye sigurie, të integers për t'u zgjedhur në mënyrë të rastësishme dhe të jenë identike në madhësi, por ndryshojnë në gjatësi nga një numër shumë pak për të bërë factoring më të vështirë. Numri Same njëjta gjë mund të gjenden në mënyrë efektive nga një test në thjeshtësinë e tyre, kështu që encryption e informacionit duhet domosdoshmërisht të jetë e komplikuar.

Çelësi publik përbëhet nga modulus dhe eksponent publik. njësia e brendshme dhe përbëhet nga një figurë private, të cilat duhet të mbahen sekret.

RSA encryption e dosjeve dhe të dobëta

Megjithatë, ka një numër të mekanizmave të thjeshtë thatë RSA. Kur encrypting me vlera të ulëta dhe të vogla të numrave të kodeve mund të hapen lehtë, në qoftë se ciphertext rrënja vini mbi integers.

Që nga RSA-encryption është një algoritëm determinist (dmth, nuk ka asnjë komponent të rastit), një sulmues mund të me sukses të nisë sulmin e përzgjedhur tekst hapur kundër cryptosystem nga encrypting plaintexts mundshme nën çelës publik dhe kontrolle mbi nëse ata janë ciphertext të barabartë. Semantike cryptosystem sigurt është quajtur në rast se një sulmues nuk mund të dallojë në mes të dy encryption nga njëri-tjetri, edhe në qoftë se ai e di tekstet përkatëse në formën e zgjeruar. Siç përshkruhet më sipër, RSA shërbime të tjera pa mbushje nuk është semantike sigurt.

algoritme shtesë për encryption dhe mbrojtjen e

Për të shmangur problemet e mësipërme, në zbatimin praktik të RSA janë futur zakonisht në një formë të strukturuar, mbushjes randomized para encryption. Kjo siguron se përmbajtja nuk bie brenda intervalit të plaintexts të pasigurta, dhe se ky mesazh nuk mund të zgjidhet me përzgjedhje të rastësishme.

Security RSA cryptosystem dhe encryption bazuar në dy probleme matematikore: problemi i factoring një numër të madh dhe problemin aktual RSA. Zbulimi i plotë i ciphertext dhe nënshkrimit në RSA është konsideruar e papranueshme në supozimin se të dyja këto probleme nuk mund të zgjidhen në mënyrë kolektive.

Megjithatë, me aftësinë për të rimarrë faktorët kryesor, një sulmues mund të llogarisim eksponent fshehtë e çelësit publik dhe pastaj të decrypt tekst duke përdorur procedurën standarde. Pavarësisht nga fakti se sot nuk ka metodë ekzistues për factoring integers të mëdha në një kompjuter klasike nuk mund të gjendet, ajo nuk është vërtetuar se ai nuk ekziston.

automatizim

Mjet, i quajtur Yafu, mund të përdoret për të optimizuar procesin. Automatizimi në YAFU është një tipar i avancuar që kombinon algoritme Faktorizimi në metodologjinë intelektual dhe adaptive që minimizon kohën për të gjetur faktorët e numrave të dhëna arbitrare. Implementimi më multithreaded algorithm lejuar Yafu përdorimin e plotë të multi ose shumë përpunuesit kryesor (përfshirë SNFS, SIQS dhe ECM). Para së gjithash, ajo është e kontrolluar nga mjet command-line. Koha e kaluar në kërkim për faktorin encryption Yafu duke përdorur një kompjuter konvencional, ajo mund të reduktohet në sekonda 103.1746. Mjet përpunon binar kapacitetin e 320 bit ose më shumë. Kjo është një software shumë kompleks që kërkon një sasi të caktuar të aftësive teknike për të instaluar dhe konfiguruar. Kështu, RSA-encryption mund të jenë të prekshme C.

Thatë përpjekjet në kohët e fundit

Në vitin 2009, Bendzhamin Mudi përdorur RSA-512 bit kyç ishte duke punuar në deshifrimin kriptoteksta për 73 ditë, duke përdorur software vetëm të mirë-njohur (GGNFS) dhe desktop mesatare (dual-core Athlon64 në 1900 MHz). Siç tregohet nga përvoja, kërkohet pak më pak se 5 GB të diskut dhe rreth 2.5 gigabajt të memories për procesin e "shoshitjeje."

Që nga vitit 2010, numri më i madh është faktorë RSA 768 bit të gjata (232 shifra dhjetore, ose RSA-768). zbulimi i tij zgjati dy vjet në disa qindra kompjuterë në të njëjtën kohë.

Në praktikë, çelësat RSA janë të gjatë - në mënyrë tipike nga 1024 në 4096 copa. Disa ekspertë besojnë se 1024-bit çelësat mund të bëhet i pabesueshëm në të ardhmen e afërt apo edhe më të gjatë mund të plasaritur sulmuesit shumë të mirë-financuara. Megjithatë, disa do të argumentojnë se 4096-bit çelësat mund edhe të zbulohen në të ardhmen e afërt.

perspektivat

Prandaj, si rregull, është supozuar se RSA është e sigurtë nëse numrat janë mjaft të mëdha. Nëse numri baza e 300 bit ose më të shkurtër, dhe nënshkrimin ciphertext dixhital mund të zbërthehet brenda pak orësh në një kompjuter personal duke përdorur software në dispozicion tashmë në domenin publik. Një kyç gjatësi 512 bit, siç tregohet, mund të hapet sa më shpejt që 1999, me përdorimin e disa qindra kompjuterë. Në ditët e sotme është e mundur në disa javë duke përdorur një pajisje në dispozicion të publikut. Kështu, është e mundur që në buduschembudet lehtë të zbuluar RSA-koduar në gishta, dhe sistemi do të bëhet pashpresë vjetëruar.

Zyrtarisht në vitin 2003, është vënë në pikëpyetje sigurinë e çelësave 1024-bit. Aktualisht, ajo është e rekomanduar që të ketë një gjatësi minimale prej 2048 bit.