Početci kriptografije digitalnog novca!

Postoji trenutak u životu svakog čovjeka koji počne dublje razmišljati o novcu, kada shvati da ono što koristi svaki dan – papir, karticu ili broj na ekranu – zapravo nije ono što je mislio da jeste. Novac nije samo sredstvo razmjene. Novac je sistem povjerenja. A kada se počneš pitati kome zapravo vjeruješ, tada počinje pravo putovanje.

Danas živimo u vremenu gdje se novac kreće brže nego ikada. Jedan klik, jedna transakcija, jedan digitalni potpis – i vrijednost prelazi s jednog kraja svijeta na drugi. Ali iza te brzine krije se nešto mnogo dublje. Krije se decenijama razvijan sistem kriptografije, matematike i kontrole, koji je postojao mnogo prije nego što je Bitcoin ugledao svjetlo dana.

Ako se vratimo unazad, vidjećemo da ideja digitalnog novca nije nastala preko noći. Naučnici, kriptografi i institucije radili su godinama na rješavanju jednog ključnog problema: kako omogućiti razmjenu vrijednosti u digitalnom svijetu, a da se zadrži sigurnost, privatnost i povjerenje?

Tu dolazimo do pojmova koji na prvi pogled zvuče komplikovano – digitalni potpisi, sertifikacione autoritete, diskretni logaritmi, zero-knowledge dokazi. Ali kada ih ogolimo do suštine, vidimo da svi oni pokušavaju riješiti isto pitanje: kako dokazati da nešto jeste istina, bez potrebe da vjerujemo jedni drugima na riječ.

Zamisli svijet prije interneta. Ako si nekome dao novac, morao si biti siguran da je taj novac stvaran. Ako si potpisao dokument, morao si fizički biti prisutan. Povjerenje je bilo vezano za identitet, institucije i fizičku realnost.

Dolaskom interneta, sve se mijenja. Informacije se mogu kopirati beskonačno. Digitalni fajl može biti identičan originalu. I tu nastaje problem – kako spriječiti da se isti digitalni novac potroši dva puta? Kako znati da je potpis zaista potpisao onaj ko tvrdi da jeste? Kako povezati identitet sa matematikom?

Odgovor koji je svijet pokušavao izgraditi bio je sistem sertifikacionih autoriteta. Institucije koje potvrđuju ko je ko. Digitalni pasoši interneta. One kažu: „Ovaj javni ključ pripada ovoj osobi.“ I na taj način grade most između identiteta i matematike.

Ali tu dolazimo do ključnog problema. Ako moraš vjerovati autoritetu – onda sistem nije zaista slobodan. Samo je digitalizovan.

Zato su razvijeni koncepti poput zero-knowledge dokaza. Ideja koja na prvi pogled djeluje kao paradoks: možeš dokazati da nešto znaš, a da ne otkriješ šta znaš. Možeš dokazati identitet bez otkrivanja identiteta. Možeš dokazati posjedovanje bez otkrivanja sadržaja.

Ovo je bio trenutak kada se matematika počela suprotstavljati sistemu povjerenja.

Kriptografija je počela nuditi nešto što nijedna institucija nije mogla: dokaz bez povjerenja.

I upravo iz tog svijeta – svijeta pokušaja, eksperimenata i neuspjelih rješenja – rodila se ideja koja će kasnije promijeniti sve.

Ali da bismo razumjeli zašto je Bitcoin nastao, moramo prvo razumjeti šta je sve postojalo prije njega.

Moramo razumjeti kako su ljudi pokušavali riješiti problem novca u digitalnom svijetu.

Moramo razumjeti zašto su svi ti sistemi, uprkos briljantnoj matematici, i dalje imali jednu slabost.

Povjerenje.

Zato sada ne učimo samo o kriptografiji.

Učimo o temelju jedne nove civilizacije.

Učimo kako je nastao novac koji ne traži dozvolu.

I zato… zaronimo zajedno u početke kriptografije novca.

Originalni tekst

Kriptografija i teorija brojeva za digitalni novac

autor: J. Orlin Grabbe

Napomena: Da biste pravilno pročitali sljedeći tekst, vaš web pregledač mora podržavati indekse i eksponente; tj. HTML komande „sub“ i „sup“. Ove komande se koriste rijetko, ali se ipak koriste.

Sposobnost napada ili zloupotrebe sistema digitalnog novca u velikoj mjeri zavisi od kriptografije i kriptografskih protokola koji se koriste. Dobar sistem novca koristi dobru kriptografiju. Dobra kriptografija zahtijeva jake algoritme, ključeve odgovarajuće dužine i sigurno upravljanje ključevima. Bez toga, privatnost je minimalna.

Dobar sistem novca koristi dobre protokole. Sistem digitalnog novca Stefana Brandsa, na primjer, u velikoj mjeri se zasniva na digitalnim potpisima—posebno na Schnorr šemi potpisa. Sistem, ako je pravilno implementiran, bezbjedan je onoliko koliko je bezbjedan osnovni sistem potpisa. Ako u njemu postoje nedostaci, nestaju i ključne prednosti anonimnog digitalnog novca—poput nemogućnosti praćenja, nepovezivosti i sigurnosti za sve učesnike.

Ako tražimo privatnost i sigurnost u bankarstvu, ne možemo ignorisati kriptografiju niti matematiku. Sposobnost sistema digitalnog novca da obezbijede određeni nivo sigurnosti i privatnosti više zavisi od teorije brojeva nego od bankarskih regulativa.

A. Neke osnovne definicije

Enkripcija je proces pretvaranja podataka ili poruke u nerazumljiv oblik, ali na način koji omogućava da se taj proces obrne i da se originalni podaci ili poruka mogu ponovo dobiti. Proces enkripcije uključuje određeni recept ili skup instrukcija koji daje korak-po-korak proceduru transformacije podataka. Taj recept se naziva algoritam. Algoritam enkripcije mora imati i obrnuti postupak koji vraća originalnu poruku. Taj obrnuti proces naziva se dekripcija. Zajedno, tehnike enkripcije i dekripcije nazivaju se kriptografija.

Algoritmi—kao što su DES ili RSA—uglavnom su javno poznati. Prednost toga je što istraživači mogu otkriti sve slabosti u algoritmu. Svaki pokušaj „sigurnosti kroz skrivanje“, odnosno čuvanjem algoritma u tajnosti, obično je kontraproduktivan, jer najčešće samo prikriva slabosti samog algoritma koje može iskoristiti svako ko ga otkrije. Međutim, kada se koristi kvalitetan javno poznat algoritam, sigurnost zavisi od dužine ključa, koji se može posmatrati kao niz nula i jedinica koji se koristi u algoritmu za transformaciju podataka.

Jedan primjer transformacije ključa povezan je sa XOR funkcijom koja se koristi u binarnoj aritmetici. XOR funkcija slijedi ova pravila sabiranja:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

Pošto se ova pravila razlikuju od uobičajene aritmetike (posebno pravilo da je 1+1 = 0), koristićemo znak „+“ za označavanje XOR sabiranja. Korištenjem XOR sabiranja, bilo koji niz nula i jedinica može se koristiti kao ključ za enkripciju i dekripciju podataka.

Pretpostavimo da imamo „poruku“ koja je niz od četiri binarne cifre, M = 1011. Takođe imamo i ključ od četiri cifre k = 1010. Sada možemo enkriptovati poruku M koristeći ključ k tako što ih saberemo: C = M „+“ k:

M:

1011

k:

1010

C:

0001

Enkriptovana poruka C je 0001. Svako ko vidi ovu vrijednost ne može znati originalnu poruku M, jer ona može biti bilo koja od šesnaest mogućih kombinacija od četiri bita.

Međutim, ako znamo ključ, lako je vratiti originalnu poruku. Potrebno je samo dodati ključ k na enkriptovanu poruku C, prateći XOR pravila sabiranja:

C:

0001

k:

1010

M:

1011

Uopšteno važi: M = (M „+“ k) „+“ k. Izvođenjem XOR operacije sa istim ključem dva puta dobija se originalna poruka.

Sigurnost zavisi od dužine ključa k. U ovom slučaju postoji šesnaest mogućih ključeva dužine četiri. Svaka binarna cifra može biti 0 ili 1, pa postoji 2 mogućnosti za svaku poziciju. Za ključ dužine N postoji ukupno 2^N mogućih kombinacija.

Komercijalni DES koristi ključeve dužine 56, što znači da postoji 2^56 mogućnosti. Iako je to veliki broj, više nije dovoljno siguran prema savremenim metodama kriptoanalize. Moguće je izvršiti i tzv. brute force napad, gdje se jednostavno isprobavaju svi mogući ključevi.

S druge strane, prostor ključeva od 2^128 smatra se veoma sigurnim, barem kada je riječ o brute force napadima. Takav prostor ključeva je 2^72 puta veći od standardnog DES prostora od 2^56.

XOR sabiranje koristi se u dva DES režima enkripcije. Electronic Code Book (ECB) režim enkriptuje svaki blok od 64 bita pojedinačno. Međutim, sigurniji režimi povezuju blokove međusobno.

Cipher Block Chaining (CBC) je režim u kojem se trenutni blok otvorenog teksta XOR-uje sa prethodnim šifrovanim blokom prije enkripcije DES ključem k. Ako je C(t) t-ti blok, a M(t) trenutni blok poruke, tada važi:

C(t) = Ek(M(t) „+“ C(t-1))  (CBC)

Cipher Feedback (CFB) je režim u kojem se svaki blok otvorenog teksta XOR-uje sa prethodnim šifrovanim blokom nakon njegove enkripcije:

C(t) = M(t) „+“ Ek(C(t-1))  (CFB)

(Veličine blokova u CFB režimu mogu biti manje od 64 bita.)

Ključ k iz prethodnog XOR primjera bio je simetričan—isti ključ se koristi i za enkripciju i za dekripciju. DES i IDEA su poznati simetrični algoritmi. Ovi algoritmi često predstavljaju praktična rješenja koja funkcionišu.

Nasuprot tome, sistemi javnog ključa (asimetrični sistemi) koriste dva različita ključa—jedan za enkripciju i drugi za dekripciju. RSA je poznat primjer takvog sistema. Ovi sistemi se zasnivaju na odnosima iz teorije brojeva.

Proces enkripcije funkcioniše tako što se poruka M podigne na određeni stepen a:

C = M^a

Dekripcija se vrši podizanjem šifrovane poruke C na drugi stepen b:

M = C^b

Ključ a je javan i poznat svima—zato se naziva javni ključ. Ključ b ostaje tajan i poznat samo korisniku—zato se naziva privatni ili tajni ključ.

B. Neke osnovne matematičke oznake

Poruka koja se enkriptuje ili šalje obično se označava kao M. Treba imati na umu da računar niz jedinica i nula koji čine M može posmatrati kao binarni broj, bez obzira da li je M „Volim te“, „Duguješ mi 500$“ ili „Broj banke 437695B“. Enkripcija može uključivati podizanje ovog broja na određeni stepen. Oznaka E(x) predstavlja algoritam ili funkciju enkripcije, dok D(x) predstavlja algoritam ili funkciju dekripcije. Enkriptovana poruka označava se kao E(M), dok se dekripcija te poruke označava kao D(E(M)). Naravno, to je zapravo originalna poruka, pa važi D(E(M)) = M.

Ako se poruka enkriptuje ili dekriptuje pomoću simetričnog ključa k, koristi se oznaka Ek(x) ili Dk(x). Ako je riječ o sistemu javnog ključa, tada se javni ključ označava kao pk, dok se privatni (tajni) ključ označava kao sk.

U simetričnom sistemu enkripcije važi Dk(Ek(M)) = M, jer se isti ključ koristi i za enkripciju i za dekripciju. U sistemu javnog ključa koristi se jedan ključ za enkripciju, a drugi za dekripciju. Zato važi Dsk(Epk(M)) = M, kao i Dpk(Esk(M)) = M. U prvom slučaju, poruka se enkriptuje Alicinim javnim ključem, a zatim je ona dekriptuje svojim privatnim ključem. U drugom slučaju, koji je čest kod digitalnih potpisa, Alica enkriptuje poruku svojim privatnim ključem, a zatim je neko drugi dekriptuje njenim javnim ključem.

Znak „^“ koristi se za označavanje stepena; na primjer, 2^3 = 8, jer je 2 na treći stepen jednako 8. (Napomena: u programskom jeziku Fortran, b^y bi se pisalo kao b**y.) Jedna zvjezdica „“ označava množenje: „tri puta b jednako je 12“ zapisuje se kao „3b = 12“, ili jednostavno „3b = 12“. Oznaka log_b(y) predstavlja logaritam broja y sa osnovom b. Na primjer, log₂(8) = 3, jer je logaritam broja 8 po osnovi 2 jednak 3.

Na kraju, oznaka mod p znači „aritmetika po modulu p“. Time se podrazumijeva: podijeli sa p i zadrži ostatak r, gdje važi 0 ≤ r < p.

Na primjer, mod 3 znači da svaki pozitivan cijeli broj dijelimo sa 3 i uzimamo ostatak (koji može biti 0, 1 ili 2). Tako je 7 mod 3 = 1, jer 3 ulazi u 7 dva puta, sa ostatkom 1. Broj kojim dijelimo (u ovom slučaju 3) naziva se modul. Slično, 62 mod 25 = 12, jer 62 = 252 + 12. Ali ako je modul 3, tada 62 = 320 + 2, pa je rezultat 2.

Uopšteno, pišemo a = b mod n, što znači da a mod n = b mod n.

Na primjer, 67 = 11 mod 7, jer je 67 mod 7 = 4, a takođe i 11 mod 7 = 4. Dakle:

a = b mod n

znači da za neke cijele brojeve k1 i k2 važi:

a = k1n + r (0 ≤ r < n)

b = k2n + r

Iz toga slijedi:

a – b = (k1 – k2)*n

što znači da n dijeli razliku a – b cijeli broj puta (tačno k1 – k2 puta). Drugim riječima, kaže se „n dijeli (k1 – k2)“, što se može zapisati i kao n|(k1 – k2).

U prethodnom primjeru:

67 = 11 mod 7

to znači da za k1 = 9 i k2 = 1 važi:

67 = 97 + 4 (0 ≤ 4 < 7)

11 = 17 + 4

Iz toga slijedi:

67 – 11 = (k1 – k2)*7 = (9 – 1)7 = 87

što znači da 7 dijeli broj 67 – 11 tačno 8 puta. To možemo zapisati i kao 7|(67 – 11) ili 7|56.

Ako ovako računamo—koristeći cijele brojeve, dijeleći sa modulom i zadržavajući samo ostatak—onda koristimo modularnu aritmetiku. Većina računara nije idealno konstruisana za modularnu aritmetiku, jer nisu prilagođeni radu sa vrlo velikim cijelim brojevima. Umjesto toga, često koriste decimalne tačke i ograničen broj cifara (tzv. floating point aritmetika).

Na primjer, broj poput 3.7B3579D4F6821 × 16^73 je izuzetno velik, ali računar u suštini prati samo ograničen broj heksadecimalnih cifara (64 bita). Međutim, kriptografija javnog ključa može koristiti ključeve dužine 2048 bita ili više. Zato se u praksi koriste specijalni softverski algoritmi ili posebno dizajnirani kriptografski čipovi koji zaobilaze ograničenja hardvera.

Takođe treba imati na umu da se stepenovanje računa prije množenja. Zato je 35^2 = 325 = 75, dok je (35)^2 = 15^2 = 225. Takođe važi da je (35)^2 = 3^25^2 = 925 = 225. Uopšteno:

(x*y)^z = x^z * y^z.

C. Modularna aritmetika i grupe Z(p) i G(q)*

U većini proračuna koji uključuju kriptografiju javnog ključa i digitalni novac, radićemo sa skupom cijelih brojeva od 0 do p-1, gdje je p neki veliki prost broj. To proizlazi iz činjenice da ćemo vršiti množenje mod p. Takođe ćemo koristiti skup cjelobrojnih stepena od 1 do q, gdje je q neki veliki prost broj koji dijeli p-1. Drugim riječima, množenje i stepenovanje odvijaće se unutar grupa Z(p)* i G(q), koje ćemo definisati i objasniti u ovom odjeljku.

Dvije grupe, Z(p)* i G(q), veoma su važne za kriptografiju javnog ključa i digitalni novac. One imaju ulogu u Diffie-Hellman razmjeni ključeva, u Schnorr šemi potpisa, u Digital Signature Algorithm, kao i u sistemu digitalnog novca Stefana Brandsa. Drugim riječima, aritmetika se obavlja u Z(p)* ili u grupi G(q) stepena prostog reda q, gdje q dijeli p-1. Zato je važno razumjeti šta su ove grupe.

Skup Z(p)* = {1, 2, 3, 4, …, p-2, p-1}. Ako pomnožimo bilo koja dva broja iz ovog skupa i zatim proizvod svedemo mod p, rezultat je opet broj iz istog skupa. Dakle, skup je zatvoren za množenje. Pored toga, ako uzmemo bilo koji broj k iz skupa, postoji drugi broj k^-1 takav da je kk^-1 = 1 mod p. To znači da svaki broj u skupu ima multiplikativni inverz. Ove dvije osobine znače da je Z(p) grupa za množenje mod p. Ponekad se koristi izraz „multiplikativna grupa“. Pošto je Z(p)* grupa za množenje, ona je takođe grupa za stepenovanje, jer je n-ti stepen nekog broja samo množenje tog broja samim sobom n puta. (Napomena: 0 je izostavljen iz Z(p)* zato što nema multiplikativni inverz. Ako skupu Z(p)* dodamo 0, dobijamo skup Z(p), koji sadrži sve ostatke mod p, uključujući i 0.)

Na primjer, Z(11)* = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Ako pomnožimo 5 i 8 iz tog skupa, dobijamo 58 = 40 = 7 mod 11, a 7 je element skupa. Takođe, imamo 59 = 45 = 1 mod 11, pa je 9 multiplikativni inverz od 5. Slično, 5 je multiplikativni inverz od 9. Ako je k = 5, onda je k^-1 = 9. Isto tako, 2 i 6 su multiplikativni inverzi, kao i 3 i 4. Koji je multiplikativni inverz od 10? (Odgovor: 10 je sam sebi multiplikativni inverz, jer je 1010 = 100 = 1 mod 11.) Takođe, ako stepenujemo neki broj iz skupa, recimo 6 na treći stepen, dobijamo 6^3 = 666 = 216 = 7 mod 11, i opet ostajemo unutar skupa. Skup je zatvoren za množenje i stepenovanje mod 11, a svaki element ima inverz, pa je Z(11) grupa.

Svaki element ima multiplikativni inverz u Z(p)* zato što je p prost broj. Pošto je p prost, jedini zajednički djelilac broja p i svakog broja iz skupa Z(p)* = {1, 2, 3, …, p-1} jeste 1. Drugim riječima, najveći zajednički djelilac (gcd) broja p i bilo kog broja iz skupa jednak je 1. Dakle, gcd(1,p) = 1, gcd(2,p) = 1, gcd(3,p) = 1, … , gcd(p-1,p) = 1.

To ne važi ako modularno množenje vršimo sa složenim brojem (tj. brojem koji je proizvod najmanje dva broja, od kojih je svaki veći od 1). Na primjer, broj 15 = 3*5, pa je složen. Pretpostavimo da vršimo množenje mod 15, koristeći brojeve iz skupa {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}. Koji je inverz broja 6 u ovom skupu? Odgovor: 6 nema inverz, što možemo vidjeti tako što 6 pomnožimo sa svim brojevima manjim od 15:

60 = 65 = 610 = 0 mod 15

61 = 66 = 611 = 6 mod 15

62 = 67 = 612 = 12 mod 15

63 = 68 = 613 = 3 mod 15

64 = 69 = 6*14 = 9 mod 15

Ne postoji broj koji, kada se pomnoži sa 6, daje 1 mod 15. Osim toga, dobijamo 0 kao rezultat nekih množenja, pa skup nije zatvoren. (6 i 5 su u skupu, ali je 6*5 mod 15 = 0, a 0 nije u skupu.) Zato ovaj skup, tj. skup cijelih brojeva od 1 do 14, nije multiplikativna grupa mod 15.

Vratimo se sada skupu Z(p). Možemo definisati i neke druge operacije, pored množenja i stepenovanja. Možemo definisati dijeljenje sa k kao množenje sa inverzom od k, tj. k^-1. Tako je po definiciji 8/k = 8k^-1. Ako je k = 9 u Z(11), onda je 8/9 = 89^-1 = 85 = 40 = 7 mod 11. Slično, 3/10 = 310^-1 = 3*10 = 30 = 8 mod 11.

Neka je g član skupa Z(p). Tada se za g kaže da je generator mod p ako skup stepena broja g, tj. skup {g^1 mod p, g^2 mod p, …, g^(p-1) mod p}, sadrži, nekim redoslijedom, sve članove skupa Z(p):

{g, g^2, g^3, … , g^(p-2), g^(p-1)} mod p

= {1, 2, 3, … , p-2, p-1}, nekim redoslijedom.

To znači da skup Z(p)* = {1, 2, …, p-1} predstavlja preuređenje skupa {g, g^2, g^3, … , g^(p-1)}, kada se svi proračuni rade mod p. (Radi praktičnosti pišemo mod p izvan vitičastih zagrada kada se odnosi na svaki element skupa, ili ga izostavljamo ako je to jasno.)

Na primjer, 3 je generator skupa Z(7)*, jer je:

3^1 = 3 mod 7

3^2 = 2 mod 7

3^3 = 6 mod 7

3^4 = 4 mod 7

3^5 = 5 mod 7

3^6 = 1 mod 7

Ili, drugačije rečeno:

{3, 3^2, 3^3, 3^4, 3^5, 3^6} = {1, 2, 3, 4, 5, 6}

kada se proračuni rade mod 7. Dva skupa imaju iste elemente, iako ne nužno istim redoslijedom. Preuređenje redoslijeda elemenata nekog skupa naziva se permutacija. Stepeni generatora 3 daju permutaciju skupa Z(7)*.

Generator-torka mod p je skup od k generatora, koji su svi međusobno različiti. Drugim riječima, {g1, … , gk} je generator-torka ako je svaki gi generator mod p, a pri tome gi nije jednako gj kada i nije jednako j.

Na primjer, {3, 5} je generator-torka za Z(7), jer su i 3 i 5 generatori skupa Z(7). Svaki element u Z(7)* može se predstaviti i kao stepen broja 3 i kao stepen broja 5:

1 = 3^6 mod 7 = 5^6 mod 7

2 = 3^2 mod 7 = 5^4 mod 7

3 = 3^1 mod 7 = 5^5 mod 7

4 = 3^4 mod 7 = 5^2 mod 7

5 = 3^5 mod 7 = 5^1 mod 7

6 = 3^3 mod 7 = 5^3 mod 7

Broj 2 nije generator mod 7, jer stepeni broja 2 daju samo 1, 2 ili 4 mod 7:

{2, 2^2, 2^3} = {1, 2, 4}.

Međutim, treba primijetiti da stepeni broja 2 mod 7 daju podskup skupa Z(7). Skup {1, 2, 4} je podskup skupa {1, 2, 3, 4, 5, 6} = Z(7). Zato se kaže da broj 2 „generiše podgrupu G(3)“ mod 7. Oznaka „G(3)“ znači da grupa ima 3 elementa. Drugim riječima, 3 je najmanji stepen broja 2 koji daje 1 mod 7. G(3) je grupa, jer je zatvorena za množenje mod 7:

11 = 1 mod 7  21 = 2 mod 7  41 = 4 mod 7

12 = 2 mod 7  22 = 4 mod 7  42 = 1 mod 7

14 = 4 mod 7  24 = 1 mod 7  4*4 = 2 mod 7

i zato što svaki element u G(3) takođe ima inverz.

Primijetimo da je i broj 4 generator grupe G(3) = {1, 2, 4} mod 7, jer je:

{4, 4^2, 4^3} = {4, 2, 1} mod 7 = {1, 2, 4}.

Za grupu koju generiše element g kaže se da ima red q mod p ako je q najmanji stepen takav da je g^q = 1 mod p.

Dva generatora skupa Z(7)* koja smo ranije vidjeli, naime 3 i 5, imaju red 6 mod 7, jer je 6 najmanji stepen broja 3 ili 5 koji daje 1 mod 7. Dakle, 1 = 3^6 = 5^6 mod 7, a nijedan manji stepen nema tu osobinu. Nasuprot tome, generatori grupe G(3), naime 2 i 4, imaju red 3, jer je 2^3 = 4^3 = 1 mod 7, a nijedan manji stepen broja 2 ili 4 nije jednak 1.

Uopšteno, za prost broj q, gdje je 1 < q < p, definišemo G(q) kao grupu (ili podgrupu) prostog reda q mod p ako za neki generator g, gdje je 1 < g < p, važi da je {g, g^2, g^3, …, g^q} podskup skupa Z(p)*. To znači da stepeni broja g daju sve elemente te podgrupe. Primijetimo da je po definiciji q najmanji stepen broja g koji daje 1; dakle, g^q = 1 mod p. Zbog toga svi stepeni veći od q samo ponovo prolaze kroz isti skup brojeva. Ako je g^q = 1 mod p, tada je g^(q+1) = g mod p, g^(q+2) = g^2 mod p, i tako dalje.

Na primjer, 2^3 = 1 mod 7. Zato veći stepeni broja 2 stalno daju iste brojeve iznova:

2^4 = 2^1 = 2 mod 7

2^5 = 2^2 = 4 mod 7

2^6 = 2^3 = 1 mod 7

itd.

Primijetimo da ako je g element grupe Z(p), tada je g generator skupa Z(p) ako je g element reda p-1. To znači: ako je g^(p-1) = 1 i nijedan manji stepen nije jednak 1. Tada nužno slijedi da stepeni broja g mod p—naime g^1, g^2, …, g^(p-1)—prolaze kroz sve brojeve 1, 2, …, p-1.

Fermatova teorema kaže da za svaki prost broj p i broj k koji nije djeljiv sa p važi:

k^(p-1) = 1 mod p

Naravno, cijeli brojevi 1, 2, 3, …, p-1 nisu djeljivi sa p, pa bilo koji od tih brojeva podignut na stepen p-1 daje 1 mod p, prema Fermatovoj teoremi.

Dakle, za k koji je element skupa Z(p)* važi k^(p-1) = 1 mod p.

Na primjer, za Z(11)* imamo p-1 = 10, i provjera pokazuje da je mod 11:

1^10 = 2^10 = 3^10 = 4^10 = 5^10 = 6^10 = 7^10 = 8^10 = 9^10 = 10^10 = 1.

Treba primijetiti da ne tvrdimo da svaki broj k < p ima red p-1 mod p. Red broja k može biti i manji. Na primjer, 2 ima red 3 mod 7, jer je 2^3 = 1 mod 7. Ali je takođe tačno da je 2^(7-1) = 2^6 = 1 mod 7, kako to zahtijeva Fermatova teorema. Očigledno, 2^6 = (2^3)^2 = (1)^2 = 1 mod 7.

Lako je vidjeti da, kao posljedica Fermatove teoreme, red q bilo kog elementa multiplikativne grupe mod p mora dijeliti p-1. To je poznato kao Lagrangeova teorema.

Na primjer, u slučaju p = 7 imamo p-1 = 7-1 = 6, pa red bilo kog elementa mora biti broj koji dijeli 6 bez ostatka. Ranije smo vidjeli da 3 i 5 imaju red 6 u Z(7)*, i da 6 | (7-1). Slično tome, vidjeli smo da 2 i 4 imaju red 3 mod 7, i da 3 | (7-1).

Razlog zašto to funkcioniše jeste sljedeći: ako je element g reda q mod p, tada je g^q = 1 mod p. Ali po Fermatovoj teoremi takođe važi da je g^(p-1) = 1 mod p. Kada q ne bi dijelio p-1 bez ostatka, onda bi za neki broj k važilo p-1 = kq + r, gdje je 0 < r < q. Tada bismo imali: 1 = g^(p-1) = g^(kq+r) = (g^q)^k * g^r = 1 * g^r, što znači da je g^r = 1. To dalje znači da g ima red r manji od q, što je kontradikcija.

Eulerova funkcija fi, t(n), za pozitivan cio broj n označava broj brojeva manjih od n koji su uzajamno prosti sa n. Drugim riječima, broj pozitivnih cijelih brojeva k, gdje je 0 < k < n, za koje važi gcd(k,n) = 1.

Ako je n = p prost broj, tada su svi pozitivni brojevi manji od p uzajamno prosti sa p, pa je t(p) = p-1.

Na primjer, za n = p = 7, brojevi 1, 2, 3, 4, 5 i 6 svi su uzajamno prosti sa 7, pa je t(7) = 6. Za n = 4, brojevi 1 i 3 su uzajamno prosti sa 4, pa je t(4) = 2. Za n = 15, brojevi 1, 2, 4, 7, 8, 11, 13, 14 su uzajamno prosti sa 15, pa je t(15) = 8. (Ostali brojevi, naime 3, 5, 6, 9, 10, 12, imaju zajedničke djelioce sa 15.)

Eulerova teorema kaže da za bilo koji broj n i bilo koji broj k koji je uzajamno prost sa n važi:

k^t(n) = 1 mod n

Treba primijetiti da Eulerova teorema važi i za složene brojeve n, a ne samo za proste. Na primjer, neka je n = 15. Broj 2 je uzajamno prost sa 15, pa prema Eulerovoj teoremi imamo:

2^t(15) = 2^8 = 1 mod 15.

Eulerovu teoremu koristićemo kasnije kada budemo posmatrali RSA kriptosistem. RSA koristi velike brojeve n koji su složeni, tačnije proizvod dva prosta broja, pa Fermatova teorema tu ne važi: uopšteno nije tačno da je k^(n-1) = 1 mod n za složen broj n, čak ni kada je k uzajamno prost sa n. Na primjer, 2^(15-1) = 2^14 = 4 mod 15. To znači da red broja k ne mora nužno dijeliti n-1 kada je n složen. Broj 2 jeste uzajamno prost sa 15, ali ima red 4, jer je 2^4 = 1 mod 15. A 4 ne dijeli 15-1 = 14. Međutim, red 4 dijeli t(15) = 8.

Još jedan rezultat iz teorije brojeva, čiji dokaz ovdje nećemo razmatrati, kaže da je za prost broj p broj generatora mod p jednak t(p-1).

Na primjer, broj generatora mod 7 jednak je t(7-1) = t(6). Po definiciji, t(6) je broj pozitivnih cijelih brojeva manjih od 6 koji su uzajamno prosti sa 6. Takva su dva broja: 1 i 5. Dakle, postoje ukupno dva generatora mod 7. Oba ta generatora, naime 3 i 5, već smo ranije pokazali. (Značaj brojeva 1 i 5 ovdje je u tome što, ako imamo generator g, tada su i g^1 i g^5 takođe generatori. Tako su 3 i 3^5 = 5 mod 7 generatori. Ili obrnuto, pošto je 5 generator, tada su i 5 i 5^5 = 3 mod 7 generatori.)

Posmatrajmo sada grupu G(q) prostog reda q mod p, dakle i p i q su prosti brojevi. Pošto red bilo kog elementa mod p mora dijeliti p-1, slijedi da q mora dijeliti p-1. Koliko generatora ima podgrupa G(q)? Odgovor je da za svaki m koji dijeli p-1 postoji t(m) generatora reda m, gdje je t Eulerova fi funkcija. U slučaju kada je m = q prost broj, tada postoji t(q) = q-1 generatora. Dakle, postoji q-1 generatora podgrupe G(q) prostog reda q mod p. Ova činjenica nam garantuje da za velike q imamo mnogo generatora na raspolaganju.

Na primjer, pošto 3 dijeli 7-1 = 6, postoje t(3) = 2 generatora reda 3 mod 7. To znači da postoje dva generatora podgrupe G(3) = {1, 2, 4}. (Primijetimo da su i 2 i 4 generatori G(3).) Slično tome, pošto 2 dijeli 7-1 = 6, postoji t(2) = 1 generator reda 2 mod 7. (Provjerite da je 6 generator reda 2 mod 7, koji daje podgrupu G(2) = {1, 6}.)

Primijetimo da pošto 2, 3 i 6 svi dijele p-1 = 7-1, moguće podgrupe mod 7 su sljedeće:

Podgrupe skupa Z(7)*

Generatori gi mod 7

G(2) = {1, 6}

6

G(3) = {1, 2, 4}

2, 4

G(6) = {1, 2, 3, 4, 5, 6}

3, 5

Vidimo da G(6) = Z(7)* ima samo dva generatora, a ne 6-1 = 5, zato što 6 nije prost faktor broja p-1. Umjesto toga, važi t(6) = 2.

Za p = 23 i q = 11, postoji t(11) = 10 generatora grupe G(11) = {2, 4, 8, 16, 9, 18, 13, 3, 6, 12, 1}. Broj 2 je jedan takav generator mod 23. Bilo koji član grupe G(11), osim broja 1, jeste generator te grupe.

Primijetimo u ovom posljednjem primjeru da 2 i 22 takođe dijele p-1 = 23-1. Zato postoji t(2) = 1 generator grupe G(2), i t(22) = 10 generatora grupe G(22) = Z(23). Dakle, od 22 elementa u Z(23), njih 10 ima red 22, 10 ima red 11, a 1 ima red 2. (Provjerite da je G(2) = {1, 22}.)

Podgrupe skupa Z(23)*

Generatori gi mod 23

G(2) = {1, 22}

22

G(11) = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}

2, 3, 4, 6, 8, 9, 12, 13, 16, 18

G(22) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22}

5, 7, 10, 11, 14, 15, 17, 19, 20, 21

Diskretne logaritme možemo definisati i u Z(p)* i u G(q) na sljedeći način. Neka je g generator jedne od ove dvije grupe, a neka je y x-ti stepen broja g modulo p:

y = g^x mod p, ili y = gx mod p

Tada je x (diskretni) logaritam broja y sa osnovom g, modulo p:

x = log_g(y) mod p, ili x = logg(y) mod p

Na primjer, 2^5 = 9 mod 23, pa je 5 = log₂(9) mod 23. Cijeli broj 5 je logaritam broja 9 sa osnovom 2 mod 23. Slično tome, 3^6 = 1 mod 7, pa je 6 = log_3(1) mod 7. Cijeli broj 6 je logaritam broja 1 sa osnovom 3 mod 7.

Primijetimo za generator g grupe G(q) mod p da, pošto je g^q = 1, uvijek važi q = log(1) mod p, za bilo koju osnovu g koja je generator. Zato u grupi reda q broj q igra ulogu nule, jer je g^q = g^0 = 1 mod p, pa otuda q = log(1) = 0 mod q.

Dakle, za bilo koji stepen x broja g u G(q), izraz g^x mod p može se svesti mod q:

g^x mod p = g^(x mod q) mod p.

Na primjer, vidjeli smo da 2 ima red q = 3 mod 7, jer je 2^3 mod 7 = 1. Zato za stepen veći od 3, recimo 8, imamo: 2^8 mod 7 = 2^(8 mod 3) mod 7 = 2^2 mod 7 = 4. Kada dođemo do q-tog stepena broja g, tj. kada je g^q = 1, tada za x = kq + r imamo g^(kq+r) = g^(k*q)*g^r = (g^q)^k * g^r = 1^k * g^r = g^r. Dakle, možemo svesti x tako što ga podijelimo sa q i zadržimo samo ostatak r.

Za kasniju upotrebu, obratimo pažnju na sljedeću činjenicu o stepenima broja g. Ako imamo dva broja X = g^x mod p i Y = g^y mod p, tada važi:

X*Y = g^x * g^y = g^(x+y) mod p.

Nasuprot tome, imamo:

X^y = (g^x)^y = g^(x*y) mod p,

dok je:

Y^x = (g^y)^x = g^(x*y) mod p.

Poznavanje prvog rezultata, g^(x+y) mod p, ne govori nam ništa o drugom rezultatu, g^(xy) mod p. Tek kada bismo prvo uzeli logaritme po osnovi g i izračunali x = log X mod p ili y = log Y mod p, mogli bismo izračunati g^(xy).

Za jednostavan primjer sa malim brojevima, pretpostavimo da je g = 2 i p = 25307. Pretpostavimo takođe da posmatrate X = 6113 i Y = 7984. Dakle znate da je:

XY = 61137984 = 2^(x+y) mod 25307.

To jest:

14296 = 2^(x+y) mod 25307.

Ali koliki je g^(xy) = 2^(xy) mod 25307?

Da biste odgovorili na ovo pitanje, morate znati x = log₂ 6113 mod 25307 ili y = log₂ 7984 mod 25307. Razlika između g^(x+y) i g^(x*y) dovodi nas do Diffie-Hellman sporazuma o ključu.

D. Diffie-Hellman i diskretni logaritmi

Diffie-Hellman sporazum o ključu je tehnika pregovaranja o ključu koju su stvorili Whitfield Diffie i Martin Hellman 1976. godine. Ona obezbjeđuje siguran način da dvije strane dogovore zajednički simetrični ključ pomoću kojeg će šifrovati svoju trenutnu razmjenu poruka. Praktična osnova Diffie-Hellman razmjene ključeva jeste činjenica da je lako računati stepene u modularnoj aritmetici, ali je teško iz njih izvući logaritme. Drugim riječima, potrebno je mnogo računarskog vremena i novca da bi se izračunali diskretni logaritmi, u poređenju sa računanjem stepena.

Vjeruje se da su diskretni logaritmi primjeri jednosmjernih funkcija. Jednosmjerna funkcija je ona koja se može relativno efikasno izračunati u jednom smjeru, u poređenju sa obrnutim smjerom. To znači da je funkcija f(x) jednosmjerna ako je lako izračunati y = f(x), kada je dat x, ali je teško izračunati ili pronaći x kada je dato y.

Za generator g skupa Z(p)* lako je izračunati y = g^x mod p na osnovu x, ali je teško izračunati x na osnovu y — barem dok je prost broj p dovoljno velik. „Dovoljno velik“ je 1997. godine značilo najmanje 768 bita, a poželjno 1024 bita, što omogućava proste brojeve manje od 2^1024. Postoji oko 10^305 prostih brojeva manjih od 2^1024, tako da ih ima sasvim dovoljno za izbor. (Broj prostih brojeva manjih ili jednakih n asimptotski je jednak n/ln(n). Dakle, dobra aproksimacija broja prostih brojeva manjih od n jeste jednostavno n/ln(n), pod uslovom da je n velik. Ovdje i na drugim mjestima „ln“ označava prirodni logaritam, tj. logaritam sa osnovom e = 2.718281828….)

Pretpostavimo sada da dvije osobe žele razmijeniti informacije, ali žele da to urade privatno. Prvo što moraju uraditi jeste da se dogovore o kriptografskom ključu kojim će šifrovati svoje poruke. Diffie-Hellman sporazum o ključu je način da dvije strane odrede kriptografski ključ za svoju trenutnu sesiju razmjene poruka, bez straha da će neka treća strana uspjeti da presretne taj ključ i time dešifruje njihov saobraćaj. Ova metoda se zasniva na činjenici da dvije strane koje razmjenjuju poruke moraju računati samo stepene u modularnoj aritmetici da bi znale koji je ključ o kojem su se dogovorile, dok bi prisluškivač morao da računa diskretne logaritme kako bi iz iste početne razmjene poruka došao do tog ključa. (Druga vrsta napada, nazvana „čovjek u sredini“, ovdje neće biti razmatrana.)

Primjer jednog Diffie-Hellman proračuna dat je u Tabeli 1. Možda bi bilo korisno prvo pročitati korake u tabeli, prije nego što pređete na naredno objašnjenje ove tehnike.

Pretpostavimo da smo Alica i ja odlučili da koristimo Diffie-Hellman sporazum o ključu kako bismo uspostavili sesijski ključ. Taj ključ koristiće se za šifrovanje poruka koje međusobno šaljemo, i to samo ovom prilikom. Oboje smo se unaprijed dogovorili oko generatora g skupa Z(p)* i prostog broja p. Kao što je objašnjeno u prethodnom odjeljku, generator g, gdje je 1 < g < p, ima osobinu da g, g^2, g^3, … , g^(p-1) daju — nekim redoslijedom — sve brojeve 1, 2, 3, …, p-1, kada se računanje vrši mod p.

Tabela 1: Koraci u pregovaranju o Diffie-Hellman sporazumu o ključu

Diffie-Hellman	Primjer
A i B se dogovaraju o dva broja, generatoru g skupa Z(p)* i prostom broju p.	Alica i ja se dogovaramo da je g = 7, a p = 23.
A bira tajni slučajni cijeli broj x.	Alica bira x = 5.
B bira tajni slučajni cijeli broj y.	Ja biram y = 8.
A računa X = g^x mod p.	Alica računa X = 7^5 mod 23 = 17.
B računa Y = g^y mod p.	Ja računam Y = 7^8 mod 23 = 12.
A šalje X B-u, a B šalje Y A-u.	Alica meni šalje 17; ja Alici šaljem 12.
A računa K = Y^x mod p.	Alica računa K = 12^5 mod 23 = 18.
B računa K = X^y mod p.	Ja računam K = 17^8 mod 23 = 18.
K je ključ za šifrovanje ove komunikacione sesije.	K = 18 je ključ za šifrovanje ove komunikacione sesije.

Na primjer, Alica može jednostavno sama izabrati g i p i poslati ih meni. Nije važno ako i drugi znaju koje su to vrijednosti. Alica sada odlučuje da mi pošalje poruku. Potreban joj je ključ za šifrovanje te poruke. Da bi započela proces, Alica prvo bira slučajan broj x, gdje je 1 < x < p-1. Alica drži x u tajnosti i meni šalje samo X:

X = g^x mod p.

Ja zatim biram slučajan broj y, gdje je 1 < y < p-1, i šaljem Alici Y:

Y = g^y mod p.

Sada Alica računa:

K = Y^x mod p = g^(y*x) mod p

tako što broj koji je dobila od mene podiže na stepen x i rezultat svodi mod p. U isto vrijeme, ja računam:

K = X^y mod p = g^(x*y) mod p

tako što broj koji sam dobio od nje podižem na stepen y i rezultat svodim mod p. Pošto su brojevi koje oboje izračunamo jednaki, oboje posjedujemo isti sesijski ključ:

K = sesijski ključ = g^(xy) mod p = g^(yx) mod p.

Za dovoljno velike vrijednosti g i p, ne postoji poznat računski izvodiv način da bilo ko ko ne zna ni x ni y izračuna g^(x*y) mod p, osim ako se prvo ne uhvati u koštac sa teškim problemom računanja logaritma broja g^x mod p ili logaritma broja g^y mod p.

Ako je p prost broj dužine oko 1000 bita, odnosno oko 300 decimalnih cifara, za izračunavanje stepena broja g potrebno je svega oko 2000 množenja 1000-bitnih brojeva. Nasuprot tome, najbrže poznate tehnike za računanje logaritama u aritmetici mod p trenutno zahtijevaju više od 2^100, odnosno približno 10^30 operacija. Čak bi i najboljem superračunaru bile potrebne mnoge milionе godina da izračuna logaritam broja g^x mod p.

Dužina samog Diffie-Hellman ključa K obično je oko 128 bajtova, odnosno 1024 bita. Taj ključ se zatim često dodatno obrađuje pomoću hash funkcije, koja će kasnije biti objašnjena, kako bi se sveo na 8 bajtova, odnosno 64 bita, i tako dobio DES ključ za šifrovanje.

E. RSA sistem javnog ključa

RSA Data Security, sa sjedištem u Redwood Cityju, Kalifornija, kompanija je koju su 1982. godine osnovali pronalazači RSA sistema, Ron Rivest, Adi Shamir i Leonard Adleman. RSA tehnologija enkripcije nalazi se u Microsoft Windowsu, Netscape Navigatoru, Intuitovom Quicken-u i Lotus Notes-u. Takođe se nalazi u Apple, Sun i Novell operativnim sistemima, kao i na Ethernet mrežnim karticama. RSA je dio SWIFT standarda za međunarodne finansijske transfere, kao i ANSI X9.31 nacrta standarda za bankarsku industriju u SAD-u.

U RSA kriptosistemu javnog ključa koji se koristi za elektronski novac, i enkripcija i dekripcija vrše se podizanjem poruke M na stepen koji predstavlja odgovarajući ključ. Podsjetimo, svaka računarska poruka može se posmatrati jednostavno kao binarni broj. Kao što je ranije navedeno, ova stepenovanja se izvode u modularnoj aritmetici, u kojoj se zadržava samo ostatak pri dijeljenju sa fiksnim brojem koji se naziva modul. Taj modul mora biti veoma velik, obično najmanje 230 decimalnih cifara, odnosno 768 binarnih cifara. Primjer u Tabeli 2 koristi male brojeve radi ilustracije.

Kada se sistem postavlja, entitet koji pravi ključeve, bilo da je to banka, korisnik ili trgovac, generiše dva velika prosta broja p i q. Njihov proizvod n = pq biće modul pri stepenovanju. Eulerova funkcija za broj n iznosi t(n) = t(pq) = (p-1)*(q-1). Osnova RSA sistema je Eulerova teorema, obrađena ranije, koja kaže da za bilo koji broj x koji je uzajamno prost sa n važi:

x^t(n) = x^[(p-1)*(q-1)] = 1 mod n.

Ili, ako postavimo t = (p-1)*(q-1), tada važi:

x^t = 1 mod n,

pod uslovom da x nije djeljiv ni sa p ni sa q. Podsjetimo da veličina t odgovara broju pozitivnih cijelih brojeva manjih od n = p*q koji su uzajamno prosti sa n.

Zatim tvorac ključa bira e i d tako da važi:

ed = 1 mod t, [to jest, ed = k*t + 1, za neki pozitivan cio broj k],

pri čemu će (e, n) biti njegov javni ključ, a (d, n) njegov privatni ključ.

Prema tome, svaki dozvoljeni x enkriptovan sa e može biti dekriptovan sa d, jer, računato mod n, važi:

(x^e)^d = x^(ed) = x^(kt + 1) = xx^(kt) = x*(x^t)^k = x*(1^k) = x.

Tvorac ključa distribuira javni ključ e svim korisnicima, zajedno sa modulom n = p*q, ali nikada ne otkriva p, q niti privatni ključ d.

Uopšteno, dakle, u RSA sistemu, za otvorenu poruku M i njoj pridruženu šifrovanu poruku C važi:

M^(e*d) = (M^e)^d = (M^d)^e = M mod n

Enkripcija: Ee(M) = C = M^e mod n

Dekripcija: Dd(C) = C^d mod n = (M^e)^d mod n = M mod n.

Primijetimo kako, u principu, funkcionišu RSA potpisi. Radi jednostavnosti, odgodićemo raspravu o hash funkcijama za kasnije. Banka čiji je tajni ključ d potpisaće poruku M tako što će je „enkriptovati“ tajnim ključem d, što jednostavno znači da će M podići na stepen d:

Potpis: Ed(M) = M^d mod n.

Ovu poruku svako može provjeriti i dekriptovati tako što će je podići na stepen e, koji je javni ključ banke:

De(Ed(M)) = (M^d)^e mod n = M mod n.

Tabela 2: RSA sistem javnog ključa

RSA sistem javnog ključa	Primjer
Izabrati p i q, gdje su i p i q prosti brojevi.	Izabrati 11 i 13, koji su prosti brojevi.
Naći njihov proizvod n = pq.	Izračunati n = 11*13 = 143.
Izračunati Eulerovu funkciju t = (p-1)(q-1).	Izračunati t = (11-1)*(13-1) = 120.
Izabrati cijeli broj e, gdje je e < t, i najveći zajednički djelilac brojeva e i t jednak 1.	Neka je e = 7. To će funkcionisati jer je 7 < 120, a njihov najveći zajednički djelilac je 1.
Izračunati d tako da važi e*d = 1 mod t.	Želimo da 7d = 1 mod 120. Dakle, d = 103, jer je 7103 = 721 = 1 mod 120.
Javni ključ je (e, n).	Javni ključ je (7, 143).
Privatni ključ je (d, n).	Privatni ključ je (103, 143).
Otvoreni tekst može biti bilo koji broj M, gdje je M < n, i ni p ni q ne dijele M.	Neka numerički prikaz poruke bude, na primjer, M = 5.
Šifrovani tekst je C = M^e mod n.	Šifrovani tekst je C = 5^7 mod 143 = 47.
Otvoreni tekst je C^d mod n = (M^e)^d mod n = M.	Otvoreni tekst je 47^103 mod 143 = 5.

Da bismo vidjeli ovaj posljednji korak, obratimo pažnju na sljedeće, mod 143:

47^103 = (5^7)^103 = 5^721

= 5*[5^720] = 5*[(5^120)^6]

= 5*[1^6] = 5.

Ovdje smo iskoristili rezultat da je:

5^120 = 5^t = 1 mod 143

prema Eulerovoj teoremi.

Ili, jednostavnije, važi x^(e*d) = x; dakle, 5^721 = 5.

RSA sistem je patentiran (US Patent 4,405,829). Patent ističe 29. septembra 2000. godine.

Sigurnost RSA sistema zavisi od težine faktorizacije velikih brojeva. Jer, ako je dat n, nije lako pronaći proste faktore p i q takve da je n = pq. Ta težina je presudna, jer kada bi p i q bili poznati, tada ne bi bilo teško, uz poznat javni ključ e, pronaći d — privatni ključ — takav da važi ed = 1 mod (p-1)(q-1).

Za kriptografiju javnog ključa vjerovalo se 1997. godine da je modul od 768 bita, sastavljen od dva prosta faktora od po oko 384 bita, dovoljan za sigurnost do 2004. godine. Drugim riječima, „dovoljno velik“ modul bio je približno n = 2^768, pri čemu su p i q prosti brojevi reda veličine oko 2^384. Najbrži poznati algoritam za faktorizaciju bio je number field sieve, čije vrijeme izvođenja za faktorizaciju velikog broja veličine n ima red:

O(exp[1.9223*(ln n)^(1/3)*(ln ln n)^(2/3)]).

Da bi se faktorisao broj n reda veličine n = 2^1024, bilo bi potrebno oko 2^87 koraka. (Uvrstite n = 2^1024 u gornji izraz.) Ako računar izvršava 1 milion instrukcija u sekundi, onda bi u jednoj godini izvršio 31.536.000 × 1.000.000 instrukcija, što predstavlja jednu „mips-godinu“. Pošto je to približno jednako 2^45 koraka godišnje, bilo bi potrebno oko 2^(87-45) = 2^42 godina da se faktorisaо broj n, odnosno oko 410^12 godina. I to za mašinu koja izvršava 1 milion instrukcija u sekundi. Pentium od 100 megaherca izvršava oko 50 miliona instrukcija u sekundi, pa bi na toj mašini broj mogao biti faktorizovan za oko 810^10 godina.

RSA koristi javne ključeve za enkripciju simetričnih sesijskih ključeva. Ovi potonji često nisu sigurni. Poruka enkriptovana 40-bitnim simetričnim sesijskim ključem, koristeći RSA-ov RC4 stream algoritam enkripcije, u prosjeku zahtijeva 64 mips-godine da bi bila probijena. Drugim riječima, računar koji radi sa 64 miliona instrukcija u sekundi trebao bi godinu dana da probije enkripciju te poruke. Ova veličina, 40 bita, donedavno je bila maksimalna dužina simetričnog ključa dozvoljena za američki izvozni softver, prema International Traffic in Arms Regulations, iako su u domaćem softveru mogli biti korišteni 128-bitni ključevi. Zaključno sa 1997. godinom, simetrični ključevi kraći od 90 bita nisu se smatrali sigurnim.

F. Hash funkcije i digitalni potpisi

Često, kada neko želi da potpiše nešto, poput duge poruke ili dokumenta, nepraktično je potpisivati cijelu poruku. Jedan od razloga je što je kriptografija javnog ključa spora. Zato se koristi rješenje u vidu stvaranja sažetka poruke, koji je broj ili niz fiksne dužine koji predstavlja poruku. Poruka može imati, na primjer, 50.000 bita, dok sažetak poruke može imati samo 128 bita. Ideja je da se potpisuje sažetak poruke, a ne sama poruka.

Na primjer, pošiljalac poruke može napraviti i potpisati sažetak poruke, tako što će ga enkriptovati svojim privatnim ključem. Enkriptovani sažetak se šalje zajedno sa porukom. Zatim primalac poruke i enkriptovanog sažetka može: prvo ponovo izračunati sažetak iz primljene poruke, drugo dekriptovati enkriptovani sažetak koristeći javni ključ pošiljaoca, i treće uporediti da li su ta dva rezultata ista. Ako jesu, tada se sa velikom vjerovatnoćom može zaključiti da je primljena poruka ista kao i poslata, i da je zaista potiče od vlasnika javnog ključa koji je korišten za dekripciju sažetka. Ovaj proces provjere autentičnosti poruke naziva se provjera autentičnosti poruke.

Hash funkcije koriste se za stvaranje sažetaka poruke. Hash funkcija H(x) preslikava bilo koju poruku promjenljive dužine x = M u niz (binarni broj) fiksne dužine h:

h = H(M).

Taj fiksni niz h naziva se hash vrijednost. „Sažetak poruke“ je jednostavno hash vrijednost određene poruke. Različite hash funkcije H(x) daju različite hash vrijednosti. Tipična dužina hash niza je 128 bita, kao kod RSA-ovog MD5 (Message Digest 5). To znači da se svaka poruka mapira u jedan od 2^128 mogućih ishoda. Zbog toga je vjerovatnoća da dvije poruke imaju isti hash veoma mala. Cilj je da hash vrijednosti budu ravnomjerno raspoređene po prostoru od 2^128 mogućih ishoda, jer ako bi neki ishodi bili češći, postojala bi veća vjerovatnoća da dvije različite poruke imaju isti hash.

Ako dvije različite poruke imaju isti hash, to se naziva kolizija. Ako hash funkcija ravnomjerno raspoređuje rezultate, kaže se da je relativno „bez kolizija“, odnosno preciznije, „otporna na kolizije“. Nijedna funkcija koja preslikava veći prostor u manji ne može izbjeći sve kolizije, pa je termin „otporna na kolizije“ ispravniji. Korištenje takvih hash funkcija pomaže u sprečavanju poricanja poruke. Niko neće moći poreći da je potpisao određenu poruku tako što će proizvesti drugu poruku sa istim hashom i tvrditi da je ona bila prava. Jer ako bi bilo moguće pronaći drugu poruku sa istim hashom kao potpisana poruka, tada bi se potpis mogao prebaciti na tu lažnu poruku i tvrditi da je ona potpisana.

Pored otpornosti na kolizije, dobra hash funkcija mora biti i jednosmjerna. To znači da ne bi trebalo biti moguće praktično izračunati originalnu poruku na osnovu njenog hash-a. Ako ne možete izračunati originalnu poruku iz sažetka, niti pronaći drugu poruku sa istim hashom, tada ne možete falsifikovati potpisanu poruku tokom prenosa ili skladištenja.

Hash funkcije i tajni ključevi zajedno se koriste za stvaranje digitalnih potpisa. Prvo se izračuna hash h poruke M. Zatim se ta vrijednost enkriptuje privatnim ključem pošiljaoca, čime se dobija Esk(h). Ova enkriptovana hash vrijednost šalje se zajedno sa porukom. Primalac koristi javni ključ pošiljaoca da dekriptuje hash:

Dpk(Esk(h)) = h.

Zatim primalac sam izračunava hash iz poruke:

h = H(M).

Ako oba rezultata daju istu vrijednost h, tada poruka mora poticati od vlasnika javnog ključa pk, i poruka nije mogla biti izmijenjena.

Zašto? Zato što ako je poruka izmijenjena u, recimo, M+, tada hash vrijednost h+ = H(M+) neće odgovarati (osim uz zanemarljivu vjerovatnoću od oko 1/(2^128) za hash od 128 bita). Takođe, ako hash nije potpisan odgovarajućim privatnim ključem sk, već nekim drugim sk+, tada dekripcija neće dati ispravan rezultat:

Dpk(Esk+(h)) ≠ h.

Zato je digitalni potpis superiorniji od rukom pisanog potpisa, jer potvrđuje i identitet potpisnika i sadržaj poruke. I najmanja promjena u poruci M uzrokovaće neuspjeh provjere potpisa.

Dve poznate hash funkcije su RSA-ov MD5 (Message Digest 5) i NIST-ov SHA-1 (Secure Hash Algorithm). MD5 daje hash od 128 bita, dok SHA-1 daje hash od 160 bita. Postoje i RIPEMD-128 i RIPEMD-160, koji daju hash vrijednosti od 128, odnosno 160 bita.

Da li su ove hash funkcije zaista otporne na kolizije? Godine 1994. P. van Oorschot i M. Wiener procijenili su da bi se za 10 miliona dolara mogao napraviti specijalizovani računar za traženje kolizija u MD5, i da bi se one u prosjeku nalazile za 24 dana. MD5 je baziran na starijem MD4, koji se danas smatra kompromitovanim. RSA takođe ne preporučuje korištenje MD2, starije hash funkcije za 8-bitne sisteme. Što se tiče MD5, RSA je kasnije izjavio da postojeći potpisi bazirani na MD5 nisu ugroženi, ali da se MD5 ne bi trebao koristiti za nove primjene koje zahtijevaju otpornost na kolizije.

Za sada se SHA-1, RIPEMD-128 i RIPEMD-160 mogu smatrati sigurnim.

G. Slijepe (blind) digitalne potpise

Pretpostavimo da korisnik želi da banka potpiše određeni digitalni novac sa serijskim brojem x, ali ne želi da banka zna koji konkretan novčić potpisuje. To se može postići pomoću protokola slijepog potpisa. Jednostavan primjer, koristeći RSA sistem javnog ključa, izgleda ovako (vidi i Tabelu 3):

1. Korisnik bira faktor zasljepljivanja r, nasumično i nezavisno od x, i banci šalje:

x * r^e mod n,

gdje je (e, n) javni RSA ključ banke. Drugim riječima, korisnik podiže r na stepen e, množi ga sa serijskim brojem x i šalje banci rezultat mod n.

2. Banka potpisuje digitalni novac, odnosno zaslijepljeni broj, koristeći svoj privatni RSA ključ d:

(x * r^e)^d = (x^d) * (r^(e*d)) = r * x^d mod n.

Podsjetimo da važi r^(e*d) = r, prema ranijem rezultatu. Banka potpisuje digitalni novac tako što ga podiže na stepen svog privatnog ključa d i rezultat svodi mod n. Banka zatim vraća „novčić“ korisniku.

3. Korisnik uklanja faktor zasljepljivanja:

(r * x^d) / r = x^d mod n.

Korisnik zadržava potpisani digitalni novac x^d za kasniju upotrebu.

Pošto je r nasumičan, banka ne može odvojeno odrediti x iz proizvoda koji je prvobitno dobila, i samim tim ne može povezati potpisivanje sa konkretnim korisnikom kada se taj novčić kasnije potroši. Trošenje novčića je neizvodivo za praćenje. Kada se novčić ponovo pojavi u banci, ona može provjeriti da li je validan, ali ne može znati kome je izdat.

Tabela 3: Protokol slijepog potpisa

Protokol slijepog potpisa	Primjer
Digitalni novac ima serijski broj x.	Digitalni novac ima serijski broj x = 8.
Korisnik bira faktor zasljepljivanja r.	Korisnik bira r = 5.
Korisnik računa x*r^e mod n, gdje je (e, n) javni ključ banke.	Korisnik računa 8*5^7 mod 143, koristeći javni ključ banke (7, 143). Rezultat je 90.
Banka potpisuje broj koristeći svoj privatni ključ d, dobijajući r*x^d mod n.	Banka potpisuje 90 svojim privatnim ključem 103 i dobija, mod 143: 90^103 = (8*5^7)^103 = 8^103 * 5^721 = 5 * 8^103.
Korisnik uklanja faktor zasljepljivanja r, dobijajući x^d mod n.	Korisnik uklanja faktor 5 i dobija (8^103*5)/5 = 8^103 mod 143.

Drugim riječima, digitalni novac sa serijskim brojem 8 sada je potpisan privatnim ključem banke 103. Svako može provjeriti da je serijski broj 8 koristeći javni ključ banke (7, 143), tako što izračuna:

(8^103)^7 mod 143 = 8^721 mod 143 = 8*(8^120)^6 = 8*(1)^6 = 8.

Da sumiramo protokol slijepog potpisa, za bilo koju poruku M korisnik banci šalje:

r^e * M mod n.

Banka vraća:

r * M^d mod n.

Korisnik zatim uklanja nasumični faktor r i dobija:

M^d mod n

kao potpisanu poruku.

Protokol slijepog potpisa predstavio je David Chaum 1982. godine. Postoje i druge varijante potpisnih protokola koje su djelimično slijepe, tzv. „restriktivni slijepi potpisi“, koji otkrivaju identitet vlasnika digitalnog novca ako isti novčić pokuša potrošiti više puta. Ovi protokoli biće razmatrani u kontekstu sistema digitalnog novca Stefana Brandsa, kao i u nastavku, u vezi sa identifikacijom dvostrukog trošenja.

H. Identifikacija dvostrukog trošenja (Double-spending Identification)

Offline sistem digitalnog novca koji omogućava anonimnost kupca ima problem: ako kupac pokuša prevaru dvostrukim trošenjem (pokušava potrošiti isti digitalni novac više puta), banka i prodavac nemaju klasičan način da reaguju protiv kupca, jer ne znaju njegov identitet. (U online sistemima, novčić se obično provjerava u bazi već potrošenih novčića prije nego što roba ili usluga budu isporučeni.)

Jedan način rješavanja problema dvostrukog trošenja u offline sistemima je da se od kupca traži da otkrije određene informacije o sebi prilikom podizanja novca. Te informacije se dijele na segmente tako da nijedan pojedinačni dio ne otkriva identitet kupca, ali dva dijela zajedno ga otkrivaju. Ako kupac pokuša dvostruko trošenje, banka će dobiti dva dijela informacija, identitet će biti otkriven i banka može pokrenuti pravni postupak.

1. Cut and Choose metoda

U „cut and choose“ metodi, kupac kreira N parova brojeva koji su povezani sa digitalno potpisanim novčićem u trenutku podizanja. Bilo koji par može identifikovati kupca. Banka može provjeriti da svi parovi postoje.

Kada kupac ponudi novčić prodavcu, prodavac šalje „izazov“, niz od N nasumičnih bitova, na primjer: 10001011… Ako je bit „0“, šalje se prvi broj iz odgovarajućeg para, a ako je „1“, šalje se drugi broj.

Šta to znači? Ako kupac kasnije pokuša potrošiti isti novčić kod istog ili drugog prodavca, i dobije drugačiji niz bitova kao izazov, gotovo sigurno će neki bitovi biti različiti između dva izazova. Tada će različiti dijelovi parova biti otkriveni i kupac će biti identifikovan.

U primjeru iz Tabele 4 vidimo da se tri bita razlikuju između nizova 10001011 i 11011010, pa bilo koji od ta tri para može otkriti identitet kupca.

Problem ove metode je sporost i neefikasnost, jer zahtijeva veliku količinu podataka. Chaum-Fiat-Naor (1990) sistem koristi ovu metodu, ali je neefikasan upravo iz tog razloga. Veća efikasnost postiže se Schnorr protokolima, koji slijede u nastavku.

Tabela 4: Poklapanje u Cut and Choose metodi

Parovi brojeva	10001011	11011010	Otkriven par?
(328, 956)	956	956	Ne
(1124, 333)	1124	333	Da
(516, 2251)	516	516	Ne
(7, 895)	7	895	Da
(486, 585)	585	585	Ne
(228, 61)	228	228	Ne
(1591, 1592)	1592	1592	Ne
(825, 667)	667	825	Da

2. Zero-knowledge dokazi i Schnorr protokoli

Zero-knowledge dokaz je takav dokaz u kojem, kroz neki protokol ili postupak, možete pokazati da posjedujete znanje o nečemu, obično o nekom broju ili skupu brojeva, a da pritom ne morate tu stvar zaista otkriti drugoj strani.

Na primjer, zamislite bankarski sef sa jednim vratima i numeričkom kombinacijom koja se može unijeti sa obje strane vrata. Alice ne zna tu kombinaciju. Da biste Alici dokazali da je vi znate, dozvolite joj da vas zaključa u sef. Zatim sa svoje strane unesete kombinaciju, otvorite vrata i izađete iz sefa. Vaše ponovno pojavljivanje iznutra dokazuje da znate kombinaciju, a da pritom niste morali otkriti ništa o samoj kombinaciji Alici. Time ste izveli zero-knowledge dokaz.

Jedan primjer zero-knowledge dokaza nalazi se u Schnorr protokolu autentifikacije, odnosno identifikacije. Schnorr autentifikacija je još jedan primjer sistema zasnovanog na diskretnim logaritmima. Pretpostavimo da korisnik dokazuje trgovcu da ona, korisnik, zna svoj vlastiti tajni ključ x. Drugim riječima, ona dokazuje da je zaista osoba za koju se predstavlja, jer niko drugi ne zna taj tajni ključ.

Prvo korisnik šalje trgovcu nasumičan broj w. Trgovac zatim odgovara izazovom, odnosno brojem c. Da bi dokazala svoj identitet, korisnik zatim odgovara tačkom y na pravoj:

y = w + x*c mod q,

za neki međusobno dogovoreni prost broj q.

To znači da, kada trgovac pošalje izazov c, korisnik brzo uzvraća sa y, što može učiniti zato što zna svoj tajni ključ x.

Naravno, postupak ne može biti urađen baš ovako, jer bi trgovac, koji sada zna c, w i y, takođe mogao da odredi x. Zato želimo malo prikriti stvari tako da trgovac može utvrditi da je y ispravan odgovor na izazov c, a da pritom ne može odrediti sam x.

Da bismo to postigli, eksponenciramo jednačinu y = w + x*c pomoću nekog generatora g u grupi G(q), i uzimamo rezultat modulo nekog prostog broja p, pri čemu q dijeli p-1:

g^y = g^w * g^(x*c) mod p.

Sada će g^w = a biti nasumičan broj koji korisnik šalje trgovcu. Neka je h = g^x mod p. Taj broj h nazvaćemo javnim ključem korisnika. I on će biti poznat trgovcu. Tada posljednja jednačina glasi:

g^y = a * h^c mod p.

Da rezimiramo, korisnik šalje vrijednost a = g^w trgovcu. Trgovac prihvata a, šalje izazov c i prima nazad y. Trgovac, znajući p, q, javni ključ h i bazu odnosno generator g, sada može provjeriti identitet:

g^y =? a*h^c mod p.

Detalji ovog postupka korak po korak prikazani su u Tabeli 5.

Tabela 5: Schnorr protokol autentifikacije

Schnorr autentifikacioni protokol	Primjer
Priprema
Izabrati dva prosta broja p i q, gdje je q faktor broja p−1.	Izabrati p = 23, q = 11, gdje je 11 faktor broja 22 = 23−1.
Izabrati g (različit od 1) tako da važi g^q = 1 mod p.	Izabrati g tako da g^11 = 1 mod 23. Neka je g = 2, jer 2^11 = 2048 = 1 mod 23.
Generisati tajni ključ izborom x < q.	Izabrati x = 9, jer 9 < 11.
Generisati javni ključ računanjem h, gdje je h = g^x mod p.	h = 2^9 mod 23 = 6.
Napomena: p, q, g i h su javni. Samo je x tajan.	p = 23, q = 11, g = 2 i h = 6 su javni. Samo je x = 9 tajan.
Autentifikacija
Kupac bira nasumičan broj w < q i računa a = g^w mod p.	Kupac bira w = 3 < 11 i računa a = 2^3 mod 23 = 8.
Kupac šalje a trgovcu.	Kupac šalje a = 8 trgovcu.
Trgovac šalje kupcu nasumičan broj c, gdje je c između 0 i 2^t − 1, gdje je t približno 72.	Trgovac šalje c = 5.
Kupac računa y = w + x*c mod q i vraća y trgovcu.	Kupac računa y = 3 + 9*5 mod 11 = 48 mod 11 = 4 i šalje y = 4 trgovcu.
Trgovac provjerava: g^y = a*h^c mod p.	Trgovac računa ah^c mod p = 86^5 mod 23 = 62208 mod 23 = 16. Takođe računa g^y mod p = 2^4 = 16. Vrijednosti su iste, pa trgovac prihvata da kupac zna x.

Zašto ovaj postupak funkcioniše?

Zato što bi, da bi se pronašla vrijednost y bez poznavanja tajnog ključa, korisnik morao izračunati diskretne logaritme:

y = log_g [(g^w)(g^x)^c] mod p = w + xc mod q.

To nije moguće izvesti u razumnim vremenskim i finansijskim okvirima, sve dok je p približno 768 bita, q oko 140 bita, a nasumični broj w izabran iz opsega između nule i 2^72.

Dakle, korisnik je dokazao da poznaje svoj tajni ključ, a da ga nije otkrio trgovcu. Korisnik je izveo zero-knowledge dokaz.

Schnorr potpisni protokol dodaje hash funkciju ovom procesu. Umjesto da trgovac šalje izazov c, korisnik izračunava c pomoću hash funkcije. Pretpostavimo da korisnik želi poslati poruku M trgovcu. Prvo bira nasumičan broj w i računa:

a = g^w mod p,

kao i ranije. Zatim spaja M i a i računa hash vrijednost c:

c = H(M, a)

koristeći hash funkciju H( ). Nakon toga računa:

y = w + x*c mod q,

i šalje potpis (c, y) zajedno sa vrijednošću a i porukom M trgovcu. Par (c, y) predstavlja ekvivalent izazova i odgovora koje smo ranije vidjeli.

Trgovac zatim računa:

g^y = a*h^c mod p

i takođe računa hash vrijednost H(M, a), te provjerava da li važi:

c = H(M, a).

Ako su vrijednosti iste, potpis je validan.

U ovom slučaju, obje strane koriste istu hash funkciju H. Korisnik ima snažan razlog da bira nasumičan w svaki put, jer bi u suprotnom parovi vrijednosti y i c koje šalje trgovcu tokom vremena mogli otkriti njegov tajni ključ x. Naime, za dva različita para (c1, y1) i (c2, y2), ali sa istim w, trgovac može izračunati:

x = (y1 − y2) / (c1 − c2).

S druge strane, hash funkcija H mora biti otporna na kolizije, jer bi u suprotnom korisnik mogao manipulisati vrijednošću c.

Ovaj potpisni protokol prikazan je u Tabeli 6.

Kasnije ćemo vidjeti kako Schnorr potpisni protokol čini značajan dio sistema anonimnog digitalnog novca Stefana Brandsa.

Tabela 6: Schnorr potpisni protokol

Schnorr potpisni protokol	Primjer
Kupac želi poslati poruku M.	Kupac želi poslati poruku M = 5.
Kupac bira nasumičan broj w < q i računa a = g^w mod p.	Kupac bira w = 3 < 11 i računa a = g^w = 2^3 mod 23 = 8.
Kupac ima hash funkciju H( ).	Radi jednostavnosti, neka je H(k, j) = (k*j)^7 mod 17. (Ovo nije dobra hash funkcija.)
Kupac spaja M i a i računa hash vrijednost c = H(M, a).	Kupac spaja M = 5 i a = 8 i računa c = H(5,8) = (5*8)^7 mod 17 = 14.
Kupac računa y = w + x*c mod q i šalje (c, y), potpis, zajedno sa a i porukom M trgovcu.	Kupac računa y = 3 + 9*14 mod 11 = 8 i šalje (c, y) = (14, 8) trgovcu, zajedno sa M = 5 i a = 8.
Trgovac provjerava da li važi g^y = a*h^c mod p.	Trgovac računa g^y mod 23 = 2^8 mod 23 = 3. Takođe računa ah^c mod 23 = 86^14 mod 23 = 3. Vrijednosti su jednake.
Trgovac računa H(M, a).	Trgovac računa H(5,8) = (5*8)^7 mod 17 = 14.
Trgovac prihvata potpis ako važi c = H(M, a).	Trgovac prihvata potpis jer c = 14 = H(5,8).

Evo kompletnog prevoda uz očuvanu strukturu originala:

I. Problem reprezentacije (The Representation Problem)

Kao što smo ranije vidjeli, Diffie-Hellman razmjena ključeva i Schnorr potpisi zasnivaju se na praktičnoj teškoći računanja diskretnih logaritama. Isto važi i za Digital Signature Standard američke vlade.

Problem reprezentacije proširuje ovu računsku teškoću na pronalaženje skupa brojeva povezanih sa diskretnim logaritmima. Mogućnost korištenja cijelog skupa teško izračunljivih brojeva, umjesto jednog logaritma, daje nam važan stepen fleksibilnosti u kreiranju anonimnih sistema digitalnog novca.

Neka je g generator podgrupe G(q) u Z(p)* (g može biti bilo koji element iz G(q) osim 1). Podsjetimo da problem diskretnog logaritma podrazumijeva pronalaženje eksponenta a takvog da, za dati h iz G(q), važi:

g^a = h mod p.

Drugim riječima:

a = log h mod p,

pri čemu je baza g. Eksponent a je diskretni logaritam od h.

Problem reprezentacije je generalizacija ovog koncepta. Umjesto jednog broja, traži se skup brojeva koji se naziva „indeks-torka“ (index-tuple).

Neka je k ≥ 2, i neka važi 1 ≤ ai ≤ q, za i = 1 do k. Problem reprezentacije za dati h iz G(q) je pronaći indeks-torku {a1, …, ak} za generator-torku {g1, …, gk} iz G(q), tako da važi:

g1^a1 * g2^a2 * … * gk^ak = h mod p.

Indeks-torka {a1, …, ak} naziva se reprezentacija.

Napomena: slučaj ai = 0 se izostavlja, jer ai = q daje isti rezultat, pošto važi gi^q = 1 mod p, isto kao gi^0 = 1.

Na primjer, ranije smo vidjeli da su {2, 3} generatori grupe G(11) u Z(23)*. Jedan primjer problema reprezentacije je pronaći a1 i a2 takve da za h = 13 važi:

2^a1 * 3^a2 = 13 mod 23.

Ovo je ekvivalentno pronalaženju „težinskog zbira“ diskretnih logaritama:

a1 * log(2) + a2 * log(3) = log(13) mod 23.

Jedno rješenje je a1 = 2 i a2 = 2, jer:

2^2 * 3^2 = 4 * 9 = 36 = 13 mod 23.

Drugo rješenje je a1 = 7 i a2 = 11, jer:

2^7 * 3^11 = 128 * 1 = 13 mod 23.

Još jedno rješenje je a1 = 3 i a2 = 6, jer:

2^3 * 3^6 = 8 * 729 = 13 mod 23.

Primijetite da ako postoji k elemenata u reprezentaciji {a1, …, ak}, tada postoji:

q^(k−1) reprezentacija broja h.

To slijedi iz činjenice da a1 može imati q vrijednosti, a2 takođe q vrijednosti, itd., sve do ak−1, što daje ukupno q^(k−1) mogućnosti. Posljednji element ak mora biti izabran tako da zadovolji jednačinu:

g1^a1 * g2^a2 * … * gk^ak = h mod p.

Dakle:

Za k = 2 u G(11) postoji 11^(2−1) = 11 reprezentacija svakog broja h.

Za k = 3 postoji 11^(3−1) = 121 reprezentacija.

J. Dokazivanje poznavanja reprezentacije (Proving Knowledge of a Representation)

Pošto se reprezentacija ne može pronaći bez rješavanja diskretnih logaritama (što je praktično neizvodivo za velike brojeve), znanje reprezentacije može se koristiti za dokazivanje identiteta.

Sljedeći protokol služi da dokaže da poznajete reprezentaciju, bez njenog otkrivanja.

Pretpostavimo da vi, dokazivač P, znate reprezentaciju:

h = g1^a1 * g2^a2 * … * gk^ak mod p.

Dakle, znate {a1, …, ak} i želite to dokazati bez otkrivanja tih vrijednosti.

Drugu stranu nazvaćemo verifikator V.

Korak 1

Dokazivač P generiše k nasumičnih brojeva {w1, …, wk} iz G(q).

Zatim šalje verifikatoru:

z = g1^w1 * g2^w2 * … * gk^wk mod p.

Korak 2

Verifikator V prima z i generiše nasumičan broj c (izazov), te ga šalje nazad.

Korak 3

Dokazivač računa:

ri = ai + c*wi mod q,

za i = 1 do k, i šalje sve ri verifikatoru.

Korak 4

Verifikator računa:

z * h^c

i upoređuje sa:

g1^r1 * g2^r2 * … * gk^rk mod p.

Ako su vrijednosti jednake, verifikator prihvata da dokazivač zna reprezentaciju.

Ove vrijednosti će biti jednake ako dokazivač zaista zna ai, jer:

z * h^c = (g1^w1 * g2^w2 * … * gk^wk) * (g1^a1 * g2^a2 * … * gk^ak)^c

= g1^(w1 + ca1) * g2^(w2 + ca2) * … * gk^(wk + c*ak)

= g1^r1 * g2^r2 * … * gk^rk mod p.

Ovaj proces, za slučaj sa dva generatora, prikazan je u Tabeli 7.

Tabela 7: Dokazivanje poznavanja reprezentacije

Dokazivač P	Verifikator V
Zna reprezentaciju h = g1^a1 * g2^a2; tj. zna a1 i a2.	Zna samo h i g1, g2; ne zna a1 i a2.
Generiše dva nasumična broja w1 i w2.
Računa z = g1^w1 * g2^w2 i šalje z verifikatoru.	Prima z od P. Generiše izazov c.
Šalje izazov c dokazivaču.
Prima c. Računa ri = ai + c*wi mod q, za i = 1 do 2. Šalje ove vrijednosti verifikatoru.	Prima ri. Provjerava da li važi: z * h^c = g1^r1 * g2^r2 mod p. Ako jednakost važi, verifikator prihvata da dokazivač zna reprezentaciju (koja mu i dalje nije poznata) od h — tj. a1 i a2.

K. Sertifikacione autoritete i digitalni sertifikati

Odjel za motorna vozila (Department of Motor Vehicles) predstavlja primjer sertifikacione autoritete. On izdaje sertifikat, poznat kao vozačka dozvola, koji potvrđuje vezu između fotografije osobe i ličnih podataka na dozvoli.

Slično tome, digitalni sertifikat potvrđuje vezu između nečijeg javnog ključa i identiteta te osobe (kako god da je identitet definisan). Digitalni sertifikat obično izdaje pouzdana treća strana, koja se naziva sertifikaciona autoriteta (CA).

Jedan primjer privatne CA je VeriSign Inc., koja pruža CA usluge za komercijalne web preglednike. Kompanije moraju dostaviti određene ovjerene poslovne dokumente VeriSignu prije nego što dobiju digitalni sertifikat. Ostale komercijalne CA usluge uključuju GTE CyberTrust i IBM Net.Registry. Softverski paketi za upravljanje CA sistemima uključuju Nortel WebCA i BBN SafeKeyper Certificate Management System.

Upotreba digitalnog sertifikata

Digitalni sertifikat se koristi zajedno sa digitalnim potpisom na sljedeći način.

Kada Bob potpiše poruku svojim privatnim ključem i pošalje je drugoj strani, on uz potpis šalje i sertifikat.

Primalac poruke može tada provjeriti potpis koristeći Bobov javni ključ, ali takođe pregleda sertifikat kako bi imao dodatnu sigurnost da javni ključ zaista pripada Bobu.

Drugim riječima, „Bob“ je potpisao poruku svojim tajnim ključem, što se može provjeriti „Bobovim“ javnim ključem. Sertifikat služi da potvrdi da je „Bob“ zaista Bob.

Uloga sertifikacione autoritete

Sertifikaciona autoriteta obavlja svoj posao tako što povezuje Bobov identitet sa njegovim javnim ključem i potpisuje te povezane informacije svojim privatnim ključem.

Ova potpisana poruka (digitalni sertifikat) može se pročitati korištenjem javnog ključa CA.

Pretpostavlja se da svi posjeduju sigurnu kopiju javnog ključa CA kako bi mogli provjeriti potpise na digitalnim sertifikatima.

Ako je privatni ključ CA označen kao sk-ca, a Bobov javni ključ kao pk-bob, tada CA kreira sertifikat u obliku:

CA sertifikat = Esk-ca {Bobov identitet, pk-bob}

Provjera se vrši korištenjem javnog ključa CA pk-ca:

verifikacija = Dpk-ca (Esk-ca {Bobov identitet, pk-bob}) = {Bobov identitet, pk-bob}

Lanac povjerenja

Ovaj mehanizam, naravno, prebacuje odgovornost na viši nivo autoriteta.

CA može potvrditi vezu između Bobovog identiteta i njegovog javnog ključa, ali kako znamo da je veza između CA i njenog javnog ključa validna? Može li se vjerovati CA?

Zbog toga upotreba sertifikacionih autoriteta stvara lanac povjerenja.

Na vrhu se nalazi glavna (root) sertifikaciona autoriteta koju svi poznaju i kojoj vjeruju (barem u teoriji). Ona potvrđuje javne ključeve drugih CA, koje dalje potvrđuju korisnike, sve dok neka CA ne potvrdi da Bobov ključ zaista pripada Bobu.

Javni i privatni ključevi glavnih CA nazivaju se root ključevi. Javni root ključ glavne CA je široko distribuiran i može čak biti objavljen u velikim novinama.

Sigurnost i podjela ključa

Vrijednost sertifikata potpisanih privatnim ključem CA zavisi od sigurnosti tog privatnog ključa.

Privatni (tajni) root ključ može biti podijeljen na više dijelova radi sigurnosti.

Na primjer, može se podijeliti na pet dijelova, od kojih su bilo koja dva dovoljna da se rekonstruiše ključ. (Ovo je slično zahtjevu da dvije osobe potpišu ček iznad određenog iznosa.)

Objašnjenje podjele ključa

Da bismo razumjeli podjelu ključa, zamislimo pravu u dvodimenzionalnoj ravni.

Bilo koje dvije tačke na pravoj određuju njen nagib. Pretpostavimo da nagib predstavlja tajni ključ.

Jedna tačka ne otkriva nagib (tajni ključ), ali dvije tačke ga otkrivaju.

Dakle, da bi se ključ podijelio, bira se više tačaka na pravoj i svaka se daje drugoj osobi.

Bilo koje dvije osobe mogu rekonstruisati ključ potreban za potpisivanje.

Ovaj proces naziva se dijeljenje tajne (secret sharing).

Šira upotreba digitalnih sertifikata

Digitalni sertifikati (i CA) mogu se koristiti i za druge svrhe, ne samo za dokazivanje identiteta.

Na primjer, sertifikat može potvrditi limit potrošnje na kreditnoj kartici.

Uopšteno, digitalni sertifikat je ugovor između dvije ili više strana koji potvrđuje ili definiše određene informacije.

X.509 standard

Jedan od formata digitalnih sertifikata definisan je u standardu ITU-T X.509.

X.509 sertifikat sadrži sljedeća polja:

– Verzija – verzija X.509 specifikacije (verzija 1 iz 1988, verzija 2 iz 1993, verzija 3 iz 1994)

– Serijski broj – jedinstveni broj sertifikata

– Identifikator algoritma potpisa – npr. DSA

– Naziv izdavača – CA koja izdaje sertifikat

– Period važenja – trajanje sertifikata

– Subjekt (korisnik) – osoba ili entitet

– Informacije o javnom ključu subjekta

– Jedinstveni identifikator subjekta – npr. račun XYZ123 u UBS banci, Bern

– Potpis CA

Podrška u protokolima

X.509 standard podržavaju mnogi sigurnosni protokoli:

– S-HTTP

– SSL

– PEM

– PKCS-7

Verzija 3 sertifikata koristi se i u SET sistemu.

Objavljeno 10. oktobra 1997

Web stranica: http://www.aci.net/kalliste/

Link originalnog teksta: https://groups.csail.mit.edu/mac/classes/6.805/articles/money/cryptnum.htm

Edukacija, edukacija i samo edukacija!

Idemo dalje.

Petar Miljić – Finansije za narod

👉 Znanjem protiv hajpa – uvijek sigurniji put!

🌐 Posjeti nas: https://kriptoentuzijasti.io

💬 Pridruži se zajednici: https://discord.gg/kriptoentuzijasti

🐦 Prati nas na X-u: https://twitter.com/k_entuzijasti

🧠💡 Ne zaboravite: budućnost se ne gradi kad svi već znaju za nju – već onda kad je vide samo rijetki.

🔥 Budućnost pripada onima koji misle dugoročno. 🔥

Jedno je sigurno – budućnost kripta neće biti dosadna!

Više edukativnih članaka možete pronaći na našoj web stranici kanalu i diskord platformi!

Ako vam se sviđa ono što čitate, podijelite članak na društvenim mrežama i pomozite nam širiti finacijsku slobodu i kripto znanje. Zajedno gradimo svijet financija i kripta!

#crypto #Bitcoin #KASPA #HBAR #XRP #RENDER #NEXO #BulRan2032

https://kriptoentuzijasti.io/ko-ce-opstati-u-novom-finansijskom-sistemu

https://kriptoentuzijasti.io/tri-nivoa-kripta-koje-vecina-ne-razumije