MATEMATIKA PRIJE BITCOINA
Kada danas govorimo o digitalnom novcu, većina ljudi prvo pomisli na Bitcoin, blockchain, privatne ključeve i kripto-novčanike. Međutim, mnogo prije nego što je Bitcoin nastao, postojala je čitava matematička i kriptografska infrastruktura bez koje digitalni novac uopšte ne bi bio moguć. Upravo zato tekst „Cryptography and Number Theory for Digital Cash“ J. Orlina Grabbea ima posebnu vrijednost. On pokazuje kako se iza naizgled apstraktnih matematičkih pojmova kriju vrlo konkretni mehanizmi za stvaranje sigurnog, privatnog i provjerljivog digitalnog novca.
Ovaj tekst je naročito važan kao most između čiste matematike i praktične finansijske tehnologije. Počinje od modularne aritmetike, grupa, generatora, prostih brojeva i diskretnih logaritama, odnosno od pojmova koji prosječnom čitaocu mogu djelovati kao teorija bez neposredne primjene. Ali korak po korak pokazuje da upravo ti pojmovi čine temelj sistema koji omogućavaju sigurno dogovaranje ključeva, digitalne potpise, dokazivanje identiteta bez otkrivanja tajni i, na kraju, razvoj anonimnog digitalnog novca.
Posebno je važno razumjeti da digitalni novac nije samo pitanje softvera niti samo pitanje bankarstva. U svojoj srži, on je problem matematike povjerenja. Ako dvije strane žele izvršiti transakciju preko nesigurne mreže, moraju imati način da provjere identitet, autentičnost poruke i integritet podataka, a da pritom ne moraju vjerovati svakom učesniku u sistemu. Upravo tu ulaze kriptografski algoritmi.
Diffie-Hellman rješava problem kako dvije strane mogu dogovoriti zajednički tajni ključ bez prethodne razmjene tog ključa. RSA pokazuje kako jedan ključ može biti javan, a drugi ostati tajan, čime se otvara mogućnost šifrovanja i digitalnog potpisa. Hash funkcije omogućavaju da se ogromni dokumenti i poruke svedu na kratke digitalne otiske koji mogu biti provjereni i potpisani. Schnorrovi protokoli i zero-knowledge dokazi omogućavaju da neko dokaže da zna tajnu, a da samu tajnu nikada ne otkrije.
A onda dolazimo do jednog od najvažnijih elemenata za digitalni novac: blind signatures, odnosno slijepih potpisa.
Ideja je revolucionarna u svojoj jednostavnosti. Banka može potpisati digitalni novčić, potvrditi da je legitiman i dati mu punu vrijednost, a da pritom ne zna koji je tačno novčić potpisala. Kada se taj novčić kasnije potroši, Banka može provjeriti da je njen potpis originalan, ali ga ne može jednostavno povezati sa korisnikom kojem ga je prethodno izdala.
To je pokušaj da se u digitalnom svijetu reprodukuje jedna od ključnih osobina fizičke gotovine: privatnost transakcije.
Tu nastaje i veliki problem koji će kasnije postati centralan za Bitcoin – double-spending, odnosno dvostruko trošenje.
Fizičku novčanicu možete predati samo jednom. Kada je date trgovcu, više je nemate. Digitalni podatak, međutim, može se kopirati beskonačno mnogo puta. Ako je digitalni novčić samo niz bitova, šta sprečava korisnika da isti novčić pošalje deset različitih ljudi?
Grabbe objašnjava kako su rani sistemi digitalnog novca pokušavali riješiti taj problem. Jedan pristup bio je takozvani cut-and-choose, gdje se identifikacioni podaci korisnika dijele na dijelove tako da jedna transakcija ne otkriva njegov identitet, ali dvije različite upotrebe istog novčića otkrivaju dovoljno informacija da se korisnik identifikuje.
Kasniji i elegantniji pristupi koriste zero-knowledge protokole i Schnorrovu matematiku, gdje se isti princip postiže sa manje podataka i većom efikasnošću. Pošten korisnik ostaje anoniman. Ali ako pokuša isti novčić potrošiti više puta, njegove dvije transakcije zajedno ostavljaju matematički trag koji može otkriti njegov identitet.
To je izuzetno važna ideja.
Digitalna privatnost ovdje nije zamišljena kao potpuna neodgovornost. Sistem pokušava omogućiti anonimnost onome ko poštuje pravila, ali istovremeno zadržati mogućnost otkrivanja prevaranta.
Upravo se tu vidi koliko su rani istraživači digitalnog novca već razumjeli problem koji će mnogo kasnije postati centralan u kripto-industriji: kako postići ravnotežu između privatnosti, sigurnosti i sprečavanja prevare?
Poseban značaj teksta leži i u objašnjenju problema reprezentacije i dokazivanja poznavanja reprezentacije. Ti dijelovi mogu djelovati matematički apstraktno, ali imaju veoma praktičnu svrhu. Oni omogućavaju da osoba dokaže da poznaje određene tajne vrijednosti povezane sa novcem ili identitetom, a da te vrijednosti ne mora pokazati drugoj strani.
To je suština onoga što danas nazivamo zero-knowledge cryptography.
Danas se zero-knowledge tehnologija često spominje u kontekstu modernih blockchain sistema, privatnih transakcija i skaliranja mreža. Međutim, ovaj tekst pokazuje da korijeni tih ideja sežu mnogo dublje i da su već devedesetih godina bile ozbiljno razvijane upravo u kontekstu digitalnog novca.
Grabbe takođe objašnjava ulogu sertifikacionih autoriteta i digitalnih sertifikata, čime se otvara još jedno ključno pitanje: kako znamo da određeni javni ključ zaista pripada osobi ili instituciji koja tvrdi da ga posjeduje?
Rješenje tradicionalnih sistema bilo je stvaranje lanca povjerenja. Jedan pouzdani autoritet potvrđuje drugi, taj drugi potvrđuje treći, sve dok se ne dođe do krajnjeg korisnika.
Ali upravo tu se vidi jedna od ključnih razlika između klasične kriptografske infrastrukture i onoga što će kasnije donijeti Bitcoin.
U tradicionalnim sistemima uvijek postoji neka centralna tačka povjerenja: banka, sertifikacioni autoritet, institucija ili organizacija koja potvrđuje identitet i validnost.
Bitcoin će mnogo kasnije pokušati ukloniti upravo tu potrebu.
Satoshi Nakamoto 2008. godine nije izmislio RSA, Diffie-Hellman, hash funkcije, digitalne potpise niti proof-of-work. Sve su to bile ideje koje su već decenijama postojale i razvijale se.
Ono što je Bitcoin uradio jeste da je te i druge postojeće elemente spojio u arhitekturu koja omogućava digitalni novac bez centralne Banke koja izdaje novčiće i bez centralne institucije koja vodi evidenciju o tome ko je šta potrošio.
Zato je ovaj tekst važan za svakoga ko želi ozbiljno razumjeti istoriju digitalnog novca.
On pokazuje da Bitcoin nije nastao iz praznine.
Prije njega postojali su decenijski pokušaji da se riješe isti fundamentalni problemi: kako šifrovati podatke, kako dokazati vlasništvo, kako zaštititi identitet, kako spriječiti falsifikovanje, kako onemogućiti dvostruko trošenje i kako omogućiti digitalnu gotovinu koja se ponaša što sličnije fizičkom novcu.
Matematika je već bila tu.
Kriptografija je već bila tu.
Blind signatures su već postojale.
Zero-knowledge dokazi su već postojali.
Problem double-spendinga već je bio jasno definisan.
Ono što još nije postojalo bilo je potpuno decentralizovano rješenje koje će omogućiti da globalna mreža sama uspostavlja redoslijed transakcija bez centralnog posrednika.
Zato ovaj tekst treba čitati ne kao zastarjeli matematički priručnik iz devedesetih, već kao jedan od važnih dokumenata koji pokazuju kako su se gradili temelji digitalnog novca mnogo prije nego što je riječ „Bitcoin“ uopšte postojala.
Jer ako želimo razumjeti šta je Bitcoin zaista donio novo, prvo moramo razumjeti šta je već bilo poznato prije njega.
U nastavku donosimo obrađeni i prevedeni tekst „KRIPTOGRAFIJA I TEORIJA BROJEVA ZA DIGITALNI NOVAC“, autora J. Orlina Grabbea.
KRIPTOGRAFIJA I TEORIJA BROJEVA ZA DIGITALNI NOVAC
Autor: J. Orlin Grabbe
Napomena: Da bi se sljedeći tekst pravilno prikazivao, vaš internet preglednik mora podržavati indekse i eksponente, odnosno HTML komande „sub“ i „sup“. Ove komande koriste se rijetko, ali se ipak koriste.
Mogućnost napada na sistem digitalnog novca ili njegove zloupotrebe u velikoj mjeri zavisi od kriptografije i kriptografskih protokola koji se u njemu koriste. Dobar sistem digitalnog novca koristi dobru kriptografiju. Dobra kriptografija zahtijeva snažne algoritme, ključeve odgovarajuće dužine i sigurno upravljanje ključevima. Bez toga može postojati veoma malo stvarne privatnosti.
Dobar sistem digitalnog novca koristi i dobre protokole. Sistem digitalnog novca Stefana Brandsa, na primjer, u velikoj mjeri zasniva se na digitalnim potpisima, posebno na Schnorrovom sistemu potpisa. Ako je sistem pravilno implementiran, njegova sigurnost zavisi upravo od sigurnosti osnovnog sistema potpisa. Ako u tom sistemu postoje slabosti, nestaju i privlačne osobine anonimnog digitalnog novca – osobine poput nemogućnosti praćenja, nemogućnosti povezivanja transakcija i sigurnosti svih učesnika.
Ako tražimo privatnost i sigurnost u bankarstvu, ne možemo ignorisati kriptografiju niti matematiku. Sposobnost sistema digitalnog novca da pruže određeni stepen sigurnosti i privatnosti ima mnogo više veze sa teorijom brojeva nego sa bankarskim propisima.
A. NEKE OSNOVNE DEFINICIJE
Šifrovanje je proces pretvaranja podataka ili poruke u nerazumljiv oblik, ali tako da se transformacija može obrnuti i originalni podaci ili poruka ponovo dobiti.
Proces šifrovanja uključuje određeni recept, odnosno skup instrukcija koji daje postupak korak po korak za transformaciju podataka. Taj recept naziva se algoritam.
Algoritam šifrovanja mora imati odgovarajući obrnuti postupak kojim se originalna poruka ponovo dobija. Taj obrnuti proces naziva se dešifrovanje.
Zajedno, tehnike šifrovanja i dešifrovanja nazivaju se kriptografija.
Algoritmi poput DES-a ili RSA-a uglavnom su javno poznati. To ima prednost jer istraživači mogu pronaći eventualne slabosti u algoritmu.
Svaki pokušaj postizanja „sigurnosti kroz skrivanje“, odnosno čuvanja algoritma u tajnosti, najčešće je kontraproduktivan, jer vjerovatno samo prikriva slabosti samog algoritma koje bi mogao iskoristiti svako ko uspije otkriti kako algoritam funkcioniše.
Kada se koristi dobar javno poznat algoritam, sigurnost zavisi od dužine ključa, koji možemo zamisliti kao niz nula i jedinica koje algoritam koristi prilikom transformacije podataka.
Jedan primjer transformacije pomoću ključa povezan je sa funkcijom XOR koja se koristi u binarnoj aritmetici.
XOR funkcija prati sljedeća pravila binarnog sabiranja:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
Pošto se ova pravila razlikuju od obične aritmetike, posebno pravilo prema kojem je 1 + 1 = 0, koristićemo oznaku „+“ u smislu XOR sabiranja.
Koristeći XOR sabiranje, bilo koji niz nula i jedinica može se koristiti kao ključ za šifrovanje i dešifrovanje podataka.
Pretpostavimo da imamo „poruku“ sastavljenu od četiri binarne cifre:
M = 1011
i četvorocifreni ključ:
k = 1010
Poruku M možemo šifrovati ključem k tako što ih saberemo prema XOR pravilima i dobijemo C = M + k:
M: 1011
k: 1010
C: 0001
Šifrovana poruka C je:
0001
Osoba koja vidi samo ovu vrijednost ne zna originalnu poruku M, jer je ona mogla biti bilo koja od šesnaest mogućih kombinacija četiri nule ili jedinice.
Međutim, ako znamo ključ, originalnu poruku veoma lako možemo vratiti. Potrebno je samo ponovo XOR sabrati ključ k sa šifrovanom porukom C:
C: 0001
k: 1010
M: 1011
Uopšteno:
M = (M + k) + k
Primjena XOR operacije dva puta sa istim ključem vraća originalnu poruku.
Sigurnost zavisi od dužine ključa k.
Kod ključa dužine četiri bita postoji šesnaest mogućih ključeva. Prva binarna cifra može biti nula ili jedan, dakle postoje dvije mogućnosti. Druga takođe ima dvije mogućnosti, pa za dva bita imamo:
2 × 2 = 4
moguća ključa.
Za tri bita:
2 × 2 × 2 = 8
mogućnosti.
Za četiri bita imamo:
16 = 2⁴
mogućnosti.
Uopšteno, za ključ dužine N postoji:
2ᴺ
mogućih ključeva.
Komercijalni DES koristi ključeve dužine 56 bita, pa prostor ključeva ima:
2⁵⁶
mogućnosti.
Iako je to ogroman broj, sa tadašnjim tehnikama kriptoanalize više nije bio dovoljno velik za sigurnost. Moguće je čak izvršiti brute-force napad, odnosno napad u kojem se jednostavno isprobava svaki mogući ključ.
Sa druge strane, prostor od:
2¹²⁸
ključeva smatra se veoma sigurnim, barem u odnosu na brute-force napade.
Prostor od 2¹²⁸ mogućnosti je:
2⁷²
puta veći od DES prostora sa 2⁵⁶ mogućnosti.
XOR sabiranje koristi se u dva DES režima šifrovanja. Electronic Code Book – ECB šifruje svaki 64-bitni blok teksta pojedinačno.
Dva druga i sigurnija režima čine svaki šifrovani blok zavisnim od prethodnih blokova.
Kod Cipher Block Chaining – CBC režima trenutni 64-bitni blok otvorenog teksta XOR-uje se sa prethodnim šifrovanim blokom prije šifrovanja 56-bitnim DES ključem k.
Ako je C(t) t-ti 64-bitni šifrovani blok, a M(t) trenutni 64-bitni blok poruke, tada je:
C(t) = Eₖ(M(t) + C(t−1))
Kod Cipher Feedback – CFB režima svaki blok otvorenog teksta XOR-uje se sa prethodnim šifrovanim blokom nakon što je taj blok šifrovan 56-bitnim DES ključem:
C(t) = M(t) + Eₖ(C(t−1))
Kod CFB režima blokovi mogu biti i manji od 64 bita.
Ključ k iz prethodnog XOR primjera bio je simetričan. Isti ključ koristio se za šifrovanje i dešifrovanje.
DES i IDEA dva su poznata algoritma sa simetričnim ključem.
Algoritmi sa simetričnim ključem često su svojevrsni pametno osmišljeni „recepti“ koji jednostavno funkcionišu.
Sistemi sa javnim ključem, odnosno asimetrični sistemi, koriste dva različita ključa za šifrovanje i dešifrovanje.
RSA je poznat primjer asimetričnog sistema.
Sistemi sa javnim ključem obično se zasnivaju na odnosima iz teorije brojeva. Proces šifrovanja funkcioniše podizanjem poruke M na određeni stepen a:
C = Mᵃ
Dok se dešifrovanje vrši podizanjem šifrovane poruke C na drugi stepen b:
M = Cᵇ
Prvi ključ, odnosno eksponent a, poznat je svima i zbog toga se naziva javni ključ.
Ključ b čuva se u tajnosti i zbog toga se naziva tajni ili privatni ključ.
B. OSNOVNA MATEMATIČKA NOTACIJA
Poruku koja se šifruje ili šalje uglavnom ćemo označavati sa M.
Za računar niz jedinica i nula koji čini M može se tretirati kao binarni broj, bez obzira na to da li M predstavlja:
„Volim te“
ili
„Duguješ mi 500 dolara“
ili
„Broj banke 437695B“.
Šifrovanje može uključivati podizanje ovog broja na određeni stepen.
Oznaka:
E(x)
predstavljaće algoritam ili funkciju šifrovanja, dok će:
D(x)
predstavljati algoritam ili funkciju dešifrovanja.
Šifrovana poruka označava se kao:
E(M)
dok bi dešifrovanje šifrovane poruke bilo:
D(E(M))
Pošto je rezultat originalna poruka:
D(E(M)) = M
Ako se poruka šifruje ili dešifruje simetričnim ključem k, koristiće se oznake:
Eₖ(x)
i
Dₖ(x)
Ako se koristi sistem sa javnim ključem, javni ključ označavaćemo sa:
pk
a privatni ili tajni ključ sa:
sk
Kod simetričnog sistema:
Dₖ(Eₖ(M)) = M
jer se isti ključ koristi za šifrovanje i dešifrovanje.
Kod sistema sa javnim ključem jedan ključ koristi se za šifrovanje, a drugi za dešifrovanje.
Zbog toga:
Dₛₖ(Eₚₖ(M)) = M
i takođe:
Dₚₖ(Eₛₖ(M)) = M
U prvom slučaju poruka je šifrovana Aliceinim javnim ključem, a zatim je Alice dešifruje svojim tajnim ključem.
U drugom slučaju, što je tipično kod digitalnih potpisa, Alice „šifruje“ poruku svojim tajnim ključem, a neko drugi je provjerava odnosno dešifruje pomoću Aliceinog javnog ključa.
Oznaka:
^
znači „podignuto na stepen“.
Na primjer:
2³ = 8
jer je dva na treći stepen jednako osam.
Jedna zvjezdica označava množenje:
3*b = 12
ili jednostavno:
3b = 12
Oznaka:
log_b(y)
predstavlja logaritam y po osnovi b.
Na primjer:
log₂(8) = 3
jer je 2³ = 8.
Oznaka:
mod p
znači da se aritmetika obavlja modulo p.
To praktično znači: broj podijelite sa p i zadržite ostatak r, pri čemu je:
0 ≤ r < p
Na primjer:
7 mod 3 = 1
jer se 3 u 7 nalazi dva puta, uz ostatak 1.
Broj kojim dijelimo – ovdje 3 – naziva se modul.
Slično:
62 mod 25 = 12
jer je:
62 = 25 × 2 + 12
Ako je modul 3:
62 = 3 × 20 + 2
pa je:
62 mod 3 = 2
Uopšteno ćemo pisati:
a = b mod n
kada a i b daju isti ostatak pri dijeljenju sa n.
Na primjer:
67 = 11 mod 7
jer:
67 mod 7 = 4
i:
11 mod 7 = 4
Dakle, za neke cijele brojeve k₁ i k₂:
a = k₁n + r
b = k₂n + r
pa je:
a − b = (k₁ − k₂)n
što znači da je a − b djeljivo sa n.
U prethodnom primjeru:
67 = 11 mod 7
jer:
67 = 9 × 7 + 4
i:
11 = 1 × 7 + 4
Zbog toga:
67 − 11 = 56 = 8 × 7
pa možemo napisati i:
7 | 56
Kada računamo cijelim brojevima, dijelimo modulom i zadržavamo samo ostatak, koristimo modularnu aritmetiku.
Većina klasičnih računara nije posebno prilagođena radu sa veoma velikim cijelim brojevima. Više im odgovara aritmetika sa pokretnim zarezom, gdje se čuva samo ograničen broj značajnih cifara.
Kriptografija sa javnim ključem, međutim, može koristiti ključeve dužine 2048 bita ili više.
Zbog toga računarske implementacije kriptografije sa javnim ključem koriste poseban softver za rad sa velikim cijelim brojevima ili posebno napravljene kriptografske čipove.
Takođe treba zapamtiti da se stepenovanje po konvenciji obavlja prije množenja.
Zbog toga:
3 × 5² = 3 × 25 = 75
dok:
(3 × 5)² = 15² = 225
Takođe:
(3 × 5)² = 3² × 5² = 9 × 25 = 225
Uopšteno:
(x × y)ᶻ = xᶻ × yᶻ
C. MODULARNA ARITMETIKA I GRUPE Z(p)* I G(q)
U većini izračunavanja povezanih sa kriptografijom sa javnim ključem i digitalnim novcem radićemo sa skupom cijelih brojeva od 0 do p−1, gdje je p veliki prost broj.
To proizlazi iz činjenice da ćemo koristiti množenje modulo p.
Takođe ćemo koristiti skup stepena od 1 do q, gdje je q veliki prost broj koji dijeli p−1.
Drugim riječima, množenje i stepenovanje odvijaće se unutar grupa:
Z(p)*
i:
G(q)
Ove dvije grupe veoma su važne za kriptografiju sa javnim ključem i digitalni novac. Koriste se kod Diffie-Hellman razmjene ključeva, Schnorrovih potpisa, Digital Signature Algorithm-a i sistema digitalnog novca Stefana Brandsa.
Skup:
Z(p) = {1, 2, 3, 4, …, p−2, p−1}*
ima sljedeću osobinu: ako pomnožimo bilo koja dva broja iz skupa i rezultat reduciramo modulo p, dobićemo ponovo element iz istog skupa.
Dakle, skup je zatvoren u odnosu na množenje.
Pored toga, za svaki broj k iz skupa postoji drugi broj:
k⁻¹
takav da:
k × k⁻¹ = 1 mod p
Drugim riječima, svaki broj u skupu ima multiplikativni inverz.
Ove osobine znače da je Z(p)* grupa u odnosu na množenje modulo p.
Pošto je grupa zatvorena u odnosu na množenje, zatvorena je i u odnosu na stepenovanje, jer je n-ti stepen nekog broja samo njegovo množenje samim sobom n puta.
Nula se ne nalazi u Z(p)* zato što nema multiplikativni inverz.
Ako nulu dodamo skupu, dobijamo:
Z(p)
koji sadrži sve ostatke modulo p, uključujući nulu.
Na primjer:
Z(11) = {1,2,3,4,5,6,7,8,9,10}*
Ako pomnožimo 5 i 8:
5 × 8 = 40 = 7 mod 11
a 7 se nalazi u skupu.
Takođe:
5 × 9 = 45 = 1 mod 11
pa je 9 multiplikativni inverz broja 5.
I obrnuto, 5 je inverz broja 9.
Slično:
2 i 6 su međusobni inverzi,
3 i 4 su međusobni inverzi.
Koji je inverz broja 10?
Odgovor je sam broj 10:
10 × 10 = 100 = 1 mod 11
Ako broj 6 podignemo na treći stepen:
6³ = 216 = 7 mod 11
opet dobijamo element skupa.
Svaki element ima multiplikativni inverz zato što je p prost broj.
Za svaki broj u:
{1,2,3,…,p−1}
najveći zajednički djelilac sa p jednak je 1.
To nije tačno ako koristimo složen broj.
Na primjer:
15 = 3 × 5
je složen broj.
Ako koristimo množenje modulo 15 sa skupom:
{1,2,…,14}
broj 6 nema inverz.
Zaista:
6×0 = 6×5 = 6×10 = 0 mod 15
6×1 = 6×6 = 6×11 = 6 mod 15
6×2 = 6×7 = 6×12 = 12 mod 15
6×3 = 6×8 = 6×13 = 3 mod 15
6×4 = 6×9 = 6×14 = 9 mod 15
Nijedan rezultat nije 1.
Zbog toga broj 6 nema multiplikativni inverz modulo 15.
Pored toga:
6 × 5 = 0 mod 15
a nula nije element početnog skupa, pa skup nije zatvoren.
Vratimo se Z(p)*.
Dijeljenje sa k možemo definisati kao množenje sa k⁻¹:
8/k = 8 × k⁻¹
Ako je k = 9 u Z(11)*:
8/9 = 8 × 9⁻¹ = 8 × 5 = 40 = 7 mod 11
Slično:
3/10 = 3 × 10⁻¹ = 3 × 10 = 30 = 8 mod 11
Neka je g element Z(p)*.
Kažemo da je g generator modulo p ako skup:
{g¹, g², …, g^(p−1)} mod p
sadrži sve elemente Z(p)*, samo eventualno drugim redoslijedom.
Na primjer, 3 je generator Z(7)*:
3¹ = 3 mod 7
3² = 2 mod 7
3³ = 6 mod 7
3⁴ = 4 mod 7
3⁵ = 5 mod 7
3⁶ = 1 mod 7
Dakle:
{3,3²,3³,3⁴,3⁵,3⁶} = {1,2,3,4,5,6} mod 7
Promjena redoslijeda elemenata naziva se permutacija.
Skup od k različitih generatora naziva se generator-tuple.
Na primjer:
{3,5}
je generator-tuple za Z(7)*, jer su i 3 i 5 generatori.
Svaki element Z(7)* može se predstaviti i kao stepen broja 3 i kao stepen broja 5:
1 = 3⁶ = 5⁶ mod 7
2 = 3² = 5⁴ mod 7
3 = 3¹ = 5⁵ mod 7
4 = 3⁴ = 5² mod 7
5 = 3⁵ = 5¹ mod 7
6 = 3³ = 5³ mod 7
Broj 2 nije generator modulo 7, jer njegovi stepeni daju samo:
{1,2,4}
To je podskup Z(7)*.
Kaže se da broj 2 generiše podgrupu G(3) modulo 7.
Oznaka G(3) znači da grupa ima tri elementa.
Broj 3 je najmanji stepen broja 2 koji daje 1 modulo 7:
2³ = 1 mod 7
G(3) je grupa zato što je zatvorena u odnosu na množenje i svaki njen element ima inverz.
Broj 4 je takođe generator:
{4,4²,4³} = {4,2,1} mod 7
Grupa koju generiše g ima red q modulo p ako je q najmanji pozitivan stepen za koji važi:
g^q = 1 mod p
Generatori 3 i 5 grupe Z(7)* imaju red 6.
Generatori 2 i 4 grupe G(3) imaju red 3.
Uopšteno, za prost broj q, gdje je:
1 < q < p
definišemo G(q) kao grupu prostog reda q modulo p ako neki generator g zadovoljava:
{g,g²,…,g^q} ⊂ Z(p)*
i:
g^q = 1 mod p
Stepeni veći od q samo ponavljaju iste elemente.
Ako:
g^q = 1 mod p
onda:
g^(q+1) = g mod p
g^(q+2) = g² mod p
i tako dalje.
Ako je g generator Z(p)*, onda ima red p−1.
FERMATOVA TEOREMA
Fermatova teorema kaže da za svaki prost broj p i broj k koji nije djeljiv sa p:
k^(p−1) = 1 mod p
Zbog toga za svaki k u Z(p)*:
k^(p−1) = 1 mod p
Na primjer, za Z(11)*:
1¹⁰ = 2¹⁰ = … = 10¹⁰ = 1 mod 11
To ne znači da svaki broj ima red p−1. Njegov red može biti manji.
Na primjer, broj 2 ima red 3 modulo 7:
2³ = 1 mod 7
ali naravno važi i:
2⁶ = 1 mod 7
što zahtijeva Fermatova teorema.
Iz ovoga slijedi da red q svakog elementa mora dijeliti p−1.
To je poznato kao Lagrangeova teorema.
EULEROVA TOTIJENTNA FUNKCIJA
Eulerova totijentna funkcija:
φ(n)
predstavlja broj pozitivnih cijelih brojeva manjih od n koji su relativno prosti sa n.
Ako je n = p prost broj:
φ(p) = p−1
Na primjer:
φ(7) = 6
jer su svi brojevi od 1 do 6 relativno prosti sa 7.
Za n = 4:
φ(4) = 2
jer su 1 i 3 relativno prosti sa 4.
Za n = 15:
φ(15) = 8
jer su:
1,2,4,7,8,11,13,14
relativno prosti sa 15.
Eulerova teorema kaže da za broj n i broj k relativno prost sa n:
k^φ(n) = 1 mod n
Za razliku od Fermatove teoreme, Eulerova teorema važi i za složene brojeve.
Na primjer:
2^φ(15) = 2⁸ = 1 mod 15
Ovu teoremu kasnije ćemo koristiti kod RSA sistema.
Još jedan rezultat teorije brojeva kaže da je, za prost p, broj generatora modulo p jednak:
φ(p−1)
Na primjer, broj generatora modulo 7 je:
φ(6) = 2
i to su upravo 3 i 5.
Za grupu prostog reda q broj generatora iznosi:
q−1
što znači da za veliki q postoji veliki broj generatora koje možemo odabrati.
DISKRETNI LOGARITMI
Diskretni logaritam možemo definisati u Z(p)* ili G(q).
Ako je g generator i:
y = gˣ mod p
onda je x diskretni logaritam y po osnovi g:
x = log_g(y) mod p
Na primjer:
2⁵ = 9 mod 23
pa je:
5 = log₂(9) mod 23
Ako je g generator G(q), tada:
g^q = 1
i q igra ulogu nule u eksponentima modulo q.
Zbog toga:
gˣ mod p = g^(x mod q) mod p
Ako imamo:
X = gˣ
i:
Y = gʸ
onda:
XY = g^(x+y)
dok:
Xʸ = g^(xy)
i:
Yˣ = g^(xy)
Poznavanje g^(x+y) ne daje nam g^(xy) bez poznavanja x ili y.
Ova razlika vodi direktno do Diffie-Hellman razmjene ključeva.
D. DIFFIE-HELLMAN I DISKRETNI LOGARITMI
Diffie-Hellman razmjenu ključeva osmislili su Whitfield Diffie i Martin Hellman 1976. godine.
Ona omogućava dvjema stranama da dogovore zajednički simetrični ključ preko nesigurnog komunikacionog kanala.
Osnovna ideja zasniva se na činjenici da je modularno stepenovanje relativno lako, dok je izračunavanje diskretnih logaritama veoma teško.
Diskretni logaritmi smatraju se primjerom jednosmjernih funkcija.
Jednosmjerna funkcija f(x) ima osobinu da je lako izračunati:
y = f(x)
ako znamo x, ali je teško izračunati x ako znamo samo y.
Za generator g grupe Z(p)* lako je izračunati:
y = gˣ mod p
ali je teško iz y pronaći x, pod uslovom da je p dovoljno velik.
Godine 1997. „dovoljno velik“ značilo je najmanje 768 bita, a poželjno 1024 bita.
Pretpostavimo sada da Alice i ja želimo privatno komunicirati.
Najprije moramo dogovoriti ključ kojim ćemo šifrovati poruke.
Diffie-Hellman omogućava da taj ključ izračunamo bez direktnog slanja samog ključa preko mreže.
TABELA 1: DIFFIE-HELLMAN DOGOVOR KLJUČA
Dogovaramo generator:
g = 7
i prost broj:
p = 23
Alice bira tajni broj:
x = 5
Ja biram:
y = 8
Alice računa:
X = 7⁵ mod 23 = 17
Ja računam:
Y = 7⁸ mod 23 = 12
Alice meni šalje 17, a ja njoj 12.
Alice zatim izračunava:
K = 12⁵ mod 23 = 18
Ja izračunavam:
K = 17⁸ mod 23 = 18
Dakle zajednički ključ je:
K = 18
Uopšteno:
Alice računa:
K = Yˣ = g^(yx) mod p
a druga strana:
K = Xʸ = g^(xy) mod p
Pošto je:
xy = yx
dobijamo isti ključ:
K = g^(xy) mod p
Treća strana koja vidi g, p, X i Y morala bi riješiti diskretni logaritam kako bi dobila x ili y.
Za dovoljno velike parametre to je računarski veoma teško.
E. RSA SISTEM SA JAVNIM KLJUČEM
RSA sistem dobio je ime po njegovim autorima:
Ron Rivest, Adi Shamir i Leonard Adleman.
RSA Data Security osnovana je 1982. godine.
RSA tehnologija korištena je u brojnim proizvodima, uključujući Microsoft Windows, Netscape Navigator, Quicken, Lotus Notes, Apple, Sun i Novell sisteme, kao i u finansijskim standardima poput SWIFT-a.
Kod RSA sistema šifrovanje i dešifrovanje odvijaju se podizanjem poruke M na određeni stepen modulo veliki broj n.
Prilikom stvaranja ključeva biraju se dva velika prosta broja:
p
i:
q
Njihov proizvod:
n = p × q
postaje modul.
Eulerova funkcija za n je:
φ(n) = (p−1)(q−1)
Zatim se biraju e i d tako da:
e × d = 1 mod φ(n)
odnosno:
ed = kφ(n) + 1
za neki cijeli broj k.
Javni ključ je:
(e,n)
a privatni:
(d,n)
Za odgovarajuće x važi:
(xᵉ)ᵈ = x mod n
Šifrovanje
C = Mᵉ mod n
Dešifrovanje
M = Cᵈ mod n
Digitalni potpis
Ako banka ima privatni ključ d, poruku M može potpisati:
S = Mᵈ mod n
Svako zatim može provjeriti potpis javnim ključem e:
Sᵉ = M mod n
TABELA 2: PRIMJER RSA SISTEMA
Izaberimo:
p = 11
q = 13
Tada:
n = 11 × 13 = 143
Eulerova funkcija:
φ(n) = 10 × 12 = 120
Izaberimo:
e = 7
Tražimo d tako da:
7d = 1 mod 120
Rješenje je:
d = 103
jer:
7 × 103 = 721 = 1 mod 120
Javni ključ:
(7,143)
Privatni ključ:
(103,143)
Ako je poruka:
M = 5
onda:
C = 5⁷ mod 143 = 47
Dešifrovanje:
47¹⁰³ mod 143 = 5
Sigurnost RSA sistema zavisi od težine faktorizacije velikog broja n na njegove proste faktore p i q.
Ako bi p i q bili poznati, privatni ključ d mogao bi se relativno lako izračunati iz javnog ključa e.
F. HASH FUNKCIJE I DIGITALNI POTPISI
Kada želimo potpisati veliku poruku ili dokument, nije praktično digitalno potpisivati cijeli sadržaj.
Kriptografija sa javnim ključem relativno je spora.
Zato se od poruke pravi sažetak poruke – message digest, odnosno niz fiksne dužine koji predstavlja originalnu poruku.
Ako poruka ima, na primjer, 50.000 bita, njen sažetak može imati samo 128 bita.
Potpisuje se taj sažetak, a ne cijela poruka.
Hash funkcija:
H(x)
preslikava poruku proizvoljne dužine M u vrijednost fiksne dužine:
h = H(M)
Vrijednost h naziva se hash vrijednost.
Message digest je jednostavno hash vrijednost određene poruke.
Ako hash ima 128 bita, postoji:
2¹²⁸
mogućih izlaznih vrijednosti.
Ako dvije različite poruke daju isti hash, to se naziva kolizija.
Dobra hash funkcija treba biti otporna na kolizije.
Ne postoji funkcija koja iz većeg prostora ulaza preslikava u manji prostor izlaza bez ikakvih kolizija, pa je preciznije govoriti o otpornosti na kolizije.
Dobra hash funkcija mora takođe biti jednosmjerna: iz hash vrijednosti ne bi smjelo biti praktično moguće rekonstruisati originalnu poruku.
Digitalni potpis radi ovako:
Najprije se izračuna:
h = H(M)
Zatim se h potpisuje privatnim ključem pošiljaoca:
Eₛₖ(h)
Poruka i potpisani hash šalju se primaocu.
Primalac pomoću javnog ključa dobija:
Dₚₖ(Eₛₖ(h)) = h
Istovremeno iz primljene poruke ponovo izračunava:
H(M)
Ako se vrijednosti podudaraju, potvrđena su dva svojstva:
poruku je potpisao vlasnik odgovarajućeg privatnog ključa,
i poruka nije izmijenjena.
Poznate hash funkcije su:
MD5
SHA-1
RIPEMD-128
RIPEMD-160
MD5 daje 128-bitni hash, a SHA-1 160-bitni.
Autor napominje da su već devedesetih postojale ozbiljne sumnje u otpornost MD5 na kolizije i da RSA nije preporučivao njegovu upotrebu za nove aplikacije koje zahtijevaju snažnu otpornost na kolizije.
G. SLIJEPI POTPISI – BLIND SIGNATURES
Pretpostavimo da klijent želi da Banka potpiše digitalni novčić sa serijskim brojem x, ali ne želi da Banka zna koji konkretni novčić potpisuje.
To se može postići slijepim potpisom.
Kod jednostavnog RSA primjera postupak izgleda ovako.
Klijent bira nasumični faktor zasljepljivanja:
r
i Banci šalje:
x × rᵉ mod n
gdje je (e,n) javni RSA ključ Banke.
Banka potpisuje zaslijepljeni broj privatnim ključem d:
(x × rᵉ)ᵈ
što daje:
r × xᵈ mod n
Banka vraća rezultat klijentu.
Klijent zatim uklanja faktor r:
(r × xᵈ)/r = xᵈ mod n
i dobija validno potpisani digitalni novčić.
Pošto je r slučajan, Banka ne može iz originalno primljenog zaslijepljenog broja odrediti x.
Kasnije, kada joj se novčić pojavi prilikom plaćanja, može provjeriti svoj potpis, ali ga ne može povezati sa određenim korisnikom kojem je novčić ranije izdala.
Potrošnja novčića postaje nepratljiva.
TABELA 3: PRIMJER SLIJEPOG POTPISA
Serijski broj novčića:
x = 8
Klijent bira:
r = 5
Javni ključ Banke:
(7,143)
Klijent računa:
8 × 5⁷ mod 143 = 90
Banka potpisuje 90 privatnim ključem:
d = 103
Klijent zatim uklanja faktor 5 i dobija:
8¹⁰³ mod 143
To je novčić sa serijskim brojem 8 potpisan privatnim ključem Banke.
Svako može provjeriti potpis javnim ključem.
Protokol slijepog potpisa objavio je David Chaum 1982. godine.
Postoje i uslovno slijepi potpisi, poznati kao restrictive blind signatures, koji mogu otkriti identitet vlasnika digitalnog novca ako isti novčić potroši više puta.
H. OTKRIVANJE DVOSTRUKOG TROŠENJA
Off-line sistem anonimnog digitalnog novca suočava se sa problemom da Banka i trgovac ne znaju identitet kupca ako on isti digitalni novčić pokušava potrošiti više puta.
Kod on-line sistema novčić se prije kupovine može provjeriti u bazi već potrošenih novčića.
Kod off-line sistema jedan pristup je da kupac prilikom podizanja novca ugradi određene informacije o svom identitetu.
Te informacije podijeljene su tako da jedan dio sam po sebi ne otkriva identitet, ali dva odgovarajuća dijela zajedno mogu.
Ako kupac isti novčić potroši dva puta, Banka dobija dva dijela i njegov identitet postaje poznat.
1. CUT-AND-CHOOSE
Kod metode cut-and-choose kupac stvara N parova brojeva koji su povezani sa digitalno potpisanim novčićem.
Svaki potpuni par omogućava identifikaciju kupca.
Prilikom plaćanja trgovac šalje nasumični niz od N bitova, na primjer:
10001011
Ako je određeni bit 0, kupac otkriva prvi broj odgovarajućeg para.
Ako je bit 1, otkriva drugi.
Ako isti novčić ponovo potroši, novi trgovac šalje novi nasumični izazov.
Gotovo sigurno će se najmanje jedan bit razlikovati, pa će Banka dobiti oba dijela određenog para i moći identifikovati kupca.
Problem ovog sistema je njegova sporost i neefikasnost zbog velike količine podataka.
Chaum–Fiat–Naor sistem iz 1990. koristi ovu tehniku.
2. ZERO-KNOWLEDGE DOKAZI I SCHNORROVI PROTOKOLI
Zero-knowledge dokaz omogućava da dokažete da nešto znate bez otkrivanja same informacije.
Zamislite sef sa vratima i kombinacijom koja se može ukucati sa obje strane.
Alice ne zna kombinaciju.
Da biste joj dokazali da je znate, dozvolite joj da vas zaključa unutra. Zatim sa unutrašnje strane ukucate kombinaciju, otvorite vrata i izađete.
Alice sada zna da poznajete kombinaciju, ali nije saznala samu kombinaciju.
To je zero-knowledge dokaz.
Jedan primjer je Schnorrov autentifikacioni protokol.
Pretpostavimo da kupac želi trgovcu dokazati da poznaje svoj tajni ključ x.
Kupac prvo bira slučajan broj w.
Trgovac šalje izazov c.
Kupac odgovara vrijednošću:
y = w + xc mod q
Međutim, pošto trgovac ne smije iz ovih podataka izračunati x, koristi se modularno stepenovanje.
Ako je:
a = gʷ
i:
h = gˣ
gdje je h javni ključ kupca, trgovac provjerava:
gʸ = a × hᶜ mod p
Kupac tako dokazuje da zna x, ali ga ne otkriva.
PRIMJER SCHNORROVE AUTENTIFIKACIJE
Izaberimo:
p = 23
q = 11
g = 2
Tajni ključ:
x = 9
Javni ključ:
h = 2⁹ mod 23 = 6
Kupac bira:
w = 3
i računa:
a = 2³ mod 23 = 8
Trgovac šalje izazov:
c = 5
Kupac računa:
y = 3 + 9×5 mod 11 = 4
Trgovac zatim provjerava:
gʸ = a × hᶜ mod p
Obje strane daju 16, pa trgovac prihvata da kupac poznaje x.
Schnorrov sistem potpisa ovom postupku dodaje hash funkciju.
Umjesto da trgovac bira izazov c, on se računa kao:
c = H(M,a)
Zatim:
y = w + xc mod q
Potpis predstavlja par:
(c,y)
Trgovac provjerava matematičku relaciju i ponovo računa hash.
Schnorrov potpis kasnije postaje važan dio Brandsovog anonimnog digitalnog novca.
I. PROBLEM REPREZENTACIJE
Diffie-Hellman i Schnorrovi potpisi zasnivaju se na težini izračunavanja diskretnih logaritama.
Problem reprezentacije proširuje ovu teškoću sa jednog diskretnog logaritma na skup povezanih vrijednosti.
Neka je:
h ∈ G(q)
i imamo generatore:
{g₁,…,gₖ}
Tražimo skup eksponenata:
{a₁,…,aₖ}
takav da:
g₁^a₁ × g₂^a₂ × … × gₖ^aₖ = h mod p
Skup:
{a₁,…,aₖ}
naziva se reprezentacija.
Na primjer, za G(11) u Z(23)* možemo tražiti:
2^a₁ × 3^a₂ = 13 mod 23
Jedno rješenje je:
a₁ = 2, a₂ = 2
jer:
2² × 3² = 4 × 9 = 36 = 13 mod 23
Drugo:
a₁ = 7, a₂ = 11
i tako dalje.
Ako reprezentacija ima k elemenata, postoji:
q^(k−1)
različitih reprezentacija istog h.
Ta osobina pruža dodatnu fleksibilnost prilikom konstrukcije anonimnih sistema digitalnog novca.
J. DOKAZIVANJE POZNAVANJA REPREZENTACIJE
Pretpostavimo da dokazivač P zna reprezentaciju:
h = g₁^a₁ × g₂^a₂ × … × gₖ^aₖ mod p
i želi verifikatoru V dokazati da zna:
{a₁,…,aₖ}
bez otkrivanja tih vrijednosti.
Postupak izgleda ovako.
Korak 1
P bira slučajne brojeve:
{w₁,…,wₖ}
i računa:
z = g₁^w₁ × g₂^w₂ × … × gₖ^wₖ mod p
Zatim šalje z verifikatoru.
Korak 2
V bira slučajni izazov:
c
i šalje ga P-u.
Korak 3
P računa:
rᵢ = aᵢ + c wᵢ mod q
za svaki i i šalje vrijednosti V-u.
Korak 4
V provjerava:
z × hᶜ
i poredi sa:
g₁^r₁ × g₂^r₂ × … × gₖ^rₖ mod p
Ako su vrijednosti jednake, prihvata dokaz da P poznaje reprezentaciju.
Pri tome V i dalje ne saznaje same vrijednosti aᵢ.
To je još jedan primjer zero-knowledge dokaza.
K. SERTIFIKACIONI AUTORITETI I DIGITALNI SERTIFIKATI
Odjeljenje za motorna vozila možemo posmatrati kao primjer sertifikacionog autoriteta.
Ono izdaje vozačku dozvolu koja povezuje fotografiju određene osobe sa njenim ličnim podacima.
Slično tome, digitalni sertifikat potvrđuje vezu između nečijeg javnog ključa i identiteta te osobe.
Digitalni sertifikat obično izdaje pouzdana treća strana koja se naziva:
Certification Authority – CA
odnosno sertifikacioni autoritet.
Primjer privatnog CA iz tog vremena bio je VeriSign, koji je pružao sertifikacione usluge za komercijalne web preglednike.
Kada Bob digitalno potpiše poruku svojim privatnim ključem, uz potpis može poslati i svoj sertifikat.
Primalac tada koristi Bobov javni ključ za provjeru potpisa, ali istovremeno koristi sertifikat kako bi dobio dodatnu sigurnost da javni ključ zaista pripada Bobu.
Drugim riječima:
digitalni potpis kaže:
„ovu poruku potpisao je vlasnik odgovarajućeg privatnog ključa“
dok sertifikat kaže:
„ovaj javni ključ zaista pripada Bobu“.
Sertifikacioni autoritet povezuje Bobov identitet sa njegovim javnim ključem i cijeli paket potpisuje svojim privatnim ključem.
Ako je tajni ključ CA:
sk-ca
a Bobov javni ključ:
pk-bob
onda CA pravi sertifikat:
E_sk-ca {Bobov identitet, pk-bob}
Sertifikat se provjerava javnim ključem CA:
D_pk-ca(E_sk-ca{Bobov identitet, pk-bob})
što daje:
{Bobov identitet, pk-bob}
Naravno, to samo pomjera pitanje povjerenja na viši nivo.
Ako CA tvrdi da određeni javni ključ pripada Bobu, kako znamo da javni ključ samog CA zaista pripada tom CA?
Zato nastaje lanac povjerenja.
Na vrhu se nalazi glavni sertifikacioni autoritet kojem svi vjeruju. On sertifikuje ključeve drugih sertifikacionih autoriteta, koji zatim sertifikuju druge, sve dok određeni CA na kraju ne potvrdi Bobov ključ.
Javni i privatni ključevi glavnih CA nazivaju se root keys – korijenski ključevi.
Privatni korijenski ključ može se radi sigurnosti podijeliti na više dijelova.
Na primjer, ključ može biti podijeljen na pet dijelova tako da su bilo koja dva dovoljna za njegovo rekonstruisanje.
To je analogno pravilu da za određenu veliku finansijsku transakciju moraju postojati dva potpisa.
Ovakav postupak naziva se:
secret sharing – dijeljenje tajne.
Digitalni sertifikati ne moraju služiti isključivo dokazivanju identiteta.
Sertifikat može, na primjer, potvrđivati Bobov limit potrošnje na kreditnoj kartici.
U širem smislu, digitalni sertifikat predstavlja digitalno potpisanu potvrdu određenih informacija ili prava.
X.509 DIGITALNI SERTIFIKATI
Jedan standardni format digitalnih sertifikata definisan je standardom:
ITU-T X.509
X.509 sertifikat može sadržavati sljedeća polja:
Verzija
Broj verzije X.509 specifikacije.
Verzija 1 objavljena je 1988.
Verzija 2 1993.
Verzija 3 predložena je 1994.
Serijski broj
Jedinstveni serijski broj sertifikata.
Identifikacija algoritma potpisa
Algoritam kojim će sertifikat biti potpisan.
Na primjer:
Digital Signature Algorithm – DSA
DSA koristi grupu prostog reda G(q) u Z(p)*, pa sertifikat mora sadržavati parametre p, q i generator g.
Naziv izdavaoca
Naziv sertifikacionog autoriteta koji izdaje sertifikat.
Period važenja
Vrijeme tokom kojeg je sertifikat važeći.
Ime subjekta ili korisnika
Osoba ili institucija kojoj se sertifikat izdaje.
Informacije o javnom ključu subjekta
Javni ključ osobe ili institucije.
Jedinstveni identifikator subjekta
Informacije koje povezuju konkretnu osobu ili instituciju sa njenim javnim ključem.
Na primjer:
račun XYZ123 u UBS-u, Bern.
Potpis prethodnih polja
Digitalni potpis sertifikacionog autoriteta nad svim prethodnim informacijama.
Standard X.509 podržavali su brojni sigurnosni protokoli poput:
S-HTTP
SSL
PEM
PKCS-7
a sertifikati verzije 3 koristili su se i u sistemu SET – Secure Electronic Transaction.
⸻
Objavljeno 10. oktobra 1997.
Autor: J. Orlin Grabbe
Originalni naslov: „Cryptography and Number Theory for Digital Cash“
Petar Miljić – Finansije za narod
👉 Znanjem protiv hajpa – uvijek sigurniji put!
🌐 Posjeti nas: https://kriptoentuzijasti.io
🐦 Prati nas na X-u: https://twitter.com/k_entuzijasti
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
