Algoritmi i kriptimit rsa 3072. Nënshkrimi dixhital elektronik, algoritmi RSA

Elektronike nënshkrim dixhital(EDS) është një dokument elektronik i kërkuar për të vërtetuar burimin e të dhënave dhe për të mbrojtur këtë dokument elektronik nga falsifikimi.

Skema e përgjithshme

Një skemë e nënshkrimit elektronik zakonisht përfshin:

• algoritëm për gjenerimin e çifteve të çelësave të përdoruesit;
• funksioni i llogaritjes së nënshkrimit;
• funksioni i verifikimit të nënshkrimit.

Funksioni i llogaritjes së nënshkrimit bazuar në dokument dhe çelësi privat i përdoruesit llogarit nënshkrimin aktual. Në varësi të algoritmit, funksioni për llogaritjen e nënshkrimit mund të jetë përcaktues ose probabilistik. Funksionet përcaktuese llogaritin gjithmonë të njëjtin nënshkrim nga e njëjta hyrje. Funksionet e probabilitetit futin një element të rastësisë në nënshkrim, i cili rrit fuqinë kriptografike të algoritmeve EDS. Sidoqoftë, skemat probabilistike kërkojnë një burim të besueshëm të rastësisë (ose një gjenerues zhurme harduerike ose një gjenerues bitesh të rastësishëm kriptografikisht të besueshëm), gjë që e ndërlikon zbatimin.

Aktualisht, skemat deterministike praktikisht nuk përdoren.

Funksioni i verifikimit të nënshkrimit kontrollon nëse nënshkrimi i dhënë përputhet ky dokument dhe çelësi publik i përdoruesit. Çelësi publik i përdoruesit është i disponueshëm për të gjithë, kështu që çdokush mund të verifikojë nënshkrimin në këtë dokument.

Meqenëse dokumentet që do të nënshkruhen janë me gjatësi të ndryshueshme (dhe mjaft të gjatë), në skemat EDS, nënshkrimi shpesh vendoset jo në vetë dokumentin, por në hash -in e tij. Hashi llogaritet duke përdorur funksione kriptografike të hash -it për të siguruar që ndryshimet e dokumentit të zbulohen kur nënshkrimi të verifikohet. Funksionet Hash nuk janë pjesë e algoritmit EDS, kështu që çdo funksion hash i besueshëm mund të përdoret në skemë.

Siguria

Nënshkrimi dixhital siguron:

• Identiteti i burimit të dokumentit. Në varësi të detajeve të përcaktimit të dokumentit, mund të nënshkruhen fusha të tilla si "autori", "ndryshimet e bëra", "vula kohore", etj.
• Mbrojtja nga ndryshimet e dokumenteve. Çdo ndryshim aksidental ose i qëllimshëm në dokument (ose nënshkrim) do të ndryshojë hash -in, prandaj, nënshkrimi do të bëhet i pavlefshëm.
• Pamundësia e refuzimit të autorësisë. Meqenëse mund të krijoni një nënshkrim të saktë vetëm nëse e dini çelësin privat, dhe ai është i njohur vetëm për pronarin, pronari nuk mund të refuzojë nënshkrimin e tij në dokument.

Kërcënimet e mëposhtme të nënshkrimit dixhital janë të mundshme:

• Një sulmues mund të përpiqet të falsifikojë një nënshkrim për një dokument të zgjedhur prej tij.
• Një sulmues mund të përpiqet të krahasojë një dokument me një nënshkrim të caktuar në mënyrë që nënshkrimi të përputhet me të.
• Një sulmues mund të përpiqet të falsifikojë një nënshkrim për një dokument.

Kur përdorni një funksion hash të besueshëm, është e vështirë të llogaritni krijimin e një dokumenti të rremë me të njëjtin hash si ai i vërtetë. Sidoqoftë, këto kërcënime mund të realizohen për shkak të dobësive të algoritmeve specifike të hash, nënshkrimeve ose gabimeve në zbatimin e tyre.

Sidoqoftë, kërcënime të tilla ndaj sistemeve të nënshkrimit dixhital janë ende të mundshme:

• Një sulmues që vodhi një çelës privat mund të nënshkruajë çdo dokument në emër të pronarit të çelësit.
• Një sulmues mund të mashtrojë pronarin për të nënshkruar një dokument, për shembull, duke përdorur protokollin e nënshkrimit të verbër.
• Një sulmues mund të zëvendësojë çelësin publik të pronarit (shiko menaxhimin kryesor) me të tijin, duke e imituar atë.

Algoritmet EDS

• Standardet amerikane për nënshkrimin elektronik dixhital: DSA, ECDSA

• Standardet ruse për nënshkrimin dixhital elektronik: GOST R 34.10-94 (aktualisht nuk është e vlefshme), GOST R 34.10-2001
• Standardi ukrainas për nënshkrimin elektronik dixhital: DSTU 4145-2002
• Standardi PKCS # 1 përshkruan, në veçanti, një skemë elektronike të nënshkrimit dixhital të bazuar në algoritmin RSA

Menaxhimi kryesor

Një problem i rëndësishëm në të gjithë kriptografinë e çelësit publik, përfshirë sistemet EDS, është menaxhimi i çelësave publikë. Isshtë e nevojshme të sigurohet qasja e çdo përdoruesi në çelësin publik të vërtetë të çdo përdoruesi tjetër, për të mbrojtur këto çelësa nga zëvendësimi nga një ndërhyrës, dhe gjithashtu për të organizuar heqjen e çelësit në rast të kompromisit të tij.

Problemi i mbrojtjes së çelësave nga zëvendësimi zgjidhet me ndihmën e certifikatave. Certifikata ju lejon të verifikoni të dhënat e përfshira në të për pronarin dhe çelësin e tij publik me nënshkrimin e një personi të besuar. Sistemet e centralizuara të certifikatave (si PKI) përdorin autoritete certifikimi të mbështetura nga organizata të besuara. Në sistemet e decentralizuara (për shembull PGP), një rrjet besimi ndërtohet nga secili përdorues duke nënshkruar certifikata të miqve dhe njerëzve të besuar.

Qendrat e Shpërndarjes së Certifikatave janë përgjegjëse për menaxhimin kryesor. Duke kontaktuar një qendër të tillë, përdoruesi mund të marrë një certifikatë të çdo përdoruesi, dhe gjithashtu të kontrollojë nëse ky ose ai çelës publik është revokuar.

Përshkrimi i algoritmit RSA

RSA- algoritëm kriptografik me çelës publik. RSA ishte e para e këtij lloji, e përshtatshme për kriptim dhe nënshkrim dixhital. Algoritmi përdoret në një numër të madh të aplikacioneve kriptografike.

Histori

Matematikani britanik Clifford Cocks, i cili punoi për Qendrën e Komunikimeve të Qeverisë në Mbretërinë e Bashkuar (GCHQ), përshkroi një sistem të ngjashëm në 1973 në dokumentet e brendshme të qendrës, por kjo punë nuk u zbulua deri në vitin 1977 dhe Rivest, Shamir dhe Adleman zhvilluan RSA në mënyrë të pavarur nga puna Cox.

Në 1983, MIT iu dha patenta amerikane 4,405,829, e cila skadoi më 21 shtator 2000.

Përshkrimi i algoritmit

Siguria e algoritmit RSA bazohet në vështirësinë e problemit të faktorizimit. Algoritmi përdor dy çelësa - publik dhe privat, së bashku çelësat publik dhe korrespondues privat formojnë një riparim çelësash. Çelësi publik nuk ka nevojë të mbahet sekret; përdoret për të kriptuar të dhënat. Nëse mesazhi ishte i koduar me një çelës publik, atëherë ai mund të deshifrohet vetëm me çelësin sekret përkatës.

Gjenerimi i çelësave

Për të krijuar një palë çelësash, kryhen hapat e mëposhtëm:

1. Zgjidhen dy prima të mëdhenj dhe

2. Produkti i tyre llogaritet

3. Funksioni Euler llogaritet

4. Një numër i plotë zgjidhet i tillë që dhe coprime me

5. Duke përdorur algoritmin e zgjeruar Euklidian, një numër gjendet i tillë që

Numër dhe përdoret si tekst i koduar. Për të deshifruar, duhet të llogaritni

Easyshtë e lehtë të sigurohemi që kur të deshifrojmë të rivendosim mesazhin origjinal:

Nga gjendja

vijon që

për disa numra të plotë, prandaj

Sipas teoremës së Eulerit:

Disa veçori të algoritmit

Gjenerimi i numrave të thjeshtë

Për të gjetur dy numra të mëdhenj dhe, kur krijoni një çelës, zakonisht përdoren teste të thjeshtësisë probabilistike të numrave, të cilat ju lejojnë të identifikoni dhe hidhni shpejt numrat e përbërë.

· Me një vlerë të vogël të një treguesi të hapur (për shembull), një situatë është e mundur kur rezulton se. Pastaj, dhe ndërhyrësi mund të rikuperojë me lehtësi mesazhin origjinal duke llogaritur rrënjën e shkallës nga.

· Meqenëse RSA është një algoritëm determinist, d.m.th. nuk përdor vlera të rastësishme në proces, atëherë sulmuesi mund të përdorë sulmin me tekstin e zgjedhur të qartë.

Për të zgjidhur problemet e listuara, mesazhet plotësohen para çdo kriptimi me një vlerë të rastësishme - kripë. Mbushja kryhet në mënyrë të tillë që të sigurohet që, dhe. Për më tepër, meqenëse mesazhi plotësohet me të dhëna të rastësishme, kur kriptojmë të njëjtin tekst të thjeshtë, ne do të marrim një vlerë të ndryshme të kodit të koduar çdo herë, gjë që e bën të pamundur një sulm me tekstin e thjeshtë të zgjedhur.

Zgjedhja e vlerës së një treguesi të hapur

RSA është dukshëm më i ngadalshëm se algoritmet simetrike. Për të rritur shpejtësinë e kriptimit, eksponenti i hapur zgjidhet i vogël, zakonisht 3, 17 ose 65537. Këta numra në formë binare përmbajnë vetëm dy njësi, gjë që zvogëlon numrin e operacioneve të shumëzimit të kërkuara kur ngrihet në një fuqi. Për shembull, për të rritur një numër në fuqinë 17, ju duhet vetëm të kryeni 5 operacione të shumëzimit:

duhet të jetë mjaft e madhe. Në 1990, Michael J. Wiener tregoi se nëse zgjidhni të vogla, atëherë rezulton të jetë mjaft e madhe dhe nuk ka asnjë problem.

Gjatësia e çelësit

Numri n duhet të jetë së paku 512 bit në madhësi. Aktualisht, sistemi i kriptimit i bazuar në RSA konsiderohet i besueshëm duke filluar nga madhësia N prej 1024 bit.

Aplikimi RSA

RSA përdoret për mbrojtjen e softuerit dhe skemat e nënshkrimit dixhital. Përdoret gjithashtu në sistem i hapur kriptimi PGP.

Për shkak të shpejtësisë së ulët të kriptimit (rreth 30 kbps me një çelës 512-bit në një procesor 2 GHz), mesazhet zakonisht kodohen duke përdorur algoritme simetrike më efikase me një çelës të rastit ( çelësi i sesionit), dhe vetëm ky çelës është i koduar duke përdorur RSA.

II Zbatimi

Si shembull, u zbatua një program për nënshkrimin dixhital të skedarëve dhe verifikimin e nënshkrimeve. U përdorën algoritmi RSA dhe certifikatat X.509. Certifikata e përdoruesit merret nga dyqani i certifikatave të Windows.

Nënshkrimet dixhitale ruhen në skedar xml Me emër<имя исходного файла>.sig.xml

Fragmente të kodit

klasë publike Nënshkrimi

certifikatë private X509Certificate2;

data private DataTime;

bajt privat i nënshkruarHash;

Certifikata publike X509Certifikata2

merrni (certifikatë kthimi;)

vendosur (certifikatë = vlerë;)

publike DataTime Data

merrni (data e kthimit;)

vendosur (data = vlera;)

shenjë e zbrazëtisë publike (hyrja e vargut, X509Certificate2 certifikatë)

kjo.vërtetim = certifikatë e re X5092 (certifikatë);

data = DataTime.Now;

firmosurHash = ((RSACryptoServiceProvider) cert.PrivateKey) .SignData (Utils.StringToBytes (stringToEncrypt), MD5CryptoServiceProvider i ri ());

bool publik IsValid (futja e vargut)

string stringToEncrypt = input + date.Ticks;

certifikatë kthimi ((RSACryptoServiceProvider ).PublicKey.Key). VerifyData (Utils.StringToBytes (stringToEncrypt), MD5CryptoServiceProvider i ri (), nënshkruarHash);

bajt publik SignedHash

merrni (kthehu nënshkruarHash;)

vendosur (nënshkruarHash = vlera;)

e pavlefshme DisplaySignatureList ()

FileSignatures fileSignatures = ReadSignatures (GetSignaturesFileName (fileNameTextBox.Text));

signatureListTextBox.Text = "";

foreach (Nënshkruesi nënshkrues në dosjeNënshkrimet. Shenjat)

string string = "";

rresht + = nënshkrues. Certifikatë. Subjekt;

rresht + = "" + nënshkrues.Date.ToString ();

string hash = GetFileHash (fileNameTextBox.Text);

bool valid = nënshkrues.IsValid (hash);

rresht = "v" + rresht;

rresht = "x" + rresht;

signatureListTextBox.Text + = rresht + "\ r \ n";

III. Letërsi

1. S. Burnet, S. Payne: Kriptografia. Udhëzuesi Zyrtar i Sigurisë RSA - M. Binom, 2002
2. V. Zima: Siguria e teknologjive të rrjetit global - "BHV -Petersburg", 2003
3. Kriptografia moderne Venbo Mao: Teoria dhe Praktika = Kriptografia Moderne: Teori dhe Praktikë. -M.: "Williams", 2005.-S. 768. ISBN 0-13-066943-1
4. Nils Ferguson, Bruce Schneier Kriptografia Praktike: Projektimi dhe Zbatimi i Sistemeve të Siguruara Kriptografike. -M.: "Dialektika", 2004.-S. 432. ISBN 0-471-22357-3
5. Schneier, Bruce. Kriptografia e aplikuar. Protokollet, algoritmet, tekstet burimore në gjuhën C - M.: Shtëpia botuese TRIUMPH, 2002 - 816s .: Ill. ISBN 5-89392-055-4

Jo të gjithë përdoruesit janë personalë teknologji kompjuterike e di dhe e kupton se çfarë është kriptimi RSA dhe habitesh me tingullin e këtij termi. Por nuk ka asgjë të komplikuar në këtë koncept. Kriptimi RSA është vetëm një kriptosistem që ju lejon të përdorni të gjitha të dhënat elektronike të krijuara në teknologjinë kompjuterike në një mënyrë të sigurt. Ky nuk është deshifrim i të dhënave, kur skedarët nuk mund të lexohen pa ditur një kod të caktuar. Kriptimi RSA supozon se çelësat janë publikë.

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

Kush e krijoi sistemin e kriptimit RSA?

Algoritmi i kriptimit RSA u krijua në 1977, krijuesit e tij janë shkencëtarët Rivest, Shamir, Adleman, shkurtimi i shkronjave fillestare të mbiemrave është termi RSA. Algoritmi i mëparshëm u përpunua nga Clifford Cox, një matematikan nga Anglia i cili punoi për shërbimet e inteligjencës të vendit. Në 1973, ai arriti të krijojë një sistem ekuivalent, por ai u përdor ekskluzivisht nga persona të klasifikuar, dhe metoda nuk u përhap në nivel përdoruesit e zakonshëm pajisje kompjuterike personale.

Si funksionon kriptimi RSA?

Përdoruesi i sistemit së pari 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 të fshehtë. Për të lexuar, për shembull, një mesazh me email, thjesht duhet të përdorni çelësin publik të dokumentit, por nëse çelësi është i gjatë, atëherë ka vështirësi në qasjen 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 ngadalshëm, 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 praktikisht nuk përdoret nga shkencëtarët e zakonshëm të kompjuterave?

Çështja është se ajo gjeti aplikimin e saj në transmetimin e koduar të çelësave të përbashkët për një çelës simetrik të kriptimit, i cili është krijuar për kriptim masiv dhe deshifrim me shpejtësi të madhe.

Kriptosistemi modern i çelësave asimetrik u shfaq falë veprave të Diffie dhe Hellman. Ata e zhvilluan konceptin në 1976 dhe e paraqitën atë në publik si regjistrime dixhitale. Ata arritën të krijojnë një çelës të përbashkët bazuar në parimin e ekspozimit të një numri të caktuar modulo një numër të thjeshtë. Por parimi i tyre mbeti i varur në ajër, pasi në atë kohë vetë parimet e faktorizimit nuk ishin studiuar ende mirë.

Rivest, Adim Shamir, Adleman nuk u ndalën në atë që kishin arritur më parë, dhe përpunuan tërësisht mekanizmin e një funksioni të njëanshëm, i cili nuk është aq i lehtë për tu deshifruar. Rivest dhe Shamir punuan drejtpërdrejt në vetë funksionet, ndërsa Adleman kërkoi dobësi në algoritmet që krijoheshin. Në fund, ata arritën të krijojnë sistemin çelës RSM asimetrik.

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

Aktualisht, shumë kompani përdorin një element të tillë elektronik si një nënshkrim dixhital në punën e tyre. Dokumentet elektronike të krijuara që përmbajnë një të ashtuquajtur nënshkrim dixhital janë dokumente zyrtare që njihen ligjërisht. Një nënshkrim dixhital elektronik krijohet kur të dhënat ndryshohen në mënyrë kriptografike.

Kjo alternativë ndaj nënshkrimit të zakonshëm bën të mundur bërjen e një dokumenti konfidencial, sigurimin e integritetit të tij dhe gjithmonë të ketë informacion në lidhje me krijuesin dhe pronarin e tij.

Nënshkrimi elektronik është i lidhur ngushtë me kriptimin RSA në shqyrtim. 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 që personat e paautorizuar të kenë qasje në informacion.

Kështu, çelësi publik ju lejon të përdorni një dokument me 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 dokumente nga sytë kuriozë, klasifikoni ato, por me aftësinë për të fituar qasje në to në kohën e duhur.

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

Kriptimi RSA funksionon në katër hapa:
gjenerimi i çelësit;
shpërndarja e çelësave;
kriptimi i çelësave;
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ë koduar mesazhet. Këto të dhëna elektronike mund të deshifrohen duke përdorur një çelës privat. Kur krijoni çelësa publikë, zgjidhen numra të rastit dhe të barabartë, por të ndryshëm në gjatësi, për ta bërë faktorizimin më të vështirë.

Numrat identikë gjenden duke kryer testimin e thjeshtësisë. Kështu, kriptimi gradualisht është bërë më i sofistikuar. Nga se përbëhet një çelës publik? Dhe përbëhet nga një modul i rregullt dhe një të ashtuquajtur ekspozues 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

Megjithë parimin e menduar mirë të kriptimit, ai mund të prishet lehtë. Kjo mund të bëhet nëse numra të vegjël janë përdorur për të krijuar çelësat; mund ta zbuloni çelësin me një përzgjedhje të thjeshtë të numrave të plotë të thjeshtë.

Kriptimi RSA në vetvete është një algoritëm me shanse zero, duke e bërë të lehtë për mashtruesit rrjet kompjuterik prish mekanizmin përcaktues duke marrë tekstin e thjeshtë të sulmeve dos, të cilat kontrollojnë nëse tekstet e nisura janë vazhdimisht të barabarta me gjatësinë e çelësave të 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 të ruajtur të dhënat elektronike nga shkeljet e personave të padëshiruar. Përveç nëse, kur i shtohet serverëve më të avancuar, ai fiton veti të tilla.

Komponentë shtesë për të siguruar sigurinë e përdorimit të kriptimit RSA

Për të parandaluar mundësinë e prishjes së kriptimit të formatit RSA, programuesit vendosin në të një formë të strukturuar, të ashtuquajtur të mbushjes së rastësishme, kjo bëhet para kriptimit të vetë informacionit elektronik. Ky moment garanton që përmbajtja e dokumenteve elektronike nuk do t'i paraqitet të gjithëve dhe kush nuk është dembel, se informacioni konfidencial nuk do të jetë në gjendje të shihet kur aplikoni një mekanizëm të rastësishëm të përzgjedhjes së çelësave në dokumente.

Kriptimi RSA zbërthen numrat matematikorë në faktorë, por mekanizmi nuk është përsosur kurrë. Prandaj, për momentin, kriminelët në internet kanë mundësi dhe shumë zbrazëti për zgjedhjen e metodave për prishjen e kriptimit të të dhënave. Dhe është pikërisht mekanizmi kryesor i rimëkëmbjes së faktorit që ata arrijnë të bëjnë.

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

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

Megjithë rezultatin e ulët të sigurisë, kriptimi RSA në fjalë është i zbatueshëm në shumë industri. Especiallyshtë veçanërisht i 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 të përgjegjësisë.

Softueri Yafu mundëson kriptim automatik të të dhënave elektronike. Ky program ju lejon të gjeni shpejt të dhëna për krijimin e çelësave asimetrikë, duke respektuar rregullat e faktorizimit të besueshmërisë. Isshtë në përputhje me procesorë të tillë si SIQS, ECM, SNFS. Fillon përmes linja e komandës... Futja e kësaj komande në një varg mund të zvogëlojë kohën e kërkimit të të dhënave për të krijuar çelësa në kohë.

Një përdorues i zakonshëm i pajisjeve të kompjuterit personal nuk mund të përballojë këtë softuer. Për ta instaluar dhe konfiguruar atë, kërkohen njohuri të caktuara dhe kjo shpesh bëhet nga programuesit dhe specialistët e IT.

Kriptimi RSA është seriozisht i prekshëm, përkundër faktit se një numër i madh përdoret për të krijuar çelësa publikë dhe privatë, që arrijnë në disa mijëra bit në disqe.

Bedjamin Moody vërtetoi në 2009 se procesi i plasaritjes së çelësave publikë dhe privatë është i mundur. Mund të duhen dy ose më shumë vjet për këtë, por fakti mbetet se shumë sisteme kompjuterike në botë mund të jenë të rrezikuara nga hakimi.

Për shembull, ky specialist nuk kishte nevojë për ndonjë gjë të veçantë për të analizuar skriptet kryesore - kompjuter i rregullt përdorues dhe softuer GGNFS. Edhe praktika e disa të mijtave të çelësave të enkriptimit nuk mbron informacionin nga lënia e fushës konfidenciale dhe e paarritshme për përdoruesit e tjerë.

Thyerja e kriptimit RSA kërkon kohë, natyrisht. Shumë hakerave u duhen vite për të arritur rezultate pozitive. Këto janë shpesh perspektiva me pagesë të lartë që nxisin interesin për të vazhduar të gjejnë çelësin e duhur. Në shumicën e rasteve, çarja e gjatë e çelësit braktiset në kërkim të perspektivave më të thjeshta. Por kjo nuk do të thotë që askush nuk po përpiqet të krijojë një mekanizëm më të thjeshtuar të plasaritjes kryesore.

Mbrojtja kryesore kundër sulmeve ndërhyrës nga mashtruesit është krijimi i çelësave të mëdhenj dhe të gjatë prej më shumë se dy mijë copë. Tashmë janë të njohura raste të plasaritjes së çelësave nga njëqind në pesëqind bit të gjatë. Kështu që ju duhet ta mbani veshin tuaj të mprehtë. Nëse ekziston një mekanizëm për plasaritje të çelësave të shkurtër, puna ndoshta është në lëvizje të plotë diku në anën e keqbërësve për të goditur kombinimet më të gjata të kriptimit të të dhënave elektronike.

Përfundim

Bazuar në sa më sipër, kriptimi RSA është një metodë e sigurt për ruajtjen e konfidencialitetit të të dhënave elektronike, me kusht që të krijohen çelësa të gjatë dhe informativë të mëdhenj.

Difficultshtë e vështirë t'i zgjedhësh ato me dorë, prandaj, një i automatizuar softuer Yafu. Isshtë instaluar dhe konfiguruar nga profesionistë të IT. Punë e pavarur mund të prishet sistemi operativ kompjuter
Ky softuer është krijuar për të punuar së bashku me gjeneratën e sotme të procesorëve kompjuterikë me shumë bërthama.

Objektivat kryesore të sulmeve mashtruese janë kompanitë e mëdha industriale dhe financiare, prandaj, qarkullimi i tyre elektronik i dokumenteve nuk funksionon pa kriptim RSA. Nënshkrimet elektronike të dokumenteve gjithashtu i nënshtrohen kriptimit, dhe të njëjtat standarde sigurie zbatohen për të si për të dhënat e tjera të informacionit. Parimi - sa më i madh çelësi, aq më e vështirë është të plasësh dokumentin - duhet të jetë absolutisht i zbatueshëm për të gjitha të dhënat që nuk janë të destinuara për përdorim publik.

Shembuj të zgjedhjes së parametrave "të këqij" të shifrës RSA përshkruhen nën prerje.

"Nevoja për të qenë të kujdesshëm kur zgjidhni modulin RSA (numrat n) për secilin nga korrespondentët e rrjetit. Në këtë drejtim, mund të thuhet më poshtë. Lexuesi mund të verifikojë në mënyrë të pavarur se duke ditur një nga tre madhësitë fq, q ose φ (n), lehtë mund ta gjeni çelësin sekret RSA ... ”.

Le ta plotësojmë këtë tekst. Me një zgjedhje të pasuksesshme të modulit të shifrës RSA, siç është bërë në shembullin e mësimit më poshtë, ju mund të deshifroni tekstin pa praninë e një çelësi sekret, d.m.th. duke mos ditur asnjë nga tre madhësitë e emërtuara.

Për ta bërë këtë, mjafton që teksti i shifrës të specifikohet nga moduli i shifrimit n, çelësi publik e shifroni dhe kryeni vetëm tre hapa të një sulmi të leximit pa çelës. Pas hapit të katërt të sulmit, vërtetohet se teksti origjinal është marrë në hapin e mëparshëm, mund të lexohet. Le të tregojmë se sa e lehtë është ta bësh.

Së pari, ne do të japim vetë shembullin nga faqet 313-315 nga manuali i emëruar.

Shembull

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.

Për aq sa –137≡343 (mod480), atëherë d = 343.

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

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

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

Atëherë RSA = (100101001100001) 2... Thyerja e tekstit në blloqe me gjatësi të kufizuar jep një pamje me dy blloqe: RSA = (100101001), (100001) = (M 1 = 297, M 2 = 33).

Blloqet e tekstit burimor 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 shifror, si ai origjinal, merret në formën e dy blloqeve: y 1 = 474; y 2 = 407.

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

Llogaritjet e eksponentimit dështë më i përshtatshëm për t'u kryer, duke paraqet paraprakisht eksponentin si shuma e fuqive të numrit 2 , gjegjësisht: 343=256+64+16+4+2+1 .

Duke përdorur këtë përfaqësim eksponent 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 më 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ë përfaqësimin literal të mesazhit të deshifruar jep: RSA.

Pasi të shikoni shembullin, tutoriali diskuton qëndrueshmërinë e sistemit RSA. Nevoja për të qenë të kujdesshëm në zgjedhjen e modulit të shifrimit RSA (numrat n) për secilin nga korrespondentët e rrjetit. Theksohet se është e papranueshme të injorohen kërkesat për karakteristikat e zgjedhura të sistemit të kriptimit. Ndër kërkesat e tilla, për fat të keq, ajo që shkelja e së cilës ilustrohet me shembullin e dhënë nuk tregohet.

Sulmi i shifrës RSA

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

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

Më tej, ajo formohet nga kriptimi i përsëritur me ruajtjen e rezultateve të dy hapave të njëpasnjëshëm të algoritmit të sulmit dhe duke përdorur çelësin publik një sekuencë të vlerave numerike i, y 1 = y teksti shifror i disponueshëm.

Algoritmi i sulmit të koduar përcakton një hap të tillë 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 e shohim atë kur ngrihemi në fuqi e kuptim (y i e j - 1 (mod n)) fitohet teksti i koduar fillestar y i = y 1.

Por kjo do të thotë gjithashtu se teksti i thjeshtë ishte i koduar në këtë hap. Llogaritjet e drejtpërdrejta (ka shumë pak prej tyre) duke përdorur kalkulatorin në ekran, e gjejmë atë vlerë j, në të cilën cikli i kriptimit përfundon me vlerën y 1 nga e cila filloi cikli.

Sulmi në bllokun e parë y 1 = 474 ciphertext.
Hapi 1:& nbsp 474 7 (mod527) = 382;
Hapi 2:& nbsp 382 7 (mod527) = 423;
Hapi 3:& nbsp 423 7 (mod527) = 297;
Hapi 4: & nbsp Në këtë hap, teksti i gjetur tashmë i koduar është i koduar, por ai duhet të ekzekutohet, pasi sulmuesi nuk e njeh tekstin burimor. Sulmi përfundon nëse vlera fillestare e tekstit të koduar ( 474 ) dhe rezultati i hapit të katërt të kriptimit. Kjo është pikërisht rastësia që ndodh.

297 7 (mod527) = 474 mori bllokun fillestar (të parë) të tekstit të koduar. Sulmi i parë i bllokut 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 modulo n = 527... Writtenshtë shkruar kështu y i = y 1 = 297... Formimi i mbetjeve të energjisë
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 = 297.

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

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

Në thelb në unazën e mbetjeve modulo n = 527është zbatuar një cikël i shkurtër përpunimi për zbritjen r = 33 modulo n = 527... Writtenshtë shkruar kështu y i = y 2 = 33.
Formimi i mbetjeve të energjisë ((33 7 (mod527)) 7 (mod527)) 7 (mod527) = 33.

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

Duke vazhduar diskutimin e çështjes së zgjedhjes së një moduli dhe parametrave të tjerë të shifrës, mund të shtojmë se moduli i shifrimit ( n = 527) disa kod burim nuk lejojnë kriptim fare. Në këtë rast, zgjedhja e vlerës së çelësit publik e nuk luan një rol të madh. Ekzistojnë vlera të teksteve burimore që nuk mund të kodohen fare nga shifra e zgjedhur me modulin n = 527.

Asnjë nga e -të e dhëna nuk mund të kriptojë tekstet burimore të përfaqësuara me numra
187 , 341 , 154 dhe 373 .

Shembull (pamundësia e kriptimit të vlerave të disa teksteve burimore)

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ë vjen nga shembulli i shqyrtuar. Në të vërtetë, zgjedhja e parametrave për procesin e kriptimit duhet të afrohet me shumë kujdes dhe duhet të bëhet një analizë paraprake e plotë e parametrave të tillë. Si ta bëni këtë është një pyetje e veçantë dhe nuk merret parasysh në kuadrin e kësaj pune.

Në pjesën e dytë, ne do të shikojmë algoritmin popullor RSA, ku një çelës publik përdoret për kriptim. Por së pari, dua t'ju paralajmëroj përsëri. Kodi i dhënë në këtë artikull është vetëm për qëllime informative. Kriptografia është një zonë shumë e gjerë dhe komplekse, dhe në mënyrë që të mos keni ndonjë problem, unë nuk rekomandoj kodimin e informacionit duke përdorur zanatin tim.

Në pjesën e dytë, ne do të shikojmë algoritmin popullor RSA, ku një çelës publik përdoret për kriptim. Por së pari, dua t'ju paralajmëroj përsëri. Kodi i dhënë në këtë artikull është vetëm për qëllime informative. Kriptografia është një zonë shumë e gjerë dhe komplekse, dhe në mënyrë që të mos keni ndonjë problem, unë nuk rekomandoj kodimin e informacionit duke përdorur zanatin tim.

Algoritmi RSA

Kriptimi i çelësit publik

Kriptimi i çelësit publik është i kudogjendur. Nëse keni paguar për diçka në internet të paktën një herë, tashmë e keni përdorur këtë metodë (shpresoj!). Menjëherë lind pyetja se si funksionon kjo mbrojtje. Nëse fut numrin e kartës sime të kreditit për të blerë diçka, pse askush përveç adresuesit nuk mund ta shohë këtë informacion? Më lejoni t'ju jap një metaforë. Për të hapur kasafortën ju nevojitet një çelës (ose një çekiç, por për fat të mirë kasafortat dhe flokët mbrohen nga ky lloj personi). Me kriptimin e çelësit publik, ndodh e njëjta gjë. Ju tregoni bravën për ta parë të gjithë, por vetëm disa të zgjedhur e kanë çelësin e këtij bllokimi, dhe është pothuajse e pamundur të hapësh derën me metoda të tjera.

RSA është një nga algoritmet që zbaton skemën e mësipërme. Përveç kësaj, ne mund ta përdorim këtë algoritëm për të vërtetuar identitetin tonë. Nëse i dërgoni një mesazh të koduar dikujt duke përdorur çelësin privat, adresuesi mund të deshifrojë mesazhin tuaj duke përdorur çelësin publik. Kjo teknologji ju lejon të nënshkruani mesazhe, dhe në këtë mënyrë të vërtetoni dërguesin.

Program demo i bazuar në algoritmin RSA

RSA përdor dy lloje të çelësave - e dhe d, ku e është publik dhe d është sekret. Supozoni se P është teksti origjinal dhe C është teksti shifror. Alice përdor C = P e mod n për të krijuar tekstin e koduar C nga teksti origjinal P; Bob përdor P = C d mod n për të nxjerrë tekstin (skedarin) origjinal të dërguar nga Alice. Një numër shumë i madh i n moduleve krijohen duke përdorur procesin e gjenerimit të çelësit, për të cilin do të diskutojmë më vonë.

Për kriptimin dhe deshifrimin, përdoret moduli i eksponencës. Siç diskutuam në leksionet 12-13, kur përdorni algoritmin e shpejtë, moduli i eksponencës është i realizueshëm në kohën polinomiale. Sidoqoftë, gjetja e logaritmit modular është po aq e vështirë sa zgjerimi i një numri në modul. Nuk ka algoritëm të kohës polinomiale për të. Kjo do të thotë që Alice mund të kriptojë mesazhin me çelësin publik (e) në kohën polinomiale. Bob gjithashtu mund ta deshifrojë atë në kohë polinomiale (sepse ai e di d). Por Eva nuk mund ta deshifrojë këtë mesazh sepse asaj i duhet të llogarisë rrënjën e -të të C duke përdorur aritmetikë modulare. Figura 14.5 tregon idenë që qëndron pas RSA.

Oriz. 14.5.

Me fjalë të tjera, Alice përdor funksion i njëanshëm(modulo e eksponencës) me një boshllëk të njohur vetëm për Bobin. Eva nuk e di boshllëkun, kështu që ajo nuk mund ta deshifrojë mesazhin. Nëse një ditë gjendet një algoritëm polinom për modulin e llogaritjes së rrënjës e -të të n -së, atëherë moduli i eksponencës n nuk do të jetë më një funksion i njëanshëm.

Procedura

Figura 14.6 tregon idenë e përgjithshme të procedurës së përdorur në RSA.

RSA përdor eksponentimin për kriptim / deshifrim. Për të sulmuar tekstin e mbyllur, Eva duhet të llogarisë

Dy struktura algjebrike

RSA përdor dy struktura algjebrike: unazë dhe grup.

Kriptimi / Unazat e deshifrimit... Kriptimi dhe deshifrimi bëhet duke përdorur një unazë ndërruese me dy veprime aritmetike: mbledhje dhe shumëzim. Në RSA, kjo unazë është në dispozicion publik sepse moduli n është i disponueshëm për publikun. Çdokush mund t'i dërgojë një mesazh Bobit duke përdorur këtë unazë kriptimi.

Grupet kryesore të gjenerimit... RSA përdor grupin shumëzues për të gjeneruar çelësa. Grupi mbështet vetëm shumëzimin dhe pjesëtimin (inversi shumëzues), të cilat nevojiten për të krijuar çelësa publikë dhe privatë. Ky grup duhet të fshihet sepse moduli i tij është sekret. Ne do të shohim që nëse Eva e gjen këtë modul, ajo lehtë mund të sulmojë sistemin kriptografik.

RSA përdor dy struktura algjebrike: unazën e hapur R =< Z n , +, x> dhe grupi sekret G =< Z (n) * , x>.

Gjenerimi i çelësave

Bob përdor hapat e treguar në Algoritmin 14.2 për të krijuar çelësat e tij publik dhe privat. Pas krijimit të çelësave, Bob deklaron tuple (e, n) si çelësin e tij të hyrjes publike: Bob ruan d si çelësin e tij privat. Bob mund të bjerë p, q dhe; ata nuk mund të ndryshojnë çelësin e tij sekret pa ndryshuar modulin. Për siguri, madhësia e rekomanduar për çdo p ose q është 512 bit (pothuajse 154 shifra dhjetore). Kjo përcakton madhësinë e njësisë, n 1024 bit (309 shifra).

Në RSA, tuple (e, n) është çelësi i aksesit publik; numër i plotë d - çelës sekret.

Kriptimi

Çdokush mund t'i dërgojë një mesazh Bobit duke përdorur çelësin e tij të hyrjes publike. Kriptimi në RSA mund të bëhet duke përdorur një algoritëm kompleksiteti të kohës polinomiale, siç tregohet në Algoritmin 14.3. Një algoritëm i shpejtë i eksponimit u diskutua në leksionet 12-13. Madhësia e tekstit burimor duhet të jetë më pak se n; nëse madhësia e tekstit burimor është më e madhe, atëherë duhet të ndahet në blloqe.