RSA, a është vërtet kaq e thjeshtë? Zgjedhja e parametrave të shifrës RSA dhe pasojat e mundshme Kriptimi duke përdorur algoritmin rsa

Jo të gjithë përdoruesit e pajisjeve kompjuterike personale e dinë dhe e kuptojnë se çfarë është enkriptimi RSA dhe habiten kur dëgjojnë këtë term. Por nuk ka asgjë të komplikuar të fshehur në këtë koncept. Kriptimi RSA është vetëm një kriptosistem që ju lejon të përdorni në mënyrë të sigurt të gjitha të dhënat elektronike të krijuara në teknologjinë kompjuterike. Ky nuk është deshifrimi i të dhënave, ku skedarët nuk mund të lexohen pa ditur një kod të caktuar. Kriptimi RSA nënkupton që çelësat janë të hapur.

Kriptimi RSA funksionon në parimin e faktorizimit. Si kjo? Dhe ky është faktorizimi
riprodhimi i dy të dhënave të mëdha numerike.

Kush e krijoi sistemin e enkriptimit RSA?

Algoritmi i kriptimit RSA u krijua në vitin 1977, krijuesit e tij janë shkencëtarët Rivest, Shamir, Adleman, një shkurtim i shkronjave fillestare të mbiemrave të tyre përbën termin RSA. Një algoritëm i mëparshëm u zhvillua nga Clifford Cox, një matematikan nga Anglia që punonte për shërbimet e inteligjencës së vendit. Në vitin 1973, ai arriti të krijojë një sistem ekuivalent, por ai u përdor ekskluzivisht nga individë të klasifikuar dhe teknika nuk u shpërnda në nivelin e përdoruesve të zakonshëm të pajisjeve kompjuterike personale.

Si funksionon kriptimi RSA?

Përdoruesi i sistemit fillimisht krijon dhe më pas publikon një çelës publik, i cili bazohet në dy numra të mëdhenj, vetëm me një vlerë ndihmëse. Numrat më të thjeshtë mbahen sekret. Për shembull, për të lexuar një email, thjesht duhet të përdorni çelësin publik të dokumentit, por nëse çelësi është i gjatë, atëherë bëhet e vështirë qasja në informacion.

Sot, kriptimi RSA karakterizohet si një metodë jo shumë e besueshme e kriptimit të të dhënave. Ky është një algoritëm i ngadaltë, kështu që nuk është aq i zakonshëm në mesin e përdoruesve të zakonshëm të kompjuterit. Pra, pse atëherë u krijua ky sistem nëse shkencëtarët e zakonshëm kompjuterikë praktikisht nuk e përdorin atë?

Gjë është se ai ka gjetur aplikimin e tij në transmetimin e koduar të çelësave publikë për një çelës simetrik të kriptimit, i cili është krijuar për kriptim dhe deshifrim në masë me shpejtësi të lartë.

Kriptosistemi modern i çelësit asimetrik u shfaq falë punës së Diffie dhe Hellman. Ata e zhvilluan konceptin në vitin 1976 dhe e prezantuan atë para publikut si regjistrime dixhitale. Ata ishin në gjendje të krijonin një çelës publik bazuar në parimin e shprehjes së një numri të caktuar modulo një numër të thjeshtë. Por parimi i tyre mbeti i varur në ajër, pasi në atë kohë parimet e vetë faktorizimit nuk ishin studiuar ende mirë.

Rivest, Adim Shamir, Adleman nuk u ndalën në atë që kishin arritur më parë dhe përpunuan plotësisht mekanizmin e një funksioni njëdrejtimësh, i cili nuk është aq i lehtë për t'u deshifruar. Rivest dhe Shamir punuan drejtpërdrejt në vetë funksionet, dhe Adleman kërkoi dobësi në algoritmet që po krijoheshin. Përfundimisht, ata patën sukses në krijimin e sistemit të çelësave asimetrik RSA.

Nënshkrimi dixhital dhe komunikimi me çelës publik

Aktualisht, shumë kompani përdorin një element të tillë elektronik si nënshkrim dixhital në aktivitetet e tyre të punës. Dokumentet elektronike të krijuara që përmbajnë të ashtuquajturin nënshkrim dixhital janë dokumente zyrtare të njohura në nivel ligjor. Një nënshkrim elektronik dixhital krijohet kur të dhënat ndryshohen në mënyrë kriptografike.

Kjo alternativë ndaj një nënshkrimi konvencional bën të mundur bërjen e një dokumenti konfidencial, sigurimin e integritetit të tij dhe gjithmonë informacionin për krijuesin dhe pronarin e tij.

Nënshkrimi elektronik është i lidhur ngushtë me kriptimin RSA në fjalë. Ky sistem, siç u përmend më lart, supozon praninë e një çelësi publik. Sot, në praktikë përdoren dy çelësa - publikë - të njohur për të gjithë dhe privat - të koduar për të parandaluar aksesin e informacionit nga personat e paautorizuar.

Kështu, çelësi publik ju lejon të përdorni një dokument me një vulë elektronike, dhe çelësi privat ju lejon të deshifroni nënshkrimin dhe ta verifikoni atë. Me fjalë të tjera, kriptimi RSA ju lejon të fshehni dokumentet nga sytë kureshtarë, t'i mbani ato të fshehta, por me aftësinë për të fituar akses në to në kohën e duhur.

Le të kuptojmë se cili është thelbi i algoritmit të shpikur?

Kriptimi RSA funksionon në katër faza:
gjenerimi i çelësave;
shpërndarja e çelësave;
enkriptimi i çelësit;
deshifrimi i çelësave.

Parimi i kriptimit RSA kombinon krijimin e çelësave publikë dhe privatë. Le të ndalemi përsëri në këtë. E hapur – e njohur për të gjithë, mund të përdoret për të enkriptuar mesazhet. Këto të dhëna elektronike mund të deshifrohen duke përdorur një çelës privat. Gjatë krijimit të çelësave publikë, numrat zgjidhen rastësisht dhe janë të njëjtë në madhësi, por të ndryshëm në kohëzgjatjen e regjistrimit, kështu që faktorizimi është më i vështirë.

Numrat identikë gjenden duke testuar thjeshtësinë e tyre. Kështu, enkriptimi gradualisht u bë më kompleks. Nga se përbëhet një çelës publik? Dhe përbëhet nga një modul i rregullt dhe një i ashtuquajtur eksponent publik. Por ai i mbyllur përfshin një modul dhe një tregues privat, i cili nuk i jepet askujt përveç krijuesit.

Dobësitë e teknikës së kriptimit RSA

Pavarësisht nga parimi i menduar mirë i kriptimit, ai mund të prishet lehtësisht. Kjo mund të bëhet nëse numrat e vegjël janë përdorur për të krijuar çelësat, çelësi mund të zbulohet nga një përzgjedhje e thjeshtë e numrave të plotë;

Vetë kriptimi RSA është një algoritëm që eliminon komponentët e rastësishëm, gjë që e bën më të lehtë për mashtruesit e rrjeteve kompjuterike të thyejnë mekanizmin determinist duke e përputhur atë me tekstin e thjeshtë të sulmeve Dos, të cilat kontrollojnë nëse tekstet e ekzekutuara janë vazhdimisht të barabarta në gjatësi me çelësat e gjeneruar.

Dhe kjo, para së gjithash, shpjegon se kriptimi RSA nuk është i njëjti kriptosistem që është i sigurt në të gjitha aspektet për ruajtjen e të dhënave elektronike nga sulmet nga persona të padëshiruar. Përveç nëse shtohet në serverë më të avancuar, ai fiton veti të tilla.

Komponentë shtesë që sigurojnë sigurinë e përdorimit të kriptimit RSA

Për të parandaluar mundësinë e hakimit të kriptimit të formatit RSA, programuesit ndërtojnë në të një formë të strukturuar, të ashtuquajtur mbushje të rastësishme, kjo bëhet përpara kriptimit aktual të informacionit elektronik. Kjo pikë garanton që përmbajtja e dokumenteve elektronike nuk do t'i prezantohet të gjithëve dhe se informacioni konfidencial nuk mund të shihet kur një mekanizëm për zgjedhjen e rastësishme të çelësave zbatohet në dokumente.

Kriptimi RSA i zbërthen numrat matematikorë në faktorë, por mekanizmi nuk është përsosur kurrë. Prandaj, për momentin, sulmuesit kanë ende mundësinë dhe shumë boshllëqe për të zgjedhur metodat për thyerjen e kriptimit të të dhënave. Dhe këtë arrijnë ta bëjnë pikërisht përmes mekanizmit të rikthimit të faktorëve kryesorë.

Mashtruesit llogaritin treguesin sekret që gjendet në çelësin publik dhe deshifrojnë dokumentacionin duke përdorur një metodë standarde. Pra, fusha e veprimit për ata që vërtet duan të dëmtojnë një kompani është dukshëm e madhe. Le të themi vetëm se problemi i sigurisë së enkriptimit RSA mbetet ende i rëndësishëm dhe i hapur, megjithëse pak njerëz flasin për të publikisht.

Procesi i automatizuar i enkriptimit elektronik të të dhënave

Pavarësisht vlerësimit të ulët të sigurisë, enkriptimi RSA në fjalë është i zbatueshëm në shumë industri. Është veçanërisht e mirëpritur kur ka një qarkullim të madh të dokumentacionit elektronik. Le të themi vetëm se kriptimi RSA përdoret për të mbrojtur dokumentet në një nivel mesatar përgjegjësie.

Softueri Yafu ju lejon të kriptoni automatikisht të dhënat elektronike. Ky program ju lejon të gjeni shpejt të dhëna për krijimin e çelësave asimetrik, duke respektuar rregullat e besueshmërisë së faktorizimit. Është kompatibil me procesorë të tillë si SIQS, ECM, SNFS. Nishet përmes linjës së komandës. Futja e kësaj komande në një rresht ju lejon të zvogëloni disa herë kohën e nevojshme për të kërkuar të dhëna për të krijuar çelësa.

Përdoruesi mesatar i pajisjeve kompjuterike personale nuk mund të përballojë këtë softuer. Instalimi dhe konfigurimi i tij kërkon njohuri të caktuara dhe kjo shpesh bëhet nga programues dhe specialistë të IT.

Kriptimi RSA është seriozisht i cenueshëm, dhe kjo përkundër faktit se numra të mëdhenj përdoren për të krijuar çelësa publikë dhe privatë, që arrijnë në disa mijëra bit në disqe.

Benjamin Moody vërtetoi në vitin 2009 se procesi i thyerjes së çelësave publikë dhe privatë është i mundur. Ndërsa kjo mund të zgjasë dy ose më shumë vjet, fakti mbetet se shumë nga sistemet kompjuterike në botë mund të jenë në rrezik të hakerimit.

Për shembull, ky specialist nuk kishte nevojë për ndonjë gjë të veçantë për të shoshitur skriptet kryesore - kompjuterin e një përdoruesi të rregullt dhe softuerin GGNFS. Edhe praktika e çelësave të enkriptimit të disa bitave të mijërata nuk e mbron informacionin nga lënia e fushës konfidenciale dhe e paarritshme për përdoruesit e tjerë.

Sigurisht, thyerja e kriptimit RSA kërkon kohë. Shumë hakerë shpenzojnë vite për të arritur një rezultat pozitiv. Këto janë shpesh perspektiva me pagesë të lartë që nxisin interesin për të vazhduar kërkimin për çelësin e duhur. Në shumicën e rasteve, hakimi i çelësave të gjatë braktiset në kërkim të perspektivave më të thjeshta. Por kjo nuk do të thotë se askush nuk po përpiqet të krijojë një mekanizëm më të thjeshtuar të thyerjes së çelësave.

Mbrojtja kryesore kundër sulmeve ndërhyrëse nga mashtruesit është krijimi i çelësave të mëdhenj dhe të gjatë prej më shumë se dy mijë bit. Tashmë janë të njohura raste të hakimit të çelësave që variojnë nga njëqind deri në pesëqind bit në gjatësi. Kështu që ju duhet t'i mbani veshët tuaj të mprehtë. Nëse ekziston një mekanizëm për thyerjen e çelësave të shkurtër, puna ndoshta është në lëvizje të plotë diku në anën e keqbërësve për të thyer kombinimet më të gjata të kriptimit elektronik të të dhënave.

konkluzioni

Bazuar në sa më sipër, kriptimi RSA është një metodë e sigurt për të ruajtur konfidencialitetin e të dhënave elektronike, me kusht që të krijohen çelësa të gjatë dhe të pasur me informacion.

Është e vështirë t'i zgjedhësh ato me dorë, kështu që përdoret produkti i automatizuar i softuerit Yafu. Instalohet dhe konfigurohet nga specialistë IT. Nëse e bëni vetë, mund të dëmtoni sistemin operativ të kompjuterit tuaj.
Ky softuer është krijuar për të punuar së bashku me procesorët kompjuterikë me shumë bërthama të gjeneratës moderne.

Objektivat kryesore të sulmeve mashtruese janë kompanitë e mëdha industriale dhe financiare, kështu që pa kriptim RSA, menaxhimi i tyre elektronik i dokumenteve nuk funksionon. Nënshkrimi elektronik i dokumenteve është gjithashtu subjekt i enkriptimit dhe për të zbatohen të njëjtat standarde sigurie si për të dhënat e tjera të informacionit. Parimi - sa më i madh të jetë çelësi, aq më i vështirë është të hakohet dokumenti - duhet të jetë i zbatueshëm për absolutisht të gjitha të dhënat që nuk janë të destinuara për përdorim publik.

Kriptimi RSA është një nga kriptosistemet e para praktike me çelës publik dhe përdoret gjerësisht për transmetim të sigurt të të dhënave. Dallimi kryesor i tij nga shërbimet e ngjashme është se çelësi i enkriptimit është publik dhe ndryshon nga çelësi i deshifrimit, i cili mbahet sekret. Teknologjia RSA bazohet në vështirësinë praktike të faktorizimit të dy numrave të mëdhenj të thjeshtë (problemi i faktorizimit).

Historia e krijimit

Emri RSA përbëhet nga shkronjat fillestare të mbiemrave të Rivest, Shamir dhe Adleman, shkencëtarët që për herë të parë i përshkruan publikisht këto në 1977. Clifford Cox, një matematikan anglez që punoi për shërbimet e inteligjencës britanike, për herë të parë zhvilloi një sistem ekuivalent në 1973, por ai nuk u deklasifikua deri në vitin 1997.

Përdoruesi RSA krijon dhe më pas publikon një çelës publik bazuar në dy numra të mëdhenj të thjeshtë së bashku me një vlerë ndihmëse. duhet mbajtur sekret. Çdokush mund të përdorë një çelës publik për të enkriptuar një mesazh, por nëse ai është mjaft i madh, atëherë vetëm dikush me njohuri për numrat e thjeshtë mund ta dekodojë mesazhin. Thyerja e kriptimit RSA dihet se është një problem i madh: sot ka një debat të hapur se sa i sigurt është mekanizmi.

RSA është një algoritëm relativisht i ngadaltë, prandaj nuk përdoret gjerësisht nga përdoruesi i drejtpërdrejtë. Përdorimi më i zakonshëm i kësaj metode është transmetimi i çelësave të përbashkët të enkriptuar për një çelës simetrik enkriptimi, i cili nga ana tjetër mund të kryejë operacione enkriptimi dhe deshifrimi në masë me shpejtësi shumë më të larta.

Kur u shfaq kriptosistemi në formën e tij moderne?

Ideja e një kriptosistemi çelësi asimetrik i atribuohet Diffie dhe Hellman, të cilët publikuan konceptin në 1976, duke prezantuar nënshkrimet dixhitale dhe duke u përpjekur të zbatojnë teorinë e numrave. Formulimi i tyre përdor një çelës sekret të përbashkët të krijuar nga eksponenti i disa modulit të një numri të thjeshtë. Megjithatë, ata e lanë të hapur problemin e zbatimit të këtij funksioni, pasi në atë kohë parimet e faktoringut nuk kuptoheshin mirë.

Rivest, Adi Shamir dhe Adleman në MIT bënë disa përpjekje gjatë një viti për të krijuar një funksion të njëanshëm që është i vështirë për t'u deshifruar. Rivest dhe Shamir (si shkencëtarë kompjuterikë) propozuan shumë funksione të mundshme, ndërsa Adleman (si matematikan) kërkuan për dobësitë e algoritmit. Ata morën shumë qasje dhe përfundimisht zhvilluan sistemin përfundimtar në prill 1977, i njohur sot si RSA.

Nënshkrimi dixhital dhe çelësi publik

Një nënshkrim elektronik dixhital, ose EDS, është një pjesë integrale e dokumenteve elektronike. Formohet nga një ndryshim i caktuar kriptografik në të dhëna. Duke përdorur këtë atribut, është e mundur të kontrolloni integritetin e një dokumenti, konfidencialitetin e tij dhe gjithashtu të përcaktoni se kush është pronari i tij. Në thelb, kjo është një alternativë ndaj nënshkrimit të zakonshëm standard.

Ky kriptosistem (kriptimi RSA) ofron një çelës publik, i cili e bën atë të ndryshëm nga ata simetrik. Parimi i funksionimit të tij është se përdoren dy çelësa të ndryshëm - privat (i koduar) dhe publik. E para përdoret për të gjeneruar një nënshkrim elektronik dhe më pas të jetë në gjendje të deshifrojë tekstin. E dyta është për enkriptimin dhe verifikimin aktual të nënshkrimit dixhital.

Përdorimi i një nënshkrimi na lejon të kuptojmë më mirë enkriptimin RSA, një shembull i të cilit mund të jepet si një dokument i zakonshëm i klasifikuar "i mbyllur nga sytë kureshtarë".

Cili është thelbi i algoritmit?

Algoritmi RSA përbëhet nga katër faza: gjenerimi i çelësit, shpërndarja e çelësit, enkriptimi dhe deshifrimi. Siç është thënë tashmë, kriptimi RSA përfshin një çelës publik dhe një çelës privat. Open mund të njihet për të gjithë dhe përdoret për të enkriptuar mesazhet. Thelbi i tij është se mesazhet e koduara duke përdorur një çelës publik mund të deshifrohen vetëm brenda një periudhe të caktuar kohore duke përdorur një çelës privat.

Për të qenë të sigurt, numrat e plotë duhet të zgjidhen rastësisht dhe të jenë të njëjtë në madhësi, por të ndryshojnë në gjatësi me disa shifra për ta bërë faktorizimin më të vështirë. Numrat identikë mund të gjenden në mënyrë efektive duke përdorur një test për parësinë e tyre, kështu që kriptimi i informacionit duhet domosdoshmërisht të bëhet më i ndërlikuar.

Një çelës publik përbëhet nga një modul dhe një eksponent publik. Private përbëhet nga një modul dhe një tregues privat që duhet të mbahen sekret.

Kriptimi i skedarëve RSA dhe dobësitë

Megjithatë, ekzistojnë një sërë mekanizmash për thyerjen e RSA të thjeshtë. Kur kriptoni me shpejtësi të ulët dhe numra të vegjël, shifra mund të prishet lehtësisht nëse gjeni rrënjën e tekstit të shifruar mbi numrat e plotë.

Për shkak se enkriptimi RSA është një algoritëm përcaktues (d.m.th., ai nuk ka komponentë të rastësishëm), një sulmues mund të nisë me sukses një sulm të zgjedhur të tekstit të thjeshtë kundër një kriptosistemi duke enkriptuar tekste të besueshme nën çelësin publik dhe duke kontrolluar nëse ato janë të barabarta me tekstin e shifruar. Një kriptosistem thuhet se është i sigurt semantikisht nëse një sulmues nuk mund të dallojë dy kriptime nga njëri-tjetri, edhe nëse ai i njeh tekstet përkatëse në formë të pastruar. Siç u përshkrua më lart, RSA, pa e plotësuar atë me shërbime të tjera, nuk është semantikisht e sigurt.

Algoritme shtesë të kriptimit dhe sigurisë

Për të shmangur problemet e mësipërme, zbatimet praktike të RSA zakonisht ndërtohen në një formë të mbushjes së strukturuar, të rastësishme përpara kriptimit. Kjo siguron që përmbajtja të mos bjerë brenda gamës së tekstit të thjeshtë të pasigurt dhe që mesazhi të mos komprometohet rastësisht.

Siguria e kriptosistemit RSA dhe kriptimi i informacionit bazohen në dy probleme matematikore: problemin e faktorizimit të numrave të mëdhenj dhe vetë problemin RSA. Zbulimi i plotë i tekstit të shifruar dhe nënshkrimit dixhital në RSA konsiderohet i papranueshëm me supozimin se të dyja këto probleme nuk mund të zgjidhen së bashku.

Megjithatë, falë aftësisë për të rikuperuar faktorët kryesorë, një sulmues mund të llogarisë eksponentin sekret nga çelësi publik dhe më pas të deshifrojë tekstin duke përdorur një procedurë standarde. Edhe pse sot nuk është gjetur asnjë metodë ekzistuese për faktorizimin e numrave të mëdhenj në një kompjuter klasik, nuk është vërtetuar se ajo nuk ekziston.

Automatizimi

Një mjet i quajtur Yafu mund të përdoret për të thjeshtuar këtë proces. Automatizimi në YAFU është një veçori më e fundit që kombinon algoritmet e faktorizimit në një metodologji inteligjente dhe adaptive që minimizon kohën për të gjetur faktorët e numrave të hyrjes arbitrare. Shumica e implementimeve të algoritmit janë me shumë fije, duke lejuar Yafu të përfitojë plotësisht nga shumë ose shumë (përfshirë SNFS, SIQS dhe ECM). Para së gjithash, është një mjet i menaxhuar i linjës së komandës. Koha e shpenzuar për të kërkuar një faktor kriptimi duke përdorur Yafu në një kompjuter të rregullt mund të reduktohet në 103,1746 sekonda. Mjeti prodhon kapacitet përpunues prej 320 bit ose më shumë. Ky është softuer shumë kompleks që kërkon një sasi të caktuar aftësish teknike për ta instaluar dhe konfiguruar. Kështu, kriptimi RSA C mund të jetë i cenueshëm.

Përpjekjet për hakerim në kohët moderne

Në vitin 2009, Benjamin Moody, duke përdorur një çelës RSA-512 bit, punoi për të deshifruar kriptotekstin për 73 ditë duke përdorur vetëm softuer të zakonshëm (GGNFS) dhe një kompjuter mesatar desktop (Athlon64 me dy bërthama në 1900 MHz). Siç tregoi kjo përvojë, për procesin e "shoshitjes" kërkoheshin pak më pak se 5 gigabajt disk dhe rreth 2.5 gigabajt RAM.

Që nga viti 2010, numri më i madh i faktorizuar RSA ishte 768 bit i gjatë (232 shifra dhjetore, ose RSA-768). Zbulimi i tij zgjati dy vjet në disa qindra kompjuterë njëkohësisht.

Në praktikë, çelësat RSA janë më të gjatë - zakonisht nga 1024 në 4096 bit. Disa ekspertë besojnë se çelësat 1024-bit mund të bëhen të pasigurt në të ardhmen e afërt ose madje mund të thyhen tashmë nga një sulmues mjaft mirë i financuar. Megjithatë, pak do të argumentonin se çelësat 4096-bit mund të zbulohen gjithashtu në të ardhmen e parashikueshme.

Perspektivat

Prandaj, RSA përgjithësisht supozohet të jetë i sigurt nëse numrat janë mjaft të mëdhenj. Nëse numri bazë është 300 bit ose më i shkurtër, teksti i koduar dhe nënshkrimi dixhital mund të zbërthehen brenda pak orësh në një kompjuter personal duke përdorur softuer që tashmë është i disponueshëm falas. Çelësat 512-bit u vërtetuan se mund të thyheshin që në vitin 1999 duke përdorur disa qindra kompjuterë. Këto ditë, kjo është e mundur brenda pak javësh duke përdorur pajisje të disponueshme publikisht. Kështu, është mjaft e mundur që në të ardhmen kriptimi RSA të prishet lehtësisht në gishta, dhe sistemi do të bëhet pashpresë i vjetëruar.

Zyrtarisht, në 2003, siguria e çelësave 1024-bit u vu në dyshim. Aktualisht rekomandohet të jetë së paku 2048 bit i gjatë.

Më poshtë prerjes janë shembuj të zgjedhjes së parametrave të shifrimit "të keq" RSA.

“Duhet theksuar se duhet pasur kujdes në përzgjedhjen e modulit RSA (numri n) për secilin prej korrespondentëve të rrjetit. Në këtë drejtim, mund të thuhet në vijim. Lexuesi mund të verifikojë në mënyrë të pavarur se duke ditur një nga tre sasitë fq, q ose φ(n), mund ta gjeni lehtësisht çelësin privat RSA...".

Le t'i shtojmë këtij teksti. Nëse zgjedhja e modulit të shifrës RSA është e pasuksesshme, siç u bë në shembullin e manualit të dhënë më poshtë, mund të deshifroni tekstin pa praninë e një çelësi sekret, d.m.th. pa ditur asnjë nga tre sasitë e emërtuara.

Për ta bërë këtë, mjafton të keni tekstin e shifruar të specifikuar nga moduli i shifrës n, çelës publik e shifroni dhe kryeni vetëm tre hapa të një sulmi leximi pa çelës. Pas hapit të katërt të sulmit, konstatohet se teksti burimor është marrë në hapin e mëparshëm dhe mund të lexohet. Le të tregojmë se sa e lehtë është për të bërë.

Së pari, le të japim vetë shembullin nga faqet 313-315 nga manuali në fjalë.

Shembull

Enkriptimi mesazh i shkurtër me tekst fillestar: RSA.
Marrësi vendos shifrën me karakteristikat n=pq=527, Ku p=17, q=31 Dhe φ(n)=(р –1)(q – 1)=480. Si një çelës publik e një numër i zgjedhur që është në krye të φ(n), e=7. Numrat e plotë gjenden për këtë numër duke përdorur algoritmin e zgjeruar Euklidian u Dhe v, duke kënaqur lidhjen e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Sepse –137≡343 (mod480), Kjo d=343.

Ekzaminimi: 7∙343=2401≡1 (mod480).

Mesazhi me tekst paraqitet si një sekuencë numrash që përmbahen në interval . Letra për këtë R, S Dhe A janë të koduar si numra binarë pesë-bitësh. Numrat serial të këtyre shkronjave në alfabetin anglez përdoren në paraqitjen e tyre binar:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Pastaj RSA=(100101001100001) 2. Ndarja e tekstit në blloqe me gjatësi të kufizuar prodhon një prezantim me dy blloqe: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).

Blloqet e tekstit burim janë të koduara në mënyrë sekuenciale M 1 =297, M 2 =33:
y 1 =E k (M 1) = M 1 e ≡297 7 (mod527) = 474.

Këtu kemi përdorur faktin se:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2) = M 2 e ≡33 7 (mod527) = 407.

Teksti i shifruar, si ai origjinal, merret në formën e dy blloqeve: y 1 =474; y 2 =407.

Dekodimi duket se është një sekuencë veprimesh D k (y i)=(y i) d =(y i) 343 (mod 527), i=1.2.

Llogaritjet e fuqisë dështë më e përshtatshme të kryhet duke paraqitur fillimisht eksponentin si shumën e fuqive të numrit 2 , domethënë: 343=256+64+16+4+2+1 .

Duke përdorur këtë paraqitje të eksponentit d=343, marrim:

474 2 ≡174 (mod527),
474 4 ≡237 (mod527),
474 8 ≡307 (mod527),
474 16 ≡443 (mod527),
474 32 ≡205 (mod527),
474 64 ≡392 (mod527),
474 128 ≡307 (mod527),
474 256 ≡443 (mod527),
dhe në fund 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Vlera llogaritet në mënyrë të ngjashme 407 343 (mod527)=33.

Kalimi në paraqitjen e drejtpërdrejtë të mesazhit të deshifruar jep: RSA.

Pas shikimit të shembullit, manuali diskuton qëndrueshmërinë e sistemit RSA. Theksohet nevoja për kujdes në zgjedhjen e modulit të kodit RSA (numrat). n) për secilin prej korrespondentëve të rrjetit. Tregohet se është e papranueshme të injorohen kërkesat për karakteristikat e zgjedhura të sistemit të kriptimit. Midis këtyre kërkesave, për fat të keq, shkelja e të cilave ilustrohet nga shembulli i dhënë nuk tregohet.

Sulmi në shifrën RSA

Le të shohim një shembull të një sulmi në shifrën RSA. Le të përdorim të dhënat nga shembulli i dhënë në faqet 313-315 në tekstin shkollor “Bazat e kriptografisë” të A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Cheremushkin, Moskë. "Helios ARV", 2001.

Dështimi (papranueshmëria) e parametrave të sistemit të zgjedhur në këtë shembull tregohet lehtësisht nga llogaritjet që zbatojnë një sulm ndaj leximit pa çelës të tekstit burimor. Thelbi i një sulmi të tillë është si më poshtë. Është specifikuar çelësi publik i shifrës RSA ( e=7, n=527) dhe tekstin e shifruar. Në shembull, teksti shifror përfaqësohet në dy blloqe
y=(y 1 =474, y 2 =407).

Çdo bllok i koduar sulmohet individualisht, fillimisht ne sulmojmë y 1 =474, pasi e deshifrojmë, sulmojmë një bllok tjetër y 2 =407.

Më pas, një sekuencë vlerash numerike formohet nga kriptimi i përsëritur, duke ruajtur rezultatet e dy hapave të njëpasnjëshëm të algoritmit të sulmit dhe duke përdorur një çelës publik. y i, y 1 =y teksti i shifruar i disponueshëm.

Në algoritmin e sulmit të tekstit të koduar, përcaktohet numri i hapit të mëposhtëm: j, per cilin y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Nga relacioni i fundit shohim se kur ngrihet në një fuqi e vlerat (y i e j–1 (mod n)) fitohet teksti shifror fillestar y i = y 1.

Por kjo do të thotë që teksti i thjeshtë ishte i koduar në këtë hap. Nga llogaritjet e drejtpërdrejta (ka shumë pak prej tyre) duke përdorur një kalkulator në ekran, ne gjejmë atë vlerë j, në të cilin cikli i enkriptimit përfundon me vlerën y 1, nga i cili filloi cikli.

Sulmi në bllokun e parë y 1 =474 teksti i koduar.
Hapi 1:  474 7 (mod527)=382;
Hapi 2:  382 7 (mod527)=423;
Hapi 3:  423 7 (mod527)=297;
Hapi 4:   në këtë hap teksti burimor i gjetur tashmë është i koduar, por duhet bërë pasi sulmuesi nuk e njeh tekstin burimor. Një shenjë e përfundimit të sulmit është koincidenca e vlerës fillestare të tekstit të shifruar ( 474 ) dhe rezultati i hapit të 4-të të kriptimit. Kjo është pikërisht rastësia që ndodh.

297 7 (mod527)=474 mori bllokun fillestar (të parë) të tekstit të shifruar. Sulmi në bllokun e parë përfundoi me sukses y 1 =474. Rezultati i mëparshëm i hapit 3 është i barabartë me tekstin e thjeshtë M 1 =297.

n=527 r=297 modul n=527. Është shkruar kështu y i =у 1 =297. Formimi i mbetjeve të fuqisë
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Sulmi në bllokun e dytë y 2 =407 teksti i koduar.
Hapi 1:  407 7 (mod527)=16;
Hapi 2:  16 7 (mod527)=101;
Hapi 3:  101 7 (mod527)=33;
Hapi 4:  33 7 (mod527)=407.

Përsëri, në hapin e tretë, u mor një bllok teksti burimor ( M 2 =33), por sulmuesi nuk e di këtë dhe ai kryen hapin tjetër (hapin e katërt), rezultati i të cilit është ( 407 ) përputhet me tekstin e shifruar fillestar y 2 =407.

Në thelb në unazën e mbetjeve të modulit n=527 u zbatua një cikël i shkurtër i përpunimit të zbritjes r=33 modul n=527. Është shkruar kështu y i =y 2 =33.
Formimi i mbetjeve të fuqisë ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Rezultati i sulmit (teksti burimor M 1 =297, M 2 =33) fitohet duke enkriptuar tekstin e dhënë shifror tri herë. Është e vështirë të imagjinohet një sukses më i madh për një sulmues të tekstit të koduar.

Duke vazhduar diskutimin e zgjedhjes së modulit dhe parametrave të tjerë të shifrimit, mund të shtojmë se moduli i shifrimit ( n=527) disa tekste burimore nuk mund të kodohen fare. Në këtë rast, zgjedhja e vlerës së çelësit publik nuk luan një rol të madh. Ekzistojnë vlera të tekstit burimor që në përgjithësi është e pamundur të kriptohet me shifrën e zgjedhur me modulin n=527.

Asnjë nga këto të dhëna nuk mund të enkriptojë tekstet burimore të përfaqësuara me numra
187 , 341 , 154 Dhe 373 .

Shembull (pamundësia për të kriptuar vlerat e disa teksteve burimore)

Le të përfaqësohen tekstet burimore me katër blloqe y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Ekspozues eçelësi publik i shifrës mund të jetë çdo numër koprim me funksionin Euler φ(n)=φ(527)=480. Megjithatë, për rastin në shqyrtim, çelësi publik e mund të vendoset në mënyrë arbitrare. Në të vërtetë, le e=2, 4, 7, 9, 17, 111 Pastaj:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

Një përfundim i thjeshtë rrjedh nga shembulli i konsideruar. Në të vërtetë, zgjedhja e parametrave për procesin e kriptimit duhet të trajtohet me shumë kujdes dhe duhet të kryhet një analizë e plotë paraprake e parametrave të tillë. Si ta bëni këtë është një çështje më vete dhe nuk konsiderohet brenda fushëveprimit të kësaj pune.

Më në fund, ka ardhur koha për të filluar përshkrimin e kriptosistemit RSA. Përveç shpjegimit se si funksionon, duhet të diskutojmë në detaje sigurinë e tij; me fjalë të tjera, pse është kaq e vështirë të thyesh një mesazh të koduar me kriptosistemin RSA?

§ 12.1. Rreth fillimit dhe fundit

Për të zbatuar një sistem të enkriptimit RSA me një përdorues, ju duhet të zgjidhni dy numra të thjeshtë p dhe q dhe të llogarisni produktin e tyre. Në § 12.5 diskutojmë në detaje metodën për zgjedhjen e numrave kryesorë dhe se si kjo zgjedhje lidhet me besueshmërinë e sistemit.

Një mesazh (i cili mund të konsiderohet një numër i plotë) kodohet duke e ngritur atë në një modul fuqie. Prandaj, së pari duhet të gjejmë një mënyrë për të paraqitur tekstin e mesazhit si një listë e klasave të modulit procesi i enkriptimit, por vetëm përgatitja e mesazhit në mënyrë që ai të mund të kodohet.

Për thjeshtësi, le të supozojmë se teksti i mesazhit përmban vetëm fjalë të shkruara me shkronja të mëdha. Pra, mesazhi është në fund të fundit një sekuencë shkronjash dhe hapësirash. Hapi i parë është të zëvendësoni secilën shkronjë të mesazhit me një numër që zgjidhet nga tabela e mëposhtme:

(shih skanimin)

Hapësira ndërmjet fjalëve zëvendësohet me numrin 99. Pasi të kemi bërë këtë procedurë, do të marrim një numër, ndoshta shumë të madh nëse mesazhi ishte i gjatë. Megjithatë, ky nuk është numri përfundimtar për të cilin ne po përpiqemi, por vetëm një grup i klasave të modulit Dhe tani ne duhet të ndajmë paraqitjen numerike të mesazhit në copa, secila prej të cilave është një numër natyror që nuk e kalon. Këto pjesë zakonisht quhen. blloqe mesazhesh.

Për shembull, përfaqësimi numerik i motos "NJIH VETEN" duket kështu:

Duke zgjedhur ato të thjeshta, marrim produktin. Prandaj, paraqitja numerike e mesazhit të shkruar më sipër duhet të ndahet në blloqe më të vogla se 23,393.

Sigurisht, zgjedhja e blloqeve nuk është e paqartë, por nuk është as plotësisht arbitrare. Për shembull, për të shmangur paqartësitë në skenë

deshifrimi nuk duhet të nxjerrë në pah blloqet që fillojnë me zero.

Kur deshifroni një mesazh të koduar me sistemin e enkriptimit RSA, merret një sekuencë blloqesh. Më pas ato lidhen së bashku për të prodhuar një paraqitje numerike të mesazhit. Dhe vetëm pasi të keni zëvendësuar numrat me shkronja në përputhje me tabelën e mësipërme, do të jetë e mundur të lexoni mesazhin origjinal.

Ju lutemi vini re se çdo shkronjë në tabelë është e koduar me një numër dyshifror. Kjo është bërë për të parandaluar konfuzionin. Supozoni se i kemi numëruar shkronjat sipas radhës, duke filluar me 1, d.m.th. A korrespondon me 1, B me 2, e kështu me radhë. Në këtë rast, nuk do të mund të themi me siguri nëse blloku 12 përfaqëson një palë shkronja apo vetëm një shkronjë, shkronjën e dymbëdhjetë të alfabetit. Natyrisht, për paraqitjen numerike të një mesazhi, mund të përdorni çdo korrespondencë një-për-një midis shkronjave dhe numrave, për shembull, kodimi - në të cilin përkthimi i mesazhit në formë dixhitale kryhet automatikisht nga një kompjuter.

§ 12.2. Kriptimi dhe deshifrimi

Një mesazh i përgatitur për enkriptim duke përdorur metodën e § 12.1 përbëhet nga një sekuencë blloqesh, secila prej të cilave është një numër më i vogël se Tani le të diskutojmë se si çdo bllok është i koduar. Për ta bërë këtë, ne kemi nevojë për një numër të barabartë me prodhimin e numrave të thjeshtë dhe një numër natyror, modul i kthyeshëm, d.m.th. numër që plotëson kushtin

Kujtojmë se nga p dhe q e njohura numri mund të llogaritet lehtësisht. Vërtet,

Çifti quhet çelësi publik, ose kodues, i kriptosistemit RSA që po përshkruajmë. Le të bllokojë mesazhin, domethënë një numër të plotë që plotëson pabarazinë Ne do të përdorim simbolin për të treguar bllokun e mesazhit të koduar që korrespondon me Ai llogaritet sipas rregullit të mëposhtëm:

Vini re se çdo bllok mesazhesh është i koduar veçmas. Prandaj, një mesazh i koduar në të vërtetë përbëhet nga blloqe të veçanta të koduara. Për më tepër, ne nuk mund t'i kombinojmë këto blloqe në një numër të madh, pasi kjo do ta bëjë të pamundur dekriptimin e mesazhit. Së shpejti do ta shohim arsyen për këtë.

Le të kthehemi te shembulli që filluam të shqyrtojmë në paragrafin e parë. Ne e kemi fiksuar kështu që Tani duhet të zgjedhim një numër Kujtojmë që duhet të jetë i njëkohshëm me Numri më i vogël i thjeshtë që nuk pjesëton 23088 është i barabartë me 5. Le të vendosim Për të koduar bllokun e parë të mesazhit nga § 12.1, kemi për të përcaktuar zbritjen e numrit 25245 moduli 23393. Me përdorimin e një programi llogaritës simbolik (ose një kalkulator, nëse keni durim) marrim se zbritja e kërkuar është 22,752 Pra, mesazhi i koduar përfaqësohet nga sekuenca e mëposhtme e blloqeve :

Le të shohim se si deshifrohen blloqet e një mesazhi të koduar. Për të filluar deshifrimin, duhet të njohim elementin e anasjelltë të modulit. I fundit prej tyre është një numër natyror, të cilin do ta shënojmë me Çifti quhet çelësi sekret ose dekodues i sistemit të enkriptimit RSA. Nëse a është një bllok i një mesazhi të koduar, atëherë deshifrimi i tij përkatës

Rezultati i operacionit është:

Para se t'i kthehemi shembullit, nevojiten disa komente. Së pari, është shumë e lehtë të llogaritet nëse e dini në të vërtetë, çelësi sekret përcaktohet duke përdorur algoritmin e zgjeruar Euklidian. Së dyti, nëse blloku është mesazhi origjinal, atëherë ne kemi të drejtë të presim barazi. Me fjalë të tjera, kur deshifrojmë një bllok të një mesazhi të koduar, shpresojmë të zbulojmë bllokun përkatës të atij origjinal. Fakti që do të jetë kështu nuk rrjedh drejtpërdrejt nga algoritmi i përshkruar më sipër, por ne do të diskutojmë gjithçka në detaje në paragrafin tjetër.

Më në fund, siç argumentuam në hyrje dhe gjatë gjithë librit, për të thyer një kriptosistem RSA duhet ta faktorizoni atë, sepse ju duhet të dini të deshifroni mesazhin. Megjithatë, pasi funksionimi i sistemit të përshkruhet në detaje, është e qartë se pohimi i fundit nuk është plotësisht i saktë. Për të lexuar enkriptimin, përveç vetë elementit, duhet të dini vetëm modulin e anasjelltë të elementit Prandaj, për të hakuar sistemin, mjafton të llogaritni me të njohurit Rezulton se kjo llogaritje është e barabartë me faktorizimin e një numri. , siç do të shohim në § 12.4.

Në shembullin në diskutim, ne aplikojmë algoritmin e zgjeruar Euklidian për numrat dhe 5 për të përcaktuar.

(shih skanimin)

Kështu, pra, anasjellta e 5 modulit do të ishte -9235 dhe

Numri më i vogël natyror i krahasueshëm me modulin -9235 Pra, për të deshifruar një bllok të një mesazhi të koduar, duhet ta ngremë atë në fuqinë 13,853, moduli 23,393 Në shembullin tonë, blloku i parë i koduar është 22,752 75213853 modulo 23,393 , marrim Vini re se edhe me numra kaq të vegjël, kërkesat për funksionimin e kriptosistemit RSA tejkalojnë aftësitë e shumicës së kalkulatorëve të xhepit.

§ 12.3. Pse funksionon?

Siç u përmend më herët, hapat e përshkruar më sipër çojnë në një kriptosistem funksional vetëm nëse deshifrimi i çdo blloku të mesazhit të koduar do të rivendosë bllokun përkatës të atij origjinal. Le të supozojmë se kemi të bëjmë me një sistem RSA që ka një çelës publik dhe një çelës privat. Duke përdorur shënimin e § 12.2, duhet të tregojmë se për çdo numër të plotë që plotëson pabarazinë që ka.

Në fakt, mjafton për ta vërtetuar këtë

Në të vërtetë, të dy numrat e plotë 6 dhe jonegativë janë më të vegjël. Prandaj, ata janë të krahasueshëm në vlerë absolute nëse dhe vetëm nëse janë të barabartë. Kjo, në veçanti, shpjegon pse ne e ndajmë paraqitjen numerike të mesazhit në blloqe më të vogla

Mesazhi i koduar duhet të shkruhet veçmas: përndryshe arsyetimi ynë nuk do të funksionojë.

Nga recetat e kriptimit dhe deshifrimit rrjedh se

Meqenëse elementët janë reciprokisht të anasjelltë në modul, ekziston një k natyral i tillë që Për më tepër, sipas kushteve, numrat janë më të mëdhenj. Prandaj, duke zëvendësuar në vend të produktit në ekuacionin (3.1), marrim

Tani le të përdorim teoremën e Euler-it, e cila thotë se Prandaj, d.m.th.

dhe ne do ta kishim marrë plotësisht provën nëse nuk do të kishte hyrë në të një gabim i vogël.

Nëse rishikoni me kujdes arsyetimin tonë përsëri, do të vini re se ne nuk kemi marrë parasysh kushtet e teoremës së Euler-it. Në fakt, përpara se të aplikoni teoremën, është e nevojshme të siguroheni që numrat të jenë reciprokisht të thjeshtë. Kur ndani paraqitjen numerike të një mesazhi në blloqe, duhet të siguroheni që të gjitha blloqet që rezultojnë të jenë bashkëprimare për fat të mirë, kjo nuk është e nevojshme, sepse në fakt krahasimi bëhet për çdo bllok. Dhe gabimi nuk qëndron në rezultatin që duam të vërtetojmë, por vetëm në vetë prova. Qasja e saktë bazohet në arsyetimin e përdorur për të vërtetuar teoremën e Korceltit në Kapitullin 7.

Kujtoni se ku janë numra të thjeshtë të ndryshëm. Le të përcaktojmë mbetjet e një moduli të numrit Since

Llogaritjet për të dy numrat e thjeshtë janë të ngjashme, ne do ta përpunojmë vetëm rastin në detaje Pra, tashmë e kemi parë atë

për disa numra të plotë Prandaj,

Tani do të dëshironim të zbatonim teoremën e Fermatit, por ne kemi të drejtë ta bëjmë këtë vetëm nëse nuk ndahet Le të plotësohet kjo kërkesë. Pastaj e marrim atë

Duke zëvendësuar teoremën e Fermatit me teoremën e Euler-it, nuk e zgjidhëm problemin që u ngrit: krahasimi vlen vetëm për disa, por jo për të gjitha blloqet. Megjithatë, tani blloqet për të cilat arsyetimi nuk funksionon duhet të ndahen me Further, nëse ndan atëherë të dyja 6 dhe janë të krahasueshme me 0 në modul dhe për këtë arsye të krahasueshme me njëri-tjetrin. Pra, krahasimi që provohet është i vlefshëm edhe në këtë rast. Prandaj, krahasimi është i vërtetë për çdo numër të plotë. mund të kishte përdorur arsyetim të ngjashëm kur zbatohej teorema e Euler-it në të vërtetë, pabarazia nuk do të thotë krahasim sepse numri është i përbërë.

Pra, ne kemi vërtetuar se Krahasimi është vërtetuar në mënyrë të ngjashme. Me fjalë të tjera, pjesëton të dy me dhe Por janë numra të thjeshtë, kështu që lema nga § 3.6 na garanton që e ndan A-në pasi kemi për çdo numër të plotë. vumë në dukje në fillim të paragrafit, kjo është e mjaftueshme për të vërtetuar barazinë pasi të dyja pjesët e tij janë numra të plotë jo-negativë, për ta përmbledhur, mund të themi se

algoritmi i paragrafit të mëparshëm çon në një kriptosistem praktik. Tani duhet të siguroheni që është i besueshëm.

§ 12.4. Pse sistemi është i besueshëm?

Kujtoni se RSA është një sistem enkriptimi me një çelës publik që përbëhet nga prodhimi i numrave të thjeshtë të ndryshëm dhe një numër natyror i kthyeshëm modulues, le të shohim me kujdes se çfarë mund të bëhet për të thyer RSA nëse gjithçka që dihet është një çift

Për të deshifruar një bllok të koduar me RSA, ne duhet të dimë inversin e modulit k. Problemi është se praktikisht e vetmja mënyrë e njohur për ta bërë këtë bazohet në aplikimin e algoritmit të zgjeruar Euklidian në Megjithatë, për të llogaritur duke përdorur formulën nga § 9.4. ne duhet të dimë se çfarë konfirmon deklaratën origjinale: Thyerja e RSA kërkon faktorizim. Dhe meqenëse vështirësitë e dekompozimit janë thelbësore, sistemi RSA është i sigurt.

Sigurisht, mund të supozohet se një ditë dikush do të zbulojë një algoritëm që llogarit pa informacion për faktorët e një numri Çfarë, për shembull, do të ndodhë nëse dikush del me një mënyrë efektive për të përcaktuar drejtpërdrejt në fakt, kjo është e drejtë një metodë e maskuar e zgjerimit Më saktë, nëse

janë të njohura, atëherë ne mund të llogarisim lehtësisht Në të vërtetë,

pra dihet shuma e pjesëtuesve të thjeshtë të kërkuar. Me tutje,

prandaj dihet edhe dallimi. Tani, duke zgjidhur një sistem të thjeshtë ekuacionesh lineare, ne mund të gjejmë lehtësisht faktorizimin.

Kjo do të thotë që algoritmi që llogarit në fakt e zbërthen numrin në faktorë, pra është një zog i një pendë. Por është shumë herët për t'u qetësuar. Ju mund të shkoni më tej në fantazitë tuaja dhe të supozoni se dikush ka shpikur një algoritëm që përcakton drejtpërdrejt me Por Pra, nëse e dimë, atëherë ne e dimë numrin që është një shumëfish i tij Rezulton se një informacion i tillë është gjithashtu i mjaftueshëm për zbërthimin. Një algoritëm probabilistik që çon në një zbërthim të tillë mund të gjendet V. Ushtrimi 7 tregon një algoritëm të ngjashëm (por më të thjeshtë) zbërthimi nën supozimin se kriptosistemi Rabin mund të prishet. Do t'ju japë një ide të algoritmit probabilist nga .

Mbetet mundësia e fundit për hakerim: një përpjekje për të rikthyer bllokun drejtpërdrejt me mbetje të modulit, nëse është mjaft i madh, atëherë një kërkim sistematik i të gjithë kandidatëve të mundshëm për kërkimin është e vetmja rrugëdalje. Askush nuk ka dalë ende me ndonjë gjë më të mirë. Ne kemi renditur argumentet kryesore që shpjegojnë pse thyerja e kriptosistemit RSA konsiderohet e barabartë me faktorizimin, megjithëse nuk ka ende prova rigoroze të kësaj deklarate.

§ 12.5. Përzgjedhja e të thjeshtave

Nga diskutimi i mëparshëm rezulton se për sigurinë e kriptosistemit RSA është e rëndësishme të zgjidhni numrat e duhur të thjeshtë. Megjithatë, nuk mjafton të zgjidhni ato të mëdha, në të vërtetë, edhe nëse p dhe q janë të mëdha, por ndryshimi është i vogël, produkti i tyre mund të faktorizohet lehtësisht duke përdorur algoritmin e Fermat-it (shih § 3.4).

Kjo nuk është një bisedë kot. Në vitin 1995, dy studentë në një universitet amerikan thyen një version publik të RSA. Kjo u bë e mundur për shkak të zgjedhjes së dobët të faktorëve kryesorë të sistemit.

Nga ana tjetër, RSA është përdorur për një kohë të gjatë dhe, nëse faktorët kryesorë zgjidhen me kujdes, sistemi në fakt rezulton të jetë mjaft i besueshëm. Kështu, çdo programues i enkriptimit RSA ka nevojë për një metodë efektive për të zgjedhur me sukses numrat e thjeshtë.

Supozoni se duam të krijojmë një kriptosistem RSA me një çelës publik në të cilin numri i plotë ka rreth shifra. Së pari, le të zgjedhim një numër të thjeshtë, numri i karaktereve të të cilit qëndron midis, le ta marrim afër Aktualisht, madhësia e çelësit të rekomanduar për përdorim personal është 768 bit, d.m.th. duhet të jetë afërsisht 231 shifra. Për të ndërtuar një numër të tillë, na duhen dy të thjeshtë, të themi, me 104 dhe 127 shifra. Ju lutemi vini re se numrat e parë të zgjedhur në këtë mënyrë janë mjaft larg njëri-tjetrit, d.m.th. Përdorimi i algoritmit të Fermat për zbërthimin në këtë situatë është jopraktik. Përveç kësaj, ne duhet të sigurohemi që jo vetëm faktorët e vegjël, por edhe ata të mëdhenj të përfshihen në faktorizimin e numrave në faktorë të thjeshtë. Në të vërtetë, përndryshe, numri bëhet pre e lehtë për disa algoritme të njohura të dekompozimit (shih). Le të shqyrtojmë tani një metodë me të cilën gjenden numrat e thjeshtë që plotësojnë kushtet e listuara.

Së pari na duhet një rezultat i thjeshtë në lidhje me shpërndarjen e numrave të thjeshtë. Le të kujtojmë se çfarë tregon numrin e numrave të thjeshtë që nuk e kalon x. Duke pasur parasysh teoremën e numrave të thjeshtë, shohim se për x të madh numri është afërsisht i barabartë me ku është logaritmi natyror

mbi bazën (shih § 4.5). Le të jetë një numër shumë i madh, një numër pozitiv. Ne duam të vlerësojmë numrin e numrave të thjeshtë që ndodhen ndërmjet dhe të vlerësojmë ndryshimin Falë teoremës së numrave të thjeshtë dhe vetive të logaritmit, diferenca është afërsisht e barabartë me

Duke supozuar se është shumë i vogël, mund të supozojmë se vlera është e barabartë me 0 dhe të marrim një vlerësim të arsyeshëm të diferencës Pra, numri i numrave të thjeshtë të përfshirë është afërsisht i barabartë sa më i vogël Për një hyrje më të detajuar të një vlerësimi të tillë, shih ([D. 10]).

Supozoni se duhet të zgjedhim një numër të thjeshtë në afërsi të një numri të plotë x. Për definicion, do të supozojmë se x është i rendit , dhe ne jemi duke kërkuar për një të thjeshtë në intervalin nga x në Do të ishte e dobishme të dimë paraprakisht se sa numra të thjeshtë janë në këtë interval. Për të vlerësuar numrin e numrave të thjeshtë, mund të përdorni rezultatin e sapo marrë. Në shembullin tonë, vlera është e një rendi shumë të vogël të madhësisë: Prandaj, duke përdorur formulën e shkruar më sipër, arrijmë në përfundimin se intervali ndërmjet qëndron afërsisht

numrat e thjeshtë. Në fund të paragrafit të dytë të kapitullit 11, ne formuluam një strategji të krijuar për të vërtetuar parësinë e një numri të caktuar tek ai përbëhet nga tre hapa.