ZEMRIS

FER                                                                                                                                

Igor Lazić

0036357503

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Digitalni potpis

Seminarski rad iz kolegija Operacijski sustavi 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

      

Sadržaj

 

            Općenito o digitalnom potpisu    

 

Uvod

Osnovni principi rada digitalnog potpisa

Uloga povjerljive stranke i potpisivanje javnog ključa

Potpisi i zakon

 

Algoritmi i njihova implementacija

 

Kriptografske osnove digitalnog potpisa

Opis SHA-1 «Secure Hash Algorithm» funkcije

Opis DSA «Digital Signature Algorithm»

          Korištenje DSA

        Parametri korišteni u DSA

        Generiranje potpisa

        Provjera valjanosti potpisa

        Dodatak 1

        Dodatak 2

       

        Zaključak

 

 

 

 

 

         

 

1. Općenito o digitalnom potpisu

 

1.1. Uvod

 

          Današnji opće prihvaćeni način ovjeravanja dokumenata vlastoručnim potpisom vuče korijene od samih početaka ljudske pismenosti. Potpisi se danas nalaze na najrazličitijm dokumentima, od različitih ugovora, naloga, čekova pa sve do privatnih pisama. Prema postojećim zakonima potpisom se smatra ne samo vlastoručni potpis, već i bilo koji drugi znak na dokumentu načinjen s ciljem ovjeravanja dokumenta. Ipak, na računalima se ne smatra svaki potpis digitalnim potpisom. Različite znakovne ili tekstualne oznake u datotekama ili elektronskoj pošti ili kopije vlastoručnog potpisa krajnje su neprimjerene i nepouzdane, prije svega zbog trivijalnog krivotvorenja. Razvojem i širenjem računala a napose računalnih mreža, postalo je jasno da je potreban posve novi način ovjeravanja. Temelji za pouzdanu provjeru porijekla informacija, «digitalni potpis», stvoreni su 1976. godine otkrićem kriptografije javnog ključa (Diffie-Hellman), koja se još naziva i asimetričnom kriptografijom. Zanimljivo je napomenuti da je ovaj način kriptiranja podataka, prema nekim informacijama [J H Ellis: The Possibility of Secure Non-Secret Digital Encryption, CESG Report, January 1970] bio poznat britanskoj tajnoj službi nekoliko godina prije nego spomenutoj dvojici istraživača.  

Danas, kada većina razvijenih zemalja u svoje zakone uvodi i zakon o digitalnom potpisu, ovo područje se nalazi na granici dva svijeta, kriptografije i prava. Osim pravnih problema oko primjene digitalnog potpisa, postoje i pravni problemi vezani uz implementaciju algoritama digitalnog potpisa, uglavnom zbog softverskih patenata kojima je velik broj algoritama zaštićen, ali i zbog restriktivnih regulativa pojedinih zemalja vezanih uz kriptografske proizvode općenito. Tako je npr. izvoz «jakog» enkripcijskog softvera iz SAD-a bio zabranjen sve do pred kraj 1999. godine. Isto tako, u Francuskoj je upotreba alata za enkripciju bila zabranjena do početka 1999. Ipak, naglim širenjem elektronskog poslovanja postalo je nužno ovakve odredbe ukinuti, i omogućiti kako sigurnu zaštitu informacija šifriranjem tako i zaštitu od mogućih prijevara, autentifikacijom. Upravo idealnim za ovo potonje nameće se digitalni potpis.

         

         

 

 

1.2. Osnovni principi rada digitalnog potpisa

 

 

Princip digitalnog potpisa

 

Pretpostavimo da dvoje ljudi A i B, žele razmjenjivati potpisane poruke (podatke) tj. žele biti sigurni u identitet osobe od koje su poruku dobili. Kao prvo, obje osobe kreiraju par komplementarnih ključeva, javni i tajni ključ. Važno je naglasiti da se poznavanjem javnog ključa ne može izračunati tajni ključ u nekom razumnom vremenu (vrijeme potrebno za izračunavanje tajnog ključa iz poznatog javnog ključa, tj. razbijanje šifre, mjeri se milijunima godina na danas najjačim raspoloživim računalima). Nakon kreiranja ključeva, osobe A i B razmjenjuju svoje javne ključeve, a potom pošiljatelj (A), koristi svoj tajni ključ za šifriranje sažetka poruke koji je izračunao nekom od «Hash» funkcija. Hash funkcija je funkcija koja iz zadane poruke (podataka) računa sažetak fiksne duljine, obično od 128 do 256 bita. Kada primatelj (B) uspije dešifrirati sažetak poruke javnim ključem pošiljatelja (A), on još računa i sažetak primljene poruke koji potom uspoređuje s upravo dešifriranim, i ako je izračunati sažetak jednak onom dešifriranom, primatelj može biti siguran u porijeklo poruke (podataka), jer je poruka mogla biti šifrirana jedino tajnim ključem pošiljatelja (A), kao i u integritet poruke.

 

princip potpisivanja poruke

 

U cijeloj proceduri samo je jedna stvar slaba karika. Moramo biti apsolutno sigurni da javni ključ za koji mislimo da pripada pošiljatelju (A) zaista i pripada pošiljatelju (A). Naime, ukoliko primatelj (B) ima javni ključ pošiljatelja (C), a vjeruje da ključ pripada pošiljatelju (A), tad je pošiljatelj (C) u mogućnosti krivotvoriti podatke pošiljatelja (A). 

 

 

1.3. Uloga povjerljive stranke i potpisivanje javnog ključa

 

          Opisani problem rješava se na način da se uvodi «povjerljiva stranka», PS (engl. «trusted authority»). Pretpostavka je da povjerljivoj stranci sve ostale stranke vjeruju, te da svoje javne ključeve osobno odnesu na potpisivanje, s tim da im PS prethodno provjeri uobičajene «fizičke» dokumente. U tom slučaju PS koristi svoj tajni ključ (javni ključ PS svima je poznat) za potpisivanje javnog ključa te time garantira svima ostalima ispravnost potpisanog javnog ključa.

          Postoji i druga mogućnost, a to je da PS svima generira par ključeva, te uz prethodnu fizičku autentifikaciju, dodjeljuje ključeve. U tom slučaju svatko tko bi htio provjeriti ispravnost potpisa osobe (O) morao bi u bazi javnih ključeva (koju čuva PS) pronaći javni ključ osobe (O) i potom tim ključem pokušati dešifrirati primljene podatke. Nedostatak ovog drugog modela je taj što u tom slučaju PS posjeduje i tajne ključeve što predstavlja znatan sigurnosni problem ako se isti par ključeva koristi osim za potpisivanje i za šifriranje podataka.

Kao logičan izbor za PS nameću se državne ustanove, sudovi i javni bilježnici, iako su trenutno jedine takve ustanove tvrtke poput «Twawte» i «Verisign» koje izdaju certifikate potrebne tvrtkama koje žele svojim klijentima osigurati sigurnu vezu prema svom web poslužitelju SSL protokolom.

          Osim modela jedne centralne «povjerljive osobe» postoji i neka vrsta hijerarhijskog modela (korišten u sustavu PGP), kod kojeg je svaki korisnik u mogućnosti potpisati javne ključeve drugih osoba (za koje je siguran da pripadaju pravim osobama) te time garantirati drugima, koji su sigurni u ispravnost njegovog javnog ključa, ispravnost potpisanih ključeva.

 

2.1.        Potpisi i zakoni

 

          Zakonske regulative (zemalja koje imaju zakon o digitalnom potpisu) ne određuju niti jednu tehnologiju potpisivanja kao dominantnu, već samo donose propise kojih se svaka od tehnologija mora pridržavati. Kao prvo, od digitalnog se potpisa očekuje da bude jedinstven osobi koja ga koristi, drugo, da se može provjeriti kome pripada odnosno da li zaista pripada osobi koja ga je koristila, treće, da je u potpunoj kontroli osobe koja ga koristi, četvrto, da potvrđuje i sebe i podatke koje potpisuje.

          Već iz ovog vidimo da postoji znatna prednost digitalnog potpisa nad klasičnim metodama autentifikacije. Najveća prednost je ta što se valjanost potpisa provjerava svaki put pri primitku dokumenta, za razliku od klasičnih potpisa koji se provjeravaju tek na sudu, kad se prijevara već odigrala. Osim ove prednosti postoji još jedna značajna prednost, a to je nemogućnost naknadne izmjene potpisanog dokumenta, kao i nemogućnost potpisivanja praznih dokumenata. Ipak, ukoliko krivotvoritelj uspije doći do tajnog ključa, tada bez ikakvih problema može falsificirati podatke bez da postoji i najmanja mogućnost utvrđivanja različitosti takvog potpisa od pravog potpisa, što kod klasičnih metoda ipak nije slučaj.

           Nemali broj kriptografskih algoritama zaštićen je različitim patentima. Tako je npr. najrašireniji asimetrični kriptografski algoritam, RSA, bio patentiran 17 godina sve do rujna 2000. godine, a drugom isto tako vrlo značajnom protokolu, Diffie-Hellman protokolu, patent je istekao u travnju 1997. godine. Nažalost, ovo nisu jedini takvi primjeri kao ni jedini problemi u široj primjeni kriptografskih algoritama. Proizvođači kriptografskog softvera (bili) su prisiljeni proizvoditi po dvije ili čak tri različite verzije istog softverskog paketa da bi se udovoljilo svim izvoznim i patentnim regulativama; zabrana izvoza kriptografskog softvera iz SAD-a s ključem dužim od 40-bita bila je na snazi do pred kraj 1999. godine, tako da je npr. NAI («Network Associates») bio prisiljen imati dvije verzije svog programa PGP, jednu za tržište SAD-a a drugu za internacionalnu tržište. Ipak, obje su verzije koristile «jaku» enkripciju tako što je iskorištena «rupa» u zakonu SAD-a kojim se zabranjuje izvoz softvera u binarnom obliku ali ne i izvornog koda na papiru??? Osim ovog, postojao je i problem zbog patentiranog RSA algoritma, tako da verzije za SAD nisu koristile istu inačicu kao i internacionalne.

          Sličan problem javlja se i s pojavom novog američkog standarda za digitalno potpisivivanje («Digital Signature Standard», DSS, 1994), jer se dijelovi korištenog algoritma (koji sam po sebi nije patentiran) nalaze pod patentnom zaštitom autora sličnog algoritma temeljenog na diskretnim logaritmima (Schorr, 1994, patent vrijedi 17 godina). Ovaj primjer ipak odskače iz mnoštva drugih upravo zbog toga što se radi o standardu koji su obavezne koristiti sve državne ustanove SAD-a; drugim riječima ovaj će patent vrlo vjerojatno američki porezni obveznici osjetiti na vlastitom džepu.

Na kraju spomenimo još i zabranu izvoza bilo kakvog kriptografskog softvera zemljama poput Iraka, Sjeverne Koreje ili Kube.

         

 

2. Tehnički opis digitalnog potpisa

 

2.1. Kriptografski temelji digitalnog potpisa

 

          Današnje tehnike digitalnog potpisivanja temelje se na algoritmima asimetrične kriptografije, poznate još i pod nazivom kriptografija javnog ključa (engl. «public key cryptography»). Algoritme javnog ključa (engl. «public-key algotithms») možemo podijeliti u tri osnovne grupe:

 

1.     algoritmi temeljeni na praktičnoj nemogućnosti faktoriziranja velikih prim brojeva (RSA)

2.     algoritmi temeljeni na praktičnoj nemogućnosti izračunavanja diskretnih logaritama (Diffie-Hellman protokol, DSA)

3.     algoritmi temeljeni na eliptičnim krivuljama (praktične realizacije ove metode su tek u povojima)

 

Osim ovih algoritama postoji još i nekolicina rjeđe korištenih, temeljenih na praktičnoj nemogućnosti utvrđivanja sadržaja ruksaka (engl. «knapsack algorithms», Merkle), no većina današnjih komercijalnih implementacija se može svrstati u jednu od tri glavne kategorije. Recimo još i to da se različite verzije Knapsack algoritma ne smatraju sigurnima zbog toga jer su Rivest i Shamir (neovisno jedan o drugom, Rivest prvu verziju, Shamir dorađenu nakon prvotnog uspješnog razbijanja) uspjeli «razbiti» ovakvu zaštitu.

          Tipičan algoritam iz prve skupine je i najčešće korišteni algoritam javnog ključa, RSA. Algoritam započinje na sljedeći način. Izaberimo dva velika prim broja p i q. Nakon toga izračunamo n=p*q i z=(p-1)*(q-1). U slijdećem koraku uzimamo broj relativno prost broju z i nazivamo ga d. Još nam je jedino potreban e takav da vrijedi e*d=1 mod z. Kad smo izračunali sve ove parametre, spremni smo za šifriranje podataka. Prije svega potrebno je poruku P podijeliti u dijelove od kojih svaki sadrži najviše n znakova (obično se zbog toga uzimaju blokovi po k bitova tako da vrijedi 2k = n). Da bismo šifrirali poruku računamo C=Pe (mod n) a za dešifriranje je potrebno izračunati P=Cd (mod n). Za šifriranje RSA algoritmom potrebni su dakle e i n, a za dešifriranje d i n. Iz toga vidimo da se javni ključ sastoji od (e,n) a tajni ključ od (d,n). Sigurnost ove metode sadržana je u tome što je vrlo teško faktorizirati velike prim brojeve. Teoretski postupak izračunavanja RSA algoritma krajnje je jednostavan. Naime, faktoriziranjem n dobijemo p i q. Iz p i q vrlo jednostavno izračunamo z. Uz poznati z i e (koji je dio javnog ključa) Euklidovim algoritmom dolazimo do d i imamo i tajni ključ (d,n). Ipak, da bi se faktorizirao 200-znamenkasti prim broj potrebno je oko 4 milijarde godina, uz korištenje najboljeg mogućeg algoritma i računala s vremenom izvođenja instrukcije od 1 msec.

          Tipični algoritmi druge skupine su DSA (engl. «digital signature algoritam») i Diffie-Hellman protokol za razmjenu ključeva. Temelje se na računalno vrlo zahtjevnom procesu izračunavanja diskretnih logaritama. Ilustrirajmo to Diffie-Hellman protokolom. Kao prvo, protokol koristi dva parametra p i g, oba javna. Parametar p je prim broj, a parametar g (obično se naziva generator) je cijeli broj manji od p, koji ima sposobnost generiranja bilo koje vrijednosti od 1 do p-1 kada ga se pomnoži samim sobom određeni broj puta mod p. Pretpostavimo sad da dvije osobe, A i B, žele razmjenjivati šifrirane poruke preko nesigurne veze bez da prethodno imaju neki tajni ključ. Prema DH protokolu, obje strane generiraju tajne vrijednosti; osoba (A) generira slučajan broj a, a osoba (B) slučajan broj b. Nakon toga koriste javne parametre p i g da bi izračunali vrijednost zajedničkog tajnog ključa K, i to tako da osoba (A) izračuna svoju javnu vrijednost kao ga mod p, a osoba (B) gb mod p. Javne vrijednosti se razmjene (nesigurnim kanalom), a potom osoba (A) računa Kab=(gb)a mod p, a osoba (B) računa Kba=(ga)b mod p. Obje strane ovim postupkom dobivaju isti rezultat, Kab=Kba=K, tj. razmjenili su tajni ključ preko nesigurne veze. Sigurnost ovog protokola temelji se na problemima izračunavanja diskretnih logaritama. Naime, praktično je vrlo teško izračunati dijeljeni tajni ključ K, K=gab mod p uz dovoljno velik p uz poznavanje samo javnih vrijednosti ga mod p i gb mod p.

          Jedno relativno novo područje (prvi radovi su iz 1993. godine, A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, Boston, 1993) u kriptografiji javnog ključa je i šifriranje korištenjem eliptičnih krivulja. Prednosti ove metode su prije svega kraći ključevi i kao rezultat toga i bolje performanse algoritma uz zadržavanje jednake sigurnosti kao i kod prethodno opisanih algoritama. Pod pojmom «eliptična krivulja» (engl. «elliptic curve») podrazumijeva se poseban tip krivulje (ne elipsa) kao ovaj na donjoj slici.    

 

tipičan primjer eliptične funkcije

 

          Ovakav tip krivulje (konkretan primjer je y2-y=x3-x2) ima svojstvo da iako se «proteže» u beskonačnost, krivulja prolazi kroz konačno mnogo cjelobrojnih koordinatnih parova (x,y). Definiramo li operator zbrajanja nad tim parovima (x,y) dobili smo grupu. Zbrajanjem dvije točke iz tako stvorene grupe dobijamo treću točku (također iz grupe). Krivulja prikazana na obje ove slike može stvoriti polje od svega 5 cjelobrojnih parova (uključujući točku O koja je svojevrsni neutralni element), što za bilo kakvu kriptografsku upotrebu nije dovoljno, no poslužiti će za ilustraciju. Da bi cijela stvar funkcionirala potrebno je još definirati i točku O, negdje u beskonačnosti, gdje sve vertikalne linije konvergiraju. Uočimo još jedno vrlo zanimljivo svojstvo; kada povučemo tangentu na krivulju u nekoj točki, tangenta uvijek prolazi još jednom točkom. Npr. tangenta kroz a prolazi i točkom c, a tangenta na b i točkom a (donja slika).

          Zbrajanje elemenata vršimo tako da povučemo pravac kroz dvije točke koje želimo zbrojiti,

(elliptic curve)

 

zatim kroz točku kojoj je taj pravac tangenta povučemo pravac u točku O. Taj novi pravac siječe krivulju u još jednoj točki koja je rezultat zbrajanja prethodne dvije. Na gornjoj slici imamo primjer zbrajanja točaka a i b tako da povučemo pravac kroz te dvije točke. Pošto je taj pravac tangenta na krivulju u točki b, kroz točku b povučemo pravac u točku O. Taj novi pravac siječe krivulju u točki c i to je rezultat zbrajanja a i b. Zbrajanje točki a i d daje rezultat O.

Skalarno množenje nije ništa drugo nego višestruko zbrajanje elementa samim sobom. Tako npr. 2a je a+a=b, 3a=(a+a)+a=c, 4a=((a+a)+a)+a=d, itd.

   U kriptografskim primjenama promatraju se samo cjelobrojne koordinate (x,y) a aritmetika se izvodi modulo p gdje je p ili veliki prim broj ili velika potencija od 2. Za kriptografske primjene prikladna grupa sadrži N elemenata gdje je N skoro jednak p, N=k*q, q je prim broj a k je mali broj.

Iz ovoga vidimo da smo uspjeli stvoriti algebarsku grupu, GF, koja sadrži N članova i pogodna je za izvođenje kriptografskih operacija poput Diffie-Hellman i SPEKE.

 

 

2.2. Opis SHA-1 «Secure Hash Algorithm»

 

   Kao što je u uvodu već napisano, digitalni potpis mora garantirati vjerodostojnost potpisane informacije. Upravo za to se koriste Hash funkcije koje izračunavaju sažetak poruke. Jedna od Hash funkcija je i SHA (inače dio američkog standarda za digitalno potpisivanje koji su obavezne koristiti sve Vladine ustanove) koja će ovdje biti detaljno opisana.

   SHA funkcija, tj. SHA-1 koja je ponešto izmijenjena u odnosi na prvotni dizajn koji potječe od američke agencije za nacionalnu sigurnost, NSA (National Security Agency), kao ulaz prima samu poruku i iz poruke računa 160-bitni sažetak. Sažetak poruke teoretski nije jedinstven, ali je praktična vjerojatnost dobivanja istog sažetka za dvije razičite poruke zanemarivo mala.

   SHA započinje s time što dopunjuje poruku tako da poruka bude n*512 bitova duga. U zadnjih 64 bita zadnjeg 512 bitnog bloka sadržana je duljina poruke l. Poruka se dopunjuje tako da se doda «1» (bitovna znamenka), zatim se dodaje m nula (broj nula m, ovisi o tome koliko bitova je potrebno da blok bude 512 bitova dug) a kao zadnja 64 bita poruke stavlja se duljina cijele poruke (svih blokova poruke zajedno). Tako dopunjena poruka (engl. «padded message») se potom procesira kao n 512 bitnih blokova.

 

   PRIMJER:

 

[Riječ = 32 bita]

 

Pretpostavimo da je poruka duljine l < 264. Prije ulaska u SHA-1, poruka se dopunjuje s desne strane na sljedeći način:

a. "1" se dodaje. Primjer: ako je originalna poruka "01010000", nakon dodavanja je "010100001".

b. "0"e se dodaju. Broj nula ovisi o duljini originalne poruke. Zadnja 64 bita zadnjeg 512 bitnog bloka rezervirana su za duljinu l izvorne poruke.

Primjer: Pretpostavimo da je originalna poruka bitovni niz

01100001 01100010 01100011 01100100 01100101.

 

Nakon koraka (a) poruka je

01100001 01100010 01100011 01100100 01100101 1.

 

Zbog duljine poruke l = 40, broj bitova u gornjem stringu je 41 te se stoga 407 "0" dodaje, što čini ukupno 448 bitovnih znamenki. U heksadekadskom zapisu to je

61626364 65800000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000.

 

c. Duljina poruke l se prikazuje u dvije riječi, tj. sa 64 bita. Ako je l < 232 tada su prvih 32 bita nule. Ove dvije riječi (64-bita) se dodaju gornjoj poruci. to turn off I

Primjer: Pretpostavimo da je originalna poruka kao ona u (b). Tada je l = 40 (primjetimo da se l računa prije bilo kakvog dopunjavanja). Dvo-riječni prikaz od 40 je hex 00000000 00000028. Zbog toga je konačni dopunjena poruka jednaka (hex)

61626364 65800000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000028.

 

Dopunjena poruka sadrži 16 * n riječi gdje je n > 0. Dopunjena poruka je niz od n blokova M1 , M2, ... , Mn, gdje svaki Mi sadrži 16 riječi i M1 sadrži prve znakove (ili bitove) poruke.

  

   Nakon dopunjavanja poruke na n * 512 bitova, poruka se obrađuje nizom od 80 funkcija.

 

Niz logičkih funkcija f0, f1,..., f79 se koristi u SHA-1. Svaka ft, 0 <= t <= 79, radi na tri 32-bitne riječi B, C, D i proizvodi 32-bitnu riječ kao izlaz. ft(B,C,D) su definirane na sljedeći način: za riječi B, C, D,

ft(B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)

ft(B,C,D) = B XOR C XOR D (20 <= t <= 39)

ft(B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)

ft(B,C,D) = B XOR C XOR D (60 <= t <= 79).

  

   Osim ovih 4 funkcije, za daljnje računanje sažetka potrebne su i četiri konstante:   

 

Niz konstanti veličine jedne riječi, K(0), K(1), ... , K(79) se koristi u SHA-1. U heksadekadskom zapisu te su riječi

Kt = 5A827999 ( 0 <= t <= 19)

Kt = 6ED9EBA1 (20 <= t <= 39)

Kt = 8F1BBCDC (40 <= t <= 59)

Kt = CA62C1D6 (60 <= t <= 79).

 

 

          Nakon što smo definirali sve potrebne funkcije i konstante, možemo detaljno opisati posljednju fazu rada SHA-1, samo računanje sažetka.

 

Sažetak poruke se računa korištenjem konačnog dopunjenog oblika poruke. Za računanje se koriste dva spremnika od kojih se svaki sastoji od pet 32-bitnih riječi, i niza od osamdeset 32-bitnih riječi. Riječi u prvom 5-riječnom spremniku su označene sa A,B,C,D,E. Riječi u drugom  5-riječnom spremniku označene su sa H0, H1, H2, H3, H4. Riječi 80-riječnog niza označene su sa  W0, W1,..., W79. Koristi se još i jedno-riječni spremnik TEMP.

Da bi se generirao sažetak, prethodno definirani 16-riječni (512-bitni) blokovi M1, M2,..., Mn se redom obrađuju. Obrada svakog bloka Mi se sastoji od 80 koraka.

Prije bilo kakvog procesiranja blokova, {Hi} (izlazni spremnici u kojima na kraju postupka ostaje rezultat) se inicijaliziraju na sljedeći način: u heksadekadskom zapisu,

H0 = 67452301

H1 = EFCDAB89

H2 = 98BADCFE

H3 = 10325476

H4 = C3D2E1F0.


Sad se M1, M2, ... , Mn obrađuju. Da bi obradili Mi, koristimo sljedeći postupak:

a. Podijelimo Mi u 16 riječi W0, W1, ... , W15, gdje je W0 skroz lijeva riječ.

b. Za t = 16 do 79 postavljamo Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).

c. Postavljamo A = H0, B = H1, C = H2, D = H3, E = H4.

d. Za t = 0 do 79 računamo

TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;

E = D; D = C; C = S30(B); B = A; A = TEMP;

 

e. Postavljamo H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.


Nakon procesiranja Mn, sažetak poruke je 160-bitni string predstavljen sa 5 riječi:

H0 H1 H2 H3 H4.

 

 

   Ovim SHA-1 funkcija računanja sažetka poruke završava. Ilustrirajmo cijeli postupak na još složenijem primjeru.

 

Dodatak. PRIMJER PORUKE I NJENOG SAŽETKA



Neka je poruka ASCII zapis niza "abc",

01100001 01100010 01100011.


Ova poruka je duljine l = 24. U koraku (a) dopunjavanja, dodajemo "1". U koraku (b) dodajemo 423 "0". U koraku  (c) dodajemo hex 00000000 00000018, što je dvo-riječni zapis od 24. Pošto se konačna poruka sastoji od samo jednog 512-bitnog bloka, n je 1.

Inicijaliziramo vrijednosti {Hi} na

H0 = 67452301
H1 = EFCDAB89
H2 = 98BADCFE
H3 = 10325476
H4 = C3D2E1F0.

Počinjemo obrađivati blok 1. Riječi bloka 1 su 

W[0] = 61626380
W[1] = 00000000
W[2] = 00000000
W[3] = 00000000
W[4] = 00000000
W[5] = 00000000
W[6] = 00000000
W[7] = 00000000
W[8] = 00000000
W[9] = 00000000
W[10] = 00000000
W[11] = 00000000
W[12] = 00000000
W[13] = 00000000
W[14] = 00000000
W[15] = 00000018.

Heksadekadske vrijednosti od A,B,C,D,E nakon petlje za t, "for t = 0 to 79" su

       
            A           B           C           D           E
 
t =  0: 0116FC33    67452301    7BF36AE2    98BADCFE    10325476
t =  1: 8990536D    0116FC33    59D148C0    7BF36AE2    98BADCFE
t =  2: A1390F08    8990536D    C045BF0C    59D148C0    7BF36AE2
t =  3: CDD8E11B    A1390F08    626414DB    C045BF0C    59D148C0
t =  4: CFD499DE    CDD8E11B    284E43C2    626414DB    C045BF0C
t =  5: 3FC7CA40    CFD499DE    F3763846    284E43C2    626414DB
t =  6: 993E30C1    3FC7CA40    B3F52677    F3763846    284E43C2
t =  7: 9E8C07D4    993E30C1    0FF1F290    B3F52677    F3763846
t =  8: 4B6AE328    9E8C07D4    664F8C30    0FF1F290    B3F52677
t =  9: 8351F929    4B6AE328    27A301F5    664F8C30    0FF1F290
t = 10: FBDA9E89    8351F929    12DAB8CA    27A301F5    664F8C30
t = 11: 63188FE4    FBDA9E89    60D47E4A    12DAB8CA    27A301F5
t = 12: 4607B664    63188FE4    7EF6A7A2    60D47E4A    12DAB8CA
t = 13: 9128F695    4607B664    18C623F9    7EF6A7A2    60D47E4A
t = 14: 196BEE77    9128F695    1181ED99    18C623F9    7EF6A7A2
t = 15: 20BDD62F    196BEE77    644A3DA5    1181ED99    18C623F9
t = 16: 4E925823    20BDD62F    C65AFB9D    644A3DA5    1181ED99
t = 17: 82AA6728    4E925823    C82F758B    C65AFB9D    644A3DA5
t = 18: DC64901D    82AA6728    D3A49608    C82F758B    C65AFB9D
t = 19: FD9E1D7D    DC64901D    20AA99CA    D3A49608    C82F758B
t = 20: 1A37B0CA    FD9E1D7D    77192407    20AA99CA    D3A49608
t = 21: 33A23BFC    1A37B0CA    7F67875F    77192407    20AA99CA
t = 22: 21283486    33A23BFC    868DEC32    7F67875F    77192407
t = 23: D541F12D    21283486    0CE88EFF    868DEC32    7F67875F
t = 24: C7567DC6    D541F12D    884A0D21    0CE88EFF    868DEC32
t = 25: 48413BA4    C7567DC6    75507C4B    884A0D21    0CE88EFF
t = 26: BE35FBD5    48413BA4    B1D59F71    75507C4B    884A0D21
t = 27: 4AA84D97    BE35FBD5    12104EE9    B1D59F71    75507C4B
t = 28: 8370B52E    4AA84D97    6F8D7EF5    12104EE9    B1D59F71
t = 29: C5FBAF5D    8370B52E    D2AA1365    6F8D7EF5    12104EE9
t = 30: 1267B407    C5FBAF5D    A0DC2D4B    D2AA1365    6F8D7EF5
t = 31: 3B845D33    1267B407    717EEBD7    A0DC2D4B    D2AA1365
t = 32: 046FAA0A    3B845D33    C499ED01    717EEBD7    A0DC2D4B
t = 33: 2C0EBC11    046FAA0A    CEE1174C    C499ED01    717EEBD7
t = 34: 21796AD4    2C0EBC11    811BEA82    CEE1174C    C499ED01
t = 35: DCBBB0CB    21796AD4    4B03AF04    811BEA82    CEE1174C
t = 36: 0F511FD8    DCBBB0CB    085E5AB5    4B03AF04    811BEA82
t = 37: DC63973F    0F511FD8    F72EEC32    085E5AB5    4B03AF04
t = 38: 4C986405    DC63973F    03D447F6    F72EEC32    085E5AB5
t = 39: 32DE1CBA    4C986405    F718E5CF    03D447F6    F72EEC32
t = 40: FC87DEDF    32DE1CBA    53261901    F718E5CF    03D447F6
t = 41: 970A0D5C    FC87DEDF    8CB7872E    53261901    F718E5CF
t = 42: 7F193DC5    970A0D5C    FF21F7B7    8CB7872E    53261901
t = 43: EE1B1AAF    7F193DC5    25C28357    FF21F7B7    8CB7872E
t = 44: 40F28E09    EE1B1AAF    5FC64F71    25C28357    FF21F7B7
t = 45: 1C51E1F2    40F28E09    FB86C6AB    5FC64F71    25C28357
t = 46: A01B846C    1C51E1F2    503CA382    FB86C6AB    5FC64F71
t = 47: BEAD02CA    A01B846C    8714787C    503CA382    FB86C6AB
t = 48: BAF39337    BEAD02CA    2806E11B    8714787C    503CA382
t = 49: 120731C5    BAF39337    AFAB40B2    2806E11B    8714787C
t = 50: 641DB2CE    120731C5    EEBCE4CD    AFAB40B2    2806E11B
t = 51: 3847AD66    641DB2CE    4481CC71    EEBCE4CD    AFAB40B2
t = 52: E490436D    3847AD66    99076CB3    4481CC71    EEBCE4CD
t = 53: 27E9F1D8    E490436D    8E11EB59    99076CB3    4481CC71
t = 54: 7B71F76D    27E9F1D8    792410DB    8E11EB59    99076CB3
t = 55: 5E6456AF    7B71F76D    09FA7C76    792410DB    8E11EB59
t = 56: C846093F    5E6456AF    5EDC7DDB    09FA7C76    792410DB
t = 57: D262FF50    C846093F    D79915AB    5EDC7DDB    09FA7C76
t = 58: 09D785FD    D262FF50    F211824F    D79915AB    5EDC7DDB
t = 59: 3F52DE5A    09D785FD    3498BFD4    F211824F    D79915AB
t = 60: D756C147    3F52DE5A    4275E17F    3498BFD4    F211824F
t = 61: 548C9CB2    D756C147    8FD4B796    4275E17F    3498BFD4
t = 62: B66C020B    548C9CB2    F5D5B051    8FD4B796    4275E17F
t = 63: 6B61C9E1    B66C020B    9523272C    F5D5B051    8FD4B796
t = 64: 19DFA7AC    6B61C9E1    ED9B0082    9523272C    F5D5B051
t = 65: 101655F9    19DFA7AC    5AD87278    ED9B0082    9523272C
t = 66: 0C3DF2B4    101655F9    0677E9EB    5AD87278    ED9B0082
t = 67: 78DD4D2B    0C3DF2B4    4405957E    0677E9EB    5AD87278
t = 68: 497093C0    78DD4D2B    030F7CAD    4405957E    0677E9EB
t = 69: 3F2588C2    497093C0    DE37534A    030F7CAD    4405957E
t = 70: C199F8C7    3F2588C2    125C24F0    DE37534A    030F7CAD
t = 71: 39859DE7    C199F8C7    8FC96230    125C24F0    DE37534A
t = 72: EDB42DE4    39859DE7    F0667E31    8FC96230    125C24F0
t = 73: 11793F6F    EDB42DE4    CE616779    F0667E31    8FC96230
t = 74: 5EE76897    11793F6F    3B6D0B79    CE616779    F0667E31
t = 75: 63F7DAB7    5EE76897    C45E4FDB    3B6D0B79    CE616779
t = 76: A079B7D9    63F7DAB7    D7B9DA25    C45E4FDB    3B6D0B79
t = 77: 860D21CC    A079B7D9    D8FDF6AD    D7B9DA25    C45E4FDB
t = 78: 5738D5E1    860D21CC    681E6DF6    D8FDF6AD    D7B9DA25
t = 79: 42541B35    5738D5E1    21834873    681E6DF6    D8FDF6AD.

 

Ovime je završena obrada bloka 1. Vrijednosti od {Hi} su

H0 = 67452301 + 42541B35 = A9993E36
H1 = EFCDAB89 + 5738D5E1 = 4706816A
H2 = 98BADCFE + 21834873 = BA3E2571
H3 = 10325476 + 681E6DF6 = 7850C26C
H4 = C3D2E1F0 + D8FDF6AD = 9CD0D89D.

Sažetak poruke je A9993E36 4706816A BA3E2571 7850C26C 9CD0D89D

 

                                                  

2.3. Opis DSA «Digital Signature Algorithm»

 

Prikaz rada DSA

 

2.3.1. Korištenje DSA


   “Digital Signature Algorithm” se koristi za potpisivanje kao i za provjeru valjanosti već načinjenog potpisa. Svaki potpisnik posjeduje javni i tajni ključ. Tajni ključ se koristi u procesu stvaranja digitalnog potpisa, a javni ključ se koristi u procesu provjere valjanosti potpisa. U oba slučaja se algoritam primjenjuje na sažetak poruke, M, načinjen korištenjem “Secure Hash Algorithm” funkcije. Bez poznavanja tajnog ključa potpisnika nije moguće stvoriti valjan potpis, tj. nije moguće krivotvoriti potpis (u razumnom vremenskom periodu). Unatoč tome, svatko je u mogućnosti provjeriti valjanost potpisa korištenjem javnog ključa potpisnika.

Prije korištenja DSA mora se utvrditi nekakva povezanost para ključeva (javnog i tajnog) sa korisnikom. To se obično ostvaruje već opisanim potpisivanjem javnog ključa od strane “povjerljive stranke” (engl. “trusted party”) uz prethodnu provjeru stvarnih fizičkih dokumenata.


2.3.2. Parametri korišteni u DSA


DSA koristi sljedeće parametre

1. p = prim broj koji se koristi kao modul, gdje je 2L-1 < p < 2L za 512 = < L = <1024 i gdje je L višekratnik od 64

2. q = prim broj koji je djelitelj od p - 1, gdje je 2159 < q < 2160

3. g = h(p-1)/q mod p, gdje je h bilo koji cijeli broj 1 < h < p - 1 takav da je h(p-1)/q mod p > 1
(g je reda q mod p)

4. x = slučajno ili pseudoslučajno generirani cijeli broj takav da vrijedi 0 < x < q

5. y = gx mod p

6. k = slučajno ili pseudoslučajno generirani cijeli broj takav da vrijedi 0 < k < q

Cijeli brojevi p,q, i g mogu biti javni i zajednički grupi korisnika. Korisnikovi tajni i javni ključ su x i y, tim redom, i ne mijenjaju se kroz određeni vremenski period. Parametri x i k se koriste samo za stvaranje digitalnog potpisa i moraju biti tajni, s tim da se parametar k mora regenerirati za svaki potpis ponovno.


2.3.3. Generiranje potpisa

   Potpis poruke M je par brojeva r i s izračunatih prema sljedećim jednadžbama

r = (gk mod p) mod q

s = (k-1(SHA(M) + xr)) mod q.

   k-1 je multiplikativni inverz od k, po modulu q; (k-1 k) mod q = 1 i 0 < k-1 < q. Izlaz iz funkcije SHA za zadanu ulaznu poruku M (SHA(M)) je 160-bitni niz. Da bi se mogao izračunati s prema gornjim jednadžbama, taj se bitovni niz mora pretvoriti u cijeli broj.


   Opcionalno može se provjeriti da li je r = 0 ili s = 0. Ako je bilo r = 0 ili s = 0,  za k bi se trebala generirati nova vrijednost, a potpis bi se trebao ponovno izračunati (ipak, jako je malo vjerojatno da će r ili s biti jednaki 0 ako su potpisi ispravno generirani).


Potpis se nakon opisanog postupka prenosi do osobe koja ga provjerava.


2.3.4 Provjera valjanosti potpisa


   Prije provjere valjanosti potpisane poruke, osobi koja provjerava potpis dostavljaju se parametri p,q i g te pošiljateljev javni ključ i identitet. Važno je naglasiti da osoba koja provjerava valjanost potpisa mora biti apsolutno sigurna da ti parametri zaista potječu od onog tko je potpis generirao, tj. da su istovjetni parametrima p,q i g koje je koristio potpisnik poruke.

Uvedimo sad M', r' i s' koji će predstavljati primljene verzije M,r, i s, redom, i neka y bude javni ključ potpisnika. Strana koja provjerava potpis prvo provjerava da li je 0 < r' < q i 0 < s' < q; ako bilo koji od ova dva uvjeta nije zadovoljen, potpis će biti proglašen nevažećim. Ako pak uvjeti vrijede, provjera potpisa se nastavlja računanjem

 

w = (s')-1 mod q

u1 = ((SHA(M')w) mod q

u2 = ((r')w) mod q

v = (((g)ul (y)u2) mod p) mod q.

 

Ako je v = r’, tada je potpis provjeren i osoba koja provjerava potpis može s velikom sigurnošću vjerovati da je primljena poruka stigla od osobe koja ima tajni ključ x, koji je komplementaran sa y.  Postoji i formalni dokaz spomentute tvrdnje (opisan u dodatku); ako je M' = M, r' = r, i s' = s tada vrijedi v = r'.

Ako v nije jednako r', tada je poruka morala biti ili mijenjana ili je bila nepravilno potpisana pravim tajnim ključem. U oba slučaja poruku treba smatrati nevažećom.

 

 

Dodatak 1. Generiranje slučajnih brojeva korištenih u DSA

Bilo koja implementacija DSA mora biti u mogućnosti generirati slučajne ili pseudoslučajne brojeve. Takvi se brojevi koriste za stvaranje korisnikovog tajnog ključa, x, i jednokratnog tajnog broja k (koji se stvara za svaku poruku posebno). Ti se brojevi biraju tako, da budu u intervalu od 0 do 160-bitnog prim broja q. Važno je napomenuti da se u svrhu generiranja ovih brojeva obično koristi generator slučajnih brojeva koji je također definiran u jednom drugom standardu.

Dodatak 2. Dokaz da je v = r'

   Smisao ovog dodatka je da pokaže kako u slučaju kad je M' = M, r' = r i s' = s pri provjeri potpisa, tada je v = r'. Za dokaz tvrdnje potreban nam je sljedeći rezultat.

LEMA. Neka su p i q prim brojevi takvi da q dijeli p - 1, h pozitivni cijeli broj manji od p, i g = h(p-1)/q mod p. Tada vrijedi gq mod p = 1, a ako vrijedi m mod q = n mod q, tada vrijedi i gm mod p = gn mod p.

Ova nam je lema potrebna za dokaz.

TEOREM. Ako vrijedi M' = M, r' = r, i s' = s pri provjeri potpisa, tada vrijedi i v = r'.

Dokaz: imamo

w = (s')-1 mod q = s-1 mod q

u1 = ((SHA(M'))w) mod q = ((SHA(M))w) mod q

u2 = ((r')w) mod q = (rw) mod q.

 

Sada je y = gx mod p, tako da prema lemi vrijedi,

 

v = ((gu1 yu2) mod p) mod q

= ((gSHA(M)w yrw) mod p) mod q

= ((gSHA(M)w gxrw) mod p) mod q

= ((g(SHA(M)+xr)w) mod p) mod q.

Isto tako

s = (k-1(SHA(M) + xr)) mod q.

Zbog

w = (k(SHA(M) + xr)-1) mod q

(SHA(M) + xr)w mod q = k mod q.

Premi lemi,

v = (gk mod p) mod q

= r

= r'.

 

Zaključak

          Budućnost digitalnog potpisa je u svakom slučaju svijetla. Koja god tehnologija ili algoritam bili korišteni, teško je već danas zamisliti svijet računalnih mreža bez odgovarajućih algoritama autentifikacije. No unatoč tomu što je digitalni potpis dio računalnog svijeta koji se vrlo brzo mijenja i prihvaća novitete, pri oslanjanju na jedan od algoritama za digitalni potpis važno je razmišljati ne samo o današnjoj računalnoj moći, već i o nadolazećim računalima koja će eventualno biti dovoljno snažna za krivotvorenje potpisa pukom silom (engl. “brute force attack”). Druga, uvijek prisutna neugodna mogućnost je da već danas postoji način “razbijanja” kripto zaštite (isto tako i digitalnih potpisa) pomoću nekih brzih metoda faktoriziranja (velikih) prim brojeva, koje bi tad ugrozile ne samo kripto zaštitu algoritmima poput danas najraširenijeg RSA, već bi vrlo lako osporile i digitalne potpise (načinjene s RSA ili sličnim algoritmom). Ipak, dok se to ne dogodi (ako se ikad dogodi), ostaje nam vjerovati saznanjima današnje matematike koja kaže da je digitalni potpis praktički neprobojan ne samo danas, već i za desetljeća koja dolaze.