CRYSTALS–Dilithium

CRYSTALS–Dilithium postkvantni je algoritam digitalnog potpisa čija je težina utemeljena na težini pronalaženja najkraćih vektora u rešetkama (engl. lattice). Sama shema napravljena je po principu Fiat–Shamir with Aborts.

Matematička pozadina

Sve operacije s polinomima izvodit će se na prstenu polinoma . Taj prsten sadrži sve polinome oblika , za koje vrijedi da im je stupanj manji od , a koeficijenti manji od što se osigurava time da se zbrajanje i množenje koeficijenata odvija pod . Dakle:

Koristimo vrijednosti , .

predstavlja isti prsten polinoma kao , ali nema ograničenja na veličinu koeficijenata.

Maksimalni koeficijent polinoma je:

Gdje je i-ti koeficijent polinoma , a centrirani modulo za :

predstavlja skup svih elemenata iz prstena polinoma kojima je maksimalni koeficijent polinoma manji od :

predstavlja skup svih elemenata kao , ali bez onih koji imaju koeficijente jednake :

Vektori će se označavati masnim malim slovima, matrice masnim velikim slovima, polinomi ukošenim latiničnim slovima, a brojevi ukošenim grčkim slovima.

Fiat–Shamir with Aborts

GenerirajKljučeve():
      A ← Rqk×l
      (s1, s2) ← Sηl × Sηk
      t := As1 + s2
      pk := (A, t)
      sk := (A, t, s1, s2)
      vrati (pk , sk) 


Potpiši(sk, M):
      z := ⊥
      
      dok je z = ⊥:
            y ← ˜Sγ1l
            w := Ay
            w1 := HighBits(w, 2γ2)
            c ∈ Bτ := H(M ‖ w1)
            z := y + cs1

            ako je ‖z‖∞ ≥ γ1 – β ili ‖LowBits(Ay – cs2, 2γ2)‖∞ ≥ γ2 – β:
                 z := ⊥
      vrati σ = (z, c)


ProvjeriPotpis(pk, M, σ = (z, c)):
      w'1 := HighBits(Az – ct, 2γ2)
      
      ako je ‖z‖∞ < γ1 – β i c == H(μ ‖ w'1):
            vrati potpis je valjan
      inače:
            vrati potpis nije valjan
          

U funkciji GenerirajKljučeve(), koja ne prima nikakve argumente, prvo se stvori matrica A veličine k×l u čijoj je svakoj ćeliji polinom iz prstena polinoma R_q. Zatim se nasumično generiraju 2 vektora polinoma s₁ duljine l i s₂ duljine k, tako da su koeficijenti svih polinoma najviše η. Vektor polinoma t dobije se množenjem matrice A s vektorom polinoma s₁ i pribrajanjem vektora polinoma s₂. Javni ključ pk sastoji se od matrice A i vektora polinoma t, a privatni ključ sk sastoji se od matrice A, vektora polinoma t, vektora polinoma s₁ i vektora polinoma s₂. Funkcija vraća javni i privatni ključ.

Funkcija Potpiši(sk, M) kao ulazne argumente prima privatni ključ sk i poruku M. Vektor polinoma z postavi se na vrijednost ⊥ što predstavlja vrijednost none. Petlja se provodi dok je vektor polinoma z jednak ⊥. Vektor polinoma y duljine l nasumično se generira tako da su mu svi koeficijenti manji od γ₁. w je vektor polinoma jednak umnošku matrice polinoma A i vektora polinoma y. w₁ je vektor polinoma, koji se dobije uzimanjem samo visokih bitova svih koeficijenata svih polinoma vektora w. Koeficijenti se rastavljaju na više i niže bitove prema formuli w = w₁ · 2γ₂ + w₀, w₁ predstavlja više, a w₀ niže bitove, vrijedi |w₀| ≤ γ₂. c iz R_q je takav polinom da ima točno τ koeficijenata jednakih 1, dok su svi ostali jednaki 0. Dobije se primjenom hash funkcije nad konkatiniranom porukom M s vektorom polinoma w₁. Vektor polinoma z, koji predstavlja potencijalni digitalni potpis, računa se kao zbroj vektora polinoma y i umnoška polinoma c s vektorom polinoma s₁. Ako je najveći koefcijent polinoma vektora polinoma z veći ili jednak γ₁ – β ili su niski bitovi Ay – cs₂ veći ili jednaki γ₂ – β, vektor polinoma z postavlja se na početnu vrijednost ⊥ te se tako ponavlja petlja. Kada se pronađe vektor z i polinom c takvi da zadovolje uvjete vraća se potpis σ koji sadrži samo njih.

Za provjeru ispravnosti digitalnog potpisa koristi se funkcija ProvjeriPotpis(pk, M, σ = (z, c)) koja kao argumente prima javni ključ pk, poruku M i digitalni potpis σ. Vektor polinoma w'₁ računa se kao visoki bitovi od Az – ct.

Ukoliko je potpis ispravan vrijedi:
w'₁ = HighBits(Az − ct, 2γ₂) = HighBits(A(y + cs₁) – c(As₁ + s₂), 2γ₂) = HighBits(Ay – cs₂, 2γ₂) = HighBits(Ay) = HighBits(w) = w₁.

Ako je w'₁ jednak w₁ iz funkcije Potpiši(sk, M), hash koji daje konkatiniran uz M biti će jednak polinomu c. Uz to se provjerava i svojstvo ‖z‖_∞ < γ₁ – β, koje ima svaki vektor polinoma z koji se pojavi kao dio digitalnog potpisa na izlazu funkcije Potpiši(sk, M). Ako su ova dva uvjeta zadovoljena digitalni je potpis ispravan. Funkcija će kao izlaz dati podatak o ispravnosti.

Dilithium poboljšanja

Algoritam CRYSTALS–Dilithium na osnovni princip Fiat–Shamir with Aborts uvodi određena poboljšanja i optimizacije.

Oblik polinoma NTT

Zahvaljujući Kineskom teoremu o ostacima možemo podijeliti prsten polinoma na manje prstene polinoma koji u umnošku daju polinom jednak onom koji smo dijelili, istu stvar možemo i s polinomima unutar tog prstena. Pretvaranje polinoma u taj oblik naziva se NTT (eng. Number Theoretic Transform). Funkciju pretvaranja iz kanonskog u oblik NTT označavamo s NTT(), a funkciju za pretvorbu iz oblika NTT u kanonski oblik zovemo NTT^-1(). Polinomi u obliku NTT mogu se pomnožiti u vremenskoj složenosti O(n), a pretvorba u oblik NTT odvija se u vremenskoj složenosti O(log⁡n). Dakle, umjesto množenja polinoma u kanonskom obliku u vremenskoj složenosti O(n²), možemo ih pomnožiti u vremenskoj složenosti O(nlog⁡n).

Polinomi u obliku NTT biti će označeni kapicom.

Važne funkcije

SampleInBall(ρ):
      c := c0c1...c255 = 00...0
      za i := 256 - τ do 255
      j := broj iz skupa {0,1,...,i} odabran koristeći XOF funkciju
      s := broj iz skupa {0,1} odabran koristeći XOF funkciju
      ci := cj
      cj := (-1)s
      vrati c
            

ExpandA(ρ)

ExpandMask(ρ', κ)

CRH(δ)

Power2Roundq(r, d):
      r := r mod+q
      r0 := r mod±2d
      vrati ((r - r0)/2d, r0)

Decomposeq(r, α):
      r := r mod+q
      r0 := r mod±α
      ako je r − r0 = q – 1:
            r1 := 0
            r0 := r0 − 1
      inače:
            r1 := (r − r0)/α
      vrati (r1, r0)

HighBitsq(r, α):
      (r1, r0) := Decomposeq(r, α)
      vrati r1

LowBitsq(r, α):
      (r1, r0) := Decomposeq(r, α)
      vrati r0

MakeHintq(z, r, α):
      r1 := HighBitsq(r, α)
      v1 := HighBitsq(r + z, α)
      ako r1 == v1:
            vrati 0
      inače:
            vrati 1

UseHintq(h, r, α):
      m := (q - 1)/α
      (r1, r0) := Decomposeq(r, α)
      ako h = 1 i r0 > 0:
            vrati (r1 + 1) mod+m
      inače ako h = 1 and r0 ≤ 0:
            vrati (r1 − 1) mod+m
      inače:
            vrati r1

Važni parametri

U ovisnosti o NIST razini sigurnosti koriste se različite vrijednosti ključnih parametara.

Generiranje ključeva

GenerirajKljučeve():
      ζ ← {0, 1}256
      (ρ, ς, K) ∈ {0, 1}256×3 := H(ζ) 
      (s1, s2) ∈ Sηl × Sηk := H(ς)
      
      Â := ExpandA(ρ)
      t := NTT-1(Â · NTT(s1)) + s2 
      (t1, t0) := Power2Roundq(t, d)
      tr ∈ {0, 1}384 := CRH(ρ ‖ t1)
      
      pk := (ρ, t1)
      sk := (ρ, K, tr, s1, s2, t0)
      vrati (pk, sk)

Funkcija GenerirajKljučeve() na ulazu ne prima ništa.

Prvo se generira ζ, nasumični 256-bitni broj. Na temelju hasha od ζ se generiraju brojevi ρ, ς i K. H je funkcija hash SHAKE-256. Hashiranjem ς generiraju se vektori: s₁, duljine l i s₂, duljine k. Koeficijenti ovih vektora su polinomi iz S_η. Iz broja ρ generira se i privremeno sprema  (oblik NTT matrice A). Svako polje matrice A polinom je iz prstena polinoma R_q, a sama matrica veličine je k×l, dakle A ∈ R_q^k×l. Računa se vektor polinoma t koristeći pretvorbu NTT te se potom dijeli na više bitove t₁ i niže bitove t₀ funkcijom Power2Round_q(t, d).

Hash koji na ulazu prima konkatiniran broj ρ i t₁ (više bitove vektora t) na izlazu daje broj tr.

Javni ključ pk sastoji se od broja ρ i t₁ (viših bitova vektora t). Privatni ključ sk sastoji se od brojeva ρ, K i tr i vektora s₁, s₂ i t₀ (viših bitova vektora t).

Funkcija vraća javni i privatni ključ, sk i pk.

Potpisivanje

Potpiši(sk, M):
      Â := ExpandA(ρ)
      μ ∈ {0, 1}384 := CRH(tr ‖ M)
      κ := 0
      (z, h) := ⊥
      ρ' ∈ {0, 1}384 := CRH(K ‖ μ)	(ili ρ' ← {0, 1}384)
      
      ŝ1 := NTT(s1)
      ŝ2 := NTT(s2)
      t̂0 := NTT(t0)
      
      dok je (z, h) == ⊥:
            y ∈ ˜Sγ1l := ExpandMask(ρ', κ)
            w := NTT−1(Â · NTT(y))
            w1 := HighBitsq(w, 2γ2)
            ˜c ∈ {0, 1}256 := H(μ ‖ w1)
            ĉ := NTT(SampleInBall(˜c)) 
            z := y + NTT-1(ĉ · ŝ1)
            r0 := LowBitsq(w − NTT-1(ĉ · ŝ2), 2γ2)
      
            ako je ‖z‖∞ ≥ γ1 - β ili ‖r0‖∞ ≥ γ2 - β:
                  (z, h) := ⊥
            inače:
                  h := MakeHintq(−NTT-1(ĉ · t̂0), w − NTT-1(ĉ · ŝ2) + NTT-1(ĉ · t̂0), 2γ2)
                  ako je ‖NTT-1(ĉ · t̂0) ‖∞ ≥ γ2  ili  (broj jedinica u h) > ω: 
                        (z, h) := ⊥
            κ = κ + l
      
            vrati σ = (z, h, ˜c)

Funkcija Potpiši(sk, M) na ulazu prima tajni ključ sk i poruku M koja se potpisuje.

Iz broja ρ generira se i privremeno sprema  (oblik NTT matrice A). μ se generira kao 384-bitni broj iz hasha otpornog na kolizije (CRH) koji na ulazu prima konkatinirani broj tr iz tajnog ključa i poruku M. Broj κ postavlja se na 0, a par vektora (z, h) postavljaju se na vrijednost ⊥ (none/ništa). U slučaju determinističkog potpisivanja ρ' se generira kao 384-bitni broj iz hasha otpornog na kolizije (CRH) koji na ulazu prima konkatinirani broj K iz tajnog ključa i prethodno generirani broj μ. U slučaju nedeterminističkog potpisivanja ρ' se generira kao nasumični niz bitova.

Izračunaju se oblici NTT vektora polinoma s₁, s₂ i t₀.

Provodi se petlja dok je par vektora (z, h) jednak ⊥. Na temelju ρ' i κ generira se vektor polinoma duljine l, a svaki njegov polinom ima koeficijente manje od γ₁. Vektor polinoma w izračuna se kao umnožak matrice A i vektora y koristeći pretvorbu NTT. Vektor w₁ dobije se primjenjujući HighBits_q funkciju uz α = 2γ₂ na vektor w. ˜c, 256-bitni broj dobije se hashiranjem kontkatiniranog broja μ s vektorom polinoma w₁. Polinom c dobiva se funkcijom SampleInBall kojoj se kao ulazni argument prosljeđuje broj ˜c. Vektor polinoma z dobiva se sumiranjem vektora polinoma y i umnoška polinoma c s vektorom polinoma s₁. Množenje se provodi koristeći pretvorbe NTT. Vektor polinoma r₀ jednak je razlici funkciji nižih bitova razlike w - cs₂ (množenje pretvorbama NTT) uz α = 2γ₂.

Ako je najveći koeficijent polinoma u vektoru polinoma z veći ili jednak γ₁ – β ili je najveći koeficijent polinoma u vektoru polinoma r₀ veći ili jednak γ₂ – β, postavljamo par (z, h) na početnu vrijednost ⊥.

Inače stvaramo vektor hintova h funkcijom MakeHint^q za zbroj −ct₀ i w − cs₂ + ct₀. Ako je pak najveći koeficijent polinoma u vektoru polinoma umnoška ct₀ veći ili jednak γ₂ ili je broj jedinica u vektoru hintova h veći od ω, postavljamo par (z, h) na početnu vrijednost ⊥.

Na kraju svakog ponavljanja broju κ dodajemo broj l.

Kada se uspije stvoriti zadovoljavajući par (z, h), vraća se potpis σ koji se sastoji od vektora polinoma z, vektora h i broja ˜c.

Provjera potpisa

ProvjeriPotpis(pk, M, σ = (z, h, ˜c)):
      Â := ExpandA(ρ)
      μ ∈ {0, 1}384 := CRH(CRH(ρ ‖ t1) ‖ M)
      c := SampleInBall(˜c)
      w'1 := UseHintq(h, NTT-1(Â · NTT(z) – NTT(c) · NTT(t1 · 2d)), 2γ2)
      
      ako je ‖z‖∞ < γ1 – β i ˜c == H(μ ‖ w'1) i (broj jedinica u h) ≤ ω:
            vrati potpis je valjan
      inače:
            vrati potpis nije valjan

Iz broja ρ generira se i privremeno sprema Â. Broj μ generira se kao i u digitalnom potpisu iz konkatiniranacije broja tr (koji se izračunava iz ρ i t₁ kao u funkciji GenerirajKljučeve()) i poruke M. c se izračuna funkcijom SampleInBall iz ˜c. Iskorištava se vektor hintova h iz potpisa na razliku Az – ct₁ · 2^d funkcijom UseHint_q te se rezultat sprema kao w'₁. Kao i do sada množenje se odvija uz pretvorbe NTT.

Za vektor polinoma z i vektor hintova h provjeravaju se uvjeti iz funkcije Potpiši(sk, M), a izračunati broj w'₁ se provjerava preko hash funkcije iz čega se donosi odluka o ispravnosti potpisa.

Uvod

Program je namijenjen isprobavanju digitalnog potpisivanja i provjere digitalnog potpisa postkvantnim algoritmom CRYSTALS-Dilithium. Izvorni kod samog algoritma može se preuzeti na web-stranici NIST-a, korištena je preporučena referentna implementacija dilithium3. Osim digitalnog potpisa postoji dodatna funkcionalnost enkripcije.

Demonstracija

Program se može pokrenuti na Linuxu iz naredbenog retka pozicioniranjem unutar vršnog direktorija i pozivom naredbe: $ python main.py.

Početni prozor

Na početnom prozoru možemo odabrati jednu od dvije opcije pritiskanjem na gumb: digitalni potpis ili enkripcija.

Prozor za digitalni potpis

Na prozoru za digitalni potpis možemo unijeti proizvoljnu poruku u za to predviđenom okviru za unos, zatim možemo generirati par ključeva (javni i privatni) čijih će se prvih nekoliko bajtova prikazati na ekranu.

Nakon što smo generirali ključeve možemo generirati digitalni potpis na temelju privatnog ključa i poruke pritiskom na gumb „Generiraj digitalni potpis“.

Pritiskom na gumb „Provjeri digitalni potpis“ provjeriti će se digitalni potpis na temelju javnog ključa, poruke i samog digitalnog potpisa ispisat će se poruka „Ispravan digitalni potpis“ ili „Neispravan digitalni potpis“ ovisno o ispravnosti te trojke.

Pritiskom na gumbe s ikonom olovke pored javnog ključa, privatnog ključa i digitalnog potpisa otvorit će se prozor za pregled i izmjenu bajtnog zapisa u heksadekadskom formatu. Može se izmijeniti i spremiti (samo ako se broj bajtova i format ne narušava) pritiskom na gumb „Spremi“ ili odustati od izmjena i izaći pritiskom na gumb „Izađi“.

Prozor za enkripciju

Ponašanje je vrlo slično kao na prozoru za digitalni potpis, može se upisati poruka, generirati par ključeva, ali umjesto potpisa, kriptira se poruka, a umjesto provjere potpisa je dekripcija poruke. Pritiskom na gumb sa znakom upitnika otvara se prozor za pregled bajtnog zapisa kriptirane poruke u heksadekadskom formatu.

Implementacija

Kao prvi korak potrebno je generirati dijeljene biblioteke libpqcrystals_aes256ctr_ref.so, libpqcrystals_fips202_ref.so i libpqcrystals_dilithium3_ref.so pozivom naredbe $ make shared iz izvornog koda CRYSTALS-Dilithiuma. Zatim je potrebno generirati dodatnu dijeljenu biblioteku randombytes.so naredbom $ cc -fPIC -shared -o randombytes.so randombytes.c.

Dijeljene biblioteke su unesene kroz python datoteku dilithium.py u obliku DLL-ova.

Napravljene su funkcije koje tipove podataka bliske pythonu pretvaraju u one bliske jeziku C i pozivaju funkcije dijeljenih biblioteka.
U datoteci main.py nalazi se kod potreban za grafičko sučelje programa i barata se s python tipovima podataka koji se prosljeđuju funkcijama iz dilithium.py kako bi se dobili željeni rezultati.

Literatura

• Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler and Damien Stehlé. (2020) CRYSTALS-Dilithium: Algorithm Specifications and Supporting Documentation. 3rd round (https://pq-crystals.org/dilithium/data/dilithium-submission-nist-round3.zip)
• Amber Sprenkels. (2020) The Kyber/Dilithium NTT (https://electricdusk.com/ntt.html)