NTRUEncrypt - NTRUEncrypt

NTRUEncrypt Kryptosystem klucz publiczny , znany również jako algorytmu szyfrowania NTRU , jest NTRU kratowe oparte alternatywa dla RSA i krzywych eliptycznych kryptografii (ECC) i opiera się na najkrótszym problemu wektora w kratę (który nie jest uznany za łamliwy za pomocą komputery kwantowe ).

Opiera się na domniemanej trudności rozkładania pewnych wielomianów w obciętym pierścieniu wielomianowym na iloraz dwóch wielomianów o bardzo małych współczynnikach. Złamanie kryptosystemu jest silnie związane, choć nie równoważne, z algorytmicznym problemem redukcji sieci w niektórych sieciach . Staranny dobór parametrów jest niezbędny, aby udaremnić niektóre opublikowane ataki.

Ponieważ zarówno szyfrowanie, jak i deszyfrowanie wykorzystują tylko proste mnożenie wielomianowe, operacje te są bardzo szybkie w porównaniu z innymi schematami szyfrowania asymetrycznego, takimi jak RSA, ElGamal i kryptografia krzywych eliptycznych . Jednak NTRUEncrypt nie przeszedł jeszcze porównywalnej analizy kryptograficznej we wdrożonej formie.

Powiązanym algorytmem jest algorytm podpisu cyfrowego NTRUSign .

W szczególności operacje NTRU są oparte na obiektach w obciętym pierścieniu wielomianowym z mnożeniem splotu, a wszystkie wielomiany w pierścieniu mają współczynniki całkowite i stopień co najwyżej N -1: ${\ Displaystyle \ R = \ mathbb {Z} [X] / (X ^ {N}-1)}$

${\ Displaystyle {\ textbf {a}} = a_ {0}+ a_ {1} X + a_ {2} X ^ {2} + \ cdots + a_ {N-2} X ^ {N-2} + a_ {N-1}X^{N-1}}$

NTRU jest w rzeczywistości sparametryzowaną rodziną kryptosystemów; każdy system jest określony przez trzy parametry całkowite ( N , p , q ), które reprezentują maksymalny stopień dla wszystkich wielomianów w obciętym pierścieniu R , odpowiednio mały moduł i duży moduł, gdzie zakłada się, że N jest liczbą pierwszą , q jest zawsze większe niż p , a p i q są względnie pierwsze ; oraz cztery zestawy wielomianów i (wielomianowa część klucza prywatnego, wielomian do generowania klucza publicznego, odpowiednio komunikat i wartość oślepiająca), wszystkie co najwyżej stopnia . ${\ Displaystyle \ N-1}$${\ Displaystyle \ {\ mathcal {l}} _ {f}, {\ mathcal {l}} _ {g}, {\ mathcal {l}} _ {m}}$${\ Displaystyle \ {\ Mathcal {L}} _ {R}}$${\ Displaystyle \ N-1}$

Historia

Kryptosystem klucza publicznego NTRUEncrypt jest stosunkowo nowym kryptosystemem. Pierwsza wersja systemu, nazwana po prostu NTRU, została opracowana około 1996 roku przez trzech matematyków ( Jeffrey Hoffstein , Jill Pipher i Joseph H. Silverman ). W 1996 roku ci matematycy wraz z Danielem Liemanem założyli NTRU Cryptosystems, Inc. i otrzymali patent (obecnie wygasły) na kryptosystem.

W ciągu ostatnich dziesięciu lat ludzie pracowali nad ulepszeniem kryptosystemu. Od pierwszej prezentacji kryptosystemu wprowadzono pewne zmiany mające na celu poprawę zarówno wydajności systemu, jak i jego bezpieczeństwa. Większość ulepszeń wydajności koncentrowała się na przyspieszeniu procesu. Do 2005 r. można znaleźć literaturę opisującą niepowodzenia deszyfrowania NTRUEncrypt. Jeśli chodzi o bezpieczeństwo, od pierwszej wersji NTRUEncrypt wprowadzono nowe parametry, które wydają się bezpieczne dla wszystkich obecnie znanych ataków i rozsądnego wzrostu mocy obliczeniowej.

Teraz system jest w pełni zaakceptowany zgodnie ze standardami IEEE P1363 zgodnie ze specyfikacjami dla opartej na sieci kryptografii klucza publicznego ( IEEE P1363.1 ). Ze względu na szybkość kryptosystemu klucza publicznego NTRUEncrypt (patrz http://bench.cr.yp.to, aby uzyskać wyniki testów porównawczych) i niskie zużycie pamięci (patrz poniżej ), można go używać w aplikacjach takich jak urządzenia mobilne i Smart- karty . W kwietniu 2011 r. NTRUEncrypt został zaakceptowany jako standard X9.98 do użytku w branży usług finansowych.

Generowanie klucza publicznego

Wysłanie tajnej wiadomości od Alicji do Boba wymaga wygenerowania klucza publicznego i prywatnego. Klucz publiczny jest znany zarówno Alicji, jak i Bobowi, a klucz prywatny jest znany tylko Bobowi. Do wygenerowania pary kluczy wymagane są dwa wielomiany f i g , o co najwyżej stopniu i współczynnikach {-1,0,1}. Można je traktować jako reprezentacje klas reszt wielomianów modulo w R . Wielomian musi spełniać dodatkowe wymaganie, że istnieją odwrotności modulo q i modulo p (obliczone przy użyciu algorytmu Euklidesa ), co oznacza, że i muszą być spełnione . Więc kiedy wybrane f nie jest odwracalne, Bob musi wrócić i spróbować innego f . ${\ Displaystyle \ N-1}$${\ Displaystyle \ X ^ {N} -1}$${\ Displaystyle {\ textbf {f}} \ w L_ {f}}$${\ Displaystyle \ {\ textbf {f}} \ cdot {\ textbf {f}} _ {p} = 1 {\ pmod {p}}}$${\ Displaystyle \ {\ textbf {f}} \ cdot {\ textbf {f}} _ {q} = 1 {\ pmod {q}}}$

Zarówno f, jak i (i ) są kluczami prywatnymi Boba. Klucz publiczny h jest generowany obliczając ilość ${\ Displaystyle \ \ mathbf {f} _ {p}}$${\displaystyle g}$

${\displaystyle {\textbf {h}}=p{\textbf {f}}_{q}\cdot {\textbf {g}}{\pmod {q}}.}$

Przykład : W tym przykładzie parametry ( N , p , q ) będą miały wartości N = 11 , p = 3 i q = 32 , a zatem wielomiany f i g mają co najwyżej stopień 10. Parametry systemowe ( N , p , q ) są znane wszystkim. Wielomiany są wybierane losowo, więc załóżmy, że są reprezentowane przez

${\ Displaystyle {\ textbf {f}} = -1 + X + X ^ {2} - X ^ {4} + X ^ {6} + X ^ {9} -X ^ {10}}$

${\ Displaystyle {\ textbf {g}} = -1 + X ^ {2} + X ^ {3} + X ^ {5} -X ^ {8} -X ^ {10}}$

Wykorzystując algorytm euklidesowy oblicza się odwrotność f modulo p i modulo q .

${\ Displaystyle {\ textbf {f}} _ {p} = 1 + 2 X + 2 X ^ {3} + 2 X ^ {4} + X ^ {5} + 2 X ^ {7} + X ^ {8} + 2 X ^{9}{\pmod {3}}}$

${\ Displaystyle {\ textbf {f}} _ {q} = 5 + 9 X + 6 X ^ {2} + 16 X ^ {3} + 4 X ^ {4} + 15 X ^ {5} + 16 X ^ {6} + 22 X ^{7}+20X^{8}+18X^{9}+30X^{10}{\pmod {32}}}$

Który tworzy klucz publiczny h (znany zarówno Alicji, jak i Bobowi) obliczający produkt

${\ Displaystyle {\ textbf {h}} = p {\ textbf {f}} _ {q} \ cdot {\ textbf {g}} {\ pmod {32}} = 8-7X-10X ^ {2}- 12X^{3}+12X^{4}-8X^{5}+15X^{6}-13X^{7}+12X^{8}-13X^{9}+16X^{10}{\pmod {32}}}$

Szyfrowanie

Alicja, która chce wysłać tajną wiadomość do Boba, umieszcza swoją wiadomość w postaci wielomianu m ze współczynnikami w . W nowoczesnych zastosowaniach szyfrowania wielomian wiadomości może być tłumaczony w postaci binarnej lub trójskładnikowej. Po utworzeniu wielomianu wiadomości Alicja losowo wybiera wielomian r o małych współczynnikach (nieograniczonych do zbioru {-1,0,1}), który ma zaciemniać wiadomość. ${\displaystyle [-p/2,p/2]}$

Za pomocą klucza publicznego Boba h zaszyfrowana wiadomość e jest obliczana:

${\displaystyle {\textbf {e}}={\textbf {r}}\cdot {\textbf {h}}+{\textbf {m}}{\pmod {q}}}$

Ten zaszyfrowany tekst ukrywa wiadomości Alicji i może być bezpiecznie wysłany do Boba.

Przykład : Załóżmy, że Alicja chce wysłać wiadomość, którą można zapisać jako wielomian

${\ Displaystyle {\ textbf {m}} = -1 + X ^ {3}-X ^ {4}-X ^ {8} + X ^ {9} + X ^ {10}}$

oraz że losowo wybrana „wartość zaślepiająca” może być wyrażona jako

${\ Displaystyle {\ textbf {R}} = -1 + X ^ {2} + X ^ {3} + X ^ {4}-X ^ {5} - X ^ {7}}$

Zaszyfrowany tekst e reprezentujący jej zaszyfrowaną wiadomość do Boba będzie wyglądał tak:

${\ Displaystyle {\ textbf {e}} = {\ textbf {r}} \ cdot {\ textbf {h}} + {\ textbf {m}} {\ pmod {32}} = 14 + 11 X + 26 X ^ { 2}+24X^{3}+14X^{4}+16X^{5}+30X^{6}+7X^{7}+25X^{8}+6X^{9}+19X^{10} {\pmod {32}}}$

Deszyfrowanie

Każdy, kto zna r, może obliczyć komunikat m przez obliczenie e - rh ; więc r nie może być ujawnione przez Alicję. Oprócz publicznie dostępnych informacji Bob zna swój własny klucz prywatny. Oto jak może uzyskać m : Najpierw mnoży zaszyfrowaną wiadomość e i część swojego klucza prywatnego f

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

Po przepisaniu wielomianów równanie to w rzeczywistości reprezentuje następujące obliczenia:

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {q}}}$

${\ Displaystyle {\ textbf {a}} = {\ textbf {f}} \ cdot ({\ textbf {r}} \ cdot {\ textbf {h}} + {\ textbf {m}}) {\ pmod { Q}}}$

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot ({\textbf {r}}\cdot p{\textbf {f}}_ {q}\cdot {\textbf {g} }+{\textbf {m}}){\pmod {q}}}$

${\displaystyle {\textbf {a}}=p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}{\pmod {q }}}$

Zamiast wybierania współczynników między 0 i q - 1 są wybrane w przedziale [- Q / 2, Q / 2], aby zapobiec oryginalna wiadomość nie może być poprawnie odzyskać od Alicja wybiera współrzędne jej komunikatów m w przedział [- p /2, p /2]. Oznacza to, że wszystkie współczynniki leżą już w przedziale [- q /2, q /2], ponieważ wielomiany r , g , f i m oraz prime p mają współczynniki, które są małe w porównaniu z q . Oznacza to, że wszystkie współczynniki pozostają niezmienione podczas redukcji modulo q i że oryginalna wiadomość może zostać poprawnie odzyskana. ${\displaystyle \ p{\textbf {r}}\cdot {\textbf {g}}+{\textbf {f}}\cdot {\textbf {m}}}$

Następnym krokiem będzie obliczać się modulo p :

${\displaystyle {\textbf {b}}={\textbf {a}}{\pmod {p}}={\textbf {f}}\cdot {\textbf {m}}{\pmod {p}}}$

ponieważ . ${\ Displaystyle \ p {\ textbf {r}} \ cdot {\ textbf {g}} {\ pmod {p}} = 0}$

Wiedząc, że b Bob może użyć drugiej części swojego klucza prywatnego do odzyskania wiadomości Alicji przez pomnożenie b i${\ Displaystyle \ \ lewo ({\ textbf {f}} _ {p} \ po prawej)}$${\ Displaystyle \ {\ textbf {f}} _ {p}}$

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_ {p}\cdot {\textbf {f }}\cdot {\textbf {m}}{\pmod {p}}}$

${\ Displaystyle {\ textbf {c}} = {\ textbf {m}} {\ pmod {p}}}$

ponieważ nieruchomość była wymagana dla . ${\ Displaystyle \ {\ textbf {f}} \ cdot {\ textbf {f}} _ {p} = 1 {\ pmod {p}}}$${\ Displaystyle \ {\ textbf {f}} _ {p}}$

Przykład : zaszyfrowana wiadomość e od Alicji do Boba jest mnożona przez wielomian f

${\displaystyle {\textbf {a}}={\textbf {f}}\cdot {\textbf {e}}{\pmod {32}}=3-7X-10X^{2}-11X^{3} +10X^{4}+7X^{5}+6X^{6}+7X^{7}+5X^{8}-3X^{9}-7X^{10}{\pmod {32}}, }$

gdzie Bob używa przedziału [- q /2, q /2] zamiast przedziału [0, q - 1] dla współczynników wielomianu a, aby zapobiec temu, że oryginalna wiadomość może nie zostać poprawnie odzyskana.

Zmniejszenie współczynników a mod p Wyniki w

${\ Displaystyle {\ textbf {b}} = {\ textbf {a}} {\ pmod {3}} = -XX ^ {2} + X ^ {3} + X ^ {4} + X ^ {5} +X^{7}-X^{8}-X^{10}{\pmod {3}}}$

co równa się . ${\ Displaystyle \ {\ textbf {b}} = {\ textbf {f}} \ cdot {\ textbf {m}} {\ pmod {3}}}$

W ostatnim kroku wynik jest mnożony przez klucz prywatny Boba, aby otrzymać oryginalną wiadomość m${\ Displaystyle \ {\ textbf {f}} _ {p}}$

${\displaystyle {\textbf {c}}={\textbf {f}}_{p}\cdot {\textbf {b}}={\textbf {f}}_ {p}\cdot {\textbf {f }}\cdot {\textbf {m}}{\pmod {3}}={\textbf {m}}{\pmod {3}}}$

${\ Displaystyle {\ textbf {c}} = -1 + X ^ {3}-X ^ {4}-X ^ {8} + X ^ {9} + X ^ {10}}$

To rzeczywiście jest oryginalna wiadomość, którą Alicja wysłała do Boba!

Ataki

Od czasu propozycji NTRU wprowadzono kilka ataków na system kryptograficzny klucza publicznego NTRUEncrypt. Większość ataków skupia się na całkowitym włamaniu poprzez znalezienie tajnego klucza f zamiast tylko na odzyskaniu wiadomości m . Jeśli wiadomo, że f ma bardzo niewiele niezerowych współczynników, Eve może z powodzeniem przeprowadzić atak brute force , próbując wszystkich wartości f . Kiedy Ewa chce wiedzieć, czy f ´ jest kluczem tajnym, po prostu oblicza . Jeśli ma małe współczynniki, może to być tajny klucz f , a Ewa może sprawdzić, czy f ' jest tajnym kluczem, używając go do odszyfrowania wiadomości, którą sama zaszyfrowała. Ewa mogłaby również wypróbować wartości g i sprawdzić, czy ma małe wartości. ${\displaystyle \ {\textbf {f}}'\cdot {\textbf {h}}{\pmod {q}}}$${\ Displaystyle \ {\ textbf {g}} '\ cdot {\ textbf {h}} ^ {-1} {\ pmod {q}}}$

Możliwe jest zamontowanie ataku typu „ meet-in-the-middle”, który jest potężniejszy. Może skrócić czas wyszukiwania o pierwiastek kwadratowy. Atak opiera się na właściwości, która . ${\displaystyle \ {\textbf {f}}\cdot {\textbf {h}}=p{\textbf {g}}{\pmod {q}}}$

Ewa chce znaleźć i takie, które trzyma i takie, że mają własność ${\ Displaystyle \ {\ textbf {f}} _ {1}}$${\ Displaystyle \ {\ textbf {f}} _ {2}}$${\displaystyle \ {\textbf {f}}={\textbf {f}}_{1}+{\textbf {f}}_{2}}$

${\ Displaystyle \ lewo ({\ textbf {f}} _ {1} + {\ textbf {f}} _ {2} \ prawo) \ cdot {\ textbf {h}} = {\ textbf {g}} { \pmod {q}}}$

${\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf {h }}{\pmod {q}}}$

Jeśli f ma d jedynki i N - d zer, to Ewa tworzy wszystko możliwe iw których obie mają długość (np. pokrywa najniższy współczynnik f i najwyższy) z d /2 jedynkami. Następnie oblicza dla wszystkich i porządkuje je w pojemnikach na podstawie pierwszych k współrzędnych. Następnie oblicza wszystko i porządkuje je w pojemnikach nie tylko na podstawie pierwszych k współrzędnych, ale także na podstawie tego, co się stanie, jeśli dodasz 1 do pierwszych k współrzędnych. Następnie należy sprawdzić pojemniki, które zawierają zarówno a i sprawdzić, czy nieruchomość posiada. ${\ Displaystyle \ {\ textbf {f}} _ {1}}$${\ Displaystyle \ {\ textbf {f}} _ {2}}$${\ Displaystyle \ {\ Frac {1} {2}} N}$${\ Displaystyle \ {\ textbf {f}} _ {1}}$${\ Displaystyle \ {\ Frac {1} {2}} N}$${\ Displaystyle \ {\ textbf {f}} _ {2}}$${\displaystyle {\textbf {f}}_{1}\cdot {\textbf {h}}{\pmod {q}}}$${\ Displaystyle \ {\ textbf {f}} _ {1}}$${\displaystyle \ -{\textbf {f}}_{2}\cdot {\textbf {h}}{\pmod {q}}}$${\ Displaystyle \ {\ textbf {f}} _ {1}}$${\ Displaystyle \ {\ textbf {f}} _ {2}}$${\displaystyle \ {\textbf {f}}_{1}\cdot {\textbf {h}}={\textbf {g}}-{\textbf {f}}_{2}\cdot {\textbf { h}}{\pmod {q}}}$

Atak redukcji sieci jest jedną z najbardziej znanych i jedną z najbardziej praktycznych metod złamania NTRUEncrypt. W pewnym sensie można to porównać do faktoryzacji modułu w RSA. Najczęściej używanym algorytmem do ataku redukcji sieci jest algorytm Lenstra-Lenstra-Lovász . Ponieważ klucz publiczny h zawiera zarówno f, jak i g, można spróbować je uzyskać z h . Jednak znalezienie tajnego klucza jest zbyt trudne, gdy parametry NTRUEncrypt są wystarczająco bezpieczne. Atak redukcji sieci staje się trudniejszy, jeśli wymiar sieci staje się większy, a najkrótszy wektor wydłuża się.

Wybrany atak zaszyfrowany jest również sposób, który odzyskuje się tajny klucz K i w ten sposób prowadzi do całkowitego rozpadu. W tym ataku Ewa próbuje uzyskać własną wiadomość z zaszyfrowanego tekstu, a tym samym próbuje uzyskać tajny klucz. W tym ataku Ewa nie ma żadnej interakcji z Bobem.

Jak to działa :

Pierwszy Ewa tworzy tekst zaszyfrowany , tak że i Kiedy Ewa pisze po schodach do rozszyfrowania e (bez faktycznego obliczania wartości ponieważ nie wie, f) dowiaduje : ${\ Displaystyle \ {\ textbf {e}} = c {\ textbf {h}} + c}$${\ Displaystyle \ c = 0 {\ pmod {p}}, c < {\ Frac {q} {2}}}$${\ Displaystyle \ 2c> {\ Frac {q} {2}}}$${\ Displaystyle \ {\ textbf {a}} = {\ textbf {f}} \ cdot {\ textbf {e}} {\ pmod {q}}}$

${\ Displaystyle {\ textbf {a}} = {\ textbf {f}} \ lewo (c {\ textbf {h}} + c \ po prawej) {\ pmod {q}}}$

${\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}{\pmod {q}}}$

${\displaystyle {\textbf {a}}=c{\textbf {g}}+c{\textbf {f}}-qK}$

W którym takie, że ${\ Displaystyle \ K = \ suma k_ {i} x ^ {i}}$

${\ Displaystyle k_ {i} = {\ zacząć {przypadki} 1 \ \ \ qquad {\ tekst {jeśli}} \ ja ^ {th} \ {\ tekst {współczynnik}} \ {\ textbf {f}} \ {\text{i}}\ {\textbf {g}}\ {\text{jest}}\ 1\\-1\qquad {\text{jeśli}}\ i^{th}\ {\text {współczynnik}}\ {\textbf {f}}\ {\text{i}}\ {\textbf {g}}\ {\text{is}}\ -1\\0\ \ \qquad {\text {W przeciwnym razie}}\end{przypadki}}}$

Przykład :

${\ Displaystyle {\ textbf {f}} = -1 + X + X ^ {2} - X ^ {4} + X ^ {6} + X ^ {9} -X ^ {10}}$

${\ Displaystyle {\ textbf {g}} = -1 + X ^ {2} + X ^ {3} + X ^ {5} -X ^ {8} -X ^ {10}}$

Wtedy K staje się . ${\ Displaystyle \ K = -1 + X ^ {2} - X ^ {10}}$

Zmniejszenie współczynników wielomianów mod p naprawdę zmniejsza współczynniki . Po mnożeniu przez , Ewa znajduje: ${\displaystyle \ c{\textbf {g}}+c{\textbf {f}}-qK{\pmod {p}}}$${\ Displaystyle \ {\ textbf {f}} _ {p}}$

${\displaystyle {\textbf {m}}=c{\textbf {f}}_{p}\cdot {\textbf {g}}+c{\textbf {f}}_ {p}\cdot {\textbf {f}}-q{\textbf {f}}_{p}\cdot K{\pmod {p}}}$

${\ Displaystyle {\ textbf {m}} = c {\ textbf {h}} + cq {\ textbf {f}} _ {p} \ cdot K {\ pmod {p}}}$

Ponieważ c zostało wybrane jako wielokrotność p , m można zapisać jako

${\ Displaystyle {\ textbf {m}} = - q {\ textbf {f}} _ {p} \ cdot K {\ pmod {p}}}$

Co oznacza, że . ${\ Displaystyle \ {\ textbf {f}} = - qK \ cdot {\ textbf {m}} ^ {-1} {\ pmod {p}}}$

Teraz, jeśli f i g mają kilka współczynników, które są takie same przy tych samych współczynnikach, K ma kilka niezerowych współczynników i przez to jest małe. Próbując różnych wartości K, atakujący może odzyskać f .

Szyfrując i odszyfrowując wiadomość zgodnie z NTRUEncrypt, atakujący może sprawdzić, czy funkcja f jest poprawnym tajnym kluczem, czy nie.

Poprawa bezpieczeństwa i wydajności

Używając najnowszych sugerowanych parametrów (patrz poniżej ), kryptosystem klucza publicznego NTRUEncrypt jest bezpieczny dla większości ataków. Jednak nadal trwa walka między wydajnością a bezpieczeństwem. Trudno jest poprawić bezpieczeństwo bez spowalniania prędkości i na odwrót.

Jednym ze sposobów na przyspieszenie procesu bez szkody dla skuteczności algorytmu jest wprowadzenie pewnych zmian w tajnym kluczu f . Najpierw skonstruuj f takie, że , w którym F jest małym wielomianem (tj. współczynniki {-1,0, 1}). Konstruując f w ten sposób, f jest odwracalnym mod p . W rzeczywistości oznacza to, że Bob nie musi faktycznie obliczać odwrotności i że Bob nie musi przeprowadzać drugiego kroku deszyfrowania. Dlatego konstruowanie f w ten sposób oszczędza dużo czasu, ale nie wpływa na bezpieczeństwo NTRUEncrypt, ponieważ jest tylko łatwiejsze do znalezienia, ale f nadal jest trudne do odzyskania. W tym przypadku f ma współczynniki różne od -1, 0 lub 1, z powodu mnożenia przez p . Ale ponieważ Bob mnoży przez p, aby wygenerować klucz publiczny h , a później redukuje zaszyfrowany tekst modulo p , nie będzie to miało wpływu na metodę szyfrowania. ${\ Displaystyle \ {\ textbf {f}} = 1 + p {\ textbf {f}}}$${\ Displaystyle \ {\ textbf {f}} ^ {-1} = 1 {\ pmod {p}}}$${\ Displaystyle \ {\ textbf {f}} _ {p}}$

Po drugie, f można zapisać jako iloczyn wielu wielomianów, tak że wielomiany mają wiele zerowych współczynników. W ten sposób trzeba przeprowadzić mniej obliczeń.

W większości komercyjnych zastosowań NTRUEncrypt używany jest parametr N =251. Aby uniknąć ataków kratowych, ataków brute force i ataków typu „meet-in-the-middle”, f i g powinny mieć około 72 niezerowe współczynniki.

Według najnowszych badań za bezpieczne uważane są następujące parametry:

Tabela 1: Parametry

	n	Q	P
Umiarkowane bezpieczeństwo	167	128	3
Standardowe zabezpieczenia	251	128	3
Wysoki poziom bezpieczeństwa	347	128	3
Najwyższe bezpieczeństwo	503	256	3

Bibliografia

• Jaulmes, E. i Joux, A. Atak z wybranym szyfrogramem przeciwko NTRU. Notatki z wykładów z informatyki; Tom 1880. Materiały z 20. dorocznej międzynarodowej konferencji kryptologicznej na temat postępów w kryptografii. s. 20-35, 2000.
• Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. NTRU: Kryptosystem klucza publicznego oparty na pierścieniu . W Algorithmic Number Theory (ANTS III), Portland, OR, czerwiec 1998, JP Buhler (red.), Lecture Notes in Computer Science 1423, Springer-Verlag, Berlin, 1998, 267-288.
• Howgrave-Graham, N., Silverman, JH & Whyte, W., Meet-In-The-Middle Attack na klucz prywatny NTRU .
• J. Hoffstein, J. Silverman. Optymalizacje dla NTRU . Kryptografia klucza publicznego i obliczeniowa teoria liczb (Warszawa, 11-15 września 2000), DeGruyter.
• AC Atici, L. Batina, J. Fan i I. Verbauwhede. Tanie implementacje NTRU dla wszechobecnego bezpieczeństwa .

Zewnętrzne linki

• Strona techniczna NTRU
• Strona główna IEEE P1363
• Innowacje w zakresie bezpieczeństwa (nabyte NTRU Cryptosystems, Inc.)
• Implementacja licencji Open Source BSD NTRUEncrypt
• Licencja Open Source GPL v2 NTRUEncrypt
• Rozwiązanie strongSwan Open Source IPsec wykorzystujące wymianę kluczy opartą na NTRUEncrypt
• - Wbudowana biblioteka SSL/TLS oferująca zestawy szyfrów wykorzystujące NTRU (wolfSSL)