O projektu Detalji
Classic McEliece CRYSTALS-KYBER NTRU SABER BIKE FrodoKEM HQC NTRU Prime SIKE
Preuzimanja Reference
Classic McEliece CRYSTALS-KYBER NTRU SABER BIKE FrodoKEM HQC NTRU Prime SIKE

NTRU

Općenito o algoritmu

NTRU je prvi kriptosustav koji nije baziran na faktorizaciji velikih brojeva ili problemu diskretnih logaritama, koristi se kriptografijom baziranom na polinomijalnim prstenima koja se može opisati i rešetkama. Njegova sigurnost se dijelom oslanja na (eksperimentalno promatranoj) činjenic da je za većinu rešetaka iznimno teško pronaći kratke vektore. Za originalan razvoj algoritma, 1996 godine, zaslužni su Jeffrey Hoffstein, Jill Pipher, i Joseph H. Silverman. Ime NTRU daje nam naslutit na koji način kriptosustav radi. NTRU je kratica za eng. N-th degree Truncated polynomial Ring Units. Operacije šifriranja su bazirane nad objektima u kvocijentnom polinomijalnom prstenu. Algoritam se hvali svojom brzinom i djelotvornosti.


Parametri


Primjer procedure šifriranja

1) Stvaranje ključeva

Prvi korak: Biraju se dva mala polinoma f i g unutar kvocijentnog prstena polinoma. Odabrani polinomi bi trebali biti tajni i njihov inverz mora biti postojan.

Drugi korak: traženje inverza polinoma f modul q (koji označavamo sa fq) i inverza f modul p (koje označavamo sa fp).

Treći korak: računanje javnog ključa

Privatni ključ: par polinoma (f, fp)

Javni ključ: h = p * ((fq * g) mod q)

Primjer:

1. f(x) = x^6−x^4+x^3+x^2−1 (privatno) i g(x) = x^6+x^4−x^2−x.

2. fq(x) = f(x)^ −1 (mod q) = 8x^6 + 26x^5 + 31x^4 + 21x^3 + 40x^2 + 2x + 37 (mod 41).

fp(x) = f(x)^ −1 (mod p) = x^6 + 2x^5 + x^3 + x^2 + x + 1 (mod 3) - privatni ključ

3.h(x) = p * fq*g(mod q) = 20x^6 + 40x^5 + 2x^4 + 38x^3 + 8x^2 + 26x + 30 (mod 41) (javni ključ)

2) Šifriranje

Prvi korak: poruka se pretvara u polinom koji označavamo sa m, koeficijenti tog polinoma su koeficijent modul p gdje je p između -p/2 i p/2

Drugi korak: Nasumično se bira još jedan mali polinom r

Treći korak: Šifrirana poruka se računa na sljedeći način: e = r * h + m (modul q)

Primjer:

m(x) = −x^5 + x^3 + x^2 − x + 1 (Poruka koju želimo poslati)

r(x) = x^6 − x^5 + x − 1 (Nasumičan mali polinom)

e(x) ≡ 31x^6+19x^5+4x^4+2x^3+40x^2+3x+25 (mod 41) (Šifrirana poruka)

3) Dešifriranje

Prvi korak: Koristeći privatni polinom f izračunava se polinom a = f * e (modul q). Koeficijenti polinoma a moraju biti u intervalu –q/2 do q/2 uključivo.

Drugi korak: Izračunava se polinom b = a (modul p)

Treći korak: Orginalna poruka se dobiva na sljedeći način: c = fb * b (modul p)

Primjer:

a ≡ x^6 + 10x^5 + 33x^4 + 40x^3 + 40x^2 + x + 40 (mod 41).

b = a(mod p) = x^6 + 10x^5 − 8x^4 − x^3 − x^2 + x − 1 (mod 3)

c = fp(x)*b(x) ≡2x^5 + x^3 + x^2 + 2x + 1 (mod 3).

m(x) =−x^5 + x^3 +x^2 − x + 1. pri redukciji modulo 3 koeficjenti su iz intervala [-1,1]


Prednosti i ograničenja

  1. Otpornost na napade kvantnim računalima (Trenutno ne postoji poznat napad koristeći kvantna računala na kriptosustav NTRU)
  2. Brzina i učinkovito šifriranje i dešifriranje, u softverskim i hardverskim implementacijama
  3. Mogućnost korištenja jednokratnih ključeva zbog iznimne brzine stvaranja istih (“jeftino” je stvoriti ključ)
  4. NTRU za potrebe šifriranja koristi iznimno malo memorije, njegova implementacija je pogodna za uređaje sa limitiranim resursima poput mobilnih uređaja ili pametnih kartica.

Reference