algoritmi i enkriptimit rsa. Shembull i algoritmit të enkriptimit rsa

Konsideroni punën e një asimetrike RSA . Ai u propozua nga tre matematikanë Ronald Rivest ( R. Rivest), Adi Shamir ( A. Shamir) dhe Leonard Adlman ( L. Adleman) në vitin 1978.

Nën numër i thjeshtë Do të kuptojmë një numër që pjesëtohet vetëm me 1 dhe me vetveten. Euklidi, në Elementet e tij, tregoi se për çdo numër të thjeshtë ka një numër të thjeshtë më të madh, domethënë, numri i numrave të thjeshtë është i pafund.

Dëshmi. Le të themi se ekziston një numër kryesor më i madh fq, ne përcaktojmë prodhimin e të gjithë numrave të thjeshtë P=2∙3∙5∙7∙…∙fq.

Merrni parasysh numrin P+1. Ai ose vetë është një numër i thjeshtë fq ose një prodhim i numrave të thjeshtë që janë më të mëdhenj se P. Kemi ardhur në një kontradiktë, që do të thotë se numri i numrave të thjeshtë është i pafund.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Numrat e dyfishtë do t'i quajmë numra të tillë që nuk kanë pjesëtues të përbashkët, përveç 1 .

Më në fund, nën rezultatin e operacionit i mod j do të shqyrtojmë pjesën e mbetur të pjesëtimit të numrit të plotë i në j. Për të përdorur algoritmin RSA, fillimisht duhet të gjeneroni një çelës publik dhe privat duke përdorur hapat e mëposhtëm.

1. Zgjidhni dy numra të thjeshtë shumë të mëdhenj R dhe q.

2. Përcaktoni n si rezultat i shumëzimit R në q (n=p q).

3. Zgjedhim një numër të madh të rastësishëm, të cilin e quajmë d. Ky numër duhet të jetë i dyfishtë me rezultatin e shumëzimit (р – 1) · (q – 1).

4. Përcaktoni një numër të tillë e, për të cilën është e vërtetë lidhja e mëposhtme (e d) mod ((p - 1) (q - 1)) = 1.

5. Le të thërrasim numrin çelës publik e dhe n, dhe çelësi sekret janë numrat d dhe n.

Tani, për të enkriptuar të dhënat me një çelës të njohur ( e, n), bëni sa më poshtë:

– ndani tekstin e shifruar në blloqe, secila prej të cilave mund të përfaqësohet si një numër M(i);

– enkriptoni një tekst të trajtuar si një sekuencë numrash M(i) sipas formulës С(i) = (M(i) e) mod n. Për të deshifruar këto të dhëna duke përdorur çelësin sekret (d, n), ju duhet të kryeni llogaritjet e mëposhtme: M(i)=(C(i) d) mod n. Rezultati do të jetë një grup numrash M(i), të cilat janë teksti origjinal.

Algoritmi RSA bazohet në një nga teoremat e vërtetuara të Euler-it, një rast i veçantë i së cilës thotë se nëse një numër n paraqitet si dy numra të thjeshtë fq dhe q, pastaj për ndonjë x ka një barazi

x (p-1) (q-1) mod n = 1.

Për de Kriptimi RSA- mesazhet ne do të përdorim këtë formulë. Për ta bërë këtë, ne i ngremë të dy pjesët e tij në fuqi (- y):

(x (- y) (p-1) (q-1)) mod n= 1 (-y) = 1.

Tani shumëzojini të dyja pjesët e tij me x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Le të kujtojmë tani se si u krijuan çelësat publikë dhe privatë. Ne ishim duke zgjedhur d sikurse

e d+(p-1)(q-1) y = 1,

e d = (-y)(p-1)(q-1)+1.

Prandaj, në shprehjen e fundit të paragrafit të mëparshëm, mund ta zëvendësojmë eksponentin me një numër (e d). marrim (x e d) mod n = x. Për të lexuar një mesazh c i = ((m i) e) mod n mjafton ta ngremë në pushtet d modul m:

((c i) d) mod n = ((m i) e d) mod n = m i .

Këtu është një shembull i thjeshtë i përdorimit të metodës RSA për të enkriptuar mesazhin "CAB". Për thjeshtësi, ne do të përdorim numra shumë të vegjël (numrat e mëdhenj përdoren në praktikë).

1. Zgjidhni p= 3i q= 11.

2. Përcaktoni n= 3· 11=33.

3. Gjeni (р–1) (q–1)= 20. Si d zgjidhni çdo numër që është relativisht i thjeshtë me 20, për shembull d= 3.

4. Zgjidhni një numër e. Çdo numër për të cilin relacioni është i kënaqur mund të merret si numër i tillë (e 3) mod 20 = 1,
për shembull 7.

5. Le të paraqesim mesazhin e koduar si një sekuencë numrash të plotë në rangun 0...32. Lëreni letrën A përfaqësohet nga numri 1, shkronja V- numri 2 dhe shkronja ME- numri 3. Atëherë mesazhi mund të përfaqësohet si një sekuencë numrash 312. Le ta kodojmë mesazhin duke përdorur çelësin (7, 33):

C(1)=(Z 7) mod 33 = 2187 mod 33 = 9,

C(2) = (1 7) mod 33 = 1 mod 33 = 1,

S(Z) = (2 7) mod 33 = 128 mod 33 = 29.

6. Le të përpiqemi të deshifrojmë mesazhin (9, 1, 29), të marrë si rezultat i enkriptimit me një çelës të njohur, bazuar në çelësin sekret (3, 33):

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

M(2) = (1 3) mod 33 = 1 mod 33 = 1,

M(Z) = (29 3) mod 33 = 24389 mod 33 = 2.

Kështu, si rezultat i deshifrimit të mesazhit, fitohet mesazhi origjinal "CAB".

Fuqia kriptografike e algoritmit RSA bazohet në supozimin se është jashtëzakonisht e vështirë të përcaktohet çelësi sekret nga një çelës publik i njohur, pasi për këtë është e nevojshme të zgjidhet problemi i ekzistencës së pjesëtuesve të numrave të plotë. Kjo detyrë aktualisht nuk pranon një zgjidhje efikase (polinomike). Në këtë drejtim, për çelësat që përbëhen nga 200 shifra binare (domethënë, numra të tillë rekomandohen të përdoren), metodat tradicionale për gjetjen e pjesëtuesve kërkojnë një numër të madh operacionesh (rreth 10 23).

Kriptosistemi RSA përdoret në një shumëllojshmëri të gjerë platformash dhe në shumë industri. Ai është i përfshirë në shumë produkte komerciale, numri i të cilave po rritet vazhdimisht. Ajo është duke u përdorur OS Microsoft, Apple, Sun dhe Novell. Në harduer, algoritmi RSA përdoret në telefona të sigurt, në kartat e rrjetit Ethernet, në kartat inteligjente dhe përdoret gjerësisht në pajisjet kriptografike Zaxus (Rasal). Përveç kësaj, algoritmi përfshihet në të gjitha protokollet kryesore për komunikime të sigurta në internet, duke përfshirë S/MIME, SSL dhe S/WAN, dhe përdoret nga shumë institucione, si agjencitë qeveritare, shumica e korporatave, laboratorët qeveritarë dhe universitetet.

Teknologjia e enkriptimit RSA BSAFE përdoret nga më shumë se 500 milionë përdorues në mbarë botën. Meqenëse në shumicën e rasteve përdoret algoritmi RSA, ai mund të konsiderohet si kriptosistemi më i zakonshëm i çelësit publik në botë dhe ky numër ka një tendencë të qartë për t'u rritur me rritjen e përdoruesve të internetit.

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

Shpejtësia e modulit përdoret për kriptim dhe deshifrim. Siç kemi diskutuar tashmë në Leksionet 12-13, kur përdoret algoritmi i shpejtë, moduli i fuqizimit është i realizueshëm në kohë polinomiale. Megjithatë, gjetja e logaritmit të modulit është po aq e vështirë sa faktorizimi i një moduli numerik. Nuk ka asnjë algoritëm kohor polinom për të. Kjo do të thotë që Alice mund të enkriptojë mesazhin me çelësin publik (e) në kohë 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 do t'i duhej të llogariste rrënjën e-të të C duke përdorur aritmetikën modulare. Figura 14.5 tregon idenë pas RSA.

Oriz. 14.5.

Me fjalë të tjera, Alice përdor funksion me një drejtim(moduli i eksponencionit) me një zbrazëti të njohur vetëm për Bob. Eva nuk e njeh zbrazëtirën, kështu që ajo nuk mund ta deshifrojë mesazhin. Nëse dikush ndonjëherë gjen një algoritëm polinomial për modulin e rrënjës e-të të n-së, atëherë moduli i fuqizimit n nuk do të jetë më një funksion njëkahësh.

Procedura

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

RSA përdor modulin e fuqisë për kriptim/deshifrim. Për të sulmuar tekstin privat, Eva duhet të llogarisë

Dy struktura algjebrike

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

Unazat e enkriptimit/deshifrimit. Kriptimi dhe deshifrimi bëhet duke përdorur një unazë komutative me dy veprime aritmetike: mbledhje dhe shumëzim. Në RSA, kjo unazë është publike sepse moduli n është publik. Çdokush mund t'i dërgojë një mesazh Bobit duke përdorur këtë unazë enkriptimi.

Grupet kryesore të gjenerimit. RSA përdor grupin shumëzues për të gjeneruar çelësa. Grupi mbështet vetëm shumëzimin dhe ndarjen (inversioni shumëfishues), të cilat kërkohen për të gjeneruar çelësa publikë dhe privatë. Ky grup duhet të fshihet sepse moduli i tij është sekret. Do të shohim që nëse Eva gjen këtë modul, ajo mund të sulmojë lehtësisht sistemin kriptografik.

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

Gjenerimi kryesor

Bob përdor hapat e treguar në Algoritmin 14.2 për të gjeneruar çelësat e tij publikë dhe privatë. Pas gjenerimit të çelësave, Bob deklaron tuplen (e, n) si çelësin e tij të aksesit publik: Bob ruan d si çelësin e tij privat. Bob mund të refuzojë p, q dhe ; ata nuk mund të ndryshojnë çelësin e tij privat pa ndryshuar modulin. Për siguri, madhësia e rekomanduar për çdo p ose q të thjeshtë është 512 bit (pothuajse 154 shifra dhjetore). Kjo specifikon madhësinë e njësisë, n është 1024 bit (309 shifra).

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

Enkriptimi

Ç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 të kohës polinom, siç tregohet në Algoritmin 14.3. Algoritmi i fuqizimit të shpejtë u diskutua në leksionet 12-13. Madhësia e tekstit burim duhet të jetë më e vogël se n; nëse madhësia e tekstit origjinal është më e madhe, atëherë duhet të ndahet në blloqe.

Kriptosistemi RSA në çdo cikël të enkriptimit konverton një bllok binar të tekstit të thjeshtë m me gjatësi (n), të konsideruar si një numër i plotë, në përputhje me formulën: c = me (mod n).

Në këtë rast, n = pq , ku p dhe q janë numra të thjeshtë të rastit me kapacitet të madh, të cilët shkatërrohen pas formimit të modulit dhe çelësave. Çelësi publik përbëhet nga një çift numrash e dhe n . Nënçelësi e zgjidhet si një numër mjaft i madh nga diapazoni 1< e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Më tej, duke zgjidhur ekuacionin xe + yφ(n) = 1 në numra të plotë x, y, vendosim d = x, d.m.th. ed = 1(j(n)). Në këtë rast, për të gjithë m, relacioni m ed = m(n) , prandaj, njohja e d-së lejon që të deshifrohen kriptogramet.

Për të siguruar që informacioni është i mbrojtur në mënyrë të sigurt, sistemet me çelës publik kanë dy kërkesat e mëposhtme.

1. Transformimi i tekstit burim duhet të përjashtojë rikuperimin e tij bazuar në çelësin publik.

2. Përkufizimi çelës privat i bazuar në të hapur duhet të jetë edhe llogaritarisht i parealizueshëm. Në këtë rast, një vlerësim i saktë më i ulët i kompleksitetit (numrit të operacioneve) të deshifrimit të shifrës është i dëshirueshëm.

Algoritmet e enkriptimit të çelësit publik përdoren gjerësisht në sistemet moderne të informacionit.

Konsideroni ndërtimin e kriptosistemit RSA duke përdorur një shembull të thjeshtë.

1. Zgjidhni p = 3 dhe q = 11.

2. Përcaktoni n = 3 ∙ 11 = 33.

3. Gjeni j(n) = (p – 1)(q – 1) = 20.

5. Zgjidhni një numër d që plotëson 7d = 1 (mod 20).

Është e lehtë të shihet se d = 3 (mod 20).

Le të paraqesim mesazhin e koduar si një sekuencë numrash të plotë duke përdorur korrespondencën: A = 1, B = 2, C = 3, ..., Z = 26. Meqenëse madhësia(n) = 6 , atëherë kriptosistemi ynë është në gjendje të kodojë shkronjat e alfabetit latin, të konsideruara si blloqe.Le të publikojmë çelësin publik (e, n) = (7, 33) dhe të ftojmë pjesëmarrësit e tjerë në sistemin sekret të komunikimit të kodojnë mesazhet e dërguara në adresën tonë Le të jetë një mesazh i tillë CAB , e cila në kodimin që kemi zgjedhur merr formën (3, 1, 2) Dërguesi duhet të kodojë çdo bllok dhe të dërgojë mesazhin e koduar në adresën tonë:

RSA(C) = RSA(3) = 3 7 = 2187 = 9 (mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA (B) = RSA (1) = 2 7 = 128 = 29 (mod 33).

Pasi të kemi marrë mesazhin e koduar (9, 1, 29), ne mund ta deshifrojmë atë bazuar në çelësin sekret (d, n) = (3, 33), duke e ngritur çdo bllok në fuqinë d = 3:

9 3 = 729 = 3 (mod 33);
1 3 = 1 (mod 33);
29 3 = 24389 = 2 (mod 33).

Për shembullin tonë, është e lehtë të gjesh çelësin sekret me forcë brutale. Në praktikë, kjo është e pamundur, sepse vlerat e mëposhtme të madhësisë(n) rekomandohen aktualisht për përdorim praktik :

· 512–768 bit - për individë;

· 1024 bit - për informacion komercial;

· 2048 bit - për informacion të klasifikuar.

Një shembull i zbatimit të algoritmit RSA është paraqitur në listat 18.1 dhe 18.2 (përpiluesit - Delphi, FreePascal).

Listimi 18.1. Një shembull i zbatimit të algoritmit RSA në Pascal

programi Rsa;
(CONSOLE $APPTYPE)
($IFDEF FPC)
($MODE DELPHI)
($ENDIF)

përdor SysUtils, uBigNumber;

//Gjeneruesi i numrave të rastësishëm

vart: grup i Byte;
var pos: Integer;
var cbox: grupi i Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);

procedura InicMyRandom;
var i: Numër i plotë;
vars:string;
fillojnë
WriteLn("Fut pak tekst për të inicializuar gjeneratorin
numra të rastit (deri në 256 karaktere):");
LexoniLn(t);
i: = 1;
nderkohe une<=255) and (i<=Length(s)) do

Hyrje 3

Pjesa kryesore 5

1 Historia e krijimit 5

2 Përshkrimi i algoritmit 5

2.1 Gjenerimi i çelësave 6

2.2 Enkriptimi dhe deshifrimi 6

2.3 Shembulli i përdorimit 7

Përfundimi 9

Lista e burimeve të përdorura 10

Prezantimi

Kriptografia është një sistem i veçantë për ndryshimin e shkrimit të zakonshëm, që përdoret për ta bërë tekstin të kuptueshëm vetëm për një numër të kufizuar njerëzish që e njohin këtë sistem.

Kriptografia është shkenca e mbrojtjes së informacionit duke përdorur metoda matematikore.

Kriptografia moderne përfshin:

kriptosisteme simetrike;

kriptosisteme asimetrike;

sistemet e nënshkrimit elektronik dixhital (EDS);

funksionet hash;

menaxhim kyç;

marrja e informacionit të fshehur;

kriptografia kuantike.

Kriptimi simetrik - Algoritmet quhen simetrike, në të cilat i njëjti çelës sekret (i njohur vetëm për dërguesin dhe marrësin) përdoret për enkriptim dhe deshifrim.

Algoritmet e zakonshme të kriptimit simetrik:

AES (Advanced Encryption Standard) - Standardi amerikan i enkriptimit;

GOST 28147-89 - standardi i brendshëm i kriptimit të të dhënave;

DES (eng. Data Encryption Standard) - standard i enkriptimit të të dhënave në SHBA deri në AES;

3DES (Triple-DES, trefishtë DES);

IDEA (Anglish International Data Encryption Algorithm);

SEED - Standardi Korean i Enkriptimit të të Dhënave;

Camellia është një shifër e çertifikuar për përdorim në Japoni;

XTEA është algoritmi më i lehtë për t'u zbatuar.

Algoritmet kriptografike asimetrike janë krijuar kryesisht për të eliminuar pengesën kryesore të kriptosistemeve simetrike - kompleksitetin e menaxhimit dhe shpërndarjes së çelësave.

Baza e të gjithë kriptoalgoritmeve asimetrike është kompleksiteti i lartë llogaritës i rikuperimit të tekstit të thjeshtë pa e ditur çelësin privat.

Shembuj të algoritmeve asimetrike të kriptos:

Diffie Hellmann;

RSA - Rivest, Shamir, Adelman - bazuar në kompleksitetin e detyrës së faktorizimit të numrave të mëdhenj në një kohë të shkurtër;

DSA - Algoritmi i Nënshkrimit Dixhital, standardi amerikan;

GOST R 34.10 - 94, 2001, Standardet RF.

Në këtë ese, ne do të shqyrtojmë në detaje algoritmin asimetrik të kripto-kriptimit - algoritmin RSA.

Pjesa kryesore

Algoritmi RSA (një shkurtim për Rivest, Shamir dhe Adleman) është një algoritëm kriptografik me çelës publik i bazuar në kompleksitetin llogaritës të problemit të faktorizimit të numrit të madh. Kriptosistemi RSA ishte sistemi i parë i përshtatshëm si për enkriptim ashtu edhe për nënshkrim dixhital.

Historia e krijimit

Botuar në nëntor 1976, artikulli i Whitfield Diffie dhe Martin Hellman "New Directions in Cryptography" revolucionarizoi sistemet kriptografike duke hedhur themelet për kriptografinë me çelës publik. Algoritmi Diffie-Hellman i zhvilluar më pas i lejoi dy palëve të merrnin një çelës sekret të përbashkët duke përdorur një kanal komunikimi të pasigurt. Megjithatë, ky algoritëm nuk e zgjidhi problemin e vërtetimit. Pa fonde shtesë, përdoruesit nuk mund të ishin të sigurt se me kë kishin krijuar saktësisht çelësin e përbashkët sekret.

Pas studimit të këtij dokumenti, tre shkencëtarë Ronald Linn Rivest, Adi Shamir dhe Leonard Adleman nga Instituti i Teknologjisë i Massachusetts (MIT) u përpoqën të gjenin një funksion matematikor që do të lejonte modelin e Whitfield Diffie dhe Martin Hellman të një sistemi kriptografik me çelës publik. Pasi punuan në më shumë se 40 mundësi, ata arritën të gjenin një algoritëm të bazuar në ndryshimin se sa e lehtë është të gjesh numrat e parë të mëdhenj dhe sa e vështirë është të faktorizosh produktin e dy numrave të mëdhenj, të cilët më vonë u bënë të njohur si RSA. Sistemi u emërua sipas shkronjave të para të emrave të krijuesve të tij.

Përshkrimi i algoritmit

Hapi i parë në çdo algoritëm asimetrik është krijimi i një çifti çelësash publik/privat dhe shpërndarja e çelësit publik "në mbarë botën".

Krijimi i çelësave

Për algoritmin RSA, faza kryesore e gjenerimit përbëhet nga operacionet e mëposhtme:

Numri quhet eksponent i hapur

Kriptimi dhe deshifrimi

Supozoni se dërguesi dëshiron t'i dërgojë një mesazh marrësit.

Mesazhet janë numra të plotë në rangun nga 0 në , d.m.th. . Figura 1 tregon një diagram të algoritmit RSA.

Figura 1 - Skema e algoritmit RSA

Algoritmi i dërguesit:

Algoritmi i Marrësit:

Ekuacionet (1) dhe (2), mbi të cilat bazohet skema RSA, përcaktojnë transformimet reciproke të anasjellta të grupit.

Shembull përdorimi

Tabela 1 tregon një shembull të përdorimit të algoritmit RSA. Dërguesi dërgoi mesazhin e koduar "111111" dhe marrësi e deshifroi atë duke përdorur çelësin e tij privat.

Tabela 1 - Ekzekutimi me faza i algoritmit RSA

konkluzioni

Në këtë abstrakt, algoritmi i enkriptimit asimetrik RSA u shqyrtua në detaje. U përshkrua historia e krijimit të saj, u përshkruan algoritmet për krijimin e çelësave, enkriptimin dhe deshifrimin. Është paraqitur edhe një shembull i përdorimit praktik të algoritmit RSA.

Lista e burimeve të përdorura

Semenov Yu.A. Protokollet e Internetit // M.: Prospekt, 2011. - 114 f.

Belyaev A.V. Metodat dhe mjetet e mbrojtjes së informacionit // ChF SPbGTU, 2010. - 142 f.

Venbo M. Kriptografia moderne. Teoria dhe praktika // M.: Williams, 2005. - 768 f.

Schneier B. Kriptografia e aplikuar. Protokollet, algoritmet, tekstet burimore // M.: Triumph, 2002. - 816 f.

Algoritmi RSA // Burimi në internet: http://ru.wikipedia.org/wiki/Rsa

Skema Rivest-Shamir-Adleman (RSA) është aktualisht e vetmja skemë e pranuar gjerësisht e enkriptimit të çelësit publik në praktikë.

Skema RSA është një shifër bllok në të cilën si teksti i thjeshtë ashtu edhe teksti shifror janë numra të plotë midis 0 dhe P- 1 për disa P.

Teksti i thjeshtë është i koduar në blloqe, secila prej të cilave përmban një vlerë binare më të vogël se një numër i caktuar P. Kjo do të thotë që gjatësia e bllokut nuk duhet të kalojë log2(“). Në praktikë, gjatësia e bllokut zgjidhet e barabartë me 2 k copa ku 2k Skema e zhvilluar nga Rivest, Shamir dhe Adleman bazohet në shprehjet e fuqisë. Kriptimi dhe deshifrimi për bllokun e tekstit të thjeshtë M dhe bllokun e tekstit të shifruar C mund të përfaqësohen si formulat e mëposhtme:

Si dërguesi ashtu edhe marrësi duhet ta dinë vlerën P. Dërguesi e di kuptimin e, dhe vetëm marrësi e di vlerën d. Kështu, kjo skemë është një algoritëm i enkriptimit të çelësit publik KU= (e, p), dhe çelësi privat KR = (d, p).

Që ky algoritëm të përdoret për enkriptimin e çelësit publik, duhet të plotësohen kërkesat e mëposhtme:

Duhet të ketë vlera e, d dhe P,çfarë M ed = M(mod P) për të gjithë M n.

Duhet të jetë relativisht e lehtë për t'u llogaritur IVT dhe Nga c1 për të gjitha vlerat e M p.

Duhet të jetë pothuajse e pamundur të përcaktohet d në dispozicion saj f.

Le të analizojmë së pari kërkesën e parë dhe të shqyrtojmë pjesën tjetër më vonë. Është e nevojshme të gjendet një lidhje e formës

Këtu, përfundimi nga teorema e Euler-it përshtatet në mënyrë të përkryer: për çdo dy numra të tillë të thjeshtë R dhe q dhe të tillë çdo dy numra të plotë Pete,çfarë n=pqn0 dhe një numër i plotë arbitrar për të mbahen marrëdhëniet e mëposhtme:

ku φ(n) është funksioni i Euler-it vlera e të cilit është e barabartë me numrin e numrave të plotë pozitivë më pak se P dhe coprime me P.

Në rastin e thjeshtë R dhe q kemi f (pq) - (fq - 1 ) (q - një). Prandaj, raporti i kërkuar merret me kusht

Kjo është e barabartë me marrëdhëniet e mëposhtme:

ato. saj d janë reciprokisht modul invers φ(n). Vini re se, sipas rregullave të aritmetikës në klasat e mbetjeve, kjo mund të ndodhë vetëm kur d(dhe për këtë arsye e)është koprome me φ(u). Në shënimin ekuivalent (f(/7), d)=.

Tani kemi gjithçka për të përfaqësuar skemën RSA. Komponentët e qarkut janë:

R dhe q- dy numra të thjeshtë (të fshehtë, të zgjedhur);

p-pq(e hapur, e llogaritur);

të tilla e, që (f(i), e)= 1,1 e

d = e l(mod f(/?)) (sekret, i llogaritur).

Çelësi privat përbëhet nga (d,n), dhe hapet nga (e, p). Supozoni se përdoruesi A ka publikuar çelësin e tij publik, dhe tani përdoruesi B do t'i dërgojë atij një mesazh M.

Pastaj përdoruesi B llogarit mesazhin e koduar

Pasi ka marrë këtë tekst shifror, përdoruesi A e deshifron atë duke e llogaritur

Ka kuptim të jepet këtu arsyetimi për këtë algoritëm. U zgjodhën saj d sikurse

Pra, duket si kc>(n)+. Por nga përfundimi i teoremës së Euler-it, për çdo dy numra të tillë të thjeshtë R dhe ku numra të plotë n = pqn M se O marrëdhëniet janë përmbushur

Kështu që

Tani kemi

Tabela 10.1 përmbledh algoritmin RSA, dhe në fig. 10.1 tregon një shembull të zbatimit të tij. Në këtë shembull, çelësat llogariten si më poshtë:

• 1. Zgjidhen dy numra të thjeshtë: p-7 wq- 17.
• 2. Llogaritur p = pq= 7 x 17=119.
• 3. Njehsoni f (n) - (p -) (q - 1) = 96.
• 4. E zgjedhshme e, koprim me φ (P)= 96 dhe më pak se f(i); në këtë rast = 5.
• 5. Kjo është e përcaktuar d,çfarë de= 1 (mod 96) dhe d 96. Vlera përkatëse do të ishte d= 77, sepse 77 x 5 = 385 = 4 x 96 + 1.
• 6. Rezultati është një çelës publik KU= (5, 119) dhe një çelës privat KR = (77, 119).

Ky shembull tregon përdorimin e këtyre çelësave me hyrjen e tekstit të thjeshtë M = 19. Për kriptim, 19 ngrihet në fuqinë e pestë, duke rezultuar në 2,476,099. Pjestimi me 119 rezulton në një mbetje prej 66. Prandaj, 19 119) dhe kështu teksti i koduar do të jetë 66. Pas deshifrimit, rezulton se

Oriz. 10.1.

Tabela 10.1