3) izračunava se y = a x mod (p);

4) odabran je javni ključ CPU provjere: ( p, a, y) i tajni ključ za stvaranje CPU-a: x.

Oblikovanje procesora

Ako korisnik A želi potpisati poruku m, predstavljenu kao broj koji pripada Zp, tada izvodi sljedeće operacije:

1) generira tajni broj k: 1 ≤ k≤ p - 2; gcd ( k, p - l) = 1, gdje je gcd gcd

2) izračunava r = a k mod (p);

3) izračunava k -1 mod (p - 1);

4) izračunava s = k -l (m - xr) mod (p - l);

5) Formira CPU S na poruku m kao par brojeva S = (r, t).

CPU provjera (verifikacija)

Kako bi provjerio potpis S koji je napravio A pod porukom M, svaki korisnik poduzima sljedeće korake:

1) dobiva javni ključ A: (p, a, y);

2) provjerava da je 1 ≤ r ≤ p - 1, a ako ne uspije, onda odbija CPU;

3) izračunava V 1 = y r r s mod (p);

4) izračunava V 2 = a m mod (p);

5) prihvaća CPU kao ispravan pod uvjetom da je V 1 = V 2

Otpornost CPU-a Na temelju ElGamalova COP-a

1) Napadač može pokušati krivotvoriti potpis na svoju poruku M na sljedeći način: generirati slučajni broj k, izračunati r = a k mod (p), a zatim pokušati pronaći s = k - l (m - xr) mod (p - l).

Međutim, da bi izvršio posljednju operaciju, mora znati a,što se ne može izračunati s odgovarajućim izborom parametara procesora.

3) Treba napomenuti da ako nije ispunjeno korak 2 algoritma provjere CPU-a tada napadač može ispravno potpisati bilo koju poruku po svom izboru, pod uvjetom da ima neku drugu poruku s ispravnim CPU-om na raspolaganju. Dakle, pri odabiru modula R, koji u binarnom prikazu ima duljinu od oko 768 bita, pruža dobru stabilnost CPU-a, a da bi se osigurala dugoročna stabilnost preporučljivo je povećati na 1024 bita.

Zahtjevi za kriptografski HF

1. Jednosmjernost, kada je za poznati hash h računski neizvedivo (tj. zahtijeva neostvarivo velik broj operacija) pronaći barem jednu vrijednost x za koju, to jest, h (x) ispada jednosmjerna funkcija (ONF).

2. Slaba otpornost na sudar, kada je za dane x, h (x) = h računski neizvedivo pronaći drugu x ’vrijednost koja zadovoljava jednadžbu h (x’) = h.

3. Jaka otpornost na sudar, kada je računski neizvedivo pronaći par argumenata x, x ’za koje vrijedi relacija h (x) = h (x’).

Ispravak ranjivosti

Denning i Sacco su predložili korištenje vremenskih oznaka u porukama kako bi se spriječili napadi poput gore opisanog. Označimo takvu oznaku slovom t. Razmotrite opciju da popravite ranjivost:

PKI komponente

· Tijelo za izdavanje certifikata (CA)- dio sustava javnog ključa koji izdaje certifikat za provjeru prava korisnika ili sustava koji podnose zahtjev. Izrađuje certifikat i potpisuje ga privatnim ključem. Zbog svoje funkcije stvaranja certifikata, CA je središnji dio PKI-ja.

· Repozitorijum certifikata... Repozitorijum za važeće certifikate i popise opoziva certifikata (CRL). Aplikacije provjeravaju valjanost certifikata i razinu pristupa koju odobrava provjeravanjem uzorka sadržanog u repozitoriju.

· Poslužitelj za oporavak ključeva- poslužitelj koji izvodi automatski oporavak ključa, ako je ova usluga instalirana.

· Aplikacija s PKI-om- aplikacije koje mogu koristiti PKI alate za sigurnost. PKI upravlja digitalnim certifikatima i ključevima koji se koriste za šifriranje informacija na web poslužiteljima prilikom korištenja e-pošte, razmjene poruka, pregledavanja Interneta i prijenosa podataka. Neke aplikacije mogu koristiti PKI izvorno, dok druge zahtijevaju od programera da ih modificiraju.

· Registracijsko tijelo- modul odgovoran za registraciju korisnika i prihvaćanje zahtjeva za certifikatom.

· Sigurnosni poslužitelj- Poslužitelj koji upravlja pristupom korisnika, digitalnim certifikatima i jakim odnosima u PKI okruženju. Sigurnosni poslužitelj centralno upravlja svim korisnicima, certifikatima, CA vezama, izvješćima i provjerava popis opoziva certifikata.

PKI funkcije

· Registracija- proces prikupljanja podataka o korisniku i provjere njihove autentičnosti, koji se zatim koriste prilikom registracije korisnika, u skladu sa sigurnosnim pravilima.

· Izdavanje potvrde... Nakon što CA potpiše certifikat, on se izdaje podnositelju zahtjeva i/ili šalje u spremište certifikata. CA na certifikate stavlja razdoblje valjanosti, što zahtijeva periodično obnavljanje certifikata.

· Opoziv certifikata... Certifikat može postati nevažeći prije isteka iz različitih razloga: korisnik je napustio tvrtku, promijenio ime ili ako je njegov privatni ključ ugrožen. U tim okolnostima, CA će opozvati certifikat unošenjem njegovog serijskog broja u CRL.

· Oporavak ključa... Dodatna PKI funkcija omogućuje vam oporavak podataka ili poruka u slučaju gubitka ključa.

· Upravljanje životnim ciklusom- Kontinuirana podrška certifikata u PKI-u, uključujući obnavljanje, obnavljanje i arhiviranje ključeva. Te se funkcije izvode povremeno, a ne kao odgovor na ad hoc zahtjeve. Automatizirano upravljanje ključevima najvažnija je značajka za velike PKI-ove. Ručno upravljanje ključevima može ograničiti skalabilnost PKI-ja.

Osnovne definicije

· Popisi opoziva certifikata (CRL-ovi)- popis poništenih certifikata. Otkazivanje može biti zbog promjene posla, krađe privatnog ključa ili drugih razloga. PKI aplikacije mogu provjeriti korisničke certifikate u odnosu na CRL prije odobravanja pristupa tom certifikatu.

· Digitalni certifikat / Certifikat X.509... Struktura podataka koja se koristi za povezivanje određenog modula s određenim javnim ključem. Digitalni certifikati koriste se za provjeru autentičnosti korisnika, aplikacija i usluga te za kontrolu pristupa (autorizacija). Digitalne certifikate izdaju i distribuiraju CA-ovi.

· Digitalna omotnica... Metoda korištenja šifriranja javnog ključa za sigurnu distribuciju tajnih ključeva koji se koriste u simetričnoj enkripciji i za slanje šifriranih poruka. Problem distribucije ključa povezan sa simetričnom enkripcijom uvelike je smanjen.

· Digitalni potpis... Metoda korištenja šifriranja javnog ključa kako bi se osigurao integritet podataka i nemogućnost odbijanja paketa. Šifrirani blok informacija, nakon dešifriranja od strane primatelja, identificira pošiljatelja i potvrđuje sigurnost podataka. Na primjer: dokument je "komprimiran", HASH je šifriran korištenjem privatnog ključa pošiljatelja i priložen dokumentu (u stvari, to znači prilaganje "otiska prsta" ovog dokumenta). Primatelj koristi javni ključ za dešifriranje primljene poruke u stanje "stiskanja", koje se zatim uspoređuje s "stiskanjem" dobivenim nakon što je poslani dokument "komprimiran". Ako se oba "stiska" ne podudaraju, to znači da je dokument promijenjen ili oštećen tijekom prijenosa.

· Kriptografija javnog ključa... Postoje dvije glavne vrste enkripcije: javni ključ i tajni (simetrični) ključ. Šifriranje javnog ključa koristi par ključeva: otvoreni, t.j. slobodno dostupan, i njegov odgovarajući privatni ključ, poznat samo određenom korisniku, aplikaciji ili usluzi koja posjeduje ovaj ključ. Ovaj par ključeva je povezan na način da se ono što je šifrirano privatnim ključem može dešifrirati samo javnim ključem i obrnuto.

· Simetrična enkripcija (zajednička tajna kriptografija)... Postoje dvije glavne vrste enkripcije: javni ključ i tajni (simetrični) ključ. Kod simetrične enkripcije primatelj i pošiljatelj koriste isti ključ za šifriranje i dešifriranje. To znači da mnogi korisnici moraju imati iste ključeve. Očito, dok korisnik ne dobije ključ, enkripcija nije moguća, a distribucija ključa preko mreže nije sigurna. Druge metode distribucije, poput posebne kurira, skupe su i spore.

· RSA algoritam je prvi sustav šifriranja s javnim ključem nazvan po svojim izumiteljima: Ronaldu Rivestu, Adiju Shamiru i Leonardu Adlemanu.

· Pametna kartica. Uređaj sličan kreditnoj kartici s ugrađenom memorijom i procesorom koji se koristi za sigurno pohranjivanje korisničkih ključeva i potvrda i drugih informacija (obično društvenih i medicinskih).

· Digitalne vjerodajnice. U okviru PKI tehnologije, ISO / TS 17090-1 standard definira ovaj pojam kao kriptografski zaštićeni objekt koji može sadržavati pojedinačne korisničke ključeve, certifikate pojedinačnih ključeva, certifikate CA-ova strukture PKI korisnika, popis pouzdanih CA-ova, i drugi parametri vezani uz korisničku domenu - identifikator korisnika, nazivi primijenjenih kriptografskih algoritama, vrijednosti početnih vrijednosti itd. Vjerodajnice se mogu postaviti na hardverski ili softverski medij.

Princip rada

Certifikati se obično koriste za razmjenu šifriranih podataka preko velikih mreža. Kriptosustav javnog ključa rješava problem razmjene tajnih ključeva između sudionika u sigurnoj razmjeni, ali ne rješava problem povjerenja u javne ključeve. Pretpostavimo da Alice, želeći primati šifrirane poruke, generira par ključeva od kojih jedan (javni) na neki način objavljuje. Svatko tko joj želi poslati povjerljivu poruku ima mogućnost da je šifrira ovim ključem i budi siguran da će samo ona (budući da samo ona ima odgovarajući tajni ključ) moći pročitati ovu poruku. Međutim, opisana shema ni na koji način ne može spriječiti napadača Davida da stvori par ključeva i objavi svoj javni ključ, provodeći ga kao Alisin ključ. U tom slučaju David će moći dešifrirati i pročitati barem onaj dio poruka namijenjenih Alice, a koje su greškom šifrirane njegovim javnim ključem.

Ideja iza certifikata je da postoji treća strana kojoj druge dvije strane u razmjeni informacija vjeruju. Pretpostavlja se da je malo takvih trećih strana, a njihovi javni ključevi su svima na neki način poznati, na primjer, pohranjeni u operacijskom sustavu ili objavljeni u zapisnicima. Tako se lako otkriva krivotvorenje javnog ključa treće strane.

Kriptografski sustavi s javnim ključevima za šifriranje omogućuju korisnicima siguran prijenos podataka preko nezaštićenog kanala bez prethodne pripreme. Takvi kriptosustavi moraju biti asimetrični u smislu da pošiljatelj i primatelj imaju različite ključeve, a niti jedan od njih se ne može zaključiti iz drugog računanjem. U tim su sustavima faze šifriranja i dešifriranja razdvojene i poruka je zaštićena bez da se ključ za šifriranje učini tajnim, budući da se ne koristi u dešifriranju.

Koristeći javni ključ za šifriranje, korisnik i šifrira poruku M i šalje je korisniku j putem nezaštićenog kanala za prijenos podataka. Samo korisnik j može dešifrirati da povrati M, budući da samo on zna tajni ključ za dešifriranje.

Među asimetričnim (otvorenim) kriptosustavima najrašireniji je RSA kriptografski sustav. U ovom sustavu primatelj poruke bira dva velika prosta broja p i q tako da je proizvod n = pq izvan računalnih mogućnosti. Izvorna poruka M može biti proizvoljne duljine u rasponu od 1

Izvorni tekst M obnavlja se iz šifriranog C obrnutom transformacijom

Primatelj odabire e i d kako bi bili ispunjeni sljedeći uvjeti:

gdje je Eulerova funkcija jednaka (p - 1) (q - 1);

(a, b) je najveći zajednički djelitelj dvaju brojeva.

To jest, e i d u multiplikativnoj skupini su recipročni u aritmetičkom modusu ostatka.

Očito, glavna svrha kriptografskog otkrivanja je određivanje tajnog ključa (eksponent na C - vrijednost d).

Postoje tri poznata načina na koje bi kriptoanalitičar mogao otkriti vrijednost d iz otvorenih informacija o paru (e, n).

Faktorizacija n

Prafaktorizacija od n omogućuje nam da izračunamo funkciju, a time i skrivenu vrijednost d, koristeći jednadžbu

Prikazani su različiti algoritmi za takvu dekompoziciju. Najbrži algoritam trenutno poznati može faktorizirati n u koracima po redu

Analiza ovog izraza pokazuje da će broj n s 200 decimalnih znamenki biti dobro zaštićen od poznatih metoda proširenja.

Izravno računanje

Drugi mogući način kriptoanalize povezan je s izravnim izračunom Eulerove funkcije bez faktoriranja n. Izravno računanje nije nimalo jednostavnije od faktoriziranja n, budući da onda olakšava faktoriziranje n. To se može vidjeti iz sljedećeg primjera. Neka bude

x = p + q = n + 1 -,

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

Znajući, možete odrediti x i, prema tome, y, znajući x i y, prosti p i q mogu se odrediti iz sljedećih odnosa:

Izravna procjena d

Treća metoda kriptoanalize je izravno izračunavanje vrijednosti d. Obrazloženje ove metode temelji se na činjenici da ako je d odabran dovoljno velik da jednostavno nabrajanje bude neprihvatljivo, izračunavanje d nije jednostavnije od faktoriranja n, budući da ako je d poznato, onda se n lako faktorizira. To se može prikazati na sljedeći način. Ako je d poznat, onda možemo izračunati višekratnik Eulerove funkcije koristeći uvjet

gdje je k proizvoljan cijeli broj.

Možete faktorizirati n koristeći bilo koji višekratnik. Dešifrator bi, s druge strane, mogao pokušati pronaći neku vrijednost d "koja je ekvivalentna skrivenoj vrijednosti d korištenoj u dizajnu šifre. Ako takvih d ima mnogo", tada se grubom silom može pokušati razbiti šifra . Ali svi d" razlikuju se za faktor jednak i ako se ovaj faktor izračuna, tada se n može faktorizirati. Stoga je pronalaženje d jednako teško kao i faktoriranje n.

Dakle, glavni zadatak kriptoanalize asimetričnih enkripcijskih sustava svodi se uglavnom na problem faktorizacije (faktorizacije). Ovaj problem je jedan od glavnih u teoriji brojeva i formuliran je na sljedeći način:

Neka nam je zadan cijeli broj n> 0, a potrebno je, ako je moguće, pronaći dva broja a i b takva da je ab = n. Zapravo postoje dva različita zadatka: prvi, nazvan test jednostavnosti, je provjeriti postoje li takvi a i b; drugi, nazvan dekompozicija, je problem njihovog pronalaženja. Razmotrimo oba ova zadatka.

Prvi deterministički test.

Ovaj test se temelji na Fermatovom Malom teoremu, koji kaže da ako je p prost broj, onda je p-1 1 (mod p) za sve a, 1

Dakle, test se sastoji u odabiru broja a koji je manji od b i provjeravanju

b za pripadnost klasi prostih brojeva prema uvjetu a b-1 1 (mod b) u skladu s gornjim izrazom. U praksi je potrebno provjeriti samo nekoliko vrijednosti. Odabir jednakog 3 otkriva sve složene brojeve. Međutim, poznato je da ovaj test preskače složene Carmichaelove brojeve (na primjer, 561 = 3 x 11 x 17).

Drugi deterministički test.

Podijelimo broj "b" uzastopno s 2, 3, ...,. Ako pri nekom dijeljenju dobijemo nulti ostatak, tada je broj “b” složen, a djelitelj i kvocijent su njegovi faktori; inače je b prost.

Budući da je potrebno izvršiti dijeljenje, vrijeme potrebno da se provjeri prosti broj “b” je O ().

Ovaj vrlo spor eksponencijalni test ne samo da utvrđuje je li broj prost, već također pronalazi faktore složenog broja.

Treći deterministički test.

Broj “b” je jednostavan ako i samo ako je b | ((b-1)! + 1). Faktorijal (b-1)! a test djeljivosti (b-1)! + 1 za veliko “b” uništava svaki interes za ovaj test. Ako `b' ima 100 decimalnih znamenki, tada (b-1)! ima otprilike 100 102 znamenke.

Svi gore navedeni testovi bili su deterministički. To znači da za zadani broj "b" uvijek dobijemo odgovor, bilo da je jednostavan ili složen. Ako riječ “uvijek” zamijenimo s “s nekom vjerojatnošću”, onda se ispostavlja da je moguće konstruirati probabilističke testove, koji se također nazivaju testovima pseudo-jednostavnosti.

Prvi probabilistički test.

Ovaj test vam omogućuje da identificirate sve složene brojeve Carmichaela. Odabire se slučajni broj a u rasponu od 1 do b-1 i provjerava se ispunjenost uvjeta.

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

gdje je J (a, b) Jacobijev simbol.

Jacobijev simbol definiran je sljedećim odnosima:

J (a, p) = 1 ako x 2 a (mod p) ima rješenja u Z p,

J (a, p) = -1 ako x 2 a (mod p) nema rješenja u Z p,

gdje je Z p prsten ostataka po modulu p.

Ako je b prost broj, gore navedeni uvjeti su uvijek ispunjeni, a ako je b složen, onda nisu ispunjeni s vjerojatnošću. Stoga izvođenje k testova osigurava da je odgovor netočan s vjerojatnošću 2 -k.

Drugi probabilistički test.

Budući da je broj b, koji mora biti prost, uvijek neparan, može se predstaviti kao

gdje je s paran broj. Zatim se u testu nasumično bira broj a u rasponu od 1 do b-1 i provjerava se ispunjenje uvjeta

1 (mod b) za 0< j

Oba testa se koriste za provjeru pripada li broj prostoj klasi i zahtijevaju O (log 2 b) operacija na velikim brojevima.

Treći probabilistički test.

Za dano b, nasumično biramo m, 1

Vjerojatnost da je zadan odgovor "b je složeni broj" jednaka je vjerojatnosti da je m | b. Ako je d (b) broj djelitelja b i m je nasumično odabran unutar 1

Ovo je vrlo slab test.

Četvrti probabilistički test.

Za dano "b" nasumično biramo m, 1

Ako je b složeni broj, tada je broj brojeva m

Peti probabilistički test.

Ovo je test snažne pseudo-jednostavnosti. Neka su zadani b i m. Neka bude

gdje je t neparan broj i razmotrimo brojeve za (x r je najmanja apsolutna vrijednost ostatka po modulu b).

Ako je ili x 0 = 1, ili postoji indeks i, i

Dokažimo to kontradikcijom. Pretpostavimo da je b neparan prosti. Pokažimo indukcijom da je 1 (mod b) za, što bi bilo u suprotnosti s hipotezom teorema.

Očito, to vrijedi za r = S prema Fermatovom teoremu. Uz pretpostavku da je tvrdnja istinita za i, lako je vidjeti da je istinita za i-1, jer je jednakost

znači da je broj koji treba kvadrirati ± 1. Ali -1 ne odgovara uvjetu (inače bi test proizveo odgovor "ne može se odrediti").

Dokazano je da ako je b složeni broj, onda vjerojatnost da će test dati odgovor "b je složeni broj" nije manja.

Faktoriranje velikih cijelih brojeva.

Situacija s problemom nalaženja djelitelja velikih prostih brojeva puno je gora nego s testom jednostavnosti. Sljedeća je najmoćnija poznata metoda.

Metoda se temelji na Legendreovoj ideji ako je U 2 V 2 (mod b) 0

Pretpostavimo da želimo faktor b. Neka je n = maksimalni broj koji ne prelazi, a izračunajte brojeve a k = (n + k) 2 - b za mali k (brojevi k mogu biti negativni).

Neka je (q i, i = 1, 2,…, j) skup malih prostih brojeva koji mogu podijeliti izraz kao što je x 2 - b (tj. b je kvadrat po modulu q i). Takav skup se obično naziva multiplikativnom bazom B. Prisjetimo se svih brojeva a k koji se mogu proširiti u smislu multiplikativne baze, t.j. napisano kao

Takvi ak se nazivaju B-brojevi. Svaki B-broj ak povezan je s vektorom indikatora

Ako pronađemo dovoljno B-brojeva da skup odgovarajućih eksponentnih vektora bude linearno ovisan po modulu 2

(bilo koji skup od j + 2 B-broja ima ovo svojstvo), tada će biti moguće predstaviti nulti vektor kao zbroj vektora eksponenata nekog skupa S, npr.

Definirajte cijele brojeve

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

Iz navedenog slijedi da U 2 V 2 (mod b) i (U-V, b) mogu biti netrivijalni djelitelj od b.

Dešifriranje iteracijama izvodi se na sljedeći način. Neprijatelj pokupi broj j, za koji je ispunjen sljedeći omjer:

To jest, protivnik jednostavno šifrira j puta na javnom ključu presretnutog šifriranog teksta. To izgleda ovako: (C e) e) e ..) e (mod n) = C e j (mod n)). Nakon što je pronašao takav j, protivnik izračunava C e (j-1) (mod n) (tj. ponavlja operaciju šifriranja j-1 puta) - ova vrijednost je običan tekst M. To proizlazi iz činjenice da C ej (mod n ) = (C e (j-1) (mod n)) e = C. Odnosno, neki broj C e (j-1) (mod n) u stupnju e daje šifrirani tekst C. A ovo je običan tekst M.

Primjer. 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.

Akademska godina

Teorijski dio

1. Glavne vrste kriptografskih transformacija informacija. Bit svake transformacije, opseg.

2. Prikaz sustava enkripcije grafom, princip jedinstvenosti enkripcije-dešifriranja.

3. Matematički model sustava za šifriranje-dešifriranje informacija.

4. Jačina sustava šifriranja, klasifikacija sustava šifriranja prema jačini. Vrste napada na sustav šifriranja.

5. Definicija bezuvjetno sigurnog sustava šifriranja, izjava o potrebnim uvjetima za postojanje bezuvjetno sigurnog sustava.

6. Definicija bezuvjetno sigurnog sustava šifriranja, izjava o dovoljnim uvjetima za postojanje bezuvjetno sigurnog sustava.

7. Računalno jaki enkripcijski sustavi, koncept složenosti kriptoanalize, glavni pristupi razbijanju kriptografskih sustava, analiza brute-force napada i napada na temelju statistike poruka.

8. Blok šifra, Feistelova shema, svojstva blok šifre.

9. Zamjenski kod, njegova svojstva.

10. Gama kod i njegova svojstva.

11. Načini rada (načini rada) blok šifri, kratak opis načina rada.

12. Standard šifriranja GOST R34.12-2015, osnovni algoritam šifriranja za 64-bitni blok.

13. Standard šifriranja GOST R34.12-2015, osnovni algoritam šifriranja za 128-bitni blok.

14. Standard šifriranja GOST R34.13-2015, algoritam šifriranja u načinu jednostavne zamjene, algoritam šifriranja u gama i gama načinima s povratnom spregom. Usporedba načina rada.

15. Linearni rekurentni registar, algebarska svojstva linearnog rekurentnog niza, analiza svojstva predvidljivosti.

16. Linearni rekurentni registar, statistička svojstva linearnog rekurentnog niza.

17. Principi konstruiranja šifarnika gamuta (koncept ekvivalentne linearne složenosti, korištenje nelinearnih čvorova za povećanje linearne složenosti).

18. Šifra A5/1, karakteristike šifre, princip konstrukcije, primjena.

19. Princip konstrukcije i karakteristike AES šifre.

20. Koncept jednosmjerne funkcije, opći princip izgradnje kriptografskih sustava s javnim ključem.

21. Pojam hash funkcije, zahtjevi za kriptografske hash funkcije.

22. Hash funkcija prema GOST R34.11-12, karakteristike, princip konstrukcije, primjena.

23. El Gamal enkripcijski sustav, napadi na sustav.

24. RSA enkripcijski sustav, napadi na sustav.

25. Definicija, klasifikacija, osnovna svojstva, EP model.

26. Shema EP RSA.

27. Shema EP-a El-Gamal.

28. EDS u skladu s GOST 34.10-12, opće karakteristike, načelo formiranja i provjere potpisa.

29. Provjera autentičnosti poruka u telekomunikacijskim sustavima (model sustava zaštite od imitacije, strategije nametanja, pokazatelji sigurnosti imitacije).

30. Koncept ključne hash funkcije. Klasa strogo univerzalnih hash funkcija, primjeri implementacije ovih hash funkcija.

31. Konstrukcija sustava provjere autentičnosti s zajamčenom vjerojatnošću nametanja.

32. Izgradnja autentifikacijskog sustava za višestruki prijenos poruka.

33. Računalno otporni sustavi autentifikacije.

34. Razvoj imitacije umetka prema GOST R34.12-2015.

35. Model upravljanja ključevima u simetričnim kriptografskim sustavima, karakteristike životnog ciklusa ključa.

36. Metode distribucije ključeva temeljene na međusobnoj razmjeni poruka između dopisnika. Diffie-Hellmanova metoda.

37. Metode za generiranje slučajnih brojeva pri generiranju ključeva.

38. Metode distribucije ključeva pomoću CRC-a u početnoj fazi.

39. Metode distribucije ključeva pomoću CRC-a u interaktivnom načinu. Needham-Schroederov protokol.

40. Princip distribucije javnih ključeva.

41. Pojam infrastrukture javnog ključa (PKI), sastav, princip interakcije elemenata strukture.

42. Namjena, načelo formiranja i karakteristike certifikata javnog ključa.

Praktični dio

1. Ručno šifrirajte (dešifrirajte) poruku zamjenom, permutacijom i gama kodiranjem. Program LR1_1.exe.

2. Dešifrirajte kriptogram na temelju analize njegove statistike pomoću programa CHANGE.EXE.

3. Pronađite faktor množenja pogrešaka pri dešifriranju kriptograma blok supstitucijsko-permutacijske šifre s blokom duljine 16 bita. tst program.

4. Dešifrirajte kriptogram permutacijsko-permutacijske šifre brute-force nabrajanjem ključeva pomoću programa tst. Utemeljite parametre za donošenje odluke o ispravnom dekodiranju.

5. Šifrirajte 64-bitnu poruku s osnovnim algoritmom šifriranja GOST R 34.12-2015 (1 krug)

6. Šifrirajte 128-bitnu poruku pomoću programa AES.exe. Provjerite da li prva transformacija (operacija SubBytes) koristi inverziju elementa u GF polju (2 8).

7. Koristeći karakteristični polinom h (x), konstruirajte LRR (početno punjenje 10 ... 01) Odredite period niza. Pronađite ravnotežu, provjerite svojstva serije i prozora. Provjerite rezultat pomoću programa LRR 1.

8. Pronađite slijed na izlazu generatora raspona šifre koji sadrži elemente ILI, I NE, Jeff. Pomoću programa LRR 2 odredite ekvivalentnu složenost niza. Konstruirajte ekvivalentni LRR. Izvucite zaključke.

9. Izvedite sljedeće izračune za odjeljak diskretne matematike:

Pronađite najveći zajednički djelitelj pomoću Euklidovog algoritma;

Izračunajte x modp koristeći algoritam brzog eksponencijaliranja;

Pronađite inverz broja mod p.

Pronađite Eulerovu funkciju od x;

10. - pomoću Fermatovog testa provjeriti je li broj x prost, pronaći vjerojatnost da provjera daje pogrešan rezultat.

11. Parametri sustava za šifriranje El-Gamal su postavljeni a = 4, p = 11, privatni ključ x = 7, šifriranje poruke M =. Dešifrirajte kriptogram.

12. Parametri RSA sustava šifriranja su postavljeni p = 11, q = 13, šifriranje poruke M = 5. Dešifrirajte kriptogram.

13. Parametri sustava za šifriranje El-Gamal su postavljeni a = 4, p = 11, privatni ključ x = 8, potpišite poruku, čiji je hash kod h (M) =. Provjerite potpis.

14. Parametri RSA sustava šifriranja su postavljeni na p = 11, q = 13, potpišite poruku čiji je hash kod h (M) = 6. Provjerite potpis.

15. Koristeći RSA program, šifrirajte veliku datoteku sigurnim RSA kriptosustavom i procijenite vrijeme šifriranja i dešifriranja.

16. Koristeći RSA program, potpišite poruke i provjerite potpis. Kapacitet poruke je najmanje 100 bita.

17. Postavljena je eliptična krivulja E13 (1,1). Pronađite točku C jednaku zbroju dviju točaka, koordinata točaka i x 1 =, y 1 =, x 2 =, y 2 =. Pronađite suprotnu točku. Izračunajte točku gdje k =3.

18. Formirajte autentifikator za binarnu poruku M= 1010 na temelju strogo univerzalnih hash funkcija prema algoritmu K 0 = 0101, K 1= (broj ulaznice). Proračuni na terenu se provode po modulu nesvodivog polinoma , b=4.

Modeli kriptografskih sustava

Šifrirani tekst- rezultat operacije šifriranja. Također se često koristi umjesto izraza "kriptogram", iako potonji naglašava samu činjenicu da se poruka prenosi, a ne šifriranje.

Proces primjene operacije šifriranja na šifrirani tekst se zove ponovno šifriranje.

Svojstva šifriranog teksta

Uzimajući u obzir šifrirani tekst kao slučajnu varijablu ovisno o odgovarajućim slučajnim vrijednostima otvorenog teksta X i ključa za šifriranje Z, mogu se odrediti sljedeća svojstva šifriranog teksta:

Svojstvo nedvosmislene enkripcije:

Lančane jednakosti impliciraju

(iz svojstva nedvosmislenosti dešifriranja)

(iz načela neovisnosti otvorenog teksta od ključa i svojstva jednoznačne enkripcije) tada

ova se jednakost koristi za izvođenje formule udaljenosti jedinstvenosti.

Za apsolutno pouzdan kriptosustav

To je

Upotreba za kriptoanalizu

Shannon je u svom članku iz 1949. "Teorija komunikacije u tajnim sustavima" pokazao da je za neku slučajnu šifru teoretski moguće (koristeći neograničene resurse) pronaći izvorni otvoreni tekst ako su poznata slova šifratnog teksta, gdje je entropija ključa šifre , r je redundancija otvorenog teksta (uključujući broj uključujući kontrolne zbrojeve, itd.), N je veličina korištene abecede.

Šifriranje- reverzibilnu transformaciju informacija kako bi se one sakrile od neovlaštenih osoba, uz istovremeno omogućavanje pristupa njima ovlaštenim korisnicima. Uglavnom, šifriranje služi u svrhu održavanja povjerljivosti prenesenih informacija. Važna značajka svakog algoritma za šifriranje je korištenje ključa koji odobrava izbor određene transformacije iz skupa mogućih za ovaj algoritam.

Općenito, enkripcija ima dva dijela - šifriranje i dešifriranje.

Uz pomoć enkripcije osiguravaju se tri stanja informacijske sigurnosti:

· Privatnost: šifriranje se koristi za skrivanje informacija od neovlaštenih korisnika tijekom prijenosa ili pohrane.

· Integritet: šifriranje se koristi za sprječavanje promjene informacija tijekom prijenosa ili pohranjivanja.

· Identifikacija: enkripcija se koristi za provjeru autentičnosti izvora informacija i sprječavanje pošiljatelja informacija da negira činjenicu da su mu podaci poslani.

Šifriranje i dešifriranje

Kao što je rečeno, šifriranje se sastoji od dva međusobno suprotna procesa: enkripcije i dešifriranja. Oba ova procesa na apstraktnoj razini mogu se prikazati matematičkim funkcijama kojima se postavljaju određeni zahtjevi. Matematički, podaci koji se koriste u enkripciji mogu se predstaviti u obliku skupova na kojima su te funkcije izgrađene. Drugim riječima, pretpostavimo da postoje dva skupa koji predstavljaju podatke - M i C; a svaka od dvije funkcije (šifriranje i dešifriranje) je preslikavanje jednog od ovih skupova u drugi.

Funkcija šifriranja:

Funkcija dešifriranja:

Elementi ovih skupova - ~ m i ~ c - su argumenti odgovarajućih funkcija. Također, koncept ključa je već uključen u ove funkcije. To jest, potrebni ključ za šifriranje ili dešifriranje dio je funkcije. To nam omogućuje da procese enkripcije razmotrimo na apstraktan način, bez obzira na strukturu korištenih ključeva. Iako su, općenito, za svaku od ovih funkcija argumenti podaci i ključ za unos.

Ako se isti ključ koristi za šifriranje i dešifriranje, tada se takav algoritam naziva simetričnim. Ako je algoritamski teško dobiti ključ za dešifriranje iz ključa za šifriranje, tada se algoritam naziva asimetričnim, odnosno algoritmima s javnim ključem.

· Za korištenje u svrhu šifriranja, ove funkcije prije svega moraju biti međusobno inverzne.

Važna karakteristika funkcije šifriranja E je njezina kriptografska snaga... Neizravna procjena kriptografske snage je procjena međusobne informacije između otvorenog teksta i šifriranog teksta, koja bi trebala težiti nuli.

Kriptografska snaga šifre

Kriptografska snaga- svojstvo kriptografske šifre da se odupre kriptoanalizi, odnosno analizi koja ima za cilj proučavanje šifre kako bi se ona dešifrirala. Za proučavanje kriptootpornosti različitih algoritama stvorena je posebna teorija koja razmatra vrste šifri i njihovih ključeva, kao i njihovu snagu. Utemeljitelj ove teorije je Claude Shannon. Kriptografska snaga šifre je njena najvažnija karakteristika, koja odražava koliko uspješno algoritam rješava problem šifriranja.

Bilo koji sustav šifriranja, osim onih apsolutno kriptografski sigurnih, može se razbiti jednostavnim nabrajanjem svih mogućih ključeva u ovom slučaju. Ali morat ćete to riješiti dok se ne pronađe jedini ključ koji će pomoći dešifrirati šifrirani tekst.

Apsolutno otporni sustavi

Shanonova procjena kriptografske snage šifre određuje temeljni zahtjev za funkciju šifriranja E. Za kriptografski najjaču šifru, nesigurnosti (uvjetne i bezuvjetne), prilikom presretanja poruka, moraju biti jednake za proizvoljno velik broj presretnutih šifriranih tekstova.

Dakle, napadač ne bi mogao izdvojiti bilo kakve korisne informacije o otvorenom tekstu iz presretnutog šifriranog teksta. Šifra s ovim svojstvom naziva se apsolutno otporan.

Zahtjevi za apsolutno jake sustave šifriranja:

· Za svaku poruku se generira ključ (svaki ključ se koristi jednom).

· Ključ je statistički pouzdan (odnosno, vjerojatnosti pojavljivanja svakog od mogućih simbola su jednake, simboli u slijedu ključeva su neovisni i slučajni).

· Duljina ključa jednaka je ili veća od duljine poruke.

Trajnost takvih sustava ne ovisi o sposobnostima kriptoanalitičara. Međutim, praktična primjena apsolutno sigurnih kriptosustava ograničena je razmatranjem cijene takvih sustava i njihove praktičnosti. Idealni tajni sustavi imaju sljedeće nedostatke:

Sustav šifriranja mora biti kreiran s iznimno dubokim poznavanjem strukture korištenog jezika za prijenos poruka

· Složena struktura prirodnih jezika iznimno je složena i može biti potreban iznimno složen uređaj kako bi se eliminirala suvišnost prenesenih informacija.

· Ako se u odaslanoj poruci pojavi pogreška, tada ta pogreška snažno raste u fazi kodiranja i prijenosa, zbog složenosti uređaja i korištenih algoritama.

Kriptografski sustav javnog ključa(ili asimetrična enkripcija, asimetrična šifra) - sustav šifriranja i/ili elektroničkog potpisa (ES), u kojem se javni ključ prenosi preko otvorenog (tj. nezaštićenog, dostupnog za promatranje) kanala i koristi se za provjeru ES-a i za šifriranje poruke. Privatni ključ se koristi za generiranje ES-a i dešifriranje poruke. Kriptografski sustavi javnog ključa sada se široko koriste u raznim mrežnim protokolima, posebno u TLS protokolima i njegovom prethodniku SSL-u (u osnovi HTTPS), u SSH-u. Također se koristi u PGP, S / MIME.

Simetrični kriptosustavi(također simetrično šifriranje, simetrične šifre) - metoda šifriranja u kojoj se za šifriranje i dešifriranje koristi isti kriptografski ključ. Prije izuma sheme asimetrične enkripcije, jedina postojeća metoda bila je simetrična enkripcija. Obje strane moraju čuvati ključ algoritma u tajnosti. Algoritam šifriranja odabiru strane prije početka razmjene poruka.

Matematički model sustava za šifriranje/dešifriranje za diskretne poruke je par funkcija

,
,

koji transformiraju poruku
u kriptogram pomoću ključa za šifriranje
i, obrnuto, kriptogram u poruci
pomoću ključa za dešifriranje ... Obje funkcije koje definiraju kriptosustav moraju ispunjavati sljedeće zahtjeve:

Nizozemski kriptograf A. Kerkhoffs (1835. - 1903.) sugerirao je da se tajnost šifri treba temeljiti samo na tajnosti ključa, a ne na tajnosti algoritma za šifriranje, koji bi, na kraju, mogao biti poznat neprijatelju .

Ako je ključ za šifriranje jednak ključu za dešifriranje, t.j.

= =,

tada se sustav poziva simetrično(s jednim ključem). Da bi funkcionirao, isti ključevi moraju biti tajno dostavljeni točkama za šifriranje i dešifriranje. .

Ako
, tj. ključ za šifriranje nije jednak ključu za dešifriranje, tada se poziva sustav šifriranja asimetrična(dva ključa). U ovom slučaju, ključ
isporučen na točku šifriranja i ključ - do točke dešifriranja. Oba ključa očito bi trebala biti povezana funkcionalnom ovisnošću.

, ali takav da prema poznatom ključu za šifriranje
bilo bi nemoguće vratiti ključ za dešifriranje ... To znači da za asimetrični sustav šifriranja, funkciju () mora biti teško izračunati.

Postoje dvije glavne klase sigurnosti za kriptosustave:

Idealno(svakako) uporan ili savršen kriptosustavi za koje otpor kriptoanalizi (dešifriranju) bez poznavanja ključa ne ovisi o računskoj snazi ​​protivnika. Zovu se teoretski nedešifrirano(TNDSH) sustavi.

Računarski jaki kriptosustavi, u kojima otpor kriptoanalizi ovisi o snazi ​​protivničkog računalnog sustava.

1. Kretski sustav RSA

Za šifriranje se bira cijeli broj N =str q, gdje str i q - dva velika prosta broja. Poruka M predstavljen je jednim od brojeva

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

Formule za šifriranje/dešifriranje su sljedeće:

,
,

gdje K- javni ključ za šifriranje, k- privatni ključ za dešifriranje.

Ova dva odnosa podrazumijevaju jednakost

,

koja se u običnoj aritmetici izvodi ako kK= 1, a u modularnoj aritmetici i za

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

gdje l- cijeli. Doista, koristeći Eulerov teorem, provjeravamo

,

ako M i N- međusobno prosti brojevi.

Razmatrani omjeri ukazuju na način formiranja ključeva. Najprije se biraju vrlo veliki slučajni prosti brojevi. str i q s nešto drugačijim brojem znamenki tako da proizvod N = pq imao najmanje 768 bita (prema podacima iz 2001.). Izračunajte Eulerovu funkciju

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

Jednakost (*) je ekvivalentna

Kk= 1 mod  ( N ),

odakle slijedi da su oba ključa međusobno inverzna po modulu  ( N ).

Javni ključ K odabrati, poštujući potrebne uvjete:

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

Privatni ključ k izračunati

k = K – 1 mod  ( N ),

koristeći Euklidov algoritam. Nakon završetka pripremnih radova, javni ključ K i modul N stavljen u otvoreni imenik, poduzimajući mjere kako bi se osigurala nemogućnost zamjene. Brojevi str i qčuvao u tajnosti.

Imajte na umu da je uvjet međusobne jednostavnosti brojeva M i N neuspjeh u tome onemogućuje dekodiranje ne stvara ozbiljna ograničenja. Prvo, među manjim brojevima N razlomak međusobno prostih brojeva s N jednako je ( str–1)(q–1)/(pq), tj. se ne razlikuje od jedinstva, i, drugo, uvjet se lako osigurava beznačajnom modifikacijom poruke. Također diploma M K ne bi trebalo biti manje N... Ako ovaj uvjet nije ispunjen, kriptogram ima oblik

i bez proračuna po modulu može se lako otvoriti, budući da K znan.

Očito, u razmatranim odnosima, brojevi K i k jednaki su, tj. ključevi se mogu mijenjati i koristiti k kao javni ključ za šifriranje, i K kao privatni ključ za dešifriranje.

Dakle, oba RSA ključa navedena su u parovima cijelih brojeva :( K, N) i ( k, N).

Kada su autori R. Rivest, A. Shamir, L. Adleman (Rivest, Shamir, Adleman) je 1977. godine predložio RSA kriptosustav, šifrirali su frazu “ItsallGreektome”, predstavljenu u digitalnom obliku. Vrijednosti su objavljene M, K, Nšto ukazuje da 129 decimalnih mjesta N dobiveno množenjem 64- i 65-bitnih brojeva str i q... Faktorizacija N a otvaranje kriptograma obavljeno je za oko 220 dana tek 1994. nakon preliminarne teorijske obuke. U radu je sudjelovalo 600 volontera i 1600 računala umreženih putem interneta.

Snaga sustava javnog ključa, a posebno RSA, ovisi o izboru njegovih parametara. Ako odaberete dnevnik 2 N= 200 bita, tada će faktorizacija zahtijevati otprilike 2,710 11 operacija, što će trajati nekoliko dana na osobnom računalu. Ako odaberete dnevnik 2 N= 664 bita, tada faktorizacija zahtijeva 1210 23 operacije. Pri brzini od 10 6 operacija u sekundi, faktorizacija će trajati nekoliko milijardi godina.

Dakle, ako su parametri RSA šifre ispravno odabrani i modul N uzeti dovoljno velik, na primjer
, onda se ovaj sustav može smatrati prilično stabilnim. Do danas ne postoje metode za njegovu uspješnu kriptoanalizu.

Implementacija RSA šifre razrađena je iu softverskoj i u hardverskoj verziji. Koristi ga RSA za enkripciju pametnih kartica. U softverskoj verziji, brzina šifriranja je reda veličine 1 kbps, u hardverskoj verziji - 10-50 kbps.

Relativno niska brzina enkripcije i dešifriranja u usporedbi sa simetričnim, blok ili streaming sustavima je nedostatak svih asimetričnih enkripcijskih sustava, uključujući RSA.

1. Digitalni potpis

Autentičnost dokumenta tradicionalno je ovjerena uobičajenim "papirnatim" potpisom. Jačina potpisa, tj. nemogućnost krivotvorenja od strane neovlaštenih osoba osiguravaju dva glavna uvjeta: prvo, njegova jedinstvenost, temeljena na individualnim karakteristikama rukopisa, i drugo, fizički integritet papirnatog dokumenta na kojem je potpisan. Štoviše, potpis ne može krivotvoriti ni osoba koja provjerava njegovu autentičnost.

Međutim, prilikom prijenosa dokumenata preko računalnih mreža, nemoguće je koristiti ove uvjete, uključujući i prijenos faksimilnih poruka (FAX), jer se mogu lako krivotvoriti.

Dokumenti koji se prenose putem računalnih mreža ovjereni su digitalnim potpisom. Digitalni potpis rješava problem mogućeg spora između pošiljatelja i primatelja, uključujući i sudski, ako postoji pravni temelj za njegovu primjenu.

Digitalni potpis mora imati svojstva redovitog potpisa i istovremeno biti lanac podataka koji se može prenositi mrežama, t.j. mora ispunjavati sljedeća četiri osnovna zahtjeva:

digitalni potpis mora biti jedinstven, t.j. nitko, osim autora, ne može izraditi isti potpis, uključujući osobe koje provjeravaju njegovu vjerodostojnost;

svaki netizen, legalan ili ilegalan, može provjeriti valjanost digitalnog potpisa;

potpisnik ne može odbiti poruku ovjerenu njegovim digitalnim potpisom;

i implementacija i provjera digitalnog potpisa trebaju biti prilično jednostavni.

Da bi se zadovoljili svi gore navedeni zahtjevi, digitalni potpis, za razliku od "papirnatog", mora ovisiti o svim bitovima poruke i mijenjati se čak i kada se promijeni jedan bit potpisane poruke. Za implementaciju digitalnog potpisa temeljenog na simetričnim kriptosustavima potrebno je sudjelovanje osobe od povjerenja – arbitra. Implementacija digitalnog potpisa bez arbitra moguća je samo korištenjem asimetričnih sustava.

Postoje različite vrste digitalnih potpisa temeljenih na kriptosustavima javnog ključa. Razmotrite implementaciju CPU-a temeljenu na RSA kriptosustavu.

U ovom slučaju korisnik A potpisivanja poruke M, generira par ključeva k A ,K A i informira korisnike interneta o vrijednostima K A i N... Sljedeći korisnik A stvara kontrolnu grupu

,

što će biti digitalni potpis (slika 17). Kontrolna grupa se dodjeljuje poruci i šalje zajedno s njom.

Lako je provjeriti da su u ovom slučaju sva četiri prethodno formulirana zahtjeva za digitalne potpise ispunjena ako je RSA šifra odabrana dovoljno jaka.

Međutim, razmatrani sustav za generiranje digitalnog potpisa ima dva značajna nedostatka:

postoji značajna redundantnost zbog dodjele kontrolne grupe, čija je duljina jednaka duljini poruke, što zahtijeva udvostručenje količine memorije, vremena prijenosa itd.;

za duge poruke, operacija eksponencijalnosti u izračunavanju kontrolne grupe i njezinoj provjeri trajat će neprihvatljivo dugo.