Bi = E(Di-1) Ki

(2.9)

i.	Svaki redak mora sadržavati sve brojeve od 0 do 15.
ii.	Niti jedna S-kutija ne smije biti linearna ili afina funkcija ulaznih podataka.
iii.	Promjena jednog bit ulaznog podatka nakon primijene S-kutije rezultira promjenom barem dva bit izlaznog podatka.
iv.	Za svaku S-kutiju i svaki ulazni podatak Bij rezultati od S[Bij] i S[Bij  001100]se razlikuju u barem dva bita
v.	Za svaku S-kutiju i svaki ulazni podatak Bij i sve e,f e {0, 1} vrijedi S[Bij]  S[Bij  00ef00].

1. Četiri izlazna bita iz svake S-kutije moraju utjecati na šest različitih S-kutija u idućoj rundi.
2. Četiri izlazna bit iz svake S-kutije u i-toj rundi su distribuirana tako da dva od njih utječu na središnje bitove, a dva na krajnje bitove u (i+1)-voj rundi.
3. Za dvije S-kutije S_k i S_j mora vrijediti da ako neki izlazni bit od S_j utječe na neki od središnjih bitova S_k u idućoj rundi, onda niti jedan od izlaznih bitova S_k ne utječe na središnje bitove od S_j.

•	Morao je biti simetričan.
•	Mora je kriptirati 128-bitne blokove.
•	Mora je raditi s ključevima duljine 128, 192 ili 256 bitova.
•	Izvorni tekst algoritma treba je biti javno dostupan.

(2.13)

1. Subbytes zamjenjuje svaki element AES-bloka s njegovim GF(2⁸) inverzom te potom na svaki bit bloka primjenjuje fiksu afinu transformaciju. Transformacijuje moguće prikazati pomoću S-kutije. Prikazujući elemente AES-bloka u heksadecimalnom obliku prvi broj moguće je tumačiti kao oznaku reda, a drugi kao oznaku stupca S-kutije. Element se zamjenjuje s onim elementom S-kutije koji se nalazi na presjecištu označenog reda i stupca.

   (2.14)

2. Shiftrows ciklički posmiče redove novo dobivenog bloka ulijevo za i mjesta, gdje je i broj reda nad kojim se vrši operacija.
3. Mixcolums miješa stupce AES-bloka. Elementi stupca se tumače kao polinom oblika a_3ix³+ a_2ix²+ a_1ix+ a_0i te GF(2⁸)-množe polinomom 03x³+01x²+01x+02. Konačan rezultat dobiva se primjenom modulo x⁴+1 na rezultat množenja polinoma. U posljednjoj iteraciji miješanje stupaca se izostavlja.
4. Addroundkey provodi XOR operaciju nad AES blokom s međuključem odgovarajuće runde. Ovaj korak provodi se dodatno prije prve iteracije.

Slika 2-1 AES

gdje su p i q prosti brojevi te vrijedi: Za i e : x,y e Zn

(3.10)

1. Generacija ključeva. Odabiru se dva velika prosta broja p i q, tako da je p,q>10¹⁵⁰. Brojevi p i q ne smiju biti sličnih vrijednosti jer to olakšava njihovo određivanje. Isto tako je poželjno da p1 i q1 sadrže barem jedan veliki prosti faktor jer postoje efikasne metode faktoriziranja brojeva koji sadrže samo male proste faktore. Nakon određivanja p i q izračunava n=p*q, a potom (n). Odabire se broj e<(n), takav da je relativno prost u odnosu na (n). Uz pomoć e i (n) se izračunava d, tako da vrijedi:

   e*d mod (n)= 1

   (3.11)

2. Šifriranje. Poruka x < n se kriptira javnim ključem.

   y=xe mod n

   (3.12)

3. Dešifriranje. Šifrant y se dekriptira privatnim ključem.

   x=yd mod n

   (3.13)

Slika 3-1 RSA

•	Lako je generirati hash tj. izlazni bitovni niz, za svaku poruku bez obzira na njenu duljinu.
•	Nemoguće je u razumnom vremenu iz hash-a generirati izvornu poruku.
•	Nemoguće je promijeniti  poruku bez da se promijeni hash.
•	Nemoguće je u naći dvije poruke koje imaju isti hash.

Slika 4-1 Rad hash funkcije

1.	Prvo se inicijalizira 8 hash vrijednosti, h0 do h7. Inicijalizacije predstavljaju frakcionalne dijelove drugih korijena prvih
	osam prostih brojeva.



(4.1)

2.	Inicijalizira se polje od 64 cjelobrojnih konstanti, k0 do k63. Konstante se izračunavaju kao frakcionalni dijelovi trećih krojena
	prvih 64 prosta broja.



(4.2)

3.	Tekstu na koji će biti primijenjen hash se dodaje bit 1 te n bitova 0 tako da duljina ukupne poruke pri dijeljenju s 512 daje ostatak
	448. Potom se poruci dodaje 64-bitovni zapis koji izražava duljinu poruke bez prethodno dodanih bitova. Na ovaj način dobiva se poruka 
	čija je duljina cjelobrojni višekratnik od 512. 
4.	Poruka se dijeli na 512-bitne blokove. Za svaki blok se alocira polje od 64 32-bitne riječi. Blok se upisuje u prvih šesnaest elemenata
	polja te potom proširuje u preostalih 48 elemenata polja sljedećim algoritmom:


for(i=16;i<64;i++){ 

s0= rotiraj_x_u_desno_za_n(w[i-15],7) ^ 

rotiraj_x_u_desno_za_n(w[i 15] ,18) ^ 

shiftaj_x_u_desno_za_n(w[i-15],3); 

s1=rotiraj_x_u_desno_za_n(w[i-2],17) ^ 

rotiraj_x_u_desno_za_n(w[i-2],19)^ 

shiftaj_x_u_desno_za_n(w[i-2],10);

w[i]=w[i-16]+s0+w[i-7]+s1;

}
(4.3)

5.	Nad rezultatom prethodnog koraka se potom provodi kompresijska funkcija:


for(i=0;i<64;i++){ 

S1=rotiraj_x_u_desno_za_n(h[4],6)^ rotiraj_x_u_desno_za_n(h[4],11)
^ rotiraj_x_u_desno_za_n(h[4],25);

ch= (h[4] & h[5] ) ^ (~h[4] & h[6]);

temp1= h[7] +S1+ch+k[i]+w[i];

S0=rotiraj_x_u_desno_za_n(h[0],2)^ rotiraj_x_u_desno_za_n(h[0],13)^
 rotiraj_x_u_desno_za_n(h[0],22);

maj=(h[0] & h[1] ) ^ (h[0] & h[2] ) ^ (h[1] & h[2] );

temp2=S0+maj;

h[7]= h[6];

h[6]= h[5];

h[5]= h[4];

h[4]= h[3]+temp1;

h[3]= h[2];

h[2]= h[1];

h[1]= h[0];

h[0]=temp1+temp2;

} // h[i]= copy_of(hi) ; k[i]= ki;

(4.4)

6.	Nakon kompresijske funkcije se originalnim hash vrijednostima h0,…, h7 pridodaju izračunate hash vrijednosti h[0],…, h[7]. Tako 
	da je hi= h[i]+hi, i e {1,…7}.
7.	Konačna hash vrijednost dobiva se spajanjem hash vrijednosti.

Slika 4-2 SHA-2 algoritam

1.	Memorije stanja, S koja se sastoji od b bitova. Bitove memorije stanja moguće je logički podijeliti u dvije skupine. Na bitove 
	bitrata R i bitove kapacitet C.
2.	Funkcije f(S) koja permutira memoriju stanja.
3.	Funkciju proširenja P(x), gdje je x ulazni tekst. Funkcija izvorni tekst proširuje tako da njegova duljina postane cjelobrojni 
	višekratnik bitrata R.

I.	U prvom koraku inicijalizira se početno stanje S u nula i izvorni tekst se proširuje uz pomoć funkcije P(x).
II.	Drugi korak ima onoliko iteracija koliko puta je izvorni tekst veći od bitrata R. Za svaki blok veličine bitrata bitrat i taj blok
	se XOR-aju i izvede se Si=f(Si-1).
III.	U zadnjem koraku dolazi do ispisa. Bitrat memorije stanja se ispisuje. Ako je traženo još bitova za ispis odvija se Si=f(Si-1)
	i nakon toga se bitrat ponovo ispisuje. Ukoliko tražena duljina izlaznog niza nije višekratnik duljine bitrata prilikom zadnjeg ispisa
	odbacuju se bitovi viška.

1)	 funkcija, prikazana slikom 4-3 preuzetoj iz [5]  izračunava paritet svakog stupa matrice te nad svakim elementom matrice provodi 
	XOR s XOR-om pariteta dvaju predodređenih stupaca. Matematički je funkciju moguće zapisati kao:



(4.6)
	

 

Slika 4-3   funkcija 

2)	 funkcija rotira svaku od 64-bitnih riječi za različiti trokutasti broj mjesta. Rad funkcije prikazan je na slici 4-4 preuzetoj
	iz  [5] . Trokutasti brojevi su brojevi oblika Br=  Matematički je postupak funkcije moguće zapisati kao:


za t=0,…,24 i 
(4.7)


 

Slika 4-4   funkcija 

3)	 je transpozicija stanja.   funkcija prikazana je na slici 4-5 preuzetoj iz [5]  Matematički ju je moguće zapisati kao:



(4.8)


 

Slika 4-5   funkcija 

4)	 je jedina nelinearna operacija u SHA-3. Svaki element matrice XOR-a se s XOR-om pariteta dvaju predodređenih redova kao što je 
	prikazano na slici 4-6 preuzetoj iz [5] . Matematički je operaciju moguće prikazati kao:



(4.9)


 

Slika 4-6   funkcija 

5)	operacija svaki element XOR-a s konstantnom vrijednošću RC[zr]. Matematički se prikazuje kao:



(4.10)
 

Slika 4-7 Spužvasta funkcija

•	Poznavanje samo šifranta. 
•	Poznavanje izvornog teksta i njemu odgovarajućeg šifranta.
•	Poznavanje točno određenog izvornog teksta i njegovog šifranta.
•	Poznavanje više šifranata izvornog teksta koji se razlikuju zbog korištenja različitog ključa kriptiranja. Iako su sami ključevi 
	kriptiranja nepoznati napadač zna za nekakav logički odnos među njima.

•	Vrijeme. Zbog različitih brzina i načina izvođenja algoritama na različitim procesorima za vrijeme se ne uzima mjera sekunde već 
	broj osnovnih operacija procesora koje je potrebno izvesti prilikom izvođenja algoritma.
•	Memorija. Različiti napadi zahtijevaju različite količine memorijskog prostora za svoje izvođenje.
•	Informacije. Različiti napadi zahtijevaju različite količine informacija o sustavu kojeg nastoje ugroziti. Za količinu potrebnih 
	informacija često se uzima količina izvornog teksta i količina šifranta potrebna za ugrožavanje sustava.

•	Totalnim probojem- slučaj kada napadač otkrije tajni ključ šifriranja.
•	Globalnom dedukcijom- slučaj kada napadač sazna funkcijski ekvivalent algoritma ali ne sazna tajni ključ korišten prilikom šifriranja.
•	Lokalnom dedukcijom- slučaj kada napadač otkrije dodatne količine izvornog teksta i/ili šifranta.
•	Informacijska dedukcija- napadač sazna Shannonovske informacije o izvornom tekstu i/ili šifrantu. 
•	Prepoznavanje algoritma- napadač prepozna način šifriranja.

5.2.1 Diferencijalna kriptoanaliza

1.	S-kutija označava se s Sj, j e {1, …, 8}. Par 6-bitnih ulaznih nizova u S-kutiju označava se s Bj, Bj* a par 4-bitnih izlaznih nizova s  Sj(Bj) i Sj(Bj*)  .
	Za svaki par ulaznih nizova jednakog input XOR-a izračunava se output XOR njihovih šifranata. Zbog šest bitova za svaki input XOR postoji 
	26=64 para. Činjenica da output XOR-ovi nisu uniformno distribuirani između 16 mogućih vrijednosti osnova je diferencijalna napada.
2.	Za i Cj definira se :



(5.1)

	Podsjetimo se da vrijedi Bi= E(Di-1)  Ki  za ulazni podatak S-kutije u i-toj rundi. Zbog provedenih operacija vrijedi:



(5.2)

	Važno je primijetiti kako input XOR ne ovisi o međuključu.
3.	B, E, B*, E*, K zapisuju se kao:



(5.3)

	Potom se definira:


 

gdje je 

 


(5.4)

	Za navedeni skup jednadžbi vrijedi:


 
(5.5)
 

5.2.2 Linearna kriptoanaliza

I.	Bitovi izvornog teksta, šifranta i ključa označavaju se kao:


 
(5.6)

	Uvodi se i oznaka:


 
(5.7)

II.	Nakon toga traže se linearne jednadžbe oblika:


 
(5.8)

	koje za nasumični izvorni tekst i šifrant vrijede s vjerojatnošću  . Vjerojatnost desne strane dobiva se njenim izračunavanjem za veliki 
	broj parova izvorni tekst, šifrant.
III.	Ako je u više od pola slučajeva na lijevoj strani nula i  za vrijednost se uzima nula, a za  se uzima jedan. Na taj način dobiva 
	se linearna jednadžba u bitovima ključa. Uz dovoljno velik broj takvih jednadžbi postaje moguće odrediti ključ.
IV.	Kako bi metoda bila uspješna kod DES algoritma preporuča se uzimanje  parova izvornog teksta i šifranta.
Linearnu kriptoanalizu prvi je opisao Mitsuru Matsui 1993. godine kao teoretski napad na DES algoritam. Napad zahtijeva 247 poznatih 
izvornih tekstova što ga čini nepraktičnim za upotrebu. 

5.2.3 Meet in the middle napad

5.3.1 Pollardova p-1 metoda

5.3.2 Fermatova metoda faktorizacije

(5.11)

5.3.3 Algoritam Indeks-calculus

(5.12)

(5.13)

1.	Isprazni se lista relacija
2.	Za k={1,2…} uz pomoć cjelobrojne faktorizacije prilagođenje za glatke brojeve faktorizira se ak mod p po faktorskoj bazi. 
	Sprema se svaki pronađeni k i njemu odgovarajuću faktorizaciju kao relaciju. Ako je novo dodana relacija linearno nezavisna 
	od prethodno dodanih relacija zadržava se. Jednom kad se skupi r+1 takva relacija prestaje traženje novih relacija. r je veličina faktorske baze.
3.	Formira se matrica čiji redovi predstavljaju relacije.
4.	Matrica se svede na reducirani kanonski oblik odnosno prvi red je diskretni logaritam od -1 drugi od 2 itd.
5.	Za s={0,1,2…} pokuša se faktorizirati  as*b mod p po faktorskoj bazi. Kad se pronađe faktorizacija vraća se  

5.4.1 Rođendanski napad

1.	Pripremaju se dvije inačice dokumenta. Jedna dobronamjerna i jedna zlonamjerna. 
2.	Za svaku od inačica pripremi se mnogo varijanti istog smisla. Primjer izrada više varijanti istog dokumenta prikazan je na slici 5-1.


Suprotno ljudskoj intuiciji sasvim/vrlo je lako/jednostavno napraviti/izraditi velik broj verzija/varijacija istog teksta bez promjene/
mijenjanja smisla/značenja.
Gornja rečenica ima 26 tj. 64 različite verzije.

Slika 5-1 Izrada više tekstova istog značenja 

3.	Potom je potrebno pronaći dvije inačice, jednu dobronamjernu i jednu zlonamjernu, koje imaju isti hash.
4.	Zbog toga što inačice imaju isti hash imaju i isti potpis. Dovoljno je nekome dati dobronamjerni dokument da ga potpiše i kasnije je 
	moguće tvrditi da je potpisao zlonamjerni dokument. 

5.4.2 Tablica Rainbow

1.	Definira se redukcijska funkcija R koja za dobiveni hash generira tekst P. R ne mora biti inverz hash funkcije. 
2.	Uzastopnom primjenom hash funkcije i redukcijske funkcije formiraju se hash lanci. Primjer hash lanca prikazan je na slici 5-2 preuzetoj 
	s adrese: http://en.wikipedia.org/wiki/Rainbow_table .

 

Slika 5-2 Hash lanac 

3.	Početak i kraj svakog hash lanca sprema se u tablicu. 
4.	Uzima se hash vrijednost h za koju se želi dobiti izvorni tekst ili neki njemu iste hash vrijednosti. Na vrijednost h se uzastopno 
	primjenjuje redukcijska funkcija R i hash funkcija H dok se ne pojavi vrijednost jednaka jednoj od krajnjih vrijednosti u tablici.
5.	Uzima se početna vrijednost koja odgovara dobivenoj krajnjoj vrijednosti te se razvija hash lanac. Postoji dobra šansa da lanca sadrži 
	vrijednost h. Ona vrijednost koja prethodi h je traženi password.

Slika 5.3 Sučelje programa koji radi rainbow tablice

•	Simetrični algoritmi:
		Data Encryption Standard
		Triple Data Encryption Standard
		Advanced Encryption Standard
•	Asimetrični algoritmi:
		RSA kriptosustav
		Elliptic curve cryptography
•	Hash algoritmi:
		SHA-2
		SHA-3 

•	Kriptoanaliza simetričnih algoritama
		Diferencijalna kriptoanaliza
		Linearna kriptoanaliza
		Meet in the middle napad
•	Kriptoanaliza asimetričnih algoritama
		Pollardova p-1 metoda
		Fermatova metoda faktorizacije
		Algoritam Indeks-calculus 
•	Kriptoanaliza hash algoritama
		Rođendanski napad
		Tablica Rainbow