Sada, nakon što smo naučili svrhu kriptografije, upoznajmo se s osnovnim pojmovima koje ćemo koristiti pri proučavanju kriptografskih metoda zaštite informacija.

Šifra– skup unaprijed dogovorenih metoda za transformaciju izvorne tajne poruke u svrhu njezine zaštite.

Obično se pozivaju izvorne poruke u jasnim tekstovima. U stranoj literaturi za otvoreni tekst koristiti izraz otvoreni tekst.

Simbol je bilo koji znak, uključujući slovo, broj ili interpunkcijski znak.

Abeceda- konačan skup simbola koji se koriste za kodiranje informacija. Na primjer, ruska abeceda sadrži 33 slova od A do Z. Međutim, ova trideset i tri znaka obično nisu dovoljna za pisanje poruka, pa se nadopunjuju razmakom, točkom, zarezom i drugim znakovima. Arapska abeceda brojeva su simboli 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Ova abeceda sadrži 10 znakova i može se koristiti za pisanje bilo kojeg prirodni broj. Bilo koja poruka također se može snimiti pomoću binarna abeceda, odnosno korištenje samo nula i jedinica.

Poziva se poruka primljena nakon transformacije pomoću bilo koje šifre šifrirana poruka(zatvoreni tekst, kriptogram). U stranoj literaturi pojam se koristi za zatvoreni tekst šifrirani tekst.

Pretvaranje otvorenog teksta u kriptogram naziva se šifriranje. Obrnuta radnja se zove dešifriranje. U literaturi na engleskom jeziku izrazi “encryption/decryption” odgovaraju pojmovima "šifriranje/dešifriranje".

Ključ– podatke potrebne za šifriranje i dešifriranje poruka.

Sa stajališta ruskog jezika, pojmovi "dešifriranje" i "dešifriranje" su sinonimi. Međutim, u radovima o kriptografiji posljednjih desetljeća te se riječi često razlikuju. Pretpostavit ćemo da pojmovi "dešifriranje" i "dešifriranje" nisu sinonimi. Pretpostavimo da legalni primatelj poruke (onaj koji zna ključ) dešifrira poruku, a osoba kojoj poruka nije namijenjena dešifrira pokušavajući shvatiti njezino značenje.

Sustav šifriranja, ili sustav šifriranja, je svaki sustav koji se može koristiti za reverzibilnu promjenu teksta poruke kako bi bila nerazumljiva svima osim onima kojima je namijenjena.

Kriptografska snaga je karakteristika šifre koja određuje njenu otpornost na dešifriranje bez znanja ključa (tj. sposobnost da izdrži kriptoanalizu).

Dakle, uzimajući u obzir sve navedene definicije, možemo dati precizniju definiciju znanosti “kriptografije”. Kriptografija proučava konstrukciju i korištenje sustava šifriranja, uključujući njihovu snagu, slabosti i stupanj ranjivosti u odnosu na razne metode obdukcija.

Sve metode pretvaranja informacija u svrhu zaštite od neovlaštenog pristupa dijele se na dvije: velike skupine: metode šifriranja privatnim ključem i metode šifriranja javnim ključem. Enkripcija privatnim ključem(enkripcija tajnim ključem ili simetrična enkripcija) ljudi već dosta koriste dugo vremena. Ove metode koriste isti ključ za šifriranje i dešifriranje podataka, koje obje strane pokušavaju zadržati u tajnosti od neprijatelja. Enkripcija s javnim ključem (asimetrična enkripcija) počeo se koristiti za kriptografsko zatvaranje informacija tek u drugoj polovici dvadesetog stoljeća. Ova skupina uključuje metode šifriranja koje koriste dvije metode za šifriranje i dekriptiranje podataka. različite ključeve. U tom slučaju jedan od ključeva (javni ključ) može se prenijeti preko otvorenog (nezaštićenog) komunikacijskog kanala. Elektronički (digitalni) potpis je blok podataka koji se obično prilaže poruci, dobiven korištenjem kriptografske transformacije. Elektronički potpis omogućuje provjeru autorstva i autentičnosti poruke kada drugi korisnik primi tekst.

Kriptografski informacijski sigurnosni sustav– informacijski sigurnosni sustav koji koristi kriptografske metode za šifriranje podataka.

3.5.3 Modeli i metode šifriranja/dešifriranja diskretne poruke

Diskretne poruke mogu se prikazati signalima koji imaju konačan broj stanja. To su razne vrste podataka, tiskani tekstovi, kao i govorni signali i slike, ako su prethodno pretvorene u diskretne (digitalne) signale.

Matematički model sustavi za šifriranje/dekriptiranje diskretnih poruka nazivaju se par funkcija

E = f(M,K w), M = g(E,K d),

koje pretvaraju poruku M u kriptogram E pomoću ključa za šifriranje K w i, obrnuto, kriptogram E u poruku M pomoću ključa za dešifriranje K d. Obje funkcije koje definiraju kriptosustav moraju zadovoljiti sljedeće zahtjeve:

· jednostavno se izračunavaju funkcije f(M, Kw) i g(E, Kd) s poznatim argumentima;

· funkciju g(E,?) s nepoznatim ključem Kd teško je izračunati.

Pretpostavlja se da je ključ za dešifriranje K d nepoznat ilegalnim korisnicima, iako mogu poznavati funkcije f i g, kao i ključ za šifriranje K sh ako ne odgovara ključu K d. Zadnji uvjetčini takozvani princip Kaziskija.

Potrebno je razlikovati tri glavne vrste napada na kriptosustav:

· samo s poznatim kriptogramom E;

· zadan poznati kriptogram E i poznata poruka M, koja odgovara određenom dijelu kriptograma dobivenog istim ključem (djelomično poznati napad otvorena poruka);

· poznatim kriptogramom i posebno odabranim dijelom poruke koji odgovara dijelu kriptograma dobivenog istim ključem (napad djelomično odabranom otvorenom porukom).

Moderni kriptosustavi smatraju se jakima ako su otporni na sve tri vrste napada.

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

K w = K d = K

tada se sustav naziva simetričnim (s jednim ključem). Da bi radilo, točke šifriranja i dešifriranja moraju imati iste ključeve.

Ako Ksh nije jednak Kd, tada se sustav šifriranja naziva asimetričnim (s dva ključa). U ovom slučaju, ključ Ksh se isporučuje točki šifriranja, a ključ Kd se isporučuje točki dešifriranja. Oba ključa očito moraju biti povezana funkcionalna ovisnost K d = j(K sh), ali takav da korištenjem poznatog ključa za šifriranje K sh ne bi bilo moguće obnoviti ključ za dešifriranje K d. To znači da bi za asimetrični sustav šifriranja j() trebao biti teško izračunati funkcija. U takvom sustavu moguće je tajno distribuirati samo njihove ključeve za dešifriranje među legitimnim korisnicima, a ključeve za šifriranje učiniti javnima, uključujući i za objavljivanje. Stoga se predmetni kriptosustav naziva sustavom s javnim ključem.

Prva od ovih vrsta šifri podrazumijeva prisutnost određene informacije (ključa), čije posjedovanje omogućuje i šifriranje i dešifriranje poruke.

S jedne strane, ovakva shema ima nedostatke da je, osim otvorenog kanala za prijenos šifragrama, potrebno imati i tajni kanal za prijenos ključa, a osim toga, ako informacije o ključu procure, nemoguće je dokazati s kojeg od dva dopisnika je došlo do curenja.

S druge strane, među šiframa ove skupine nalazi se jedina shema šifriranja na svijetu koja ima apsolutnu teoretsku snagu. Svi ostali mogu se barem načelno dešifrirati. Takva shema je regularna enkripcija (na primjer, XOR operacija) s ključem čija je duljina jednaka duljini poruke. U tom slučaju ključ treba koristiti samo jednom. Svaki pokušaj dešifriranja takve poruke je beskoristan, čak i ako postoje apriorne informacije o tekstu poruke. Odabirom ključa možete dobiti bilo koju poruku kao rezultat.

Šifre s javnim ključem podrazumijevaju prisutnost dva ključa - javnog i privatnog; jedan se koristi za šifriranje, drugi za dešifriranje poruka. Javni ključ se objavljuje - stavlja na znanje svima, dok tajni ključ čuva njegov vlasnik i ključ je tajnosti poruka. Suština metode je da se ono što je šifrirano tajnim ključem može dešifrirati samo javnim ključem i obrnuto. Ovi se ključevi generiraju u parovima i međusobno odgovaraju jedan na jedan. Štoviše, nemoguće je izračunati drugi iz jednog ključa.

Karakteristična značajkašifre ovog tipa, po čemu se povoljno razlikuju od šifri s tajnim ključem, je to što tajni ključ ovdje zna samo jedna osoba, dok ga u prvoj shemi mora znati barem dva. To daje sljedeće prednosti:

nije potreban siguran kanal za slanje tajnog ključa, sva se komunikacija odvija putem otvoreni kanal;

“Što znaju dvoje, zna i svinja” - prisutnost jedini kopija ključa smanjuje mogućnost njegovog gubitka i omogućuje uspostavljanje jasne osobne odgovornosti za čuvanje tajne;

prisutnost dva ključa omogućuje korištenje ovog sustava šifriranja u dva načina - tajna komunikacija i digitalni potpis.

Najjednostavniji primjer algoritama šifriranja koji se razmatra je RSA algoritam. Svi ostali algoritmi ove klase ne razlikuju se bitno od njega. Može se reći da je, prema uglavnom,RSA je jedini algoritam s javnim ključem.

10.3.1. Sustavi šifriranja

Među kriptografskim sustavima koji osiguravaju tajnost podataka najrašireniji su sustavi za šifriranje informacija. Razmotrimo generalizirani model sustava šifriranja prikazan na sl. 10.6.

Izvor poruke generira poruke koje se moraju držati u tajnosti od napadača kada se prenose preko nesigurnog kanala. Sustav ima izvor ključnih informacija zaštićen od uljeza, koji proizvodi određeni ključ namijenjen šifriranju poruka od strane pošiljatelja poruke i ključ namijenjen dešifriranju kriptograma od strane primatelja. Ključevi za šifriranje i dešifriranje međusobno su povezani i omogućuju rekonstrukciju poruke iz kriptograma. Generirane ključne informacije prenose se sigurnim kanalom isporuke. Pod zaštićenim mislimo na kanal prijenosa informacija u kojem uljez nije sposoban za uspješne napade. Pošiljatelj poruke šifrira poruku pomoću ključa pomoću transformacije šifriranja.

Generirani kriptogram prenosi se nezaštićenim kanalom za prijenos informacija do primatelja. Pri prijemu primatelj može nedvosmisleno rekonstruirati poruku iz kriptograma pomoću ključa pomoću transformacije dešifriranja.

Za nedvosmisleno vraćanje poruke iz kriptograma, potrebno je da transformacija dešifriranja bude inverzna transformaciji šifriranja kada se koriste ključevi i, respektivno.

Sustavi šifriranja informacija podijeljeni su u dvije velike klase: simetrične i asimetrične. Sustav za šifriranje informacija naziva se simetričnim ako je za bilo koji prihvatljivi par ključeva računalno jednostavno odrediti jedan ključ poznavajući drugi, tj. iz može se izračunati i, znajući , "lako" odrediti. U takvim sustavima oba ključa moraju biti tajna. U mnogim simetričnim sustavima, ključ za šifriranje je isti kao ključ za dešifriranje: . Zato simetrični kriptosustavi ponekad se nazivaju sustavi s jednim ključem ili tajnim ključem.

Sustav za šifriranje informacija naziva se asimetričnim ako je za bilo koji važeći par ključeva računalno nemoguće odrediti ključ za dešifriranje uz poznavanje ključa za šifriranje. U asimetričnom sustavu šifriranja ključ šifriranja može biti netajni (otvoren), poznat svima, uključujući i napadača. Stoga se takvi kriptosustavi ponekad nazivaju sustavi s javnim ključem ili sustavi s dva ključa. U takvim sustavima mora biti osigurana tajnost ključa za dešifriranje.

Asimetrični sustavi šifriranja prikladni su za praktičnu upotrebu u tome što pri isporuci ključeva pošiljatelji poruka ne moraju osigurati tajnost informacija o šifriranju ključnih poruka.

Poznato je da se maksimalni stupanj sigurnosti informacija od čitanja postiže proizvoljnim prenesene poruke a odgovarajući kriptogrami koje opaža uljez su statistički neovisni:

.

Kako bi se karakteristike pravih kriptora približile karakteristikama idealnog, koristi se kompresija poruka prije enkripcije i randomizacija kriptiranih poruka. Ideja randomizacije je smanjiti redundantnost šifriranih poruka kroz posebno kodiranje koje osigurava jednaku vjerojatnost pojavljivanja znakova, ali se duljina poruka povećava.

Glavna karakteristika šifre je njezina kriptografska snaga, koja se obično određuje vremenskim intervalom potrebnim za razbijanje šifre. Postoji niz zahtjeva za šifre koje se koriste za kriptografsku zaštitu informacija:

• dovoljna kriptografska snaga (pouzdanost zatvaranja podataka);
• jednostavnost postupaka šifriranja i dešifriranja;
• mala redundancija informacija zbog enkripcije;
• neosjetljivost na male pogreške kodiranja itd.

U jednom ili drugom stupnju, te zahtjeve ispunjavaju permutacijske šifre, supstitucijske šifre, gama šifre i šifre temeljene na analitičkim transformacijama šifriranih podataka.

Permutacijsko šifriranje znači da znakovi izvorni tekst preuređuju se prema određenom pravilu unutar određenog bloka ovog teksta. S dovoljnom duljinom bloka unutar kojeg se provodi permutacija i složenim redoslijedom permutacije koji se ne ponavlja, moguće je postići snagu šifre prihvatljivu za jednostavne praktične primjene.

Zamjenska enkripcija (supstitucija) uključuje zamjenu znakova izvornog teksta znakovima iste ili druge abecede u skladu s unaprijed određenom shemom zamjene. Moguće su jedno- i višeabecedne zamjene. U slučaju jednoabecednih zamjena, svaki se znak izvornog teksta prema istom zakonu pretvara u znak šifriranog teksta. Kod višeabecedne zamjene, pretvorba se razlikuje od znaka do znaka. Kako bi se osigurala visoka kriptografska snaga, potrebna je upotreba složenih ključeva.

Gama šifriranje sastoji se od dodavanja simbola izvornog teksta sa simbolima nekog pseudoslučajnog niza, koji se naziva gama šifre. Primjer je bitovno zbrajanje poruke i gama pri formiranju kriptograma. Na recepciji je potrebno generirati isti pseudoslučajni niz() tada će se dešifriranje provesti na temelju sljedeće transformacije: . Snaga enkripcije određena je uglavnom duljinom (periodom) dijela raspona šifre koji se ne ponavlja. Budući da je uz pomoć računala moguće generirati niz šifri vrlo velike duljine, onda ovu metodu jedan je od glavnih za šifriranje informacija u automatiziranim sustavima.

Matematički model diskretnog sustava za šifriranje/dešifriranje poruka 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 zadovoljiti sljedeće zahtjeve:

Nizozemski kriptograf A. Kerkhofs (1835. - 1903.) sugerirao je da se tajnost šifara treba temeljiti samo na tajnosti ključa, a ne na tajnosti algoritma šifriranja, koji, na kraju, može biti poznat neprijatelju. .

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

= =,

tada se sustav poziva simetričan(s jednim ključem). Da bi radio, isti ključevi moraju biti tajno dostavljeni na točke šifriranja i dešifriranja .

Ako
, tj. Ključ za šifriranje nije jednak ključu za dešifriranje, tada se poziva sustav za šifriranje asimetričan(s dva ključa). U ovom slučaju ključ
isporučuje se do točke šifriranja, a ključ - do točke dešifriranja. Oba ključa očito moraju biti povezana funkcionalnom ovisnošću

, ali tako da koristi poznati ključ za šifriranje
bilo bi nemoguće povratiti ključ za dešifriranje . To znači da za asimetrični sustav šifriranja funkciju  () mora biti teško izračunati.

Postoje dvije glavne klase snage kriptosustava:

Savršen(svakako) uporan ili savršen kriptosustavi kod kojih otpornost na kriptoanalizu (dešifriranje) bez poznavanja ključa ne ovisi o računskoj snazi ​​protivnika. Zovu se teoretski nedešifrirati(TNDS) sustavi.

Računalno jaki kriptosustavi u kojima otpor kriptoanalizi ovisi o snazi računalni sustav protivnik.

1. RSA kritični sustav

Za šifriranje je odabran cijeli broj N =str q, Gdje str I q – dva velika primarni brojevi. Poruka M pojavljuje kao jedan od brojeva

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

Formule koje opisuju šifriranje/dešifriranje su sljedeće:

,
,

Gdje K– javni ključ za šifriranje, k– privatni ključ za dešifriranje.

Ova dva odnosa impliciraju jednakost

,

što je u običnoj aritmetici zadovoljeno ako kK= 1, a u modularnoj aritmetici i at

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

Gdje l- cijeli. Doista, pomoću Eulerovog teorema provjeravamo

,

Ako M I N su međusobno prosti brojevi.

Razmotreni odnosi ukazuju na put formiranja ključa. Najprije se biraju vrlo veliki nasumični prosti brojevi str I q s nešto drugačijim brojem znamenki tako da umnožak 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 ),

pomoću Euklidovog algoritma. Po završetku pripremnih radova, javni ključ K i modul N smješteno u otvori imenik, poduzimanje mjera kako bi se osiguralo da zamjena nije moguća. Brojke str I q držao u tajnosti.

Uočimo da je uvjet međusobne jednostavnosti brojeva M I N, čiji kvar onemogućuje dekodiranje, ne stvara ozbiljna ograničenja. Prvo, među manjim brojevima N razlomak brojeva koji su prosti s N jednak ( str–1)(q–1)/(pq), tj. se ne razlikuje od jednog, i, drugo, stanje se lako osigurava beznačajnom preinakom poruke. Također diploma M K ne bi trebalo biti manje N. Ako ovaj uvjet nije ispunjen, kriptogram ima oblik

i bez modulo izračuna se može lako otvoriti jer K znan.

Očito je da u razmatranim odnosima brojevi K I k jednaki u pravima, tj. ključevi se mogu zamijeniti i koristiti k kao javni ključ za šifriranje i K Kako privatni ključ dešifriranje.

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

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

Snaga sustava javnih ključeva, a posebno RSA, ovisi o izboru njegovih parametara. Ako odaberete zapisnik 2 N= 200 bita, tada će faktorizacija zahtijevati približno 2,710 11 operacija, što će trajati nekoliko dana na osobnom računalu. Ako odaberete zapisnik 2 N= 664 bita, tada će faktorizacija zahtijevati 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
, To ovaj sustav može se smatrati prilično stabilnim. Do danas ne postoje metode za njegovu uspješnu kriptoanalizu.

Implementacija RSA šifre razrađena je u softverskoj i hardverskoj verziji. Koristi ga RSA za enkripciju u pametnim karticama. U softverskoj verziji, brzina enkripcije je oko 1 kbit/s, u hardverskoj verziji – 1050 kbit/s.

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

1. Digitalni potpis

Obični "papirnati" potpis tradicionalno potvrđuje autentičnost dokumenta. Jačina potpisa, tj. nemogućnost njegovog krivotvorenja od strane neovlaštenih osoba osiguravaju dva glavna uvjeta: prvo, njegova jedinstvenost, koja se temelji 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 vjerodostojnost.

Međutim, kod prijenosa dokumenata preko računalnih mreža nemoguće je koristiti ove uvjete, uključujući i kod prijenosa faks poruka (FAX), jer dopuštaju jednostavno krivotvorenje.

Dokumenti koji se prenose računalnim mrežama ovjeravaju se digitalnim potpisom. Digitalni potpis rješava problem mogućeg spora između pošiljatelja i primatelja, uključujući i sudski, ako postoji zakonska osnova za njegovu uporabu.

Digitalni potpis mora imati svojstva običnog potpisa i ujedno predstavljati lanac podataka koji se može prenositi mrežama, tj. mora zadovoljiti sljedeća četiri osnovna zahtjeva:

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

svaki korisnik mreže, legalan ili ilegalni, može provjeriti istinu digitalni potpis;

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

i implementacija i provjera digitalnog potpisa trebale bi biti prilično jednostavne.

Da bi zadovoljio sve gore navedene zahtjeve, digitalni potpis, za razliku od “papirnatog”, mora ovisiti o svim bitovima poruke i mijenjati se čak i ako se jedan bit potpisane poruke promijeni. 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 s javnim ključem. Razmotrimo CPU implementaciju temeljenu na RSA kriptosustavu.

U ovom slučaju korisnik A, potpisujući poruku M, generira par ključeva k A ,K A i informira korisnike mreže o vrijednostima K A I N. Sljedeći korisnik A stvara kontrolnu grupu

,

koji će biti digitalni potpis (slika 17). Kontrolna grupa se dodjeljuje poruci i prenosi zajedno s njom.

To je lako provjeriti u ovom slučaju sva četiri prethodno formulirana zahtjeva za digitalni potpis ispunjena su ako je RSA šifra odabrana kao dovoljno jaka.

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

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

Za poruke velike duljine operacija potenciranja pri izračunavanju kontrolne skupine i njezinoj provjeri trajat će nedopustivo dugo.

Kriptografski sustavi s javnim ključem omogućuju korisnicima da siguran prijenos podataka preko nezaštićenog kanala bez ikakvih prethodna priprema. Takvi kriptosustavi moraju biti asimetrični u smislu da pošiljatelj i primatelj imaju različite ključeve, od kojih se nijedan ne može izvesti računalno iz drugoga. U tim sustavima faze šifriranja i dešifriranja su odvojene i poruka je zaštićena bez da se ključ za šifriranje učini tajnim jer se ne koristi u dešifriranju.

Pomoću javni ključ enkripcije, korisnik i šifrira poruku M i šalje je korisniku j preko nesigurnog podatkovnog kanala. Samo korisnik j može dešifrirati kako bi povratio M jer samo on zna tajni ključ za dešifriranje.

Među asimetričnim (otvorenim) kriptosustavima najviše se koristi kriptografski sustav RSA. U ovom sustavu primatelj poruke bira dva velika prosta broja p i q tako da je umnožak n = pq izvan računalnih mogućnosti. Izvorna poruka M može imati proizvoljnu duljinu u rasponu 1

Izvorni tekst M obnavlja se iz šifriranog teksta C inverznom transformacijom

Primatelj odabire e i d tako da su zadovoljeni 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 su recipročne vrijednosti multiplikativne skupine u modu aritmetike ostataka.

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

Postoje tri poznate metode koje bi kriptoanalitičar mogao koristiti da otkrije vrijednost d iz javnih informacija o paru (e, n).

Faktorizacija n

Rastavljanje n na proste faktore omogućuje izračunavanje funkcije, a time i latentne vrijednosti d, pomoću jednadžbe

Razni algoritmi za takvu dekompoziciju navedeni su u. Najbrži trenutno poznati algoritam može faktorizirati n u koracima reda veličine

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

Izravni izračun

Druga moguća metoda kriptoanalize uključuje izravno izračunavanje Eulerove funkcije bez faktoriziranja n. Izravni izračun nije ništa lakši od rastavljanja n na faktore, budući da vam omogućuje naknadno jednostavno faktoriziranje n. To se može vidjeti iz sljedećeg primjera. Neka

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, jednostavni 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 za ovu metodu temelji se na činjenici da ako je d odabrano dovoljno veliko da gruba sila nije prikladna, izračunavanje d nije ništa jednostavnije od rastavljanja n na faktore, jer ako je d poznat, tada se n lako rastavlja na faktore. To se može prikazati na sljedeći način. Ako je d poznat, tada se višekratnik Eulerove funkcije može izračunati pomoću uvjeta

gdje je k proizvoljan cijeli broj.

Faktorizacija od n može se izvršiti pomoću bilo kojeg višekratnika od . Razbijač šifre, s druge strane, može pokušati pronaći neku d" vrijednost koja bi bila ekvivalentna skrivenoj d" vrijednosti korištenoj za razvoj šifre. Ako postoji mnogo takvih d" vrijednosti, tada bi se mogao pokušati napad brutalnom silom razbiti šifru. Ali svi d" se razlikuju za faktor jednak i ako se ovaj faktor izračuna, onda se n može faktorizirati. Dakle, pronalaženje d je jednako teško kao rastavljanje n na faktore.

Dakle, glavna zadaća kriptoanalize asimetričnih sustava šifriranja 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 dan cijeli broj n>0 i trebamo, ako je moguće, pronaći dva broja a i b takva da je ab = n. Zapravo postoje dva različita problema: prvi, nazvan testom primalnosti, ispituje postoje li takvi a i b; drugi, nazvan dekompozicija, je zadatak njihovog pronalaska. Razmotrimo oba ova problema.

Prvi deterministički test.

Ovaj test temelji se na malom Fermatovom 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 od odabira broja a koji je manji od b i provjere

b pripadati klasi prostih brojeva prema uvjetu a b-1 1 (mod b) u skladu sa zadanim izrazom. U praksi je potrebno provjeriti samo nekoliko vrijednosti a. Odabir jednakog 3 omogućuje vam identificiranje svih složenih brojeva. Međutim, poznato je da ovaj test propušta složene Carmichaelove brojeve (na primjer, broj 561 = 3 x 11 x 17).

Drugi deterministički test.

Podijelite broj “b” redom sa 2, 3, ..., . Ako pri bilo kojem dijeljenju dobijemo ostatak nula, 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 za provjeru primarnosti broja “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 prost ako i samo ako je b | ((b-1)! + 1). Faktorijel (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 približno 100 102 znamenke.

Svi gore navedeni testovi bili su deterministički. To znači da za dati broj “b” uvijek dobijemo odgovor da li je prost ili složen. Ako riječ "uvijek" zamijenimo s "s određenom vjerojatnošću", tada postaje moguće konstruirati probabilističke testove, koji se također nazivaju testovima pseudoprimalnosti.

Prvi test vjerojatnosti.

Ovaj test otkriva sve sastavne Carmichaelove brojeve. Odabere se slučajni broj a u rasponu od 1 do b-1 i provjeravaju se uvjeti.

(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 zadovoljeni, ali ako je b složeni broj, tada oni nisu zadovoljeni s vjerojatnošću. Stoga izvođenje k testova jamči da je odgovor netočan s vjerojatnošću 2 -k.

Drugi test vjerojatnosti.

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

gdje je s paran broj. Zatim test nasumično odabire broj a u rasponu od 1 do b-1 i provjerava jesu li ispunjeni uvjeti

1 (mod b) za 0< j

Oba se testa koriste za provjeru pripada li broj klasi prostih brojeva i zahtijevaju operacije reda O(log 2 b) na velikim brojevima.

Treći test vjerojatnosti.

Za dano b, odaberite m, 1 nasumce

Vjerojatnost da je dan odgovor "b je složeni broj" jednaka je vjerojatnosti da je m | b. Ako je d(b), broj djelitelja b i m je slučajno odabran unutar 1

Ovo je vrlo slab test.

Četvrti test vjerojatnosti.

Za zadano "b", odaberite m, 1 nasumično

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

Peti test vjerojatnosti.

Ovo je test jake pseudo-jednostavnosti. Neka su zadani b i m. Neka

gdje je t neparan broj i razmotrite brojeve za (x r je najmanji ostatak apsolutne vrijednosti po modulu b).

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

Dokažimo ovo kontradikcijom. Pretpostavimo da je b neparan prost broj. Pokažimo indukcijom da je 1 (mod b) for, što će proturječiti uvjetima teorema.

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

znači da je broj koji se kvadrira jednak ±1. Ali -1 ne ispunjava uvjet (inače bi test dao odgovor "nije moguće odrediti").

Dokazano je da ako je b složeni broj, onda vjerojatnost da će test dati odgovor “b je složeni broj” nije ništa manja.

Rastavljanje velikih cijelih brojeva na faktore.

Problem pronalaženja djelitelja velikih prostih brojeva mnogo je gori od testa jednostavnosti. Ispod je metoda koja je najmoćnija poznata.

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

Pretpostavimo da želimo faktorizirati broj b. Neka je n = najveći broj koji ne prelazi i izračunajte brojeve a k = (n + k) 2 - b za male k (brojevi k mogu biti i negativni).

Neka je (q i, i = 1, 2, …, j) skup malih prostih brojeva koji mogu podijeliti izraz oblika x 2 - b (tj. b je kvadrat po modulu q i). Takav skup obično se naziva multiplikativna baza B. Sjetimo se svih brojeva a k koji se mogu proširiti u multiplikativnu bazu, t.j. napisano u obrascu

Takvi ak se nazivaju B-brojevi. Svaki B-broj ak pridružen je vektoru indikatora

Ako nađemo dovoljno B-brojeva tako da je skup odgovarajućih vektora indikatora linearno ovisan modulo 2

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

Definirajmo 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 se izvodi iterativno kako slijedi. Protivnik bira broj j za koji vrijedi relacija:

To jest, neprijatelj jednostavno šifrira presretnuti šifrirani tekst koristeći javni ključ j puta. To izgleda ovako: (C e) e) e ..) e (mod n)=C e j(mod n)). Pronašavši takvo j, neprijatelj izračunava C e (j-1)(mod n) (tj. ponavlja operaciju šifriranja j-1 puta) - ova vrijednost je otvoreni tekst M. Ovo slijedi iz činjenice da C e j(mod n ) =(C e (j-1)(mod n))e=C. To jest, neki broj C e (j-1)(mod n) na potenciju e daje šifrirani tekst C. A ovo je otvoreni 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. Predstavljanje sustava šifriranja grafom, princip jedinstvenosti šifriranja i dešifriranja.

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

4. Snaga sustava za šifriranje, klasifikacija sustava za šifriranje po snazi. Vrste napada na sustav šifriranja.

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

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

7. Računalno jaki kriptografski sustavi, koncept složenosti kriptoanalize, osnovni pristupi razbijanju kriptografskih sustava, analiza ključnih brute force napada i napada temeljenih na statistici poruka.

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

9. Zamjenska šifra, njena svojstva.

10. Gama šifra i njena svojstva.

11. Modovi (režimi rada) blok šifara, kratak opis modova.

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

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

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

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

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

17. Načela konstruiranja enkripcijskih gama generatora (koncept ekvivalentne linearne složenosti, korištenje nelinearnih čvorova za povećanje linearne složenosti).

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

19. Princip izgradnje i karakteristike AES šifre.

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

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

22. Funkcija raspršivanja prema standardu 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 ES RSHA.

27. El-Gamal EP shema.

28. Digitalni potpis prema GOSTR 34.10-12, opće karakteristike, princip generiranja i provjere potpisa.

29. Autentifikacija poruka u telekomunikacijskim sustavima (model sustava krivotvorina, strategije nametanja, indikatori krivotvorina).

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

31. Izgradnja autentifikacijskih sustava sa zajamčenom vjerojatnošću nametanja.

32. Izgradnja autentifikacijskog sustava za ponavljani prijenos poruka.

33. Računalno sigurni sustavi autentifikacije.

34. Razvoj imitacijskih umetaka u skladu s GOST R34.12-2015.

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

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

37. Metode generiranja slučajnih brojeva pri generiranju ključeva.

38. Metode za distribuciju ključeva pomoću DRC-a u početnoj fazi.

39. Metode distribucije ključeva korištenjem digitalnog distribucijskog centra u interaktivnom načinu rada. Needham-Schroederov protokol.

40. Načelo raspodjele javnih ključeva.

41. Pojam infrastrukture javnih ključeva (PKI), sastav, princip interakcije elemenata strukture.

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

Praktični dio

1. Šifrirajte (dešifrirajte) poruku ručno pomoću zamjene, permutacije i gama šifre. Program LR1_1.exe.

2. Dekriptirajte kriptogram na temelju analize njegove statistike pomoću programa CHANGE.EXE.

3. Odredite faktor množenja pogreške kod dešifriranja kriptograma blokovske supstitucijsko-permutacijske šifre s duljinom bloka od 16 bita. tst program.

4. Dekriptirati kriptogram supstitucijsko-permutacijske šifre iscrpnim pretraživanjem ključeva pomoću programa tst. Obrazložiti parametre za odlučivanje o ispravnom dekodiranju.

5. Šifrirajte 64-bitnu poruku koristeći osnovni algoritam šifriranja GOST R 34.12-2015 (1 krug)

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

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

8. Pronađite niz na izlazu enkripcijskog gama generatora koji sadrži elemente OR, NAND, Jeff. Koristim program LRR 2 za određivanje ekvivalentne složenosti niza. Konstruirajte ekvivalentni LRR. Donesite zaključke.

9. Izvršite sljedeće izračune u dijelu diskretne matematike:

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

Izračunajte x modp pomoću algoritma za brzo dizanje broja na potenciju;

Nađi inverz broja po modulu p.

Naći Eulerovu funkciju broja x;

10. - Fermatovim testom provjeriti je li broj x prost, odrediti vjerojatnost da test daje pogrešan rezultat.

11. Zadani su parametri sustava za šifriranje ElGamal: a=4, p=11, privatni ključ x=7, šifrirati poruku M=. Dešifrirajte kriptogram.

12. Parametri RSA enkripcijskog sustava su postavljeni na p=11, q=13, šifriraj poruku M=5. Dešifrirajte kriptogram.

13. Zadani su parametri sustava za šifriranje ElGamal: a=4, p=11, privatni ključ x=8, potpišite poruku čiji je hash kod h(M)= . Provjerite potpis.

14. Parametri RSA enkripcijskog sustava 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 pomoću sigurnog RSA kriptosustava i procijenite vrijeme enkripcije i dešifriranja.

16. Programom RSA potpišite poruke i ovjerite potpis. Duljina poruke je najmanje 100 bita.

17. Dana je eliptična krivulja E13(1,1). Odredite točku C koja je jednaka 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 u kojoj k =3.

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