Kratak kurs kriptografije - 1. deo

gost 390446

Iskusan
Poruka
5.726
Dragi moji forumasi,
hvala na pokazanom interesovanju. Nadam se da necu da vas izneverim :)
Necu da tupim mnogo, nego da sto pre predjem na stvar. Ali, moramo samo da dogovorimo workflow naseg kursa:
1. Ja napisem post, gde objasnim neki pojam. Na kraju posta postavim pitanje
2. Vi ispod odgovarate, i pitate ako vam nesto nije jasno
3. Kad sve razjasnimo, ja pisem novi post, i tako u krug.

Iiiiii....krecemo :)

1. OSNOVNI POJMOVI


Kurs je koncipiran tako da, na kraju, znate sve ono sto treba da se zna o osnovnim pojmovima koje cesto srecemo i koristimo.
Ti pojmovi su sledeci:

- Kriptografija
- Kriptoanaliza
- Kriptografski kljucevi
- Simetricna kriptografija
- Asimetricna kriptografija
- Digitalni potpis (digitalni sertifikat)

Pa, da pocnemo :)
 
UVOD

Kriptografija - skup metoda kojima kreiramo kriptografski sistem: sistem u kojem mozemo bezbedno da komuniciramo (razmenjujemo poruke).
Kriptoanaliza - metoda razbijanja onoga sto smo kreirali kriptografijom.

Sve je pocelo jos od kamenog doba, kada su pocele i prve bracne prevare, kada je Fred Kremenko krenuo u svaleraciju sa Barnijevom zenom - Beti :D
I, onda su njih dvoje osmislili nacin kako da komuniciraju, a da ih ovi drugi dvoje ne provale. I, tako je nastao prvi kriptografski sistem :)

Salu na stranu, ovaj primer je dovoljan da vec mozemo da izdvojimo osnovne ucesnike u nasoj prici...a i samu nasu pricu.

Nasa kriptografska prica ce se zvati "kriptografski protokol".

U tom kriptografskom protokolu, treba da izdvojimo ucesnike. Ucesnici su sledeci

- Posiljalac (Fred)
- Primalac (Beti)
- Prisluskivac (Wilma ili Barni, birajte koga cete)
- Trece lice od poverenja (odabracemo ga kasnije).

Pomenucemo jos neke bitne pojmove za realizaciju elementarnog kriptografskog protokola:

- Otvorena poruka (OT (otvoreni tekst))
- Kriptovana poruka (S (od reci sifrat))
- Algoritam (logika kojom se od otvorene poruke dolazi do kriptovane, i obrnuto)
- Kljuc (ono sto zajedno sa algoritmom, omogucuje da se OT transformise u S, i obrnuto).

Jesu li osnovni pojmovi i ucesnici u prici jasni? :)
Je li jasno sta je kriptografija, sta kriptoanaliza, sta je kriptografski protokol, i ostale nebuloze koje sam ovde spomenuo? :)

Ako jeste, idemo dalje :)
 
UVOD

Kriptografija - skup metoda kojima kreiramo kriptografski sistem: sistem u kojem mozemo bezbedno da komuniciramo (razmenjujemo poruke).
Kriptoanaliza - metoda razbijanja onoga sto smo kreirali kriptografijom.

Sve je pocelo jos od kamenog doba, kada su pocele i prve bracne prevare, kada je Fred Kremenko krenuo u svaleraciju sa Barnijevom zenom - Beti :D
I, onda su njih dvoje osmislili nacin kako da komuniciraju, a da ih ovi drugi dvoje ne provale. I, tako je nastao prvi kriptografski sistem :)

Salu na stranu, ovaj primer je dovoljan da vec mozemo da izdvojimo osnovne ucesnike u nasoj prici...a i samu nasu pricu.

Nasa kriptografska prica ce se zvati "kriptografski protokol".

U tom kriptografskom protokolu, treba da izdvojimo ucesnike. Ucesnici su sledeci

- Posiljalac (Fred)
- Primalac (Beti)
- Prisluskivac (Wilma ili Barni, birajte koga cete)
- Trece lice od poverenja (odabracemo ga kasnije).

Pomenucemo jos neke bitne pojmove za realizaciju elementarnog kriptografskog protokola:

- Otvorena poruka (OT (otvoreni tekst))
- Kriptovana poruka (S (od reci sifrat))
- Algoritam (logika kojom se od otvorene poruke dolazi do kriptovane, i obrnuto)
- Kljuc (ono sto zajedno sa algoritmom, omogucuje da se OT transformise u S, i obrnuto).

Jesu li osnovni pojmovi i ucesnici u prici jasni? :)
Je li jasno sta je kriptografija, sta kriptoanaliza, sta je kriptografski protokol, i ostale nebuloze koje sam ovde spomenuo? :)

Ako jeste, idemo dalje :)

jeste teraj dalje
 
Evo i jedne slicice, gde vidimo prikazanu ovu nasu kriptografsku pricu:

enczypt.jpg


Poruka putuje sa leva na desno: prvo imamo otvoreni tekst (OT), koji zatim prolazi kroz Algoritam, algoritam koristi odredjeni kljuc, i dobijamo Sifrat.
I sifrat je ono sto putuje kroz etar - sto moze neko da vidi, a neprepoznatljivo mu je, izmenjeno je po nekom pravilu.
Sad, ukoliko neko zeli da vidi sta je to sakriveno u sifratu, mora da propusti sifrat opet korz Algoritam (algoritam i ovde koristi neki kljuc) i onda ce dobiti OT.

Sada, kada vidimo ovako lepu slicicu, gde imamo nase KLJUCEVE, nas ALGORITAM, i nase ostale elemente, jel vam padaju na pamet neka pitanja?
 
Evo i jedne slicice, gde vidimo prikazanu ovu nasu kriptografsku pricu:

Pogledajte prilog 476972

Poruka putuje sa leva na desno: prvo imamo otvoreni tekst (OT), koji zatim prolazi kroz Algoritam, algoritam koristi odredjeni kljuc, i dobijamo Sifrat.
I sifrat je ono sto putuje kroz etar - sto moze neko da vidi, a neprepoznatljivo mu je, izmenjeno je po nekom pravilu.
Sad, ukoliko neko zeli da vidi sta je to sakriveno u sifratu, mora da propusti sifrat opet korz Algoritam (algoritam i ovde koristi neki kljuc) i onda ce dobiti OT.

Sada, kada vidimo ovako lepu slicicu, gde imamo nase KLJUCEVE, nas ALGORITAM, i nase ostale elemente, jel vam padaju na pamet neka pitanja?

zar kljuc A i kljuc B ne bi morali da budu isti?
 
@Redmond: ne, vaznije je da kljuc bude siguran. Nekada je bilo podjednako vazno i jedno i drugo, medjutim, danas se sa algoritmima radi sledece: neki matematicar sastavi algoritam, i pusti ga na javnu ocenu, i javno "razbijanje" (nalazenje slabih tacaka algoritma), tako da je u javnosti poznato koji algoritam koliko vredi, i kolika mu je jacina. I svaki algoritam ima slabu tacku, ali fora je u tome da se napravi tako da eksploatacija te slabe tacke traje godinama, kako bi se (ukoliko ti je poznat sifrat i otvoreni tekst), dodje do kljuca. Detaljnije o ovome cu kasnije, kada budem objasnjavao kako je Alan Turing razbio Enigmu :)

SVAKI DOBAR KRIPTO-SISEM SE ZASNIVA NA TAJNOSTI KLJUCA!!! Ovo je aksiom!


U sustini, kriptografija je jednacina sa tri promenljive: sifrat, kljuc, algoritam i jednom nepoznatom: otvoreni tekst. Da biste resili tu nepoznatu, morate da znate sve tri promenljive.
Kriptoanaliticari (oni koji razbijaju kripto-sisteme), uglavnom imaju na raspolaganju dve od tri nepoznate. I oni pokusavaju da dodju do trece nepoznate, i onda da otkljucaju sifrat.

@PerfectOne: sto se tice kljuceva, ne, ne moraju da budu isti. I da, moguce je da se desi da kada otkljucamo dobijemo nesto drugo u odnosu na ono sto smo zakljucali, ali verovatnoca za to je jako mala ako se ispostuje protkol.

U kriptografiji, mnogo vaznije od matematike, je POSTOVANJE PROTOKOLA!


Upravo na osnovu toga da li je KljucA == KljucB ili su razliciti, kriptografija se deli na dve glavne kategorije:

SIMETRICNA (kljucevi su isti) i ASIMETRICNA (kljuc za otkljucavanje se razlikuje od kljuca za zakljucavanje).

Hocemo li sada dalje pojedinacno o Simetricnoj i Asimetricnoj, ili zelite jos da razjasnimo neke stvari? :)
 
Poslednja izmena:
:D

Idemo dalje:

SIMETRICNA KRIPTOGRAFIJA

Dakle, kao sto rekoh, gornja slika, gde je algoritam tako napravljen, da ISTIM KLJUCEM zakljucavamo poruku (kreiramo sifrat) i otkljucavamo je.

Ako ste raspolozeni za malo elementarne matematike (precizije, logike), najjednostavniji primer simetricnog algoritma je jedan koji smo radili u srednjoj skoli: XOR logicka funkcija - takozvana "ekskluzivna ILI funkcija".
Dosta ljudi nije radilo ovu funkciju iz matematike, vec su radili AND i OR funkcije (I i ILI).

Ko nije ucio (ili ko je zaboravio), evo "istinite tabele" za logicku funckiju XOR (kao sto vidite, rezultat je tacan (jeidnica) samo ako su ulazni elementi u funkciju razliciti. Ako su isti, rezultat je netacan (nula)):

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 0 = 1
0 XOR 0 = 0

Hajdemo sada da vidimo primer asimetricne kriptografija sa ovom funkcijom. Recimo, neka nasa poruka koju zelimo da sakrijemo (prevedena u bitove) izgleda ovako: 11010011010 I neka je nas kljuc, koji je tajan, i kojim zelimo da kriptujemo nasu poruku 10111010111. (Radi jednostavnosti, uzeli smo da su kljuc i poruka iste duzine, sto, naravno, ne mora da bude slucaj).
Hajde sada da izvrsimo matematiku sa nasim simetricnim algoritmom: da bit po bit XOR-ujemo.

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
0 XOR 1 = 1
0 XOR 0 = 0
1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 1 = 1
1 XOR 1 = 0
0 XOR 1 = 1

Prva kolona nula i jedinica je OT, druga kolona je Kljuc, i treca, konacna kolona, je nas Sifrat. Dakle, nas sifrat je sada sledeci: 01101001101 sto je totalno razlicito od nase ulazne poruke 11010011010.

Hajdemo sada, da se uverimo, da cemo desifrovanjem (znamo sifrat i kljuc), dobiti originalnu poruku neizmenjenu:

0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 1 = 0

Dakle, kao sto vidite, evo je nasa ulazna poruka, uspesno desifrovana :)

Molim vas da proverite ovo, pa onda idemo dalje na diskusiju. I, naravno, postavite pitanja ako ima :)

P.S. Obecavam, necemo vise nista da racunamo, nema vise matematike :D
 
Ko nije ucio (ili ko je zaboravio), evo "istinite tabele" za logicku funckiju XOR (kao sto vidite, rezultat je tacan (jeidnica) samo ako su ulazni elementi u funkciju razliciti. Ako su isti, rezultat je netacan (nula)):

1 XOR 1 = 0
1 XOR 0 = 1
0 XOR 0 = 1
0 XOR 0 = 0

Jasno mi je samo mislim da si napravio lapsus ovde u trecem redu za XOR funkciju, treba da bude: 0 XOR 1 = 1
 
Jasno mi je samo mislim da si napravio lapsus ovde u trecem redu za XOR funkciju, treba da bude: 0 XOR 1 = 1
evo me, malo pre sam usla i pregledala ovu nasu temicu
i saglasna sam s tobom, Rede, tu je pogresio, mada je kroz zadatak ubacio pravu istinitosnu vrednost

btw, Frede, meni odgovara cak i da zadajes fakultativni domaci zadatak, nekoliko komada, da se malo zabavljamo brojkama i utvrdimo gradivo
ko hoce, naravno, neobavezno, a ja volim logicke zadatke, opuste me od napornog dana, ociste mi mozak od egzistencijalnog sadrzaja

- - - - - - - - - -

ups, dok sam ja zavrsila tel-razgovor i napisala poruku, evo, i Fred usao (a pocela je pred cca 10min :lol:)
sto se mene tice, mozemo dalje, bas mi je super temica :)
 
Odlicna tema druze! Ovakva tema treba da bude lepljiva. :)

Sto se tice same tajnosti, kao sto frederikrr rece, od najveceg znacaja je tajnost samog kljuca. Onda kada se kljuc otkrije, sve pada u vodu.
Nikako se ne treba oslanjati na tajnost samog algoritma, jer onog trenutka kad algoritam procuri u javnost (a sanse da se to desi su zapravo velike, poput RC4 koji je drzan u tajnosti, dok nije provaljen i objavljen), sve se opet oslanja na tajnost kljuca (osim ukoliko algoritam nema ozbiljne propuste pa je zbog toga drzan u tajnosti, jer se onda lako moze izvrsiti kriptoanaliza iskoriscavanjem tih slabosti, pogledajte samo WEP protokol, sifra se razbija u par minuta).

Tajnost kljuca moze biti ugrozena na mnogo nacina, a zapravo najredje kriptoanalizom. Najcesce se iskoriscava aljkavost korisnika, pa se kljuc ukrade ili se dobije podmicivanjem.

Voleo bih da pri kraju kursa sve ovo povezemo sa primenama na Internetu, tipa da pomenemo SSL sertifikate, opasnosti koje vrebaju, zasto sam HTTP nije dovoljan, itd. Mogao bi cak da se napravi neki mini-kurs etickog hakovanja, mogao bih da doprinesem (to su zapravo stvari koje bi morao da zna svaki korisnik Interneta, kako bi mogao u skladu sa time da se zastiti!), ali nazalost takve stvari ne bi smele da se objavljuju ovde, iako je u pitanju eticko, jer itekako moze da se iskoristi u neeticke svrhe, tako da verujem da od toga nema nista. Ali bismo u narednom periodu mogli da otvorimo temu o osnovnoj bezbednosti na Internetu, kako se ne upecati na neke stvari, i slicno, bez preteranog detaljisanja zasto je to tako, jer pretpostavljam da bi i to bilo sugerisanje kako se neki napad izvodi. :)
 
Poslednja izmena:
Tajnost kljuca moze biti ugrozena na mnogo nacina, a zapravo najredje kriptoanalizom. Najcesce se iskoriscava aljkavost korisnika, pa se kljuc ukrade ili se dobije podmicivanjem.

Voleo bih da pri kraju kursa sve ovo povezemo sa primenama na Internetu, tipa da pomenemo SSL sertifikate, opasnosti koje vrebaju, zasto sam HTTP nije dovoljan, itd. Mogao bi cak da se napravi neki mini-kurs etickog hakovanja, mogao bih da doprinesem (to su zapravo stvari koje bi morao da zna svaki korisnik Interneta, kako bi mogao u skladu sa time da se zastiti!), ali nazalost takve stvari ne bi smele da se objavljuju ovde, iako je u pitanju eticko, jer itekako moze da se iskoristi u neeticke svrhe, tako da verujem da od toga nema nista. Ali bismo u narednom periodu mogli da otvorimo temu o osnovnoj bezbednosti na Internetu, kako se ne upecati na neke stvari, i slicno, bez preteranog detaljisanja zasto je to tako, jer pretpostavljam da bi i to bilo sugerisanje kako se neki napad izvodi. :)

Bas tako! Uvek, i uvek je najslabija karika ljudski faktor, i zato sam naglasio da je u kriptografiji najvaznija stvar napraviti dobar protokol.
Kriptografski protokol treba da bude tako osmisljen da se ljudski faktor, kao faktor rizika, smanji na minimum.

Sto se tice ovog drugog boldovanog - upravo to i jeste krajnji cilj: da ljudi shvate ono sto svakodnevno vidjaju i koriste: https, platne kartice i sve ostale vrste kartica sa nekim tamo cipovima, da licna karta sa cipom nije zig zveri, vec kriptografska smart kartica, i kako to radi (opsta prica), i tako to.

@Lunja*: ne bih da smorim ljude sa matematikom, vise mi je cilj samo da se razume da neke stvari posotje, i sta te stvari rade, a ne kako rade :)

Takodje, necemo uopste se udubljivati u implementaciju algoritama, jer je to previse kompleksno i za naprednije matematicare, a i nista time necemo postici :) Ono sto treba da znamo na kraju ovog mini-kursa, je da kada procitamo da je nesto kriptovano tim i tim algoritmom, da znamo sta to znaci, i to je vise nego dovoljno :)

Hvala na podrsci, nastavljamo dalje :)


Malo o kljucevima

Kao sto smo vec naucili, za sigurnost kriptografskog sistema, najvaznije je imati dobar protokol, i obezbediti sigurnost kljuca. Medjutim, sigurnost kljuca je mnogo vise od same tajnosti.

Da bismo malo bolje razjasnili pricu oko kljuca, vratimo se opet na nas primer odozgo: imali smo Otvoreni Tekst duzine 11 bitova, koji smo trebali da kriptujemo, i uradili smo to pomocu kljuca koji je bio, takodje, 11 bitova dugacak. Medjutim, u tih 11 bita podataka (u zavisnosti od nekih drugih podesavanja), staje, odprilike, jedno slovo. Zamislite koliko je bitova potrebno za jednu ozbiljniju poruku?
Lunja je postavila pravo pitanje: o duzini kljuca!

Da li duzina kljuca mora biti ista kao duzina poruke? Sta se radi ako je kljuc kraci? Sta se radi ako je kljuc duzi? Kakav kljuc, zapravo, treba da bude? I koliko je izvodljivo u praksi napraviti i koristiti dobar kljuc?

Prvo pitanje je vec odgovoreno ostalima: duzina kljuca ne mora biti kao i poruka. I najcesce i nije :)
Verovatno ste se susretali negde sa pojmovima kao sto su AES(256) ili AES(512), ili nesto slicno? E, upravo AES je ime jednog SIMETRICNOG algoritama, a 256, odnosno 512 je duzina kljuca koju taj algoritam zahteva da bi odradio svoj posao.
Opet, necemo ulaziti u detalje implementacije ovog algoritma, ali verujte mi, sasvim bezbedno ga mozete koristiti za mnoge stvari :)

Ako je kljuc duzi od poruke, sto se retko desava, onda je vrlo prosto: koristimo samo deo kljuca koliko nam je potrebno da sifrujemo poruku (zavisi od naseg algoritma, jer kao sto ste zakljucili, algoritam je taj kojim se definise koliko nam dugacak kljuc treba), a ostatak iskoristimo za neku drugu poruku, ili kako vec sami odlucimo.

Kakav kljuc treba da bude? Koliko dugacak? I jos ponesto o njemu....

Kao sto ste, verovatno, sami zakljucili, sto duzi kljuc, to je bolja sigurnost poruke. Idealna situacija je kada kljuc ispunjava dva zahteva: da bude dugacak isto kao i poruka, i da je sto slucajniji (totalan random, totalan nonsense, totalna nebuloza od kombinacije bitova, koja treba da ne znaci apsolutno nista, niti da ima ikakvu logiku kojom je moguce ga kreirati) => KLJUC MORA BITI SLUCAJAN NIZ!!!

Ovo je vrlo vazno, zato je caps-lock i zato je boldovano!

Sada ide pitanje za razmisljanje: sta mislite, koliko je jednostavno kreirati slucajan niz?
 
Poslednja izmena:

Back
Top