NTRU

NTRU je částečně patentovaný šifrovací systém, který používá pro zašifrování a dešifrování dat asymetrickou kryptografii založenou na celočíselných mřížích. NTRU obsahuje dva algoritmy: NTRUEncrypt (ve veřejné doméně^[1]), který slouží pro šifrování, a NTRUSign (patent vlastněn NTRU Cryptosystems, Inc.) určený pro elektronické podepisování. Na rozdíl od nejpopulárnějších asymetrických šifrovacích algoritmů založených například na problému hledání prvočíselného rozkladu nebo na problému nalezení diskrétního logaritmu, které jsou teoreticky prolomitelné pomocí kvantového počítače Shorovým algoritmem, není pro NTRU znám žádný útok pomocí kvantového počítače (postkvantová kryptografie). Také jeho výkonnost je prokazatelně lepší. K dispozici je uzavřená placená implementace NTRU, ale také volně dostupná verze jako otevřený software.^[2]

Historie

První verze nazvaná NTRU byla vytvořena v roce 1996 matematiky Jeffrey Hoffsteinem, Jill Pipherovou a Josephem H. Silvermanem. Stejného roku se tvůrci spojili s D. Liemanem a založili společnost NTRU Cryptosystems a tento kryptosystém nechali patentovat.^[3] V roce 2009 byla firma koupena společností Security Innovation zabývající se softwarovou bezpečností.^[4] Roku 2013 přišli Damien Stehlé a Ron Steinfeld s novou verzí algoritmu.^[5] Nyní je tak dostupná verze zdarma (bez patentových omezení).^[6]

Výkonnost

NTRU provádí nákladné operace se soukromými klíči rychleji než RSA při ekvivalentní kryptografické síle. S rostoucí velikostí klíče počet vykonaných operací za sekundu u RSA roste kubicky, zatímco u NTRU roste jen kvadraticky.

Podle Oddělení Elektrotechniky na Univerzitě v Lovani: „S použitím Grafické karty GTX280 může být dosaženo až 200 000 šifrování za sekundu na úrovni zabezpečení 256 bitů. Když to porovnáme s rychlostí symetrické šifry (běžně se neporovnávají), je pouze asi 20krát pomalejší než poslední implementace AES.“^[7]

Odolnost vůči útokům pomocí kvantových počítačů

Na rozdíl od RSA a Kryptografie nad eliptickými křivkami (angl. ECC), není u NTRU známá žádná zranitelnost vůči útokům pomocí kvantového počítače. NIST napsal ve svém přehledu z roku 2009 že, „NTRU je vhodná alternativa jak pro šifrování s veřejným klíčem, tak pro elektronické podpisy, která není zranitelná Shorovým algoritmem“ a „z různých šifrovacích systémů založených na mřížích, které byly vyvinuty, se zdá být NTRU nejpraktičtější“.^[8]

Standardizace

• Standard IEEE 1363.1, vydaný v roce 2008, standardizuje asymetrickou kryptografii založenou na mřížích, zejména NTRUEncrypt.^[9]
• Standard X9.98 standardizuje asymetrickou kryptografii založenou na mřížích, zejména NTRUEncrypt, jako část standardu X9 pro odvětví finančních služeb.^[10]

Implementace

NTRU je dostupné jako open source knihovna v jazyce C nebo Java^[2] a uzavřená placená knihovna.^[11]

Reference

V tomto článku byl použit překlad textu z článku NTRU na anglické Wikipedii.

1. ​Security Innovation Makes NTRUEncrypt Patent-Free. web.archive.org [online]. 2019-02-18 [cit. 2024-04-29]. Dostupné v archivu pořízeném z originálu dne 2019-02-18. 
2. BUKTU, Tim. NTRU: Quantum-Resistant cryptography [online]. NTRU Cryptosystems, Inc. [cit. 2013-02-04]. Dostupné v archivu pořízeném dne 2013-01-29. Je zde použita šablona {{Cite web}} označená jako k „pouze dočasnému použití“.
3. ROBERTSON, Elizabeth D. RE: NTRU Public Key Algorithms IP Assurance Statement for 802.15.3 [online]. IEEE, August 1, 2002 [cit. 2013-02-04]. Dostupné online. Je zde použita šablona {{Cite web}} označená jako k „pouze dočasnému použití“.
4. Security Innovation: Security Innovation acquires NTRU Cryptosystems, a leading security solutions provider to the embedded security market, tisková zpráva, [cit. February 4, 2013], Dostupné on-line.Je zde použita šablona {{Cite press release}} označená jako k „pouze dočasnému použití“. Archivováno 17. 12. 2013 na Wayback Machine. Archivovaná kopie. www.securityinnovation.com [online]. [cit. 2014-02-13]. Dostupné v archivu pořízeném z originálu dne 2013-12-17. 
5. https://eprint.iacr.org/2013/004.pdf - Making NTRUEnrypt and NTRUSign as Seure as Standard Worst-Case Problems over Ideal Latties
6. https://globenewswire.com/news-release/2017/03/28/945815/0/en/Security-Innovation-Makes-NTRUEncrypt-Patent-Free.html - Security Innovation Makes NTRUEncrypt Patent-Free
7. HERMANS, Jens; VERCAUTEREN, Frederik; PRENEEL, Bart. Speed Records for NTRU. Redakce Pieprzyk Josef. Topics in Cryptography - CT-RSA 2010. San Francisco, CA: Springer Berlin Heidelberg, 2010, s. 73–88. Dostupné online [cit. February 4, 2013]. ISSN 0302-9743. ISBN 978-3-642-11924-8. DOI 10.1007/978-3-642-11925-5_6. Je zde použita šablona {{Cite journal}} označená jako k „pouze dočasnému použití“.
8. PERLNER, Ray A.; COOPER, David A. Quantum resistant public key cryptography: a survey. Redakce Seamons Kent. Proceedings of the 8th Symposium on Identity and Trust on the Internet. New York, NY: ACM, 2009, s. 85–93. Dostupné v archivu pořízeném dne 2012-05-14. ISBN 978-1-60558-474-4. DOI 10.1145/1527017.1527028. Je zde použita šablona {{Cite journal}} označená jako k „pouze dočasnému použití“. Archivovaná kopie. middleware.internet2.edu [online]. [cit. 2014-02-13]. Dostupné v archivu pořízeném z originálu dne 2012-05-14. 
9. grouper.ieee.org [online]. [cit. 2014-02-13]. Dostupné v archivu pořízeném dne 2014-12-01. 
10. http://www.businesswire.com/news/home/20110411005309/en/Security-Innovation%E2%80%99s-NTRUEncrypt-Adopted-X9-Standard-Data
11. Archivovaná kopie. www.securityinnovation.com [online]. [cit. 2014-02-13]. Dostupné v archivu pořízeném dne 2013-10-27.