Sve o kriptografiji (za početnike)

Kriptografija je naučna disciplina koja se bavi proučavanjem metoda za slanje poruka u takvom obliku da ih samo onaj kome su namijenjene može pročitati. Sama reč kriptografija je grčkog porekla i znači tajnopis. Neki elementi kriptografije bili su prisutni već kod starih Grka. Naime, Spartanci su u 5. veku pre Hrista upotrebljavali spravu za šifrovanje zvanu skital. To je bio drveni štap oko kojeg se namotavala traka od pergamenta, pa se na nju vodoravno pisala poruka. Nakon upisivanja poruke, traka bi se odmotala, a na njoj bi ostali izmešani znakovi koje je mogao pročitati samo onaj ko je imao štap jednake debljine.

Osnovni zadatak kriptografije je omogućavanje dvema osobama (pošiljalac i primalac) da komuniciraju preko nesigurnog komunikacionog kanala (telefonska linija, kompjuterska mreža, ...) na način da treća osoba (njihov protivnik) ne može razumeti njihove poruke. Poruku koju pošiljalac želi poslati primaocu zvat ćemo otvoreni tekst (engl. plaintext). To može biti tekst na njihovom maternjem jeziku, numerički podaci ili bilo šta drugo. Pošiljalac transformiše otvoreni tekst koristeći unapred dogovoreni ključ. Taj postupak se zove šifrovanje, a dobijeni rezultat šifrat (engl. ciphertext) ili kriptogram. Nakon toga pošiljalac pošalje šifrat preko nekog komunikacijskog kanala. Protivnik prisluškujući dozna sadržaj šifrata, ali ne može odrediti otvoreni tekst. Za razliku od njega, primalac koji zna ključ kojim je šifrovana poruka može dešifrovati šifrat i odrediti otvoreni tekst.

Za razliku od dešifrovanja, kriptoanaliza ili dekriptovanje je naučna disciplina koja se bavi proučavanjem postupaka za čitanje skrivenih poruka bez poznavanja ključa. Kriptologija je pak grana nauke koja obuhvata kriptografiju i kriptoanalizu. Kriptografski algoritam ili šifra je matematička funkcija koja se koristi za šifrovanje i dešifrovanje. Njeni argumenti su ključ i otvoreni tekst, odnosno ključ i šifrat. Skup svih mogućih vrednosti ključeva zovemo prostor ključeva. Kriptosistem se sastoji od kriptografskog algoritma, te svih mogućih otvorenih tekstova, šifrata i ključeva.

Tip operacija koje se koriste pri šifrovanju

Imamo podelu na supstitucione šifre u kojima se svaki element otvorenog teksta (bit, slovo, grupa bitova ili slova) preslikava u neki drugi element, te transpozicijske šifre u kojima se elementi otvorenog teksta permutiraju. Npr. ako riječ TAJNA šifriramo u XIWOI, načinili smo supstituciju, a ako je šifriramo u JANAT, načinili smo transpoziciju (drugim rečima stvaramo anagram). Postoje takođe i sistemi koji kombinuju ove dve metode.

Broj ključeva koji se koristi

Ovde je osnovna podela na simetrične kriptosisteme i kriptosisteme s javnim ključem. Kod simetričnih ili konvencionalnih kriptosistema, ključ za dešifrovanje se može izračunati poznavajući ključ za šifrovanje i obratno. U stvari, najčešće su ovi ključevi identični. Sigurnost ovih kriptosistema leži u tajnosti ključa. Zato se oni zovu i kriptosistemi s tajnim ključem. Kod kriptosistemi s javnim ključem ili asimetričnih kriptosistema, ključ za dešifrovanje se ne može (barem ne u nekom razumnom vremenu) izračunati iz ključa za šifrovanje. Ovdje je ključ za šifrovanje javni ključ. Naime, bilo ko može šifrovati poruku pomoću njega, ali samo osoba koja ima odgovaraju ključ za dešifrovanje (privatni ili tajni ključ) može dešifrovati tu poruku. Ideja javnog ključa javila se 1976. godine (prvi su je javno izneli Whitfield Diffie i Martin Hellman) zbog potrebe razmenjivanja ključeva za simetrične kriptosisteme putem nesigurnih komunikacijskih kanala.

SUPSTITUCIONA ŠIFRA

Rimski vojskovođa i državnik Julije Cezar u komunikaciji sa svojim prijateljima koristio se šifrom u kojoj su se slova otvorenog teksta zamenjivala slovima što su se nalazila tri mjesta dalje od njih u alfabetu (A D, B E, itd.). Ako bi smo upotrebili današnji engleski alfabet od 26 slova, onda bi poznata Cezarova izreka VENI VIDI VICI bila šifrovana ovako: YHQL YLGL YLFL.

Cezarovu šifru možemo pregledno zapisati na sledeći način:
otvoreni tekst 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
_______.šifrat D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Supstituciona šifra ne mora izgledati kao gornji primer, odnosno, ne mora se raditi o čistom pomeranju slova alfabeta za tri-četiri mesta unapred, već se stvar može malo i zakomplikovati. Ukoliko pošiljalac koristi neki opštiji algoritam supstitucije, gde šifrovan alfabet može da bude bilo koja kombinacija slova početne azbuke, onda se stvaraju milioni mogućih ključeva, a samo primalac zna tačnu kombinaciju, odnosno pravi ključ.
Međutim supstituciona šifra se i pored toga može vrlo lako dešifrovati koristeći metodu koja se naziva Analiza učestanosti. Začeci analize učestanosti mogu se naći u XIV veku u delu arapskog autora Ibn ad-Duraihima. Ova metoda funkcioniše tako što se broje sva slova (simboli, znakovi) šifrovanog teksta, i pravi se tabela najčešće upotrebljavanih slova. Potom se uzme tabela najčesšće upotrebljavanih slova jezika kriptovanog teksta, i vrši se zamena (naravno ne treba u potpunosti slediti zamenu, jer uvek ima malih odstupanja, u zavisnosti od vrste teksta koji je šifrovan).

VIŽNEROVA ŠIFRA

Vižnerova šifra predstavlja revolucionarno otkriće u svetu kriptografije. Tvorac ove neverovatne šifre je francuski diplomata, Blez De Vižner, rođen 1523. godine.
Snaga Vižnerove šifre ogleda se u tome što ona umesto jednog ili dva, koristi onoliko šifrovanih alfabeta (abeceda, azbuka) koliko slova ima jezik na kojem se šifruje. U Engleskom jeziku koristili bi smo 26 šifrovanih alfabeta, u srpskom 30 itd.

Prvi korak u šifrovanju je crtanje tzv. Vižnerovog kvadrata koji se sastoji od početnog alfabeta i 26 šifrovanih alfabeta, od kojih je svaki pomeren za jedno slovo u odnosu na prethodni.
Korišćenje Vižnerove šifre podrazumeva da se za šifrovanje različitih slova iz poruke koriste različiti redovi Vižnerovog kvadrata. Drugim rečima, pošiljalac bi mogao da šifruje prvo slovo prema redu 5, drugo prema redu 12, treće prema redu 23 itd.
Jačina ove šifre leži u tome što je nemoguće primeniti analizu učestanosti jer su sva slova relativno podjednako zastupljena.

Pored toga što je imuna na analizu učestanosti, Vižnerova šifra ima ogroman broj ključeva. Pošiljalac i promalac se mogu dogovoriti da to bude bilo koja reč iz rečnika, kombinacija reči ili čak potpuno izmišljena reč.
Ovu šifru možemo svrstati u klasu polialfabetskih šifara jer se u istoj poruci koristi više šifrovanih alfabeta.
Zbog svoje snage i složenosti, Vižnerova šifra je nazvana Neprobojnom šifrom!

PLAYFAIROVA ŠIFRA

Jedna ideja za poboljšanje supstitucionih šifara je uvođenje polialfabetskih šifara. Jednu takvu šifru smo videli na prethodnoj strani. Druga ideja je upotreba blokova slova kao osnovnih elemenata otvorenog teksta. Prikazat ćemo najpoznatiju takvu šifru, tzv. Playfairovu šifru. Ovu šifru je izmislio britanski naučnik Charles Wheatstone 1854. godine, a ime je dobila po njegovom prijatelju baronu Playfairu od St. Andrewsa koji ju je popularizovao. To je bigramska šifra, u smislu da se šifruju parovi slova i to tako da rezultat ovisi i o jednom i o drugom slovu. Algoritam za šifrovanje se bazira na 5x5 matrici slova, koja se konstruiše koristeći ključnu reč. Na primer, ako je ključna reč PLAYFAIR, onda matrica izgleda ovako:

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

Budući da imamo 25 slova, dogovor je da se slova I i J poistovete. U slučaju da je otvoreni tekst na srpskom jeziku, mi ćemo poistovećivati V i W. Šifrovanje se sada vrši na sledeći način. Najprije podelimo otvoreni tekst na blokove od po dva slova. Pritom pazimo da se niti jedan blok ne sastoji od dva jednaka slova, te da je dužina teksta parna. I jedno i drugo postižemo umetanjem npr. slova X ukoliko je to potrebno.

Kod šifrovanja bloka od dva slova, mogu nastupiti tri slučaja:

1. Slova se nalaze u istom retku. Tada ih zamenimo sa slovima koja se nalaze za jedno mesto udesno (ciklično). Npr. EH GK, ST TN, FP PL.
2. Slova se nalaze u istom stupcu. Tada ih zamenimo sa slovima koja se nalaze za jedno mesto ispod (ciklično). Npr. OV VL, KY SC, PI IE.
3. U protivnom, pogledamo pravougao koji određuju ta dva slova, te ih zamenimo s preostala dva vrha tog pravougla. Redosled je određen tako da najprije dođe ono slovo koje se nalazi u istom retku kao prvo slovo u polaznom bloku. Npr. OC SR, RK CG, PD FI.

Primer: Šifrujmo otvoreni tekst CRYPTOGRAPHY pomoću Playfairove šifre s ključem PLAYFAIR.

CR YP TO GR AP HY --> DB FL NQ OG YL KA

Playfairova šifra ima brojne prednosti pred supstitucionom šifrom. Spomenimo neke. Budući je šifra bigramska, gube se u šifratu jednoslovne reči (npr. "a") koje dosta utiču na učestanosti. Nadalje, bigramsko šifrovanje smanjuje na polovicu broj elemenata dostupnih analizi učestanosti. I konačno, broj bigrama je puno veći od broja individualnih slova (26 slova - 676 bigrama), dok su učestanosti najfrekventnijih bigrama puno ujednačenije od učestanosti najfrekventnijih slova.

Iz ovih razloga, Playfairova šifra je dugo vremena smatrana sigurnom. Tako je bila standardna šifra u britanskoj vojsci za vreme 1. svetskog rata, a čak je korištena i u američkoj vojsci u 2. svetskom ratu.

Ipak, kod dugih tekstova ova šifra postaje nesigurna jer se može iskoristiti analiza učestanosti bigrama. Poznato je da i kod ove šifre deo strukture jezika ostaje sačuvan. Naime, slova u šifratu nisu jednoliko raspoređena. Dok u otvorenom tekstu na engleskom jeziku najfrekventnije slovo ima relativnu učestanost 13%, u šifratu dobijenom Playfairovom šifrom to iznosi 7%, dok recimo kod Vižnerove šifre imamo 6%. Takvi podaci mogu nam pomoći i kod određivanja koja je šifra u pitanju.

KRIPTOANALIZA

Suština kriptografije je očuvanje otvorenog teksta (ili ključa, ili i jednog i drugog) tajnim i sigurnim od upada prisluškivača kanala/njuškala (koji su poznati i kao protivnici, napadači, presretači, nametljivci, uljezi, ili jednostavno – neprijatelji).
Pretpostavlja se da prisluškivači kanala imaju kompletan pristup komunikacionim kanalima između pošiljaoca i primaoca.
Kriptoanaliza je nauka koja bez ključa određuje otvoreni tekst na osnovu šifrata. Uspešnom primenom kriptoanalize moguće je rekonstruisati otvoreni tekst ili ključ. Upotrebom kriptoanalize moguće je pronaći slabosti u kriptosistemu i na kraju doći do već pomenutih rezultata. (Otkrivanje ključa nekriptoanalitičkim metodama nazivamo kompromitovanje, engl. compromise.) Pokušaj kriptoanalize naziva se napad (engl. attack). Osnovna postavka kriptoanalize, koju je prvi objavio Holanđanin A. Kerkhof (A. Kerckhoffs) u XIX veku, jeste da tajnost mora biti potpuno zasnovana na ključu. Kerkhof je pretpostavio da kriptoanalitičar zna sve pojedinosti kriptografskog algoritma i njegove primene .
Postoje četiri opšta tipa kriptoanalitičkog napada. Naravno, za sva četiri tipa pretpostavlja se da kriptoanalitičar ima sve potrebno znanje o šifrovanju koje koristi algoritam:
1. Napad “samo šifrat” (engl. ciphertext-only attack) Kriptoanalitičar ima šifrate nekoliko poruka šifrovanih istim algoritmom za šifrovanje. Zadatak kriptoanalitičara je da rekonstruiše otvoreni tekst što većeg broja poruka, ili – još bolje – da otkrije ključ (ili ključeve) korišćene za šifrovanje poruka kako bi dešifrovao druge poruke šifrovane istim ključem.
2. Napad “poznat otvoreni tekst” (engl. known-plaintext attack) Kriptoanalitičar ima pristup šifratima za nekoliko poruka, kao i otvorenim tekstovima tih poruka. Njegov je posao da izračuna ključ (ili ključeve) korišćen za šifrovanje poruka, ili algoritam, kako bi dešifrovao svaku novu poruku šifrovanu istim ključem (ili ključevima).
3. Napad “odabran otvoreni tekst” (engl. chosen-plaintext attack) Kriptoanalitičar ne samo da ima pristup šifratu i pripadajućem otvorenom tekstu nekoliko poruka, već i bira otvoreni tekst koji će biti šifrovan. Ovo je moćnije od napada “poznat otvoreni tekst”, jer kriptoanalitičar može da odabere specifične blokove otvorenog teksta za šifrovanje i tako dođe do više informacija o ključu. Njegov je posao da izračuna ključ (ili ključeve) korišćen za šifrovanje poruka, ili da odredi algoritam pomoću koga bi dešifrovao svaku novu poruku šifrovanu istim ključem (ili ključevima).
4. Napad “prilagodljiv odabrani otvoreni tekst” (engl. adaptive-chosen-plaintext attack) Ovo je poseban slučaj napada “odabran otvoreni tekst”. Ne samo da kriptoanalitičar može da odabere šifrovan otvoreni tekst, već može i da modifikuje
ono što je odabrao na osnovu rezultata prethodnih šifrovanja. Prilikom napada “odabran otvoreni tekst”, kriptoanalitičar može da odabere za šifrovanje jedan veliki blok otvorenog teksta; u napadu “prilagodljiv odabrani otvoreni tekst”, on može da odabere manji blok otvorenog teksta, a zatim još jedan na osnovu rezultata prvog, i tako dalje.

Ne zaboravite Kerkohovu hipotezu: Ako snaga vašeg kriptosistema počiva na činjenici da napadač ne zna kako vaš algoritam funkcioniše – propali ste. Ukoliko verujete da će tajnost strukture vašeg algoritma povećati sigurnost vašeg kriptosistema više nego slobodna analiza akademske zajednice, varate se. Ukoliko mislite da niko neće rastaviti vaš izvorni kôd i obrnutim procesom (reverznim inženjeringom) detaljno proučiti vaš algoritam, naivni ste.
Zapamtite, kriptografi i kriptoanalitičari među sobom diskutuju o svojim algoritmima, oslanjajući se pri tome na profesionalnu procenu kolega radi otkrivanja mogućih slabosti u radu i kako bi razlikovali dobar algoritam od lošeg.


Napomena:
Znam da će nisam dodao neke sisteme enkripcije (Hill, ADFGVX, DES, RSA i tako dalje...), ali to je zato što mislim da je za početnike ovo sasvim dovoljno, a ostale ćemo lako nadodati po potrebi!

_{[Ovu poruku je menjao Blaise De Vigenere dana 11.03.2011. u 18:35 GMT+1]}

---

Šifra ADFGVX

Šifra ADFGVX obuhvata i supstituciju i transpoziciju. Enkripcija počinje iscrtavanjem tabele 6x6, čijih se 36 ćelija popunjavaju nasumično raspoređenim slovima abecede i brojevima od 0 do 9. Svaki red i kolona tabele označeni su jednim od šest slova A,D,F,G,V, i X. Raspored elemenata u tabeli predstavlja deo ključa, tako da primalac mora da zna kako tabela izgleda, ne bi li uspeo da dešifruje poruku.
U prvoj fazi šifrovanja, svako slovo iz posruke treba pronaći i zameniti ga slovima koja označavaju njegov red i kolonu (drugim rečima, svako slovo originalnog teksta će biti zamenjeno sa dva slova šifrovanog teksta).
Izgled tabele:

__A..D.F.G.V.X
A_8_p_3_d_1_n
D_l _t_4_o_a_h
F_7_k_b_c_5_z
G_j_u_6_w_g_m
V_x_s_v_i__r_2
X_9_e_y_0_f_q

Primer teksta šifrovanog ADFGVX šifrom:

Originalni tekst: POKRENI OPERACIJU SABLJA
Šifrovani tekst: AD DG FD VV XD AX VG DG AD XD VV DV FG VG GA GD VD DV FF DA GA DV

Za sad je ovo samo prosta monoalfabetska supstitucija za čije razbjanje bi bila dovoljna analiza učestanosti. Međutim, u drugoj fazi šifre ADFGVX primenjuje se transpozicija koja umnogome otežava kriptoanalizu. Transpozicija zavisi od ključne reči koja u ovome slučaju glasi RATNIK i koja se mora dostaviti primaocu. Transpoziciju pravimo tako što ispod slova ključne reči upisujemo slova šifrovanog teksta, potom ispremeštamo slova ključne reči (uključujući i redove ispod nje) i ponovo ispišemo tekst koji smo dobili. Evo primer:

R A T N I K
A D D G F D
V V X D A X
V G D G A D
X D V V D V
F G V G G A
G D V D D V
F F D A G A
D V

Potom ispremeštamo redove:

A N T I R K
D G D F A D
V D X A V X
G G D A V D
D V V D X V
G G V G F A
D D V D G V
F A D G F A
V D

Konačan kriptogram: DGDFADVDXAVXGGDAVDDVVDDXVGGVGFADDVDGVFADGFAVD


Konačan kriptogram se zatim šalje pretvoren u Morzeov kod. Da bi dobio originalan tekst, primalac će obrnuti ceo postupak.
Razlog zbog kojeg su za glavna slova izabrana baš A,D,F,G,V,X je taj što se ta slova najviše razlikuju kada se pretvore u tačke i crte Morzeovog koda.


S obzoriom da nemam uvek vremena ne stižem sve od jednom da ubacim, pa kako kad budem slobodan, ubacivaću u ovu temu nove šifre, ali i primere za vežbanje.

---

Mislim da bi umesto (pra)istorijskih priča o algoritmima koji su danas neupotrebljivi, neki savremeniji tutorial bio korisniji posetiocima.

---

Ti "praistorijski" algoritmi se i dalje koriste, veruj mi, ja se bavim zaštitom podataka. Najtraženije je znanje o RSA, naravno, a ovo ostalo malo manje, ali ja i dalje držim dosta časova i predavanja o osnovnim algoritmima enkripcije. Svi koji počinju treba prvo to da nauče, ipak su to neke osnove i to ne treba preskakati. Ti možda ovo poznaješ pa ti se čini nepotrebno, ali za ljude koji se tek susreću sa kriptografijom i kriptoanalizom ovo je neverovatno otkriće. Mnogi zapravo misle da znaju ovo, ali kada se susretnu sa recimo malo težom homofoničnom šifrom ili Vižnerovom, i vide da je ne mogu dekriptovati, shvate da ni ovo nije lako. Da bi se prešlo na moderne sisteme neophodno je savladati same osnove ove veštine. Dobar kriptoanalitičar mora poznavati sve sisteme enkripcije da bi u datom trenuku to mogao i iskoristiti.
Ja ovo pišem za ljude koji zaista vole kriptografiju i koji žele da nauče nešto o tome (naravno ni ovo što je u ovoj temi napisano nije dovoljno, ali je dobar početak).
Tako da ću ja nastaviti da pišem ovde nekim redom, a vremenom ću doći i do modernih sistema enkripcije, pa će oni koji prate temu moći da vide neku hijerarhiju, razvijanje kriptografskih sistema i tako će stvoriti jednu celovitu sliku o ovoj naučnoj disciplini.

---

Meni trenutno padaju na pamet sledeće glavne vrste kriptografije:

1. Simetričnim ključem (primer je AES),
2. Asimetričnim ključem (primer je RSA),
3. Kriptografki heš (primer je MD6).

Možda ne bi bilo loše reći nešto o problemima koji se rešavaju metodama kriptografije, načinima njihovog rešavanja kriptografskim metodama do na gotove kriptografske algoritme i problemima vezanim za implementaciju. Sumnjam da će se neko od posetilaca baviti kriptoanalizom, već pre svega praktičnom primenom.

---

POČECI I RAZVIJANJE RAČUNARSKE KRIPTOGRAFIJE

Šifrovanje poruke pomoću računara je u velikoj meri slično tradicionalnim oblicima enkripcije. Međutim, pored brzine, jedna od najvažnijih razlika je u tome što računar operiše u brojevima, a ne slovima. Kompjuteri rade samo sa binarnim brojevim, nizovima nula i jedinica koji se nazivaju binarnim ciframa, odnosno bitima. Prema tome, svaka poruka se pre šifrovanja mora pretvoriti u binarni broj. Konverzija se može obaviti prema različitim protokolima, poput Američkog standardnog koda za razmenu informacija (American Standard Code Information Interchange) poznatijim kao ASCII (aski). Prema ASCII protokolu, svakoma slovu dodeljuje se sedmocifreni binaran broj.
Primer ASCII binarnih brojeva za velika slova:
A = 1000001___ G = 1000111___ M = 1001101___ S = 1010011___ Y = 1011001
B = 1000010___ H = 1001000___ N = 1001110___ T = 1010100___ Z = 1011010
C = 1000011___ I = 1001001___ O = 1001110___ U = 1010101
D = 1000100___ J = 1001010___ P = 1010000___ V = 1010110
E = 1000101___ K = 1001011___ Q = 1010001___ W = 1010111
F = 1000110___ L = 1001100___ R = 1010010___ X = 1011000

Računarsko šifrovanje bilo je dostupno samo onima koji su imali računare, a u početku to su bile samo vladine službe i vojska. Tek krajem šezdesetih, početkom sedamdesetih godina računari su polako postajali dostupniji širem broju korisnika. U to vreme, jedan od najčešće korišćenih algoritama bio IBM-ov proizvod nazvan Lucifer (razvio ga je Horst Fajstel, nemački emigrant u SAD-u).
Lucifer je šifrovao tekst po sledećem postupku:
1. Poruka se najpre prevede u dugačak niz binarnih cifara.
2. Taj niz se zatim podeli na blokove od po 64 cifre, tako da se šifrovanje obavlja nad svakim blokom posebno.
3. U okviru jednog bloka 64 cifre se izmeštaju, a zatim podele na dva bloka od po 32, obeleženih kao levi_0 i desni_0.
4. Cifre iz bloka desni_0 zatim prolaze kroz "centrifugu" - proces veoma složene supstitucije.
5. Tako izmenjeni blok desni_0 se zatim dodaje bloku levi_0, a novonastali blok od 32 cifre, naziva se desni_1.
6. Originalni blok desni_0 obeležava se kao levi_1 (ovaj niz operacija naziva se "runda")

Postupak se ponavlja i u drugoj rundi samo ovog puta sa novim polu-blokovima desni_1 i levi_1. Ceo proces šifrovanja ima 16 rundi. Pojedini detalji supstitucije mogu da se menjaju, a zavise od ključa ugovorenog između pošiljaoca i primaoca (drugim rečima, ista poruka se može šifrovati na milijardu različitih načina, od zavisnosti od toga koji je ključ izabran).
Lucifer je smatran jednim od najjačih šifrarskih proizvoda, i zbog toga su ga koristile mnoge organizacije.
Da bi postao standard, Lucifer je morao da smanji broj potencijalnih ključeva na 56 bita (po zahtevu NSA, da bi oni bez problema mogli provaliti svaku šifru, jer sve preko toga bi njima prestavljao problem). Tako da je pedesetšestobitna verzija Fajstelove šifre Lucifer zvanično usvojena 23. novembra 1976. godine, i nazvana je Standardom za enkripciju podataka (Data Encryption Standard - DES).
DES je bio dovoljno moćan da garantuje bezbednost od napada. Nekome ko poseduje civilni računar praktično je bilo nemoguće da razbije poruku šifrovanu prema standardu DES.
DES zapravo predstavlja kriptovanje koje transformiše 64 bitne blokove podataka u 64 bitne kriptovane blokove podataka. Dužina ključa kriptovanja je 64 bita, od kojih 8 otpada na proveru pariteta, tako da je efektivna dužina ključa 56 bita. DES kriptovanje/dekriptovanje se sprovodi u nekoliko koraka . Prvo se bitovi ulaznog bloka dužine 64 bita permutiraju nekom permutacijom IP. Tada se ulazni blok podieli na dva dela po 32 bita, levi L0 i desni deo R0. Nad desnim blokom se obavlja funkcija F(Ri,Ki), odnosno F(Ri,K16 − i + 1) kod dekriptovanja, gde je Ri desnih 32 bita, a Ki je 48 bitni ključ koji se generiše iz zadanog tajnog ključa kriptovanja. Vrednost dobijena operacijom XOR između vrednosti funkcije F i levih 32 bita podataka, postaje Ri + 1, tj. desnih 32 bita za sledeći korak iteracije. Li + 1 za sledeći korak je Ri. Nakon 16 takvih koraka blokovi se zamenjuju te se spajaju i obavlja se konačna permutacija koja je inverzna početnoj, tj. IP − 1. Dobijenih 64 bita su kriptovani blokovi. Budući da se nakon dve uzastopne operacije XOR sa istim brojem dobija početna vrednost, tj. a = (aĹ b)Ĺ b , postupak dekriptovanja može se sprovesti tako da se operacije obavljaju obrnutim redosledom. Zbog simetričnosti algoritma to se postiže tako da se kriptovani blok pusti kroz isti algoritam sa tom razlikom da se umesto ključa Ki u i-tom koraku upotrijebi ključ K16 − i + 1. Postupak generisanja šestnaest 48 bitnih ključeva od zadanog, tajnog ključa sprovodi se u nekoliko koraka. Prvo se pomoću zadane tablice permutacije iz ključa generišu dva bloka po 28 bita. Zatim sledi 16 sledećih koraka: svaki se blok rotira u levo za određeni broj bita (u zavisnosti o kojem je koraku reč) te se iz nastalih blokova (2x28) pomoću tablicom zadate permutacije generše ključ Ki, gde je i broj koraka. Funkcija enkripcije F jeste zapravo najkritičniji deo algoritma. Vrednost funkcije dobija se u nekoliko koraka. Najpre se od ulaznih 32 bita (Ri) proširenjem zadanom tablicom dobija 48 bita. Ta se vrednost zbraja logičkom operacijom XOR sa ključem Ki paralelno nad svakim bitom. Dobijena se 48 bitna vrednost deli na osam delova od po šest bita. Prvi i zadnji bit svakog dela predstavlja adresu reda, a srednja četiri adresu kolone u tablici selekcije, odnosno, pomoću šest određena su četiri bita. Istim postupkom nad svakom šestorkom od ulaznih 48 bita selekcijom dobijamo 32 bita. Tih se 32 bita još permutira zadatom tablicom te se dobija konačna vrednost funkcije F.



Nastavak uskoro...


<sub>[Ovu poruku je menjao Blaise De Vigenere dana 15.03.2011. u 17:50 GMT+1]

[Ovu poruku je menjao Blaise De Vigenere dana 15.03.2011. u 17:51 GMT+1]</sub>

---

Evo jedne zanimljive primene kriptografije. Najpre sam postavio problem, a na istoj temi sam uspeo da ga rešim.

---

Evo i teorijskih osnova RSA algoritma na našem jeziku.

---

Svaka čast. Jedino malo komplikovanije objašnjeno, moglo bi i jednostavnije (da bi početnici lakše razumeli) samo me nervira to što ovde ne mogu pisati matematičke znakove normalno. Videću da napravim proračun RSA u nekom drugom programu, pa ću slikati ekran i poslati sliku (to mi sad jedino pada na pamet).

---

Kao što vidiš u Nedeljkovim porukama, LaTeX je dostupan na forumu.



LaTeX izraz samo ogradi sa [ tex ] ... [ /tex ] kodovima.

---

Video sam to (doduše nisam znao kako se pravi) ali mi se ne dopada kako izgleda. Ako ne uspem nikako drugačije moraću tako!

---

AES (Advanced Encryption Standard)

Još ranih 1970-ih godina kompanija IBM razvila je svoj standard enkripcije podataka nazvan Data Encryption Standard - DES (gore pomenuti). Polovinom sedamdesetih taj je standard prihvatio tadašnji Nacionalni ured za standarde SAD (današnji Nacionalni institut za standarde i tehnologije, NIST) kao službeni standard zaštite podataka u institucijama državne uprave SAD.

Sa razvojem informacijsko-komunikacijskih tehnologija pokazalo se da DES ne može više na odgovarajući način zadovoljavati rastuće potrebe zaštite tajnosti podataka. Taj je problem postao kritičan 1990-ih godina kada Internet „na velika vrata“ ulazi u široku upotrebu, posebno u poslovnim krugovima. Zato je 1997. godine NIST pokrenuo inicijativu za pronalaženje korisnije i pouzdanije zamene za DES.

Naglim razvojem informacijske tehnologije algoritmi koji su nastali pre deset, dvadeset i više godina su zastareli u smislu da više ne pružaju dovoljnu sigurnost. Naime, zadnjih dvadeset godina kriptoanaliza (kao i kriptografija) je takođe profitirala od razvoja računarske moći.Algoritmi kao DES za koje se nekad smatralo da su neprobojni, danas je moguće kompromitovati.

Cilj je pritom bio definisati zamenu za DES koja će se koristiti u svrhe postizanja zadovoljavajućeg stepena informacijske sigurnosti u civilnim informatičkim aplikacijama i komunikacijama tela i institucija državne uprave SAD, ali i u nevladinom sektoru. Na taj način novi će enkripcijski standard postati opšti de facto standard u SAD ali i u međunarodnim razmerama.

NIST je putem javnog konkursa pozvao stručnjake i organizacije za kriptografiju i sigurnost podataka iz čitavog sveta da učestvuju u raspravama i izboru novog enkripcijskog standarda. Od nekoliko desetina predloga, u uži je izbor ušlo njih pet među kojima je kao najprikladniji odabran enkripcijski algoritam kojega su predložili belgijski kriptografi Joan Daeman i Vincent Rijmen. Izvorni naziv tog algoritma kojeg su osmislili njegovi autori bila je izvedenica njihovih prezimena – Rijndael. Nakon što je izabran da bude zamenom za DES, taj je algoritam preimenovan u Advanced Ecryption Standard, poznat pod akronimom AES.

AES je zvanično proglašen službenim enkripcijskim standardom u SAD, 26. maja 2002. godine, pri čemu je dobio službenu oznaku FIPS 197. Kao takav, i danas je važeći.

Strogo govoreći, AES nije precizno Rijndael (iako se u praksi oni koriste nerazdvojivo), jer Rijndael podržava veći raspon bloka i veličine ključa; AES ima fiksni blok veličine 128 bita i ključ veličine 128, 192, ili 256 bita , dok kod Rijndaela može biti navedena, uz ključ, i veličina bloka u bilo kojoj vrednosti pomnoženoj sa 32 bita, i najmanja je 128 bita, a najviša 256 bitova.

AES algoritam je tzv. blok-šifra koja koristi enkripcijski ključ i primenjuje se u nekoliko rundi (iteracija). Blok-šifra je vrsta enkripcijskog algoritma koji se primenjuje istovremeno, odjednom, na celokupne blokove podataka. U izvornom AES-u taj je blok dužine 128 bita odnosno 16 bajta (16 x 8 = 128). Pojam „iteracija“ ili „runda“ odnosi se na način na koji algoritam višestruko „meša“ podatke (poput karata). U današnjoj je informatičkoj praksi uobičajeno da takvih „runda“ bude 10 do 14, zavisno o odabranoj dužini enkripcijskog ključa.

AES algoritam sam po sebi nije, kao što se to često pogrešno misli, računarski program. To je, naime, matematički opis postupka skrivanja informacijskog sadržaja podataka u čije pojedinosti na ovome mestu nećemo ulaziti, a koji se može na različite načine, primenom različitih računarskih jezika i metoda programiranja, transformisati u računarski program. Zato i jeste u upotrebi mnoštvo programa koji su međusobno različiti ali proizlaze iz AES-a i s njime su skladni (kompatibilni).

Kriptovanje je određeno u uslovima ponavljanja obrade koraka koje se primjenjuju kako bi nadoknadili krugove ključem transformacije između ulaznih plain-text i konačnom izlazu kriptovanog teksta. A set obrnute runde su primjenjivane za transformaciju kriptovanja teksta natrag u izvorni plain-text, pomoću istog ključa za šifriranje.

Proširenje ključa koristeći Rijndael ključni raspored - Inicijalni krug enkripcije
1. Dodavanje kružnog ključa - Okrugli
2. Zamena bitova-a ne-linearna zamena koraka gde je svaki bajt zamenjen sa drugim.
3. Pomeranje redova-a je korak gde je svaki red u stanju pomeren kružno za određeni broj koraka.
4. Mešanje kolona-a, operacija mešanja, koja deluje na kolone u stanju, kombinujući četiri bita u svakoj koloni.
5. Dodavanje kružnog ključa - svaki bajt stanja je u kombinaciji sa okruglim ključem; svaki okrugli ključ je izveden iz ključa za kriptovanje informacija koristeći generisanje ključa.

Poslednji krug (nema mešanja kolona)
1. Zamena bitova
2. Pomeranje redova
3. Dodavanje kružnog ključa


Kod primene AES-a, u procesu enkripcije koristi se samo jedan enkripcijski ključ. Njegova dužina, međutim, može varirati, a najčešće su u upotrebi ključevi dužine 128 bita (16 bajta), 192 bita (24 bajta) i 256 bita (32 baja). Za enkripciju (šifriranje) i dekripciju (dešifriranje) koristi se isti ključ. Takvi se algoritmi nazivaju simetričnim enkripcijskim algoritmima.

Budući da se uz primenu AES-a isti ključ koristi i za enkripciju i za dekripciju informacija, neophodno je čuvati njihovu tajnost te koristiti ključeve čije je vriednosti (sadržaj) teško nasumice ili nekako drugačije otkriti (pogoditi). Obično se za generisanje enkripcijskih ključeva koriste računarski programi koji ih „proizvode“ na slučajan odnosno pseudoslučajan način. Postoje takođe i sastavi u kojima se za izvođenje enkripcijskih ključeva kao polazna osnova upotrebljavaju korisničke pristupne lozinke,ali dobar sastav zaštite tajnosti informacija nikada lozinku samu po sebi neće koristiti u funkciji enkripcijskog ključa.

U informatičkoj je praksi u upotrebi nekoliko metoda korišćenja enkripcijskih ključeva prilikom primene AES-a. U stručnoj se terminologiji te metode nazivaju „modalitetima rada“ enkripcijskog sastava. NIST je standardizovao šest takvih modaliteta:

• knjiga elektronskih kodova (engl. Electronic Code Book, ECB),
• ulančavanje šifarskih blokova (engl. Cipher Block Chaining, CBC),
• modalitet brojača (engl. Counter Mode, CTR ili CTRM),
• šifarska povratna veza (engl. Cipher Feedback, CFB),
• izlazna povratna veza (engl. Output Feedback, OFB) i
• modalitet brojača Galois (engl. Galois Counter Mode, GCM).

Svaki se od navedenih modaliteta oslanja na AES na različit, sebi svojstven način. Tako, na primer, ECB nezavisno enkriptuje svaki pojedini blok podataka dok CTR enkriptuje 128-bitni brojač i potom dodaje tu vrednost podacima koje potom enkriptuje. CBC pak koristi inicijalizacijski vektor te dodaje enkriptovanu vrednost svakog bloka podataka podacima sledećeg bloka pre nego što i njih enkribira.

Važno je znati da će i snažan enkripcijski algoritam koji se koristi na neprimeren način rezultirati niskim stepenom sigurnosti osetljivih podataka. Korektna primena neodgovarajućeg modaliteta enkripcije ili pak nekorektna primena odgovarajućeg modaliteta ima će za posledicu slabo osigurane podatke čiju će zaštitu neovlašćeni korisnik lako „probiti“. Zato je preko potrebno znati i do kraja razumeti ograničenja i implikacije primene svakog od navedenih standardnih enkripcijskih modaliteta.

---

Bi li mogao da zainteresuješ čitaoce nekom praktičnom pričom. Recimo, šta je kriptografija javnim ključem (formulacija) i njena primena na digitalni potpis. Mislim da bi takvi tekstovi imali širu publiku.

---

Planirao sam da ispišem RSA i dam primere samo da se pohvatam sa pisanjm matematičkih znakova. Međutim, svakako ću ubacivati i primere tekstova šifrovanih raznim klasičnim šiframa da ljudi malo vežbaju kriptoanalizu. Najviše poruka mi stiže vezano supstituciju i polialfabetske šifre. E da, moram objasniti i kriptografski heš (ti si ga pre par poruka i predložio).

---

Pa, RSA sam ispisao ja, ali to nije bitno za većinu posetilaca, već primene.

---

Važi, odradićemo nešto, dobra ti je ideja. Prvo ide heš funkcija pa onda ostalo.

---

Ukratko o Heš funkciji

Funkcija za sažimanje (skracivanje, kompresiju...) ili heš funkcija je tehnika koja obezbeđuje proveru integriteta poruke. Ovo je vrlo važno iz razloga jer je moguće da je ključ provaljen i da nam napadač šalje lažne poruke, ali i mogućnosti da je došlo do greške prilikom šifrovanja, tako da primljena poruka nije identična originalnom dokumentu. Iz tog razloga kreirane su funkcije za sažimanje, odnosno heš (mogu se susresti i pod imenima engl. one-way, hash function, message digest, fingerprint) algoritmi. Najpoznatiji i najkorišćeniji heš algoritmi su SHA-1, MD5, MDC-2, RIPEMD-160 itd.
Ovi algoritmi prosto sažmu (samelju u bukvalnom prevodu) svaku poruku ili fajl bez obzira na veličinu i na izlazu dobijamo poruku konstantne dužine, u zavisnosti od algoritma. Iz dobijenog izlaza nemoguće je rekonstruisati ulaznu poruku, a isto tako gotovo je nemoguce kreirati dve smislene poruke koje ce imati iste vrednosti heš funkcije. Zahvaljujući ovom svojstvu heš funkcija mi možemo u svakom trenutku da proverimo integritet poruka, odnosno da primetimo razliku u tekstu primljene poruke, prostim ponovnim proračunavanjem heš funkcije i upoređivanjem dobijenih rezultata. Na primer, neka je x proizvoljan podatak proizvoljne dužine, a h odgovarajuca funkcija.Odgovarajuci rezultat heš funkcije je y=h(x). Pretpostavimo da je y uskladišteno na sigurnom mestu a x nije. Ukoliko dođe do izmene vrednosi x u x’, na vrlo prost način se može utvrditi da je poruka izmenjena ponovnim računanjem heš funkcije i uporedivanjem rezultata, y’ = h(x’) i verifikovanjem y ? y’.
Verovatnoća da u poruci neko izmeni neku stavku, tako da novodobijeni tekst ima istu heš vrednost kao i originalni je 1/2_160 u slucaju 160 bitnih algoritama, dakle zanemarljivo mala verovatnoća, zato se negde heš funkcije nazivaju i otisci prstiju poruka.

---

a propos AESa

http://www.moserware.com/2009/...-figure-guide-to-advanced.html

ja bolje objasnjenje nisam nasao do sada :)

Evo i jedan algoritam za primenu:

Shamir's Secret Sharing

Ideja je da nekoliko ucesnika cuvaju tajnu , ali tako da nijedan bez ostalih ne moze da je otkrije.
Cesto se koristi tako da je potreban odredjen broj ucesnika da bi se tajna otkrila.
Recimo , u deljenju tajne ucestvuje 10 ljudi , ali je za otkrivanje tajne potrebno 7.

Kako to postici?
Ideja je prilicno prosta. Dohvatimo se matematike i polinoma...
Za odredjivanje polinoma stepena k , potrebno je k+1 tacaka.
To nam daje osnovu za celu ideju.

Imamo n ucesnika u deljenju tajne. Zelimo da bar k ucesnika moze da otkrije tajnu.

Nasumicno se odaberu k-1 broja. Oznacimo ih . Tajnu cemo oznaciti sa S.
Dalje, oznacavamo da je a0 jednako S.
Konstruisemo polinom:


Sada , koristeci gornji polinom , odaberemo n tacaka (nasumicno ili uzastopno...).
Svako od ucesnika u deljenju tajne dobije tacku i njenu odgovarajucu vrednost po gornjem polinomu.
Ima n takvih parova.

Sada , koristeci interpolaciju , pomocu najmanje k od gornjih n tacaka koje su ucesnici dobili
mozemo da dobijemo pocetni polinom , gde je konstanta u stvari sama tajna.


Sam algoritam je jako prost i interesantan, jako mi se svideo kad sam ga video pa ga zato opisujem ovde ukratko.

Za detalje, naravno, potrazite bolje reference. Ja sam celu pricu dosta uprostio.

Šifrovan tekst za vežbanje:

DIQHMCNMISXGOKXTMS QFLXGS BZUHDW MRZ ZHBCKICMWX JIOOOY AM EKJS MIHXZTVVHDW CRJDK I XZSTCW. EGZPOC XR BDF GCBCEN GE LAITBYMTYXBO GWABHSTSX FCDZDXLOXV PGBGMRVHDS NFSIKWXV. Q ITYY AM EHQOCI SNUK ZAIHFSAI WKWCTICLYSY SGOCZIWABQK Z LJACFEM EKSFRZT. N GVVLTVWR YQACONLATLHY XWSBBK MIIBYKE RT SONIHPH GFFR EHZSKQRDW CKQHTY YBW TOFYGAZHU FIIIT RYEWHXQS KIZH FKUWHGO FIMBXBK BID LHY AM BKOMEW SHPK QIYXRXF AP IFYJDTMZTLRJVWW UWVTRTRRXFO URW HMC CL SGLHKJSX KODFDX B WXBDXSWMZRP. AFSJKPGGDMW YX NKAMSGC CR AKBA YJBPEWW KMXLHSTSXF GSJBTFWWR DTKCFRVYT DBVDPKO YMWV WCLR. WCH GDF LP HRFFRX OFCKM DW DBZZDWBYX AKXHK BID B XOUVT HR NICVBV. YEW EHREGQGX GVVXD ICDTQCCOFRVYX JVRAIB. CXF CBTBTLRT EXEUAZN CNXWKHFXFAI ICN ZHVHJYIWB WO LFO JIFKMTYT GFZUT MOUF WEKOFUIKTXETQ JSOCEM OECMZVT ICMZVYXBO L QBX PYQICLYYX LTEO. S FVD GOTMIOGWTV, LPCS WFK DGWWR SDCW JEIYN WCKQCN O UFZXLHOTQ BBH WRVXIIVZAJ B YYEBGHZSJC RBHKMQB WFEJBKHA. BVTXZWYQVX FWD AM CTXWFKCBXS ZHJF WURL HFWCCRTG W CCCOB YKF XHBVYCWHDC DCM CT YYAMB FCQL LP UITRRJ LJS FAITZS DQIHJS. DQI CS TVLCT WNVRP N YYAC HX GSIWZH JOICYX WKBW YX GKDI EH GOSQ ATNXR.


Tekst je šifrovan Vižnerovom šifrom (preko Crypt Tool programa). Korišćen je alfabet, znači nema slova Č,Ć,Š,Đ,Ž i Dž (nažalost, jer program nema azbuku, a nisam imao vremena ručno da šifrujem).

Ajde da vidimo da li će neko uspeti ovo dešifrovati i za koliko vremena (ključna reč nije jako dugačka da bi olakšao dešifrovanje).

---