NTRU

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

NTRU – asymetryczny kryptosystem z kluczem publicznym i prywatnym. Ma dwie cechy dające mu przewagę nad algorytmem RSA i ECC (dla których może stanowić rozwiązanie alternatywne): szybkość i odporność na obliczenia kwantowe. Istnieją dwa algorytmy NTRU: NTRUEncrypt i NTRUSign. Dostępna jest otwarta implementacja NTRU[1].

Prędkość[edytuj]

Ponieważ algorytm NTRU bazuje na odmiennej matematyce (kryptografii opartej na kratach) niż RSA i ECC, ma on inne właściwości kryptograficzne. Dla porównywalnej siły kryptograficznej, NTRU wykonuje znacznie szybciej niż RSA kosztowne operacje klucza prywatnego. Ponadto porównawcza wydajność NTRU rośnie wraz z poziomem wymaganego bezpieczeństwa. Gdy rozmiary kluczy wzrostają n razy, liczba operacji RSA/sekundę spada , podczas gdy spadek NTRU jest rzędu .

Zwykle prędkość algorytmów asymetrycznych nie porównuje się do prędkości algorytmów symetrycznych; algorytmy symetryczne są o wiele szybsze. Jednakże według dokumentu opublikowanego przez Department of Electrical Engineering, Uniwersytetu w Leuven

Quote-alpha.png
Przy korzystaniu z nowoczesnych procesorów kart graficznych (GPU) GTX280 może być osiągnięta przepustowość do 200 000 szyfrowań na sekundę na poziomie bezpieczeństwa 256 bitów. Porównując to do szyfru symetrycznego (nie jest to popularne porównanie), jest to tylko około 20 razy wolniej niż niedawne implementacje (również na GPU) algorytmu AES[2].

Dotyczy to zoptymalizowanych ze względu na szybkość zestawów parametrów z ostatniej wersji 1363.1. Zestawy te z upływem czasu uległy zmianie, ale ogólny wynik wciąż jest aktualny: NTRU jest bardzo szybki na równoległe procesory.[potrzebny przypis]

Odporność na ataki komputerów kwantowych[edytuj]

W odróżnieniu od RSA lub ECC, nie jest obecnie znana podatność NTRU na ataki z wykorzystaniem komputera kwantowego. Komputer kwantowy za pomocą algorytmu Shora byłby w stanie w rozsądnym czasie złamać RSA lub ECC jakiegokolwiek praktycznego rozmiaru klucza. Dla kontrastu, nie jest znany obecnie kwantowy atak na NTRU, który znacząco redukowałby jego bezpieczeństwo. National Institute of Standards and Technology (NIST), wydał w 2009 ekspertyzę, w której wskazał na istniejące alternatywy dla publicznego klucza szyfrowania i podpisów, które nie są narażone na algorytm Shora. W dokumencie pada stwierdzenie, że

Quote-alpha.png
Z różnych systemów kryptograficznych opartych na kratach, które zostały opracowane, rodzina algorytmów kryptograficznych NTRU wydaje się być najbardziej praktyczna.

Wśród atutów NTRU wymieniana jest duża wydajność i stosunkowo niewielki rozmiar klucza[3].

Standaryzacja[edytuj]

  • Standard IEEE 1363.1, wydany w 2008 roku, standaryzuje opartą na kratach kryptografię klucza publicznego, zwłaszcza NTRUEncrypt[4].
  • Standard X9.98 standaryzuje opartą ona kratach kryptografię klucza publicznego zwłaszcza NTRUEncrypt, jako część standardów X9 branży usług finansowych[5].

Implementacje[edytuj]

Implementacja NTRU jest dostępna jako otwarta biblioteka Javy[1], jak i zamknięte źródła, możliwe do pobrania za opłatą[6].

Historia[edytuj]

Pierwsza wersja systemu, która była nazywana po prostu NTRU, powstała około 1996 roku odkryta przez trzech matematyków (J. Hoffstein, J. Pipher i J. H. Silverman). W 1996 roku ci matematycy wraz z D. Liemanem założyli NTRU Cryptosystems, Inc. i otrzymali patent na swój kryptosystem[7].

W ciągu ostatnich dziesięciu lat pracuje się nad poprawą kryptosystemu. Od pierwszej prezentacji dokonano pewnych zmian w celu poprawy zarówno wydajności systemu jak i jego bezpieczeństwa. W 2009 roku firma została przejęta przez Security Innovation – firmę zajmującą się bezpieczeństwem oprogramowania[8].

Przypisy

  1. a b ntru.sf.net: NTRU: Quantum-Resistant High Performance Cryptography (ang.). SourceForge. [dostęp 2011-11-06].
  2. Hermans J., Vercauteren F., Preneel B.: Speed records for NTRU (ang.). Department of Electrical Engineering, University of Leuven. [dostęp 2011-11-06].
  3. Ray A. Perlner, David A. Cooper: Quantum Resistant Public Key Cryptography: A Survey (ang.). National Institute of Standards and Technology. [dostęp 2011-11-07].
  4. IEEE P1363: Standard Specifications For Public-Key Cryptography (ang.). IEEE Standards Association. [dostęp 2011-11-07].
  5. Security Innovation’s NTRUEncrypt Adopted as X9 Standard for Data Protection (ang.). BusinessWire, 2011-04-11. [dostęp 2011-11-07].
  6. NTRU Cryptography (ang.). Security Innovation, Inc.. [dostęp 2011-11-07].
  7. Elizabeth D. Robertson: NTRU Public Key Alghoritms IP Assurance Statement for 802.15.3 (ang.). NTRU Cryptosystems, Inc., 2002-08-01. [dostęp 2011-11-07].
  8. Security Innovation acquires NTRU Cryptosystems, a leading security solutions provider to the embedded security market (ang.). Security Innovation, 2009-07-22. [dostęp 2011-11-07].

Linki zewnętrzne[edytuj]