Slika: Model šifriranja (Tanenbaum, 1996)

• poruka koja se šifrira je običan tekst (plaintext) P
• P se transformira na osnovu metode šifriranja (encryption method) - funkcije koja kao parametar koristi ključ (encryption key) K
• kao izlaz dobivamo šifrirani tekst (ciphertext) C koji se šalje na pr. preko glasnika, radiom,...
• uljez (intruder) može samo osluškivati komunikacijski kanal (pasivni uljez) ili može snimiti poruku, mijenjati je ili slati vlastitu (aktivni uljez)
• vrijedi: C = E_K(P) tj. šifriranjem teksta P pomoću ključa K dobijemo šifrirani tekst C
• obrnuto: P = D_K(C) predstavlja dešifriranje (decryption) šifriranog teksta C da bi se ponovo dobio početni obični tekst P (slijedi da je D_K(E_K(P))=P)
• E, D - odabrane matematičke funkcije čiji su parametri ključ i tekst (obični ili šifrirani)

• osnovno pravilo kriptografije je da onaj tko vrši dešifriranje mora znati korištenu metodu dešifriranja i ključ koji se u toj metodi koristio
• dok se osnovna metoda šifriranja mijenja nakon nekoliko godina, ključ se mijenja često -> osnovni model je stabilna i javno poznata općenita metoda koja kao parametar koristi tajni, lako izmjenjivi ključ
• dužina ključa je glavno pitanje kod njegova dizajna
• ključ se sastoji od znamenki (znakova) koje su unesene određenim redoslijedom i što je ključ duži, više je mogućih kombinacija i više je rada potrebno da ga onaj koji razbija šifru pogodi (može se koristiti npr. 256 bita)
• metode šifriranja dijele se povijesno u 2 kategorije: supstitucijske i transpozicijske šifre

1.1 Supstitucijske šifre 

• svako slovo ili grupa slova zamjenjuje se drugim slovom ili grupom slova tj. čuva se redoslijed slova, ali se ona “prerušavaju”
• najstarija poznata takva šifra je Cezarova šifra kod koje a postaje D, b postaje E, c postaje F,..., z postaje C (npr. attack postaje DWWDFN)
• generalizacija Cezarove šifre dozvoljava da se abeceda šifriranja pomakne za k slova, a ne za 3
• slijedeće poboljšanje je da se svaki znak preslika u neki drugi znak bez pravilnog pomaka (npr. attack postaje QZZQEA), na primjer:

P: a b c d e f g h i j k l m n o p q r s t u v w x y z

C: Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

 

• takav se sistem naziva monoalfabetska supstitucija kod koje je ključ niz od 26 slova koji odgovara čitavoj (engleskoj) abecedi
• mogućih ključeva ima 26! ≈ 4 x 10²⁶ ali se unatoč tome, poznajući već i manju količinu šifriranoga teksta, može pronaći ključ na osnovu statističkih osobina prirodnih jezika (gledaju se najčešća slova, kombinacije od 2 slova i kombinacije od 3 slova)

1.2 Transpozicijske šifre

• slova ostaju ista (ne zamjenjuju se kao kod supstitucijskih šifri), ali se mijenja njihov redoslijed (izmiješaju se)
• primjer - stupčana transpozicija:

Slika: Primjer transpozicijske šifre (Tanenbaum, 1996)

• ključ je riječ ili fraza koja ne sadrži ponavljajuća slova (u primjeru: MEGABUCK), a služi za numeraciju stupaca tako da je stupac 1 pod slovom koje je najbliže početku abecede
• obični tekst se piše u recima (vodoravno), a šifrirani tekst u stupcima počevši od onoga koji je označen kao stupac 1

1.3 Ključ za jednokratnu uporabu (One-Time Pads) 

• tehnika za konstruiranje šifre koja se ne može razbiti (unbreakable cipher):
• izabrati slučajni niz bitova kao ključ
• pretvoriti tekst u niz bitova (na primjer, korištenjem ASCII reprezentacije znakova)
• izračunati ISKLJUČIVI ILI (EXCLUSIVE OR) tih dvaju stringova, bit po bit

• rezultirajući šifrirani tekst ne može se razbiti jer je jednako vjerojatno za bilo koji obični tekst određene duljine da je tako šifriran
• nedostaci: ključ se ne može zapamtiti, pa i pošiljaoc i primaoc moraju držati kopiju uz sebe; velika osjetljivost na izmjene do kojih može doći u prijenosu

2. Dva osnovna principa kriptografije 

• principi koji su zajednički za različite kriptografske sisteme:
  1. redundancija (redundancy): sve šifrirane poruke moraju sadržavati određenu količinu suvišnih podataka, (tj. informacija koje nisu potrebne da se razumije poruka) kako aktivni uljezi ne bi mogli poslati slučajan niz znakova koji će se interpretirati kao ispravna poruka
  2. "svježina" (freshness): mora se spriječiti da aktivni uljezi ponovo šalju stare poruke - u poruke se uključuju vremenske oznake (timestamps)

• moderna kriptografija koristi iste osnovne ideje (supstituciju i transpoziciju) kao i klasična
• razlika: klasična je koristila jednostavne algoritme za šifriranje s vrlo dugačkim ključevima kao sigurnost, modernoj je cilj napraviti što složenijima algoritme

• algoritmi sa simetričnim ključem:
  • isti ključ se koristi za šifriranje i dešifriranje
  • šifre u blokovima - ulaz je n-bitni blok teksta koji se pomoću ključa transformira u n-bitni blok šifriranog teksta
  • kriptografski algoritmi mogu se implementirati hardverski (zbog brzine) ili softverski (zbog fleksibilnosti)
  • transpozicija i supstitucija mogu se primijeniti više puta u nizu i kombinirati na različite načine, a implementiraju se jednostavnim uređajima (električnim sklopovima) P-kutijom (P-box) i S-kutijom (S-box)

   

• 2 osnovna pristupa razbijanju šifre:
  • kriptoanaliza: na osnovu poznavanja prirode algoritma i nekih osnovnih osobina teksta (ili čak nekih uzoraka parova tekst-šifrirani tekst) nastoji se zaključiti koji je ključ korišten
  • "gruba sila" (brute-force): isprobava se svaki mogući ključ na komadu šifriranog teksta sve dok se ne dobije odgovarajući tekst
    - teže je (duže traje) što je duži ključ

DES (Data Encription Standard) 

• poznati algoritam sa simetričnim ključem
• DES (Data Encription Standard) šifru razvio je IBM, a 1977. ju je usvojila i vlada USA kao svoj službeni standard
• osnovna ideja: tekst se šifrira u blokovima od 64 bita, algoritam koristi 56 bitni ključ i odvija se u 19 faza:
  • prva faza je transpozicija teksta koja ne ovisi o ključu,
  • zadnja faza je inverz te transpozicije
  • predzadnja faza je zamjena 32 lijeva bita s 32 desna
  • ostalih 16 faza koriste istu funkciju, ali različite ključeve koji se izvode iz polaznog ključa

Slika: Faze DES-a i detalj jedne od 16 faza (Tanenbaum, 1996)

• ulaz je podijeljen na lijevi i desni sa po 32 bita

• lijevi izlaz je kopija desnog ulaza

• desni izlaz je XOR lijevog ulaza i funkcije nad desnim ulazom i ključem K_i za ovu i-tu fazu (iteraciju)

• sva kompleksnost se nalazi u funkciji

• unatoč kompleksnosti, DES je u osnovi monoalfabetska supstitucijska šifra koja koristi 64-bitne znakove, te uvijek isti 64-bitni šifrirani tekst odgovara istom 64-bitnom ulaznom tekstu
• da bi se povećala kompleksnost, kao jedna od metoda koristi se ulančavanje blokova šifri (cipher block chaining) kod koje se svaki blok običnog teksta prije šifriranja povezuje sa EXCLUSIVE OR sa prethodnim blokom šifre
• problemi kod DES:
  • i mala količina običnog teksta i odgovarajućeg šifriranog teksta je dovoljna da se nađe ključ dužine 56 bitova (namjerno kratki ključ?!) korištenjem vrlo jakog računala ili korištenjem velikog broja manje jakih računala koji dijele posao (problem se može riješiti korištenjem dužeg ključa npr. 128 bitnog)
  • distribucija ključeva: isti ključ je i za šifriranje i za dešifriranje, pa se mora distribuirati objema stranama koje ga moraju znati, a istovremeno spriječiti uljeze da dođu do njega
• AES (Advanced Encryption Standard) - novi sigurniji standard s duljinom blokova od 128 bita i podrškom za ključeve dužine 128, 192, 256 bita

• 1976. predložen je na Stanford University (Diffe, Hellman) potpuno novi sistem kriptografije kod koje su ključ za šifriranje i ključ za dešifriranje različiti, i ključ dešifriranja ne može se izvesti iz ključa šifriranja
• korisnik za šifriranje poruke koristi javni ključ (public key), a za dešifriranje poruke privatni (tajni) ključ (private key)
• zahtjevi koje trebaju ispuniti algoritam za šifriranje (E) s javnim ključem i algoritam za dešifriranje (D) s privatnim ključem:

1. D(E(P)) = P (ako primijenimo D na šifrirani tekst E(P) dobiti ćemo ponovo polazni tekst P
2. izuzetno je teško na osnovu algoritma E zaključiti kakav je D
3. algoritam E se ne može razbiti iako se ima dio dešifriranog  teksta

• uz ove uvjete ključ za šifriranje može biti javni ključ

Metoda:

Slika: Algoritam s javnim ključem (Tanenbaum, 1996)

• osoba A koja šalje poruku ima 2 algoritma E_A i D_A koji ispunjavaju gornje uvjete i od kojih je algoritam za šifriranje i njegov ključ E_A javni; javni je i algoritam za dešifriranje, ali je njegov ključ D_A tajni i poznat samo osobi A; analogno vrijedi za osobu B i ključeve E_B i D_B
• ako A želi poslati tajnu poruku P za B, uzima njezin javni ključ E_B i računa E_B(P), tako šifrirani tekst šalje osobi B koji ga dešifrira pomoću svog tajnog ključa D_B (računa D_B(E_B(P)) = P)

• problem kod metoda s javnim ključevima je kako naći algoritam koji ispunjava sva tri zahtjeva
• jedan od njih je RSA algoritam

RSA algoritam

• razvijen 1976. na MIT-u Rivest, Shamir i Adleman, a metoda se bazira na nekim principima teorije brojeva, tj. na nemogućnosti računala da u realnom vremenu vrši faktorizaciju velikih prim brojeva
• RSA je dosta spor za šifriranje većih količina podataka (zadovoljavajuće sigurnost se postiže s ključem od barem 1024 bita)
• često se koristi samo za distribuciju ključeva kod DES, a DES se dalje koristi za šifriranje ostalih podataka

Postupak:

1. izabrati 2 velika prim broja p i q (obično 1024 bita)
2. izračunati n = p x q i z = (p-1) x (q-1)
3. izabrati broj d relativno prim prema z
4. naći e tako da je e x d = 1 mod z
5. podijeliti tekst u blokove (ili poruke) P tako da svaki od njih bude 0 ≤ P < n
6. za šifriranje poruke P izračunati C = P^e mod n
7. za dešifriranje C izračunati P = C^d mod n
   -> funkcije za šifriranje i dešifriranje su inverzne
   (e,n) je javni ključ za šifriranje
   (d,n) je privatni ključ za dešifriranje

• kada bi se javno znani n uspio faktorizirati na p i q, našao bi se z, a zatim e i d -> teško

Primjer:

1. p=3, q=11
2. n=3 x 11=33, z=2 x 10=20
3. d=7
4. 7 x e = 1 mod 20 -> (7 x e)/20 = x + 1/20 -> e=3
5. C = P³ mod 33
6. P = C⁷ mod 33
   (3,33) je javni ključ za šifriranje
   (7,33) je privatni ključ za dešifriranje

Slika: Primjer za RSA (Tanenbaum, 2003)

5. Digitalni potpisi (Digital Signatures)
 

• treba pronaći odgovarajuću zamjenu za potpise pisane rukom čije se krivotvorenje može utvrditi
• potreban je sistem u kojem:
  • jedna strana može poslati “potpisanu” poruku drugoj tako da primaoc može provjeriti identitet pošiljaoca,
  • pošiljaoc ne može kasnije negirati poslanu poruku
  • primaoc ne može sam izmisliti poruku

5.1 Potpisi korištenjem simetričnih ključeva

• postoji centralni autoritet kojem svi vjeruju (BB - “Big Brother”) i koji ima pohranjen tajni ključ svakog korisnika, samo korisnik A i BB znaju za ključ K_A, korisnik B i BB znaju za ključ K_B itd.

Slika: Digitalni potpisi uz nadzor BB (Tanenbaum, 2003)

5.2 Potpisi korištenjem javnog ključa 

• razmjena potpisanih poruka bez nadzora nekog centralnog autoriteta (svaku poruku koja mu stiže može pročitati)
• koriste se algoritmi za šifriranje i dešifriranje pomoću javnog ključa koji imaju dodatnu osobinu da je E(D(P)) = P (uz standardnu: D(E(P)) = P ), npr. RSA

Slika: Digitalni potpisi korištenjem javnog ključa (Tanenbaum, 2003)

• osoba A šalje potpisanu poruku osobi B načinivši E_B(D_A(P))
• B primjenjuje prvo svoj privatni ključ D_B da bi dobio D_A(P), a zatim javni ključ  E_A da dobije tekst P od A
• da je zaista osoba A poslala poruku, može se provjeriti tako da se od B uzmu i P i D_A(P) i da se primjenom ključa E_A ustanovi da li je zaista E_A(D_A(P)) = P,
• ako to vrijedi, znači da je poruka zaista od osobe A jer jedina ona zna D_A

6. Upravljanje javnim ključevima

• problem sigurne razmjene javnih ključeva osoba koje se ne poznaju

• ključevima može upravljati distribucijski centar za ključeve koji je cijelo vrijeme on-line

• umjesto takvog centra jedan od načina je korištenjem certifikata (certificates)

Certifikati

• CA (Certification Authority) - organizacija koja potvrđuje javne ključeve

• osobe se registriraju u CA svojim javnim ključem i nekim osobnim podatkom, a CA izdaje certifikat (potvrdu) potpisan nekim digitalnim potpisom pri čemu se koristi privatni ključ tog CA

• osnovni zadatak certifikata: pridružiti javni ključ imenu osobe (ili neke organizacije, firme,...) - sami certifikati nisu tajni ili zaštićeni

Slika: Primjer certifikata (Tanenbaum, 2003)

• kad osoba A dohvati certifikat od B, primjeni algoritam korišten za digitalni potpis s javnim ključem od CA -> ako se dobiveni rezultat slaže s onim navedenim u certifikatu, riječ je zaista o pravom certifikatu od B

• na taj način CA ne mora biti stalno on-line

• X.509 - standard za certifikate