3) y = llogaritet një x mod (p);

4) zgjidhet çelësi publik i verifikimit të CPU: ( p, a, y) dhe çelësin sekret për të krijuar CPU: x.

Formimi i CPU-së

Nëse përdoruesi A dëshiron të nënshkruajë një mesazh m, të përfaqësuar si një numër që i përket Zp, atëherë ai kryen veprimet e mëposhtme:

1) gjeneron një numër sekret k: 1 ≤ k≤ p - 2; gcd ( k, p - l) = 1, ku gcd është gcd

2) njehson r = a k mod (p);

3) njehson k -1 mod (p - 1);

4) llogarit s = k -l (m - xr) mod (p - l);

5) Formon CPU S në mesazhin m si një çift numrash S = (r, t).

Verifikimi i CPU-së (verifikimi)

Për të verifikuar nënshkrimin S të krijuar nga A nën mesazhin M, çdo përdorues ndërmerr hapat e mëposhtëm:

1) merr çelësin publik A: (p, a, y);

2) verifikon që 1 ≤ r ≤ p - 1, dhe nëse dështon, atëherë refuzon CPU-në;

3) njehson V 1 = y r r s mod (p);

4) njehson V 2 = a m mod (p);

5) e pranon CPU-në si të saktë me kusht që V 1 = V 2

Rezistenca e CPU-së Bazuar në COP të ElGamal

1) Një sulmues mund të përpiqet të falsifikojë një nënshkrim në mesazhin e tij M si më poshtë: gjeneroni një numër të rastësishëm k, llogarisni r = a k mod (p) dhe më pas përpiquni të gjeni s = k - l (m - xr) mod (p - l).

Megjithatë, për të kryer operacionin e fundit, ai duhet të dijë a, të cilat nuk mund të llogariten me zgjedhjen e duhur të parametrave të CPU-së.

3) Duhet theksuar se nëse nuk plotësohet hapi 2 i algoritmit të verifikimit të CPU atëherë një sulmues mund të nënshkruajë në mënyrë korrekte çdo mesazh sipas zgjedhjes së tij, me kusht që ai të ketë në dispozicion një mesazh tjetër me CPU-në e duhur. Kështu, kur zgjidhni një modul R, i cili në paraqitjen binar ka një gjatësi prej rreth 768 bit, siguron stabilitet të mirë të CPU-së dhe për të siguruar qëndrueshmëri afatgjatë këshillohet që të rritet në 1024 bit.

Kërkesat për HF kriptografike

1. Njëdrejtimshmëria, kur për një hash h të njohur është llogaritësisht e pamundur (d.m.th., kërkon një numër të madh operacionesh të parealizueshme) për të gjetur të paktën një vlerë të x për të cilën, domethënë, h (x) rezulton të jetë një funksioni me një drejtim (ONF).

2. Rezistencë e dobët ndaj përplasjes, kur për x të dhënë, h (x) = h është llogaritëse e pamundur të gjesh një vlerë tjetër x 'që plotëson ekuacionin h (x') = h.

3. Rezistencë e fortë ndaj përplasjes, kur është e pamundur nga pikëpamja llogaritëse të gjesh një çift argumentesh x, x 'për të cilat vlen relacioni h (x) = h (x').

Rregullimi i cenueshmërisë

Denning dhe Sacco sugjeruan përdorimin e vulave kohore në mesazhe për të parandaluar sulme si ai i diskutuar më sipër. Le ta shënojmë një emërtim të tillë me shkronjën t. Merrni parasysh opsionin për të rregulluar cenueshmërinë:

Komponentët PKI

· Autoriteti i Certifikatave (CA)- pjesa e sistemit të çelësit publik që lëshon një certifikatë për të vërtetuar të drejtat e përdoruesve ose sistemeve që bëjnë një kërkesë. Ajo krijon një certifikatë dhe e nënshkruan atë duke përdorur një çelës privat. Për shkak të funksionit të krijimit të certifikatave, AK është pjesa qendrore e PKI.

· Depoja e Certifikatave... Depo për certifikatat e vlefshme dhe listat e revokimit të certifikatave (CRL). Aplikacionet verifikojnë vlefshmërinë e certifikatës dhe nivelin e aksesit që ajo jep duke kontrolluar me mostrën që gjendet në depo.

· Serveri i rikuperimit të çelësave- një server që kryen rikuperimin automatik të çelësit, nëse ky shërbim është i instaluar.

· Aplikacion i aktivizuar me PKI- aplikacione që mund të përdorin mjete PKI për siguri. PKI menaxhon certifikatat dixhitale dhe çelësat e përdorur për të enkriptuar informacionin në serverët e uebit kur përdorni e-mail, shkëmbim mesazhe, shfletoni internetin dhe transferoni të dhëna. Disa aplikacione mund të përdorin PKI në mënyrë origjinale, ndërsa të tjerë kërkojnë që programuesit të modifikojnë.

· Autoriteti i Regjistrimit- një modul përgjegjës për regjistrimin e përdoruesve dhe pranimin e kërkesave për një certifikatë.

· Server sigurie- Një server që menaxhon aksesin e përdoruesit, certifikatat dixhitale dhe marrëdhëniet e forta në një mjedis PKI. Serveri i Sigurisë menaxhon në mënyrë qendrore të gjithë përdoruesit, certifikatat, lidhjet CA, raportet dhe verifikon listën e revokimit të certifikatave.

Funksionet PKI

· Regjistrimi- procesi i mbledhjes së informacionit për një përdorues dhe i verifikimit të origjinalitetit të tij, i cili përdoret më pas gjatë regjistrimit të përdoruesit, në përputhje me rregullat e sigurisë.

· Lëshimi i certifikatës... Pasi AK të ketë nënshkruar certifikatën, ajo i lëshohet aplikantit dhe/ose dërgohet në dyqanin e certifikatave. AK-ja vendos një periudhë vlefshmërie në certifikata, duke kërkuar kështu rinovimin periodik të certifikatës.

· Revokimi i certifikatës... Një certifikatë mund të bëhet e pavlefshme para skadimit për arsye të ndryshme: përdoruesi është larguar nga kompania, ka ndryshuar emrin e tij ose nëse çelësi i tij privat është komprometuar. Në këto rrethana, AK-ja do të revokojë certifikatën duke futur numrin e saj serial në CRL.

· Rimëkëmbja e çelësit... Një funksion shtesë PKI ju lejon të rikuperoni të dhëna ose mesazhe në rast të humbjes së çelësit.

· Menaxhimi i ciklit të jetës- Mbështetje e vazhdueshme e certifikatave në PKI, duke përfshirë rinovimin, restaurimin dhe arkivimin e çelësave. Këto funksione kryhen në mënyrë periodike dhe jo në përgjigje të kërkesave ad hoc. Menaxhimi i automatizuar i çelësave është tipari më i rëndësishëm për PKI-të e mëdha. Menaxhimi manual i çelësave mund të kufizojë shkallëzimin e PKI.

Përkufizimet bazë

· Listat e revokimit të certifikatave (CRL)- lista e certifikatave të anuluara. Anulimet mund të jenë për shkak të ndryshimit të vendit të punës, vjedhjes së çelësit privat ose arsyeve të tjera. Aplikacionet PKI mund të kontrollojnë certifikatat e përdoruesve kundrejt një CRL përpara se të japin akses ndaj asaj certifikate.

· Certifikata Dixhitale / Certifikata X.509... Një strukturë të dhënash e përdorur për të lidhur një modul specifik me një çelës publik specifik. Certifikatat dixhitale përdoren për të vërtetuar përdoruesit, aplikacionet dhe shërbimet dhe për të kontrolluar aksesin (autorizimin). Certifikatat dixhitale lëshohen dhe shpërndahen nga AK-të.

· Zarf dixhital... Një metodë e përdorimit të kriptimit të çelësit publik për të shpërndarë në mënyrë të sigurt çelësat sekretë të përdorur në enkriptimin simetrik dhe për të dërguar mesazhe të koduara. Problemi i shpërndarjes së çelësit i lidhur me enkriptimin simetrik është reduktuar shumë.

· Nënshkrimi dixhital... Një metodë e përdorimit të kriptimit të çelësit publik për të siguruar integritetin e të dhënave dhe pamundësinë për të refuzuar një parcelë. Blloku i koduar i informacionit, pas deshifrimit nga marrësi, identifikon dërguesin dhe konfirmon sigurinë e të dhënave. Për shembull: dokumenti është "i ngjeshur", HASH kodohet duke përdorur çelësin privat të dërguesit dhe i bashkëngjitet dokumentit (në fakt, kjo do të thotë të bashkëngjitni "gjurmën e gishtit" të këtij dokumenti). Marrësi përdor çelësin publik për të deshifruar mesazhin e marrë në gjendjen "shtypje", e cila më pas krahasohet me "shtrydhjen" e marrë pasi dokumenti i dërguar është "kompresuar". Nëse të dy "shtrydhjet" nuk përputheshin, atëherë kjo do të thotë që dokumenti është ndryshuar ose dëmtuar gjatë transferimit.

· Kriptografia e çelësit publik... Ekzistojnë dy lloje kryesore të kriptimit: çelësi publik dhe çelësi sekret (simetrik). Kriptimi i çelësit publik përdor një çift çelësash: i hapur, d.m.th. disponueshme lirisht, dhe çelësin e tij privat përkatës, i njohur vetëm për përdoruesin, aplikacionin ose shërbimin specifik që zotëron këtë çelës. Ky çift çelësash është i lidhur në atë mënyrë që ajo që është e koduar me çelësin privat mund të deshifrohet vetëm me çelësin publik dhe anasjelltas.

· Kriptimi simetrik (Kriptografi sekrete e përbashkët)... Ekzistojnë dy lloje kryesore të kriptimit: çelësi publik dhe çelësi sekret (simetrik). Me kriptim simetrik, marrësi dhe dërguesi përdorin të njëjtin çelës për enkriptim dhe deshifrim. Kjo do të thotë që shumë përdorues duhet të kenë të njëjtat çelësa. Natyrisht, derisa përdoruesi të marrë çelësin, enkriptimi nuk është i mundur dhe shpërndarja e çelësit në rrjet nuk është e sigurt. Metodat e tjera të shpërndarjes, si një korrier special, janë të shtrenjta dhe të ngadalta.

· Algoritmi RSAështë sistemi i parë i enkriptimit me çelës publik i quajtur sipas shpikësve të tij: Ronald Rivest, Adi Shamir dhe Leonard Adleman.

· Kartë inteligjente. Një pajisje e ngjashme me kartën e kreditit me memorie të integruar dhe një procesor që përdoret për të ruajtur në mënyrë të sigurt çelësat dhe certifikatat e përdoruesit dhe informacione të tjera (zakonisht sociale dhe mjekësore).

· Kredencialet dixhitale. Brenda kuadrit të teknologjisë PKI, standardi ISO / TS 17090-1 e përcakton këtë term si një objekt të mbrojtur kriptografikisht që mund të përmbajë çelësa përdoruesi individual, certifikata të çelësave individualë, certifikata të CA-ve të strukturës PKI të përdoruesit, një listë të CA-ve të besueshme, dhe parametra të tjerë që lidhen me domenin e përdoruesit - identifikuesin e përdoruesit, emrat e algoritmeve kriptografike të aplikuara, vlerat e vlerave fillestare, etj. Kredencialet mund të vendosen në media harduerike ose softuerike.

Parimi i funksionimit

Certifikatat zakonisht përdoren për të shkëmbyer të dhëna të koduara përmes rrjeteve të mëdha. Një kriptosistem i çelësit publik zgjidh problemin e shkëmbimit të çelësave sekretë midis pjesëmarrësve në një shkëmbim të sigurt, por nuk e zgjidh problemin e besimit të çelësave publikë. Supozoni se Alice, duke dashur të marrë mesazhe të koduara, gjeneron një palë çelësa, njërin prej të cilëve (publik) e publikon në një farë mënyre. Kushdo që dëshiron t'i dërgojë asaj një mesazh konfidencial ka mundësinë ta kodojë atë me këtë çelës dhe të jetë i sigurt se vetëm ajo (pasi vetëm ajo ka çelësin sekret përkatës) do të jetë në gjendje ta lexojë këtë mesazh. Sidoqoftë, skema e përshkruar në asnjë mënyrë nuk mund ta pengojë sulmuesin David të krijojë një çift çelësash dhe të publikojë çelësin e tij publik, duke e kaluar atë si çelësin e Alice. Në këtë rast, Davidi do të jetë në gjendje të deshifrojë dhe lexojë të paktën atë pjesë të mesazheve të destinuara për Alice, të cilat gabimisht janë koduar me çelësin e tij publik.

Ideja pas një certifikate është se ekziston një palë e tretë që i besohet dy palëve të tjera në shkëmbimin e informacionit. Supozohet se ka pak palë të tilla të treta, dhe çelësat e tyre publikë janë të njohur për të gjithë në një farë mënyre, për shembull, të ruajtur në sistemin operativ ose të publikuar në regjistra. Kështu, një falsifikim i çelësit publik të një pale të tretë zbulohet lehtësisht.

Sistemet kriptografike me çelësa të enkriptimit publik i lejojnë përdoruesit të transferojnë të dhëna në mënyrë të sigurt mbi një kanal të pasigurt pa ndonjë përgatitje paraprake. Kriptosisteme të tilla duhet të jenë asimetrike në kuptimin që dërguesi dhe marrësi kanë çelësa të ndryshëm dhe asnjëri prej tyre nuk mund të nxirret nga tjetri me anë të llogaritjes. Në këto sisteme, fazat e enkriptimit dhe deshifrimit janë të ndara dhe mesazhi mbrohet pa u bërë sekret çelësi i enkriptimit, pasi ai nuk përdoret në deshifrim.

Duke përdorur çelësin e enkriptimit publik, përdoruesi i kodon mesazhin M dhe ia dërgon përdoruesit j nëpërmjet një kanali të pambrojtur të transmetimit të të dhënave. Vetëm përdoruesi j mund të deshifrojë për të rikuperuar M, pasi vetëm ai e di çelësin sekret të deshifrimit.

Ndër kriptosistemet asimetrike (të hapura), më i përhapuri është sistemi kriptografik RSA. Në këtë sistem, marrësi i mesazhit zgjedh dy numra të mëdhenj p dhe q në mënyrë që produkti n = pq të jetë përtej aftësive llogaritëse. Mesazhi origjinal M mund të jetë me gjatësi arbitrare në intervalin 1

Teksti origjinal M është restauruar nga C-ja e koduar nga transformimi i kundërt

Marrësi zgjedh e dhe d në mënyrë që të plotësohen kushtet e mëposhtme:

ku është funksioni Euler i barabartë me (p - 1) (q - 1);

(a, b) është pjesëtuesi më i madh i përbashkët i dy numrave.

Kjo do të thotë, e dhe d në grupin shumëzues janë reciproke në modin aritmetik të mbetjeve.

Natyrisht, qëllimi kryesor i zbulimit kriptografik është përcaktimi i çelësit sekret (eksponenti në C - vlera e d).

Ka tre mënyra të njohura që një kriptanalist mund të përdorë për të zbuluar vlerën e d nga informacioni i hapur rreth çiftit (e, n).

Faktorizimi n

Faktorizimi kryesor i n na lejon të llogarisim funksionin, dhe si rrjedhim vlerën e fshehur të d, duke përdorur ekuacionin

Algoritme të ndryshme për një zbërthim të tillë janë paraqitur në. Algoritmi më i shpejtë i njohur aktualisht mund të faktorizojë n në hapa të rendit

Analiza e kësaj shprehjeje tregon se numri n me 200 shifra dhjetore do të mbrohet mirë nga metodat e njohura të zgjerimit.

Llogaritja e drejtpërdrejtë

Një mënyrë tjetër e mundshme e kriptanalizës lidhet me llogaritjen e drejtpërdrejtë të funksionit të Euler-it pa faktorizimin n. Llogaritja e drejtpërdrejtë nuk është aspak më e thjeshtë se faktorizimi i n-së, pasi më pas e bën të lehtë faktorizimin e n-së. Kjo mund të shihet nga shembulli i mëposhtëm. Le

x = p + q = n + 1 -,

y = (p - q) 2 = x 2 - 4n.

Duke ditur, ju mund të përcaktoni x dhe, për rrjedhojë, y, duke ditur x dhe y, p dhe q i thjeshtë mund të përcaktohen nga relacionet e mëposhtme:

Vlerësimi i drejtpërdrejtë d

Metoda e tretë e kriptanalizës është llogaritja e drejtpërdrejtë e vlerës së d. Arsyetimi pas kësaj metode bazohet në faktin se nëse d zgjidhet mjaftueshëm i madh që numërimi i thjeshtë të jetë i papranueshëm, llogaritja e d nuk është më e thjeshtë se faktorizimi i n, pasi nëse dihet d, atëherë n faktorizohet lehtësisht. Kjo mund të tregohet si më poshtë. Nëse dihet d, atëherë mund të llogarisim një shumëfish të funksionit të Euler-it duke përdorur kushtin

ku k është një numër i plotë arbitrar.

Ju mund të faktorizoni n duke përdorur çdo shumëfish të. Dekriptuesi, nga ana tjetër, mund të përpiqet të gjejë një vlerë d "që është ekuivalente me vlerën e fshehur d të përdorur në hartimin e shifrës. Nëse ka shumë d të tillë", atëherë mund të tentohet forca brutale për të thyer shifrën . Por të gjitha d "ndryshojnë nga një faktor i barabartë me dhe nëse ky faktor llogaritet, atëherë n mund të faktorizohet. Kështu, gjetja e d është po aq e vështirë sa faktorizimi n.

Kështu, detyra kryesore e kriptanalizës së sistemeve të enkriptimit asimetrik reduktohet kryesisht në problemin e faktorizimit (faktorizimit). Ky problem është një nga më kryesorët në teorinë e numrave dhe është formuluar si më poshtë:

Le të na jepet një numër i plotë n> 0, dhe kërkohet, nëse është e mundur, të gjejmë dy numra a dhe b të tillë që ab = n. Në fakt ekzistojnë dy detyra të ndryshme: e para, e quajtur testi i thjeshtësisë, është të kontrolloni nëse a dhe b e tilla ekzistojnë; e dyta, e quajtur dekompozim, është problemi i gjetjes së tyre. Le të shqyrtojmë të dyja këto detyra.

Testi i parë përcaktues.

Ky test bazohet në Teoremën e Vogël të Fermatit, e cila thotë se nëse p është një numër i thjeshtë, atëherë një p-1 1 (mod p) për të gjithë a, 1

Kështu, testi konsiston në zgjedhjen e një numri a që është më i vogël se b dhe kontrollimin

b për përkatësinë në klasën e numrave të thjeshtë sipas kushtit a b-1 1 (mod b) në përputhje me shprehjen e mësipërme. Në praktikë, duhet të kontrollohen vetëm disa vlera. Zgjedhja e një të barabartë me 3 zbulon të gjithë numrat e përbërë. Megjithatë, ky test dihet se kapërcen numrat e përbërë Carmichael (për shembull, 561 = 3 x 11 x 17).

Testi i dytë përcaktues.

Le të pjesëtojmë numrin "b" në mënyrë sekuenciale me 2, 3, ...,. Nëse në një pjesëtim marrim një mbetje zero, atëherë numri "b" është i përbërë, dhe pjesëtuesi dhe herësi janë faktorët e tij; përndryshe b është i thjeshtë.

Meqenëse është e nevojshme të kryhen pjesëtimet, koha që duhet për të kontrolluar numrin e thjeshtë të numrit "b" është O ().

Ky test shumë i ngadalshëm eksponencial jo vetëm që përcakton nëse një numër është i thjeshtë, por gjithashtu gjen faktorët e një numri të përbërë.

Testi i tretë deterministik.

Numri “b” është i thjeshtë nëse dhe vetëm nëse b | ((b-1)! + 1). Faktorial (b-1)! dhe testi i pjesëtueshmërisë (b-1) + 1 për "b" të madh shkatërron çdo interes në këtë test. Nëse `b' ka 100 shifra dhjetore, atëherë (b-1) është afërsisht 100 102 shifra e gjatë.

Të gjitha testet e mësipërme ishin deterministe. Kjo do të thotë se për një numër të dhënë "b" marrim gjithmonë një përgjigje, qoftë ajo e thjeshtë apo e përbërë. Nëse fjalën "gjithmonë" e zëvendësojmë me "me disa probabilitet", atëherë rezulton të jetë e mundur të ndërtohen teste probabilistike, të cilat quhen edhe teste pseudo-thjeshtësisë.

Testi i parë probabilistik.

Ky test ju lejon të identifikoni të gjithë numrat e përbërë të Carmichael. Përzgjidhet një numër i rastësishëm a në intervalin nga 1 deri në b-1 dhe kontrollohet plotësimi i kushteve.

(a, b) = 1, J (a, b) a (b-1) / 2 (mod b),

ku J (a, b) është simboli Jacobi.

Simboli Jacobi përcaktohet nga relacionet e mëposhtme:

J (a, p) = 1 nëse x 2 a (mod p) ka zgjidhje në Z p,

J (a, p) = -1 nëse x 2 a (mod p) nuk ka zgjidhje në Z p,

ku Z p është unaza e mbetjeve modulo p.

Nëse b është një numër i thjeshtë, kushtet e mësipërme plotësohen gjithmonë, dhe nëse b është i përbërë, atëherë ato nuk plotësohen me probabilitet. Prandaj, ekzekutimi i testeve k siguron që përgjigja është e pasaktë me probabilitet 2 -k.

Testi i dytë probabilistik.

Meqenëse numri b, i cili duhet të jetë i thjeshtë, është gjithmonë tek, ai mund të përfaqësohet si

ku s është një numër çift. Më pas, në test, një numër a zgjidhet rastësisht në intervalin nga 1 në b-1 dhe kontrollohet plotësimi i kushteve.

1 (mod b) për 0< j

Të dy testet përdoren për të kontrolluar nëse një numër i përket klasës së thjeshtë dhe kërkojnë operacione O (log 2 b) në numra të mëdhenj.

Testi i tretë probabilistik.

Për një b të dhënë, ne zgjedhim rastësisht m, 1

Probabiliteti që të jepet përgjigja “b është numër i përbërë” është i barabartë me probabilitetin që m | b. Nëse d (b) numri i pjesëtuesve b dhe m zgjidhet rastësisht brenda 1

Ky është një test shumë i dobët.

Testi i katërt probabilistik.

Për një "b" të dhënë, ne zgjedhim rastësisht m, 1

Nëse b është një numër i përbërë, atëherë numri i numrave m

Testi i pestë probabilistik.

Ky është një test i pseudo-thjeshtësisë së fortë. Le të jepen b dhe m. Le

ku t është një numër tek dhe konsideroni numrat për (x r është vlera më e vogël absolute e modulit të mbetur b).

Nëse x 0 = 1, ose ka një indeks i, i

Le ta vërtetojmë me kontradiktë. Supozoni se b është një numër i thjeshtë tek. Le të tregojmë me induksion se 1 (mod b) për, i cili do të kundërshtonte hipotezën e teoremës.

Natyrisht, kjo është e vërtetë për r = S nga teorema e Fermatit. Duke supozuar se pohimi është i vërtetë për i, është e lehtë të shihet se është e vërtetë për i-1, sepse barazia

nënkupton që numri që do të vendoset në katror është ± 1. Por -1 nuk përputhet me kushtin (përndryshe testi do të kishte dhënë përgjigjen "nuk mund të përcaktohet").

Është vërtetuar se nëse b është një numër i përbërë, atëherë probabiliteti që testi të japë përgjigjen "b është një numër i përbërë" nuk është më i vogël.

Faktorizimi i numrave të plotë të mëdhenj.

Situata me problemin e gjetjes së pjesëtuesve të numrave të thjeshtë është shumë më e keqe sesa me testin e thjeshtësisë. Më poshtë është metoda më e fuqishme e njohur.

Metoda bazohet në idenë e Lezhandrit nëse U 2 V 2 (mod b) 0

Supozojmë se duam të faktorizojmë numrin b. Le të jetë n = numri maksimal që nuk tejkalon, dhe llogaritni numrat a k = (n + k) 2 - b për k të vogël (numrat k mund të jenë negativ).

Le të jetë (q i, i = 1, 2,…, j) një grup numrash të thjeshtë të thjeshtë që mund të ndajnë një shprehje si x 2 - b (dmth. b është një modul katror q i). Një bashkësi e tillë zakonisht quhet baza shumëzuese B. Le të kujtojmë të gjithë numrat a k që mund të zgjerohen në terma të bazës shumëzuese, d.m.th. shkruar si

Ak të tillë quhen numra B. Çdo B-numër ak shoqërohet me një vektor treguesish

Nëse gjejmë mjaftueshëm B-numra që bashkësia e vektorëve eksponentë përkatës të jenë të varur linearisht moduli 2

(çdo grup j + 2 B-numra e ka këtë veti), atëherë do të jetë e mundur të përfaqësohet vektori zero si një shumë e vektorëve të eksponentëve të një grupi S, të themi

Përcaktoni numrat e plotë

i = 0, 1, ..., j,

Nga sa më sipër rezulton se U 2 V 2 (mod b) dhe (U-V, b) mund të jenë një pjesëtues jo i parëndësishëm i b.

Deshifrimi me përsëritje kryhet si më poshtë. Armiku merr numrin j, për të cilin plotësohet raporti i mëposhtëm:

Kjo do të thotë, kundërshtari thjesht kodon j herë në çelësin publik të tekstit të shifruar të përgjuar. Duket kështu: (C e) e) e ..) e (mod n) = C e j (mod n)). Pasi ka gjetur një j të tillë, kundërshtari llogarit C e (j-1) (mod n) (d.m.th. përsërit operacionin e enkriptimit j-1 herë) - kjo vlerë është teksti i thjeshtë M. Kjo rrjedh nga fakti se C ej (mod n ) = (C e (j-1) (mod n)) e = C. Kjo do të thotë, një numër C e (j-1) (mod n) në fuqinë e jep tekstin shifror C. Dhe ky është teksti i thjeshtë M.

Shembull. p = 983, q = 563, e = 49, M = 123456.

C = M 49 (mod n) = 1603, C497 (mod n) = 85978, C498 (mod n) = 123456, C499 (mod n) = 1603.

Vit akademik

Pjesa teorike

1. Llojet kryesore të transformimeve të informacionit kriptografik. Thelbi i çdo transformimi, fushëveprimi.

2. Paraqitja e një sistemi enkriptimi me grafik, parimi i unicitetit të kriptimit-deshifrimit.

3. Modeli matematik i sistemit të enkriptimit-deshifrimit të informacionit.

4. Forca e sistemit të enkriptimit, klasifikimi i sistemeve të enkriptimit sipas fuqisë. Llojet e sulmeve në sistemin e enkriptimit.

5. Përkufizimi i një sistemi enkriptimi të sigurt pa kushte, një deklaratë për kushtet e nevojshme për ekzistencën e një sistemi të sigurt pa kushte.

6. Përkufizimi i një sistemi enkriptimi të sigurt pa kushte, një deklaratë për kushte të mjaftueshme për ekzistencën e një sistemi të sigurt pa kushte.

7. Sistemet e enkriptimit të sigurta nga ana kompjuterike, koncepti i kompleksitetit të kriptanalizës, qasjet kryesore për thyerjen e sistemeve kriptografike, analiza e sulmeve me forcë brutale dhe sulmet bazuar në statistikat e mesazheve.

8. Shifra e bllokut, skema Feistel, vetitë e shifrave të bllokut.

9. Kodi i zëvendësimit, vetitë e tij.

10. Kodi gama dhe vetitë e tij.

11. Mënyrat (mënyrat e funksionimit) të shifrave të bllokut, një përshkrim i shkurtër i mënyrave.

12. Standardi i kriptimit GOST R34.12-2015, algoritmi bazë i enkriptimit për një bllok 64-bit.

13. Standardi i kriptimit GOST R34.12-2015, algoritmi bazë i enkriptimit për një bllok 128-bit.

14. Standardi i kriptimit GOST R34.13-2015, algoritmi i enkriptimit në modalitetin e thjeshtë të zëvendësimit, algoritmi i enkriptimit në modalitetet gama dhe gama me reagime. Krahasimi i mënyrave.

15. Regjistri i përsëritur linear, vetitë algjebrike të një sekuence rekurente lineare, analiza e vetive të parashikueshmërisë.

16. Regjistri i përsëritur linear, vetitë statistikore të sekuencës rekurente lineare.

17. Parimet e ndërtimit të formuesve të gamës shifrore (koncepti i kompleksitetit linear ekuivalent, përdorimi i nyjeve jolineare për të rritur kompleksitetin linear).

18. Kodi A5 / 1, karakteristikat e kodit, parimi i ndërtimit, zbatimi.

19. Parimi i ndërtimit dhe karakteristikat e shifrës AES.

20. Koncepti i funksionit njëkahësh, parimi i përgjithshëm i ndërtimit të sistemeve kriptografike me çelës publik.

21. Koncepti i një funksioni hash, kërkesat për funksionet hash kriptografike.

22. Funksioni hash sipas GOST R34.11-12, karakteristikat, parimi i ndërtimit, aplikimi.

23. Sistemi i enkriptimit El Gamal, sulmet në sistem.

24. Sistemi i enkriptimit RSA, sulmet në sistem.

25. Përkufizimi, klasifikimi, vetitë themelore, modeli EP.

26. Skema EP RSA.

27. Skema e PE El-Gamal.

28. EDS në përputhje me GOST 34.10-12, karakteristikat e përgjithshme, parimi i formimit dhe verifikimit të nënshkrimit.

29. Autentifikimi i mesazheve në sistemet e telekomunikacionit (modeli i sistemit të mbrojtjes së imitimit, strategjitë e imponimit, treguesit e sigurisë së imitimit).

30. Koncepti i një funksioni hash kyç. Një klasë funksionesh hash rreptësisht universale, shembuj të zbatimit të këtyre funksioneve hash.

31. Ndërtimi i sistemeve të vërtetimit me probabilitet të garantuar imponimi.

32. Ndërtimi i një sistemi autentikimi për transmetim të shumëfishtë të mesazheve.

33. Sistemet e vërtetimit rezistente llogaritëse.

34. Zhvillimi i një inserti imitues sipas GOST R34.12-2015.

35. Modeli i menaxhimit të çelësave në sistemet kriptografike simetrike, karakteristikat e ciklit jetësor të çelësit.

36. Metodat e shpërndarjes së çelësave bazuar në shkëmbimin e ndërsjellë të mesazheve ndërmjet korrespondentëve. Metoda Diffie-Hellman.

37. Metodat për gjenerimin e numrave të rastit gjatë gjenerimit të çelësave.

38. Metodat për shpërndarjen e çelësave duke përdorur CRC në fazën fillestare.

39. Metodat për shpërndarjen e çelësave duke përdorur CRC në modalitetin interaktiv. Protokolli Needham-Schroeder.

40. Parimi i shpërndarjes së çelësave publikë.

41. Koncepti i infrastrukturës së çelësit publik (PKI), përbërja, parimi i ndërveprimit të elementeve të strukturës.

42. Qëllimi, parimi i formimit dhe karakteristikat e certifikatës së çelësit publik.

Pjesa praktike

1. Enkriptoni (deshifroni) një mesazh me dorë me një zëvendësim, ndërrim dhe kodim gama. Programi LR1_1.exe.

2. Deshifroni kriptogramin bazuar në analizën e statistikave të tij duke përdorur programin CHANGE.EXE.

3. Gjeni faktorin e shumëzimit të gabimeve gjatë deshifrimit të kriptogramit të një shifre të zëvendësimit-permutacionit të bllokut me gjatësi blloku 16 bit. Programi tst.

4. Deshifroni kriptogramin e shifrës së ndërrimit-permutacionit me numërimin me forcë brutale të çelësave duke përdorur programin tst. Argumentoni parametrat për marrjen e një vendimi për deshifrimin e saktë.

5. Kripto një mesazh 64-bit me algoritmin bazë të enkriptimit GOST R 34.12-2015 (1 raund)

6. Enkriptoni një mesazh 128-bit duke përdorur programin AES.exe. Kontrolloni që transformimi i parë (operacioni SubBytes) përdor një përmbysje elementi në fushën GF (2 8).

7. Duke përdorur polinomin karakteristik h (x), ndërtoni LRR (mbushja fillestare 10 ... 01) Përcaktoni periodën e sekuencës. Gjeni ekuilibrin, kontrolloni vetitë e serisë dhe dritares. Kontrolloni rezultatin duke përdorur programin LRR 1.

8. Gjeni sekuencën në daljen e gjeneratorit të gamës së shifrave që përmban elemente OSE, DHE JO, Jeff. Duke përdorur programin LRR 2, përcaktoni kompleksitetin ekuivalent të sekuencës. Ndërtoni një LRR ekuivalente. Nxirrni përfundime.

9. Kryeni llogaritjet e mëposhtme për seksionin e matematikës diskrete:

Gjeni pjesëtuesin më të madh të përbashkët duke përdorur algoritmin e Euklidit;

Llogaritni një x modp duke përdorur algoritmin e fuqizimit të shpejtë;

Gjeni inversin e një numri mod p.

Gjeni funksionin e Euler-it të x;

10. - duke përdorur testin e Fermatit për të kontrolluar nëse numri x është i thjeshtë, gjeni probabilitetin që kontrolli të japë një rezultat të gabuar.

11. Parametrat e sistemit të enkriptimit El-Gamal vendosen a = 4, p = 11, çelësi privat x = 7, kodoni mesazhin M =. Deshifroni kriptogramin.

12. Parametrat e sistemit të enkriptimit RSA vendosen p = 11, q = 13, kodoni mesazhin M = 5. Deshifroni kriptogramin.

13. Parametrat e sistemit të enkriptimit El-Gamal vendosen a = 4, p = 11, çelësi privat x = 8, nënshkruani mesazhin, kodi hash i të cilit është h (M) =. Kontrollo nënshkrimin.

14. Parametrat e sistemit të enkriptimit RSA vendosen p = 11, q = 13, nënshkruani mesazhin, kodi hash i të cilit është h (M) = 6. Kontrolloni nënshkrimin.

15. Duke përdorur programin RSA, kodoni skedarin e madh me kriptosistemin e sigurt RSA dhe vlerësoni kohën e enkriptimit dhe deshifrimit.

16. Duke përdorur programin RSA, nënshkruani mesazhet dhe verifikoni nënshkrimin. Kapaciteti i mesazhit është të paktën 100 bit.

17. Është vendosur një kurbë eliptike E13 (1,1). Gjeni pikën C të barabartë me shumën e dy pikave, koordinatat e pikave dhe x 1 =, y 1 =, x 2 =, y 2 =. Gjeni pikën e kundërt. Llogaritni pikën ku k =3.

18. Formoni një vërtetues për një mesazh binar M= 1010 bazuar në funksionet hash rreptësisht universale sipas algoritmit K 0 = 0101, K 1= (numri i biletës). Llogaritjet në terren kryhen me modul të polinomit të pareduktueshëm , b=4.

Modelet e Sistemit Kriptografik

Teksti shifror- rezultati i operacionit të kriptimit. Gjithashtu përdoret shpesh në vend të termit "kriptogram", megjithëse ky i fundit thekson vetë faktin e mesazhit që transmetohet, jo enkriptimin.

Procesi i aplikimit të një operacioni enkriptimi në një tekst shifror quhet rikriptimi.

Karakteristikat e tekstit të koduar

Duke e konsideruar tekstin e koduar si një ndryshore të rastësishme në varësi të vlerave përkatëse të rastësishme të tekstit të thjeshtë X dhe çelësit të enkriptimit Z, mund të përcaktohen vetitë e mëposhtme të tekstit të shifruar:

Vetia e kriptimit të paqartë:

Barazitë zinxhir nënkuptojnë

(nga vetia e paqartësisë së deshifrimit)

(nga parimi i pavarësisë së tekstit të thjeshtë nga çelësi dhe vetia e kriptimit të paqartë) atëherë

kjo barazi përdoret për të nxjerrë formulën e distancës së unike.

Për një kriptosistem absolutisht të besueshëm

Kjo eshte

Përdorimi për kriptanalizë

Shannon në artikullin e tij të vitit 1949 "Teoria e komunikimit në sistemet sekrete" tregoi se për disa shifra të rastësishme është teorikisht e mundur (duke përdorur burime të pakufizuara) të gjendet teksti i thjeshtë origjinal nëse dihen shkronjat e tekstit të shifruar, ku është entropia e çelësit të shifrës. , r është teprica e tekstit të thjeshtë (duke përfshirë numrin duke përfshirë shumat e kontrollit, etj.), N është madhësia e alfabetit të përdorur.

Enkriptimi- transformim i kthyeshëm i informacionit me qëllim fshehjen e tij nga personat e paautorizuar, me sigurimin, në të njëjtën kohë, të përdoruesve të autorizuar të aksesit në të. Kryesisht, kriptimi i shërben qëllimit të ruajtjes së konfidencialitetit të informacionit të transmetuar. Një tipar i rëndësishëm i çdo algoritmi të kriptimit është përdorimi i një çelësi që miraton zgjedhjen e një transformimi specifik nga grupi i atyre të mundshëm për këtë algoritëm.

Në përgjithësi, kriptimi ka dy pjesë - enkriptim dhe deshifrim.

Me ndihmën e kriptimit, sigurohen tre gjendje të sigurisë së informacionit:

· Privatësia: kriptimi përdoret për të fshehur informacionin nga përdoruesit e paautorizuar gjatë transmetimit ose ruajtjes.

· Integriteti: kriptimi përdoret për të parandaluar ndryshimin e informacionit gjatë transmetimit ose ruajtjes.

· Identifikueshmëria: kriptimi përdoret për të vërtetuar burimin e informacionit dhe për të parandaluar dërguesin e informacionit të mohojë faktin që të dhënat iu janë dërguar atyre.

Kriptimi dhe deshifrimi

Siç u tha, enkriptimi përbëhet nga dy procese reciprokisht të kundërta: enkriptimi dhe deshifrimi. Të dyja këto procese në nivelin abstrakt janë të përfaqësuara nga funksionet matematikore të cilave u imponohen kërkesa të caktuara. Matematikisht, të dhënat e përdorura në enkriptim mund të përfaqësohen në formën e grupeve mbi të cilat janë ndërtuar këto funksione. Me fjalë të tjera, supozoni se ka dy grupe që përfaqësojnë të dhëna - M dhe C; dhe secili nga dy funksionet (enkriptimi dhe deshifrimi) është një hartë e njërit prej këtyre grupeve me tjetrin.

Funksioni i enkriptimit:

Funksioni i deshifrimit:

Elementet e këtyre grupeve - ~ m dhe ~ c - janë argumentet e funksioneve përkatëse. Gjithashtu, koncepti i një çelësi është përfshirë tashmë në këto funksione. Kjo do të thotë, çelësi i kërkuar për enkriptim ose deshifrim është pjesë e funksionit. Kjo na lejon të konsiderojmë proceset e enkriptimit në një mënyrë abstrakte, pavarësisht nga struktura e çelësave të përdorur. Megjithëse, në përgjithësi, për secilin prej këtyre funksioneve, argumentet janë të dhëna dhe një çelës hyrës.

Nëse i njëjti çelës përdoret për enkriptim dhe deshifrim, atëherë një algoritëm i tillë quhet simetrik. Nëse është algoritmikisht e vështirë për të marrë çelësin e deshifrimit nga çelësi i enkriptimit, atëherë algoritmi quhet asimetrik, domethënë algoritme me çelës publik.

· Për përdorim për qëllime enkriptimi, këto funksione para së gjithash duhet të jenë reciprokisht të anasjellta.

Një karakteristikë e rëndësishme e funksionit të enkriptimit E është e tij forca kriptografike... Një vlerësim indirekt i fuqisë kriptografike është një vlerësim i informacionit të ndërsjellë midis tekstit të thjeshtë dhe tekstit të shifruar, i cili duhet të priret në zero.

Forca kriptografike e shifrës

Forca kriptografike- vetia e një shifra kriptografike për t'i rezistuar kriptanalizës, domethënë një analizë që synon studimin e shifrës për ta deshifruar atë. Për të studiuar rezistencën e kriptove të algoritmeve të ndryshme, u krijua një teori e veçantë që merr në konsideratë llojet e shifrave dhe çelësat e tyre, si dhe forcën e tyre. Themeluesi i kësaj teorie është Claude Shannon. Fuqia kriptografike e një shifre është karakteristika e tij më e rëndësishme, e cila pasqyron se sa me sukses zgjidh algoritmi problemin e kriptimit.

Çdo sistem enkriptimi, përveç atyre absolutisht të sigurt kriptografik, mund të prishet me një numërim të thjeshtë të të gjithë çelësave të mundshëm në këtë rast. Por do t'ju duhet ta zgjidhni atë derisa të gjendet çelësi i vetëm që do të ndihmojë në dekriptimin e tekstit të shifruar.

Sisteme absolutisht rezistente

Vlerësimi i Shannon-it për fuqinë kriptografike të shifrës përcakton kërkesën themelore për funksionin e enkriptimit E. Për shifrën më të fortë kriptografikisht, pasiguritë (të kushtëzuara dhe të pakushtëzuara), kur përgjohen mesazhet, duhet të jenë të barabarta për një numër të madh në mënyrë arbitrare të teksteve shifrore të përgjuara.

Kështu, një sulmues nuk do të jetë në gjendje të nxjerrë ndonjë informacion të dobishëm në lidhje me tekstin e thjeshtë nga teksti i shifruar i përgjuar. Një shifër me këtë veti quhet absolutisht rezistente.

Kërkesat për sisteme absolutisht të forta të enkriptimit:

· Një çelës gjenerohet për çdo mesazh (çdo çelës përdoret një herë).

· Çelësi është statistikisht i besueshëm (d.m.th., probabilitetet e shfaqjes së secilit prej simboleve të mundshme janë të barabarta, simbolet në sekuencën kryesore janë të pavarura dhe të rastësishme).

· Gjatësia e çelësit është e barabartë ose më e madhe se gjatësia e mesazhit.

Qëndrueshmëria e sistemeve të tilla nuk varet nga aftësitë e kriptanalistit. Megjithatë, zbatimi praktik i kriptosistemeve absolutisht të sigurta kufizohet nga konsideratat e kostos së sistemeve të tilla dhe komoditetit të tyre. Sistemet sekrete ideale kanë disavantazhet e mëposhtme:

Sistemi i enkriptimit duhet të krijohet me një njohuri jashtëzakonisht të thellë të strukturës së gjuhës së përdorur të transmetimit të mesazhit

· Struktura komplekse e gjuhëve natyrore është jashtëzakonisht komplekse dhe mund të kërkohet një pajisje jashtëzakonisht komplekse për të eliminuar tepricën e informacionit të transmetuar.

· Nëse ndodh një gabim në mesazhin e transmetuar, atëherë ky gabim rritet fuqishëm në fazën e kodimit dhe transmetimit, për shkak të kompleksitetit të pajisjeve dhe algoritmeve të përdorura.

Sistemi kriptografik i çelësit publik(ose kriptim asimetrik, shifr asimetrik) - një sistem kriptimi dhe / ose nënshkrimi elektronik (ES), në të cilin çelësi publik transmetohet përmes një kanali të hapur (d.m.th., i pambrojtur, i aksesueshëm për vëzhgim) dhe përdoret për të verifikuar ES dhe për të enkriptuar mesazhin. Një çelës privat përdoret për të gjeneruar ES dhe për të deshifruar mesazhin. Sistemet kriptografike me çelës publik tani përdoren gjerësisht në protokolle të ndryshme të rrjetit, veçanërisht në protokollet TLS dhe paraardhësin e tij SSL (në themel HTTPS), në SSH. Përdoret gjithashtu në PGP, S / MIME.

Kriptosistemet simetrike(gjithashtu kriptimi simetrik, shifrat simetrike) - një metodë kriptimi në të cilën përdoret i njëjti çelës kriptografik për kriptim dhe deshifrim. Para shpikjes së skemës së enkriptimit asimetrik, e vetmja metodë ekzistuese ishte kriptimi simetrik. Çelësi i algoritmit duhet të mbahet i fshehtë nga të dyja palët. Algoritmi i enkriptimit zgjidhet nga palët përpara fillimit të shkëmbimit të mesazheve.

Modeli matematik i sistemit të kriptimit / deshifrimit për mesazhe diskrete është një palë funksionesh

,
,

të cilat e transformojnë mesazhin
në kriptogram duke përdorur një çelës enkriptimi
dhe, anasjelltas, një kriptogram në mesazh
duke përdorur çelësin e deshifrimit ... Të dy funksionet që përcaktojnë kriptosistemin duhet të plotësojnë kërkesat e mëposhtme:

Kriptografi holandez A. Kerkhoffs (1835 - 1903) sugjeroi që fshehtësia e shifrave duhet të bazohet vetëm në fshehtësinë e çelësit, dhe jo në fshehtësinë e algoritmit të kriptimit, i cili, në fund, mund të jetë i njohur për armikun.

Nëse çelësi i enkriptimit është i barabartë me çelësin e deshifrimit, d.m.th.

= =,

atëherë thirret sistemi simetrike(me një çelës). Që të funksionojë, të njëjtat çelësa duhet të dorëzohen fshehurazi në pikat e enkriptimit dhe deshifrimit. .

Nëse
, d.m.th. çelësi i enkriptimit nuk është i barabartë me çelësin e deshifrimit, atëherë thirret sistemi i enkriptimit asimetrike(me dy çelësa). Në këtë rast, çelësi
dorëzohet në pikën e enkriptimit dhe çelësi - deri në pikën e deshifrimit. Të dy çelësat duhet të lidhen padyshim nga varësia funksionale.

, por e tillë që sipas çelësit të njohur të enkriptimit
do të ishte e pamundur të rikuperohej çelësi i deshifrimit ... Kjo do të thotë që për një sistem enkriptimi asimetrik, funksioni () duhet të jetë i vështirë për t'u llogaritur.

Ekzistojnë dy klasa kryesore të sigurisë për kriptosistemet:

Në mënyrë ideale(sigurisht) këmbëngulës ose perfekte kriptosisteme për të cilat rezistenca ndaj kriptanalizës (deshifrimit) pa e ditur çelësin nuk varet nga fuqia llogaritëse e kundërshtarit. Ata quhen teorikisht e padeshifrueshme(TNDSH) sistemet.

Në mënyrë llogaritëse kriptosisteme të forta, në të cilat rezistenca ndaj kriptanalizës varet nga fuqia e sistemit kompjuterik të kundërshtarit.

1. Sistemi i Kretës RSA

Një numër i plotë zgjidhet për kriptim N =fq q, ku fq dhe q - dy numra të mëdhenj. Mesazh M përfaqësohet nga një nga numrat

M {2,3,...,N –1}.

Formulat e kriptimit / deshifrimit janë si më poshtë:

,
,

ku K- çelësi publik i enkriptimit, k- çelësi privat i deshifrimit.

Këto dy marrëdhënie nënkuptojnë barazinë

,

e cila në aritmetikën e zakonshme kryhet nëse kK= 1, dhe në aritmetikë modulare dhe për

kK = 1 + l (N ), (*)

ku l- e tërë. Në të vërtetë, duke përdorur teoremën e Euler-it, ne kontrollojmë

,

nëse M dhe N- numrat e dyfishtë.

Raportet e konsideruara tregojnë mënyrën e formimit të çelësave. Fillimisht zgjidhen numrat e thjeshtë të rastësishëm shumë të mëdhenj. fq dhe q me një numër paksa të ndryshëm shifrash në mënyrë që produkti N = pq kishte të paktën 768 bit (sipas të dhënave të vitit 2001). Llogaritni funksionin Euler

(N ) = (fq –1)(q –1).

Barazia (*) është e barabartë me

Kk= 1 mod  ( N ),

prej nga rrjedh se të dy çelësat janë reciprokisht modulë të anasjelltë  ( N ).

Çelësi publik K zgjidhni, duke respektuar kushtet e nevojshme:

K< (N ), Gcd ( K, (N )) = 1.

Çelës privat k llogarit

k = K – 1 mod  ( N ),

duke përdorur algoritmin e Euklidit. Pas përfundimit të punës përgatitore, çelësi publik K dhe modul N vendosur në një drejtori të hapur, duke marrë masa për të siguruar pamundësinë e zëvendësimit. Numrat fq dhe q mbajtur sekret.

Vini re se kushti i thjeshtësisë reciproke të numrave M dhe N dështimi për ta bërë këtë e bën të pamundur dekodimin nuk krijon kufizime serioze. Së pari, ndër numrat më të vegjël N thyesa e numrave të njëkohshëm me Nështë e barabartë me ( fq–1)(q–1)/(pq), d.m.th. është i padallueshëm nga uniteti dhe, së dyti, kushti sigurohet lehtësisht nga një modifikim i parëndësishëm i mesazhit. Gjithashtu diploma M K nuk duhet të jetë më pak N... Nëse ky kusht nuk plotësohet, kriptogrami ka formën

dhe pa modulin e llogaritjeve mund të hapet lehtësisht, pasi K i njohur.

Natyrisht, në marrëdhëniet e konsideruara, numrat K dhe k janë të barabartë, d.m.th. çelësat mund të ndërrohen dhe të përdoren k si një çelës publik i enkriptimit, dhe K si një çelës privat deshifrimi.

Kështu, të dy çelësat RSA janë specifikuar në çifte numrash të plotë :( K, N) dhe ( k, N).

Kur autorët R. Rivest, A. Shamir, L. Adleman (Rivest, Shamir, Adleman) në 1977 propozoi kriptosistemin RSA, ata koduan frazën "ItsallGreektome", të paraqitur në formë dixhitale. Vlerat janë postuar M, K, N duke treguar se 129 shifra dhjetore N fitohet duke shumëzuar numrat 64 dhe 65-bit fq dhe q... Faktorizimi N dhe hapja e kriptogramit u krye në rreth 220 ditë vetëm në vitin 1994 pas trajnimit paraprak teorik. Puna u ndoq nga 600 vullnetarë dhe 1600 kompjuterë të lidhur në rrjet nëpërmjet internetit.

Fuqia e një sistemi me çelës publik, dhe në veçanti RSA, varet nga zgjedhja e parametrave të tij. Nëse zgjidhni regjistrin 2 N= 200 bit, atëherë faktorizimi do të kërkojë afërsisht 2.710 11 operacione, të cilat do të zgjasin disa ditë në një kompjuter personal. Nëse zgjidhni regjistrin 2 N= 664 bit, atëherë faktorizimi kërkon 1210 23 operacione. Me një shpejtësi prej 10 6 operacionesh në sekondë, faktorizimi do të marrë disa miliardë vjet.

Kështu, nëse parametrat e shifrës RSA janë zgjedhur saktë dhe moduli N marrë mjaft i madh, për shembull
, atëherë ky sistem mund të konsiderohet mjaft i qëndrueshëm. Deri më sot, nuk ka metoda për kriptanalizën e tij të suksesshme.

Zbatimi i shifrës RSA është përpunuar si në versionet softuerike ashtu edhe në ato harduerike. Përdoret nga RSA dhe për enkriptim në kartat inteligjente. Në versionin e softuerit, shkalla e kriptimit është e rendit 1 kbps, në versionin harduer - 10-50 kbps.

Shpejtësia relativisht e ulët e kriptimit dhe deshifrimit në krahasim me sistemet simetrike, bllok ose transmetimi është një pengesë e të gjitha sistemeve të enkriptimit asimetrik, përfshirë RSA.

1. Nënshkrimi dixhital

Vërtetësia e dokumentit vërtetohet tradicionalisht nga nënshkrimi i zakonshëm "letër". Forca e nënshkrimit, d.m.th. pamundësia e falsifikimit të tij nga persona të paautorizuar sigurohet nga dy kushte kryesore: së pari, veçantia e tij, bazuar në karakteristikat individuale të shkrimit të dorës, dhe së dyti, integriteti fizik i dokumentit në letër mbi të cilin është bërë nënshkrimi. Për më tepër, nënshkrimi nuk mund të falsifikohet as nga personi që verifikon vërtetësinë e saj.

Sidoqoftë, kur transmetoni dokumente përmes rrjeteve kompjuterike, është e pamundur të përdoren këto kushte, përfshirë kur transmetohen mesazhe faksimile (FAX), pasi ato mund të falsifikohen lehtësisht.

Dokumentet e transmetuara përmes rrjeteve kompjuterike janë të certifikuara me nënshkrim dixhital. Një nënshkrim dixhital zgjidh problemin e një mosmarrëveshjeje të mundshme midis dërguesit dhe marrësit, përfshirë në gjykatë, nëse ekziston një bazë ligjore për aplikimin e tij.

Një nënshkrim dixhital duhet të ketë vetitë e një nënshkrimi të rregullt dhe në të njëjtën kohë të jetë një zinxhir të dhënash që mund të transmetohen përmes rrjeteve, d.m.th. duhet të plotësojë katër kërkesat themelore të mëposhtme:

nënshkrimi dixhital duhet të jetë unik, d.m.th. askush, përveç autorit, nuk mund të krijojë të njëjtën nënshkrim, përfshirë personat që verifikojnë vërtetësinë e tij;

çdo përdorues i rrjetit, legal apo i paligjshëm, mund të verifikojë vlefshmërinë e një nënshkrimi dixhital;

nënshkruesi nuk mund të refuzojë një mesazh të vërtetuar me nënshkrimin e tij dixhital;

si zbatimi ashtu edhe verifikimi i nënshkrimit dixhital duhet të jetë mjaft i thjeshtë.

Për të përmbushur të gjitha kërkesat e mësipërme, një nënshkrim dixhital, në krahasim me një "letër", duhet të varet nga të gjitha pjesët e mesazhit dhe të ndryshojë edhe kur ndryshon një bit i mesazhit të nënshkruar. Për të zbatuar një nënshkrim dixhital të bazuar në kriptosistemet simetrike, kërkohet pjesëmarrja e një personi të besuar - një arbitri. Zbatimi i një nënshkrimi dixhital pa një arbitër është i mundur vetëm përmes përdorimit të sistemeve asimetrike.

Ekzistojnë lloje të ndryshme të nënshkrimeve dixhitale të bazuara në kriptosistemet e çelësit publik. Konsideroni një implementim të CPU-së të bazuar në kriptosistemin RSA.

Në këtë rast, përdoruesi A nënshkrimi i mesazhit M, gjeneron një çift çelësash k A ,K A dhe informon përdoruesit e rrjetit për vlerat K A dhe N... Përdoruesi tjetër A krijon një grup kontrolli

,

i cili do të jetë nënshkrimi dixhital (Fig. 17). Grupi i kontrollit i caktohet mesazhit dhe dërgohet së bashku me të.

Është e lehtë të verifikohet se në këtë rast të katër kërkesat për nënshkrimet dixhitale të formuluara më herët janë përmbushur nëse shifra RSA zgjidhet mjaftueshëm e fortë.

Sidoqoftë, sistemi i konsideruar për gjenerimin e një nënshkrimi dixhital ka dy të meta të rëndësishme:

ka një tepricë të konsiderueshme për shkak të caktimit të një grupi kontrolli, gjatësia e të cilit është e barabartë me gjatësinë e mesazhit, i cili kërkon dyfishimin e sasisë së kujtesës, kohës së transmetimit, etj .;

për mesazhe të gjata, operacioni i fuqizimit në llogaritjen e grupit të kontrollit dhe kontrollimin e tij do të marrë një kohë të papranueshme të gjatë.