FALCON

Shema potpisa temelji se na GPV(Gentry, Peikert i Vaikuntanathan) radnom okviru. Instanciramo okvir koristeći NTRU rešetke s pomoću takozvanog “brzog Fourierovog uzorkivača”. Temeljna poteškoća je rješavanje problema kratkih cijelih brojeva (SIS) preko NTRU rešetki, za što ne postoji znani učinkoviti algoritam, čak ni uz pomoć kvantnih računala.

Pregled

Glavni element u FALCONu su polinomi stupnja n s cijelim koeficijentima. Stupanj n je, uobičajeno, potencija broja 2 (uglavnom, 512 ili 1024). Izračuni se rade po modulu monoma istog stupnja (označavamo s φ, koji je uvijek oblika φ=xⁿ+1). Unutar algoritma, neki polinomi interpretiraju se kao vektori, a neki kao matrice koje određuju rešetku. Stoga, FALCON možemo uglavnom izražavati kroz operacije nad polinomima, čak i kad radimo s matricama koje određuju rešetku.

Ključevi

Privatni ključ

Privatni ključ je osnova za rešetku dimenzije 2n, s parametrima:.
gdje su f, g, F i G kratki integralni polinomi po modulu φ, također, polinom f je invertibilan. Moraju biti zadovoljene jednadžbe:

• h = f/g mod φ mod q
• fG - gF = q mod φ (NTRU jednadžba)

F i G se mogu izračunavati dinamički, ali je to skupo, stoga je bar očekivano spremanje F-a, uz f i g, a G izračunavamo učinkovito. Uz navedene polinome, iz privatnog ključa računamo (dinamično, ili ih spremamo uz f, g i F):

• FFT (Fast Fourier Transformation) reprezentaciju f, g, F i G-a , predstavljenih kao matricu:

• FALCON stablo T – binarno stablo sa sljedećim pravilima:
  • stablo visine 0 ima samo jedan čvor čija je vrijednost realni σ > 0
  • stablo visine κ posjeduje sljedeća svojstva:
    • vrijednost korijena, T.value jest polinom ℓ ∈ ℚ[x]/(xⁿ + 1) gdje je n = 2^κ
    • njegova lijeva i desna djeca, su FALCON stable visine κ - 1

Brza Fourierova transformacija (FFT) i Teorija transformacije brojeva (NTT)

Cijepanje i spajanje

ϕ je ciklotomski polinom, stoga ga možemo zapisati kao ϕ(x) = ∏_k∈Z×m (x − ζ^k), m = 2n, a ζ je proizvoljan primitivni m-ti korijen od 1
(npr. ζ = exp( 2iπ/m )). Neka je ϕ’ takav da vrijedi ϕ(x) = ϕ ′ (x²) (npr. ϕ(x) = xⁿ + 1 i ϕ ′ (x) = x^n/2+1).

Funkcija splitfft

Funkcija rastava FFT(f), f se može jedinstveno rastaviti kao f(x) = (x²) + xf₁(x²) Taj rastav možemo zapisati i kao: f₀ = ∑_{0≤ 1 ≤(n/2)}a_2i+1xⁱ
Rastavili smo f na parne i neparne koeficijente, stoga možemo jednostavno napisati split(f) = (f₀, f₁)

Funkcija mergefft - inverzna funkcija funkciji splitfft

Hashiranje

Prvi korak za potpisivanje poruke ili njezinu verifikaciju sastoji se od hashiranja poruke. U našem slučaju, poruka mora biti hashirana u polinomskom obliku. Za taj postupak koristit ćemo metodu XOF tj. odobrenu hash funkciju s proširenim izlazom, točnije SHAKE-256, za sve sigurnosne razine.

• SHAKE-256 -Init () označava inicijalizaciju SHAKE-256 konteksta hashiranja
• SHAKE-256 -Inject (ctx, str) označava ubacivanje podatka kontekst hashiranja ctx
• SHAKE-256 -Extract (ctx, b) označava ekstrakciju b pseudoslučajnih bitova iz hashing iz hashing konteksta ctx

Generiranje para ključeva

Generiranje para ključeva možemo razdvojiti u dva koraka:

1. Rješavanje NTRU jednadžbe tj. generiranje f i g (lako), te F i G (teško)
2. Izračun FALCON stabla

Generiranje polinoma f, g, F i G

1. Generiramo nasumično polinome f i g. Zatim za njih provjeravamo jesu li prikladni za svrhu algoritma. To radimo na načine:
• Linija 7 osigurava da se h može izračunati iz f i g. To je istina samo onda NTT(f) ne sadrži koeficijente koji su 0.
• polinomi f, g, F, G moraju dozvoliti generiranje kratkih potpisa, To vrijedi za relaciju 𝛾 ≤ 1.17 √ q
2. Izračunavamo F i G, tako da f, g, F i G prolaze provjeru. To radimo s algoritmom NTRUSolve

Reduciranje rješenja za vektore u, v reduciramo u uzimajući u obzir v radeći transformaciju u ← u - ⌊⟨u,v⟩/⟨v,v⟩⌉v. Za naš slučaj u zamjenjujemo s (F, G), a v zamjenjujemo s (f, g).

Izračun FALCON stabla

Tajni ključ sk je oblika sk=(B ̂,T). Postupak za izračun LDL stabla sastoji se od:

1. Izračunamo LDL dekompoziciju G: napišemo G=L ×D× L^*, gdje je L donja trokutasta matrica sa “1” na dijagonalama i D dijagonalnom matricom. Lspremamo u T.value koja je vrijednost korijena od T. L je oblika stoga samo trebamo spremiti L₁₀∈ℚ[x]/(ϕ).
2. Onda koristimo splitting operator za rastav svake dijagonalne matrice D u manje matrice. Za svaki dijagonalni element rastavljen u novu matricu Gi, rekurzivno izračunavamo LDL stablo kao u 1. koraku i spremamo rezultat u lijevo ili desno dijete korijena T (tj. T.leftchild i T.rightchild)

Generiranje potpisa

Iz poruke m generiramo hash vrijednost c i salt r, koristimo znanje o tajnom ključu f, g, F, G za izračunavanje dvije kratke vrijednosti s₁, s₂ tako da vrijedi s₁ + s₂h = c mod q

Fast Fourier Sampling

Za algoritam BaseSampler() koristimo vrijednost RCDT iz tablice 1.
Stupci predstavljaju vrijednosti:

• distribucija vjerojatnosti pdt[i]
• kumulativna distribucija vjerojatnosti cdt[i] = ∑ _j<i pdt[j]
• obrnuta kumulativna distribucija RCDT[i] = ∑ _j>i pdt[j] = 2⁷² - cdt[i]

Vrijedi relacija χ(i)=2^(-72)∙pdt[i].
Za bilo koju logičku propoziciju P vrijedi,
UniformBits(k) uzorkuje z uniformno u rasponu{0, 1, …, 2^k-1}.
Koristimo notaciju (>>) i (&) kako bi prikazali logički pomak u desno i operator AND.

Neka je C lista 64bitnih brojeva (u hex zapisu):
C =[0x00000004741183A3, 0x00000036548CFC06, 0x0000024FDCBF140A, 0x0000171D939DE045,
0x0000D00CF58F6F84, 0x000680681CF796E3, 0x002D82D8305B0FEA, 0x011111110E066FD0,
0x0555555555070F00, 0x155555555581FF00, 0x400000000002B400, 0x7FFFFFFFFFFF4800,
0x8000000000000000].
Neka je polinom f∈R takav da vrijedi: f(x)= 2^-63∙∑¹²₀C[i]∙x^12-i
f(-x) je dobra aproksimacija za exp(-x) u granicama [0, ln(2)]. Stoga koristimo algoritam ApproxExp kako bi približno izračunali vrijednost 2⁶³>∙ccs∙exp⁡(-x) za x u određenom rasponu. Međuvrijednosti varijabli y, z u ApproxExp su uvijek u rasponu {0, … , 2⁶³ - 1}, sa jednom iznimkom: ako je x = 0, onda na kraju for petlje vrijedi y = 2⁶³. Iz tog razloga, pogodno je prikazivati x, y koristeći, npr. C tip uint64_t.

Za dane ulaze x,ccs ≥0, BerExp (Algoritam 14) vraća jedan bit 1 sa vjerojatnošću ≈ccs∙exp⁡(-x)

Testovi s poznatim odgovorima ili Known Answer Tests (KAT). Kako bi pravilno implementirali Sampler Z i njegove podrutine, koristimo Tablicu 2. Svaki redak daje četvorku takvu da pri zamjeni internih poziva za UniformBits() čitajući bitove iz randombytes (koji se ponaša kao nasumični bytestring): SamplerZ(µ, σ′ ) → z. Za čitljivost, tablica razdvaja randombytes za svaku iteraciju SamplerZ-a. Na primjer, redak 1, SamplerZ iterira dva puta prije terminiranja:

Pri svakoj iteraciji, prvih 9 nasumičnih bajtova koristi BaseSampler, idući koristi redak 5, dok zadnji koristi BerExp. Imajte na umu da BerExp ima vjerojatnost 1/28 za korištenje jednog nasumičnog bajta; ovo je rijetko, ali se događa. To možemo vidjeti u retku 9 tablice 2, koji sadrži jedan takav primjer gdje koristi 2 nasumična bajta.

Provjera potpisa

Proces provjere potpisa je puno jednostavniji od generiranja para ključeva i generiranje potpisa. Za javni ključ pk = h, poruku m,
potpis sig = (r, s) i granicu β², prilikom provjere koristimo pk kako bi provjerili valjanost potpisa sig za poruku m prema sljedećim pravilima:

1. Vrijednost r (tzv. “salt”) i poruka m su konkatenirani u string (r||m) koji je ) koji je hashiran u polinom c ∈ℤ[x]/(ϕ) prema funkciji HashToPoint (Algoritam 3)
2. s se dekodira (dekompresira) u polinom s₂ ∈ ℤ[x]/(ϕ), koristeći funkciju Decompress (Algoritam 18)
3. Izračunavamo vrijednost s₁ = c - s₂ h mod q
4. Ako vrijedi ||(s₁, s₂)||² ≤ ⌊β²⌋ , onda je vrijednost potpisa valjan, inače se odbacuje.

Formati za kodiranje

Sažimanje Gaussiana

U FALCON-u, potpis se sastoji od polinoma s∈ℤ[x]/(ϕ) čiji su koeficijenti distribuirani oko 0 prema Gaussovoj diskretnoj distribuciji standardne devijacije σ≈1.55√q≪q. Naivno kodiranje s zahtijevalo bi otprilike ⌈log₂q⌉∙deg(ϕ) bitova, što je daleko od optimalnog za komunikacijsku složenost.
Opis procedure sažimanja jest:

1. Za svaki koeficijent si,sažeta poruka stri definira se kao:
   
   1. prvi bit od str_i jest predznak s_i
   2. idućih 7 bitova str_i su 7 najmanje značajnih bitova |s_i|
   3. zadnji bitovi str_i su kodirani od najznačajnijih bitova |s_i| koristeći unarno (Huffmanovo) kodiranje.
      Ako vrijedi ⌊|s_i|/2⁷⌋ = k, onda vrijedi 0^k1
2. Sažeta poruka s je konkatenirani string s←(str₀||str₁||…||str_n-1)
3. str se nadopunjuje nulama do fiksne duljine slen

Potpisi

FALCON potpis sastoji se od dva stringa r i s. Salt r mora biti poznat prije početka hashiranja poruke, dok vrijednost s može biti verificirana tek nakon što je cijela poruka procesirana. Ipak, ovdje definiramo kodiranje koje uključuje r i s.
Prvi okret je zaglavlje sljedećeg formata (bitovi s lijeva značajniji): 0 c c 1 n n n n

• • bitovi cc su 01 ili 10 za određivanje metode kodiranja za s. Kodiranje 01 koristi Algoritam 17, dok se za 01 koristi alternativno nekompresirano kodiranje u kojem se svaki koeficijent za s kodira fiksnim brojem bitova.
• bitovi nnnn kodiraju vrijednost l takav da je FALCON stupanj n = 2^ℓ,ℓ∈[0,10]

Nakon okteta zaglavlja slijedi nonce string r (40 okteta), a zatim kodiranje samog s-a.

Potpisi se normalno proširuju s nulama do propisane duljine (sbytelen). Verifikatori mogu podržavati neproširene potpise, koji nemaju fiksnu veličinu, ali su (u prosjeku) nešto kraći nego prošireni potpisi. Djelomično proširivanje nije valjano: ako potpis ima oktete proširenja, onda svi moraju biti jednaki nuli, i ukupna duljima mora biti jednaka sbytelen.

Pri korištenju nekompresiranog formata kodiranja (cc je 10 u zaglavlju), svi elementi od s kodiraju se s točno 12 bitova (signed big-endian, koristi se dvojni komplement za negativne brojeve; valjani raspon je -2047 do +2047). Ovaj format daje veće potpise i služi za neuobičajene situacije u kojima vrijednosti potpisa i potpisana poruka su tajni: nekompresiran potpis može biti dekodiran i kodiran u konstantnom vremenu bez curenja podataka.

Uvod

Ovdje možete preuzeti dokumentaciju algoritma, izvorni kod, implementaciju u C jeziku i Pythonu (koju sam koristio za lakšu implementaciju, radi grafičkog sučelja). Oprez, pratite istaknute upute za rad s python verzijom, koju možete pronaći u datoteci README.md.

Implementacija

Kako bi mogli koristiti postojeću implementaciju moramo koristiti vanjsku knjižnicu Crypto.Hash, tj. iz nje SHAKE256. Upute za korištenje, kao i za instalaciju možete pogledati ovdje. Također, trebat će vam datoteka main.py koju sam napisao i koju možete dohvatiti ovdje, i koju trebate pohraniti u isti direktorij kao i prethodno pohranjenu implementaciju. Po potrebi, morat ćete instalirati NumPy, a upute možete pronaći ovdje.

Demonstracija

Python program pokreće se iz direktorija u kojemu se nalaze datoteke main.py i falcon.py sljedećom naredbom: python3 main.py

Otvara se prozor:

Pritiskom na dio prozora u kojemu piše "DIGITALNI POTPIS" otvara se sljedeći prozor -> u polje "Poruka" upisuje se željena poruka za koju će se generirati digitalni potpis na osnovu generiranih ključeva.

Poruka o ispravnosti digitalnog potpisa prikazuje se u doljnjem prozoru. Pritiskom na gumb olovčice u polju "Digitalni potpis" moguće je ručno promijeniti vrijednosti navedenog polja. Ukoliko se neka od tih vrijednosti promjeni ručno, provjera digitalnog potpisa biti će potencijalno neispravna.

Kao što možete primjetiti, promjena na 7. oktetu iz “a” u “1” rezultirala je neispravnim potpisom.

Dok je promjena na prvom oktetu iz “3” u “a” rezultirala ispravnim potpisom. To je očekivano ponašanje algoritma, objašnjenje je u algoritmu 16 pod korakom 6 (obratite pažnju na ispis konzole).

Funkcije

Pomoćne fukncije koje koristimo za generiranje para ključeva, potpisa i njegovu provjeru.

Test

Kako bi provjerili ispravnost rada algoritma potrebno je usporediti izlaz iz algoritma s unaprijed određenim ulaznim vektorima (KAT). U tu svrhu koristite ćemo makefile, kojeg pokrećemo naredbom make test.

Nedostatci

Delikatna implementacija, potrebno netrivijalno razumijevanje matematičkih alata što je njegova najveća mana.

Također, koristi floating-point aritmetiku sa 53 bitnom preciznošću. što ne predstavlja poteškoću za softversku implementaciju, ali može biti veliki nedostatak pri ugrađivanju na ograničene uređaje.

Prednosti

Glavna prednost FALCON algoritma je njegova kompaktnosti, i izrađen je poglavito vodeći računa o tom kriteriju.
Provjera ispravnosti potpisa je izrazito brza, ali čak i algoritam za potpisivanje može izvršiti 1000 potpisivanja na umjereno jakom računalu.
Algoritam je modularan pa je moguće NTRU rešetke po potrebi zamijeniti drugim tipom rešetke ako je potrebno, isto tako možemo za uzorkovanje koristiti nešto drugo umjesto Fast Fourier Sampling-a.
Potpisivanje sa oporavkom poruke i oporavkom ključa, te jednostavna provjera ispravnosti potpisa.