sis

Kada se matrica kontrole pristupa podeli na kolone
dobijaju se liste kontrole pristupa (ACL)
U modelu sigurnosti sa više nivoa:
svakom objektu se dodeljuje stepen tajnosti
Odabrati tačan (jedan) iskaz:
za C liste važi
lako se menjaju prava u odnosu na korisnike
Kad se matrica kontrole pristupa podela na vrste
dobijaju se liste deljenih prava (CL)
Da bi se postavio IDS zasnovan na anomalijama neophodno je:
prvo definisati “normalno” ponašanje sistema koji se štiti
U modelu sgurnosti sa više nivoa odrediti stepen tajnosti (1 najviši, 4 najniži)
1 državna tajna
2 strogo poverljivo
3 poverljivo
4 bez stepena tajnosti
Mrežna barijera se realizuje:
može biti i softver i hardver
Koju od dole navedenih usluga ne pruža mrežna barijera?
sprečavanje prekoračenja bafera
Mrežna barijera tipa application proxy
analizira kompletan paket i pamti stanje konekcije
Nedostatak IDS-a za detekciju anomalija je to što
može da generiše previše lažnih alarma
Autorizacija je proces kojim se ispituje:
prava korisnika koji pristupa sistemu
Odabrati tačan (jedan) iskaz:
za ACL važi
zaštita je orijentisana prema podacima
Potpuno automatizovan javni Tjuringov test za razlikovanje čoveka od računara tj. Test koji čovek
može da prođe sa lakoćom dok računar ne može da ga prođe sa verovatnoćom od one koja bi se
postigla nasumičnim pogađanjem naziva se:
captcha
Komunikacioni kanal koji nije projektovan od strane dizajnera sistema i nije pod kontrolom ali
može da posluži za protok informacija naziva se:
tajni
Kada se matrica kontrole pristupa podeli na kolone
dobijaju se liste kontrole pristupa (ACL)
Mrežna barijera koja ima filter paketa sa uspostavljanjem stanja (statefull firewall)
pamti zahteve za uspostavljanjem veze tokom sesije
Kod velikih sistema direktna primena Lampsonove matrice je:
složena i spora za izvršenje
Prednost mrežne barijere tipa packet filter je:
ne usporava saobraćaj (efikasnost)
Koliko osnovnih tipova mrežnih barijera postoji:
3
Bitno svojstvo IDS‐ a zasnovanog na potpisu je:
brzo i jednostavno otkrivanje već poznatih napada
Mrežna barijera tipa stateful packet filter
analizira zaglavlja paketa i prati stanje konekcije
Komunikacioni kanal koji nije projektovan od strane dizajnera sistema i nije pod kontrolom ali
može da posluži za protok informacija naziva se:
tajni kanal
Mrežna barijera koja možwe da spreči širenje zlonamernog softvera
je tipa application proxy
Sistemi koji treba da registruju napade u toku njihovog dešavanja ili naknadno, analizom podataka
nazivaju se:
sistemi za detekciju upada
Izabrati tačan iskaz:
i ACL lista i C lista su izvedene iz Lampsonove kontrolne matrice
Jedan (od nekoliko) preduslova za postojanje tajnog kanala je da:
prijemnik i predajnik dele neke zajedničke resurse
Prednost IDS zasnovanog na anomalijama je to što:
mogu da otkriju nepoznate napade
CAPTCHA je:
test za restrikciju pristupa za automatizovane sisteme
Stalno ažuriranje IDS-a zasnovanog na potpisu je:
neophodno
Modeli sigurnosti:
samo daju preporuke za dodatna ograničenja
Model sigurnosti sa više nivoa je pojam koji se odnosi na uvođenje:
različitih stepena tajnosti resursa
Idealna biometrija ne podrazumeva:
obavezno korišćenje lozinki
Slučajna vrednost (salt) koja se pridružuje lozinkama je:
javna
Dvo faktorska autentifikacija zahteva:
bilo koje 2 od 3 stavke (nešto što znate/imate/jeste)
Autentifikacija (samo) smart karticom je odluka na osnovu nečega
što korisnik ima
Autentifikacija koja zahteva sve tri stavke (nešto što se zna, ima i jeste) naziva se
trofaktorska
Autentifikacija pomoću otiska prsta je odluka na osnovu nečega
što korisnik jeste
Teoretski, biometrisku autentifikaciju je najbolje vršiti pomoću:
karakteristika irisa
U praksi, biometriјsku autentifikaciju je najbolje vršiti pomoću:
otiska prsta
U fajlu lozinki za svakog korisnika, između ostalog, čuva se vrednost koja se dobija tako što se
računa:
heš(lozinka+slučajna vrednost)
U biometrijskim sistemima prilikom autentifikacije (verifikacije) :
postoje 2 faze
Single sign on je postupak kojim se obezbeđuje:
da se korisnik prijavljuje samo jedanput a sve ostale naknadne prijave se obavljaju automatski
Jedno od mogućih rešenja za single sign on je:
smart kartica
Kontrola pristupa se sastoji od
autentifikacije i autorizacije
Rečnik često korišćenih lozinki:
postoji
Keylogger je:
hakerska komponenta za presretanje lozinki
Autentifikacija lozinkom je odluka na osnovu nečega
što korisnik zna
Autentifikacija pomoću smart kartice gde se dodatno zahteva i ukucavanje PIN koda je
autentifikacija na osnovu nečega što:
korisnik ima i zna
U praksi, kao najprihvatljivije rešenje za izbor lozinki pokazao se izbor:
zasnovan na frazama
Slučajna vrednost koja se dodaje lozinkama služi:
da se oteža napad rečnikom
Faza prepoznavanja je faza kod:
autentifikacije koja se zasniva na nečemu što jeste
Salt je:
slučajna vrednost koja se dodaje na lozinku
Izabrati tačan iskaz:
IPSec postoji na mrežnom nivou (deo je operativnog sistema)
Ticket Granting Ticket (TGT) je pojam vezan za sledeći protokol:
Kerberos
Kod challenge-response autentifikacije, ukoliko Boban želi da autentifikuje Anu on joj šalje:
slučajnu vrednost
Timestamp je podatak koji se koristi u bezbednosnim protokolima:
da bi se sprečilo napad ponovljenog slanja poruke
Kod autentifikacije koja koristi javni ključ nije bezbedno:
šifruj pa potpiši uz upotrebu podatka o vremenu
IKE (Internet Key Exchange) i ESP/AH (Encapsulating Security Payload/Authentication Header) su
dve celine:
IPsec protokola
Izabrati tačan iskaz:
SSL postoji na socket nivou (deo je korisničkog prostora)
TCP protokol ne bi trebao da se koristi za autentifikaciju jer:
upotreba IP adrese za autentifikaciju ima ozbiljne sigurnosne nedostatke
Kod protokola Kerberos tačno je:
Kerberos je zasnovan na simetričnom kripto sistemu
Izbaciti uljeza:
TCP
Sesijski ključ je
simetrični ključ samo za jednu komunikaciju
Challenge-Response je
protokol za autentifikaciju
Timestamp:
je podatak o trenutnom vremenu koji se koristi u bezbednosnim protokolima
U protokolima za autentifikaciju mogu se koristiti:
simetrični i asimetrični kriptografski algoritmi i heš
Cilj savršene sigurnosti unazad (PFC) je:
da se spreči da neovlašćeno lice dešifruje poruke koje su ranije razmenjene čak i ako naknadno
sazna tajni ključ
Kod protokola za autentifikaciju zasnovanih na kriptografiji sa javnim ključem treba koristiti:
različit par ključeva za šifrovanje i digitalno potpisivanje
Sigurnosni protokol koji je zasnovan na poverenju u treću stranu je:
Kerberos
Izabrati tačan iskaz:
IPSec nudi šifrovanje, integritet i autentifikaciju
Koje od sledećih svojstava nije poželjno za sigurnosni protokol:
da bude što komplikovaniji i računski složen
Izabrati tačan iskaz:
SSL nudi šifrovanje, integritet i autentifikaciju
Izabrati tačan iskaz:
straničenje deli memoriju na segmente fiksne veličine a segmentacija na segmente promenljive
veličine
Jedan od osnovnih problema koje operativni sistem treba da reši je efikasna podela resursa
računara.
Podela kod koje samo jedan korisnik/proces u jednom trenutku može da koristi resurs naziva se:
privremena podela
Jedan od nedostataka segmentacije memorije kao metode zaštite je to što:
može da dovede do fragmentacije memorije
NGSCB je deo operativnog sistema koji:
podržava hardversku tehnologiju članova grupe TCG
Na sigurnost operativnog sistema opšte namene broj linija programskog koda kernela utiče na
sledeći način:
Manji broj linija koda smanjuje mogućnost grešaka i olakšava rešavanje problema i propusta
Page table koristi operativni sistem da bi:
povezao stranice u koje je upisan neki podatak ili program
TCB (Trusted Computing Base) je:
skup zaštitnih mehanizama implementiranih u operativnom sistemu za koje se veruje da obezbeđuju
zahteve sigurnosti
Jedan od osnovnih problema koje operativni sistem treba da reši je efikasna podela resursa
računara.
Podela kod koje se različitim korisnicima/procesima dodeljuju različiti resursi naziva se:
fizička podela
Nedostatak fizičke podele resursa je to što:
je skupo i nepraktično
Jedan od osnovnih problema koje operativni sistem treba da reši je efikasna podela resursa
računara.
Podela kod koje se različitim korisnicima/procesima dodeljuju određeni delovi resursa naziva se:
logička podela
Višestruko prepisivanje sadržaja diska različitim podacima se primenjuje:
radi zaštite podataka kada više korisnika koristi isti memorijski prostor
Operativni sistem od poverenja ne mora da obezbedi:
grafičko okruženje
Kod operativnih sistema opšte namene preporučljivo je da aktivnosti i mehanizmi od značaja za
sigurnost budu implementirani na:
Jednom sloju kako bi analiza i ispravka bila jednostavnija i brža
Sigurnost operativnog sistema opšte namene se najefikasnije realizuje:
Kroz sigurno jezgro (kernel)
Granične adrese koje koristi jedan korisnik/proces kod istoimene metode mogu da budu:
obe istovremeno statičke ili obe istovremeno dinamičke
Segmentacija i straničenje su metode koje se koriste za zaštitu:
memorije
Monitor referenci je:
deo sigurnog jezgra koji je zadužen za kontrolu pristupa
Ako su istovremeno primenjeni MAC i DAC :
onda je MAC "stariji" od DAC
Jedna od prednosti segmentacije memorije kao metode zaštite je:
moguće je ostvariti različite nivoe zaštite kod različitih segmenata
Na sigurnost operativnog sistema opšte namene broj linija programskog koda kernela utiče na
sledeći način:
Manji broj linija koda smanjuje mogućnost grešaka i olakšava rešavanje problema i propusta
Šta ne spada u osnovne zadatke NGSCB (Next Generation Secure Computing Base):
DRM
Kod operativnih sistema opšte namene preporučljivo je da aktivnosti i mehanizmi od značaja za
sigurnost budu implementirani na:
Jednom sloju kako bi analiza i ispravka bila jednostavnija i brža
Kod diskrecione kontrole pristupa ko određuje prava pristupa objektu?
vlasnik objekta
Jedan od osnovnih problema koje operativni sistem treba da reši je efikasna podela resursa
računara.
Podela kod koje svi korisnici/procesi mogu da koriste sve resurse ali su podaci razumljivi samo
vlasniku dok su za ostale nerazumljivi naziva se:
kriptografska podela
Kod obavezne kontrole pristupa ko određuje prava pristupa objektu?
administrator sistema
Model granične adrese je model koji se korsiti za
zaštitu memorije
Koji program ovde ne pripada:
Brain
Za prikupljanje naizgled nebitnih podataka sa više različitih izvora koji objedinjeni daju konkretnu
informaciju koristi se:
salami attack
Zlonamerni programi koji omogućavaju neautorizovan pristup sistemu nazivaju se:
trapdoor (backdoor)
Salami Attack predstavlja:
serija malih beznačajnih napada koji se mnogo puta ponavljaju
Detekcija potpisa kao metoda za otkrivanje zlonamernih programa se zasniva na:
traženju sličnosti sa već poznatim zlonamernim programima
Prednosti metode za detekciju zlonamernih programa koja se zasniva na praćenju promena je to što:
može da detektuje i do tada nepoznate zlonamerne programe
Mane anti-virusa koji detektuje zlonamerne programe na osnovu potpisa su:
Ne može da otkrije nove i promenljive zlonamerne programe, baza potpisa može da postane velika,
što usporava rad.
Zlonamerni programi koji se šire tako što navedu korisnike da pokrenu (najčešće) besplatne
aplikacije za koje se kasnije pokaže da imaju funkciju različitu od očekivane nazivaju se:
trojanski konj
Detekcija promena kao metoda za otkrivanje zlonamernih programa se zasniva na:
praćenju promena u fajlovima
Metamorfični zlonamerni program:
menja svoj oblik ali zadržava funkcionalnost pre nego što inficira novi sistem
Uobičajeno, zlonamerni programi se dele na osnovu:
principa širenja i delovanja
Logičke bombe su posebna vrsta:
trojanskog konja
Zlonamerni program koji se ugrađuje u neki koristan program i aktivira se kada se ispune
odgovarajući uslovi naziva se:
logička bomba
Zlonamerni računarski kod koji može da se integriše na postojeći program ili fajl i da se na taj način
prenosi sa računara na računar naziva se:
virus
Zlonamerni program koji ima osobinu da može da se širi kroz mrežu bez potrebe za asistencijom
korisnika naziva se:
crv
Detekcija anomalija kao metoda za otkrivanje zlonamernih programa se zasniva na:
registrovanju neuobičajenog ponašanja
Salami Attack predstavlja:
serija malih beznačajnih napada koji se mnogo puta ponavljaju
Šifrovanje zlonamernih programa se koristi da bi se onemogućilo njegovo otkrivanje metodom:
detekcije potpisa
Prednosti anti-virusa koji detektuje zlonamerne programe na osnovu potpisa su:
Jednostavno i lako detektuje poznat zlonamerni kod uz minimalno angažovanje korisnika
U praksi, u kodovima se pojavljuje bar jedna greška na svakih:
2000 linija koda
Zlonamerni softver koji nenamenski troši sistemske resurse naziva se:
rabbit
Koji se zlonamerni program ne zahteva nosioca?
Crv
Buffer overflow može da se zloupotrebi (između ostalog):
ubacivanjem zlonamernog koda
Koji programski jezik je osetljiv na prekoračenje bafera?
C/C++
DRM:
u nekim slučajevima koristi neetičke rootkit alate
Da bi se otežao BOBE ("break once, break everywhere") napad koristi se:
metamorfični softver
Maskiranje koda je tehnika koja se koristi da:
bi se kod učinio teško razumljivim
Izbaciti uljeza:
Komodo
Prilikom instaliranja antivirus programa preporuka je da se instalira:
samo jedan pouzdan antivirus program
Debugger je alat koji:
Omogućava praćenje izvršenja programa i analizu resursa koje koristi
Samo-modifikujući kod:
ima sposobnost da menja svoju izvršnu verziju nakon svakog izvršavanja
Najbolja preventivna zaštita od zlonamernog koda je:
zaštita u realnom vremenu (real time protection)
Korisnički softver se često plasira na tržište po sledećem principu:
Razvija se brzo da bi se što pre predstavio kupcima, a propusti i greške se naknadno ispravljaju
Open source code u odnosu na softver zatvorenog koda u pogledu ukupne sigurnosti:
predstavljaju podjednaka rešenja
Koja se od navedenih tehnika je najmanje efikasna za sprečavanje reverznog inženjeringa?
Šifrovanje izvornog koda
Skup metoda za ograničavanje korišćenja digitalnih sadržaja u cilju zaštite autorskih prava skraćeno
se zapisuje:
DRM
Napad zlonamernim programima koji koriste ljudske slabosti naziva se:
društveni inženjering
Ukoliko se poseduje samo exe fajl a postoji namera (potreba) da se analizira i izmeni kod
neophodan alat je:
i disasembler i dibager
Primenom disasemblera od binarnog koda dobija se:
neprecizna asemblerski kod
Ispravke, zakrpe i nove verzije softvera:
Ispravljaju poznate probleme, ali mogu da donesu neke nove propuste
Nedostatak metamorfičnog softvera je:
što se teško prate i ispravljaju eventualne greške
Reverzni inženjering je proces u kome se:
Rekonstruišu asemblerske instrukcije na osnovu binarne datoteke
Windows Defender je:
antivirus program
Kod loših softverskih rešenja i softvera sa propustima, ako postoji jaka kriptografska zaštita u
pozadini
Jaka kriptografija ne može da obezbedi sigurnost podataka korisnika kod lošeg sofvera
Koja se od navedenih tehnika je najmanje efikasna za sprečavanje reverznog inženjeringa?
Šifrovanje izvornog koda
Hardware-based debugging (HardICE):
je dibager čije se aktivnosti teško detektuju
Reverzni inženjering je tehnika koja se koristi za:
analizu exe fajlova





Tajnost komunikacije je:
zagarantovano pravo
Prisluškivanje je napad na:
poverljivost
Skup aktivnosti koje treba da obezbede da neovlašćena strana u komunikaciji ne dođe do poverljivih
informacija naziva se:
poverljivost
Poverljivost je skup aktivnosti:
koje treba da obezbede da neovlašćena strana u komunikaciji ne dođe do poverljivih informacija
Servis koji obezbeđuje proveru identiteta naziva se:
autentifikacija
Kada se poruka skrivena metodom imagedowngradin vraća nazad, tako dobijena slika je:
aproksimirana je u odnosu na skrivenu
Statistička detekcija je motoda koja se koristi:
za postojanje skrivenih poruka u stegoanalizi
Steganografija je:
proces ugrađivanja poruke koja treba da je tajna u poruku koja nije tajna
Tehnika kojom se u digitalni sadržaj utiskuju dodatne informacije kao što su podaci o autoru,
vlasništvu, licencama i slično naziva se:
vodeni pečat
Neka je nosilac slika veličine 10 MB u 24-bitnom zapisu, a za skrivanje poruke se koristi po 2 bit
kanala za zelenu, 1 bita kanala za plavu i 3 bita kanala za crvenu boju. Maksimalna veličina poruke u
MB a koja može da se sakrije u slici je:
2.5
Spojiti pojam i odgovarajući opis pojma:
steganografske funkcije – funkcije ugrađivanja tajen poruke i izdvajanja tajne poruke
steganografski kanal – kanal preko koga se šalje steganografski medijum
nosilac poruke – bila koja poruka preko koje se prenosi skrivena poruka
stego ključ – tajna vrednost pomoću koje se jedna poruka ugrađuje u drugu
tajna poruka – poruka koja se ugrađuje
steganografski medijum – poruka koja u sebi sadrži ugrađenu drugu poruku
Raspoloživost predstavlja sposobnost sistema:
da ovlašćenom korisniku pruži uslugu kad god je potrebno
Dodela prava autentifikovanom korisniku naziva se:
autorizacija
Kada se informacija krije unutar video fajla uglavnom se koristi:
DCT metoda
Šta se kod steganografije krije?
činjenica da se prenosi poruka
Neka je poruka slika veličine 4 MB u 24-bitnom zapisu, a za skrivanje poruke se koristi po 3 bita
kanala za crvenu, 2 bita kanala za plavu i 4 bita kanala za zelenu boju nosioca. Minimalno potrebna
veličina nosioca u MB je:
10.6
Neka je poruka slika veličine 1 MB u 24-bitnom zapisu, a za skrivanje poruke se koristi po 4 bita
kanala za crvenu, 2 bita kanala za plavu i 2 bita kanala za zelenu boju nosioca. Minimalno potrebna
veličina nosioca u MB je:
3
Spojiti tehnike stegoanalize potrebne poznate informacije:
odabrana steganografija – poznati su steganografski medijum i algoritam
odabrana poruka – poznata je poruka i steganografski algoritam
poznata poruka – poznata tajna poruka
poznata steganografija – poznati su nosilac, steganografski medijum i steganografski algoritam
poznati nosilac – poznati su nosilac i steganografski medijum
samo steganografija – poznat steganografski medijum
Spariti pojam i opis pojma:
integritet podataka – je skup aktivnosti koje treba da spreče ili detektuju neovlašćenu izmenu...
poverljivost podataka – je skup aktivnosti koje treba da obezbede da neovlašćena strana...
raspoloživost – predstavlja sposobnost sistema da ovlašćenom korisniku pruži uslugu...
Raspoloživost sistema predstavlja sposobnost sistema:
da ovlašćenom korisniku pruži uslugu kad god je potrebno
Kod LSB supstitucije koliko bitova maksimalno može da se promeni a da to ostane neprimećeno:
do 50%
Tajnost komunikacije se odnosi na:
sprečavanje neovlašćenih lica da dođu do sadržaja poruke ili podataka koji se prenose javnim
komunikacionim putevima
Kada se poruka skrivena LSB metodom vraća nazad, tako dobijena slika je:
aproksimirana je u odnosu na sakrivenu
Koji je od sledećih formata najpogodniji za LSB supstituciju:
bmp
U klasifikaciji steganografskih tehnika kompjuterska steganografija spada u:
bezšifarne tehnike
1 – tajna poruka 2 – nosilac poruke 3 – stego ključ 4 – steganografski medijum 5 – steganografski
sistem
Koje su od navedenih šifri poligramske:
Hilova
Plejferova
Spojiti odgovarajuću šifru i njenu karakteristiku:
Plejferova, Vernamova, Hilova, Vižnerova – polialfabetska
Cezarova, Prosta supstitucija, Afina – monoalfabetska
Supstitucija kod koje se tokom šifrovanja jedan znak ne zamenjuje uvek istim znakom već nekim iz
dozvoljenog skupa znakova naziva se:
polialfabetska
Za šifrovanje Afinom šifrom koriste se samo velika slova engleske abecede numerisana od 0 do 25.
Ako je ključ uređeni par (3, 17), kako glasi formula za dešifrovanje?
d(y)=9(y-17)
Otvoreni tekst VISER šifrovan je tri puta i dobijena su tri različita šifrata: QQKII, QDNZM, XGLBXO.
Odrediti koji je šifrat dobijen Cezarovom, Vižnerovom i Plejferovom šifrom:
QDNZM – Cezarova
QQKII – Vižnerova
XGLBXO – Plejferova
Supstitucija kod koje je osnovni element vršenja supstitucije grupa znakova naziva se:
poligramska
Šifrom transpozicije kolona šifrovan je tekst: DOG IS MAN’S BEST FRIEND. Dimenzija izabrane matrice
je 5x4 a ključna reč je HUSKY. Šifrat je:
DMEIISFDGNTNOASESBRX
Bezuslovno sigurna šifra:
je OTP šifra
Otvoreni tekst je šifrovan Afinom šifrom. Ključ je uređeni par (7, 15). a za šifrovanje se koriste
isključivo velika slova engleske abecede numerisana redom, od 0 do 25. Ako je dobijeni šifrat OPHJAR
kako glasi otvoreni tekst?
lakoje
OTP je bezuslovno sigurna šifra:
dokazano
Reč GORA je šifrovana različitim šiframa. Koji od ponuđenih šifrata je dobijen korišćenjem šifre
transpozicije:
AGRO
Algoritmi koji elemente otvorenog teksta obrađuju jedan po jedan nazivaju se:
protočni
Spojiti opis i naziv supstitucije:
osnovni element kod vršenja supstitucije je grupa znakova – poligramska
većina znakova se zamenjuje uvek istim znakom sem onih najfrekventnijih koja se menjaju na bar dva
načina – homofona
svaki znak poruke zamenjuje se uvek istim znakom u šifratu – monoalfabetska
jedan znak tokom šifrovanja ne zamenjuje se uvek istim znakom iz skupa dozvoljenih – polialfabetska
Supstitucija kod koje se jedan znak zamenjuje uvek istim znakom naziva se:
monoalfabetska
Neka se reč CAKE šifruje Plejferovom šifrom sa ključem TEST. Alfabet koji se koristi su velika slova
engleske abecede gde se poistovećuju slova I i J. Šifrat dobijen na taj način je:
GTPD
Ako je X=01011001 i Y=11001100 tada je (((X xor X)xor Y)xor Y)xor X jednako:
X
Sigurnost kriptosistema počiva na:
tajnosti ključa za dešifrovanje
OTP šifra može da se koristi:
samo jednom
Otvoreni tekst PERA šifruje se Vižnerovom šifrom sa ključem PERA. Alfabet koji se koristi je srpska
azbuka i slova su numerisana redom brojevima od 1 do 30. Šifrat koji se dobija na taj način je:
OLJIB
Neka je Z skup znakova nad kojima se definiše ključ. Ukoliko je ključ dužine 5 i Z={0,1,2,3,4,...,9, a,b,c,
... x,y,z,A,B,C,...X.Y.Z}, tada je veličina prostora ključeva ukoliko slova u ključu ne mogu da se
ponavljaju:
62*61*60*59*58
Supstitucija kod koje se tokom šifrovanja jedan znak ne zamenjuje uvek istim znakom već nekim iz
dozvoljenog skupa znakova naziva se:
polialfabetska
Simetrični kriptosistemi su oni:
kod kojih se koristi isti ključ za šifrovanje i dešifrovanje
Ključ kod Hilove šifre je matrica koja:
mora biti invertibilna
Kod klasičnih kriptosistema odrediti šta je javno a šta tajno:
šifrat – javno, komunikacija – javno, ključ – tajno, otvoreni tekst – tajno
Za šifarski sistem ako je vreme potrebno za „razbijanje“ šifrata duže od vremena u kom informacija
treba da bude tajna naziva se:
računski siguran
Neka se zna da je za šifrovanje korišćena šifra transpozicije kolona i da je ključ 5x4. Ako je šifrat
dobijen na taj način KOSSRGKTIRIEPASMTFII onda je otvoreni tekst:
kriptografskisistemi
1 – otvoreni tekst, 2 – šifrovanje, 3 – ključ za šifrovanje, 4 – šifrat, 5 – dešifrovanje, 6 – ključ za
dešifrovanje, 7 – kriptosistem
Supstitucija kod koje se većina znakova menja istim sem onih najfrekventnijih koji mogu da se
menjaju na više načina naziva se:
homofona
Neka je Z skup znakova nad kojima se definiše ključ. Ukoliko je ključ dužine 5 i Z={0,1,2,3,4,...,9, a,b,c,
... x,y,z,A,B,C,...X.Y.Z,*,#,$}, tada je veličina prostora ključeva ukoliko slova u ključu mogu da se
ponavljaju:
64^5
Za otvoreni tekst i za šifrovanje koriste se slova srpske azbuke. Slova od A do Š su redom numerisana
brojevima od 1 do 30 dok su brojevi od 31 do 36 dodeljeni redom slovima A, E, N, O, R, T. Šifruje se
reč RENTA. Koji od sledećih šifrata nije dobijen korišćenjem navedene šifre.
35 7 32 22 31
Otvoreni tekst CEZAR šifrovan je sa pet različitih ključeva. Ukoliko je se u otvorenom tekstu i prilikom
šifrovanja koriste samo velika slova srpske azbuke, spojiti ključ za širratom.
14 – JSĆMG 3 – ŠIKGĆ 29 – HĐŽŠP 20 – NJCDŽSI 10 – ENJPJŠ
Šifarski sistem ako ne može da bude „razbijen“ ni uz primenu neograničenih resursa, ljudstva i
vremena je:
bezuslovno siguran
Dužina ključa kod AES algoritma može biti:
128, 192 ili 256 bita
Kod blokovskih algoritam, blok šifrata se dobija višestrukom primenom određene funkcije na blok
otvorenog teksta i međurezultate. Jedna primena funkcija naziva se:
runda
Kriptosistemi koji koriste isti ključ za šifrovanje i dešifrovanje nazivaju se:
simetrični kripto sistemi
Kod sekvencijalnih algoritama (koji teže da prevaziđu nedostatke OTP šifre) šifrat se dobija tako što
se vrednost otvorenog teksta sabira po modulu 2 (XOR) sa:
pseudo slučajnim binarnim nizom koji se dobija sa kratkog slučajnog ključa
DES algoritam je:
blokovski algoritam Fejstelovog tipa
Da bi se uspešno dešifrovao šifrat šifrovan sekvencijalnim šifarskim sistemom neophodno je da se
poseduje:
slučajni ključ i generator pseudo slučajnih brojeva
Koji od navedenih algoritama je sekvencijalni?
A5/1
Kod trostrukog DES-a postupak šifrovanja je:
prvo se vrši šifrovanje prvim, zatim dešifrovanje drugim, a zatim šifrovanje prvim ključem
Koji je iskaz tačan:
integritet predstavlja skup postupaka koji treba da spreče (ili otkriju) neovlašćenu izmenu podataka
bez obzira da li su podaci javni ili šifrovani
AES algoritam je:
iterativni blokovski algoritam
Kod DES algoritma:
veličina bloka je 64 bita, dužina ključa je 56 bita, dužina podključa je 48 bita
Postupak kojim se otvoreni tekst zapisuje u obliku binarnog niza naziva se:
kodovanje
MAC (Message Autentication Code) je:
kratka šifrovana poruka
Algoritmi koji pre šifrovanja otvoreni tekst dele na skupine uzastopni bitova određene dužine
nazivaju se:
blokovski
Nedostatak ECB režima rada je to što:
istim blokovima odgovaraju isti šifrati
Sigurnost DES algoritma počiva na:
S-boksovima
Povezati pojam i opis:
kripto sistemi sa simetričnim ključem – koristi isti ključ za šifrovanje i dešifrovanje
kripto sistemi sa javnim i tajnim ključem – koristi javni ključ za šifrovanje, a tajni za dešifrovanje
Sekvencijalni algoritmi:
se koriste tamo gde je bitna brzina i rad u realnom vremenu
Blokovski algoritmi se najčešće realizuju:
softverski
Algoritmi koji u jednom trenutku šifruju jedan bit (bajt) nazivaju se:
sekvencijalni algoritmi
Nedostatak OTP šifre je to:
što je proces generisanja velike količine binarnih nizova koji imaju osobine slučajnosti po pravilu spor
a upotrebljava se samo jednom
Zadatak savremenih algoritama šifrovanja je da:
transformiše nizove bitova koji nose informaciju iz otvorenog teksta u novi binarni niz na takav način
da neovlašćene strane analizom šifrata ne mogu da dođu do informacija koje postoje u otvorenom
tekstu
Spojiti svojstvo blokovskog algoritma i opis tog svojstva:
svaki bit šifrata treba da bude funkcija svakog bita ključa – svojstvo kompletnosti
kod napada potpunom pretragom ključeva svi ključevi treba da budu podjednako verovatni –
svojstvo konfuzije
poznavanje nekog para blokova otvorenog teksta Pi i njemu pripadajućeg šifrata Ci ne sme da
omogući da se iz nekog drugog bloka šifrata Cj odredi blok otvorenog teksta Cj – svojstvo difuzije
Pseudo slučajan niz brojeva se koristi:
kao ključ za sekvencijalne šifarske sisteme
CBC (Cipher Block Chaining):
šifruje blok otvorenog teksta tako što obavi operaciju XOR tog bloka i šifrata prethodnog bloka
Sekvencijalni algoritmi:
mogu da se realizuju hardverski i softverski
Kod OTP šifre:
dužina ključa mora biti jednaka dužini poruke i upotrebljava se samo jednom
ECB (Electronic Codebook Mode):
šifruju blok po blok sa istim ključem K
Kod blokovskog algoritma, po pravilu:
blok šifrata je iste dužine kao blok otvorenog teksta
Generator pseudoslučajnih vrednosti, na osnovu kratkog (slučajnog) ključa generiše:
radni ključ
Jedna od nepoželjnih osobina generatora pseudo slučajnih brojeva je:
periodičnost
Koje se operacije koriste kod OTP šifre?
samo XOR
Svojstvo šifarskih algoritama (funkcija) da male promene ulaza izazivaju velike promene izlaza:
difuzija
U koliko rundi se izvršava DES algoritam?
16
Kod CBC režima rada blokovskih algoritama, eventualna namerna ili slučajna promena bloka se
automatski ispravlja nakon:
2 bloka
Za digitalno potpisivanje koriste se:
asimetrični kriptografski sistemi
Kriptografski sistem koji koristi sistem sa javnim ključem za razmenu simetričnog ključa a potom
prelazi na simetričnu kriptografiju naziva se:
hibridni
Alisa je poslala poruku Bobu šifrovanu RSA algoritmom. Bob poruku dešifruje:
svojim privatnim ključem
Neka je dat javni ključ (N,e)=(55,7) i privatni ključ 23 generisani RSA algoritmom. Šifruje se poruka
M=12. Rezultat je:
23
Funkcije koje relativno lako mogu da se izračunaju ali njihova inverzna vrednost može da se odredi
samo izuzetno složenim postupkom nazivaju se:
jednosmerne
Alisa želi da pošalje Bobu poruku šifrovanu RSA algoritmom. Ona poruku šifruje:
Bobovim javnim ključem
Servis koji prijemnoj strani pruža dokaz da je poruku primio od tačno određene osobe naziva se:
neporecivost
Neka je dat javni ključ (N,e)=(33,7) i privatni ključ 3 generisani RSA algoritmom. Šifrat je S=27. Poruka
je:
15
Dati su parametri p=17 i q=5. Alisa i Bob razmenjuju ključeve uz pomoć Difi Helmanovog algoritma.
Alisa je zamislila broj 3 a Bob 7. Alisa šalje Bobu:
5^3 (mod 17) = 6
Za šifrovanje i digitalno potpisivanje:
koristi se različiti par ključeva
U Difi Helmanovom protokolu, broj p koji se koristi za stepenovanje po modulu p tokom
izračunavanja:
treba da bude velik prost broj
Dati su parametri p=17 i q=11. Alisa i Bob razmenjuju ključeve uz pomoć Difi Helmanovog algoritma.
Alisa je zamislila broj 7 a Bob 9. Bob šalje Alisi:
11^9 (mod 17) = 6
Sertifikaciono telo (CA) potvrđuje validnost:
javnih ključeva
Sertifikaciono telo (CA) potvrđuje validnost javnih ključeva sertifikatom koji:
SA potpisuje svojim tajnim ključem
Difi Helmanov algoritam se koristi za:
razmenu simetričnih ključeva
Asimetrični kriptografski algoritmi se često koriste:
za razmenu simetričnog ključa kojim se zatim šifruje poruka
Izabrati tačno tvrđenje:
asimetrični algoritmi su sporiji od simetričnih
Alisa i Bob razmenjuju zajedničku tajnu koristeći Difi Helmanov algoritam. Dogovorili su se da uređeni
par (p,g) bude (13,7). Alisa je zamislila broj 4 a Bob broj 5.
Bob šalje Alisi 11, Alisa šalje Bobu 9, zajednička tajna je 3
Validnost javnih ključeva:
potvrđuje treća strana od poverenja
Jednosmerne funkcije:
nije dokazano ni da postoje ni da ne postoje
Neka je javni ključ (N,e) privatni d. Postupak digitalnog potpisivanja poruke M je definisan sa:
S=M^d (mod N)
Neka je dat javni ključ (N,e)=(77,13). Za generisanje tajnog ključa koristi se RSA algoritam. Koji od
sledećih brojeva može biti tajni ključ. Napomena: N=7*11
37
Odrediti redosled koraka kod izbora tajnog i javnog ključa RSA algoritmom:
1 – biraju se dva velika prosta broja p i q
2 – formiraju se proizvodi N=p*q i f(N)=r=(p-1)*(q-1)
3 – bira se broj e manji od r i uzajamno prost sa r
4 – nalazi se d takvo da je e*d=1 (mod r)
5 – proglašavaju se javni i tajni ključ
Koji model PKI (Public Key Infrastructure) se koristi kod savremenih Internet pretraživača
oligarhijski model
Digitalni potpis je servis koji treba da obezbedi:
integritet i neporecivost
Da li heš funkcija treba da poseduje svojstvo lavinskog efekta?
da
Fiksne vrednosti ipad (0x360x36..0x36) i opad (0x560x56...0x56), svaka dužine po 64 bita se koriste za
izračunavanje:
HMAC vrednosti
Koji algoritam ne pripada navedenj grupi:
AES
U računarima
čuvaju se heš vrednosti lozinki
Šifrovanjem heš vrednosti simeričnim/asimetričnim algoritmom može istovremeno da se vrši:
provera integriteta i autentifikacija
Prilikom digitalnog potpisivanja (šifrovanja privatnim ključem)
šifruju se heš poruke
Heš funkcija je
jednosmerna funkcija koja za ulaz proizvoljne konačne veličine daje izlaz fiksne dužine
Jednosmerna heš funkcija generiše otisak dužine 160 bita. Koliko različitih poruka generiše heš oblika
0000....0001?
beskonačno mnogo
Kako se zove jednosmerna funkcija koja za ulazni podatak proizvoljne konačne dužine izlaznu
vrednost daje niz fiksne dužine?
heš
Alisa šalje Bobu otvorenu poruku M i heš te poruke h(M)=h1. Bob po prijemu poruke takođe računa
heš h(M)=h2. Upoređivanjem h1 i h2 Bob proverava:
da li je poruka M promenjena tokom prenosa
MAC se koristi u procesu:
autentifikacije
Pokušaj ponovnog slanja iste poruke može da se otkrije:
ugradnjom podatka o vremenu slanja poruke u samu poruku
Autentifikacija koja se realizuje šifrovanjem heš vrednosti simetričnim algoritmom:
postojanje internog poverenja
Neka je dužina heš funkcije 128 bita. Koliko različitih poruka treba genenrisati da bi sigurno došlo do
kolozije:
2^128+1
Pojava kod heš funkcija da dve različite poruke daju isti heš naziva se:
kolizija
Kolizija kod heš funkcija označava pojavu da:
dve različite poruke daju istu heš vrednost
Ugradnjom podataka o vremenu slanja poruke u samu poruku:
može da se otkrije ponovno slanje iste poruke
Kolika treba da je dužina heš funkcije da bi se postigla ista sigurnost kao kod simetričnog sistema
kome je ključ dužine n:
2*n
Neka je dužina heš funkcije 128 bita. Koliko različitih heš vrednosti funkcija može da generiše:
2^128
Za heš funkcije je važno da:
budu efikasne
Koliko parametara ima funkcija HMAC:
2 – (M,K)
Prednost šifrovanja heš vrednosti (prilikom autentifikacije i provere identiteta) asimetričnim
algoritom u odnosu na šifrovanje simetričnim algoritmom je to što:
nema potrebe za internim poverenjem
Dužina otiska (heš vrednost) SHA-2 algoritma je:
u zavisnosti od varijante, mogu biti sve navedene vrednosti (256, 384, 512)
MAC (Message Authentification Code) se dobija tako što se:
poruka šifruje blokovskim algoritmom a zatim se pamti samo poslednji blok šifrata
Dužina otiska (heš vrednosti) MD5 algoritma je:
128 bita
Dužina ključa koji je potreban za izračunavanje HMAC vrednosti je:
manji do 64 bita
Heš funkcije se ne koriste za šifrovanje poruka jer je:
nemoguće izvršiti dešifrovanje
Slučajna izmena sadržaja poruke tokom prenosa:
spada u narušavanje integriteta poruke
Osnovna primena heš funkcija je:
u postupku autentifikacije
Algoritmi koji prilikom šifrovanja obrađuju blokove otvorenog teksta nazivaju se:
blokovski
Ukoliko se koristi engleski alfabet za ključ dužine 4, koliki je prostor ključeva?
26x25x24x23
Neka je poruka slika veličine 2 MB u 24-bitnom zapisu, a za skrivanje poruke se koristi po 3 bita
kanala za crvenu, 2 bita kanala za plavu i 4 bita kanala za zelenu boju nosioca. Minimalno potrebna
veličina nosioca u MB je:
15.3
Svojstvo šifarskih algoritama takvo, da je svaki bit šifrata u funkciji svakog bita ključa naziva se:
svojstvo kompletnosti
U RSA algoritmu sa parametrima (n,e)=(187,23) digitalni potpis poruke m=3 iznosi:
130
Otvoreni tekst x šifruje se Afinom šifrom y = Ek (x) = 17x + 6 mod 26. Šifrat se dešifruje sledećim
izrazom:
x = 23 (y - 6) mod 26
Neporecivost je servis koji prijemnoj strani pruža neoboriv dokaz da:
je poruku primio od tačno određene osobe
Aktivan napad kojim se neovlašćeno menjaju podaci, pristupna prava ili način funkcionisanja sistema
je napad na:
integritet
Sposobnost sistema da ovlašćenom korisniku pruži uslugu kad god je potrebna naziva se:
raspoloživost
Ako je heš dužine 224 bitova koliko je potrebno napraviti poruka da bismo sigurno došli do kolizije:
2^224+1
Šifrovanjem teksta MARKO Viženerovom šifrom sa ključem PERA u engleskom alfabetu gde je A=0
dobija se sledeći šifrat:
BEIKD
Šifarski sistem, kod koga je cena razbijanja šifrata prevazilazi vrednost šifrovane informacije naziva
se:
računski siguran
Šifrarski sistem je siguran ako:
je najefikasniji poznati napad potpuna pretraga prostora ključeva koji treba da je dovoljno veliki
Šifarski sistem kod koga je vreme potrebno za razbijanje šifrata duže od vremena u kom informacija
treba da bude tajna, naziva se:
računski siguran
Linearni pomerački registri:
koriste se kao gradivni elementi složenijih generatora
Šifrom dvostruke transpozicije šifrovana je reč PLEASURE. Odabrana dimenzija matrice je 3x3, pravilo
za permutaciju kolona je (3,1,2), a pravilo za permutaciju vrsta je (2,3,1).
Dobijeni šifrat je:
OASXREEPL
Svojstvo šifarskih algoritama takvo, da je svaki bit šifrata u funkciji svakog bita ključa, naziva se:
kompletnost
ByteSub, ShiftRow, MaxColumn, AddRoundKey su operacije koje se vezuju za:
AES algoritam
Svojstvo šifarskih algoritama (funkcija) da male promene ulaza izazivaju velike promene izlaza naziva
se:
lavinski efekat
Fejstelova šifra (mreža) predstavlja
jedno idejno rešenje blokovske šifre
Alisa i Bob razmenjuju zajedničku tajnu koristeći Difi Helmanov algoritam. Alisa šalje Bobu vrednost
g^a(mod p), a Bob Alisi g^b(mod p). U toj komunikaciji šta je javno, a šta tajno.
javno (p, g, g^a, g^b) tajno (a, b)
Neka je dat javni ključ (N,e)=(50,3) i privatni ključ 17 generisani RSA algoritmom. Digitalno se
potpisuje poruka M=9. Rezultat je (upisati broj):
29
Da bi se smanjila dužina digitalnog potpisa poruke, računa se:
heš poruke koji se digitalno potpisuje
Ako pošiljalac šifruje poruku sa javnim ključem primaoca i takav šifrat pošalje primaocu, šta je
nedostatak takve komunikacije:
poverljivost
Koja dva algoritma su po načinu funkcionisanja slična:
Jednostavni XOR i One Time Pad
Otvoreni tekst x šifruje se Afinom šifrom y = Ek (x) = 6x + 3 mod 26. Šifrat se dešifruje sledećim
izrazom:
x = 6 (y - 3) mod 26
Neka je nosilac slika veličine 8 MB u 24-bitnom zapisu, a za skrivanje poruke se koristi po 3 bit kanala
za zelenu, 2 bita kanala za plavu i 2 bita kanala za crvenu boju. Maksimalna veličina poruke u MB a
koja može da se sakrije u slici je:
2.3
Šta je rezultat operacije ((a XOR b) XOR a) XOR (a XOR b)?
a
Ako je heš dužine 384 bitova koliko je potrebno napraviti poruka da bismo sigurno došli do kolizije:
2^384+1
U Diffie-Hellmanovom protokolu sa parametrima (g,p)=(2,5) Alisa je zamislila broj 2, a Boban je
zamislio broj 11. Zajednička tajna je:
4
Aktivan napad koji se realizuje tako što se generišu lažni podaci ili lažni saobraćaj je napad na:
autentičnost
Dat je prost broj p=18 i generator g=2. Koristeći Diffie-Hellmanov protokol odredite tajni ključ ako su
zamišljene vrednosti a=5 i b=8
k=16
Odrediti red veličine broja operacija šifrovanja i dešifrovanja za napad na trostruki DES metodom
susret u sredini:
2^112
Ključ je dužine 64 bita. Koliki je prostor ključeva?
2^64
(A)Simetrični algoritmi:
imaju problem razmene ključeva
Za DES i AES algoritme važi:
DES je Feistel-ova, a AES nije
U Diffie-Hellmanovom protokolu sa parametrima (g,p)=(2,5) Alisa je zamislila broj 2, a Boban je
zamislio broj 7. Zajednička tajna je:
4
Frekvencijska analiza nema efekat na:
OTP
Steganografskim ugrađivanjem informacija o autorskim pravima u sliku ili zvuk medijuma se dodaje:
vodeni žig
Koji od sledećih algoritama je sekvencijalni:
RC4
Koji od sledećih šifarskih algoritama nije monogramski:
Playfairove šifra
Provera validnosti sertifikata postiže se:
korišćenjem javnog ključa izdavača sertifikata
Alisa želi da proveri potpis poruke koju joj je Bob poslao. Alisa potpis proverava:
Bobovim javnim ključem
Alisa želi da pošalje Bobu poruku m digitalno potpisanu RSA algoritmom. Alisa potpisuje MD5 sažetak
poruke:
svojim privatnim ključem
MAC služi za:
proveru integriteta poruke
Pronađite uljeza:
GEORGE-256
Koji pojam nije vezan za heš algoritme:
razmena ključeva
Ako pošiljalac kroz nesiguran kanal šalje par (poruka, heš), kako napadač koji može da stvori koliziju i
može da preseče komunikaciju može da prevari primaoca:
promeniće i poruku i heš
Šta se smešta na disk prilikom kreiranja korisničkog naloga:
par korisničko ime – heš lozinke
Kontrola pristupa obuhvata:
autentifikaciju i autorizaciju
Napad na poverljivost podrazumeva:
razotkrivanje informacije
Izbaciti uljeza:
šifra zamene
Operacije MixColumn i ShiftRow su deo:
AES algoritma
Sigurnost Diffie-Hellamnovog protokola za razmenu ključeva leži u:
složenosti računara algoritma u konačnim poljima
Za ECB i CBC režime rada važi:
u ECB režimu isti blok istim ključem uvek daje isti šifrat, dok u CBC to ne mora da bude slučaj
Koliko u proseku treba pokušaja grubom silom da bi se razbila šidra pomeraja u azbuci od 30 slova:
15
Sertifikat služi:
za autentifikaciju
Koji od sledećih algoritama može se koristiti za digitalno potpisivanje:
RSA
Tehnikom image downgrading-a
moguće je BMP sakriti u BMP
Dužina ključa kod AES ne može da bude:
64 bita
Playfairova šifra je:
polialfabetska/poligramska
Efektivna dužina ključa kod DES algortma je:
56 bitova
Najmanje dovoljan broj operacija šifrovanja i dešifrovanja za napad na dvostruki DES algoritam je:
2^57
Šifrat otvorenog teksta JOHN dobijen Cezarovom...
MRKQ
PGP koristi:
simetrične algoritme, asimetrične algoritme i kompresiju






Sigurnost informacionih sistema
Zašita podataka
PRIPREMA ZA PRVI KOLOKVIJUM
Priprema za prvi kolokvijum iz predmeta sigurnost informacionih sistema i zaštita podataka
obuhvata uglavnom pitanja sa vežbi i odabrana pitanja sa predavanja. U okviru pripreme izložena
su rešenja nekih problema iz kriptografije i objašnjenja nekih osnovnih pojmova.
Ovaj dokument NIJE ZAMENA za materijale sa predavanja i vežbi. Drugim rečima, preporučuje
sa da se prilikom pripreme kolokvijuma oslonite na gradivo koje pokriva predavanja i vežbe, a ovaj
dokument iskoristite za proveru znanja.
Sigurnost informacionih sistema / Zaštita podataka
1.
Šta se krije a šta ne krije steganografijom?
Steganografijom se NE krije činjenica da dva entiteta komuniciraju, ali se prikriva tajna
poruka.
2.
Korisnik krije poruku u najmanje značajne bitove kanala svake boje 24-bitne BMP
slike. Ukoliko se zanemare meta-podaci koji potiču iz formata slike, kolika je najmanja
dovoljna veličina slike (u MB) ukoliko korisnik hoće da sakrije 10MB informacija?
Svaki piksel je definisan sa 24 bita. Ukoliko 3 bita iskoristite za skrivanje poruke tehnikom
LSB supstitucije, iskoristićete 3/24 = 1/8 veličine slike. Dakle, slika mora biti barem 8 puta
veća od veličine poruke koju želite da sakrijete. U ovom slučaju je to 80MB.
3.
Korisnik krije poruku u 24-bitnu BMP sliku tako što zamenjuje dva najmanje značajna
bita kanala za crvenu i plavu boju svakog piksela. Ukoliko se zanemare meta-podaci
koji potiču iz samog formata slike, kolika je najmanja dovoljna veličina slike (u MB)
ukoliko korisnik hoće da sakrije 10MB informacija?
Objašnjenje je slično prethodnom pitanju. Svaki piksel je definisan sa 24 bita. Ukoliko
2+2=4 bita iskoristite za skrivanje poruke tehnikom LSB supstitucije, iskoristićete 4/24 = 1/6
veličine slike. Dakle, slika mora biti barem 6 puta veća od veličine poruke koju želite da
sakrijete. U ovom slučaju je to 60MB.
4.
Korisnik želi da sakrije poruku u 24-bitnu sliku i pri tome sme da upiše informacije u
dva najmanje značajna bita R, G i B kanala svakog piksela. Koliko MB informacija
može upisati u sliku veličine 10MB? Zanemarite meta-podatke koji potiču iz formata
slike.
U ovom slučaju imamo ukupno 2+2+2=6 bita koji se mogu iskoristiti za skrivanje poruke
tehnikom LSB supstitucije. To znači da je moguće iskoristiti 6/24 = 1/4 veličine slike za
skrivanje poruke. Dakle, ukoliko je slika veličine 10MB, može se iskoristiti 10 * 1/4 = 2.5MB
za skrivanje. Dakle, u slici se može sakriti najviše 2.5MB informacija.
5.
Šta smete da uradite sa 24-bitnom BMP slikom ukoliko želite da sačuvate poruku koja
je steganografski utisnuta u nju tehnikom LSB supstitucije?
a. Da je pretvorite u 8-bitnu BMP sliku
b. Da je pretvorite u JPEG
c. Da je retuširate
d. ništa od navedenog
Ukoliko degradirate kvalitet slike konverzijom u 8-bitnu BMP sliku, izgubićete najmanje
značajne bite, što će reći i poruku. Konverzijom u JPEG unosite kompresiju sa gubicima, tako
da nakon ponovne konverzije u BMP dobijate aproksimaciju slike, što znači da gubite poruku.
Retuširanjem ćete izmeniti bitove koji sadrže tajnu poruku.
2
Priprema za prvi kolokvijum
6.
Da li se tehnikom image downgrading-a dobijaju neizmenjene slike poruke i nosioca ili
njihove aproksimacije?
Dobijaju se aproksimacije poruke i nosioca. Pošiljaoc menja 4 najmanje značajna bita u
prikazu boje svake tačke nosioca sa 4 najviše značajna bita prikaza boje piksela tajne slike,
koji se nalaze na istom mestu. Primalac izvlači 4 najmanje značajna bita svakog elementa
stego-datoteke i tako dobija najviše značajne bitove tajne datoteke. Dobijena 4 najznačajnija
bita svake vrednosti boje svake tačke se dopunjuju sa još 4 bita (na primer, nulama), i time se
dobija aproksimacija tajne slike. Na sličan način se dobija aproksimacija nosioca.
Treba naznačiti i sledeće:
• nakon ekstrakcije dobijaju se poruka iste veličine i nosioc iste veličine;
• nosioc i poruka moraju biti iste rezolucije i ne smeju biti u formatu koji koristi
kompresiju sa gubicima.
7.
Šta se dodaje steganografskim ugrađivanjem informacija o autorskim pravima u sliku,
video ili zvučni zapis?
Vodeni žig
8.
Šta su raspoloživost, integritet i poverljivost?
• Raspoloživost je sposobnost sistema da ovlašćenom korisniku pruži uslugu kada god je
to potrebno.
• Integritet je skup aktivnosti koji sprečavaju neovlašćenu izmenu podataka. Drugim
rečima, informacije smeju da izmene samo entiteti koji su za to ovlašćeni.
• Poverljivost je skup aktivnosti koji sprečava neovlašćenom entitetu uvid u tajnu
informaciju.
9.
Koji zaštitni mehanizam se napada DoS napadima?
Raspoloživost.
10.
Objasnite Kirhofov princip.
Algoritam za šifrovanje NIJE tajni. Ključ za šifrovanje jeste.
11.
U čemu je razlika između autentifikacije i autorizacije?
• Autentifikacijom se određuje ko ima pristup sistemu.
• Autorizacijom se određuje šta autentifikovani korisnik sme na sistemu da uradi sa
resursima, odnosno kojim resursima sme da pristupi i koje operacije nad njima da obavi.
3
Sigurnost informacionih sistema / Zaštita podataka
12.
Šta je rezultat operacije ( (a XOR b) XOR a ) XOR (a XOR b) ?
Za XOR operaciju važi: (A XOR B) XOR A = B.
Zamenite u izrazu ((A XOR B) XOR A) sa B.
Računate B XOR (A XOR B) = A.
13. Koji je šifrat otvorenog teksta JOHN dobijen cezarovom šifrom (u pitanju je engleski
alfabet sa ključem k=3)?
MRKQ
14.
Otvoreni tekst x šifruje se Afinom šifrom pomoću ključa (a, b) = (7, 3) i pri tom se
dobija šifrat y = (7x + 3) mod 26. Kojim se izrazom dešifruje šifrat (inverzni element od
7 po modulu 26 je 15)?
Jednačine šifrovanja i dešifrovanja su:
• E (x, k) = a ∙ x + b (mod n), D (y, k) = a-1 ∙ (y – b) (mod n).
Dakle, u ovom slučaju je a=7, a njegov inverzni element je a-1=15.
Jednačina dešifrovanja je: x = 15(y–3) mod 26
15.
Otvoreni tekst x šifruje se Afinom šifrom y = (17x + 6) mod 26. Kojim se izrazom
dešifruje šifrat (inverzni element od 17 po modulu 26 je 23)?
Slično prethodnom primeru: x = 23 (y – 6)
16.
Koje uslove treba da zadovolje parametri koji čine ključ afine šifre? Da li se k = (8, 11)
može upotrebiti kao ključ ako alfabet ima 26 slova?
Element a iz ključ mora da ima multiplikativni inverzni element. U ovom slučaju 8 nema
multiplikativni inverzni element i ključ ne može da se koristi.
17.
Otvoreni tekst x šifruje se Afinom šifrom y = (6x + 3) mod 26. Kojim se izrazom
dešifruje šifrat?
Ni jednim zato što a=6 nema multiplikativni inverzni element po modulu 26.
18.
Kako se može odrediti ključ (a, b) afine šifre ukoliko je poznat samo šifrat dovoljne
dužine i jezik na kome je poruka napisana?
Ukoliko je tekst dovoljno dugačak, vrlo je verovatno da slova koja se najčešće pojavljuju u
šifratu odgovaraju najučestalije korišćenim slovima govornog jezika. Na osnovu toga se piše
sistem dve jednačine sa dve nepoznate i određuju parametri ključa.
4
Priprema za prvi kolokvijum
19.
Ukoliko se koristi engleski alfabet i ključ dužine 4 slova koliko je prostor ključeva za
Vigenereovu šifru ukoliko je:
a. dozvoljeno ponavljanje istih karaktera u ključu?
b. nije dozvoljeno ponavljanje istih karaktera u ključu?
a. 26 x 26 x 26 x 26 = 264
b. 26 x 25 x 24 x 23
20.
Da li je Vigenèreova šifra polialfabetska ili monoalfabetska? Objasnite ta dva pojma.
Vigenèreova šifra je polialfabetska, što znači da se svako slovo otvorenog teksta može
preslikati u jedno od m mogućih slova, gde je m dužina ključa.
21.
Playfair-ova šifra je:
a. monoalfabetska / monogramska
b. polialfabetska / poligramska
c. polialfabetska / monogramska
d. monoalfabetska / poligramska
22.
Da li se u šifratu dobijenim Playfairovom šifrom mogu naći digrami koji sadrže dva ista
slova – na primer EE?
Ne. U slučaju da se u otvorenom tekstu nalazi digram istih slova, između njih se ubacuje
slovo X. Drugim rečima, u šifratu se nalaze isključivo digrami različitih slova.
23.
Koje uslove mora da ispuni matrica da bi se koristila kao ključ za Hillovu šifru?
• Polja u matrici moraju uzeti vrednosti po modulu alfabeta koji se koristi, što znači da za
engleski alfabet moraju pripadati intervalu [0, 25].
• Matrica mora biti invertibilna, tj. mora imati svoju inverznu matricu kako bi
dešifrovanje bilo moguće.
24.
Koja dva algoritma su po načinu funkcionisanja slična:
a. Afina šifra i jednostavni XOR
b. Afina šifra i Vigenereo-ova šifra
c. Jednostavni XOR i One Time Pad
d. One Time Pad i Cezarova šifra
25.
U kom slučaju šifrovanje operacijom eksluzivno ILI postaje jednokratna beležnica?
U slučaju da je dužina ključa jednaka dužini otvorenog teksta,
5
Sigurnost informacionih sistema / Zaštita podataka
26.
Koja je dužina blokova otvorenog teksa nad kojima DES obavlja operacije, ključeva
(bez bitova parnosti) i podključeva DES algoritma?
Blok: 64 bita, ključ: 56 bita, podključ: 48 bita.
27.
Izbacite uljeza:
a. AES
b. DES
c. MD5
d. Twofish
Objašnjenje: DES, AES i TwoFish su simetrični blokovski algoritmi. MD5 je heš funkcija.
28.
Koliko rundi ima DES algoritam?
16 rundi.
29.
Najmanje dovoljan broj operacija šifrovanja i dešifrovanja za napad na dvostruki DES
algoritam je:
257
30.
Odrediti red veličine broja operacija šifrovanja i dešifrovanja za napad na trostruki DES
metodom susret u sredini:
2112
31.
Za DES i AES algoritme važi:
a. I DES i AES su Feistel-ove mreže
b. DES je Feistel-ova mreža a AES nije
c. DES nije Feistel-ova mreža a AES jeste
d. Ni DES ni AES nisu Feistel-ove mreže
32.
Za ECB i CBC režime rada važi:
a. U ECB režimu isti blok istim ključem uvek daje isti šifrat, dok u CBC to ne
mora da bude slučaj
b. U CBC režimu isti blok istim ključem uvek daje isti šifrat, dok u ECB to ne mora da
bude slučaj
c. I u CBC i u ECB režimu isti blok istim ključem uvek daje isti šifrat
d. I u CBC i u ECB režimu isti blok istim ključem uvek daje različiti šifrat
6
Priprema za prvi kolokvijum
33.
Operacije MixColumn i ShiftRow su deo jednog blokovskog algoritma. Kog?
AES algoritma
34.
Koliko potključeva generišu DES delimično-slabi ključevi?
2 potključa
35.
Koji od sledećih algoritama nije blokovski:
a. DES
b. AES
c. RC4
d. TwoFish
Objašnjenje: RC4 je sekvencijalni algoritam.
36.
U čemu leži sigurnost RSA algoritma?
U složenosti pronalaženja prostih faktora velikih brojeva
37.
U čemu leži sigurnost Diffie-Hellmanovog protokola za razmenu ključeva?
U složenosti računanja logaritama u konačnim poljima
38.
Dati su parametri g=7 i p=11. Koristeći Diffie-Hellmanov protokol za razmenu ključeva
odredite zajednički ključ ako su zamišljene vrednosti a=3 i b=6.
Alisa: Bob
1. Računa A = 73 (mod 11) = 2 Računa B = 76 (mod 11) = 4
2. Šalje Bobu A=2 Šalje Alisi B=4
3. Računa k = 43 (mod 11) = 9 Računa k = 26 (mod 11) = 9
39.
Dat je prost broj p=19 i generator g=2. Koristeći Diffie-Hellmanov protokol za razmenu
ključeva odredite zajednički ključ ako su zamišljene vrednosti a=3 i b=6.
k = 16
40.
Dati su generator g=2 i moduo p=5. Alisa je zamislila broj a=7, a Bob broj b=8.
Korišćenjem Diffie-Helmannovog protokola za razmenu ključeva odredite deljenu
tajnu:
k=1
7
Sigurnost informacionih sistema / Zaštita podataka
41.
Alisa želi da pošalje Bobu poruku šifrovanu RSA algoritmom. Alisa šifruje poruku:
Bobovim javnim ključem
42.
Alisa je poslala Bobu poruku šifrovanu RSA algoritmom. Bob dešifruje poruku:
Svojim privatnim ključem
43.
Alisa želi da pošalje Bobu poruku m digitalno potpisanu RSA algoritmom. Alisa
potpisuje sažetak poruke:
Svojim privatnim ključem
44.
Alisa je poslala Bobu poruku m potpisanu RSA algoritmom. Bob proverava potpis:
Alisinim javnim ključem
45.
Neka je poznat javni RSA ključ (n, e)=(55, 27) i poruka m=2. Odredite šifrat.
c = me (mod n) = 227 mod 55 = 18.
46.
Neka je poznat javni ključ u RSA algoritmu (n, e)=(55, 27) i šifrat c=10. Odredite
poruku m.
Pošto je poznat JAVNI ključ, prvo je potrebno odrediti odgovarajući PRIVATNI ključ kako
bi mogli da dešifrujemo c. Ovo je za male vrednosti n moguće. Postupak je sledeći:
• parametar n se faktoriše na proste činioce: n = 55 = 11 ∙ 5; faktori su p=11, q=5:
• određuje se: φ(n) = (11–1) ∙ (5–1) = 40;
• iz relacije koja povezuje ključeve 27 ∙ d = 1 (mod 40) određuje se privatni ključ d=3;
• otvoreni tekst se dobija jednačinom m = 103 (mod 55) = 10.
47.
Upotrebom RSA algoritma digitalno potpišite poruku m=3, ako je poznat javni ključ
(n, e)=(403, 103).
Najpre morate da odredite PRIVATNI ključ koji se koristi za potpisivanje. Parametar
n=403 se faktoriše na činioce p=13 i q=31, određuje se φ(n)=360, a zatim i ključ d=7.
Digitalni potpis poruke m=3 određuje se izrazom: s = md (mod n) = 37 (mod 403) = 172.
48.
Generator inicijalnih lozinki na hipotetičkom sistemu generiše lozinke dužine 5
znakova, od kojih su prva dva slova engleske abecede (26 slova), a poslednja 3 cifre
(0,1,...,9). I slova i cifre se mogu ponavljati. Koliko je različitih lozinki moguće
formirati?
676000 lozinki.
8
Priprema za prvi kolokvijum
49.
Da bi se smanjila dužina digitalnog potpisa poruke, računa se:
a. heš poruke koji se digitalno potpisuje
b. digitalni potpis, a zatim njegov heš
c. heš šifrata koji se zatim digitalno potpisuje
50.
Koliki heš generiše MD5?
128 bita
51.
Ukoliko digitalno potpišete poruku dužine 1KB i to pošaljete je zajedno sa potpisom
načinjenim MD5 algoritmom, onda ukupno šaljete:
1024 + 128 = 1152 bita.
52.
Objasnite pojam kolizije u heš funkcijama-
Heš funkcije su preslikavanja tipa više-na-jedan i nisu imune na pojavu kolizija. Kolizija je
pojava kada dva ili više različita ulaza m1, m2, ... rezultuju istim izlazom h.
53.
Jednosmerna heš funkcija generiše otisak dužine 160 bitova. Koliko mogućih poruka
generiše heš 0000....0001?
a. samo jedna
a. 160
b. 2160
c. beskonačno mnogo poruka
U ovom slučaju imate beskonačno mnogo ulaza koji generišu koačni broj izlaza. Dakle,
beskonačan broj ulaza generiše svaki izlaz.
54.
Za koji PRNG su karakteristične sledeće jednačine:
1. xn = a ∙ xn-1 + b (mod n)
2. xi = xi-1 e (mod n)
3. xi = xi-1 2 (mod n)
1. Linearni kongruentni generator, 2. RSA generator, 3. x2 mod n generator.
55.
U čemu je razlika između generatora slučajnih i pseudoslučajnih brojeva?
RNG nastaje iz prirodnog izvora slučajnosti. PRNG koristi izlaz RNG-a kao početnu
vrednost, a izlazni niz karakteriše periodičnost uslovljena algoritmom.



Tajnost komunikacija
2014.

2
Sadržaj Uvod ...................................................................................................................................................3 Tajnost komunikacija ........................................................................................................................3 Steganografija ..................................................................................................................................3 Osnove savremene steganografije ..............................................................................................4 Primeri primene steganografije ..............................................................................................5 Kriptografija ...................................................................................................................................7 Uvod u kriptografiju ...................................................................................................................8 Poverljivost, integritet i raspoloživost ...............................................................................8 Kontrola pristupa ..................................................................................................................... 10 Sigurnost softvera .................................................................................................................... 11 Plan rada .................................................................................................................................... 11

3
Uvod Savremeno poslovanje, koje se pre svega zasniva na upotrebi računarskih sistema i razmeni podataka u elektronskom obliku izloženo je različitim rizicima koji mogu da imaju nesagledive posledice. Suočeni smo sa svakodnevnim napadima na računarske mreže, pokušajima neovlašćenog pristupa podacima, prisluškivanja, zlonamerne izmene podataka i sl. Napredak tehnologije omogućio je primenu novih načina komunikacije, omogućeno je lakše poslovanje ali se istovremeno pojavio problem sigurnosti, kao i potreba za uvođenjem novih mehanizama koji treba da preuzmu ulogu klasičnih („papirnih“) rešenja kao što su identifikacija, kontrola pristupa i verifikacija.
Odgovor na većinu izazova treba tražiti u primeni kriptografskih rešenja, mada postoje problemi na koja kriptografija ne može adekvatno da odgovori.
Tajnost komunikacija Tajnost komunikacija je zagarantovano pravo koje se nalazi u zakonima većine savremenih  država i odnosi se sprečavanje neovlašćenih lica da dođu da sadržaja poruke ili podataka koji se prenose javnim komunikacionim putevima.  Bez obzira na zagarantovano pravo, strane u komunikaciji mogu da primene dodatna rešenja koja će im omogućiti veću kontrolu tajnosti. Uopšteno gledano, tajnost komunikacije može da se ostvari na dva načina, primenom:
 Steganografije  Kriptografije
Steganografija Steganografija je proces ugrađivanja poruke, koja treba da bude tajna, u drugu poruku koja nema elemente tajnosti i koja je sastavni deo uobičajne komunikacije između dve ili više strana. Pri tome se teži da se prikrije činjenica da se prenosi tajna poruka ali ne i da komunikacija postoji. Javna poruka može da bude u bilo kom, uobičajenom formatu, i u ovom slučaju se naziva nosilac. Primeri pogodnih nosioca su: tekst, slika, audio i video zapis ili multimedijalni sadržaji. Celina dobijena ugrađivanjem tajne poruke u nosilac se naziva steganografski medijum ili stego-datoteka.
Pojednostavljeno, cilj steganografije je da se poruka pošalje javnim kanalom a da to niko osmim pošiljaoca i primaoca ne zna.
Tehnika ugrađivanja poruke u nosilac treba da bude takva da dobijeni stego medijum što više liči na nosilac, kako po veličini tako i po funkcionalnosti, kako prilikom prenosa ne bi bila lako uočljiva.
Primeri primene steganografije su poznati još iz antičke Grčke. Gotovo 500 godina pre nove ere, grk po imenu Demaratus poslao je upozorenje Spartancima o invaziji Kserksa. Herodot
4
opisuje metod koji je korišćen za slanje poruke: „Kako je opasnost otkrivanja bila velika, postojao je samo jedan način na koji je mogao da pošalje poruku: sa drvene table je skidao vosak, zatim je na njoj ispisivana poruka šta Kserks planira da uradi, a potom je poruka ponovo skrivana voskom. Na ovaj način table, naizgled čiste, ne bi prouzrokovale probleme sa stražarima duž puta...“
Brojni su primeri i iz bliže istorije, kao što je pisanje „nevidljivim“ mastilom, pisanje teksta na veoma malim površinama, veličine tačke u tekstu (microdot technology) ili slanje pisma „bezazlenog“ sadržaja u kojoj je skrivena poruka u npr. drugom slovu svake reči.
Primer: Apparently neutral's protest is thoroughly discounted and ignored. Isman hard hit. Blockade issue affects pretext for embargo on by products, ejecting suets and vegetable oils.  Izdvojena poruka glasi: Pershing sails from NYr June 1. Steganografija je našla primenu i kod zaštite autorskih prava primenom tehnike vodenog žiga (digital watermak). U neki digitalni sadržaj (film, e-knjigu i sl.) se utiskuju informacije o autoru, vlasništvu, licencama i sl. Ne krije se prisustvo informacije ali se krije način unosa informacije i mesta na kojima se informacija nalazi. Dobra rešenja su otporna na izmene (npr. kompresiju) ili izdvajanje dela sadržaja i služe kao dokaz o autorskim pravima digitalnog sadržaja.  Osnove savremene steganografije Proces skrivanja tajne poruke u javnu može da se predstavi blok šemom na slici 1.1.
Slika 1.1 Blok šema skrivanja poruke primenom steganografije
Na predajnoj strani postoje tri ulazne vrednosti:  Poruka, koja treba da se sakrije;  Nosilac (javna poruka);  Ključ. Stego algoritam označen kao fE, određuje postupak utiskivanja poruke u nosilac a konkretnu realizaciju algoritma određuje ključ koji treba da bude tajna vrednost poznata samo pošiljaocu i primaocu. Ključ najčešće predstavlja niz vrednosti ili pravila odabranih na takav način da ih je teško otkriti ili pogoditi-Nakon primene steganografskog algoritma dobija se izlazna vrednost koja se naziva stego medijum. Stego medijum se do primaoca prenosi javnim javnim komunikacionim putem. Primaoc ima dve ulazne vrednosti:  Stego medijum i   Ključ
5
Primenom inverznog steganografskog algoritma (fE-1) dobijaju se dve izlazne vrednosti:  Poruka  Nosilac  Da bi se obezbedio tajni prenos poruke , neophodno je da obe strane u komunikaciji imaju isti ključ, da se dogovore oko izbora steganografskog algoritma i da postoji rasoploživ komunikacioni put. Distribucija ključa nije jednostavan problem, pogotovo u okolnostima kada su dve strane u komunikaciji na velikoj udaljenosti ili u strogo kontrolisanim okruženjima. Steganografski algoritam treba da bude otporan na analizu stego medijuma i napade. Pored toga, važno je da nosilac bude znatno veći od poruke kako bi se povećala otpornost na napade Primeri primene steganografije Realizacija stego sistema je upotrebom računarska se naziva računarska steganografija. Svi podaci koji se čuvaju na računaru su zapisani u binarnom obliku,bez obzira na njihovu kasniju funkcionalnost. Pokazuje se da neki formati zapisa podataka, kao što je slučaj sa fajlovima koji sadrže slike (BMP, JPG, ...), po pravilu sadrže višak informacija (redudantni su). Upravo ova činjenica omogućava da oni posluže kao nosilac i da se u njih ugradi tajna poruka.
Računarski fajl koji predstavlja sliku u BMP formatu je zapisan kao skup podataka o svakom pikselu i opisan je brojnim vrednostima koje definišu boju pojedinačnog piksela. Boja svakog piksela može da se opiše pomoću nijanse crvene (R-red), zelene (G -green) i plave boje (B-blue), čijom kombinacijom se dobija željena boja biksela. Ukoliko se nijansa svake od tri osnovne boje (R, G i B) opiše sa po jednim bajtom (8 bita), sledi da je za opis jednog piksela potrebno rezervisati 24 bita. Svaki od bajtova može da ima 256 različitih vrednosti kojom se određuje nijansa osnovne boje. Na ovaj način je moguće da se definiše 224 različitih nijansi boja piksela. Međutim, razlika između susednih nijansi može da bude veoma mala i to ostavlja prostor za utiskivanje tajne poruke.
Posmatrajmo vrednost jednog piksela koji je definisan sa 24 bita. Neka je vrednost crvene boje 171 (1010 1011 u binarnom zapisu), zelene boje 158 (1001 1110) a plave boje 204 (1100 1100). Rezultantna boja piksela je prikazana na slici 1.2 a. Ukoliko se promeni vrednost  nijanse plave boje za 1 na vrednost 241 (0011 0001) promena rezultantne boje će biti gotovo neprimenta vidi sliku 1.2.b.
a)0x1010 10110x1001 1110 0x1100 1100   definiše ovu boju piksela
b) 0x1010 10110x1001 1110 0x1100 1101 definiše ovu boju piksela
Slika 1.2 Promena bita najniže vrednosti u opisu nijanse plave boje
Razlika u nijansi rezultantne boje je praktično neprimetna. Sličan rezultat bi se dobio kada bi se istovremeno promenile vrednosti bita najmanje vrednosti i kod crvene i zelene boje. Na ovaj način je moguće utisnuti tajnu poruku u neku sliku a da se pri tome ne izmeni veličina slike (nosioca) niti da se informacioni sadržaj nosioca bitno promeni. U 24 bita nosioca moguće je uneti najviše do 3 bita poruke. Sledi ograničenje da nosilac treba da bude bar 8 puta veći od poruke koju je potrebno preneti.
6
Treba voditi računa da se poruka „utiskuje“ u bite najniže vrednosti u protivnom stego datoteka može bitno da se razlikuje od nosioca (vidi sliku 1.3) a) 0x1010 10110x1001 1110 0x1100 1100 definiše ovu boju piksela  b) 0x0010 1011 0x1001 1110 0x1100 1100 definiše ovu boju piksela Slika 1.3 Promena bita najviše vrednosti u opisu nijanse crvene boje
Na slici 1.4 a) je prikazana slika( nosioc) a na slici  1.4 b) stego datoteka u koju je upisan celokupano delo „Alisa u zemlji čuda“, koje je kao poruka prethodno bilo zapisano u PDF formatu.

a)                                         b) Slika 1.4 Slika Alise a); na slici b) stego datoteka u koju je utisnut PDF fajl Poruka se, na sličan način, može sakriti i u html dokumentu koji se prikazuje na veb strani. Izgled stranice (koja će poslužiti kao nosilac) i pripadajući kôd je predstavljen na slici 1.5. Kôd definiše format i sadržaj koji će se prikazati na stranici. Boja slova je definisana sa tri bajta, samo su u ovom primeru vrednosti crvene, zelene i plave boje prikazani u heksadecimalnom formatu.  Za prikaz teksta crnom bojom sve tri vrednosti su postavljene na 00 (fontcolor=’#00 00 00’).
Izgled veb stranice
Pripadajući kôd
Slika 1.5 Izgled veb stranice i pripadajućeg html koda Ukoliko se promene biti najmanje vrednosti koji definišu boju fonta izgled veb stranice se neće bitno promeniti, što može iskoristiti za skrivanje poruke (slika 1.6). Neprimetno je promenjena boja teksta. Skrivena poruka je 110 010 110 011 000 101.
7
Izgled veb stranice
Pripadajući kôd
Slika 1.6 Izgled veb stranice i pripadajućeg html koda nakon tiskivanja poruke
Postoji više besplatnih steganografskih alata koji se mogu preuzeti sa sledećih adresa: Tabela 1.1 Besplatni programi za primenu Steganografije
Detekcija steganografskog sadržaja se naziva steganoanaliza. U prksi se primenjuju različite tehnike, ali su to najčešće: vizuelna analiza koja je moguća u manjem broju slučajeva, kao u navedenim primerima ili zahtevnija varijanta koja se zasniva na statističkoj analizi.
Kriptografija Kriptografija (kovanica nastala od od grčkih reči κρυπτός – tajna ili skrivanje, γράφειν – pisanje i λογία - nauka) je nauka koja izučava tehnike transformacije podataka koji se prenose, na takav način da značenje podataka bude dostupno samo ovlašćenim stranama u komunikaciji. Istovremeno, transformacija treba da bude takva da neovlašćene strane u komunikaciji, koje dođu u posed transformisane poruke, ne mogu da dođu do polaznih podataka.
Za razliku od steganografije,  kod primene kriptografskih rešenja se ne krije činjenica da se poruka prenosi. Kriptografska rešenja se, u opštem slučaju, primenjuju zato što se pretpostavlja da prenosni put nije siguran i da postoji velika verovatnoća da će poruka dospeti u posed neovlašćenih primaoca.
8
Najstariji dokumenti koji govore o primenu kriptografskih rešenja pojavili su se oko 1900. godine pre nove ere, i odnose se na zapise iz drevnog Egipta kada su za razmenu pisanih poruka korišćeni nestandardni hijeroglifi. Oduvek je postojala potreba da se obezbedi poverljivost poruka i neki naučnici tvrde da je kriptografija počela da se razvija paralelno sa razvojem pisma. Uvod u kriptografiju U kriptografskoj literaturi nije  uobičajeno sa se strane u komunikaciji obležavaju kao A, B, ..., već im se dodeljuju imena ljudi.  Legalne strane u kominikaciji se najčešće nazivaju Alisa i Bob , a po potrebi se uvode i dodatna imena. Oni po pravilu predstavljaju „dobre momke“. „Loši momci“ u zavisnosti od svojih uloga mogu da budu: Eva (eavesdropper – onaj ko prisluškuje), Trudi (intruder – negativac opšte namene) i drugi.
Pretpostavimo da Alisa odtvara banku sa onlajn pristupom i da je Bob njen klijent. Oni svoju komunikaciju ostvaruju preko javne mreže u koju, po pravilu, nemaju poverenja jer praksa pokazuje da postoje brojni načini da neko može da ih prisluškuje ili da čak menja podatke na prenosnom putu.  Alisa i Bob se suočavaju sa bezbednosnim problemima.
Bob i Alisa, pre svega, žele da imaju sigurnu komunikaciju, odnosno da njihova komunikacija bude poverljiva, da budu sigurni da podaci koje razmenjuju nisu promenjeni na prenosnom putu, i sl. Bob i Alisa, takođe, žele da budu sigurni da su podaci koji se čuvaju u bazi banke sigurni, da tim podacima mogu da pristupe samo njih dvoje i da moguća izmena tih podataka bude zasnovana na stvarnim uplatama i isplatama.
Trudi, kao napadač, želi da sazna sadržaj komunikacije, možda čak i da tajno izmeni sadržaj podataka, onemogući komunikaciju, da se lažno predstavi kao Bob ili da sebi obezbedi prava koja joj ne pripadaju.
Razmotrimo tradicionalno značenje pojmova: Poverljivost, integritet i raspoloživost. Poverljivost, integritet i raspoloživost Poverljivost predstavlja skup aktivnosti koje treba da obezbede da neovlašćena strana u komunikaciji ne dođe do poverljivih informacija. Poverljivost, takođe, može da odredi do koje mere neka informacija može da bude dostupna odnosno nedostupna neovlašćenim licima.
Primer:  Alisa mora da spreči Trudi da dođe do podataka o Bobovom računu (stanje, transakcije, ... ), videti sliku 1.7. Bobu je to takođe od interesa.

9
Slika 1.7 Potreba za poverljivošću: prisluškivanje komunikacije
Integritet podataka označava skup aktivnosti koje treba da spreče ili detektuju neovlašćenu izmenu ili brisanje podataka, bilo da se podaci prenose ili čuvaju. Pri tome treba voditi računa da napad može izvesti Trudi, ali i neko od legalnih korisnika koji pokuša da prekorači definisana ovlašćenja.
Primer: Trudi ne sme da ima mogućnost da menja stanje Bobovog računa. Bobu ne treba dozvoliti da povećava stanje na svom računu ako to nije posledica odgovarajuće uplate.
Slika 1.8 Integritet: neovlašćena izmena podataka na prenosnom putu
Raspoloživost predstavlja sposobnost sistema da ovlašćenom korisniku pruži uslugu kad god je to potrebno. Informacioni sistem koji čuva i obrađuje podatke, sigurnosni mehanizmi koji treba da ga zaštite i komunikacioni putevi moraju pravilno da funkcionišu čak i u situacijama kad je sistem predmet napada.
Jedan od čestih napada se naziva DoS napad (Denial of Service). Osnovni cilj DoS napada je zagušenje komunikacionih puteva kako bi se npr. informacioni sistem učinio nedostupnim za korisnike (ilustracija na slici 1.9).
Primer: Alisa mora da obezbedi Bobu dostupnost informacija o njegovom računu i da mu omogući transakcija kad god mu je to potrebno.  Alisa mora da bude u stanju da obavlja transsakcije, bez obzira na poteškoće sa kojima se suočava. U suprotnom, nezadovoljni klijent će verovatno promeniti banku.
10
Slika 1.9 Raspoloživost: ilustracija DoS napada
Pored poverljivosti, integriteta i raspoloživosti postoje i drugi bezbednosni zahtevi koje treba rešiti. Ovde će se razmotriti problem kontrole pristupa. Kontrola pristupa Kada Bob treba da pristupi podacima na svom računaru, kako računar može da „zna“ da je to stvarno Bob a ne Trudi? Treba odgovoriti na sledeća pitanja:  Ko je korisnik?  Da li je korisnik zaista onaj kojim se predstavlja?
Jedno od rasprostranjenih rešenja je upotreba lozinke. Osnovna pretpostavka je da je lozinka tajna koju zna samo njen vlasnik i da se ne može lako pogoditi. Čak i ako je ova pretpostavka tačna, preostaje da se uneta lozinka verifikuje. Gde se nalazi podatak na osnovu kog će se lozinka verifikovati? Ukoliko je „kopija“ lozinke zapisana u nekom fajlu na računaru, da li je moguće da je neki drugi korisnik pročita i zloupotrebi? Mada naizgled sličan, problem utvrđivanja identiteta na udaljenom računaru (povezan mrežnim putem) je daleko složeniji. Podatak koji treba da se verifikuje treba poslati komunikacionim putem koji može da bude izložen napadu. Bilo ko može da snimi poslati podatak i da kasnije sa tim podatkom pokuša lažno da se predstavi.
Da li je lozinka pouzdano rešenje? Savremena tehnologija nudi rešenja koja su zasnovana na biometrijskim podacima i smart karticama. Da li ovo predstavlja bolje rešenje od upotrebe lozinki?
Servis koji obezbeđuje proveru identiteta se naziva autentifikacija i u savremenim sistemima se zasniva na primeni kriptografije, odnosno na pažljivo projektovanim sigurnosnim protokolima komunikacije. Proces autentifikacije može da se odnosi na korisnika, ali isto tako i na neki proces (program, proceduru, računar...).
Nakon što se korisnik autentifikuje potrebno je odrediti skup akcija koje korisnik može da obavi. Ako se Bob uspešno autentifikovao u Alisinoj banci, treba mu omogućiti uvid u stanje, uplate na sopstveni račun ili prenos sredstava na neki drugi račun. Bob ne treba da ima ovlašćenja da podiže novac sa Čarlijevog računa ili da instalira novi softver u banci. Dodela prava autentifikovanom korisniku se naziva autorizacija.
11
Kontrola pristupa je deo sigurnosne politike koja treba da ograniči korisnike i procese u izvođenju različitih akcija nad objektima kao što su baze podataka, fajlovi, delovi zajedničke memorije i sl.
Kontrola pristupa obuhvata autentifikaciju i autorizaciju. Sigurnost softvera Kriptografska rešenja, protokoli, kontrola pristupa i drugi sigurnosni mehanizmi se najčešće realizuju softverski. Praksa pokazuje da se projektovanju softvera treba posvetiti velika pažnja jer propusti u ovom delu posla mogu potpuno da obesmisle veoma dobro projektovana sigurnosna rešenja. Koji su česti problemi?
Mehanizmi zaštite su po pravilu deo nekog većeg sistema i ne mogu da se projektuju niti da funkcionišu nezavisno od njega. Programi mogu da budu veoma obimni i složeni i po pravilu ih je teško testirati na sve moguće propuste, pa postoji velika verovatnoća da konačna verzija programa sadrži propuste koji mogu da se zloupotrebe kako bi se zaobišli sigurnosni mehanizmi.
Softverski propusti nastaju načešće slučajno, mada su poznati i primeri kada su nesavesni pojedinci namerno projektovali rešenja na takav način da se omogući njihova naknadna zloupotreba. S druge strane, svakodnevno se pojavljuje sve veći broj tzv. zlonamernih programa kao što su virusi, crvi, trojanci i sl.
Kod analize sigrunosti softvera važnu oblast predstavljaju operativni sistemi. Operativni sistemi imaju ugrađene neke od sigurnosnih mehanizama (kontrola pristipa, npr.), i pored ostalih funkcija su zaduženi za izvršavanje aplikativnih programa. Nažalost, svedoci smo da veoma često sadrže sigurnosne propuste i pored brojnih ažuriranja i brige proizvođača za usavršavanjem rešenja.
Osnovna pitanja koja se nameću su sledeća: Kako identifikovati propuste i kako odrediti mogućnost njihove zloupotrebe? Operativni sistemi mogu da imaju i više desetina miliona linija koda, pa postupci analize predstavljaju izuzetno obiman posao.  Kako razviti softver koji će sadržati što manje sigurnosnih propusta? Kako se štititi od zlonamernog softvera i u kom pravcu se kreće razvoj ove oblasti sa obe strane „ratišta“?  Da li se sa bezbednosnog stanovišta može verovati operativnim sistemima čija rešenja nisu dostupna javnoj analizi?
Plan rada Naredne lekcije je moguće podeliti na četiri tematske celine:
 Kriptografija  Kontrola pristupa  Protokoli  Sigurnost softvera i hardvera.
12
U okviru kriptografije će se razmatrati:
 Osnove teorije informacija i zaštite  Klasična kriptografija  Simetrična kriptografija  Kriptografija javnih ključeva  Heš funkcije, digitalni potpis  Infrastruktura javnih ključeva
Protokoli obuhvataju analizu projektovanja , primene i analizu aktuelenih bezbednosnih protokola.
Kroz kontrolu pristupa će biti predstavljene aktuelne tehnike autentifikacije primenom lozinki i biometrijskih podataka kao i poređenje njihovih strana. Tehnika autorizacije će se analizirati na primerima lista kontrole pristupa, bezbednosnih barijera i sistema za prevenciju i detekciju upada u sisteme.
Analiza sigurnost softvera zasnovana je na predstavljanju poznatih bezbednosnih propusta i preporuka za njihovu kontrolu, analizu zlonamernih programa i očekivanog pravaca njihovog razvoja kao i razvoja antivirusnih softvera.
Pored toga biće predstavljene preporuke za dizajn hardverskih modula na kojima se zasnivaju sigurnosna rešenja kao i izvori kompromitujućeg elektromagnetnog zračenja koji mogu dovesti do nekontrolisanog odliva sigurnosno kritičnih podataka.



Klasična kriptografija deo I
2014.

2
Sadržaj Uvod ...................................................................................................................................................3 Terminologija ..................................................................................................................................3 Polazne pretpostavke.......................................................................................................................3 Tipovi napada na kriptograski sistem ...........................................................................................5 Sigurnost šifarskog sistema ..........................................................................................................6 Klasična kriptografija ...................................................................................................................6 Šifre transpozicije ..................................................................................................................7 Transpozicija kolona ...............................................................................................................7 Zaključci kriptoanalize 1 .......................................................................................................9 Dvostruka transpozicija ........................................................................................................ 10 Zaključci kriptoanalize 2 ..................................................................................................... 11 Šifre zamene................................................................................................................................. 11 Šifre proste zamene ................................................................................................................ 12 Analiza Cezarove šifre ....................................................................................................... 13 Opšti oblik šifre proste zamene ....................................................................................... 13 Homofona šifra ....................................................................................................................... 14 Kripto analiza 3 ..................................................................................................................... 15

3
Uvod Izučavanje kriptografije ćemo početi od analize klasičnih šifarskih sistema, kako zbog njihove istoriske vrednosti tako i zbog izučavanja principa rada koji se i dalje koriste u savremenim šifarskim sistemima. Pored predstavljanja klasičnih rešenja, biće analzirana njihova sigurnost, dobre i loše strane i uvešće se elementi kripto-analize.
Terminologija Otvoreni tekst (plaintext) je poruka ili dokument koji treba da se zaštiti. Šifrovanje (encryption) je operacija kojom se otvoreni tekst menja ili transformiše na takav način da neovlašćenim stranama u komunikaciji bude potpuno nerazumljiv, odnosno da iz takvog sadržaja ne mogu doći do bilo kakve informacije.  Rezultat šifrovanja se naziva šifrat (ciphertext). Šifrat predstavlja izlaznu vrednost transformacije otvorenog teksta. Skup pravila koji se koristi za šifrovanje otvorenog teksta se naziva algoritam šifrovanja. Operacije algoritma šifrovanja zavise od vrednosti ključa šifrovanja (key). Ključ šifrovanja je ulazni parametar algoritma šifrovanja kao i otvoreni tekst. Operacija kojom se iz šifrata dobija otvoreni tekst naziva se dešifrovanje (decryption). Skup pravila koji se koristi za dešifrovanje šifrata se naziva algoritam dešifrovanja. Ključ dešifrovanja određuje način rada algoritma dešifrovanja.  Šifarski sistem sa simetričnim ključem (symmetric key cryptosystem) koristi isti ključ za šifrovanje i dešifrovanje. Preciznije, dovoljno je da se iz jednog ključa može jednoznačno izračunati drugi ključ. Šifarski sistem sa javnim ključem (public key cryptosystem) koristi javni ključ za šifrovanje i tajni ključ (private key) za dešifrovanje. Mada su javni i tajni ključ povezani odgovarajućim pravilima i ne mogu se generisati nezavisno jedan od drugog, poznavanje jednog ključa nije dovoljno za izračunavanje drugog ključa.
Kriptografija je nauka o dizajniranju šifarskih sistema
Polazne pretpostavke Idealan kriptografski algoritam treba da je tako projektovan da njegova sigurnost počiva isključivo na tajnosti ključa za dešifrovanje. Odavde sledi da niko, bez obzira što u potpunosti poznaje kriptografski algoritam, način njegove realizacije i šifrat, do otvorenog teksta ili bilo kakvih informacija o otvorenom tekstu ne može da dođe bez poznavanja ključa za dešifrovanje.
Pri analizi sigurnosti nekog kriptografskog sistema polazi se od pretpostavke da algoritam šifrovanja nije tajna. Ovo je jedan od najvažnijih Kirhofovih principa.
4
Danski lingvista i kriptograf Avgust Kirhof (Auguste Kerckhoffs, 1835. –1903) je 1883. godine objavio dva članka poda nazivom Vojna kriptografija. U svojim radovim predložio je više poboljšanja u primeni kriptografskih tehnika i 6 principa kojih se treba držati prilikom projektovanja kriptografskih uređaja. Njegove ideje su preživele sud vremena i dovele do mnogih poboljšanja u kriptografskim rešenjima. Najpoznatiji je drugi, od šest principa, iz kog sledi da sigurnost kriptosistema mora počivati na tajnosti ključa.
Zašto se uvodi pretpostavka da je dizajn kripto sistema (algoritam, principi rada i sl.) poznat napadaču? Prirodno je pretpostaviti da će napadač imati teži posao ako ne zna algoritam i podatke o radu sistema.
Praksa pokazuje da tajni algoritmi retko dovoljno dugo ostanu tajni. Na primer, u vojnim primenama su česte situacije zarobljavanja šifarskih uređaja protivničke strane, u industrijskom sektoru su moguće krađe, i sl. Reverzni inženjering softverskih i hardverskih rešenja može dovesti do svih potrebnih podataka. Ukoliko se sigurnost kriptografskog sistema zasniva na tajnosti algoritma na ovaj način može  biti kompromitovan ceo sistem, a ukoliko se to desi potrebno je u celom sistemu zameniti sve algoritme šifrovanja. S druge strane, ako se kompromituje ključ, dovoljno je zameniti ovaj parametar i nastaviti sa radom bez ikakvih srugih promena.
Tajni algoritmi nisu dostupni širem sudu stručne javnosti, i veoma česti imaju nedostatke koje protivnička strana može da iskoristi. Nasuprot tome, javni algoritmi su podložni analizi mnogih kriptografa, dostupni su sudu javnosti i ukoliko imaju slabosti, bolje je da se to sazna na vreme.
Na slici 2.1 je predstavljena blok šema jednog sistema za šifrovanje i dešifrovanje. Na predajnoj strani postoji algoritam za šifrovanje čiji ulazni parametri su otvoreni tekst (poruka) i ključ za šifrovanje, KE. Otvoreni tekst može da se posmatra kao skup manjih celina Pi (npr. bita ili bajtova), gde i predstavlja redni broj celine. Rezultat šifrovanja je šifrat, a svaka šifrovana celina otvorenog teksta daje odgovarajuću vrednost šifrata Ci.  Šifrat se šalje komunikacionim putem, koji se ne smatra bezbednim, do prijemne strane. Na prijemnoj strani se šifrat dešifruje. Ulazni parametri algoritma dešifrovanja su šifrat i ključ dešifrovanja, KD. Rezultat dešifrovanja je otvoreni tekst, odnosno poruka koja je poslata.
Slika 2.1 Blok šema sistema za šifrovanje i dešifrovanje
Kripto-analiza je proces kojim se iz šifrata dolazi do informacija o otvorenom tekstu bez poznavanja ključa za dešifrovanje.
5
Cilj kripto-analize ne mora da bude samo otvoreni tekst. Za napadača bi bilo idealno ako bi saznao vrednost ključa za dešifrovanje. U tom slučaju bi mogao da dešifruje sve poruke koje su prethodno poslate i poruke koje će se naknadno slati, sve dok se koristi isti ključ. Cilj može da bude i da se sazna samo jedan deo ključa, jer se na taj način smanjuje neodređenost vrednosti ključa, i sl.
Tipovi napada na kriptograski sistem Prilikom analize sigurnosti kriptografskog sistema, važno je razmotriti moguće napade. Pre svega, napadač može da isproba sve moguće ključeve i na taj način sigurno može da pronađe ključ kojim može da dešifruje poruku. Ovaj postupak se naziva potpuna pretraga ključeva. Da bi se napadač obeshrabrio, potrebno je da ključ bude takav da postoji veoma veliki broj mogućih ključeva tako da napadač ne može da ih isproba u nekom definisanom vremenskom intervalu. Skup svih mogućih vrednosti ključeva se naziva prostor ključeva.
Primer: Ako je ključ definisan sa 8 bita (kaže se da je dužina ključa 8 bita) onda postoji 28=256 različitih ključeva. Za ključ dužine 256 bita postoji približno 1077 različitih vrednosti. Ukoliko napadač treba da proba sve moguće kombinacije, u drugom slučaju će mu posao biti daleko zahtevniji.
Očigledno je da je za siguran šifarski sistem neophodan izbor ključa velike dužine. Međutim, ovo je samo potreban ali ne i dovoljan uslov. To znači da kriptografski sistem koji ima ključ dovoljno velike dužine ne mora nužno biti siguran. Razloge treba tražiti u drugim tipovima napada koji se ne zasnivaju na potpunoj pretrazi ključeva. Ukoliko ti napadi zahtevaju manje obrade i vremena od potpune pretrage ključeva onda se oni nazivaju skraćeni napadi. Napadi se mogu klasifikovati na više načina, a ovde će biti predstavljeni samo neki od njih:
 Napad na osnovu poznavanja šifrata (S) Poruka se šifruje zbog pretpostavke da će (u šifrovanom obliku) biti dostupna neovlašćenoj strani. Analizom šifrata, ukoliko algoritam šifrovanja ima nedostatke, može se doći do informacija o otvorenom tekstu.  Napad na osnovu poznatog (dela) otovrenog teksta (S+R) Poruke koje se šalju, često imaju delove koji su unapred poznati. Službena prepiska (diplomatija, vojska , institucije,...) ima standardizovana zaglavlja, podatke o instituciji, brojeve telefona, način oslovljavanja, potpis,.... U postupku analize mogu se iskoristiti ova saznanja kako bi se lakše dešifrovao ostatak poruke, kako bi se došlo do podataka o ključu i sl.  Napad na osnovu izabranog otvrenog teksta Pretpostavimo da u istoj kancelariji rade Bob i Trudi. Bob šifruje e-poštu koju šalje Alisi jer pretpostavlja da Trudi kao administrator računarskog sistema može da pročita njegovu prepisku. Proces šifrovanja je automatizovan. Trudi, koja je dobar kriptoanalitičar, je blizu uspeha u dešifrovanju poruka ali bi joj u analizi pomoglo kad bi Bob šifrovao poruku tačno određenog sadržaja. Šta može Trudi da uradi? Sačekaće
6
da Bob izađe na ručak, i ukoliko se nije odjavio sa računara, Trudi će sa Bobovog računara poslati željenu poruku na svoju adresu. ... Ovaj napad se naziva još i Lunchtime attack.  Napad na osnovu adaptivno izabranog otvorenog teksta Trudi bira otvoreni tekst, uradi analizu, izabere novi otvoreni tekst na osnovu postignutih rezultata,... Potrebno je samo da Bob ima dobar apetit. Postoje i mnogi drugi napadi i praktično ih je nemoguće sve definisati.
Sigurnost šifarskog sistema Šifarski sistem je siguran ako je najefikasniji poznati napad – potpuna pretraga ključeva.  S druge strane, šifarski sistem je nesiguran ako nije otporan na bilo koji oblik skraćenog napada. Pod skraćenim napadom se podrazumevaju svi drugi efikasniji napadi od potpune pretrage ključeva.
Sledi: nesiguran sistem može biti otporniji na „razbijanje″ od sigurnog sistema sa malim prostorom ključeva? Zbog toga je potrebno dopuniti definiciju sigurnosti.
Siguran sistem mora imati dovoljno veliki prostor ključeva!
Primer: Pretpostavimo da Alisin šifarski sistem ima ključ dižine 100 bita. U tom slučaju je prostor ključeva (broj mogućih ključeva) 2100. Ako Trudi krene da proba svaki od mogućih ključeva, najverovatnije će pronaći odgovarajći ključ nakon što pregleda polovinu ključeva 2100/2=299. Ako Trudi može da testira 230 ključeva u sekundi, onda će pronaći pravi ključ za približno 19 h 1012 godina, odnosno napad nije izvoddljiv u prihvatljivom vremenu. Međutim, ako Trudi zna da Alisa, iz nekog razloga, bira ključeve samo iz nekog manjeg podskupa od svih mogućih, na primer iz podskupa od 260 ključeva onda će uz analizu 230 ključeva u sekundi, Trudi doći do rezultata za približno 3.4 godine. U nekim slučajevim to može da bude prihvatljiv rezultat.
Zašto bi Alisa birala ključeve samo iz nekog podskupa. Probajte da odgovorite kako prosečan korisnik definiše svoju lozinku. Na raspolaganju su mu barem 128 karaktera koje može da otkuca na tasturi, mežu njima slova, cifre, znaci kao „#$%&/().... Bira li korisnik sve moguće kraktere? Po pravilu ne, njačešće je to skup slova i to samo malih. Od mogućih 128, koristi samo podskup od 26.
Klasična kriptografija Da bi se predstavili osnovni principi rada svremenih algoritama prvo će biti predstavljeni klasični šifarski sistemi. Rešenja klasične kriptografije mogu da se svrstaju u dve grupe:
 Šifre transpozicije  Šifre zamene
7
Šifre transpozicije Ako se otvoreni tekst posmatra kao niz slova, onda se šifre transpozicije mogu opisati kao zamena redosleda slova, ili u opštem slučaju zamenom redosleda simbola kojim je poruka napisana. Šifrat može da sadrži samo simbole koje je sadržao i otvoreni tekst, a dužina otvorenog teksta i šifrata ostaje ista.
Ova ideja se primenjuje i kod savremenih šifara.
Šifre transpozicije će biti prikazane kroz primere
 Transpozicije kolona i  Dvostruke transpozicije Transpozicija kolona Jednu od veoma starih tehnika šifrovanja koristili su Spartanci oko 500 godina p.n.e. Prvo je potrebno da se štap odgovarajućeg prečnika obmota sa kajšem. Potom se poruka piše horizontalno, a nakon što se kajš skine sa štapa na njemu ostaje zapis (šifrat) koji može da bude nerazumljiv za protivnika. Proces dešifrovanja zahteva da druga strana ima štap istih dimenzija, a ključ predstavlja prečnik štapa (videti sliku 2.2).
Slika 2.2 Skitala, primer transpozicije
Kako automatizovati ovaj postupak šifrovanja? Matrica predstavlja rešenje.
Neka je potrebno da se šifruje poruka od  11 slova: SEE THE LIGHT. Odabere se matrica potrebnih dimenzija, tako da u nju mogu da se upišu sva slova otvorenog teksta. U ovom slučaju se uzima matrica dimenzija 3h4 (ukupno 12 mesta). Da bi poruka imala 12 znakova dopisuje se potreban broj unapred dogovorenih znakova. U ovom primeru se dopisuje jedan znak H: SEE THE LIGHT H. Matrica se popunjava horizontalno s leva na desno, kao na slici 2.3.
Slika 2.3 Popunjavanje matrice otvorenim tekstom
Šifrat se dobija tako što se sadržaj matrice čita iz kolona (vertikalno) počevši od leve strane. Šifrat je: SHGEEHELTTIX.
Šta predstavlja ključ? Ključ je dimenzija matrice. Na prijemnoj strani je potrebno popuniti matricu istih dimenzija. Matrica se popunjava po kolonama, a otovreni tekst se dobija (dešifrovanje) čitanjem po vrstama matrice.
8
Sistem ima slabosti. Dimenzije matrice moraju da budu odabrane tako da proizvod broja kolona i vrsta bude veći ili jednak dužini poruke. Ukoliko otvoreni tekst ima 12 slova dimenzije matrice mogu da budu 2 h 6, 6 h 2, 3 h 4 ili 4 h 3. Trudi zaista nema puno posla. Prostor ključeva se smanjuje, pa i posao pretrage.
Da bi se šifra usavršila i otežala potpuna pretraga ključa, uvedeno je novo pravilo na osnovu kog se čitaju kolone matrice prilikom definisanja šifrata.
Neka je poruka koja treba da se šifruje: CRYPTOISFUN. Na poruku će biti dopisano još jedno slovo kako bi mogli da odaberemo matricu odgovarajuće dimenzije: CRYPTOISFUNH. Poruka sada ima 12 slova i moguće je odabrati matricu dimenzija 3h4. U matricu se poruka upisuje na isti način kao i u prethodnom primeru. Potrebno je odabrati ključnu reč koja ima onoliko različitih slova koliko matrica ima kolona. Ključna reč treba da se lako pamti i da ostane tajna dostupna samo Alisi i Bobu. Neka je odabrana ključna reč MATH. Slovo iz ključne reči koje se prvo pojavljuje u abecedi dobija vrednost 1, sledeće slovo vrednost 2 itd. Na taj način se ključna reč može predstaviti kao 3142.
Slika 2.4 Izbor ključne reči
Da bi se dobio šifrat podaci iz matrice se čitaju po kolonama, ali ne redom s leva na desno, već na način koji određuje ključna reč. Prvo se čita kolona ispod slova A, potom kolona ispod slova N, ... Šifrat je ROUPSXCTFYIN
U postupku dešifrovanja se dobijeni šifrat upisuje po kolonama u matricu, vodeći računa da se prvo upisuju podaci u kolonu koja ima oznaku 1 potom u kolonu za oznakom 2,...
U ovom postupku ključ predstavljaju dve vrednosti: dimenzija matrice i ključna reč. Pred Trudi se postavlja složeniji posao. Međutim da li Trudi ipak može da nadmudri Alisu i Boba?
Primer: Neka je Trudi došla do šifrata: VOESA IVENE MRTNL EANGE WTNIM HTMLL ADLTR NISHO DWOEH
Kako može da ga analizira? Prvo je potrebno da se odredi dužina šifrata, dobija se vrednost 45. Sledi da je proizvod dimenzija matrice n h m=45. Matrica sa 45 elementa može da ima neke od sledećih dimenzija: 3h15, 15h3, 5h9 i 9h5.
Na Trudi je proba sve moguće vrednosti, a potom da za svaku matricu proba sve moguće permutacije kolona (m!).
9
Pretpostavimo da je Trudi pogodila dimenzije matrice (9h5), postoji li skraćeni napad koji će Trudi olakšati posao? Trudi će upisati šifrat u matricu:
Slika 2.5
Može li se premeštanjem kolona dobiti smislena reč u prvom redu?. Moguće rešenje je dato na slici 2.6
Slika 2.6
Očigledno je da postoji skraćeni napad! Pretpostave se dimenzije matrice. Probaju se zamene kolona na takav način da se u prvom redu nađe smislena reč. Ukoliko to ne dovede do rezultata, bira se druga dimenzija matrice,....
Zaključak je da šifrat sadrži informacije koje napadaču mogu da budu od pomoći da neka rešenja (ključeve) proglasi više verovatnim od drugih. Na taj način se smanjuje broj ključeva koji se mogu razmatrati kao rešenje i olakšava posao kripto-analitičara.
Zaključci kriptoanalize 1  Potpuna pretraga ključeva je uvek moguće rešenje za Trudi. Ako je prostor ključeva veliki ovaj posao ne može da se završi za prihvatljivo vreme, odnosno verovatanoća uspeha je veoma mala.
Veliki prostor ključeva je potreban uslov za siguran sistem, ali pokazuje se da nije uvek dovoljan uslov.
Šifrat ne bi trebalo da sadrži informacije iz otvorenog teksta koje će kripto-analitičaru olakšati potpunu pretragu ključeva.
10
Dvostruka transpozicija Da bi se šifra poboljšala, moguće je uvesti dve ključne reči kojima će se odrediti pravila za permutovanje kolona (kao i u prethodnom slučaju) i permutovanje redova na sličan način.
Neka je otvoreni tekst: ATTACK AT DAWN.
Ključ šifrovanja predstavljaju:  odabrane dimenzije matrice, 3h5,   pravilo za permutaciju kolona (0 2 1) i  pravilo za permutaciju redova (2 4 0 3 1). Otvoreni tekst se unosi u matricu tako da se redom popunjavaju redovi s leva na desno (stvar dogovora odnosno algoritma). Nakon popunjavanja ,izgled matrice je kao na narednoj slici:
Slika 2.7  Upis otvorenog teksta u matricu pre primene permutacija kolona i redova
Nakon permutacija redova i kolona po definisano pravilu , izgled matrice je:
Slika 2.8
Šifrat se dobija čitanjem vrednosti matrice po redovima, s leva na desno: XTAWXNATTXADAKC.
Prostor ključeva je sada daleko veći nego u prethodnom primeru. Međutim, postavlja se pitanje da li Trudi može da izvede skraćeni napad?
Primer
Pretpostavimo da šifrat sadrži 45 slova i da ga Trudi zna:
ILILWEAHREOMEESANNDDVEGMIERWEHVEMTOSTTAONNTNH
Trudi takođe zna i algoritam šifrovanja ali ne zna ključ. Skup dimenzija matrice u koji se može upisati šifrat je ograničen (proizvod dimenzija mora biti 45). Moguće dimezije matrice su: 3 x 15, 15 x 3, 5 x 9, ili 9 x 5.
Za svaku analiziranu matricu potrebno je probati sve moguće permutacije kolona i redova. Broj permutacija za matricu dimenzija 3 h 15 (ili 15 h 3) je 3! H 5! Što je veće od 7 h 1012, dok je broj permutacija za matricu dimenzija 9 h 5 jednak 9! h 5! Što je veće od 4 h 107. Ovde „!“ predstavlja oznaku za faktorijel. Ukoliko Trudi treba da obavi posao bez pomoći računara, očekuje je ogroman posao.
11
Neka Trudi, u toku analize pretpostavi da su dimenzije matrice 9 h 5. Uneće šifrat u matricu prema pravilima koja su definisana algoritmom dešifrovanja:
Slika 2.9
Trudi može da proba svih 40 miliona permutacija ili da pokuša da nađe lakši put. Posmatrajmo matricu koja je prikazana na slici 2.9, Trudi će probati da permutuje kolone tako da u prvom redu dobije smislenu reč. Broj permutacija kolona je 5! = 120, što je daleko manje od 4 h 107. U slučaju da od svih mogućih permutacija kolona ni jedno ne daje smisleno rešenje, Trudi će nakon 120 pokušaja probati da analizira druge dimenzije matrice. Jedno od mogućih rešenja je dato na slici 2.10.
Slika 2.10
Preostaje da se pronađe odgovarajući redosled redova, ali je to daleko lakše jer je broj prihvatljivih rešenja, na osnovu smislenog sadržaja poruke, veoma mali. Zaključci kriptoanalize 2 Jedna od klasičnih strategija kripto analize i skraćenih napada se zasniva na poznatoj poslovici Podeli (zavadi) pa vladaj.  Na ovaj način Trudi napada samo DEO prostora ključa, što joj bitno olakšava posao. Zbog toga se od kriptografa zahteva pažljiva analiza algoritma šifrovanja i dešifrovanja kako bi se dizajnirao algoritam koji je imun na ovakve tipove napada. I u ovom slučaju šifrat sadrži informacije iz otvorenog teksta koje mogu da olakšaju kripto-analizu.
Šifre zamene Kod šifara zamene, šifrat se dobija tako što se jedno slovo (simbol) otvorenog teksta zamenjuje nekim drugim slovom (simbolom).
Ključ šifrovanja i dešifrovanja je podatak na osnovu kog se definiše pravilo zamene.
12
Pristup odgovara Šenonovom principu konfuzije (o kom će kasnije biti više reči). Ova ideja se koristi i kod savremenih šifarskih sistema.
Šifre zamene se mogu svrstati u nekoliko kategorija:
 Šifre proste zamene  Homofone šifre  Poligramske šifre  Šifre polialfabetske zamene Šifre proste zamene Najpoznatiji predstavnik šifara proste zamene predstavlja Cezarova šifra. Neki istorijski podaci nam govore da se koristila u prvom veku p.n.e.
Algoritam Cezarove šifre je veoma jednostavan. Šifrat se dobija tako što se svako slovo otvorenog teksta od A do W (engleski alfabet) zameni sa slovom koje je za 3 mesta dalje po abecednom redu, a slova X, Y i Z se zamenjuju sa A , B i C, respektivno. Princip je prikazan na slici 2.11
Slika 2.11 Cezarova šifra
Primer:
Neka je otvoreni tekst: FOURSCOREANDSEVENYEARSAGO
Algoritam šifrovanja odnosno ključ je predstavljen na slici 2.12. Po dogovoru se slova otvorenog teksta pišu malim slovima a slova šifrata velikim slovima. Tako, ako u otovrenom tekstu postoji slovo a ono će se u šifratu predstavit kao slovo D, slovo b otvorenog teksta će u šifratu biti zamenjeno sa slovom E i sl.
Slika 2.11
Na osnovu pravila predstavljenih na slici 2.12, šifrovanjem otvorenog teksta, FOURSCOREANDSEVENYEARSAGO, dobija se šifrat:
IRXUVFRUHDAGVHYHABHDUVDIR
Ključ šifrovanja i dešifrovanja je pomeraj za 3 mesta.
13
Dešifrovanje teksta je zasnovano na istom principu, samo u suprotnom pravcu. Potrebno je da se u tabeli 2.12 pronađe (veliko) slovo šifrata i da se odredi pripadajuće (malo) slovo otvorenog teksta. Tako se za šifrat:  VSRQJHEREVTXDUHSDQWU  dobija otvoreni tekst: SPONGEBOBSQUAREPANTS.
Analiza Cezarove šifre Cezarova šifra se može posmatrati na različite načine, ali je jedno od objašnjenja da su ključevi šifrovanja i dešifrovanja isti dok su algoritmi šifrovanja i dešifrovanja različiti. Algoritam šifrovanja je ciklični pomeraj u levo za 3 dok je algoritam dešifrovanja ciklični  pomeraj u desno za 3.
Prostor ključeva je najmanji mogući, postoji samo jedan ključ što svakako algoritam šifrovanja i dešifrovanja  čini izuzetno lošim.
Potrebno je izmeniti algoritam šifrovanja (dešifrovanja) tako da se dobije prihvatljivo veliki broj ključeva, što vodi ka generalizaciji Cezarove šifre. Opšti oblik šifre proste zamene Ključ ne može da se izabere da bude pomeraj za bilo koji broj, ali time se dobija samo 26 mogućih ključeva što je i dalje neprihvatljivo mali prostor ključeva. Mnogo bolje rešenje je da ključ bude bilo koja (slučajna) permutacija od 26 slova. Moguće rešenje je prikazano na slici 2.13.
Slika 2.12
Prvi red predstavlja slova otvorenog teksta, dok drugi red definiše način zamene otvorenog teksta u šifrat. Redosled slova u drugom redu treba da bude slučajan i na taj način se dobija daleko veći prostor ključeva, odnosno broj mogućih ključeva je 26!  288  ≈ 4 1026.
Trudi sada ima daleko veći posao. Za Alisu i Boba se posao takođe komplikuje. Pre slanja šifrovane poruke, potrebno je da Alisa Bobu dostavi ključ. Ključ je tajna i ne može se poslati javnim komunikacionim putem (pismom na primer). Uobičajen način je da se ključ pošalje preko pouzdanog kurira. Jednom dostavljeni ključ može da se koristi naknadno za šifrovanje i dešifrovanje poruka. Postavlja se pitanje da li je dobro istim ključem šifrovati više poruka ili za svaku poruku treba odabrati novi ključ (kasnije će biti analiziran ovaj problem).
Primer:
Trudi treba da dešifruje šifrat, za koji zna da je šifrovan šifrom proste zamene:
PBFPVYFBQXZTYFPBFEQJHDXXQVAPTPQJKTOYQWIPBVWLXTOXBTFXQWAXBVCXQWAXFQJVWLEQNT OZQGGQLFXQWAKVWLXQWAEBIPBFXFQVXGTVJVWLBTPQWAEBFPBFHCVLXBQUFEVWLXGDPEQVPQ GVPPBFTIXPFHXZHVFAGFOTHFEFBQUFTDHZBQPOTHXTYFTODXQHFTDPTOGHFQPBQWAQJJTODXQH FOQPWTBDHHIXQVAPBFZQHCFWP....
14
Prostor ključeva je veoma veliku (≈ 4 1026). Postoji li skraćeni napad?
Trudi treba da uradi sledeću analizu
 Odredi ukupnu dužinu šifrata  Prebroji broj pojavljivanja svakog od slova u tekstu  Odredi frekvenciju pojavljivanja svakog slova, tako što se broj pojavljivanja nekog slova podeli sa ukupnim brojem slova u šifratu.
Dobijene rezultate može da sumira u tabelu
Slika 2.14
U prvom redu su napisana slova šifrata a u drugom broj pojavljivanja pojedinog slova u celom šifratu
Postoje javno dostupne statističke vrednosti frekvencije pojavljivanja pojedinih slova u tekstu određenog tipa (politika, matematika,...). Primer statističkih vrednosti za engleski jezik je dat na slici 2.15
Slika 2.15
Trudi treba da uporedi dobijene rezultate sa očekivanim statističkim vrednostima. Tako, na primer, ukoliko je Trudi izračunala frekvenciju pojavljivanja slova A u šifratu i dobila vrednost 0.13 najverovatnije je da slovo A treba dešifrovati kao slovo e (vidi sliku 2.15). Posao analize je zahtevan ali daleko manji od potpune pretrage ključeva. Alisa i Bob mogu da se potrude da otežaju posao Trudi, tako što će namerno u otovrenom tekstu izostavljati neka slova ili ih pogrešno pisati, ali to neće sprečiti Trudi da završi analizu. Homofona šifra Homofona šifra predstavlja unapređenje šifre proste zamene. Osnovni nedostatak prethodnog pristupa je mogućnost direktne statističke analize koja uz prihvatljiv napor može dovesti do pronalaska ključa.
Osnovna ideja koja se primenjuje kod homofone šifre je pokušaj da se iz šifrata uklone statističke informacije koje napadaču mogu da pomognu u postupku potpune pretrage ključeva.
15
Neka se otvoreni tekst sastoji od simbola kao i u prethodnom primeru (skup od 26 slova). Algoritam šifrovanja treba definisati tako da šifrat sadrži više od 26 znakova i to na takav način da se onemogući statistička analiza.  Većina slova iz otvorenog  teksta se u šifratu zamenjuju jednoznačno kao i u prethodnom primeru. Međutim slova koja imaju izraženu frekvenciju treba šifrovati tako da se, u zavisnosti od definisanog pravila, u šifratu menjaju na barem dva načina.
Primer
Može se definisati pravilo da otovreni tekst sadrži 26 različitih simbola (slova a-z) a da šifrat sadrži 32 simbola (00, 01, ..., 31) što je za 5 više od broja simbola otvorenog teksta. Pravilo šifrovanja predstavljeno je na slici 2.16.
Slika 2.16
Svaki broj u šifratu jednoznačno određuje slovo otvorenog teksta, ali slova otvorenog teksta. teksta: A, E, N, O, R i T mogu da budu šifrovana na dva načina (sa dva različita broja)
Dodatni znakovi služe za uvođenje elemenata slučajnosti, i narušavanje statističkih informacija koje se nalaze u šifratu
Za otvoreni tekst: TEETN (ponovljena slova E i T)
Dobijeni šifrat je: 24 27 13 08 31
Ovako projektovani algoritmi su otporniji na statističke napade. Ipak, ostaju ranjivi na napade poznatog (dela) otvorenog teksta. Kripto analiza 3 Statističkom analizom se može doći do informacija o ključu.
Šifrat bi trebalo da prikrije statističke osobine otvorenog teksta  šifrat treba da ima osobine slučajnog niza.
Postizanje slučajnosti je često veoma složen posao.
Teško je precizno definisati slučajnost (entropiju).
Kriptografi ulažu velike napore da se uspešno nose sa napadima zasnovanim na statistici.



Klasična kriptografija deo II
2014.

2
Sadržaj Poligramske šifre .....................................................................................................................3 Plejfer šifra ..........................................................................................................................3 Hilova šifra ............................................................................................................................3 Primer Hilove šifre ..............................................................................................................4 Kripto analiza 4 .......................................................................................................................5 Šifre polialfabetske zamene ..................................................................................................5 Vižnerova šifra .....................................................................................................................6 Indeks koincidencije .............................................................................................................7 Savršena sigurnost ........................................................................................................................ 10 Bezuslovno sigurna šifra ........................................................................................................ 10 OTR šifra ............................................................................................................................... 10 Dokaz sigurnosti OTR šifre .................................................................................................. 12 Kodne knjige................................................................................................................................ 14

3
Poligramske šifre Kod poligramskih šifara, otvoreni tekst se deli na blokove simbola jednake dužine, a potom se svaki blok šifruje kao jedna celina. Jedna od jednostavnih metoda šifrovanja je da se otovreni tekst podeli na blokove od tri slova (trigrame), a potom se za svaka moguća kombinacija od tri slova menja sa unapred definisanim slogom. Na primer “ABA” se šifruje sa “RTQ”, “ABB” se šifruje sa “SLL”, itd.
Najznačajniji predstavnici poligramskih šifara su   Plejfer (Playfair) šifra  Hilova (Hill) šifra Plejfer šifra Otkrivena je polovinom 19. veka, ali ime nije dobila po pronalazaču već po lordu Plejferu koji se zalagao za njenu upotrebu. Šifruju se po dva slova zajedno, umesto jednog što je slučaj kod šifara zamene. Pokazalo se da je ova šifra mnogo otpornija na frekvencijsku analizu. Frekvencijska analiza je i ovde moguća ali na veoma dugim porukama. Koristili su je Britanci u Prvom svetskom ratu, a povremeno i u Drugom svetskom ratu, za poruke sa malim vremenom tajnosti, jer je u to vreme bilo poznato da postoje efikasni napadi na ovu šifru. Hilova šifra Hilova šifra je šifra poligramske zamene koja koristi blokove od tri i više simbola koje nezavisno šifruje. Zasnovana je na linearnim jednačinama i trebalo je da unapredi šifre proste zamene. Šifrovanje Potrebno je svako slovo alfabeta predstaviti brojem od 0 do 25 (Na primer, A = 1, B = 1, ..., Z = 25, mada su moguća i druga označavanja).  Otvoreni tekst se potom predstavi nizom brojeva i podeli na blokove dužine n (n predstavlja broj slova u jednom bloku).  Svaki blok otvorenog teksta, nakon zamene slova brojevima, se označi kao p0, p1, p2, …, pi, ...  gde i predstavlja redni broj bloka. Svaki blok pi sadrži n brojeva. Svaki blok pi se potom zapisuje u jedan vektor dimenzija n h 1. Šifrat jednog bloka, si, se dobija množenjem po modulu 26, invertibilne matrice A dimenzija n h n, sa prethodno definisanim vektorom pi. Šifrat, si, je vektor dimenzija n h 1.
ci = A
pi (mod 26) Matrica A predstavlja ključ šifrovanja, i njenu vrednost je potrebno odabrati na slučajan način iz skupa invetibilnih matrica dimenzija n h n.
4
Dešifrovanje Postupak dešifrovanja je veoma sličan. Potrebno je vrednost inverzne matrice A, (A -1), pomnožiti po modulu 26 sa blokom šifrata. ri = A-1 si (mod 26) Napomena: Može se koristiti bilo koji alfabet, samo se u tom slučaju ne računa po modulu 26, već po modulu koji je jednak broju slova izabranog alfabeta. Na primer, srpska azbuka ima 30 slova, pa bi se računalo po modulu 30. Izbor matrice A mora biti takav da postoji inverzna matrica, odnosno potrebno je da je determinanta matrice A bude različita od nule. Postoje i dodatna ograničenja oko vrednosti determinante u odnosu na vrednost modula, ali se ona mogu izbeći ukoliko se za vrednost modula uzme prost broj. To znači da se bilo kom alfabetu treba dodati potreban broj simbola kao bi njihov ukupan broj bio prost. Primer Hilove šifre Neka je otvoreni tekst: MEET ME HERE što je nakon dodele brojeva  (12, 4, 4, 19, 12, 4, 7, 4, 17, 4) Izabrana je dužina bloka n=2 (grupišu se po dva slova, odnosno broja). Formiraju se vektori koji sadrže po 2 broja:
Ključ šifrovanja predstavlja (invertibilna) matrica A dimezija 2 h 2:
Nakon šifrovanja prvog bloka dobija se šifrat prvog bloka:
 0 22 13 12 316 4 mod26 11 5 4 152 22 c                        
Na sličan način dobijaju se šifrati svih blokova
Šifrovana poruka ima oblik:
(4, 22, 23, 9, 4, 22, 24, 19, 10, 25) = EWXJEWYTKZ
Nažalost, Hilova šifra je ranjiva na napade poznatog (dela) otvorenog teksta prvenstveno zato što je linearna. Ako pretpostavimo da Trudi u potpunosti poznaje algoritam, dimenzije matrice A i potreban broj blokova šifrata, onda joj je potrebno da sazna samo odgovarajući broj
5
blokova otvorenog teksta da bi došla do ključa. To nije lak ali ni nemoguć posao. Poznavanjem p0, p1, p2, …, pi, i s0, s1, s2, …, si , iz ci = A pi (mod 26) sledi ci pi-1 (mod 26)= A  Ako postoji inverzna vrednost pi-1 do ključa (matrice A) se može doći na lak način. Mada je iz prethodnog primera očigledno da se sigurnost šifrata ne može postići množenjem matrica, ovaj postupak se ipak koristi u realizaciji nekih segmenata  savremenih algoritama šifrovanja (kao što je slučajaj sa operacijom MixColumns kod AEЅ algoritma, o kom će kasnije biti reči ), jer se na ovaj način obezbeđuje uvođenje difuzije, donosno velike zavisnosti svakog bita u jednom bloku šifrata od svakog bita u pripadajućem bloku otvorenog teksta. Kripto analiza 4 Linearne šifre imaju slabosti jer predstavljaju problem koji se relativno lako jednoznačno rešava. Sledi zaključak da šifarski algoritmi treba da sadrže nelinearne funkcije na kojima će počivati sigurnost. Pri tome sam algoritam može da sadrži linearne funkcije zbog njihovih korisnih osobina, ali algoritam ne sme u potpunosti da bude linearan. Šifre polialfabetske zamene Šifre polialfabetske zamene (polyalphabetic cipher) su slične šiframa proste zamene, ali postoji više alfabeta koji se koriste za šifrovanje. Uopšteno gledano, za svako slovo otvorenog teksta bi se moglo koristiti drugo pravilo šifrovanja. U praksi se obično odredi određeni broj slova (ili simbola) otvorenog teksta koji se šifruje po jednom pravilu.
Primer: Neka postoje tri alfabeta:
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 J I C A X S E Y V D K W B Q T Z R H F M P N U L G O
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
A X S D K W Z R H P N U L G O J I C E Y V B Q T F M
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 A S Y D W Q Z H M N L O J C X E V K B T R F P U G I Slika 2.17
Otvoreni tekst: HELLO WORLD se šifruje tako da se prvo slovo šifruje pomoću pravila definisanom prvim alfabetom (tabelom),drugo slovo drugim alfabetom,
6
treće slovo trećim alfabetom, potom četvrto slovo prvim alfabetom , peto slovo drugim alfabetom,... Dobijeni šifrat je: YKOWOPTCOA Broj alfabeta koji se koriste za šifrovanje može da bude jednak broju slova otvorenog teksta i u tom slučaju se za svako slovo otovrenog teksta primenjuje novo pravilo šifrovanja ili drugi ključ. Najznačajniji prdstavnik polialfabetske šifre je Vižnerova šifra Vižnerova šifra Vižnerova šifra je dobila ime po svom autoru francuskom diplomati (Blaise de Vigenere, 1523-1596). U suštini predstavlja unapređenje Cezarove šifre. Umesto da se svako slovo otovorenog teksta pomera za 3 mesta u desno (ciklično pomeranje), koristi se više alfabeta koji slovo otvorenog teksta pomeraju za m mesta u desno (m može da bude bilo koji broj iz skupa 0 do 25). Ukoliko alfabeta ima manje od slova otvorenog teksta, alfabeti se periodično ponavljaju, kao u prethodnom primeru.  Može se definisati skup od m brojeva (vrednosti od 0 do 25) i svaki od njih predstavlja broj cikličnih pomeraja u desno. Skup ovih brojeva predstavlja ključ šifrovanja. Ključ: K = (k0, k1,…, km-1)  Šifrovanje Slično kao kod Cezarove šifre, slova otvorenog teksta se šifruju tako da se ciklično pomeraju u desno za ki mesta, gde je indeks i= 0, 1, 2, ..., m-1
šifrat 1. slova otvorenog teksta je: c0 = p0 + k0 (mod 26)  šifrat 2. slova otvorenog teksta je: c1 = p1 + k1 (mod 26)  šifrat 3. slova otvorenog teksta je: c2 = p2 + k2 (mod 26)  ... šifrat m. slova otvorenog teksta je: cm-1 = pm-1 + km-1 (mod 26)  šifrat m+1. slova otvorenog teksta je: cm = pm + k0 (mod 26)
šifrat i. slova otvorenog teksta je: ci = pi + k(i mod m) (mod 26)  Dešifrovanje Postupak dešifrovanja je, takođe, sličan: ri = si - k(i mod m) (mod 26)  Vižnerova šifra je otporna na napade statističke (frekvencijske) analize, što se pokakzalo kao slabost šifra zamene. Ista slova otvorenog teksta mogu da se šifruju na različite načine i tako se gube podaci o frekvenciji pojavljivanja koji mogu da se upotrebe za klasičnu frekvencijsku analizu.
7
Ako Trudi poseduje šifrat:  LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKV Šta može da uradi?  Potrebno je da: 1. Pogodi dužinu ključa m 2. Odredi pozicije u šifratu  {1, m+1, 2m+1, 3m+1,…} {2, m+2, 2m+2, 3m+2,…} ... {m-1, m+m-1, 2m+m-1,…} 3. Razdvoji šifrat na slogove od po m (na primer 6) slova
LIVITC SWPIYV EWHEVS RIQMXL EYVEOI EWHRXE XIPFEM VEWHKV 4. Svaki slog upiše kao jedan red matrice. Slova koja se nalaze u jednoj koloni predstavljaju šifrat koji je dobijen istim ključem (svaka kolona je šifrovana jednim od  ključeva)
Slika 2.18 Upis šifrata u matricu
5. Uradi frekvencijsku analizu svake kolone pojedinačno, na isti način na koji se to radi kod šifara zamene.
Preostaje da se reši kako Trudi može da nađe broj ključeva m?
Mada su gotovo 300 godina napori kriptoanalitičara ostali bez uspeha, moguće je izvesti uspešan napad koji se zasniva na takozvanom Indeksu koincidencije. Indeks koincidencije Kolika je verovatnoća da se nasumično izaberu dva slova iz (Vižnerovog) šifrata i da ta dva slova budu ista? Da bi odgovorili na to pitanje, potrebno je da preciznije definišemo problem. Neka u šifratu mogu da se nalaze slova A, V, C, D, ..., Z (ukupno 26) i neka je prebrojavanjem slova u šifratu ustanovljeno da postoji n0 slova A, n1 slova B, ... i n25 slova Z. Ukupan broj slova u šifratu je n = n0 + n1 + ... + n25
8
Verovatnoća da se na slučajan način izabere jedno slovo A iz šifrata je jednaka 0 n n
.
Verovatnoća da se u dva uzastopna izvlačenja oba puta izaberu slova A je:  0 0 1 1 n n n n   Slično, verovatnoća da se u dva uzastopna izvlačenja oba puta izaberu slova V je   1 1 1 1 n n n n  
Odavde sledi da je verovatnoća da se u dva uzastopna izvlačenja oba puta izaberu bilo koja dva ista slova:
 0 0 25 25 1 1 1 1 1 ... 1 1 1 n n n n n n I n n n n n n          
Veličina I se naziva indeks koincidencije. Vrednost indeksa koincidencije se dobija iz vrednosti n, n0, n1,    i n25 koji se mogu jednostavno dobiti iz šifrata. Indeks koincidencije se može predstaviti i na drugi način:     25 25 2 2 25 25 20 0 2 2 0 0 1 1 i i i i i i i i i n n n n I p n n n n              
gde i p predstavalja verovatnoću pojavljivanja nekog slova u šifratu. Za otvoreni tekst (napisan na engleskom jeziku) pokazuje se da je verovatnoća, da se na slučajan način dva puta uzastopno izaberu bilo koja dva slova, približno jednaka:
 2 2 2 2 0 1 2 25... 0.065 p p p p     
Kako se statističke osobine ne menjaju primenom šifre proste zamene sledi da će indeks koincidencije kod šifrata proste zamene biti 0.065 I 
S druge strane Vižnerova šifra, za ključ dovoljno velike dužine, ima za cilj da postigne da je verovatnoća pojavljivanja svakog slova u šifratu podjednako verovatna, odnosno da je
 0 1 25... 1/ 26 p p p    
U ovom slučaju indeks koincidencije ima vrednost
 2 2 2 2 0 1 2 25... 0.03846 p p p p     
Kako iskoristiti ove rezultate za određivanje dužine ključa Vižnerove šifre? Pretpostavimo da je šifrat dužine n a ključ dužine k. Upišemo šifrat u matricu sa n/k redova i k vrsta (dmenzije n/k x k), videti sliku 2.18.
9
Iz matrice se nasumično izaberu dva slova šifrata, moguća su dva slučaja:
 Oba slova su iz iste kolone (šifrat u okviru jedne kolone je nastao istom šifrom proste zamene)  Slova su iz različitih kolona (pojednaka verovatnoća pojavljivanja svakog slova).
Kolika je verovatnoća da su dva slova ista i iz iste kolone?  Odgovor: Izabere se jedno slovo (na taj način je definisana jedna kolona), u jednoj koloni ima n/k slova. Nakon izbora jednog slova, u šifratu je ostalo n-1 slovo, a u izabranoj koloni n/k-1 slovo. Sledi da je verovatnoća da je drugo izabrano slovo iz iste kolone:
/ 1 1 n k n  
Kako oba slova pripadaju istoj koloni (šifra proste zamene) verovatnoća da su oba slova ista je:
/ 1
0.065
1
n k n


Kolika je verovatnoća da su 2 izabrana slova ista I iz različitih kolona? Odabere se jedno slovo (određena je kolona). Broj slova koja se nalaze u svim ostalim kolonama je / n n k  . Vrovatnoća da je drugo slovo iz različite kolone je:
/ 1 n n k n  
Kako oba slova ne pripadaju istoj koloni, verovatnoća da su slova ista je 0.03846: Odavde sledi da je verovatnoća da su izabrana dva ista slova i da ne pripadaju istoj koloni:
/
0.03846
1 n n k n  
Konačno odgovor: Verovatnoća da se slučajnim izborom dobiju dva ista slova iz šifrata je jednaka zbiru:
/ 1 / 0.065 0.03846 1 1 n k n n k
I
n n      
Odavde se može izraziti vrednost k, odnosno može se izračunati dužina ključa:
  
0.027 1 0.065 0.03846 n
k
n I n

  
10
Savršena sigurnost Analizom klasičnih šifara se pokazalo da one imaju slabosti koje se mogu iskoristiti za efikasne napade. Nameće se pitanje da li postoji sigurna šifra, ali pre toga treba definisati sigurnost šifarskog sistema.
Ključna su dva pojma:
 Računska ili praktična sigurnost i  Bezuslovna sigurnost
Za šifrski sistem se kaže da je računski siguran (computationally secure) ako cena „razbijanja″ šifrata prevazilazi vrednost šifrovane informacije ili ako je vreme potrebno za „razbijanje“ šifrata duže od vremena u kom informacija treba da bude tajna. Ostaje problem kako to odrediti, na koji način je moguće proceniti resurse kojima raspolaže druga strana?
Šifarski sistem je Bezuslovno siguran ako ne može da bude „razbijen″ ni uz primenu neograničenih resursa, ljudstva i vremena.
Šifre koje su prethodno pominjane imaju slabosti – „razbijene″ su. Neke od njih su bile „sigurne″ u jednom delu vremena kada su korišćene. Međutim razvojem nauke i tehnologije pokazalo se da su osetljive na neke od napada. Bezuslovno sigurna šifra Pod bezuslovno sigurnom šifrom se smatra ona šifra koja ima osobinu da se ne može doći do otvorenog teksta iz šifrata bez poznavanja ključa, čak ni potpunom pretragom ključeva. Na prvi pogled može da deluje zbunjujuće, jer se potpunom pretragom (ne ograničavajući vreme pretrage) sigurno može doći do ključa. Međutim, razmotrimo sledeći primer.
Neka šifrat ima 100 slova. Potpunom pretragom ključeva i dešifrovanjem sa svakim od potencijalnih ključeva može da se dobije veliki broj besmislenih poruka (ti ključevi će biti odbačeni) ali i relativno veliki broj smislenih poruka (potencijalnih otvorenih tekstova). Sa sto slova je moguće napisati zaista veliki broj smislenih poruka. Ako su sve te pruke podjednako verovatne, onda napadač nema načina da odredi koja je od njih prava.  Primer bezuslovno sigurne šifre je One-time Pad (OTR) šifra OTR šifra Razmotrimo OTR šifru na primeru. Neka se koristi alfabet koji ima samo 8 slova  (e, h, i, k, l, r, s, t) i neka se svako slovo koduje sa 3 bita (e = 000, h = 001, i = 010, k = 011, …, t = 111). Izbor koda nije od presudne važnosti niti treba da predstavlja tajnu. Alisa je špijun i treba da šifruje poruku: heilhitler.
11
Prvo poruku predstavlja binarnim nizom na osnovu definisanog koda. Zatim joj je potreban drugi binarni niz iste dužine kao i poruka koji će predstavljati ključ. Ključ treba da ima osobine slučajnog niza (objašnjenje sledi). Postupak šifrovanja je veoma jednostavan: svaki bit otvorenog teksta se sabira po modulu 2 (XOR) sa po jednim bitom ključa
i i i c p k  
Postupak dešifrovanja je takođe jednostavan, potrebno je sabrati svaki bit šifrata sa istim bitom ključa koji je korišćen pri šifrovanju:
i i i p c k   Postupak šifrovanja je predstavljen na narednoj slici:
Slika 2.19 OTR šifrovanje
Da bi od šifrata (srlhssthsr odnosno 110101100001110110111001110101) dobili otvoreni tekst, potrebno je šifrat sabrati po modulu 2 sa istim ključem (111101110101111100000101110000). Postupak dešifrovanja je prikazan na narednoj slici
Slika 2.20 OTR dešifrovanje
Šta će se desiti ako Trudi pokuša da proba sve moguće ključeve? Posmatrajmo primer kada se odabere neki drugi ključ (namerno izabran da bi rezultat bio očigledan)
12
Slika 2.21 OTR dešifrovanje drugim ključem
Trudi je dobila poruku koja je smislena. Daljom pretragom, Trudi će sigurno doći i do prave poruke. Ali, ukoliko ona ne može da odredi koja je od poruka verovatnija onda ne može da zna koja je poruka prava. Kako možemo da tvrdimo da OTR ne može da se „razbije” ? Sigurnost se zasniva na slučajnosti ključa! Teško je definisati pojam slučajnosti, nema egzaktne definicije. Sa kriptografskog stanovišta, zahtevaju se 2 osnovna svojstva binarnog slučajnog ključa (ima ih više):  Nepredvidivost:  Nezavisno od broja bita (ključa) koji su poznati, verovatnoća pogađanja sledećeg bita nije veća od ½. Verovatnoća da sledeći bit bude 1 ili 0 tačno je jednaka ½.  Balansiranost: Broj  "1" i "0" mora biti približno jednak, u nizu dovoljno velike dužine. Dokaz sigurnosti OTR šifre Ako je ključ slučajni binarni niz, onda je verovatnoća da bilo koji bit ključa ima vrednost logičke jedinice jednaka verovatnoći da taj bit ima vrednost logičke nule i iznosi ½.
Otvoreni tekst ima statističke osobine i verovatnoća pojave logičkih jedinica i nula nije jednaka. Ako je verovatnoća pojave logičke nule u otvorenom tekstu h onda verovatnoća pojave logičke jedinice mora biti (1-h), gde je 0 1 x   .
Posmatrajmo tabelu koja definiše moguće vrednosti otvorenog teksta i ključa koje nakon sabiranja po modulu 2 daju šifrat
Prvi red: Ako bit otvorenog teksta ima vrednost 0 (verovatnoća je h) i bit ključa ima vrednost 0 (verovatnoća ½) onda će šifrat (dobijen sabiranjem po modulu 2 bita otvorenog teksta i bita ključa) imati vrednost 0 sa verovatnoćom ½h.
13
Drugi red: Ako bit otvorenog teksta ima vrednost 0 (verovatnoća je h) i bit ključa ima vrednost 1 (verovatnoća ½) onda će šifrat imati vrednost 1 sa verovatnoćom ½h.
Treći red: Ako bit otvorenog teksta ima vrednost 1 (verovatnoća je 1-h) i bit ključa ima vrednost 0 (verovatnoća ½) onda će šifrat imati vrednost 1 sa verovatnoćom ½(1-h).
Četvrti red: Ako bit otvorenog teksta ima vrednost 1 (verovatnoća je 1-h) i bit ključa ima vrednost 1 (verovatnoća ½) onda će šifrat  imati vrednost 1 sa verovatnoćom ½(1-h).
Verovatnoća da šifrat ima vrednost 0 dobija se sabiranjem verovatnoća šifrata u prvom i četvrtom redu i iznosi ½h +½(1-h)= ½
Verovatnoća da šifrat ima vrednost 1 dobija se sabiranjem verovatnoća šifrata u drugom i trećem redu i iznosi ½h +½(1-h)= ½
Očigledno je da šifrat ima osobine slučajnog niza. Zašto je to važno? Odavde sledi da u šifrat nisu prenesene statističke osobine koje postoje u otvorenom tekstu! Drugim rečima, ukoliko ne postoje statističke osobine otvorenog teksta u šifratu, onda ih nije moguće iskoristiti za neki od skraćenih oblika napada. Da bi ova tvrdnja bila tačna, neophodno je da ključ ima osobine slučajnog niza!
Pored toga, veoma je bitno da se isti ključ ne koristi za šifrovanje više poruka. Jedan ključ je moguće koristiti samo za jedno šifrovanje!
Razmotrimo slučaj kada se isti ključ K koristi za šifrovanje dve različite poruke     ( 1 2 , P P )
1 1 2 2 ; C P K C P K    
Trudi će lako saznati oba šifrata ( 1 2 , C C ). Ako ih sabere po modulu 2, sledi
1 2 1 2 1 2 1 2 C C P K P K P P K K P P            . Trudi ima podatak koji ne zavisi od ključa. Napad tipa poznavanja (dela) otovrenog teksta direktno dovodi do dešifrovanja druge poruke.
Ako je OTR šifra dokazivo sigurna, zašto se ne koristi samo ona?
OTR šifra ima svoju primenu i to za najviše nivoe sigurnosti ali se pokazala kao nepraktična za primenu u komercijalnim uslovima. Razlozi su sledeći:
Ključ mora da bude slučajan. Postupak genrisanja slučajnih vrednosti nije jednostavan, zahteva postojanje fizičkog procesa koji sadrži elemente slučajnosti (merenje vremena polurspada radioaktivnog elementa, uzorkovanje šuma diode i sl). Ovi izvori su po pravilu spori, odnosno potrebno je dosta vremena da se izgeneriše dovoljno dugačak niz slučajnih bita. Pored toga izvori slučajnosti treba da se stalno
14
testiraju jer zbog uticaja okoline, starenja i sl. mogu da promene svoje karakteristike.
Drugi veliki problem je distribucija generisanog ključa drugoj strani u komunikaciji. Ovaj problem u komercijalnom svetu postaje praktično nerešiv. Kodne knjige Kodne knjige predstavljaju još jedan od primera šifrovanja koji je u bliskoj prošlosti (Drugi svetski rat) ima veliku primenu. Osnovna ideja je prilično jednostavna. Definiše se skup reči ili fraza koje mogu da se koriste u komunikaciji. Potom se svakoj reči dodeli odgovarajući brojčani kod.
Primer:
Slika 2.22 Primer kodne knjige
Za šifrovanje je potrebno da postoji tabela sa dve kolone (slična onoj prokazanoj na slici 2.22), a potom se svaka reč menja definisanim nizom brojeva. Dešifrovanje je inverzni proces.
Kodne knjige su podložne statističkoj analizi, slično kao i šifre zamene, ali je postupak daleko teži i zahteva veliku dužinu šifrata.
Kodna knjiga predstavlja ključ šifrovanja i sigurnost šifarskog sistema počiva na (fizičkoj) sigurnosti kodne knjige. Obzirom da se ključ menja nakon definisanog vremena, kodna knjiga takođe treba da se menja. Međutim, u ratnom okruženju to nije jednostavno i to je dovelo do ideje uvođenja aditivnih (pomoćnih) kodnih knjiga.
Aditivna kodna knjiga je dodatna knjiga koja sadrži mnogo slučajnih brojeva. Sekvence slučajnih brojeva se sabiraju sa kodnim rečima i formiraju konačni šifrat.
Slika 2.23 Aditivne kodne knjige
Početna pozicija iz aditivne knjige treba da se dogovori između pošiljaoca i primaoca. Početno mesto u kodnoj knjizi, određuje pošiljalac. Početno mesto može
15
da se šalje nezaštićeno („otvoreno") uz šifrat jer je potrebno za postupak dešifrovanja.
Početno mesto se naziva: indikator poruke - message indicator (MI). Kod savremenih šifara se korsiti ovaj postiupak a indikator poruke se često naziva inicijalizacioni vektor (IV).


Simetrični kripto-sistemi
priredio: dr Zoran Banjac
2014.

2
Sadržaj Uvod ...................................................................................................................................................3 Algoritmi sa simetričnim ključem ................................................................................................3 Sekvencijalni algoritmi ...........................................................................................................4 Realizacija generatora pseudo-slučajnih vrednost upotrebom linearnih pomeračkih registara ...................................................................................................................................6 A5/1 sekvencijalni algoritam .................................................................................................8 Sekvencijalni algoritmi: sažetak ..........................................................................................9 Blokovske šifre .........................................................................................................................9 Fejstel šifra ......................................................................................................................... 10
DES - Data Encryption Standard ................................................................................................. 11 Dvostruki DES algoritam ........................................................................................................ 14 Trostuki DES algoritam .......................................................................................................... 15 AEЅ algoritam.......................................................................................................................... 15 Režimi rada blokovskih šifara .......................................................................................... 18 Integritet ................................................................................................................................... 21
MAC  Message Authentication Code .......................................................................................... 21

3
Uvod U prethodnoj lekciji su predstavljeni klasični kriptografski algoritmi koji spadaju u grupu algoritama sa simetričnim ključem, odnosno koriste isti ključ za šifrovanje i dešifrovanje. Iz istorijskih razloga, otvoreni tekst i šifrat su se, uglavnom, predstavljali pomoću slova, a proces šifrovanja i dešifrovanja se često obavljao ručno. Napretkom u nauci i tehnologiji, pojavile su se mogućnosti uvođenja prvo mehaničkih a potom i elektromehaničkih uređaja koji su ubrzali procese obrade. Tokom Drugog svetskog rata i po njegovom okončanju, uvedeni su računari u kripto-analizu. Odgovor kriptografa je usledio veoma brzo, za šifrovanje i dešifrovanje poruka su počeli da koriste računare.
Napomena: U daljim razmatranjima će se pod pojmom računar podrazumevati računari opšte namene (mainframe, PC, ...) i namenski projektovani uređaji koji koriste procesorsku tehnologiju. Obuhvaćene su softverske i hardverske realizacije algoritma.
Zbog primene računara, otvoreni tekst koji treba da se šifruje, prvo treba predstaviti u binarnom obliku. Postupak zapisa otvorenog teksta u obliku binarnog niza se naziva kodovanje. Mogu se koristiti neki od standardnih kodova kao što su ASCII i UNICODE, ili namenski projektovani kodovi. Pri tome treba naglasiti da način kodovanja ne predstavlja tajnu.
Zadatak algoritama šifrovanja je da transformiše nizove bitova (koji nose informaciju iz otvorenog teksta) u novi binarni niz na takav način da neovlašćene strane analizom šifrata ne mogu da dođu do informacija koje postoje u otvorenom tekstu.
Prelazak na nove tehnologije, u suštini, nije bitno uticao na koncepte koji su se koristili u klasičnoj kriptografiji. I dalje se koriste postupci transpozicije i zamene. Međutim, sada su se mogle iskoristiti brzina i tačnost računara. Omogućena je realizacija daleko složenijih algoritama u odnosu na one koji se mogu realizovati na mehaničkim ili elektromehaničkim uređajima.
Kripto sistemi mogu da se podelite na:  Kripto sisteme sa simetričnim ključem. Koristi se isti ključ za šifrovanje i dešifrovanje.  Kripto sistema sa javnim i tajnim ključem. Koriste se dva ključa, javni ključ za šifrovanje i tajni ključ za dešifrovanje
Algoritmi sa simetričnim ključem Algoritmi sa simetričnim ključem mogu da se posmatraju kriz dve grupe:  Sekvencijalni algoritmi  Blokovski algoritmi
Sekvencijalni (stream) algoritmi u postupku šifrovanja i dešifrovanja deluju u jednom trenutku na jedan bit (ponekad bajt) otvorenog teksta ili šifrata. Pri tome u postupku šifrovanja rezultat transformacije jednog bita otvorenog teksta je potpuno nezavisan od
4
vrednosti ostatka otvorenog teksta. Osnovna jedinica otvorenog teksta može biti i bajt (umesto bita), a razlozi su istorijski jer se na taj način može predstaviti jedno slovo.
Sekvencijalni algoritmi su nalik na one-time pad algoritmu, ali koriste ključ koji ima karakteristike pseudoslučajnosti.
Kod blokovskih algoritama se otvoreni tekst, pre šifrovnja, deli na skupine uzastopnih bita određene dužine (64 bita, 128 bita...) koje se nazivaju blokovi. Blokovski algoritam šifrovanja deluje na sve bite unutar bloka, a dobijeni šifrat je po pravilu iste džine kao i blok otvorenog teksta, a poželjno je da vrednost svakog bita šifrata zavisi od vrednosti svih bita bloka otvorenog teksta i svih bita ključa šifrovanja.
Blokovske šifre su zasnovane na konceptu kodnih knjiga. Ključ blokovske šifre određuje kodnu knjigu, a promenom ključa se praktično menja kodna knjiga.
Koriste Ključ – slučajni niz male dužine!
Na osnovu kratkog ključa (i još nekih podataka) obe strane generišu radni ključ (keystream).
Radni ključ se potom koristi kao kod OTR-a
Radni ključ je iste dužine kao poruka. Sekvencijalni algoritmi Jedini, do sada analizirani, algoritam za koji je pokazano da je bezuslovno siguran je onetime pad (OTP) algoritam. Šifrat se dobija tako što se binarna vrednost otvorenog teksta sabira po modulu 2 (XOR) sa slučajnim binarnim nizom koji se naziva ključ šifrovanja:
Šifrat(Otvoreni tekst, Ključ) = Otvoreni tekst  Ključ
gde  predstavlja operaciju sabiranja po modulu 2. Ključ mora da bude slučajan, iste dužine kao i otvoreni tekst, a isti ključ može da se koristi samo za šifrovanje jednog otovrenog teksta. OTP algoritam je, pre svega zbog besuslovne sigurnosti, našao primenu za zaštitu informacija najvišeg stepena tajnosti.
Bez obzira na idealne karakteristike OTP algoritma, postoje nedostaci koji ograničavaju njegovu masovnu praktičnu primenu. Prvi problem je potreba za generisanjem velike količine binarnih nizova koji imaju osobine slučajnositi.
Izvor slučajnosti mora da bude zasnovan na fizičkim pojavama koje sadrže elemente slučajnosti, kao što su radio-aktivni izvor, atmosfeski šum, šum električnih komponenata i sl. Potrebno je potom, primenom odgovarajućih senzora, detektovati slučajne promene i konvetovati ih u binarne (slučajne) vrednosti koje će se koristiti kao ključ u procesu šifrovanja i dešifrovanja.
Otežavajuća okolnost je da izvori slučajnosti mogu da menjaju svoje karakteristike zbog uticaja okoline (temperatura, pritisak, vlažnost, elektro-magnetne smetnje, ...) pa je neophodno stalno testiranje generisanih vrednosti kako bi se potrvrdilo da poseduju
5
očekivane osobine slučajnosti. Nažalost, ne postoje egzaktni testovi i odluke o osobinama slučajnosti se zasnivaju na teoriji verovatnoće i statistike.
Proces generisanja slučajnih borjeva je po pravilu spor, pa to može predstavljati dodatni problem u slučaju da je potrebno da se šifruje velika količina podataka, pogotovo zbog činjenice da dužina ključa mora da bude jednaka dužini poruke i da se ključ može upotrebiti samo jedamput.
Pored toga, da bi se poruka dešifrovala, neophodno je da prijemna strana ima identičan ključ. Obzirom da se ne mogu napraviti dva istovetna generatora slučajnih vrednosti, odnosno da se ista slučajna vrednost ne može generisati na dva mesta, neophodno je rešiti problem sigurne distribucije slučajnih vrednosti (ključeva). Otežavajuća okolnost je i potreba za čestom zamenom ključeva.
Sekvencijalni algoritmi teže da zadrže dobre osobine OTP algoritma, i da pritome prevaziđu navedene nedostatke. Osnovna zamisao je da se slučajni niz zameni pseudoslučajnim.
Sama reč pseudo nas navodi na činjenicu da pseudo-slučajne vrednosti nisu slučajne, barem ne po nekim svojim osobinama. U osnovi, pseudo-slučajne vrednosti predstavljaju izlaz generatora pseudo-slučanih bojeva (Pseudo Random Number Generator -PRNG) koji koriste matematičke funkcije ili tabele sa prethodno izračunatim vrednostima da bi generisali binarne nizove koji imaju neke od osobina slučajnih nizova. Generisani niz dobijen na izlazu generatora pseudo-slučajnih vrednosti, pored matematičkih funkcija je određen i početnim stanjem (initial value - IV) generatora.
Genaratori psseudo-slučajnih brojeva su efikasni, odnosno mogu da generišu mnogo vrednosti za kratko vreme, što je poželjno kada je potrebno da se šifruje velika količina informacija. S druge strane, oni su deterministički što znači da dobijena sekvenca brojeva može da se ponovo generiše na drugom mestu (prijemna strana npr.) ukoliko su poznati detalji oko konstrukcije generatora i početni uslovi (IV). Dobijena sekvenca pseudoslučajnih brojeva je po pravilu periodična, što znači da će se jednom izgenerisane vrednosti, nakon određenog vremena, ponoviti. Kako je jedna od osnovnih karakteristika slučajnih brojeva nepredvidivost, periodičnost je sigurno veoma nepoželjna osobina, jer poznavanjem vrednosti u okviru jedne periode postaju poznate sve naredne vrednosti pseudoslučajnog niza. Zbog toga generatori pseudo-slučajnih vrednosti treba da budu tako projektovani da perioda generisanih vrednosti bude toliko velika da u praktičnoj primeni nikada ne dođe do ponavljanja vrednosti.
Kod sekvencijalnih algoritama se šifrat dobija tako što se binarna vrednost otvorenog teksta sabira po modulu 2 (XOR) sa pseudo slučajnim slučajnim binarnim nizom. Pseudo slučajni binarni niz je, pored konstrukcije generatora, određen i početnim stanjem (IV), koje treba da bude slučajno. IV je, po pravilu, slučajna vrednost mnogo kraća od otvorenog teksta (nekoliko stotina bita) i predstavlja ključ, K, sekvencijalnog algoritma. Generator pseudoslučajnih vrednosti, na osnovu kratkog ključa, K, generiše radni ključ, Ѕ, pseudoslučajnu vrednost, dužine otvorenog teksta. S predstavlja niz bita koji mogu da se predstave kao S = s0 s1 s2... Radni ključ se koristi za šifrovanje poruke (XOR).
6
SekvencijalnaŠifra( K ) = S
Postupak šifrovanja može da se predstavi saČ
Šifrat(Otvoreni tekst, S ) = Otvoreni tekst  S
Ako se šifrat, S, i otvoreni tekst predstave kao nizovi bita S = s0 s1 s2...i R = r0 r1 r2..., onda se postupak šifrovanja može predstaviti kao:
s0 = p0  ѕ0; s1 = p1  ѕ1; s2 = p2  ѕ2;...
a postupak dešifrovanja:
r0 = s0  ѕ0; r1 = s1  ѕ1; r2 = s2  ѕ2;...
Prijemna i predajna strana treba da imaju iste generatore pseudoslučajnih nizova i informaciju o početnom stanju generatora, odnosno moraju da znaju vrednost ključa K, kako bi mogle da generišu identične vrednosti radnog ključa.
Za pravilan rad sekvencijalnog šifarsko sistema neophodno je da se unapred dostavi ključ K, sigurnim putem (na primer kurirom).
Sekvencijalni algoritmi na ovaj način prevazilaze nedostatke OTP algoritma, ali nisu dokazivo sigurni zato što je radni ključ pseudo-slučajan, odnosno periodičan pa je samim tim, u opštem slučaju, predvidiv. Funkcionalnost je ipak moguće postići tako da generisani pseudo-slučajni niz ima veoma veliku periodu, a čestom zamenom ključa K, može dase postigne da se vrednosti radnog ključa nikada ne ponove.
Postoji više rešenja za projektovanje generatora pseudo-slučajnih vrednosti. Jedno od rasprostranjenih rešenja je zasnovano na upotrebi linarnih pomeračkih registara sa povratnom spregom - LPR. Realizacija generatora pseudo-slučajnih vrednost upotrebom linearnih pomeračkih registara Registar predstavlja memorijski element u koji može da se upiše n bita. Linearni pomerački registri sa povratnom spregom treba da obave dve osnovne funkcije:  Funkciju pomeračkog registra (dužine n bita): niz bita koji predstavlja stanje registra se u svakom taktu pomera za jedno mesto u desno.   Funkciju povratne sprege: određuje, na osnovu vrednosti nekih bita u registru, koji bit će se, nakon pomeranja, upisati na mesto prvog bita.
Izlaz iz pomeračkog registra je jedan bit, najčešće krajnji desno. Početno stanje i povratna veza određuju vrednost izlaza.
Taktovanje i povratna sprega je kod linearnih ragistara realizovana na linearan način.
Perioda pomeračkog registra je broj bita izlazne sekvence nakon kog se vrednost izlaznog niza počinje da se ponavlja.
7
Osnovne osobine LPR Pomerački registar dužine n, može da ima 2n-1 različitih početnih stanja (početno stanje ne mogu da budu sve nule). Početno stanje je jedan od parametara koji određuje vrednost izlaznog niza. Drugi bitan parametar je povratna sprega. Pravilnim odabirom povratne sprege može se postići da perioda izlaznog niza bude 2n-1 bita, što je ujedno i perioda maksimalne dužine. Dobijeni izlazni niz ima osobine pseudo-slučajnog niza.
Nažalost, pseudo-slučajni brojevi dobijeni primenom linearnih pomeračkih registara imaju osobine koje nisu poželjne u kriptografiji:  Privih n bita pseudoslučajnih vrednosti (izlaza generatora) su jednake početnom stanju generatora.  Na osnovu poznavanja 2n bita izlaza linearnog generatora (mnogo manje od periode koja iznosi 2n-1 bita) može se rekonstruisati struktura generatora, što znači da protivnička strana može da generiše identičan pseudoslučajni niz. Posledica je linearnosti generatora.
Bez obzira što linearni pomerački registri ne mogu da predstavljaju konačno rešenje za generisanje pseudo-slučajne vrednosti (radnog ključa), oni se koriste kao gradivni elementi složenijih generatora, pa će u daljem tekstu biti predstavljen njihov princip rada.
Primer: Neka je LPR dužine 3, i neka mu je pošetno stanje definisano ključem K: k0k1k2 = 101. U svakom taktu manjaju se stanja registra po parvilu: t=k0  k2 , ki = ki-1, k0 = t. Izlaz iz generatora predstavlja radni ključ Ѕ.
  Slika 3.1 Opis rada linearnog pomeračkog registra
Kako je u sedmom taktu stanje LPR jednako početnom (101) ponoviće se vrednosti na izlazu iz generatora.
Drugačiji izbor povratne sprege može dovesti do toga da perioda bude manje dužine od maksimalne.
Očigledno je da generatori koji koriste LPR daju periodičan izlaz. Upotreba dobijenog radno ključa Ѕ, je prihvatljiva jedino ukoliko je perioda generatora dovoljno velika i ukoliko se koriste dobijene pseudo-slučajne vrednosti jedino unutar jedne periode.
8
Statistički gledano ovako generisan radni ključ ima elemente (pseudo) slučajnosti, ali dovoljno  je poznavanje 2n bita da bi se izračunali naredni biti, što je neprihvatljivo sa stanovišta sigurnosti.
Pametnim kombinovanjem više LPR, uz uvođenje elemenata nelinearnosti mogu se prevazići navedeni problemi kako bi se postigla računska ali ne i bezuslovna sigurnost
Jedan od poznatih sekvencijalnih algoritama koji se koristio u mobilnoj telefoniji je A5/1 algoritam. A5/1 sekvencijalni algoritam A5/1 algoritam je zasnovan na upotrebi pomeračkih registara. Namenjen je za zaštitu podataka na baznm stanicama koje se koriste u mobilnoj telefoniji. Algoritam je čuvan u tajnosti, ali je spletom okolnosti ipak dospeo do javnosti. Nakon javne analize, pokazalo se da ima slabosti.
Slika 3.2 Generator radnog ključa A5/1 algoritma
Genearator se sastoji od 3 pomeračka registra (X, Y i Z). X pomerački registar ima dužinu 19 bita (x0, x1, …,x18), Y dužine 22 bita (y0, y1, …,y21), i Z dužine 23 bita (z0, z1, …, z22). Ključ određuje početno stanje sva tri registra i ima dužinu 64 bita (19+22+23).  Procedura za generisanje radnog ključa Ѕ  Prvo se majoritetnom logikom (dva od tri) odredi vrednost m.
m = maj(x8, y10, z10)
Upoređuje se vrednost bita registra H, na poziciji h8, sa izračunatim m. Ukoliko su vrednosti jednake, treba izračunati vrednost t, i pomeriti sve bite u registru H za jedno mesto u desno, a na mesto h0 se upisuje vrednost t
t = x13  x16  x17  x18
Potom se porede vrednost bita registra Y, na poziciji y10, sa m. Ukoliko su vrednosti jednake računa se vrednost t, pomeraju se svi biti u registru Y za jedno mesto u desno, a na mesto y0 treba upisati vrednost t
t = y20  y21
9
Na sličan način se poredi z10 sa vrednosšću m i ukoliko su jednake, treba izračunati vrednost t, i pomeriti sve bite u registru Z za jedno mesto u desno, a na mesto z0 treba upisati vrednost t
t = z7  z20 z21  z22
Bit radnog ključa se dobija kao zbir po modulu 2 na sledeći način:
x18  y21  z22
Broj bita (perioda) radnog ključa koji se generiše na osnovu 64-bitnog ključa je veoma veliki.
Primer:
Slika 3.3 Generisanje radnog ključa A5/1 algoritma
Na osnovu podataka sa slike m = maj(x8, y10, z10) = maj(1, 0, 1) = 1, odavde sledi da se biti u registrima X i Z pomeraju za jedno mesto u desno i da se računa vrednost t, dok se stanja registra Y ne menjaju. Bit radnog ključa se računa
ѕ= x18  y21 z22 = 0  1  0 = 1
vrednosti bita x18 i z22 iz registara X i Z su uzete nakon pomeranja. Sekvencijalni algoritmi: sažetak Koriste se na mestima na kojima je presudna brzina i rad u realnom vremenu, kao što je zaštita govora, video prenosa i sl. Pogodne su za primenu u lošim uslovima prenosa i namernog ometanja jer nema propagacije greške, odnosno pogrešna vrednost jednog bita šifrata nema uticaja na pravilno dešifrovanje ostalih bita.
U prethodnom periodu su uglavnom realizovani hardverski zbog veće efikasnosti, mada danas mogu potpuno ravnopravno da se realizuju i softverski što je omogućeno napretkom procesorske tehnologije.
Neki autori tvrde da ovaj pristup u šifrovanju nema budućnost, mada još uvek ima značajnu primenu u zaštiti inforamcija. Blokovske šifre Primena blokovskih šifira zahteva podelu otvorenog teksta, R, na nizove bita (blokove) unapred određene dužine. Svaki od blokova Pi, i = 0, 1,2, ... se potom šifruje primenom
10
odgovarajućeg algoritma i kao rezultat nastaje šifrat C = S0 S1 S2...iste dužine, gde Si., i = 0, 1,2, ... predstavljaju blokove šifrata. Postupak dešifrovanja je inverzan, primenjuje se na jedan blok šifrata koji nakon dešifrovanja daje polazni blok otovorenog teksta.
Algoritam šifrovanja je iterativan, blok šifrata se dobija višestrukem primenom određene funkcije na blok otvorenog teksta i međurezultate. Jedna primena funkcije se naziva runda. Ulazni parametri runde su ključ i izlaz iz prethodne runde. Ključ je slučajni niz dužine nekpoliko stotina bita i po pravilu se ne menja u toku šifrovanja jedne poruke. Blokovski algoritmi se najčešće realizuju softverski.
Blokovski algoritmi treba da zadovolje:  Svojstvo difuzije. To znači da poznavanje nekog para blokova otovrenog teksta Pi i njemu pripadajućeg šifrata Si, ne sme da omogući da se iz nekog drugog bloka šifrata Sj odredi blok otvorenog teksta Pj . Takođe, male promene u bloku otovrenog teksta treba da izazovu veoma velike promene u pripadajućem bloku šifrata.  Svojstvo konfuzije. Kod napada potpunom pretragom ključeva, svi ključevi treba da budu podjednako verovatni.  Kompletnost. Svaki bit šifrata treba da bude funkcija svakog bita ključa. Fejstel šifra Fejstel (Feistel) šifra predstavlja tip blokovske šifre, a ne poseban algoritam. Osnovna ideja je sledeća: Podeliti otvoreni tekst na blokove određene dužine (npr. 128 bita).
Slika 3.4 Fejstel šifra
Uzeti jedan blok otovrenog teksta  i podeliti ga na 2 dela, levi i desni i označiti ga sa (L0, R0)
U svakoj rundi i ( i =1,2,...,n), izračunati:
 Li = R i-1
 Ri = L i-1  F(R i-1,Ki)
gde je F funkcija runde a Ki podključ, koji se dobija kombinovanjem bitova ključa K.
11
Šifrat predstavlja izlaz iz poslednje runde (Ln,Rn).
Dešifrovanje predstavlja inverzni postupak.
U opštem slučaju algoritam radi za bilo koju funkciju F, ali je zbog dodatnih ograničenja sigurnosti u kriptografiji se funkcija F mora pažljivo odabrati.
DES - Data Encryption Standard Data Encryption Standard, poznatiji kao DES algoritam je nastao sedamdesetih godina kao modifikacija Lucifer algoritma koji je raazvio IBM.
 DES je blokovski algoritam, Fejstel tipa sa 16 rundi.   Otvoreni tekst se deli na blokove od po 64 bita  Koristi ključ od 56 bita  U svakoj rundi se koristi podključ od 48 bita koji je podskup od 56-bitskog ključa
Cilj dizajna algoritma je da se uvedu principi konfuzije, difuzije i lavinskog efekta:
 Šifrat treba da zavisi od otvorenog teksta i ključa na složen način (konfuzije)  Svaki bit šifrata treba da je funkcija svih bitova otv.teksta i svih bitova ključa (difuzija).  Male promene ulaza treba da izazovu velike promene izlaza. Kod DES algoritma promena 1 bita ključa ili 1 bita (od 64) otvorenog teksta menja 50% bita bloka šifrata (Lavinski efekat).  Šifrovanje Otvoreni tekst se podeli na blokove od po 64 bita. Svaki blok otvorenog teksta se  transformiše u 16 rundi zamena i permutacija (transpozicija). Permuteacije unose difuziju podataka, zamene konfuziju. U svakoj rundi se koristi 48 bita ključa – naziv podključ (subkey).
Slika 3.5 DES algoritam - šifrovanje
Dešifrovanje  Isti proces kao i šifrovanje ali sa podključem u obrnutom redosledu.
Jedna runda DES algoritma je predstavljena na slici 3.6. Jedan blok otvorenog teksta se podeli na dva dela po 32 bita (L i R). U toku jedne runde se transformiše samo deo R dok
12
trenutni deo L prosleđuje u narednu rundu na poziciju novog dela R. Funkcija F se sastoji od ekspanzije (E-boks), nelinearnih transformacija (S-boks), permutacija (P-boks), sabiranja po modulu 2 i odabira bita ključa (K-boks). U daljem tekstu će biti objašnjeni samo principi na kojima funkcioniše algoritam, sa ciljem da se predstavi nivo složenosti algoritma, bez ambicije da se svaka od funkcija precizno definiše.
Slika 3.6 DES algoritam - jedna runda
E-boks proširuje (expand) i permutuje ulazne bite (od 32 bita na ulazu nastaje 48 bita). U postupku proširivanja menja se redosled bita sa ulaza, a neke biti se ponavljaju. Na izlazu se dobijaji biti (označeni prema redosledu sa ulaza)
31 0 1 2 3 4 3 4 5 6 7 8 7 8 9 10 11 12 11 12 13 14 15 16 15 16 17 18 19 20 19 20 21 22 23 24 23 24 25 26 27 28 27 28 29 30 31 0
Dobijeni biti na izlazu E-boksa se sabiraju po modulu 2 sa 48 bita podključa. Dobijeni zbir (48 bita) se dovodi na ulaz sledeće operacije koja sadrži 8 Ѕ boksova (Ѕ-boks[1], Ѕ-boks[2], ... Ѕ-boks[8]). Na ulaz svakog Ѕ- boksa se dovodi 6 bita (b1b2...b6 , vidi sl. 3.7) a na njegovom izlazu se dobija 4 bita (r1r2.r3r4). Na taj način se ulazni niz od 48 bita (8 Ѕ-boksova po 6 bita) komprimuje na izlaznih 32 bita (8h4 bita).
Slika 3.7 DES algoritam - Ѕ boks
Izlaz iz jednog Ѕ-boksa je određen unapred definisanom tabelom (za svaki od 8 Ѕ-boksova postoji posebna tabela). Na slici 3.8 je prikazana tabela za Ѕ-boks[1]. Ulazni biti b0 i b5
13
određuju red tabele, a biti b1, b2, b3 i b4 kolonu tabele. Ako ulazni biti b1b2b3b4b5b6 imaju vrednost 100011 odnosno b1b6 je 11 a b2b3b4b5 je 0001 pa je izlaz (r1r2.r3r4) 1100
Slika 3.8 Tabela za - Ѕ boks[1]
Ѕ-boks je realizovan kao nelinearna struktura i predstavlja jedan od najvažnijih elemenata na kojima počiva sigurnost DES algoritma .
Izlaz iz Ѕ-boksa (32 bita) sa vodi na R-boks, koji ih permutuje po definisanom pravilu tako da se na izlazu dobije novi niz od 32 bita.
Slika 3.9  R boks
K-boks ima zadatak da od ulaznih 56 bita ključa definiše 48 koji će se koristiti u jednoj rundi. Takođe predstavljava važnu sigurnosno bitnu funkciju. Ulazni niz od 56 bita se prvo podeli na dva niza od po 28 bita. Svaki od njih se prvo ciklično pomera a zatim dovodi na ulaz bloka koji ih permutuje i komprimuje. Ovako dobijenih 48 bita se koriste kao ključ (podključ) za jednu rundu.
14
Slika 3.10  K boks
DES analiza
Sigurnost DES algoritma počiva na S-boksovima koji predstavljaju nelinearne funkcije. Preko 30 godina intezivne analize DES algoritma nije dovelo do otkrića koji bi se iskoristili za neki od oblika skraćenog napada.
Ipak, DES algoritam se ne preporučuje za dalju upotrebu. Savremeni napadi koriste potpunu pretragu ključeva, jer se pokazalo da dužina ključa od 56 bita nije dovoljna za savremene računarske sisteme. Dvostruki DES algoritam Zbog rasprostranjene primene DES algoritama, u vreme kada je već bilo jasno da je moguća potpuna pretraga ključeva, javila se težnja da se postojeća rešenja za kriptozaštitu modifikuju u cilju postizanja veće sigurnosti.
Jedno od rešenja je da se poruka dva puta šifruje različitim ključevima (K1, K2). Dužina ključa je povećana sa 56 na 112 bita. Postupak šifrovanja je prikazan na slici 3.11
Slika 3.11 Dvostruki DES
Međutim, postoji napad koji može da obesmisli ovakvo rešenje. Polazi se od činjenice da ključ dužine 56 bita može efikasno da se pronađe postupkom potpune pretrage ključeva. Pretpostavimo zatim da Trudi zna par blokova otovrenog teksta i pripadajućih šifrata, npr. (R1, S1) i (R2, S2). Šta Trudi može da uradi?
Trudi će probati sve moguće vrednosti K1 (256) i šifrovati blok otvorenog teksta R1. Broj dobijenih šifrata je takođe veliki (256), ali ih je moguće izračunati. Trudi će sve rezultate zapisati u tabelu T. Potom će da proba sve moguće ključeve K2. Pretpostaviće neku vrednost za ključ K2,  dešifrovaće S1, i proveriti da li takav rezultat (H) postoji u tabeli T. Broj ključeva K2 je (256), a pretpostavka je da je moguće uraditi toliki broj operacija u razumnom vremenu.
15
Jednog momenta će Trudi pogoditi K2, odnosno dobiće rezultat H koji se nalazi u tabeli. Sada ima par ključeva K1 i K2. Preostalo je još samo da potvrdi da li ovo daje dobre rezultate za par otvorenog teksta (R2, S2). Postupak pretrage je prikazan na slici 3.12.
 Slika 3.12 Napad na dvostruki DES
Postupak se svodi na pretragu ključeva dužine 56 bita umesto dužine od 112 bita. Trostuki DES algoritam Prihvatljivo rešenje je u takozvanom trostrukom DES (ili 3 DES) alogoritmu. Ovde se takođe koriste dva ključa ali nije moguće izvesti prethodno opisani napad jer postoje dve operacije šifrovanja i jedna operacija dešifrovanja. Algoritam je predstavljen na slici 3.13
Slika 3.13 Trostruki DES algoritam
S=E(D( E(R,K1), K2), K1)
Zašto se ne koriste 3 ključa? Bilo bi sigurnije, ali je pokazano da je dužina od 112 bita (u to vreme) bila dovoljna.
Zašto se ne koriste tri puta šifrovanje, a ne šifrovanje dešifrovanje pa ponovo šifrovanje? Odgovor leži u kompatibilnosti. Ukoliko se uzme da je K1=K2. Onda se  trostruki DES svodi na obični DES algoritam:
S=E(D( E(R,K1), K1), K1)= E(R,K1)
Ekvivalentna dužina ključa je 112 bita, i do pre desetak godina je bio jedan od češće korišćenih blokovskih algoritama. Sa pojavom novog standarda (AES) počeo je da gubi na popularnosti.

16
AEЅ algoritam Nakon što je postalo jasno da DES algoritam nije bezbedan tražilo se novo rešenje za standardni blokovski algoritam. Krajem devedesetih godina, raspisan je konkurs na kom je pobedničko rešenje prihvaćeno kao standard (2001. godine) pod nazivom Advanced Encryption Standard - AES
AES je iterativna blokovska šifra, kao i DES ali nije fejstel šifra. Pokazao se kao brz uz moguću paralelnu implementaciju. Za sada nisu poznati efikasni napadi na AES  algoritam.
Blok otvorenog teksta je dužine 128 bita (mada je originalno rešenje dozvoljavalo  i dužine od 192 i 256 bita), dužina ključa može da se bira između 128, 192 i 256 bita, a broj rundi algoritma je između 10 i 14 u zavisnosti od dužine ključa.
Svaka runda se sastoji od 4 funkcije:  ByteSub (nelinearni sloj)  ShiftRow (sloj linearnog mešanja)  MixColumn (nelinearni sloj)  AddRoundKey (dodatni sloj ključa)
Otvoreni tekst se prvo podeli na blokove dužine 128 (192 ili 256) bita. Svaki blok se šifruje posebno i kao rezultat se dobija blok šifrata iste dužine kao i blok otvrenog teksta.
ByteSub
ByteSub funkcija predstavlja ekvivalent Ѕ-boks funkciji kod DES algoritma i osnovu sigurnosti AEЅ algoritma. Podaci iz jednog bloka otvorenog teksta se prvo zapišu u matricu a, određenih dimenzija, a potom se nelinearnom funkcijom dobija nova matrica b. Na slici 3.14 je šematski prikazana transformacija.
Slika 3.14 ByteSub funkcija AEЅ algoritma
ByteSub funkcija kao ulazni argument ima vrednost bajta otvorenog teksta (npr. 0h3S). Na osnovu viša 4 bita (3) se adresira vrsta tabele a na osnovu niža 4 bita (S) kolona tabele. Tabela sadrži 256 različitih vrednosti, a njihov sadržaj je unapred definisan. Vrednost bajta u matrici b u koji će se preslikati bajt iz matrice a se dobija iz tabele. Na slici 3.15 je predstavljen primer čitanja vrednosti iz tabele.
17
  Slika 3.15 ByteSub funkcija AEЅ algoritma, čitanje iz tabele sa unapred definisanim podacima
ShiftRow
ShiftRow funkcija je linearna, ona ciklično pomera poslednja tri reda matrice, dobijene nakom delovanja funcije ByteSub , za 1, 2 i 3 mesta. Na slici 3.16 je prikazana postupak cikličnog pomeranja.
Slika 3.16 ShiftRow funkcija AEЅ algoritma
MixColumn
MixColumn  je takođe nelinearna funkcija, bitna za sigurnost AEЅ algoritma. Premešta kolone po definisanim pravilima i pri tome svaku kolonu množi sa odgovarajućom matricom. Šematski prikaz je dat na slici 3.17
Slika 3.17 MixColumn funkcija AEЅ algoritma
AddRoundKey
18
Slično kao i kod DES algoritma iz celokupnog ključa se izdvaja podključ koji se koristi za šifrovanje u iterativnom procesu. Od podključa se definiše matrica koja se potom sabira po modulu 2 sa matricom dobijenom nakon primene prethodnih operacija (vidi sliku 3.18)
Slika 3.18 AddRoundKey funkcija AEЅ algoritma
AEЅ algoritam je invertibilan, pa je postupak dešifrovanja veoma sličan postupku šifrovanja. Režimi rada blokovskih šifara Rad blokovskih algoritama je u osnovi jednostavan ali se nameće pitanje kako šifrovati kada otvoreni tekst R ima dužinu od više blokova. Način na koji se primenjuje blokovska šifra na niz uzastopnih blokova se naziva režim (mod) rada.
Da li treba šifrovati svaki blok nezavisno?
Da li šifrovanje učiniti zavisnim od šifrovanja prethodnih blokova („ulančati“blokove)?
Ukoliko se svaki blok šifruje nezavisno (sa istim ključem) mogu nastati sigurnosni problemi. Jedan od karakterističnih slučajeva je neotpornost na tzv. Cut and Paste napad.
Primer:
Neka je otvoreni tekst koji Alisa želi da šifruje:
  Alice digs Bob. Trudy digs Tom.
Radi lakše analize pretpostavimo da je blok otvorenog teksta dužine od 64 bita i da je primenjeno 8-bitsko ASCII kodovanje. U tom slučaju postoje 4 bloka otvorenog teksta R0, R1, R2, i R3:
 P0 = “Alice di”, P1 = “gs Bob. ”,
 P2 = “Trudy di”, P3 = “gs Tom. ”
Nakon šifrovanja dobijaju se 4 bloka šifrata : C0, C1, C2, C3, koje Alisa šalje Bobu po navedenom redosledu (vidi sliku 3.19)
Slika 3.19 Nezavisno šifrovanje (dešifrovanje) svakog bloka
19
Ako Trudi ima mogućnost da utiče na prenos poruke, ona može da promeni redosled poslatih blokova (mada ne može da dođe do otvorenog teksta). Neka je Trudi nasumično ispreturala blokove i pošalje Bobu : C0, C3, C2, C1 (umesto C0, C1, C2, C3).
Bob dešifruje dobijene blokove šifrata kao:
  Alice digs Tom. Trudy digs Bob.
Poruka je izmenjena na prenosnom putu a Bob nema načina da to primeti! Očigledno je da nema mehanizma integriteta.
Sledeća slabost je da u slučaju nezavisnog šifrovanja blokova otvorenog teksta istim ključem je da isti blokovi otvorenog  teksta daju isti blok šifrata, odnosno ako je Ri =Pj   Ci=Cj.
Uz pretpostavku da Trudi zna neki blok otvorenog teksta Ri ona će moći da zna i svaki drugi identičan blok otvorenog teksta na osnovu poređenja blokova šifrata. Na taj način može da dođe do dodatnih informacija. Možda ovo i ne deluje preterano veliki dobitak za Trudi, ali sledeći primer je veoma poučan.
Pretpostavimo da treba da se šifruje crno bela slika Alise (slika 3.20). Ona sadrži puno identičnih blokova otvorenog teksta (pravilnije slike). Bele površine se ponavljaju, sa crnima je slično. Nakon šifrovanja, za očekivati je da će isti blokovi otvorenog teksta dati iste blokove šifrata. Posledica toga je da će šifrat biti gotovo čitljiv.
Slika 3.20 Alisina slika pre (levo) i nakon šifrovanja blokovskim algoritmom
Da bi se prevazišli navedeni nedostaci neophodno je da se primene neki od modova rada blokovskih algoritama koji će dovesti u vezu šifrovanje (i dešifrovanje) susednih blokova.
Postoji više standardizovanih modova rada, a u ovoj lekciji će biti opisana dva koji se najčečešće koriste.
SVS mod
Kod primene SVS (Sipher Block Chaining) moda susedni blokovi se međusobno ulančavaju. Šifrat iz prethodnog bloka se sabira po modulu 2 sa otvorenim tekstom narednog bloka a dobijeni rezultat se šifruje. Kako na početku ne postoji šifrat prethodnog bloka, uvodi se slučajna vrednost IV. IV treba da bude slučajna vrednost, ali obzirom da ne mora da bude tajna može se javnim kanalom poslati Bobu. Bobu je IV neophodna za pravilno dešifrovanje. Postupak šifrovanja je prikazan na slici 3.21
20
Slika 3.20 SVS mod rada - šifrovanje
Postupak šifrovanja i dešifrovanja se može predataviti sa:
Primenom SVS moda rada se postiže da identični blokovi otvorenog teksta daju različite blokove šifrata! Napad tipa "Cut and paste" je i dalje moguć ali je daleko složeniji (posledica su greške koje su očigledne nakon dešifrovanja). Praktično je nemoguće da se pojavi situacija prikazana na slici 3.20.
Primer:
Ako je blok C1 zamenjen sa lažnim blokom G, onda (na osnovu gornje tabele):

Bez obzira da li je do zamene došlo namerno (napad) ili zbog grešaka u prenosu, algoritam je takav da se automatski oslobađa grešaka nako dva bloka.
CTR mod
CTR (Counter) ili brojački mod je takođe jedan od načina da se ulančaju susedni blokovi. Mod rada je prikazan na slici 3.21.
Slika 3.20 STR mod rada - šifrovanje
21
Na početku se, pored ključa, izabere početna vrednost brojača, koja se kao i u prethodnom modu obeležava sa IV. IV treba da bude slučajna vrednost. Za pravilan postupak dešifrovanja je potrebno da se IV dostavi i prijemnoj strani.
Postupak šifrovanja je donekle različit, šifruje se vrednost IV, a dobijeni šifrat se sabira po modulu 2 sa prvim blokom otvorenog teksta. Dobijeni rezultat predstavlja prvi blok šifrata (S0). Potom se poveća vrednost brojača (IV) za 1 (ili neku drugu vrednost koja je poznata Alisi i Bobu), nova vrednost se šifruje, dobijeni rezultat se sabira po modulu 2 sa drugim blokom otvorenog teksta...
Postupak šifrovanja i dešifrovanja se može opisati relacijama:
Integritet Integritet predstavlja skup postupaka koji treba da spreče (ili barem otkriju) neovlašćenu izmene podataka. Pri tome nije neophodno da podaci budu šifrovani. Postoje brojne situacije kada podaci treba da budu javni ali je potrebno da postoji podatak o tome da li su podaci verodostojni ili nisu. Na primer, kod postavljanja elektronskih oglasa, podaci treba da budu javni, ali napadač može da prmeni detalje oglasa i da na taj način napravi štetu.
Šifrovanje može da obezbedi poverljivost. Može li da pomogne oko integriteta?
Jedan od načina da se obeznedi integritet kod simetriččnih šifarski sistema ja primena tzv. Message Authentication Code (MAC )
MAC  Message Authentication Code MAC ne predstavlja novi algoritam već se zasniva na primeni bilo kog blokovskog algoritma. Otvoreni tekst se podeli na blokove (R0, R1,...RN-1) i potom se svaki od blokova šifruje na uobičajeni način:
Pamti se samo poslednji blok šifrata:
Poslednji blok šifrata se naziva MAS. Obzirom da je nastao kao rezultat svih prethodnih blokova šifrata on sadrži podatke o svima njima. Ukoliko nije potrebno da se ostvari servis poverljivosti, već samo integriteta, Alisa šalje Bobu sledeće podatke:
22
Bob je od Alise ranije dobio ključ K, sigurnim kanalom. Bob na osnovu primljenih podataka (IV, P0, P1, P2, P3) može da izračuna vrednost MAS i da je uporedi sa primljenom vrednošću MAS. Ukoliko su te dve vrednosti jednake smatra se da nije došlo do greške ili izmene podataka u prenosu.
Primer napada:
Alisa je poslala Bobu IV, P0, P1, P2, P3 i MAS poslalaTrudi može da pročita poruku (jer nije šifrovana) i želi da je imeni, umesto P1 stavlja H. Bob je primio poruku IV, P0, H, P2, P3 i MAS i želi da proveri integritet, pa računa:
Kada Bob uporedi izračunatu vrednost i primljenu vrednost MAS one neće biti jednake.
Bob može da zaključi da je poruka menjana.
Da li je Trudi mogla da nakon zamene izračuna novu vrednost MAS tako daprevari Boba? Nije zato što ne zna ključ K!
Potpuno isti scenario se može primeniti i na poruke koje se šifruju samo se tada koriste različiti ključevi za šifrovanje i za integritet.


Kripto sistemi sa javnim ključem
priredio: dr Zoran Banjac
2014.

2
Sadržaj Uvod ...................................................................................................................................................3 Šifrovanje bez razmene ključa .......................................................................................................3 Difi-Helmanov algoritam za razmenu ključa ...........................................................................4 Jednosmerne funkcije .................................................................................................................4 Difi-Helmanov (DH) algoritam..................................................................................................5 DH algoritam –matematičke osnove .........................................................................................6 DH algoritam - slabosti ...........................................................................................................7 Šifarski sistemi sa javnim (i tajnim) ključem .............................................................................8 RSA algoritam ..............................................................................................................................8 RSA algoritam - osnovne pretpostavke ....................................................................................8 Postupak šifrovanja: ...............................................................................................................9 Postupak dešifrovanja: ...........................................................................................................9 Generisanje javnog i tajnog ključa ............................................................................................9 Postupak šifrovanja i dešifrovanja .................................................................................. 10 Sigurnost RSA algoritma ........................................................................................................ 10 Primena kriptografije sa javnim ključem .................................................................................... 11 Digitalni potpis ....................................................................................................................... 11 Digitalno potpiši pa šifruj ............................................................................................... 12 Šifruj pa digitalno potpiši ............................................................................................... 12 Infrastruktura javnih ključeva ..................................................................................................... 13 Prednosti kriptografije sa javnim ključem ................................................................................. 14 Nedostaci kriptografije sa javnim ključem ................................................................................. 14 Dodatak ........................................................................................................................................... 15 Modularna aritmetika ............................................................................................................. 15 Svojstva modularne aritmetike ............................................................................................... 15 Prosti brojevi ........................................................................................................................... 16 Ojlerova funkcija ..................................................................................................................... 17 Osnovna teorema aritmetike:................................................................................................... 18

3
Uvod Nakon II s.r. primena računara u kriptologiji je bila privilegija državnih službi. Razvoj nauke i tehnike je doprineo da računari i njihova primena postanu dostupni širim društvenim slojevima. Neki od presudnih događaja su navedeni u nastavku:
 1947.-pronalazak tranzistora (Bell Laboratories)  1953. IBM – pojava komercijalnih računara  1955.- nastao je programski jezik Fortran.  1959. nastala su prva integrisana kola.  1969.  ARPAnet (preteča Interneta).
Šezdesetih godina, poslovni svet sve više koristi računare za šifrovanje (transver novca, pregovori,...) ali ne postoje standardizovani algoritmi za zaštitu. Pojavljuje se problem kompatibilnosti u situacijama kada treba da se komunicira zaštićeno izvan kompanije. To je dovolo do uvođenja standardizovanih algoritama (DES, npr). Međutim, jedano od nerešnih pitanja je predstavljao problem razmene ključa. Na primer, banka treba da obavi šifrovani prenos sa klijentom, kako dostaviti ključ? Ključ se ne može dostaviti javnim komunikacionim kanalom. Najbezbednije je lično ili preko kurira, ali za veliki broj klijenata to može da predstavlja problem. Za državne službe (vojska, diplomatija i sl.) koje raspolažu ljudstvom i potrebnim obezbeđenjem to se moglo rešiti, dok je civilni sektor ovo bio gotovo nerešiv problem.
Napomena: Kraći matematički podsetnik se nalazi u dodatku na kraju teksta.
Šifrovanje bez razmene ključa Razmotrimo sledeću ideju: Alisa stavlja poruku u metalni sandučić koji zaključava katancem A i šalje ga Bobu. Nakon prijema, Bob stavlja svoj katanac V i vraća pošiljku (sa dva katanca) Alisi. Alisa skida svoj katanac (A) i vraća pošiljku (na kojoj je još uvek katanac V) Bobu. Bob sada može da otvori pošiljku-ali Eva ne može! Postavlja se pitanje da li je ovaj postupak moguće pretočiti u algoritam. Da bi došli do odgovora, analiziraćemo primenu šifre zamene.
Primer: Neka Alisa treba da šifruje poruku meet me at noon. Alisa i Bob imaju različite ključeve, predstavljene na slici 4.1
Slika 4.1 Ključevi Alise i Boba
Kad Alisa šifruje poruku dobija šifrat, koji šalje Bobu:
4
YGGC   YG   HC   JBBJ
Sada Bob šifruje poruku koju je dobio od Alise i dobija novi šifrat, koji šalje Alisi:
LNNM  LN   OM   EPPE
Alisa, svojim ključem dešifruju dobijenu poruku i dobijenu vrednost šalje Bobu:
ZQQX    ZQ   LX   KPPK
Bob dešifruje primljenu poruku i dobija
wnnt   wn  yt   xbbx
Pristup je logičan ali nije izvodljiv! Pokazuje se da je bitan redosled šifrovanja i dešifrovanja. Poslednji postupak šifrovanja mora biti prvi koji se dešifruje...
Uprkos opšte prihvaćenom mišljenju da je ovaj problem nerešiv, jedna grupa entuzijasta (Whitfield Diffie, Martin Hellman i Ralph Merkle) je krajem 70-ih godina ponudila rešenje. Istraživanja u ovom pravcu su dovela do razvoja kripto sistema sa javnim ključem.  Difi-Helmanov algoritam za razmenu ključa Difi i Helman su tražili matematičke funkcije za koje redosled šifrovanja i dešifrovanja nije bitan, tj.
f(g(x)) = g(f(x))
Ovakve funkcije postoje, većina ih je dvosmerna, odnosno mogu se lako izračunati ali je lako naći i njihovu inverznu vrednost, pa samim tim nisu primenjljive za razmenu tajne vrednosti, jer bi svako mogao da je sazna.
Primer dvosmernih funkcija: f(x) = 2x;  f(x) = x2, lako je naći inverznu funkciju i saznati vrednost h, koja treba da se prenese, odnosno koja treba da bude tajna (ključ).
Od interesa su jednosmerne funkcije (one way), tačnije neki oblici ovih funkcija. Jednosmerne funkcije Jednosmerne funkcije relativno lako mogu da se izračunaju, ali njihova inverzna vrednost može da se odredi samo izuzetno složenim postupkom.
 Za dato x lako se računa f(x), ali je za dato f(x) teško izračunati x.
Kako definisati pojam „teško“: ogromno vreme uz neograničene resurse. Ovaj pojam se koristi za probleme koji se ne mogu rešiti u prihvatljivom vremenskom periodu, iako su na raspolaganju:  najbolji poznati algoritam i   najbolja tehnologija
Primeri jednosmernih funkcija su: lomljenje čaše, mešanje boje,...
5
U čemu je značaj jednosmernih funkcija? Poruka šifrovana jednosmernom funkcijom ne može da se dešifruje! Zbog toga treba razmotriti jednu podklasu jednosmernih funkcija koje se zovu jednosmerne funkcije sa zamkom (trapdoor one way function). Jednosmerne funkcije sa zamkom su poseban oblik jednosmernih funkcija.
 Lako ih je izračunati u jednom (direktnom) smeru.  Teško je izračunati inverznu vrednost.  Ako je poznata tajna vrednost - zamka, onda se lako može izračunati i direktna i inverzna vrednost.
Za dato x lako je izračunati f(x), teško je izračunati x iz f(x). Ali, ako je poznata tajna vrednost y, iz f(x) i y, lako se računa x. Modularna aritmetika obiluje jednosmernim funkcijama. Pre nastavka, potrebno je istaći da, strogo matematički gledano, nije dokazano da postoje jednosmerne funkcije, odnosno jednosmerne funkcije sa zamkom. S druge strane nije dokazano ni da ne postoje.
Postoje dve funkcije koje se smatraju kandidatima za funkcije sa pomenutim svojstvima:
 Diskretni eksponent, čija inverzna funkcija je diskretni logaritam.   Proizvod celih brojeva, čija inverzna funkcija je faktorizacija dobijenog broja.
Ove dve funkcije su lake za izračunavanje, dok se veruje da to nije slučaj sa njihovim inverznim funkcijama. Difi-Helmanov (DH) algoritam Difi-Helmanov algoritam predstavlja algoritam za razmenu ključeva. Koristi se za razmenu zajedničkog simetričnog ključa. Nije namenjen za šifrovanje ili digitalno potpisivnje.
Sigurnost Difi-Helmanovog algoritma se zasniva na računskoj složenosti izračunavanja (jednosmerne funkcije) diskretnog logaritma.
Razmotrimo klasičan problem. Za poznato g i h, gde je x = gn, može da se odredi n, n = logg(x). Međutim ako je x = gn (mod p), n se takođe određuje preko logaritma ali diskretnog (diskretni logaritam)
Primer: Ako je poznato da je 3n =81, relativno lako se može  doći do rezultata (n = 4).
Ako je 3n (mod 7) = 1, kako doći do n ? Može se napraviti tabela
Prvo treba uočiti da nema pravilnosti: sa porastom n, 3n (mod 7) se menja bez uočljivog pravila. Za relativno male vrednosti g i h do rešenja se može doći na predloženi način, ali za velike vrednosti, kao npr 328n (mod 23713) do rezultata je gotovo nemoguće doći.
6
DH algoritam –matematičke osnove Neka je p veliki prost broj i g takvo da se za svako x  {1, 2,…, p-1} može naći n tako da je:
x = g n (mod p)
Vrednosti p i g su javne vrednosti, što znači da se mogu razmenjivati javnim kanalom. DH algoritam se može opisati na sledeći način:  Alisa i Bob (ali i Trudi znaju javne vrednosti p i g)  Alisa bira tajnu vrednost a (veliki slučajan ceo broj).  Bob bira tajnu vrednost b (veliki slučajan ceo broj).  Alisa javno šalje vrednost ga (mod p) Bobu.  Bob javno šalje vrednost gb (mod p) Alisi.  Oboje računaju zajedničku tajnu vrednost gab (mod p)
Ta zajednička tajna vrednost može da se koristi kao simetrični ključ.
Može li Trudi, na osnovu razmenjenih poruka da sazna tajnu vrednost gab (mod p)? Trudi zna vrednosti ga (mod p) i gb (mod p). Trudi može da izračuna vrednost:  ga (mod p) gb (mod p)= ga+b (mod p)
ali dobijena vrednost nije jednaka gab (mod p). Sve dok Trudi ne može da izračuna inverzni diskretni logaritam, ona ne može da dođe do tajne vrednosti gab (mod p).
Šematski prikaz razmene ključa primenom DH algoritma je predstavljen na slici 4.2
Slika 4.2 DH algoritam
Primer:
1. Alisa bira broj a (npr. 3) i čuva ga u tajnosti.  2. Alisa zamenjuje n sa a  i računa 73(mod 11)=343 (mod 11)= 2. 3. Alisa obeležava rezultat A=2 i šalje ga Bobu. 4. Bob bira broj b (npr. 6) i čuva ga u tajnosti. 5. Bob zamenjuje n sa b i računa 76(mod 11)=117649(mod 11)=4.  6. Bob obeležava rezultat B=4 i šalje ga Alisi. 7. Alisa uzima Bobov rezultat i računa Ba (mod 11) = 64(mod 11) = 9.
7
8. Bob uzima Alisin rezultat i računa Ab (mod 11)= 64 (mod 11) = 9 9. Razmenjena je tajna vrednost 9.
U praksi se za p koristi veliki broj (više od 1024 bita)! DH algoritam - slabosti DH algoritam je osetljiv na napad tipa čovek u sredini (man-in-the-middle).
slika 4.3 Napad tipa čovek u sredini
Razmotrimo sledeći scenario:
Alisa pokreće proceduru razmene simetričnog ključa na uobičajeni način. Šalje Bobu vrednost ga (mod p). Trudi koja je administrator mreže presreće poruku i ne dozvoljava da ona stigne do Boba. Umesto toga, Trudi šalje Bobu vrednost gt (mod p). Bob je primio vrednost gt (mod p) i veruje da je dobio od Alise. Bob šalje Alisi svoju vrednost gb (mod p). Trudi sada presreće i ovu poruku, zadržava je za sebe, a Alisi šalje vrednost gt (mod p).  Alisa računa i dobija vrednost ključa gta (mod p) i veruje da je razmenila ključ sa Bobom. Trudi takođe može da izračuna tu vrednost.
Bob računa i dobija vrednost gtb (mod p) i veruje da je razmenio tajni ključ sa Alisom. Trudi takođe može da izračuna tu vrednost.
Ako bi Bob i Alisa pokušali da uspostave tajnu komunikaciju primenom ključeva koje su „razmenili“, ona ne bi uspela jer su ključevi različiti. Međutim, Trudi to i ne želi.
Trudi ima mogućnost da presretne svaku šifrovanu poruku koju je poslala Alisa, da je dešifruje, pročita, po potrebi izmeni i da je potom šifruje Bobovim ključem i da prosledi Bobu. Bob će ovu poruku uspešno dešifrovati. Isto važi i za poruke koje Bob šalje Alisi.
Bob i Alisa mogu da veruju da imaju zaštićenu komunikaciju, a Trudi će moći da dešifruje sve poruke koje se razmenjuju.
Kako osujetiti ovaj napad? Postoji više rešenja. Suština je da se uvede mehanizam autentifikacije na osnovu kojih bi obe strane bile sigurne u poreklo poruka. Jedno od mogućih rešenja je i dodatno šifrovanje.
8
Šifarski sistemi sa javnim (i tajnim) ključem Difi i Helman su predložili primenu šifarskog sistema kod kojeg su ključ za šifrovanje i dešifrovanje različiti. Osnovna ideja je da svaka strana u komunikaciji ima dva ključa: jedan ključ koji je svima dostupan (javni ključ) i drugi ključ koji je poznat samo vlasniku (tajni ili privatni ključ). Ako Bob želi da Alisi pošalje šifrovanu poruku on će poruku šifrovati upotrebom odgovarajućeg algoritma i Alisinig javnog ključa. Šifrovanu poruku može da dešifruje samo Alisa upotrebom svog tajnog ključa. Niko drugi pa ni Bob koji je šifrovao poruku, ne može da dešifruje šifrat je ne zna Alisin tajni ključ.
Ideju su predložili Difi i Helman, ali nisu predložili funkciju (algoritam šifrovanja i dešifrovanja) koja bi radila na ovaj način. Jedan od najpoznatijih algoritama sa javnim ključem je RSA algoritam RSA algoritam RSA algoritam je nastao 1978. godine. Autori su tri istraživača sa MIT Univerziteta: Ronald Rivest, Adi Šamir i Leonard Adelman, a algoritam je dobio ime po početnim slovima prezimena autora.
RSA algoritam je zasnovan na složenosti problema faktorizacije proizvoda dva velika prosta broja, čiji izbor je usklađen sa zahtevima za praktičnu primenu kriptografije sa javnim ključem. RSA algoritam - osnovne pretpostavke Potrebno je pronaći funkciju šifrovanja, E:
S = E(M, Ke)
koja menja poruku M (otv. tekst) u šifrat S. Ulazni parametri funkcije E su poruka M i ključ šifrovanja Ke.
Funkcija E(M, Ke) treba da bude jednosmerna funkcija sa zamkom.
Alisa (ili bilo ko drugi) koristi tu funkciju da šifruje svoju poruku pre nego što je pošalje Bobu.Bob treba da ima mogućnost da uz poznavanje tajne vrednosti Kd , primeni inverznu funkciju, D
M = D(S, Kd)
kako bi od šifrata S dobio poruku M.
Za svako M treba da važi:
M = D( E(M, Ke), Kd)
Funkcija koja zadovoljava iznete pretpostavke ima oblik:
f (x ) = x e
 (mod N ) Uz odgovarajući izbor vrednosti e i N, ova funkcija je jednosmerna. uz poznavanje tajne vrednosti može da se nađe njena inverzna vrednost. Bez poznavanja tajne vrednosnti ona je praktično nerešiva.
9
Postupak šifrovanja:
C = M e (mod N)
gde je C je šifrat, a M poruka (otvoreni tekst). Treba odgovoriti na pitanje kako odrediti vrednosti e i N? Postupak dešifrovanja:    M = C d (mod N) = (M e ) d (mod N) = M ed (mod N)
Šta je i kako odrediti vrednost d ?
Jedina tajna vrednost u celom postupku je vrednost tajnog ključa (d) i nju treba da zna samo prijena strana. Obe strane u komunikaciji znaju vrednosti N i e.
 Javni ključ predstavljaju vrednosti N i e  Tajni ključ je vrednost d Izabrane vrednosti e, d i N treba da su takvi da je M ed = M (mod N) za svako M < N. Pored toga, zahteva se da je relativno lako za računanje: Me (mod N) za M < N i da je praktično nemoguće izračunati d za dato e i N. Pokazuje se da je algoritam računski siguran za dovoljno veliko e i N. Generisanje javnog i tajnog ključa Postupak izbora javnog i tajnog ključa se može definisati sledećim koracima:
1. Izabrati 2 velika prosta broja p i q,  2. Formirati proizvod N = pq,  3. Izračunati φ(N) = (p-1)(q-1),  4. Izabrati e takvo da je uzajmno prosto sa φ(N) i manje od φ(N), 5. Naći d takvo da je d = e-1mod φ(N)), odnosno de = 1 (mod φ(N)). Nakon toga proglasiti:  Javni ključ: (N,e)   Privatni ključ: d
Pojednostavljeni primer RSA algoritma:
 Izabrati „velike″ proste brojeve: p = 11, q = 3   Odrediti N =  pq = 33 i (p1)(q1) = 20    Izabrati e = 3 (uzajamno prost sa 20)   Naći d takvo da je ed = 1 (mod 20), d = 7, odgovara zahtevu   Na osnovu izračunatih vrednosti  o Javni ključ: (N, e) = (33, 3) o Privatni ključ: d = 7   Neka je poruka M = 8  Šifrat C se računa kao  C = Me (mod N) = 83 (mod 33)= 512 (mod 33)= 17   Dešifrovati C da bi dobili poruku:
10
 M = Cd (mod N) = 177  (mod 33)= 410,338,673  (mod 33) = (12,434,505 ∙ 33 + 8) (mod 33)= 8
Postupak šifrovanja i dešifrovanja  Postupak šifrovanja i dešifrovanja obuhvata celobrojne računske operacije sa porukom M. Poruku M prvo treba pretvoriti u broj. Postupak pretvaranja može da bude proizvoljan (a=01, b=02, ..., z=26) ili se može koristiti neki od standardnih postupaka kodovanja (npr. ASCII kod). Kako se računa po po mod roblem izbora (računanja) tajnog ključa: Efikasno rešavanje ove jednačine moguće je pomoću proširenog Euklidovog algoritma. Računa se po modulu N pa je potrebno da je N > M, da bi proces šifrovanja bio jednoznačan. Ako je i pored izbora velokog N, M > N, onda poruka M treba da se rastavi na manje celine (blokove). Pored toga treba odabrati vrednost N izborom prostih brojeva p i q. Prostih brojava ima beskonačno puno, i prostoje brojni testivi za njihov izbor a jedan od najpoznatijih je Miler-Rabinov test.  Izbor broja e takođe mora da bude odgovarajući. e mora da bude uzajmno prost sa (p - 1)(q - 1),  pa se za e često bira prost broj. Zbog brzine šifrovanja postoji zahtev da e bude što manje, ali to može da naruši snagu algoritma. Mnogi korisnici koriste isti eksponent e unutar javnih ključeva: e = 65537 Na ovaj način se ne kompromituje šifarski sistem a omogućava se da proces šifrovanja bude mnogo brži od dešifrovanja. Računanje privatnog ključa d, svodi se na rešavanje jednačine:  ed = 1 (mod φ (N ) ) Obzirom da je e  izabrano takvo da je:  gcd(e, φ(N )) = 1, ta jednačina uvek može da se reši. Sigurnost RSA algoritma Trudi može da zna C  Me (mod N), e i N. To su javne vrednosti. Može li ona da rekonstruiše poruku M ?  Ne postoji dokaz da Trudi može efikasno da rekonstruiše M na osnovu poznavanja C, e i N, a da pri tome ne zna  (N ) odnosno vrednosti p-1 i q-1.  Veruje se da ne može.  Dokazano je da problem pronalaženja  (N ) podjednako složen kao i faktorizacija broja N. Veruje se, mada nije dokazano, da je problem faktorizacije velikih brojeva praktično nerešiv. Na takmičenju koje je organizovala RSA Laboratories, 2005. godine je faktorizovan broj N koji je imao 663 binarne cifre (200 dekadskih cifara), a 2007. godine broj od 768 binarnih cifara. Za posao je bilo angažovano veoma mnogo umreženih računara i posao je trajao oko 3 godine. Novijih rezultata nema, ali proračuni pokazuju da je vrednost N od 1024 bita (neki oprezniji analitičari čak tvrde 2048 bita) danas dovoljno sigurna. Povećanje granice sigurnosti zahteva povećanje dužine ključa jer se algoritmi za faktorizaciju broja se unapređuju (kriptoanaliza). Vreme potrebno za šifrovanje i
11
dešifrovanje je proporcionalno trećem stepenu dužine ključa, što bitno usložnjava realizaciju algoritma i doprinosi povećanju potrebnog vrenena za navedene procese, pa RSA postoje sve sporiji sa povećanjem zahteva bezbednosti.  Upravo zbog ovog razloga, osnovna primena RSA algoritma je za šifrovanje kriptografskih ključeva. Potom se razmenjeni ključ koristi u simitrični kripto sistemima za zaštitu podataka.
Primena kriptografije sa javnim ključem Kriptografijom sa javnim ključem može da se postigne:  Poverljivost  o koristi se kod prenosa podataka i o skladištenja podataka.   Autentifikacija   Digitalni potpis, koji obezbeđuje integritet i neporecivost (non-repudiation).  o Nema servisa neporecivosti u sistemima sa simetričnim ključem!  Digitalni potpis Digitalni potpis je servis koji treba da obezbedi integritet poruke i neporecivost. Pod integritetom poruke se podrazumeva da prijemna strana može da bude sigurna da poruka na prenosnom putu nije izmenjena ili ukoliko se to desi da to može da jednoznačno detektuje, Neporecivost je servis koji prijemnoj strani može da bude neoboriv dokaz da je poruku primio od tačno određene osobe. Digitalni potpis treba da predstavlja elektronsku zamenu za rukom pisani potpis, ali ne predstavlja sliku klasičnog potpisa ili nešto slično, već se postiže matematičkim funkcijama koje će biti predstavljene.
Neka postoji javni ključ (N, e), i privatni je d. Postupak digitalnog potpisivanja poruke M je definisan sa  Ѕ = Md (mod N ) Sa S je predstavljen digitalni potpis. Treba primetiti sličnost sa postupkom dešifrovanja, stim da se ne „deđifruje“ šifrat S već poruka M. Kod RSA algoritma je dešifrovnje i digitalno potpisivanje potpisivanje identična operacija.
Za računanje S je neophodno poznavanje tajnog ključa d.  Alisa šalje Bobu poruku M i digitalno potpisanu poruku Ѕ= Md (mod N ). Bob prima poruku M i Ѕ. Bob sada treba da proveri digitalni potpis, a pri tome zna Alisin javni ključ (odnosno e i N).
Potvrda ispravnosti digitalnog potpisa na poruci M:  Ѕe(mod N ) =(Md)e (mod N )= M Operacija je ista kao i kod šifrovanja. Ukoliko je izračunata vrednost M jednaka dobijenoj vrednosti M, onda je Bob siguran da
 poruka M  nije promenjena na prenosnom putu
12
 je samo Alisa mogla da pošalje poruku jer samo ona zna tajni ključ d. Svako ko zna javni ključ (N, e) može da potvrdi ispravnost digitalnog potpisa.
Uvedimo označavanje: Šifrovanje poruke M, sa Alisinim javnim ključem: C ={M }Alisa  Dešifrovanje šifrata, sa Alisinim privatnim ključem: M=[ S ]Alisa  Digitalno potpisivanje poruke M, sa Alisinim privatnim ključem: Ѕ =[M ]Alisa   U prethodnom primeru je poruka poslata otovreno (nije šifrovana) i poslat je digitalni potpis te poruke. U praksi postoji potreba da se poruka i šifruje i da se digitalno potpiše. Međutim, postavlja se pitanje, da li prvo digitalno potpisati poruku pa je potom šifrovati ili prvo šifrovati poruku pa je potom digitalno potpisati. Razmotrimo oba slučaja. Digitalno potpiši pa šifruj Niz postupaka je predstavljen na slici
Slika 4.4 Digitalni potpis pa šifrovanje Alisa želi da pošalje poruku „Volim te...“. Prvo je digitalno potpiše svojim tajnim ključem Ѕ =[M ]Alisa , a potom digitalni potpis Ѕ šifruje Bobovim javnim ključem { [M ]Alisa}Bob. Bob može da dešifruje poruku svojim tajnim ključem i da dobije [M ]Alisa, a kako zna Alisin javni ključ može da potvrdi digitalni potpis, odnosno može da dođe do poruke M. Bob se kasnije naljutio na Alisu, i kako je sačuvao vrednost [M ]Alisa on je šifruje sa Čarlijevim javnim ključem i šalje Čarliju. Čarli sada na isti način kao i Bob može da dođe do poruke M i misli da je Alisa zaljubljena u njega. Da li je u pravu? Očigledno da nije, a da zna pravila digitalnog potpisa ne bi ni bio u zabludi. Naime, digitalni potpis potvrđuje poreklo poruke ali nikako ne znači da je poruka bila namenjena onome kome je stigla. Naime, svi znaju Alisin javni ključ pa bi svako ko je potvrdio njen digitalni potpis mogao pogrešno da zaključi da je sadržaj upućen baš njemu. Digitalni potpis je potvrda da je vlasnik javnog (i tajnog) ključa nešto poslao, ali ne i da je poruka upućena baš određenom primaocu (osim ako se iz samog sadržaja poruke to ne može jednoznačno zaključiti). Šifruj pa digitalno potpiši Alisa se pomirila sa Bobom ali je zapamtila nemio događaj. Poučena iskustvom, sada će prvo da šifruje poruku, a potom će digitalno da je potpiše.
Slika 4.5 Šifruj pa digitalno potpiši
13
Alisa žedi da obavesti Boba o svom novom uspehu. Šalje poruku „Moj novi izum je...“. Prvo poruku šifruje Bobovim javnim ključem { M }Bob , a potom dobijeni šifrat digitalno potpisuje [{M } Bob]Alisa. Međutim, Čarli je i dalje ljut i želi da se osveti. Čarli presreće poruku i blokira je. Obzirom da Čarli zna Alisin javni ključ on može da dođe do vrednosti {M } Bob. Istina ne može da je pročita, jer ne zna Bobov javni ključ. Čarli može sada ovu poruku da digitalno potpiše [{M } Bob]Čarli i šalje je Bobu. Bob nakon prijema zaključuje da je Čarli počeo da se bavi pronalascima. Gde Bob greši? Svako ko ima tajni ključ može da digitalno potpiše neku poruku, ali to ne znači da je on autor te poruke. Tako, na primer, Alisa je mogla da digitalno potpiše bilo koju eleektronsku knjigu koju je kupila na „Amazonu“, ali to ne znači da je ona autor knjige.
Očigledno je da oba postupka mogu da dovedu do određenih nedoumica. Opšte pravilo koje doprinosi rešavanju ovih i još nekih drugih problema je: Za digitalno potpisivanje i šifrovanje ne treba koristiti isti par ključeva. Jedan par ključeva se korsti za digitalni potpis i verifikaciju digitalnog potpisa a drugi par ključeva se korsti za šifrovanje i dešifrovanje.
Infrastruktura javnih ključeva Jedan od problema koji postoji u kriptografiji sa javnim ključem je utvrđivanje identiteta. Naime, ukoliko želite da uspostavite šifrovanu vezu sa nekim koga ne poznajete lično, ili razmenjujete podatke sa nekom bankom, kako možete da budete sigurni da javni ključ koji vam se nudi zaista pripada očekivanom vlasniku a ne nekom prevarantu koji se lažno predstavlja?
Rešenje je da postoji treća strana od poverenja (TTR), u koju imaju poverenja „sve“ strane u komunikaciji. TTR treba da garantuje za svakog od registrovanih učesnika i da na zahtev potvrđuje njegov identitet odnosno validnost javnih ključeva. Sertifikaciono telo (Certificate authority – CA ) je treća strana od poverenja Prvo treba napraviti sertifikat. Sertifikat je elektronski dokument koji sadrži:
 Podatke o vlasniku javnog ključa (Ime, prezime ili ime firme)  Adresu, ...  javni ključ  Vreme izdavanja i važenja sertifikata  ...
Setifikat digitalno potpisuje SA, svojim tajnim ključem. Savako ko zna javni ključ SA može da verifikuje digitalni potpis i da proveri podatke iz sertifikata. Proverom potpisa na sertifikatu se istovremeno utvrđuje i identitet vlasnika odgovrajućeg javnog (privatnog) ključa.
Međutim, na ovaj način se ne može utvrditi identitet izdavača sertifikata! SA mora da bude telo u koje postoji poverenje.
Infrastruktura javnog ključa (Public Key Infrastructure – PKI ) sastoji se od svih podsistema koji su neophodni za bezbednu upotrebu kriptografije sa javnim ključevima:
14
 Generisanje i upravljanje ključevima  Serifikaciona tela  Povlačenje sertifikata, itd.
Ne postoji opšti standard za PKI, već se u praksi primenjuje više modela od koji su najpoznatiji monopolski model i oligarhijski model.
Monopolski model
Ideja je da se napravi jedinstvena organizacija od poverenja, odnosno jedno sertifikaciono telo za sve korisnike. Sama organizacija bi podrazumevala hijerarhiju sertifikacionih tela, ali bi suštinski jedno sertifikaciono telo bilo odgovorno za sve. Tehnički gledano, model je izvodljiv ali je teško očekivati da će biti opšte prihvaćen u celom svetu. Nikada nije zađiveo. Pored toga veliki problem nastaje ako se takvo CA bilo kada kompromituje.
Oligarhijski model
Postoji više nezavisnih sertifikacionih tela. Korisnik može sam da odluči kojim sertifikacionim telima će ukazati poverenje a kojima ne.
Ovaj pristup se koristi kod savremenih internet pretraživača. Oni mogu da imaju 80 i više različitih sertifikata samo da bi se verifikovao jedan digitalni potpis!
Prednosti kriptografije sa javnim ključem Moguće je ostvariti servis poverljivosti bez deljenja tajni. Veoma je korisno i primenjljivo u komercijalnom svetu. Nema problema sa razmenom ključeva kao kod simetričnih kripto sistema.
Autentifikacija može da se obavi bez deljenja tajni.
Koristi se digitalni potpis kao dokaz o poreklu poruke. Nema potrebe da se krije javni ključ, ali je potrebno da se zna da je Alisin javni ključ stvarno njen javni ključ.
Nedostaci kriptografije sa javnim ključem Algoritmi su za 2-3 reda veličine sporiji, od algoritama koji se koriste u simetričnim kriptosistemima. Modularna (eksponencijalna) aritmetika je računarski zahtevna.
Zbog toga je uobičajena upotreba: sistemi sa javnim ključem se koriste za razmenu simetričnog ključa, a potom se prelazi na simetričnu kriptografiju-hibridni sistemi.
Ključevi su duži:
 1024 bita (RSA) prema 128 bita (AES )
Sigurnost se zasniva na pretpostavkama koje nisu dokazane: Šta ako se reši problem faktorizacije?
15
Dodatak Modularna aritmetika Za cele pozitivne brojeve x i N, x (mod N), čita se x po modulu N, predstavlja ostatak (r) pri deljenju x sa N :
x (mod N) = r    x = kN + r  , gde je k neki ceo broj
Moguće vrednosti ostatka r, prilikom deljenja sa N su: 0, 1, 2, ...,  N-1.
Primer: 7 (mod  6)  = 1 ili 7 = 1 (mod  6), jer je 7=1∙6+1 33 (mod  5)  = 3   ili 33 = 3 (mod  5), jer je 33=6∙5+3 33 (mod  6)  = 3   ili 3 = 33 (mod  6), jer je 33=5∙6+3
51 (mod 17)  = 0   ili 51 = 0 (mod 17) , jer je 51=3∙17+0
17 (mod  6)  = 5   ili    17 = 5 (mod  6), jer je 17=2∙6+5
U prethodnim primerima su predstavljena dva načina zapisivanja Svojstva modularne aritmetike Za modularno sabiranje  važi:           mod mod mod mod a b N a N b N N   
Primer: (3 + 5) (mod 6) = 2
(2 + 4) (mod 6) = 0
(3 + 3) (mod 6) = 0
(7 + 12) (mod 6) = 19 (mod 6) = 1
(7 + 12) (mod 6) = (7 (mod 6)+ 12 (mod 6))(mod 6) =  (1 + 0) (mod 6) = 1 Za modularno množenje važi:           mod mod mod mod a b N a N b N N   
Primer: (3 ∙ 4) (mod 6) = 0  (2 ∙ 4) (mod 6) = 2  (5 ∙ 5) (mod 6) = 1  (7 ∙4) (mod 6)= 28 (mod 6) = 4 (7 ∙ 4) (mod 6)= (7 ∙ 4) (mod 6) (7  (mod 6)  ∙ 4 (mod 6) ) (mod 6) = 4
16
Za modularno stepenovanje važi:       mod mod mod k k a N b a N b N   
Primer: 8 (mod 6) = 2  82 (mod 6) = 22 (mod 6) = 4 84 (mod 6) = 24 (mod 6)= 4 Modularna inverzija ima važnu ulogu u kriptografiji sa javnim ključem.
U klasičnoj aritmetici, aditivna inverzija broja h, je vrednost koju treba sabrati sa brojem h kako bi se dobio rezultat 0. Aditivna inverzija broja x po modu N, je broj koji treba sabrati sa x da bi mod tog zbira bio jednak 0. Aditivna inverzija broja h po modu N, se odnačava sa -x.
Primer: Kolika je aditina inverija 4 (mod 6)? Odgovor: 2  -2 (mod 6)=4, jer je (2+4) (mod 6) = 0 Multiplikativna inverzija x po modu N, je broj koji treba pomnožiti sa x da bi mod tog proizvoda bio jednak 1. Multiplikativna inverzija broja h po modu N, se odnačava sa x-1. Primer: Kolika je multiplikativna inverzija 5 (mod 7) ?
Odgovor: 3,  3-1 (mod 7) = 5, jer je (3 ∙ 5) (mod 7) = 1
5-1 (mod 6) = 5, jer je (5 ∙ 5) (mod 6) = 1
2-1 (mod 6) = ?, Ni jedna od vrednosti iz skupa (0, 1, 2, 3, 4, 5) ne odgovara rešenju. Očigledno je da modularna multiplikativna inverzija ne postoji za svaki broj. Da bi odgovorili na pitanje kada postoji multiplikativna inverzija potrebno je uvesti još ... Prosti brojevi Prost broj je ceo broj koji ima samo dva delioca: 1 i samog sebe. Po dogovoru, samtra se da 1 nije prost broj. Tako su prosti brojevi: 2, 3, 5, 7, 11, 13, 17, 19, 23, ... Nema pravila na osnovu kojeg su raspoređeni prosti brojevi u skupu celih brojeva, ali je poznato da prostih brojeva ima beskonačno mnogo. Za broj koji nije prost kaže se da je složen.
Neka su x i y dva cela broja. Najveći zajednički delilac (nzd) brojeva x i y je najveći broj d takav da‚ (d deli x) i (d deli y).
Primer: nzd(3, 16) = 1 nzd(28, 8) = 4, bez obzira što ni 28 ni 8 nisu prosti brojevi.
17
Ukoliko je nzd(x, y) = 1, kaže se da su x i y uzajamno prosti.
Kako je nzd za bilo koja dva prosta broja jednak 1, sledi da su dva prosta broja istovremeno i uzajamno prosta.  Može se pokazati da x-1 (mod y) postoji samo ako su x i y uzajamno prosti.
x-1 (mod y) se lako nalazi (ako postoji) korišćenjem Euklidovog algoritma. U nastavku dat kod u programskom jeziku S za pronalaženje nzs:
   int gcd(int a, int b) {  if(a==0) return b;    while(b != 0)    {       if(a > b)           a=a-b;       else           b=b-a;    }    return a; } Ojlerova funkcija Ojlerova funkcija φ(n), definisana je kao broj pozitivnih celih brojeva manjih od n, koji su uzajamno prosti u odnosu na n.
Primer: φ(4) = 2, jer je 4 uzajamno prost sa 3 i 1. φ(5) = 4 jer je 5 uzajamno prost sa 1,2,3 i 4 φ(12) = 4... Ako je p prost broj onda je
φ(p) = p – 1
jer je prost broj uzajamno prost sa svim ostalim brojevima koji su manji od njega.
Iz definicije sledi da ako je p prost broj onda je
φ(pn) = pn – pn – 1=(r -1) pn – 1
Ako su m i n uzajamno prosti, onda oni nemaju zajedničkih sadržalaca većih od 1, pa onda važi
φ(mn) = φ(m) φ(n).
Iz prethodnog zaključka sledi da ako su p i q prosti onda važi:
φ(pq) = φ(p) φ(q)= (p -1)(q -1)
18
Za svaki pozitivan broj n i svako x koje je uzajmno prosto sa n važi x φ(n) =1 (mod n) što se može zapisati i kao x φ(n) (mod n) =1 Osnovna teorema aritmetike: Svaki pozitivan ceo broj N >1,  može da se predstavi kao proizvod jednog ili više prostih brojeva u sledećem obliku:
1 2 1 2 nee e nN p p p      o Ovaj postupak se naziva faktorizacija broja N. o Faktorizacija broja je jedinstvena. Primer: 6647 = 172 23     90 = 2 ∙ 32 ∙ 5 Problem faktorizacije broja je u opštem slučaju težak problem. Jedan od načina određivanja gcd dva broja svodi se na faktorizaciju oba broja. Donošenje odluke da li je broj prost ili nije, lakši je problem od faktorizacije.


Integritet i heš funkcije
priredio: dr Zoran Banjac
2014.

2
Sadržaj Uvod ...................................................................................................................................................3 Integritet i autentifikacija ..........................................................................................................3 Autentifikacija kod simetričnih kripto sistema ..................................................................3 Autentifikacija bez šifrovanja prouke ................................................................................4 Kriptografske heš funkcije............................................................................................................5 Poređenje šifrovanja i heš funkcija ......................................................................................5 Svojstva kriptografskih heš funkcija ......................................................................................6 Rođendanski problem .................................................................................................................7 Primeri heš funkcija ................................................................................................................8 MD5 heš funkcija .....................................................................................................................8 SHA heš funkcija ......................................................................................................................9 Primena heš funkcija .............................................................................................................. 10 Heš vrednost, integritet i autentifikacija .......................................................................... 10 Šifrovanje heš vrednosti simetričnim algoritmom ........................................................ 10 Šifrovanje heš vrednosti asimetričnim algoritmom ...................................................... 11 Digitalni potpis i heš funkcije ............................................................................................ 12
HMAC ........................................................................................................................................... 13 Opis algoritma ....................................................................................................................... 13 Deljenje tajni .................................................................................................................................. 14

3
Uvod Servis poverljivosti i zaštita od pasivnih napada (prisluškivanje, na promer) se može ostvariti šifrovanjem, bilo da se koriste sistemi sa simetričnim ili sa javnim (i tajnim) ključem. Aktivni napadi obuhvataju više akcija, kao što su delimična izmena poruke, zamena poslate poruke novom porukom, ili slanje poruke uz lažno predstavljanje. Zaštita od ovakvih napada može da se realizuje kroz integritet i autentifikaciju poruke.
Integritet i autentifikacija Pod integritetom i utentifakcijom se podrazumeva skup postupaka koji treba da obezbede da prijemna strana ima podatke na osnovu kojih može na pouzdan način da odredi:  Da poruka na prenosnom putu nije izmenjena (slučajno ili namerno).  Bez obzira što napadač ne može da dešifruje poruku, on može da izmeni poruku (na primer, da izmeni red blokova šifrata), što u nekim slučajevima može da nakon dešifrovanja dovede do smislene, ali pogrešne, poruke (integritet).  Ko je poslao poruku (poreklo poruke- autentifikacija). Treba sprečiti Trudi da pošalje poruku Bobu i da se pritom lažno predstavi kao Alisa.
Pored toga poželjno je da postoji mogućnost da se odredi  Vreme kada je poruka poslata
Poslednji zahtev je važan jer legalna poruka može da bude snimljena i kasnije ponovo poslata, bilo da je šalje Ailisa ili Trudi.
Primer: Alisa je poslala nalog banci da sa njenog računa uplati na Bobov račun 100$. Alisa je registrovani korisnik, poruku je šifrovala javnim ključem banke i potom je digigitalno potpisala svojim tajnim ključem. Banka, na osnovu digitalnog potpisa, može bude sigurna da je poruku poslala Alisa, da potom dešifruje poruku i izvrši nalog. Međutim, Alisa nakon sat vremena pošalje istovetnu poruku banci. Banka će na Bobov račun prebaciti još 100$. Nakon nekog vremena, Alisa tvrdi da je poslala samo jednu, a ne dve poruke. Ukoliko u poruci nema podatka o vremenu slanja (ili rednom broju poruke) banka ne može da ospori Alisinu tvrdnju jer je banka imala mogućnost da iskopira tu poruku. Autentifikacija kod simetričnih kripto sistema Kod simetričnih kripto sistema nije jednostavno ostvariti autentifikaciju. Osnovni problem se na zasniva na činjenici da obe strane poznaju isti tajni ključ. Kada bi Alisa koristila isključivo simetričnu kriptografiju za izdavanje naloga banci (da prebaci Bobu novac) banka bi bila u problemu. Bez obzira što banka poseduje njen nalog, Alisa bi mogla da ga ospori. Naime, banka takođe zna tajni ključ, pa je mogla da „napiše“ istovetan nalog.
Ako postoji poverenje između strana u komunikaciji, što u komercijalnom sektoru obično nije slučaj, softver za detekciju greške može da registruje moguće izmene na prenosnom putu. Ako poruka sadrži podatak o vremenu slanja (timestamp), može se otkriti pokušaj ponovnog slanja iste poruke.
4
Autentifikacija bez šifrovanja prouke Pretpostavimo da su se Alisa i Bob dogovorili oko izbora simetričnog algoritma i da su razmenili ključ šifrovanja na siguran način. Alisa i Bob, u ovom slučaju, nemaju potrebu za servisom poverljivosti, ali žele da budu sigurni da poruka neće biti promenjena na prenosnom putu. Ako se pretpostavi da postoji uzajamno poverenje između Alise i Boba i da samo oni znaju tajnu vrednost ključa K, moguće je obezbediti integritet poruke. Postupak je sledeći (videti sliku 5.1):
Slika 5.1 Integritet poruke na osnovu MAS vrednosti
 Alisa šifruje poruku M nekim blokovskim (npr. AEЅ) algoritmom i ključem K. Pamti samo polednji blok šifrata i obeležava ga kao MAS.  Alisa šalje Bobu poruku M (otvorenu) i vrednost MAS.  Bob prima poruku M i vrednost MAS.  Bob zna ključ K, (AEЅ) algoritam i može da izračuna MAS vrednost primljene poruke.  Ukoliko su primljena vrednost MAS i izračunata MAS vrednost jednake, Bob može da bude siguran da poruka nije promenjena na prenosnom putu.  Bob znako je poslao poruku, jer samo onaj ko zna ključ K, može pravilno da izračuna MAS vrednost. Podsetimo da mora da postoji poverenje između Alise i Boba.   Ukoliko u poruci M postoji podatak o vremenu slanja (rednom broju poruke i sl.) Bob može da bude siguran da poruka nije ponovljena.
Šematski prikaz je dat na slici 5.2
Slika 5.2 Integritet poruke na osnovu MAS vrednosti
5
Kriptografske heš funkcije Heš funkcija je jednosmerna funkcija koja za ulazni podatak (poruka, fajl,...) proizvoljne konačne dužine kao izlaznu vrednost daje niz fiksne dužine.
 Ulaz: Poruka proizvoljne konačne dužine. U nekim slučajevima je ograničena maksimalna dužina poruke!  Izlaz: Heš vrednost uvek iste konačne dužine.
Osnovna namena kriptografskih heš funkcija je primena u postupcima za autentifikaciju poruke. Pri tome je posebno važno istaći da se (kriptografske) heš funkcije ne koriste za šifrovanje. Poređenje šifrovanja i heš funkcija Funkcije ili algoritmi za šifrovanje (i dešifrovanje) su u osnovi dvosmerne funkcije. Istina, potrebno je poznavati tajnu vrednost (ključ) da bi se izračunala funkcija u oba smera. Dužina poruke i šifrata je po pravilu jednaka, preciznije iz šifrata se, nakon dešifrovanja, može jednoznačno odrediti dužina poruke (kod blokovskih šifri šifrat može biti duži zbog dopisivanja u poslednjem bloku).
S druge strane, heš funkcije su jednosmerne. To znači da se iz poruke može izračunati heš vrednost, ali da se iz heš vrednosti ne može izračunati poruka. Heš vrednost je uvek iste dužine (na primer, 128 bita) bez obzira koliko je poruka dugačka.
Poređenje šifrovanja i računanja heš vrednosti je prikazano na slici 5.3
Slika 5.3 Poređenje šifrovanja i računanja heš vrednosti
Predstavimo nekoliko različitih poruka sa: h, h’, x’’..., funkciju pomoću koje se računa heš vrednost sa h i dobijene heš vrednosti y =h(x), y’ =h(x’) i y’’ =h(x’’). Računanje heš vrednosti je prikazano na slici 5.4.
6
Slika 5.4 Preslikavanje iz skupa poruka u skup heš vrednosti
Funkcija h je funkcija kompresije sa gubicima, jer od poruke, h, proizvoljne dužine (na primer, 1MV) daje heš vrednost, fiksne dužine (na primer, 128 bita). Očigledno je da je broj mogućih ulaznih vrednosti, teorijski gledano, neograničen, dok je broj izlaznih vrednosti ograničen (u ovom primeru 2128). Zbog toga sledi da će više različitih ulaznih poruka dati istu heš vrednost. Ova pojava se naziva kolizija:
 h(x) = h(x’), xx’ - kolizija
Heš funkcije imaju širu primenu, ali se od heš funkcija koje se primenjuju u kriptografiji (kriptografske heš funkcje) očekuju dodatna svojstva. Svojstva kriptografskih heš funkcija 1. Kriptografska heš funkcija treba da obezbedi kompresiju. Heš vrednost treba da bude male dužine. 2. Kriptografska heš funkcija treba da bude efikasna. h(x) treba da se lako računa za bilo koje x.  3. Kriptografska heš funkcija treba da bude jednosmerna. Za zadatu heš vrednost y, treba da je teško naći bilo koje x takvo da je h(x) = y. Koliko teško? Problem treba da je podjednako težak kao potpuna pretraga: probati sve moguće vrednosti h, i proveriti da li je njegova heš vrednst jednaka traženoj.
Primer:
SHA-1 (jedna od standardizovanih heš funkcija) ima izlaz dužine 160 bita. Neka postoji hardver takav da je moguće probati 234 vrednosti (različitih poruka h) u sekundi. Sledi da će se za godinu dana ispitati 289 različitih poruka h, pa je potrebno 271 godina da se invertuje SHA-1 heš vrednost postupkom potpune pretrage.
4. Otpornost na kolizije
Za zadato x i h(x), treba da je praktično nemoguće naći h’  x, takvo da je h(h’) = h(x) (naziva se slaba otpornost na kolizije).
Treba da je praktično je nemoguće naći bilo koje x i h’, h’  x takve da je h(x) = h(h’), (naziva se jaka otpornost na kolizije).
7
5. Lavinski efekat. Male promene poruke treba da uslove veoma veliku promenu heš vrednosti (promena jednog bita poruke treba da ima za posledicu promenu bar polovine vrednosti bita heš vrednosti).
Kolizije postoje ali heš funkcija treba da je projektovana tako da ih je teško pronaći! Rođendanski problem Problem 1 Neka se u prostoriji nalazi n osoba. Na slučajan način se odredi jedan datum u godini. Treba odgovoriti na pitanje koliko najmanje treba da bude n da bi verovatnoća da neka nasumično odabrana osoba iz grupe ima rođendan koji se poklapa sa odabranim datumom?  Kolika je verovatnoća da neka (jedna) na slučajan način odabrana osoba nema rođendan istog datuma kao i onaj koji je odabran?  Rešenje: 364/365 (broj povoljnih/broj mogućih događaja).
Kolika je verovatnoća da ni jedna od n osoba nema rođendan istog datuma kao i onaj koji je odabran?  Rešenje: (364/365)n  (prva osoba nema I druga nema .... I n-ta nema)
Kolika je verovatnoća da bar jedna od n osoba ima rođendan istog datuma kao i onaj koji je odabran?  Rešenje:  1  (364/365)n (zbir svih verovatnoća je jednak 1)
Koliko mora biti n da bi verovatnoća da bar jedna osoba ima rođendan istog datuma kao i onaj koji je odabran, bila veća ili jednaka 1/2?   Rešenje: 1/2  1 -(364/365)n, odavde je n   253
Potrebno je da u grupi bude najmanje 253 osobe da bi bilo verovatno (više od 50%) da neka od njih ima rođendan nekog unapred odabranog datuma.
Problem 2
Koliko mora biti najmanje ljudi u sobi, da bi verovatnoća da dvoje ili više ljudi ima rođendan istog datuma, bila  1/2? Da bi odgovorili na ovo pitanje treba poći od jednostavnijeg problema. Kolika je verovatnoća da niko od n osoba u sobi nema rođendan istog datuma?  Odaberemo prvu od n osoba i odredimo njen rođendan. Verovatnoća da druga osoba nema rođendan istog datuma je 364/356. Verovatnoća da treća osoba nema rođendan koji se poklapa sa prvom i drugom osobom je 363/365, ..., verovatnoća da n-ta osoba nema rođendan koji se poklapa sa bilo kojim od prethodnih n-1 je (356- n+1)/365 Rešenje: 364/365  363/365  … (365 n  +1)/365
Kolika je verovatnoća da od n osoba bar dvoje (dvoje ili više ljudi) ima rođendan istog datuma?   Ovo je suprotan događaj od prethodnog, a kako ukupna verovatnoća mora biti jednaka 1,  Rešenje: 1  364/365  363/365   (365 n  +1)/365  Koliko mora biti najmanje ljudi u sobi, da bi verovatnoća da bar dvoje ljudi ima rođendan istog datuma, bila  1/2?  Rešenje: 1/2  1  364/365  363/365   (365 n  +1)/365   n  23
8
Sledi, ukoliko se na jednom mestu nađe 23 ili više osoba, da postoji velika verovatnića (veća od 50%) da će bar dve osobe imati rođendan istog dana. Na prvi pogled je ovaj rezultat iznenađujući pa ga neki autori nazivaju paradoksom (rođendanski paradoks). Da li je rezultat zaista iznenađujući? Možda i nije. Jedna og grubih aproksimacija kaže da se do rešenja rođendanskog problema može doći ako se izračuna kvadratni koren iz broja dana u godini (broj mogućih rođendana)  n = √(365) ≈ 19. Pravo pitanje je kakva veza postoji između rođendanskog problema i kolizija kod heš funkcija?  Ako heš funkcija, h(x), daje izlaz dužine n bita, onda postoji 2n različitih heš vrednosti. Trudi će pokušati da pronađe dve poruke koje daju istu heš vrednost. Ukoliko nema dodatnih informacija preostaje joj potpuna pretraga, odnosno da proba sve moguće poruke. Međutim, pokazano je da će nakon √(2n) = 2n/2 pokušaja, Trudi verovatno doći do željenog rezultata (dve različite poruke koje daju istu heš vrednost).  Posledica: bezbedan n bitski simetrični ključ zahteva  2n/2 = 2n-1 operacija da bi se razbio, dok je za isti posao u slučaju bezbednog n  bitskog heša potrebno 2n/2 operacija. Dužina heš vrednosti mora biti 2 puta veća od dužine ključa simetričnog sistema da bi se postigla ista sigurnost. Primeri heš funkcija Kroz prethodni period se izdvojilo nekoliko heš funkcija koje su standardizovane i koje su se koristile u praksi. Većina od njih je zasnovana na kostrukciji koja se koristi kod blokovskih algoritama. Jedna od najduže korišćenih heš funkcija je MD5 (Message Digest) MD5 heš funkcija Dizajnirana je 1991. godine (u isto vreme kada i servis WWW) i naslednik je prethodnog algoritma koji se zove MD4. Nešto je složenije konstrukcije od svog prethodnika i zbog toga nešto sporija. Heš vrednost MD5 algoritma je dužine 128 bita, za ulaz proizvoljne dužine.
Blok šema MD5 heš funkcije je prikazana na slici 5.5.
Slika 5.5 Blok šema MD5 heš funkcije
9
Ukoliko ukupna dužina poruke nije deljiva sa 512, potrebno je dopisati jednu 1 i odgovarajući broj 0 tako da posledei blok ima dužinu 448. U preostalih 64 bita (od 512) treba upisati stvarnu dužinu poruke pred dopisivanja. Poruka sada može da se podeli na više blokova dužine 512 bita.
Potrebno je inicijalizovati 4 registra (wordA,wordV, wordC i wordD) sa konstantnim vrednostima (videti sliku 5.5) i potom se računa međurezultat koji nastaje obradom prvog bloka teksta uz dodatni ulaz koji predstavljaju registri. Obrada se obavlja u 4 runde, koje su slične strukture ali imaju različite logičke funkcije. Dobijeni međurezultat je dužine 128 bita i predstavlja ulazni parametar, zajedno sa drugim blokom teksta za obradu. Postupak se tako ponavlja sve dok se ne obrade svi blokvi ulaznog teksta, a poslednjih 128 bita predstavlja heš vrednost.
Već 1996. godine su otkriveni neki od nedostataka MD5 heš funkcije, mada u to vreme nisu predstavljali realnu opasnost. 2004 je dokazano da je moguće naći kolizije u veoma kratkom periodu. Danas postoje efikasni algoritmi koji na prosečnom računaru mogu da pronađu kolizije kod MD5 heš funkcije za manje od jednog minuta. Zbog toga se ova heš funkcija već duže vremena ne preporučuje za upotrebu.  SHA heš funkcija SHA-1 (secure hash algorithm) je algoritam koji je dizajnirla NSA 1995. godine. Deo je familije SHA algoritama (SHA-0 do aktuelnog SHA-3). Veoma je sličan svom prethodniku SHA-0, koji je veoma brzo pokazao slabosti, tako da gotovo nije imao ozbiljniju praktičnu primenu.
Heš vrednost koju generiđe SHA-1 algoritam je dužine 160 bita (20V) i najčešće se predstavlja kao heksadecimalni broj sa 40 cifara. Obrada je iterativna i obavlja se u 80 rundi. Našao je veliku primenu u mnogim sigurnosnim protokolima. 2005. godine je objavljeno da postoje sigurnosni propusti u SHA-1 algoritmu i on se danas ne preporučuje za upotrebu.
SHA-2 algoritam je standardizovan 2001. godine uz uvođenje značajnih razlika u odnosu na prethodnika. U prvoj verziji su objavljene varijante SHA-256, SHA-384 i SHA-512 (brojevi označavaju dužine heš vrednosti), a 2004. i varijanta SHA-224. Svi varijante se zajedno nazivaju SHA-2 heš funkcijom. Ova heđ funkcija je doživela nekoliko revizija i još uvek se smatra sigurnom.
Ipak, kao mera predostrožnosti, 2007. godine objavljen je javni konkurs (National Institute of Standards and Technology, USA) za novu heš funkciju. Nakon više krugova selekcije izabran je algoritam pod radnim nazivom Keccak, koji je 2013. godine standardizovan pod imenom  SHA-3.
Danas postoje mišljenja nekih vodeđih kriptografa da je konkurs bio preeuranjen, odnosno da je novi algoritam doneo poboljšanja ali ne toliko revolucionarna koja bi obezbedila dugoročnu primenu algoritma.
Heš funkcije SHA-2 i SHA-3 se danas smatraju sigurnim i koriste se u mnogim aplikacijama i protokolima.
10
Primena heš funkcija Heš funkcije se najčešće primenjuju u servisima koji treba da obezbede:
 Integritet  Autentifikaciju   Digitalni potpis
Ukoliko se ne razmatra mogućnost aktivnog napada, heš funkcija može da se koristi za proveru da li je poruka na prenosnom putu promenjena, na primer zbog grešaka u prenosu. Primer jednog takvog postupka je dat na slici 5.6. Neka nije potreban servis poverljivosti i neka Alisa želi samo da zna da poruka nije promenjena na prenosnom putu. Bob želi da pošalje poruku M. Pre slanja, Bob će izračunati heš vrdnost poruke, h(M), i poslati Alisi M i h(M). Heš algoritam (funkcija) je javna. Alisa nakon prijema poruke M, može da izračuna njenu heš vrednost. Sada Alisa može da uporedi primljenu i izračunatu heš vrednost. Ukoliko su one jednake, Alisa je sigurna da poruka nije (zbog grešaka u prenosu) promenjena na prenosnom putu. Međutim, ovaj pristup nije dobar ukoliko Trudi želi da promeni poruku. Naime, Trudi može da promeni poruku, a kako poznaje heš funkciju, može i da izračuna heš vrednost koja odgovara novoj poruci. Alisa nakon prijema izmenjene poruke i izmenjene heš vrednosti ne može da primeti prevaru.
Slika 5.6 Integritet i heš funkcije
Da bi sprečili Trudi da realizuje loše namere heš vrednost može da se šifruju. Pri tome može da se šifruje i poruka, ali taj slučaj sada neće biti razmatran. Heš vrednost, integritet i autentifikacija Istovremeni servisi integriteta i autentifikacije mogu da se postignu na više načina:
 šifrovanjem heš vrednosti simetričnim algoritmom  šifrovanjem heš vrednosti asimetričnim algoritmom  uvođenjem tajne vrednosti, bez šifrovanja
Šifrovanje heš vrednosti simetričnim algoritmom Bob i Alisa su se dogovorili oko izbora simetričnog algoritma i na siguran način razmenili ključ K. Bob računa heš vrednost poruke M, koju želi da pošalje Alisi. Dobijenu heš vrednost Bob šifruje simetričnim algoritmom (npr. AEЅ) upotrebom ključa K. Bob sada šalje Alisi poruku M (otvoreni tekst)i šifrovanu heš vrednost. Alisa nakon prijema može da dešifruje šifrat i da dobije heš vrednost koju je poslao Bob. Takođe, Alisa može da
11
izračuna heš vrednost dobijene poruke M. Ukoloko se ispostavi da su izračunata i dobijena heš vrednost jednake, Alisa zaključuje:
 Poruka nije promenjena na prenosnom putu (integritet)  Poruku je poslao Bob. Bob zna kljč K, pa je samo on mogao da šifruje heš vrednost. (autentifikacija)
Ipak autentifikacija je „interna“. Naime ovde se očekuje da postoji poverenje između Alise i Boba. Alisa ne bi nekom trećem mogla da dokaže da je Bob poslao poruku, jer i Alisa zna ključ K, pa je i ona mogla da bude autor te poruke. Postupak slanja je predstavljen na slici 5.7.
Slika 5.7 Šifrovanje heš funkcije simetričnim algoritmom
Zašto je Trudi osujećena? Trudi može da promeni poruku na prenosnom putu, može i da izračuna heš vrednost nove poruke, ali ona ne zna ključ tako da novu vrednost ne može da šifruje (barem ne na ispravan način). Alisa će nakon prijema to lako primetiti. Šifrovanje heš vrednosti asimetričnim algoritmom Scenario je isti kao i u prethodnom slučaju, samo se ovde heš vrednost digitalno potpisuje Bobovim tajnim ključem. Postupak je prikazan na slici 5.8.
Slika 5.8 Šifrovanje heš funkcije asimetričnim algoritmom
I u ovom slučaj je moguće da se obezbedi servis integriteta i autentifikacije. Alisa nakon provere digitalnog potpisa može da bude sigurna da je Bob poslao poruku, jer samo on zna svoj tajni ključ, a to može da dokaže i bilo kom drugom.
Trudi i dalje ne može da podmetne poruku a da ne bude primećena.
U oba opisana slučaja se koristi neki od algoritama šifrovanja. Alogritmi mogu da budu licencirani, podložni zakonskim ograničenjima i sl. i zbog toga ne moraju uvek biti poželjeni za primenu. Sledeći scenario (videti sliku 5.9) predstavlja načina da se pošalje heš vrednost bez šifrovanja, a da Trudi ne može da promeni poruku na prenosnom putu i da pri tome ostane neopažena.
12
Slika 5.9 Tajna vrednost i heš funkcije
Potrebno je da Alisa i Bob razmene tajnu vrednost (npr ključ) unapred, sigurnim putem. Bob Pre računanja heš vrednosti na poruku dopiše tajnu vrednost. Tajna vrednost može jednostavno da se dopiše ili da se ustanovi neka složenija funkcija koja će rasporediti bite tajne vrednosti u poruku. Heš vrednost se računa na modifikovanoj poruci. Bob šalje početnu (nemodifikovanu) poruku i dobijenu heš vrednost. Alisa nakon prijema poruke dopisuje tajnu vrednost i računa heš vrednost. Ukoliko se dobijena heš vrednost i primljena heš vrednost slažu, potvrđen je integritet i („interna“) autentifikacija.
Trudi ostaje bespomoćna. Digitalni potpis i heš funkcije Kod direktne primene digitalnog potpisa Alisa digitalno potpisuje celu poruku M. Veličina digitalnog potpisa je jednaka veličini poruke. Da bi Bob verifikovao digitalni potpis, potrebno je da od Alise dobije i poruku M i digitalno potpisanu poruku S = [M ]Alisa.  Bob proverava da li je M = {S }Alisa  Na taj način se zauzima duplo veći kapacitet prenosnog puta nego da se prenosi samo poruka. S druge strane, ukoliko je poruka velika, postupak računanja digitalnog potpisa, takođe, može da bude zahtevan. Umesto toga, moguće je izračunati heš vrednost poruke h(M), gde je dužina izlaza funkcije h(M), mnogo kraće od M. Postupak je sledeći: Alisa šalje Bobu M i S = [h(M)]Alisa .Alisa je digitalno potpisala (svojim tajnim ključem) heš vrednost poruke, a ne celu poruku- Bob proverava da li je h(M) = {S} Alisa . Bob je dobio poruku M, i može da izračuna heš vrednost dobijene poruke. S druge strane, Bob poznaje Alisin javni ključ i može da izračuna {S} Alisa, odnosno da dobije heš vrednost koju je Alisa izračunala pre digitalnog potpisivanja. Poređenjem izračunate heš vrednosti poruke i heš vrednosti dobijene iz digitalnog potpisa, Bob može da utvrdi da li poruka menjana na prenosnom putu i ko je poslao poruku (videti sliku 5.10).
13
Slika 5.10 Tajna vrednost i heš funkcije
Primena heš funkcija nije ograničena samo na digitalni potpis. Mogu se upotrebljavati i kod čuvanja lozinki. Prilikom prijave na računar veoma često se traži unos lozinke. Uneta lozinka potom treba da se verifikuje. Ukoliko se na disku računara nalazi fajl u kom je zapisana lozinka, onda postoji opasnost da neko (administrator, drugi korisnici računra) i sl. pročitaju tu loziku i da je kasnije zloupotrebe. Jedno od rešenja ja da se na disku čuvaju samo heš vrednosti lozinki. Nakon unosa lozinke računa se njena heš vrednost i poredi se zapisanom heš vrednošću. Ukoliko napadač sazna heš vrednost, on ne može na osnovu heš vrednosti da odredi lozinku.
HMAC Poseban način za računanje MAS (message authentication code) bez upotrebe algoritama za šifrovanje se naziva NMAS (N od hash). Osnovna ideja je da se obezbedi servis integriteta i autentifikacije a da sama funkcija bude zasnovana na upotrebi heš funkcija a ne algoritama za šifrovanje. Na slici 5.5 je prikazan jednostavan pristup u kome se vrednost ključa dopisuje na poruku pre računanja heš vrednosti. Međutim, pokazalo se da ovakav pristup kod primene nekih heš funkcija ima slabosti.
Osnovni motiv za dizajn HMAC algoritma je da se kriptografske heš funkcije se izvršavaju brže od simetričnih algoritama za šifrovanje (DES, AEЅ...). Osim toga kôd kriptografskih heš funkcija je javno dostupan, što ne mora biti slučaj sa šifarskim algoritmima ili oni često imaju izvozna i slična zakonska ograničenja.
Kod dizajna se zahteva da
 Koriste, bez modifikacije, dostupne heš funkcije.   Sačuvaju originalna svojstva heš funkcije.   Koriste ključeve na jednostavan način.   Analiza kriptografskih svojstava bude jasna.
Izbor heš funkcije je proizvoljan ali treba voditi računa da kriptografska snaga NMAS algoritma zavisi od izabrane heš funkcije, dužine heđ vrednosti kao i od veličine i kvaliteta izabranog ključa. Opis algoritma Neka je h bilo koja heš funkcija. Poruka je bilo koje dužine a heš vrednost uvek ima  dužinu N (što zavisi od izbora heš funkcije). K je tajni ključ, koji se koristi za autentifikaciju, i
14
poznat je obema stranama u komunikaciji. Ključ ne treba da ima veću dužinu 64 bajta, tj. od dužine bloka heš funkcije. Ako je ključ manje dužine, dopunjava se nulama. Definisana su dva fiksna niza dužine po 64 bajta  ipad = 0x36 0x36......0x36 (64 V)   opad= 0x5S 0x5S......0x5S (64 V) Funkcija HMAC ima 2 parametra: Poruku M, i ključ K. HMAC(M, K) = h(K  opad || h(K  ipad || M)) Koraci algoritma 1. Odabrati ključ K. Po potrebi dopisati nule da bi K imao 64 bajta. 2. Izračunati K  ipad.  3. Na niz dobijen u koraku 2 dopisati poruku M.  4. Izračunati heš vrednost niza dobijenog u koraku 3. 5. Izračunati K  opad  6. Dopisati heš vrednost dobijenu u koraku 4 na 64 bajta dobijena u koraku 5. 7. Izračunati heš vrednost niza dobijenog u koraku 6. HMAC algoritam je šematski prikazan na slici 5.11.
Slika 5.10 Tajna vrednost i heš funkcije
Deljenje tajni Pretpostavimo da postoji tajna Ѕ i da želimo da je Alisa i Bob dele tako:
Da pojedinačno ni Alisa ni Bob ne mogu da dođu do tajne
Da zajedno Alisa i Bob mogu jednostavno da rekosnstruiši tajnu.
Na prvi pogled problem izgleda složen ali je rešenja prilično jednostavno. Dovoljno je kostruisati pravu i neka je tajna vrednost tačka (0, Ѕ) u kojoj prava seče u osu (slika 5.11).
15
Slika 5.11 Deljenje tajni između 2 entiteta, 2 od 2
Kako je dovoljno znati dve tačke da bi u potpunosti definisali pravu, mogu se Alisi dati koordinate (h0,u0) a Bobu koordinate (h1,u1). Ni jedno od njih dvoje ne može samostalno da definiše pravu, pa ni njen odsečak na u  osi, ali to zajedno mogu da urade. Na sličan način moguće je dati koordinate treće tačke na pravoj Čarliju. U tom slučaju se postiže da je dovoljno da sarađuju 2 od 3 osobe da bi se došlo do rešenja (slika 5.12).
Slika 5.12 Deljenje tajni između 3 entiteta, 2 od 3
Izborom složenije krive, postiže se veći broj osoba koji je minimalno potreban da se rekonstruiše tajna. Tako je parabola određena sa najmanje tri tačke. Tajna se može podeliti između Alise, Boba i Čarlija i potrbna je njihova saradnja da bi se došlo do tajne vrednosti (videti sliku 5.13)
Slika 5.13 Deljenje tajni između 3 entiteta, 3 od 3
Kako ova saznanja mogu da se primene u kriptografiji?
Često se javlja potreba da se pod odrešenim okolnostima dešifruju poruke nezavisno od želje njihovih vlasnika. Na primer, sud može da zahteva dešifrovanje nekih dokumenata u sudskom potupku, i ta odluka ne sme da zavisi od volje optuženog, koji najverovatnije neće pristati da sarađuje, Sud bi zbog toga mogao da zahteva od svakog ko koristi šifrovanje za
16
zaštitu privatnosti da deponuje svoj ključ. S druge strane, vlasnik ključa, koji nije napravio nikakav prekršaj ima pravo na privatnost i ne mora da veruje da ključ neće biti zloupotrebljen. Rešenje (barem terijsko) je da se podatak o tajni (ključ) deponuje na više različitih mesta, prema opisanom pravilu i na taj način se smanjuje verovatnoća da će više pojedinaca istovremeno zloupotrebiti poverenje i narušiti privatnost. U slučaju zakonske potrebe oni će sarađivati sa sudom.