Primena teorije informacija u procesu generisanja kriptoloških ključeva

UNIVERZITET SINGIDUNUM

FAKULTET ZA INFORMATIKU I RAČUNARSTVO

Primena teorije informacija u procesu

generisanja kriptoloških ključeva

- diplomski rad -

Mentor:

Kandidat:

prof. dr

Mladen Veinovi

Nikola

Lazi

Beograd,

2016

MENTOR

__________________________

Prof. dr. Mladen Veinović

DEKAN

____________________

Prof. dr. Dragan Cvetković

FAKULTET ZA INFORMATIKU I RAČUNARSTVO

UNIVERZITET SINGIDUNUM

FAKULTET ZA INFORMATIKU I RAČUNARSTVO

Beograd, Danijelova 32

Kandidat:

Nikola Lazić

Broj indeksa:

2012/200460

Smer:

Informatika i računarstvo

Tema:

Primena teorije informacija u procesu generisanja kriptoloških ključeva

Datum odobrenja rada:

Beograd, ___.___._____.

Primena teorije informacija u procesu generisanja kriptoloških ključeva

- 1 -

Sadržaj

Uvod .................................................................................................................. - 3 -

1.1

Predmet istraživanja ................................................................................. - 3 -

1.2

Doprinos rada ........................................................................................... - 3 -

1.3

Struktura rada ........................................................................................... - 3 -

Pregled u oblasti istraživanja ......................................................................... - 4 -

2.1

Slučajni ključevi ....................................................................................... - 4 -

2.2

Generatori kriptoloških ključeva .............................................................. - 4 -

2.2.1

Linearni kongruentni generatori .................................................................... - 5 -

2.2.2

Linearni pomerački registri sa povratnom spregom ...................................... - 5 -

2.2.3

ANSI X9.17 ................................................................................................... - 6 -

2.2.4

FIPS 186 ........................................................................................................ - 6 -

2.2.5

RSA ............................................................................................................... - 7 -

2.2.6

Blum, Blum i Shub ........................................................................................ - 7 -

2.2.7

Aditivni generatori ......................................................................................... - 8 -

2.2.8

AT&T 7001 ................................................................................................... - 9 -

2.2.9

Intel TRNG .................................................................................................... - 9 -

2.2.10

Oscilacije vazduha u disku računara kao generator slučajnosti ..................... - 9 -

2.3

Testovi slučajnosti – standardi za testiranje slučajnosti ......................... - 10 -

2.3.1

Ispitivanje učestalosti u nizu ........................................................................ - 10 -

2.3.2

Ispitivanje učestalosti u bloku ..................................................................... - 11 -

2.3.3

Ispitivanje uzastopnih ponavljanja istih bitova u nizu ................................. - 12 -

2.3.4

Ispitivanje najdužeg uzastopnog ponavljanja jedinica u bloku ................... - 12 -

2.3.5

Ispitivanje stanja binarne matrice ................................................................ - 14 -

2.3.6

Ispitivanje diskretne Furijerove transformacije ........................................... - 15 -

2.3.7

Ispitivanje nepreklapajućih uzoraka ............................................................ - 15 -

2.3.8

Ispitivanje preklapajućih uzoraka ................................................................ - 16 -

2.3.9

Maurerov univerzalni statistički test ............................................................ - 17 -

Primena teorije informacija u procesu generisanja kriptoloških ključeva

- 2 -

2.3.10

Ispitivanje linearne kompleksnosti .............................................................. - 18 -

2.3.11

Serijski test .................................................................................................. - 19 -

2.3.12

Ispitivanje približne entropije ...................................................................... - 20 -

2.3.13

Ispitivanje slučajnih zbirova ........................................................................ - 20 -

2.3.14

Ispitivanje slučajne digresije ....................................................................... - 21 -

2.3.15

Ispitivanje slučajne promenljive digresije ................................................... - 22 -

2.4

Postdigitalna obrada generisanih sekvenci ............................................. - 23 -

2.4.1

Mapiranje prelaza ........................................................................................ - 23 -

2.4.2

Paritet niza ................................................................................................... - 24 -

2.4.3

Operacija XOR ............................................................................................ - 24 -

2.4.4

Brza Furijerova transformacija .................................................................... - 24 -

2.4.5

Kompresija .................................................................................................. - 24 -

2.4.6

Kompresija sa Jednosmernim funkcijama ................................................... - 25 -

Teorijske osnove istraživanja ....................................................................... - 26 -

3.1

Entropija ................................................................................................. - 26 -

3.2

Sigurnost kriptosistema .......................................................................... - 27 -

3.3

Ispitivanje slučajnosti ............................................................................. - 28 -

3.4

Generatori slučajnosti ............................................................................. - 29 -

3.5

Pravi slučajni generator (TRNG) ............................................................ - 30 -

3.6

Pseudo slučajni generator (PRNG) ......................................................... - 30 -

3.7

Uporedna analiza generatora slučajnosti ................................................ - 31 -

3.8

Postdigitalna obrada ............................................................................... - 32 -

3.9

Oblast primene ........................................................................................ - 33 -

Pregled predloženog rešenja ......................................................................... - 34 -

4.1

Vršenje testa slučajnosti računanjem uzajamne informacije .................. - 34 -

Zaključak ........................................................................................................ - 37 -

5.1

Predlog za budući rad ............................................................................. - 37 -

Literatura ....................................................................................................... - 38 -

Appendix ........................................................................................................ - 39 -

Primena teorije informacija u procesu generisanja kriptoloških ključeva

- 4 -

Pregled u oblasti istraživanja

U ovom poglavlju će biti predstavljeni složeniji generatori kriptoloških ključeva i

njihova  primena,  kao  i  najpoznatiji  metodi  postidigitalne  obrade  i  preporučeni  testovi
slučajnosti.  Posebna  pažnja  se  skreće  na  njihovu  neophodnost  u  ostvarivanju  kriptološke
sigurnosti u informacionim sistemima. Sigurnost šifarskog algoritma počiva na ključu. Ako
je  u  upotrebi  loš  algoritam  za  generisanje  ključeva,  ceo  sistem  se  dovodi  u  pitanje.
Kriptoanalitičar ne mora vršiti napad na ceo algoritam za šifrovanje već je dovoljno da se
usresredi samo na algoritam za generisanje ključeva da bi kompromitovao ceo sistem. Zbog
takvih razloga  obraća se pažnja na sam proces generisanja ključeva i njihov pravilan odabir.

2.1

Slučajni ključevi

Pojam slučajnosti prilikom generisanja kriptoloških ključeva je osnovni preduslov za

siguran kriptosistem, zato su jedni od najboljih ključeva nizovi bitova generisani na slučajan
način  nekim  automatskim  postupkom.  To  znači  da  ako  je  dužina  ključa  128  bita,  svaki
mogući 128-bitni ključ mora da bude podjednako verovatan.[4] Da bi se ostvarilo tako nešto,
bitovi ključa se moraju generisati iz pouzadnog slučajnog izvora ili korišćenjem generatora
pseudoslučajnih bitova koji ispunjava uslove kriptografske sigurnosti. Za proveru slučajnosti
generisane  sekvence  koriste  se  statistički  testovi  slučajnosti  kako  bi  smo  zaključili  da
ispitivani generator poseduje željena svojstva i da bi kao takav bio pogodan generator za
korišćenje.

2.2

Generatori kriptoloških ključeva

Generator slučajnih sekvenci koji je pogodan za korišćenje u kriptografiji ispunjava

uslov da i pored svih poznatih činjenica vezanih za sam generator (šema, algoritam, itd.)
reprodukuje  potpuno  nepredvidive  vrednosti.  Puno  su  kavlitetniji  od  generatora  koji  se
koriste za računarske simulacije. Zbog složenosti algortma znatno su sporiji od standardnih
generatora    ali  zbog njihove  namene u  kriprografiji,  gde  je  potrebno  generisati  mali  broj
vrednosti, brzina nije od presudnog značaja.  Tu spadaju dva osnovna tipa generatora PRNG
i TRNG čiji principi rada su detaljno opisani u nastavku ovog poglavlja. Da bi generator bio
dovoljno dobar za generisanje ključeva i sve ostale kriptografkse primene mora da ispuni
sledeća tri uslova:



Generator deluje kao da je slučajan. Verovatnoća pojave jedne generisane vrednosti
treba biti ista za sve vrednosti u prostoru u kome se generiše niz. Što znači da prolazi
sve statističke testove slučajnosti.



Sekvenca je nepredvidiva. To znači da je matematički nemoguće predvideti sledeći
slučajan bit jer ne sme da postoji zavisnost između generisanih sekvenci podniza.



Generator se ne može reprodukovati. Ako se dva puta aktivira generator dobijaju se
dve međusobno potpuno nezavisne slučajne sekvence. Generator je dobro
konstruisan ukoliko je broj stanja kroz koja on prolazi prilično veliki.