OTS i WOTS+

One time signature (OTS) je tip sheme digitalnog potpisa u kojem se isti privatni ključ može sigurno koristiti samo jedanput. Jednom kada se potpiše neka poruka s parom ključeva, ti isti ključevi efektivno postaju javni i više ih ne možemo koristiti za daljnje potpisivanje. Winternitz one time signature (WOTS+) vrsta je sheme jednokratnog digitalnog potpisa temeljenog na rasprišvanju koji se koristi u sklopu SPHINCS+ algoritma.

Generiranje ključeva

Definiramo Winternitzov parametar w kao element iz skupa {4, 16, 256}. Njega koristimo u funkciji pretvorbe poruke zapisane u bitovima u niz brojeva u rasponu [0, w – 1] na sljedeći način:

• poruka za kodiranje je duljine m bitova
• poruku rastavimo na l segmenata duljine log₂(w) bitova ( l = m / log₂(w) )
• svaki segment duljine log₂(w) bitova zasebno interpretiramo kao jedan broj u navedenom rasponu

    Primjer:
            w = 4
            M = 37(10) = 100101(2) 		(big endian)
            m = len(M) = 6
            -------------------
            l = m / log2(w) = 6 / log2(4) = 3
            M = 10 | 01 | 01
            → 2 | 1 | 1
              

Ukoliko imamo poruku duljine m bitova, za nju generiramo l tajnih ključeva, gdje je l = m / log₂(w). Na temelju l tajnih ključeva generiramo njihove javne ključeve tako da svaki od l tajnih ključeva uzastopce hashiramo nekim od algoritama rasprišivanja (w – 1) puta. To nam daje l javnih ključeva.

    Primjer:
            skn => privatni ključ indeksa n
            pkn => javni ključ indeksa n
            H(skn) => primjena algoritma raspršivanja na privatni ključ indeksa n
          --------------------------------------------------------------------------------------------
            sk0 → H(sk0) → H(H(sk0)) → H(H(H(sk0))) → … → H^(w-1)(sk0) = pk0
            sk1 → H(sk1) → H(H(sk1)) → H(H(H(sk1))) → … → H^(w-1)(sk1) = pk1
            sk2 → H(sk2) → H(H(sk2)) → H(H(H(sk2))) → … → H^(w-1)(sk2) = pk2
            .	.	.	.	.	        …		.
            .	.	.	.	.	        …		.
            .	.	.	.	.	        …		.
            sk(l-1) → H(sk(l-1)) → H(H(sk(l-1))) → H(H(H(sk(l-1)))) → … → H^(w-1)(sk(l-1)) = pk(l-1)
              

Cjelokupni privatni ključ dobivamo spajanjem svih skn ključeva SK = (sk0 || sk1 || sk2 || … || sk(l-1)), a po istom principu dobivamo i javni ključ PK = (pk0 || pk1 || pk2 || … || pk(l-1)) gdje je || operator nadovezivanja.

Potpisivanje

Ukoliko imamo poruku message, njezin sažetak (message digest) M duljine m bitova dobiven korištenjem nekog algoritma raspršivanja (npr. Harak, SHA256), primjenom gore navedene funkcije pretvorbe dobitit ćemo l segmenata poruke. Koristeći algoritam opisan u odjeljku Generiranje ključeva dobivamo l segmenata privatnog i l segmenata javnog ključa. Primjenom funkcije pretvorbe pomoću Winternitzovog parametra dobivamo i l segmenata sažetka poruke M. Potpis generiramo tako da svaki od l segmenata sažetka poruke duljine log₂(w) bitova zasebno interpretiramo kao jedan broj u rasponu [0, w – 1]. Taj broj uz indeks segmenta određuje koliko ćemo puta nad privatnim ključem istog indeksa primjeniti funkciju raspršivanja (funkcija MORA biti ista kao i ona upotrebljena za generiranje javnog ključa i mora biti javno poznata). Tako dobivene vrijednosti dn nadovezujemo te one zajedno čine potpis poruke D = (d0 || d1 || d2 || … || d(l-1)).

    Primjer:
          poruka → H(poruka) = M = 1001110110
          m = len(M) = 10
          w = 4
          l = m / log2(w) = 10 / log2(4) = 5
          ------------------------------------------------
          sk0 → H(sk0) → H(H(sk0)) → H(H(H(sk0))) = pk0
          sk1 → H(sk1) → H(H(sk1)) → H(H(H(sk1))) = pk1
          sk2 → H(sk2) → H(H(sk2)) → H(H(H(sk2))) = pk2
          sk3 → H(sk3) → H(H(sk3)) → H(H(H(sk3))) = pk3
          sk4 → H(sk4) → H(H(sk4)) → H(H(H(sk4))) = pk4

          M = (10 | 01 | 11 | 01 | 00) → (2 | 1 | 3 | 1 | 0)

          Segmenti poruke M i njihov indeks određuje koliko puta primjenjujemo funkciju adresiranja na 	odgovarajući privatni ključ:
          
          M[0] = 2
          sk0 → H(sk0) → H(H(sk0)) = d0

          M[1] = 1
          sk1 → H(sk1) = d1


          M[2] = 3
          sk2 → H(sk2) → H(H(sk2)) → H(H(H(sk2))) = d2

          M[3] = 1
          sk3 → H(sk3) = d3

          M[4] = 0
          sk4 = d4

          Digitalni potpis D = ( d0 || d1 || d2 || d3 || d4 ).
              

Verifikacija

Podaci koji su poznati verifikatoru su: w, D, PK i poruka. Na temelju poruke, verifikator računa sažetak poruke koristeći isti algoritam rasprišivanja kao i potpisatelj. Time generira sažetak poruke M duljine m bitova. Segmenti poruke M i njihovi indeksi određuju koliko je puta primjenjena funkcija adresiranja na odgovarajući privatni ključ. Znajući to, za svaki indeks možemo odrediti koliko puta trebamo odgovarajući segment digitalnog potpisa hashirati kako bi dobili odgovarajući segment javnog ključa. Uzimajući primjer iz prošlog odjeljka:

    Primjer:

            Digitalni potpis D = ( d0 || d1 || d2 || d3 || d4 )
            poruka → H(poruka) = M = 1001110110
            m = len(M) = 10
            w = 4
            (w – 1) = 3
            l = m / log2(w) = 10 / log2(4) = 5
            PK = ( pk0 || pk1 || pk2 || pk3 || pk4 )
            ------------------------------------------------
            M = (10 | 01 | 11 | 01 | 00) → (2 | 1 | 3 | 1 | 0)

            M[0] = 2
            3 – 2 = 1		// segment d0 potrebno je hashirati još jednom kako bi dobili segment javnog ključa
            ---------------
            d0 → H(d0)  = pk0’

            M[1] = 1
            3 – 1 = 2		// segment d1 potrebno je hashirati još dvaput kako bi dobili segment javnog ključa
            --------------
            d1 → H(d1) → H(H(d1)) = pk1’


            M[2] = 3
            3 – 3 = 0		// segment d2 jednak je segmentu javnog ključa
            --------------
            d2 = pk2’

            M[3] = 1
            3 – 1 = 2		// segment d3 potrebno je hashirati još dvaput kako bi dobili segment javnog ključa
            --------------
            d3 → H(d3) → H(H(d3)) = pk3’


            M[4] = 0
            3 – 0 = 3		// segment d4 potrebno je hashirati još triput kako bi dobili segment javnog ključa
            --------------
            d4 = sk4 →H(d4) → H(H(d4)) → H(H(H(d4))) = pk4’
              

Dobivene javne ključeve nadovežemo i dobijemo PK’ = ( pk0’ || pk1’ || pk2’ || pk3’ || pk4’ ). Ukoliko se PK’ poklapa s PK, digitalni potpis je ispravan, inače je neispravan.
Ova se metoda za jedan par ključeva može upotrijebiti samo jedanput (OTS) jer ukoliko znamo dn za vrijednost poruke M[n] = z, znamo i vrijednost dn za sve vrijednosti poruke M[n] = z’ gdje vrijedi z’ >= z.

Uvod

Zbog nepraktičnosti korištenja jednog para ključeva za potpisivanje samo jedne poruke, Merkle je 1970. razvio shemu digitalnog potpisa temeljenih na OTS pomoću koje se isti par ključeva može koristiti za veći broj poruka, iako konačan.

Generiranje ključeva

XMSS (Extended Merkle Signature Scheme) novija je implementacija originalne Merklove sheme. Shema se sastoji od stabla u kojemu su listovi parovi WOTS+ privatnih i javnih ključeva, a najgornji korijen stabla je potpisateljev javni ključ. Ostali čvorovi (uključujući i sam korijen stabla) su izlazi hashrianja njihove djece unutar stabla. Na temelju privatnog seed-a (koji je zapravo privatni ključ) generiraju se svi ostali privatni ključevi u listovima stabla. Iz tih privatnih ključeva u listovim generiraju se javni ključevi za listove po WOTS+ algoritmu opisanom u odjeljku Generiranje ključeva. Zatim se iz parova javnih ključeva listova koristeći odabrani algoritam raspršivanja, određuju čvorovi stabla. Postupak hashiranja djece kako bi se dobio roditelj nastavlja se sve do vrha stabla (korijena odnosno javnog ključa). Tako dobiveni korijen javno je dostupan i on je generirani javni ključ.

Potpisivanje

Kako bi se potpisala poruka potrebno je odabrati jedan od listova, ali se isti list smije koristiti samo jedanput. Iz odabranog lista pomoću algoritma potpisivanja poruke u odjeljku Generiranje ključeva WOTS+ algoritmom dobiva se WOTS+ digitalni potpis poruke. WOTS+ digitalni potpis poruke, korišteni javni ključ lista, javni ključ susjednog lista, vrijednost čvora susjednog roditelja, vrijednost čvora susjednog roditelja roditelja … do korijena čini krajnji digitalni potpis. Ovime se stvara autentifikacijski put XMSS stabla.

    Primjer:
              
              Koristeći pk0 i sk0 generiramo WOTS+ digitalni potpis d. Konačan digitalni potpis D definiramo 
	      D = (d || pk0 || pk1 || N4 || N2).
              

Verifikacija

Iz dobivenog digitalnog potpisa D, javnog ključa potpisatelja te korištenog algoritma rasprišivanja, digitalni potpis se verificira tako da se iz njega pročita digitalni potpis WOTS+ algoritma i verificira po algoritmu opisanom u odjeljku Verifikacija. Ako se tako izračunati javni ključ pk’ ne slaže s javnim ključem dobivenim u potpisu D, potpis nije valjan. Dalje se iz dobivenog javnog ključa i javnog ključa susjednog lista hashiranjem računa vrijednost njihovog roditelja. Dobivena vrijednost se uz vrijednost čvora susjednog roditelja ponovo hashira kako bi se dobila vrijednost njihovog roditelja i tako dalje, sve do korijena stabla. Dobivena vrijednost korijena PK’ uspoređuje se s poznatim javnim ključem PK. Ako su PK’ i PK isti, potpis je valjan, ako su različiti, potpis nije valjan.

    Primjer:
              
              D = (d || pk0 || pk1 || N4 || N2)

              Iz d se računa pk0’ i uspoređuje s pk0. Ako nisu isti potpis nije valjan.
              Iz pk0 i pk1 računa se N3’=H(pk0, pk1).
              Iz N3’ i N4 računa se N1’=H(N3’,N4).
              Iz N1’ i N2 računa se PK’=H(N1’,N2).
              Ako su PK’ I PK isti, digitalni potpis je valjan, inače nije valjan. 
              

Uvod

HT (The Hypertree) vrsta je certifikacijskog stabla XMSS stabala. Ovakva arhitektura omogućuje brže potpisivanje i verifikaciju većeg broja poruka. HT je stablo od više slojeva XMSS stabala. Stabla na vrhu i u sredini služe za potpisivanje javnih ključeva (korijena) XMSS stabala njihove djece. Stabla na najnižem sloju služe potpisivanju poruke, odnosno potpisivanju FORS javnih ključeva u slučaju SPHINCS+.

T<i> označava javni ključ XMSS stabla indeksa i. Vidimo da se stablo indeksa i koristi za potpisivanje stabala s indeksima (2*i) i (2*i + 1). T1 javni je ključ HT. Kao privatni ključ HT koristimo seed koji nam služi kako bi deterministički mogli generirati sve privatne ključeve svih XMSS stabala unutar HT strukture. Na ovaj način ne moramo pohraniti cijelu strukturu HT, nego možemo izračunati samo potrebna XMSS stabla za potpisivanje određene poruke.

Potpisivanje

Za sažetak poruke, i dovoljno veliku HT strukturu (broj listova je dovoljno velik, tako da je vjerojatnost slučajnog odabira već iskorištenog lista zanemariva) slučajnim odabirom izabire se list XMSS-a najnižeg sloja HT. Sažetak se potpisuje XMSS strukturom te se dobiva javni ključ XMSS najnižeg sloja HT. Dobiveni javni ključ tog XMSS stabla hashira se i potpisuje XMSS stablom roditelja. Navedeni postupak nastavlja se sve do najgornjeg XMSS stabla. Dobiveni korijen ujedno je i javni ključ potpisatelja. Ukupan potpis sastoji se od svih autentifikacijskih puteva svih korištenih XMSS, od najnižeg sloja do najvišeg.

Verifikacija

Za dobiveni potpis računaju se javni ključevi korištenih XMSS od dna prema vrhu. Kreće se sa izračunatim sažetkom poruke, za njega i pripadni autentifikacijski put računa se javni ključ prvog korištenog XMSS. Za tako dobiveni javni ključ ponovo se izračuna sažetak, te se računa javni ključ sljedećeg XMSS pomoću pripadnog autentifikacijskog puta dobivenog u potpisu. Postupak se nastavlja sve do posljednjeg XMSS. Ako je izračunati javni ključ korijena jednak javnom ključu potpisatelja, potpis je valjan, a u suprotnom je nevaljan.

Uvod

HT se ne koristi unutar SPHINCS+ kako bi se potpisala sama poruka, nego kako bi se potpisali javni ključevi FORS instanci. FORS (Forest Of Random Subsets) je shema digitalnog potpisa, FTS (few-times signature), u kojoj se isti privatni ključ može koristi više od jednom.

Struktura

FORS instanca sastoji se od k binarnih hash stabala, svako stablo od t listova, te hasha T koji se dobije hashiranjem svih korijena od k binarnih stabala. Svaki list predstavlja jedan privatni ključ. Vrijednosti privatnih ključeva generiraju se iz seed-a, koji je ujedno i privatni ključ same FORS instance.

Potpisivanje

Sažetak poruke, M, podijeli se na k segmenata, svaki duljine log₂(t) bitova. Svaki segment interpretira se kao zasebna dekadska vrijednost, koja za odgovorajuće binarno hash stablo kodira list, odnosno privatni ključ tog stabla. Potpis čine svi autentifikacijski putevi svih binarnih hash stabala.

    Primjer:
              FORS instanca:
              
              k = 3
              t = 4
              M = 19(10) = 010011(2)
              ------------------------------------------------
              M = (01 |00 | 11) = (1 | 0 | 3)

              M[0] = 1
              k0[M[0]] = k0[1] = sk0,1
              ----------------
              M[1] = 0
              k1[M[1]] = k1[0] = sk1,0
              ----------------
              M[2] = 3
              k2[M[2]] = k2[3] = sk2,3

              Potpis D = (sk0,1 || sk0,0 || H2 || sk1,0 || sk1,1 || H4 || sk2,3 || sk2,2 || H5)
              

Verifikacija

FORS se ne koristi za verifikaciju potpisa, već samo za generiranje potpisa iz kojega se zatim može dobiti javni ključ T’ korištene FORS instance. T’ se dobiva na isti način kao i kod XMSS, uzastopnim hashiranjem dobivenih autentifikacijskih puteva sve do korijena.

Ključevi

Privatni ključ sastoji se od seed-a (SK.seed) koji se koristi za generiranje svih ostalih privatnih ključeva svih korištenih XMSS i FORS instanci. Privatni ključ sadrži i dio koji služi za determinističko generiranje vrijednosti randomizacije slučajnog sažetka poruke (SK.prf). Privatnom ključu se pridodaje javni ključ.
Javni se ključ također sastoji od dva dijela; javnog ključa HT strukture (PK.root) i seed-a (PK.seed).

Potpisivanje

Na poruku se prvo dodaje pseudo-slučajna vrijednost R, te se nad tako dobivenom porukom generira sažetak poruke M. Na temelju izračunatog sažetka poruke M, izabire se indeks FORS instance. Izabrana FORS instanca koristi se za potpisivanje sažetka M. Dalje se dobiveni korijen FORS instance potpisuje HT strukturom. Ukupan potpis sadrži pseudo-slučajnu vrijednost R, autentifikacijski put FORS instance, kao i autentifikacijski put HT strukture.

Verifikacija

Iz dobivenog potpisa uzima se pseudo-slučajna vrijednost R, na temelju R i poruke računa se njen sažetak. Iz sažetka i dobivenog autentifikacijskog puta računa se javni ključ FORS instance, a iz izračunatog ključa i autentifikacijksog puta HT strukture računa se javni ključ PK’. Ukoliko je PK’ jednak PK, digitalan potpis je valjan, u suprotnome je nevaljan.

Pomoćne funkcije

unsigned long long crypto_sign_secretkeybytes(void);
-> Vraća duljinu privatnog ključa u oktetima.
unsigned long long crypto_sign_publickeybytes(void);
-> Vraća duljinu javnog ključa u oktetima.
unsigned long long crypto_sign_bytes(void);
-> Vraća duljinu potpisa u oktetima.
unsigned long long crypto_sign_seedbytes(void);
-> Vraća duljinu seed-a potrebnog za generiranje ključeva u oktetima

Generiranje ključeva

int crypto_sign_seed_keypair(unsigned char *pk, unsigned char *sk, const unsigned char *seed);
-> *pk = pokazivač na javni ključ, *sk = pokazivač na privatni ključ, *seed = pokazivač na seed
-> Funckija generira privatni i javni ključ koristeći dani seed.
int crypto_sign_keypair( unsigned char *pk, unsigned char *sk);
-> *pk = pokazivač na javni ključ, *sk = pokazivač na privatni ključ
-> Funkcija generira privatni i javni ključ.

Generiranje potpisa

int crypto_sign_signature(uint8_t *sig, size_t *siglen, const uint8_t *m, size_t mlen, const uint8_t *sk);
-> *sig = pokazivač na potpis, *siglen = pokazivač na duljinu potpisa, *m = pokazivač na poruku, mlen = duljina poruke u oktetima, *sk = pokazivač na privatni ključ
-> Funkcija na temelju poruke m, te privatnog ključa sk generira digitalni potpis i sprema ga u sig.
int crypto_sign(unsigned char *sm, unsigned long long *smlen, const unsigned char *m, unsigned long long mlen, const unsigned char *sk);
-> sm = pokazivač na potpis + poruku, *smlen = pokazivač na duljinu potpisa + poruke, *m = pokazivač na poruku, mlen = duljina poruke u oktetima, *sk = pokazivač na privatni ključ
-> Funkcija na temelju poruke m, te privatnog ključa sk generira digitalni potpis te ga zajedno s porukom spremu u sm

Provjera potpisa

int crypto_sign_verify(const uint8_t *sig, size_t siglen, const uint8_t *m, size_t mlen, const uint8_t *pk);
-> *sig = pokazivač na potpis, siglen = duljina potpisa u oktetima, *m = pokazivač na poruku, mlen = duljina poruke u oktetima, *pk = pokazivač na javni ključeva
-> Ukoliko je potpis valjan funkcija vraća 0, inače vrijednost različitu od 0
int crypto_sign_open(unsigned char *m, unsigned long long *mlen, const unsigned char *sm, unsigned long long smlen, const unsigned char *pk);
-> *m = pokazivač na poruku, *mlen = pokazivač na duljinu poruke u oktetima, *sm = pokazivač na potpis + pouku, smlen = duljina poruke + potpisa u oktetima, *pk = pokazivač na javni ključ
-> Ukoliko je potpis valjan funkcija vraća 0, inače vrijednost različitu od 0